Can you please help me with this RSA Question? Decipher the following message to
ID: 3587831 • Letter: C
Question
Can you please help me with this RSA Question?
Decipher the following message to get the initials of an organization: 88 17 2 Each letter is encoded using the same 0-25 scheme as the previous problem, then individually encrypted in RSA with public key (e = 23, n = 55). For example, the message "HEY" wll be encoded and encrypted as follows. The letter H corresponds to 7, and 723 mod 55 equals 13. The letter E corresponds to 4, and 423 mod 55 equals 9. The letter Y corresponds to 24, and 2423 mod 55 equals 19. So the mssage "HEY", when encoded and encrypted, reads as follows. 13 9 19 Solve for the private key d, then decrypt and decode the "8 8 17 2" message. What inials do you find?Explanation / Answer
So, first let’s list out the details given to us..
Encoded cypher text is : 8 8 17 2
(It has to be processed separately)
public key e=23, n=55
So, in order to decrypt the cypher text, the following formula is used..
M = Cd mod n
where M is plain text message, C is a cypher text, d is the secret key missing here.
There’s a formula to obtain ‘d’ using ‘e’ and ‘n’ which is
[d * e] mod (n) = 1
So first we need to find (n)
As per RSA, ‘n’ is a multiplication of 2 prime numbers p and q. Here, n = 55. So, if we factorize 55, we will get 1, 5, 11 and 55 are its factors.
Among which 5 and 11 are the only prime numbers.
So, we will take p = 5 and q = 11. n = p * q = 5 * 11 = 55 is satisfied.
(n) = (p-1) (q-1) = 4 * 10 = 40
Therefore, d * 23 mod 40 = 1
Now, try to put different value of ‘d’ to find which is the value satisfying above equation.
d=1, 23 mod 40 = 23 1
d=2, 46 mod 40 = 6 1
d=3, 69 mod 40 = 29 1
d=4, 92 mod 40 = 12 1
d=5, 115 mod 40 = 35 1
d=6, 138 mod 40 = 18 1
d=7, 161 mod 40 = 1
So, d = 7
So, let’s decrypt the cypher text 8 8 17 2 number by number
C = 8, M = 87 mod 55 = 2
C = 17, M = 177 mod 55 = 8
C = 2, M = 27 mod 55 = 18
So, plain text is 2 2 8 18
Now, decoding it as per 0-25 scheme, where A is 0 and Z is 25, the plain text becomes CCIS.
Do comment if there’s any query. I’ll surely address it.
Thank you. :)