RSA Encryption and Decryption with Numerical Example and C Program on RSA Encryption and Decryption

To generate the encryption and decryption keys, we can proceed as follows.

1. Generate randomly two “large” primes p and q.

2. Compute n = pq and  ϕ= (p − 1)(q − 1).

3. Choose a number e so that gcd(e, ϕ) = 1.

4. Find the multiplicative inverse of e modulo ϕ, i.e., find d so that ed ≡ 1 (mod ϕ).

This can be done efficiently using Euclid’s Extended Algorithm.

The encryption public key is K_E = (n, e) and the decryption private key is K_D = (n, d).

The encryption function is   E(M) = M^e mod n.

The decryption function is   D(M) = M^d mod n.

These functions satisfy  D(E(M)) = M and E(D(M)) = M for any 0 ≤ M ≤ n.

*****

Let’s look at a numerical example.

1. Let p = 7 and q = 13 be the two primes.

2. n = pq = 91 and ϕ = (p − 1)(q − 1) = 72.

3. Choose e. Let’s look among the primes.

            • Try e = 2;  gcd(2, 72) = 2 (does not work)

            • Try e = 3;  gcd(3, 72) = 3 (does not work)

            • Try e = 5;  gcd(5, 72) = 1 (it works)

            We choose e = 5.

4. Let’s find d. We want to find d such that  ed  ≡  1 (mod ϕ) which is equivalent to find d such that   ed + ϕ k = 1 for some integer k. Recall that gcd(e, ϕ) = 1.

            We can use the Extended Euclid’s Algorithm to find integers x and y such that

                         ex + ϕy = gcd(e, ϕ).

            If  e = 5 and ϕ = 72, we find x = 29 and y = −2. 

            Indeed, 5(29) + 72(−2) = gcd(5,      72) = 1.    Then,         d = 29.    

            In general, we use d = x mod ϕ.

5. The encryption function is  E(M) = M^e mod n = M⁵ mod 91.

    The decryption function is D(M) = M^d mod n = M²⁹ mod 91.

6. Suppose the message is M = 10.

            E(M) = E(10) = 10⁵ mod 91 = 82

           Here 82 is called as CipherText

           D(E(M)) = D(82) = 82²⁹ mod 91 = 10

7. Let’s see how to compute efficiently 82²⁹ mod 91 using the square-and-multiply algorithm.

            (82)¹  ≡   8² (mod 91)

            (82)²  ≡   8¹ (mod 91)

            (82)⁴ ≡   (81)² ≡  9 (mod 91)

            (82)⁸ ≡   (9)²   ≡  81 (mod 91)

            (82)¹⁶ ≡  (81)² ≡  9 (mod 91

 

            Since 29 = 16 + 8 + 4 + 1 (in binary 29 is 11101),  we deduce that

            82²⁹  ≡    (82)¹⁶(82)⁸(82)⁴(82)¹ (mod 91)

                     ≡   (9)(81)(9)(82) (mod 91)

                     ≡    10 (mod 91)

 

            We conclude that 82²⁹ mod 91 = 10 (Original Message).

 

Consider an another example

1. Let p = 19 and q = 23 be the two primes.

2. n = p*q = 437 and ϕ = (p − 1)*(q − 1) = 396.

3. Choose e. Let’s look among the primes.

            • Try e = 2;  gcd(2, 396) = 0 (does not work because it has factors)

            • Try e = 3;  gcd(3, 396) = 0 (does not work because it has factors)

            • Try e = 5;  gcd(5, 396) = 1 (it works)

             We choose e = 5.

4. Let’s find d. We want to find d such that  ed  ≡  1 (mod ϕ) which is equivalent to find d such that   ed + ϕ k = 1 for some integer k. Recall that gcd(e, ϕ) = 1.

            We can use the Extended Euclid’s Algorithm to find integers x and y such that

                         ex + ϕy = gcd(e, ϕ).  i.e.  5x+396y=1
                                                                   x= (1-396y)/5

            If  e = 5 and ϕ = 396,

            we find x = 317 and y = −4.  Indeed, 5(317) + 396(−4) = gcd(5, 396) = 1.
            Then,         d = 317.    

            In general, we use d = x mod ϕ.

5. The encryption function is  E(M) = M^e mod n = M⁵ mod 437.

    The decryption function is  D(M) = M^d mod n = M³¹⁷ mod 437.

6. Suppose the message is M = 7.

            E(M) = E(10) = 7⁵ mod 437 = 201

           Here 201 is called as CipherText

            D(E(M)) = D(201) = 201³¹⁷ mod 437 = 7 (Original Message)

 

 

 

 

C program on RSA Encryption and Decryption

#include<iostream.h>

#include<conio.h>

#include<math.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

int prime( int n)

{

 int i,r;

  for(i=2;i<n-1;i++)

  {

   r=n%i;

   if(r==0)

    {  return 0;  }

  }

  return 1;

 }

int gcd(int a, int b)

{

  int r=0;

  while(b>a)

  {

   r=b%a;

   if(r==0){ break;}

     b=a;

     a=r;

  }

   return a;

}

 

 void main()

 {

  clrscr();

  int n,pi,x,y,privatekey, publickey,p,q,primecheck,gcdvalue;

  cout<<"enter two prime numbers"<<"\n";

  cin>>p>>q;

  if (prime(p)==0 || prime(q)==0 ||p==q)

  {

     cout<<" one of the number is not prime or both numbers are same"<<"\n";

  }

  else

  {

   n=p*q;

   pi= (p-1)*(q-1);

   for(int e=3; e<pi-1; e++)

   {

      if (prime(e)==1)

       {

             if (gcd(e,pi)==1)

             {

               publickey= e;

               break;

             }

       }

   }

   cout<<"Public Key="<<publickey<<"\n";

   y=1;

   while(1)

   {

      x= (1-(pi*(-y)))/publickey ;

      if (publickey*x+pi*(-y)==1) { break; }

      y++;

   }

   privatekey=x;

   cout<<"private key="<< privatekey<<"\n";

   cout<<"enter message"<<"\n";

   int msg;

   cin>>msg;

   long ctext=1,i;

   for (i=0;i<publickey; i++)

    ctext=(ctext*msg)%n;

 

   ctext=ctext%n;

   cout<<"ciphertext or encrypt="<<ctext<<"\n";

   long ptext=1,j;

   for(j=0;j<privatekey;j++)

     ptext=(ptext*ctext)%n;

   ptext=ptext%n;

   cout<<"plain Text="<<ptext<<"\n";

  }

   getch();

 }