Assignment #3
1. For n=pq, where p and q are distinct odd primes, define
A,(n) (P-l)(q-l).
gcd(p-l,q-l)
Suppose that we modify the RSA cryptosystem by requiring that ed=l mod I,,(n).
a. Prove that encryption and decryption are still inverse operations in this modified cryptosystem.
b. Ifp=37, q=79, and e=7, compute d in this modified cryptosystem, as well as in the orjginal
RSA cryptosystem.
2. A common way to speed up RSA decryption incorporates the Chinese Remainder Theorem, as
follows. Suppose that dk(y)=yd mod nand n=pq. Define dp=d mod (P- l) and dq=d mod (q-l); and
let Mp=q-l mod p and Mq=p-l mod q. Then, consider the ollowing algorithm:
Algorithm 1. CRT -Optimized RSA Decryption (n, dp , dq , Mp , M q , y)
xp~~pmodp
Xq ~ yt" mod q
x ~ Mpqxp + Mqpxq mod n
return (x)
The Algorithm 1 replaces an exponentiation modulo n by modular exponentiations modulo p and
q. Ifp and q are I-bit integers and exponentiation modulo an I-bit integer takes time cP, then the
time to perform the required exponentiation is reduced from c(2l)3 to 2cP, a saving of 75%. The
final step, involving the Chinese Remainder Theorem, require O(F) if dp , dq , Mp , and Mq have
been pre-computed.
a. Prove that the value x returned by Algorithm 1 is, in fact, yd mod n.
b. Given thatp=1511, q=2003, and d=1234577, compute dp, dq , Mp, and Mq .
c. Given the above values ofp, q, and d, decrypt the ciphertexty=152702 using Algorithm 1.
iA. 'l<r" jol( -1 dj{~(r-1) rwodt ::: J 01 ~
=
LXl- : l~ ~ ~ t.....t (~-I)~ dJ."..J ""
;>. -:>-
'j1'n\9- ')(" Nt?,ll(y f M,"P ~~ .-l f'\. ~ (.h,~ ~~r.I,,,:7~
~rJ...~f\ =- ~.
~. W 1'-1 p).) [}t77 wJ Q5 Ii - i'r ~f)7
:1-
~" ol""'( '/,-1 ::: 11~'It7) 1l>'cI. (l.tlO),-I):::. ~ \3ltS
;0
fiAp ;: ~-I .-t r" ~-1 '(l\>'~A Ii ::;. 777
Mt ;: rlll...J. t= I) 1[-' mJ ~Jy" ~ 7'7
(,. . 1-;. j.Ly 4::: I ~ 17 OJ, ~ I~ f:t o7 I".., \ ,.. )'tfd
I .
'X r_ cJ", ~ '& ;:' 1'S~ol~S 1'l"& ),oN~ '" ,o~7
t.-~ _ i. JAf,H17?;lI.\1Ij,'oBlmO~ 1S11~~.
i M\> tXy-t ~r /)(1; rrJf\ - Til r- ~
==
::- l4-lf , ).If 7
3. Consider an EIGamal scheme with a common prime q=71 and a generator g=7.
a. If B has public key YB=3 and A chose the random integer k=2 , what is the ciphertecxt of
M=30?
b. If A now chooses a different value of k, so that the encoding of M=30 is C=(59, C2), what is
the integer C2?
b 5T~ r R,...J If A~ !?
C,-::: /V''f/ ..J{=3° · j?:>-br/ =1
4. On the elliptic curve over the real numbers I = X 3 - 36x, let P=( -3.5 9.5) and Q=( -2 .5, 8.5).
Find P + Q and 2P.
r:A.~ 12 -11 = J /; -1.r ':: - \
~'2-"" 'X \ -),r- ( -~S)
1?J-;.. J\'J-- IX \ -)~ :: \-1)z- - t~ JJ- ~ AJ).= 7
10"" (IxY--'X3}\ - ~l';' c,J -1) (-I) - P-:= I
P-f(A :: ([. l)
~,. ~'X'I2. of- a. _ ~:l.t~,S)~-+ t-3-6)__ i..
}\~~ 7/j1 - d" I,f ,- 7'
'l'J:: X-yr.\:;. ~ r-d-HS);: l~ I
iJa::: «X,- IXI;/J\-~, :: (--"s-7"')* - ('f=-f.~.
'2-f" C]. \7'> I, ( . !)
5. Consider the elliptic curve over Z23: l=x 3+x+ 1 mod 23. P lease list all the non-negative points
in the quadrant from (0, 0) through (22, 22) that satisfy th equation mod 23.
"'(.. IX~ t~ \ ywo(~. ~.~? ;1.
() I ~ I, )..l
\ 6 ~ 1. ,b
1- II 7W /
3 ~ '?\ 10. (:1.:>
~ 0 ¢)eY ~o, '-?T:
5- Ib ';frA/ 4· ,r·
b fh ~- 4, ,1·
1 ~ ~ fl. 1;2.,
g yvo /
'S 7,11;
i ? ~
[to :Ll.
, )'\'\>
~
/
3, w
"
1'2
f?-
t6
~
~
~
Cf, It
7,16
l {f )...:L rw /
tV\? /'
t) 10
Ib tor yv.J /
,J
'1 rq
~
jPY
-? .w
3. W
(1 ).. }-er f, rY
].,A) . ,]. M ~
21 14> r1P /
Yl-- 22. yt.O /'
MtJi.
( 0 .1).
-r'>t F :
(. l? ))..) l \, 1), (I , fb). (3, (0) ,(3, I'). \~, {») .(S-, ~), l5JV
lb. tt) ,(6 . ,~) , (1. (J), (?, ,~), (1. )),(1,,6), ('•. ~)"V+.2()(rl/~)
U2, r1J, V1;, ] ), (~ (I~. r6), (r), '?), U7, Jl». U~, -»}, s, ~
VI' n) Gi" (~
