Perform encryption and decryption using the RSA algorithm as

Perform encryption and decryption using the RSA algorithm, as in Figure for the following:

p=3;q=11, e=7;M=5

p=5;q=11, e=3;M=9

p=7;q=11, e=17;M=8

Key Generation by Alice

Select p, q

p and q both prime, pq

Calculate n=p×q

Calcuate (n)=(p1)(q1)

Select integer e

gcd ((n), e)=1;1<e<(n)

Calculate d

de1(mod(n))

Public key

PU={e, n}

Private key

PR={d, n}

Encryption by Bob with Alice’s Public Key

Plaintext:

M<n

Ciphertext:

C=Memodn

Decryption by Alice with Alice’s Public Key

Ciphertext:

C

Plaintext:

M=Cdmodn

Key Generation by Alice
Select p, q	p and q both prime, pq
Calculate n=p×q
Calcuate (n)=(p1)(q1)
Select integer e	gcd ((n), e)=1;1<e<(n)
Calculate d	de1(mod(n))
Public key	PU={e, n}
Private key	PR={d, n}

Solution

1)

n = p x q = 3 x 11 = 33

j(n) = (p-1) x (q-1) = 2 x 10 = 20

gcd(j(n), e) = gcd(20, 7) = 1

d e^-1(mod j(n))

d x e mod j(n) = 1

7d mod 20 = 1

d = 3

So:    Public Key         pu = {e, n} = {7, 33}

       Private Key        pr = {d, n} = {3, 33}

Encryption:

       C = M^e mod n = 5⁷ mod 33 = 14

Decription:

              M = C^d mod n = 14³ mod 33 = 5

2)

n = p x q = 5 x 11 = 55

j(n) = (p-1) x (q-1) = 4 x 10 = 40

gcd(j(n), e) = gcd(40, 3) = 1

d e^-1(mod j(n))

d x e mod j(n) = 1

3d mod 40 = 1

d = 27

So:    Public Key         pu = {e, n} = {3, 55}

       Private Key        pr = {d, n} = {27, 55}

Encryption:

C = M^e mod n = 9³ mod 55 = 14

     Decription:

              M = C^d mod n = 14²⁷ mod 55 = 9

3)

n = p x q = 7 x 11 = 77

j(n) = (p-1) x (q-1) = 6 x 10 = 60

gcd(j(n), e) = gcd(60, 17) = 1

d e^-1(mod j(n))

d x e mod j(n) = 1

17d mod 60 = 1

d = 53

So:    Public Key         pu = {e, n} = {17, 77}

       Private Key        pr = {d, n} = {53, 77}

Encryption:

       C = M^e mod n = 8¹⁷ mod 77 = 57

     Decription:

              M = C^d mod n = 57⁵³ mod 77 = 8