Tutorialspoint.dev

How to solve RSA Algorithm Problems?

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 p and q
    Lets take p = 3 and q = 11

  • Step-2: Compute the value of n and phi
    It is given as,

    n = p 	imes q and phi = (p-1) 	imes (q-1)

    Here in the example,
    n = 3 	imes 11 = 33
    phi = (3-1) 	imes (11-1) = 2 	imes 10 = 20



  • Step-3: Find the value of e (public key)
    Choose e, such that e should be co-prime. Co-prime means it should not multiply by factors of phi and also not divide by phi

    Factors of phi are, 20 = 5 	imes 4 = 5 	imes 2 	imes 2 so e should not multiply by 5 and 2 and should not divide by 20.

    So, primes are 3, 7, 11, 17, 19…, as 3 and 11 are taken choose e as 7

    Therefore, e = 7

  • Step-4: Compute the value of d (private key)
    The condition is given as,
    gcd(phi, e) = phi x +ey = 1 where y is the value of d.

    To compute the value of d,

    1. Form a table with four columns i.e., a, b, d, and k.
    2. Initialize a = 1, b = 0, d = phi, k = – in first row.
    3. Initialize a = 0, b = 1, d = e, k = frac{phi}{e} 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
      • a_{i} = a_{i-2} - (a_{i-1} 	imes k_{i-1})
      • b_{i} = b_{i-2} - (b_{i-1} 	imes k_{i-1})
      • d_{i} = d_{i-2} - (d_{i-1} 	imes k_{i-1})
      • k_{i} = frac{d_{i-2}}{d_{i-1}}

    As soon as, d = 1, stop the process and check for the below condition

    if b > phi
        b = b mod phi
    if b < 0
        b = b + phi
    

    For a given example, the table will be,

    a b d k
    1 0 20
    0 1 7 2
    1 -2 6 1
    -1 3 1

    As in the above table d = 1, stop the process and check for the condition given for the b
    	herefore b = 3

    To verify that b is correct, the above condition should satisfy, i.e.
    gcd(phi, e) = phi x + ey = (20 	imes -1) + (7 	imes 3) = 1. Hence d is correct.

  • Step-5: Do the encryption and decryption
    Encryption is given as,
    c = t^{e}mod n
    Decryption is given as,
    t = c^{d}mod n

    For the given example, suppose t = 2, so
    Encryption is c = 2^{7}mod 33 = 29

    Decryption is t = 29^{3}mod 33 = 2

    Therefore in the final, p = 3, q = 11, phi = 20, n = 33, e = 7 and d = 3

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. p = 13 and q = 17
  2. Compute n = 13 	imes 17 = 221 and phi = (13-1) 	imes (17-1) = 12 	imes 16 = 192
  3. e = 35 (public key)
  4. Compute d (private key)
    a b d k
    1 0 192
    0 1 35 5
    1 -5 17 2
    -2 11 1

    	herefore d = 11 (private key)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter