Networking Assignment Help: Explain the RSA Public Key Encryption Scheme in detail...

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 = M^e mod N

And to decrypt the message C compute

M = C^d 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 = M^e mod N = 8⁵ = 32768 = 17 mod 85

Decrypt C to recover the message M by

M = C^d mod N = 17⁷ = 410,338,673

= 12,434,505 * 85 + 8 = 8 mod 85