Assume you are to apply the RSA algorithm. You decided to choose the prime numbers p and q as follows: p= 7 and q= 11. You also selected e= 13. (a) What is the public key that you want to advertise? (Hint: find N) (b) What is the totient value: (N) (c) Fi

Assume you are to apply the RSA algorithm. You decided to choose the prime numbers p and q as follows: p= 7 and q= 11. You also selected e= 13. (a) What is the public key that you want to advertise? (Hint: find N) (b) What is the totient value: (N) (c) Fi

a)

p=7, q=11
n=p*q, n=77

e =13

the public key is (n, e) (77,13)

=====================================================================================

b)

Φ(n) = (p-1)(q-1)
Φ(n) = (6)*(10) = 60

=====================================================================================

c)

e*d mod Φ(n) =1
13*d mod 60 =1

step 1: Euclidean alogrithm
60x+13y=1
60 = 4(13)+8
13 = 1(8)+5
8 = 1(5)+3
5 = 1(3)+2
3 = 1(2)+1

step 2: Back substitution
1= 3 - 1( 2 )
1 = 3 -1 (5 - 1(3))
1 = 2( 3 ) - 1(5)
1 = 2(8 -1(5)) - 1(5)
1= 2(8 ) - 3(5)
1= 2(8) - 3(13-1(8))
1 = 5(8)-3(13)
1= 5(60 - 4(13))-3(13)
1 = 5(60) - 23(13)

d=-23
it is negative so one more step
d= Φ(n)-d

d= 60-23
=37

d will act as the private key. our private key is 37.