Handwritten answers will not be accepted due to legibility issues. All such answ

Question

Handwritten answers will not be accepted due to legibility issues. All such answer will receive a thumbs down. Please do not waste your time as well as mine.

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

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

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

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

Figure 9.5 The RSA Algorithm Key Generation by Alice Select p, q pand q both prime, p q Calculate n = p × q calcuated(n) = (p-1)(q-1) Select integer e gcd ((n), e) = 1:1

Explanation / Answer

i) Given, p=3,q=11,e=7 and M=5

Now,

* calculate n = p*q = 3*11 = 33 (Here,p and q are both primes and p!=q)

* calculate (n) = (p-1)*(q-1) = 2*10 = 20.

* Given, e=7 we are having "e" such that it is relatively prime to (n) i.e, 7 is relatively prime to 20 (no common factors)

* so,the pair (e,n) is our public key that is used to encrypt i.e, (7,33) is public key.

* Now, we have to calculate "d" such that d = e^(-1) mod (n) i.e,

d*e = 1 mod (n)

7*d = 1 mod 20

To, find "d" use Extended euclidean algorithm as e and d are prime numbers

(n) =20 and e =7

20 = 2*7 + 6 (write "(n)" i.e,20 in terms of "e" i.e,7)

7 = 1*6 + 1 (until remainder is 1)

Now, back substitution

1 = 7 - 1*6

1 = 7 - 1*(20-2*(7))

1 = 3*(7) - 1*(20)

Thus, value of d is "3" i.e, d=3

* Now, private key (d,n) is (3,33)

* Given, plain text M=5 (M<n)

so,Ciphertext C = M^e mod n = 5^7 mod 33 = 78125 mod 33 = 14

"14" is the ciphertext for plaintext "5"

* Decryption using ciphertext C=14 as M = c^d mod n = 14^3 mod 33 = 2744 mod 33 = 5 that is nothing but our pain text M=5.

ii) Given, p=5,q=11,e=3,M=9

Now,

* calculate n = p*q = 5*11 = 55 (Here,p and q are both primes and p!=q)

* calculate (n) = (p-1)*(q-1) = 4*10 = 40.

* Given, e=3 we are having "e" such that it is relatively prime to (n) i.e, 3 is relatively prime to 40 (no common factors)

* so,the pair (e,n) is our public key that is used to encrypt i.e, (4,55) is public key.

* Now, we have to calculate "d" such that d = e^(-1) mod (n) i.e,

d*e = 1 mod (n)

3*d = 1 mod 40

To, find "d" use Extended euclidean algorithm as e and d are prime numbers

(n) =40 and e =3

40 = 13*3 + 1(write "(n)" i.e,40 in terms of "e" i.e,3)

Now, back substitution

1 = 40 - 13(3)

Here the value is (-13) and that is negative so, value of d = (n) - 13 = 40-13 =27

Thus, value of d is "27" i.e, d=27

* Now, private key (d,n) is (27,55)

* Given, plain text M=9 (M<n)

so,Ciphertext C = M^e mod n = 9^3 mod 55 =729 mod 55 = 14

"14" is the ciphertext for plaintext "9"

* Decryption using ciphertext C=14 as M = c^d mod n = 14^27 mod 55 = 9 that is nothing but our pain text M=9.

iii) Given p=7, q=11, e=17,M=8

Now,

* calculate n = p*q = 7*11 = 77 (Here,p and q are both primes and p!=q)

* calculate (n) = (p-1)*(q-1) = 6*10 = 60.

* Given, e=17 we are having "e" such that it is relatively prime to (n) i.e, 17 is relatively prime to 60 (no common factors)

* so,the pair (e,n) is our public key that is used to encrypt i.e, (17,77) is public key.

* Now, we have to calculate "d" such that d = e^(-1) mod (n) i.e,

d*e = 1 mod (n)

17*d = 1 mod 60

To, find "d" use Extended euclidean algorithm as e and d are prime numbers

(n) =60 and e =17

60 = 3*17 + 9 (write "(n)" i.e,60 in terms of "e" i.e,17)

Gcd(17,53) =1

Thus, value of d is "53" i.e, d=53.

* Now, private key (d,n) is (53,77)

* Given, plain text M=8 (M<n)

so,Ciphertext C = M^e mod n = 8^17 mod 77 = 57

"57" is the ciphertext for plaintext "17".

* Decryption using ciphertext C=57 as M = c^d mod n = 56^53 mod 77 = 17 that is nothing but our pain text M=17.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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