Exercise 9.9.2: Encrypting and decrypting a message with RSA. n this problem, we

Question

Exercise 9.9.2: Encrypting and decrypting a message with RSA. n this problem, we will implement the RSA algorithm to encrypt and decrypt the message "H For this exercise, you may want to use a calculator that can compute the mod function. (a) Use the scheme used in your text to convert the message "HI" into an integer Call the integer m (b) Set the primes p and q as follows: p 343 and q 379. What are the values for N and D? (c) The value for e is chosen to be 29. Use Euclid's algorithm to verify that e and are relatively prime and to find d, the multiplicative inverse of e mod D. (d) crypt the message m by computing me mod N (e) The result of the previous question is the cyphertext c that is transmitted. To decrypt the message, compute cd mod N (f Verify that the decrypted message is the same as m. Convert m back into a text message.

Explanation / Answer

9.9.2)

a) "HI" is 809 = m.

b) The first step of the RSA algorithm is to get two prime numbers, p and q.

Given p = 43 and q = 79

The product of p and q is n.

Hence n = p * q = 43 * 79 = 3397

The euler totient (n) is

(n) = (p-1) * (q-1) = 42 * 78 = 3276

c) 29 is a prime number hence its factors are only 1 and 29.

     To find d,

e * d 1 mod (n)

29 * d 1 mod 3276

Using the Euclidean Algorithm, the possible value we can assume for d is 113.

e * d mod (n) = 29 * 113 mod 3276 = 3277 mod 3276 = 1

Now we have both a Public and Private Key,

Pub = (e,n) = (29, 3397)

Priv = (d,n) = (113,3397)

d) Encryption: c = m ^ e mod n

c = 809 ^ 29 mod 3397

c = 336

e) Decryption: m = c ^ d mod n

m = 336 ^ 113 mod 3397

m = 809

f) So the decrypted message is 809 which is translates back into "HI"

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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