In RSA for p = 5 and q = 11 find out public key and private key from given p and q

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 take
  and
• Step-2: Compute the value of
  and
  
  It is given as,

   and 
  

  Here in the example,
  

  
  

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

  Factors of

  are,
  so
  should not multiply by
  and
  and should not divide by 20.

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

  as 7

  Therefore,

• Step-4: Compute the value of
  (private key)
  The condition is given as,
  
  where y is the value of
  .

  To compute the value of

  ,
  1. Form a table with four columns i.e., a, b, d, and k.
  2. Initialize a = 1, b = 0, d =
     , k = – in first row.
  3. Initialize a = 0, b = 1, d =
     ,
     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

  As soon as,

  , stop the process and check for the below condition

  if 
  
      
  
  if 
  
      
  
  

  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

  , stop the process and check for the condition given for the
  
  

  To verify that

  is correct, the above condition should satisfy, i.e.
  
  . Hence
  is correct.

• Step-5: Do the encryption and decryption
  Encryption is given as,
  
  
  Decryption is given as,
  

  For the given example, suppose

  , so
  Encryption is

  Decryption 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?

1. and
2. Compute
   and
3. (public key)
4. Compute
   (private key)
   

   a	b	d	k
   1	0	192	–
   0	1	35	5
   1	-5	17	2
   -2	11	1	–

   (private key)