Q)Explain the RSA Public
Key Encryption Scheme in detail.In particular ,how do the encryption and
decryption algorithms work? Explain also how you choose the public and private
keys.Suppose a user picks n=17*5; i.e .,p=17 and q=5.How should he pick the public
key and the private key (i.e., d and e)? Give the encryption and decryption
algorithms.
Sol:
RSA Public Key Encryption which was invented by
Cocks (GCHQ), independently, by Rivest, Shamir and Adleman (MIT). Say for
example let ‘p’ and ‘q’ is the two large prime numbers.
Let N = p*q be the modulus, then Choose ‘e’
relatively prime to (p-1)*(q-1)
Find d such that e*d = 1 mod (p-1)*(q-1)
Here the Public key is given by (N, e) and the Private
Key is given by ‘d’.
The encryption as well as the decryption algorithm
works as follows:
To encrypt the message M compute
C = Me mod N
And to decrypt the message C compute
M = Cd mod N
Please recall that e and N are public, hence if
attacker can factor N, then he can definitely use ‘e’ to easily find the value
of ‘d’ since e*d = 1 mod (p-1)*(q-1)
Factoring the modulus will break the RSA, therefore
it is not known that whether the factoring is the only one way to break RSA.
Suppose a user picks N=17*5; i.e., p=17 and q=5.
Hence N= 85,
(P-1)*(q-1) = 16*4=64
Choose ‘e’ such that it is relatively prime to 64.
Hence e=5
Find‘d’ such that e*d = 1 mod 64,
we find that d = 7 works
Public
key: (N, e) = (85, 5)
Private
Key: d = 7
Encryption as well as decryption
algorithm works as follows:
Public
key: (N, e) = (85, 5)
Private
Key: d = 7
Suppose message M = 8
Cipher text C is computed as
C = Me mod N = 85
= 32768 = 17 mod 85
Decrypt C to recover the message
M by
M = Cd mod N = 177
= 410,338,673
= 12,434,505 * 85 + 8 = 8 mod 85
