You are using the RSA algorithm to encrypt and decrypt messages. Your public key

Question

You are using the RSA algorithm to encrypt and decrypt messages. Your public key is n = 143 and e = 37.

(a) Determine the prime factorization of n; that is, find your prime numbers p and q. Note that this is the expensive step that Eve would have to undertake to “crack” your encryption; it should be fairly straightforward with the small n used here.

(b) Calculate GCD(e, (p 1)(q 1)). Is e a valid encryption key?

(c) What is the decryption key: d = 7, d = 13, or d = 25? Justify your answer.

(d) You receive the encrypted message a = 125. What is the (decrypted) message?

Explanation / Answer

(a) Determine the prime factorization of n; that is, find your prime numbers p and q.
Ans:-
Given n=143, e=37.
According to RSA encryption algorithm,
n=p*q (where p anmd q are prime numbers).

Therefore 143=p*q
sqrt(143)=11.9.
Hence we have to look for prime numbers till 11. i.e 1,3,5,7,11
So it will be 11*13=143
so p=11,q=13

b) Calculate GCD(e, (p 1)(q 1)). Is e a valid encryption key?
Ans:- p=11,q=13
p-1=10, q-1=12
   e=37
   (n)=(p 1)(q 1)=120
   GDC(37,10*12)=GDC(37,120)
   =1
   According to RSA encryption algorithm,Choose e such that 1 < e < (n) and e and (n) are coprime.
  
   hence e is a valid encryption key.
  
c)What is the decryption key: d = 7, d = 13, or d = 25?
Ans:- According to RSA encryption algorithm,Compute a value for d such that (d * e) % (n) = 1.
For d=7;
(d * e) % (n)=(7*37)%120=19
   hence d is not 7.
For d=13;
(d * e) % (n)=(13*37)%120=1
   hence d is 13.
  
   For d=25;
(d * e) % (n)=(25*37)%120=85
   hence d is not 25.
  
d)You receive the encrypted message a = 125. What is the (decrypted) message?
Ans:-
Given encrypted message a = 125
n=143
   d=13

private key(d,n)
   To decrypt a message we use the private key(13,143)
   The decryption of message = a^d % n
   =125^13%143
  =1.818989403545856475830078125e+27%143
                               =86 Ans

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.