Improve Article
Save Article
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 and
Lets takeand - Step-2: Compute the value of
and
It is given as,andHere in the example,
- Step-3: Find the value of
[public key]
Choose, such thatshould be co-prime. Co-prime means it should not multiply by factors ofand also not divide byFactors of
are,soshould not multiply byandand should not divide by 20.So, primes are 3, 7, 11, 17, 19…, as 3 and 11 are taken choose
as 7Therefore,
- Step-4: Compute the value of
[private key]
The condition is given as,where y is the value of.To compute the value of
,- Form a table with four columns i.e., a, b, d, and k.
- Initialize a = 1, b = 0, d = , k = – in first row.
- Initialize a = 0, b = 1, d = ,in second row.
- From the next row, apply following formulas to find the value of next a, b, d, and k, which is given as
As soon as,
, stop the process and check for the below conditionif
ifFor a given example, the table will be,
abdk 1 0 20 – 0 1 7 2 1 -2 6 1 -1 3 1 – As in the above table
, stop the process and check for the condition given for theTo verify that
is correct, the above condition should satisfy, i.e.. Henceis correct. - Step-5: Do the encryption and decryption
Encryption is given as,
Decryption is given as,For the given example, suppose
, so
Encryption isDecryption is
Therefore in the final,
,,,,and
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?
- and
- Compute and
- [public key]
- Compute
[private key]
abdk 1 0 192 – 0 1 35 5 1 -5 17 2 -2 11 1 – [private key]