How to solve RSA Algorithm Problems? - GeeksforGeeks (2024)

RSA algorithm is an asymmetric cryptography algorithm which means, there should be two keys involve while communicating, i.e., public key and private key. There are simple steps to solve problems on the RSA Algorithm.

Example-1:

• Step-1: Choose two prime number[Tex]p[/Tex]and[Tex]q[/Tex]Lets take[Tex]p = 3[/Tex]and[Tex]q = 11[/Tex]
• Step-2: Compute the value of[Tex]n[/Tex]and[Tex]\phi[/Tex]It is given as,

[Tex]n = p \times q[/Tex] and [Tex]\phi = (p-1) \times (q-1)[/Tex]

• Here in the example,[Tex]n = 3 \times 11 = 33[/Tex][Tex]\phi = (3-1) \times (11-1) = 2 \times 10 = 20[/Tex]
• Step-3: Find the value of[Tex]e[/Tex](public key) Choose[Tex]e[/Tex], such that[Tex]e[/Tex]should be co-prime. Co-prime means it should not multiply by factors of[Tex]\phi[/Tex]and also not divide by[Tex]\phi[/Tex]Factors of[Tex]\phi[/Tex]are,[Tex]20 = 5 \times 4 = 5 \times 2 \times 2[/Tex]so[Tex]e[/Tex]should not multiply by[Tex]5[/Tex]and[Tex]2[/Tex]and should not divide by 20. So, primes are 3, 7, 11, 17, 19…, as 3 and 11 are taken choose[Tex]e[/Tex]as 7 Therefore,[Tex]e = 7[/Tex]
• Step-4: Compute the value of[Tex]d[/Tex](private key) The condition is given as,[Tex]gcd(\phi, e) = \phi x +ey = 1[/Tex]where y is the value of[Tex]d[/Tex]. To compute the value of[Tex]d[/Tex],
  1. Form a table with four columns i.e., a, b, d, and k.
  2. Initialize a = 1, b = 0, d =[Tex]\phi[/Tex], k = – in first row.
  3. Initialize a = 0, b = 1, d =[Tex]e[/Tex],[Tex]k = \frac{\phi}{e}[/Tex]in second row.
  4. From the next row, apply following formulas to find the value of next a, b, d, and k, which is given as
     • [Tex]a_{i} = a_{i-2} – (a_{i-1} \times k_{i-1})[/Tex]
     • [Tex]b_{i} = b_{i-2} – (b_{i-1} \times k_{i-1})[/Tex]
     • [Tex]d_{i} = d_{i-2} – (d_{i-1} \times k_{i-1})[/Tex]
     • [Tex]k_{i} = \frac{d_{i-1}}{d_{i}}[/Tex]
• Step-5: Do the encryption and decryption Encryption is given as,[Tex]c = t^{e}\mod n[/Tex]Decryption is given as,[Tex]t = c^{d}\mod n[/Tex]For the given example, suppose[Tex]t = 2[/Tex], so Encryption is[Tex]c = 2^{7}\mod 33 = 29[/Tex]Decryption is[Tex]t = 29^{3}\mod 33 = 2[/Tex]Therefore in the final,[Tex]p = 3[/Tex],[Tex]q = 11[/Tex],[Tex]\phi = 20[/Tex],[Tex]n = 33[/Tex],[Tex]e = 7[/Tex]and[Tex]d = 3[/Tex]

Example-2: GATE CS-2017 (Set 1) In an RSA cryptosystem, a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of A is 35. Then the private key of A is?

1. [Tex]p = 13[/Tex]and[Tex]q = 17[/Tex]
2. Compute[Tex]n = 13 \times 17 = 221[/Tex]and[Tex]\phi = (13-1) \times (17-1) = 12 \times 16 = 192[/Tex]
3. [Tex]e = 35[/Tex](public key)
4. Compute[Tex]d[/Tex](private key)

1. [Tex]\therefore d = 11[/Tex](private key)

Example-3: In RSA algorithm if p = 7, q = 11 and e = 13 then what will be the value of d?

Step:

1) Calculate value of n = p × q, where p and q are prime no.’s

2) calculate Ø(n) = (p-1) × (q-1)

3) consider d as public key such that Ø(n) and d has no common factors.

4) consider e as private key such that (e × d) mod Ø(n) = 1

5) Cipher text c = message i.e. m^dmod n

6) message = cipher text i.e. c^emod n

Calculation

p =7, q= 11, e = 13

Use step 2 and 4 of RSA algorithm to calculate private key.

Ø(n) = (7– 1) × (11 – 1) = 6 × 10 = 60

Now,

(e × d) mod Ø(n) = 1

(13 × d) mod 60 = 1

d = 37

So, key of A = 37

Example-4: In an RSA cryptosystem, a participant uses two prime numbers p = 3 and q = 11 to generate his public and private keys. If the private key is 7, then how will the text COMPUTER be encrypted using the public key?

Step:

RSA Algorithm:

Step 1:Calculate value of n = p × q, where p and q are prime no.’s

Step 2:calculate Ø(n) = (p-1) × (q-1)

Step 3:consider d as a private key such that Ø(n) and d have no common factors. i.egreatest common divisor (Ø(n) ,d )= 1

Step 4:consider e as a public key such that (e × d) mod Ø(n) = 1.

Step 5:Ciphertext = message i.e. memod n.

Step 6:message= cipher text i.e. cdmod n.

Calculation:

Given prime numbers, p=3, q = 11

n= 3x 11=33

Ø(n) = (3-1) × (11-1) = 2x 10=20

greatest common divisor (20, d) =1

d = Private Key = 7

As per question d =7.

(e × d) mod Ø(n) = 1

(e x 7) mod 20= 1

So, e x 7= 20x 1+1

e=217= 3 possible.

,e = public Key=3 =encrypt key

So n = 33 ,e = 3, d = 7,Ø(n)=20

Plan text =COMPUTER

Ciphertext =m^emod n.

Ciphertext for C = 3³mod 33=27

Ciphertext for O = 153mod 33= 9

Ciphertext for M = 133mod 33 = 19

Ciphertext for P = 163mod 33 =4

Ciphertext for U = 213mod 33 =21

Ciphertext for T = 203mod 33 = 14

Ciphertext for E = 53mod 33 = 26

Ciphertext for R = 183mod 33 = 24.

Example-5: Using ‘RSA’ algorithm, if p = 13, q = 5 and e = 7, the value of d and cipher value of ‘6’ with (e, n) key are

RSA Algorithm:

Step 1:Calculate value of n = p × q, where p and q are prime no.’s

Step 2:calculate Ø(n) = (p-1) × (q-1)

Step 3:consider d as a private key such that Ø(n) and d have no common factors. i.egreatest common divisor (Ø(n) ,d )= 1

Step 4:consider e as a public key such that (e × d) mod Ø(n) = 1.

Step 5:Ciphertext = message i.e. memod n.

Step 6:message= cipher text i.e. cdmod n.

Calculation:

To find the value of ‘d’ in the RSA algorithm, we need to calculate the modular multiplicative inverse of ‘e’ modulo φ(n), where n is the product of the two prime numbers p and q, and φ(n) is the Euler’s totient function.

Given:
p = 13
q = 5
e = 7
ciphertext = 6

First, calculate n:
n = p ×q
n = 13 ×5
n = 65

Next, calculate φ(n):
Ø(n)=(p – 1) ×(q – 1)
Ø(n)= (13 – 1) ×(5 – 1)
Ø(n)= 12 ×4
Ø(n)= 48

Now, we need to find the modular multiplicative inverse of ‘e’ moduloØ(n). In other words, we need to find ‘d’ such that (e * d) modØ(n)= 1.

Using the extended Euclidean algorithm, we can find ‘d’:

Step 1:
48 = 7 ×6 + 6
7 = 6 ×1 + 1

Step 2:
6 = 1 * 6 + 0

Since the remainder in the last step is 1, we can conclude that the greatest common divisor of 7 and 48 is 1. Therefore, ‘d’ exists, and it is the coefficient of 7 in the equation:

1 = 7 – 6 ×1

So, ‘d’ is equal to 7.

Now, to decrypt the ciphertext using the private key (d, n), we can use the formula:

plaintext = (ciphertext^d) mod n

Substituting the values:
plaintext = (6⁷) mod 65

Calculating this:

plaintext = 279936 % 65
plaintext = 46

Therefore, the value of ‘d’ is 7 and the plaintext (decrypted value) of the ciphertext ‘6’ using the private key (d, n) is 46.

Solving RSA algorithm problems usually involves the following steps:

1. Choose two prime numbers: Start by selecting two large prime numbers, p and q, and compute their product, n = p * q. This product forms the modulus for the RSA algorithm.
2. Compute Euler’s totient function: Compute Euler’s totient function, phi(n) = (p-1) * (q-1). This value is used to generate the public and private keys.
3. Choose the public key: Choose a number e that is relatively prime to phi(n). This means that e and phi(n) share no common factors other than 1. The public key consists of the pair (e,n).
4. Compute the private key: Compute the modular multiplicative inverse of e modulo phi(n). This can be done using the extended Euclidean algorithm. The private key consists of the pair (d,n).
5. Encrypt a message: To encrypt a message, first convert it to a number m. Then compute the ciphertext c = m^e mod n.
6. Decrypt a message: To decrypt a message, compute the plaintext m = c^d mod n.

Here are some tips for solving RSA algorithm problems:

1. Choose large prime numbers: The strength of the RSA algorithm depends on the size of the prime numbers used. For security purposes, it is recommended to choose prime numbers that are at least 1024 bits long.
2. Use a calculator or programming language: Performing the calculations by hand can be difficult and time-consuming. Instead, use a calculator or a programming language that supports large integers.
3. Check your calculations: RSA calculations involve many large numbers, so it’s easy to make mistakes. Double-check your calculations to make sure you haven’t made any errors.
4. Practice with examples: Practice solving RSA problems with examples to get a better understanding of the algorithm. There are many online resources that provide RSA examples and practice problems.