Question

In public key cryptography, there are two keys created, one for encoding a message (the public key) and one for decoding the message (the private key). One form of this scheme is known as RSA, from the first letters of the last names of Ron Rivest, Adi Shamir, and Leonard Adleman, who published the method in 1977 while professors at the Massachusetts Institute of Technology. This method uses modular arithmetic in a very unique way To create a coding and decoding scheme in RSA cryptography, we begin by choosing two large, distinct prime numbers p and q, say, p-59 and q-83. In practice, these would be prime numbers that are 200 or more digits long. Find the product of p and q, n-p-q-59-83-4897. The value of n is the modulus. Now find the product z-(p-1)(q-1)-58-82-4756 and randomly choose a number e, where 1 < e < z and e and z have no common factors, we will choose e-129. Solve the modular equation ed-1 mod Z for d. For the numbers we are using, we must solve 129d 1 mod 4756. We won't go into the details but the solution is d- 1401. Recall that because 129 - 14011 mod 4756, 1401 is the multiplicative inverse of 129 mod 4756. To receive encrypted messages, Olivia posts these values of n and e to a public key encryption service, called a certificate authority, which guarantees the integrity of her public key. If Henry wants to send Olivia a message, he codes his message as a number using a number for each letter of the alphabet. For instance, he might use A -11, B-12, C-13, , and Z-36. For Henry to send the message MATH, he would use the numbers 23 11 30 18 and code those numbers using Olivia's public key, N129 mod 4897·M, where N is the plaintext (23 11 30 18), and M is the ciphertext, the result of using the modular equation. This is shown below. 23129 mod 4897 3065 11129 mod 48972001 30129 mod 4897 95718129 mod 4897 275:3 Thus Henry sends Olivia the ciphertext numbers 3065, 2001, 957, and 2753. When Olivia receives the message, she uses her private key, M1401 mod 4897 message. Olivia calculates N, where M is the ciphertext she received from Henry and N is the original plaintext, to decode the 30651401 mod 4897 23 20011401 mod 4897 11 9571401 mod 4897 30 27531401 mod 4897 18 She decodes the message as 23 11 30 18 or MATH

This is the prompt then the question asks, "What is the ciphertext for the word LODE? (Simplify your answers completely. Enter your answers as a comma-separated list.)"

Please help I have been stuck for hours.

Answer 1

For the word 'LODE', let's go step by step:

Step 1: Let's decide distinct prime numbers p and q, as p=59, q=83, same as the above example.

Step 2: Finding the value of 'n' which is the product of p and q decided in step 1. Therefore, n=p*q, n=59*83, n=4897

Step 3: Compute the value of 'z' which is the product of (p-1)*(q-1). Therefore,

z=(59-1)*(83-1) = 4756. z=4756

Step 4: Deciding the value of 'e' such that z and e have no common factor other than 1. For this take a random number such as 153 and calculate GCD (Greatest Common Divisor) of both 'e' and 'z'. If the GCD is 1, then you can take the number as 'e' else try some other number. e=153

To calculate GCD of two numbers, you can follow this method: Factors of 153: 3*3*17*1 Factors of 4746: 2*2*29*41*1 To get the GCD of 153 and 4756, multiply common factors in both. The only common factor if 1, hence you can say that 153 and 4756 have no common factors '1' being the universal exception.

Step 5: Solve the modular equation e*d = 1 mod z for 'd', which is equivalent to finding
delmod

First, follow Euclid's division method:

Divident=divisor*quotient + remainder 4756 = 31*(153) + 13 ................................(i) 153 = 11*(13) + 10 ................................(ii) 13 = 1*(10) + 3    ................................(iii) 10 = 3*(3) + 1 ................................(iv) If '1' is not the last remainder(GCD), then we cannot find the inverse. have numbered the equation because we will use it later.

Now, Express '1' as the difference of multiples of 4756 and 153

From equation(iv),   1 = 10 - 3*(3)    ................................(a) From equation(iii) 3 = 13 - 1*(10)   replacing value of '3' in equation (a) 1 = 10 - 3*[13 - 1*(10)] = 10 - 3*(13) + 3*(10) = 4*(10) - 3*(13) 1 = 4*(10) - 3*(13) ................................(b) From equation(ii), 10= 153 - 11*(13) replacing value of '10' in equation (b) 1 = 4*[153 - 11*(13)] - 3*(13) = 4*153 - 44*(13) - 3*(13) = 4*153 - 47*(13) 1 = 4*153 - 47*(13)   ................................(c) From equation (i) 13 = 4756 - 31*(153) replacing value of '13' in equation (c) 1 = 4*153 - 47*[4756 - 31*(153)] = 1461*(153) - 47(4756) 1 = 1461*(153) - 47(4756) Apply modulo 4756 to both the sides, 1 mod 4756 = 1461(153) - 47 mod (4756) mod 4756 4756 mod 4756 =0 Hence, 1 mod 4756 = 1461(153) , Therefore d= 1461

Step 6: According to the question A=11, B=12 ,... etc, Therefore, 'LODE' is equivalent to numbers, {22, 25, 14, 15}

Step 7: Calculate the encrypted text for numbers {22, 25, 14, 15} using public key whose formula is:

N¹⁵³ mod 4897 = M

22¹⁵³mod 4897 = 1797

25¹⁵³ mod 4897 = 2084

14¹⁵³ mod 4897 = 1898

15¹⁵³mod 4897 = 717

Therefore, the encrypted text is { 1797, 2084, 1898, 717}