Question

Discrete Mathematics - RSA Algorithm and Mod

These are problems concerning the RSA algorithm and Modulo.

A. In RSA, suppose bob chooses p = 3 and q = 43. Determine one correct value of the public exponent e, your choice should be the smallest positive integer that is greater than 1. Justify your answer.

B. For the e's value you chose above, compute the corresponding secret exponent d. Show your work.

C. Compute 5⁴⁰Mod13

D. Compute 5^-1Mod11

Answer 1

ANSWER:

• Select two primes p and q.

Here , p=3 and q=43.

• Find n = p*q = 3×43 = 129.

• Calculate f(n) = (p-1)*(q-1) = (3-1)*(43-1) = 2*42 =84.

• Select e such that gcd ( f(n) , e )=1. ; 1 < e < f(n)

Let e=25.

• Calculate d such that (d.e)mod f(n) = 1.

• Use Euclid's algorithm to find d=e^-1 mod f(n)

• Use 84k+1 = 169 , 253 , 337 , 421 , 505 , 589 , 673 , 757 , 841 , 925 ,.....

• Check which of the above is divisible by 25.

• 925 is divisible by 25 giving d=925/25 = 37.

Thus , e =25 and d=37

Therefore, key 1 = { 25,129} and key 2 ={ 37, 129}.

Verification :

We know that ,

If C = p^e mod n then , P = C^d mod n.

Here , p = 3 , e =25 and n=129

Then C = 3²⁵ mod 129 = 48.

Now , Let us find C^d mod n and this should give out p=3 again.

we have , C=48 , d=37 and n=129.

Then , 48³⁷ mod 129 = 3 (=p).   hence verified!

C : 540 mod 13 = 7.