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 = 209 and e = 59. (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. (b) Calculate GCD(e, (p ? 1)(q ? 1)). Is e a valid encryption key? (c) What is the decryption key: d = 14, d = 119, or d = 67? Justify your answer. (d) You receive the encrypted message a = 9. What is the (decrypted) message? Note: You might find slides 35, 37, and 38 of the lecture notes very helpful for this problem.

Explanation / Answer

Clearly ,As RSA is an asymmetric cryptography algorithm .
And in this we have two types of Keys ....

1....Public Key and the Other is Private key

The public key ,i.e. 'n' is basically the product of two prime numbers
and the private key is calculated using this same two prime numbers.

Now ,We have n=209 (GIVEN)
Using Hit and trial method ,we can get that 209 is basically the
product of two prime numbers that are 19 and 11 respectively.(Part-a)

Now let p=19 and q=11;

Let us denote ?(n)=(p-1)(q-1).
Now for 'e' to be a valid encryption key ,it should be

1)Not a factor of n;
2)An integer
3)It should contain its value between 1 and ?(n) (Both excluded)

As e=59(Given)
Clearly 59 is not a factor of n i.e. -209 ,hence 1st point satisfied.
Also 59 is an integer (2nd point satisified)
Now ?(n)=180 ,Hence 3rd point is also satisfied.

Hence 'e' is a valid encryption key.
Now GCD(e,(p-1)(q-1))=GCD(58,(18)(10))=GCD(59,180)=1;{B part answered}

C.) Now ,as the private key i.e. decryption key 'd' can be calculated as

       d=(l*?(n) + 1) / e ......(1) ,where l is an integer;
    
        Now ,Putting the different values of 'd' in (1) i.e. above equation and
        checking if the value of l comes to be an integer or not
   
    When d=14,then l=4.583333 (Not an integer,Hence d=14 is not possible);
    When d=119,then l=39 (An integer,Hence d=119 is possible);
     When d=67 ,then l=21.95555 (Not an integer,Hence d=67 is not possible);

D. ) When the encrypted message c=9(Given)
     Then ,the decrypted message =pow(c,d)%(n)
      Where pow(c,d) refers to the c raised to the power d.i.e. 'c' multiplied 'd' times.
      And '%' refers to modulus.
   Hence decrypted message = pow(9,119)%209 =5 ;
   As 'e' is the 5th letter of english alphabet ,
   Hence Decrypted message='5' or 'e' .

--------------****************************-------------------
   All the best ,Thank U ......................
    

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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