RSA algorithm

Aim:Write a program to implement RSA algorithm

Theory: Cryptography has a long and colorful history. The message to be encrypted, known as the plaintext, are transformed by a function that is parameterized by a key. The output of the encryption process, known as the ciphertext, is then transmitted, often by messenger or radio. The enemy, or intruder, hears and accurately copies down the complete ciphertext. However, unlike the intended recipient, he does not know the decryption key and so cannot decrypt the ciphertext easily. The art of breaking ciphers is called cryptanalysis the art of devising ciphers (cryptography) and breaking them (cryptanalysis) is collectively known as cryptology.

There are several ways of classifying cryptographic algorithms. They are generally categorized based on the number of keys that are employed for encryption and decryption, and further defined by their application and use. The three types of algorithms are as follows:

1.      Secret Key Cryptography (SKC): Uses a single key for both encryption and decryption. It is also known as symmetric cryptography.

2.      Public Key Cryptography (PKC): Uses one key for encryption and another for decryption. It is also known as asymmetric cryptography.

3.      Hash Functions: Uses a mathematical transformation to irreversibly "encrypt" information

Public-key cryptography has been said to be the most significant new development in cryptography. Modern PKC was first described publicly by Stanford University professor Martin Hellman and graduate student Whitfield Diffie in 1976. Their paper described a two-key crypto system in which two parties could engage in a secure communication over a non-secure communications channel without having to share a secret key.

Generic PKC employs two keys that are mathematically related although knowledge of one key does not allow someone to easily determine the other key. One key is used to encrypt the plaintext and the other key is used to decrypt the ciphertext. The important point here is that it does not matter which key is applied first, but that both keys are required for the process to work. Because pair of keys is required, this approach is also called asymmetric cryptography.

In PKC, one of the keys is designated the public key and may be advertised as widely as the owner wants. The other key is designated the private key and is never revealed to another party. It is straight forward to send messages under this scheme.

The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977. The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.

Algorithm :

1.      Generate two large random primes, P and Q, of approximately equal size.

2.      Compute N = P x Q

3.      Compute Z = (P-1) x (Q-1).

4.      Choose an integer E, 1 < E < Z, such that GCD (E, Z) = 1

5.      Compute the secret exponent D, 1 < D < Z, such that E x D ≡ 1 (mod Z)

6.      The public key is (N, E) and the private key is (N, D).

Where, the values of P, Q, and Z should also be kept secret.

The message is encrypted using public key and decrypted using private key.

An example of RSA encryption :

1.      Select primes P=11, Q=3.

2.      N = P x Q = 11 x 3 = 33
Z = (P-1) x (Q-1) = 10 x 2 = 20

3.      Lets choose E=3
Check GCD(E, P-1) = GCD(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check GCD(E, Q-1) = GCD(3, 2) = 1
therefore GCD(E, Z) = GCD(3, 20) = 1

4.      Compute D such that E x D ≡ 1 (mod Z)
compute D = E^{^-1} mod Z = 3^{^-1} mod 20
find a value for D such that Z divides ((E x D)-1)
find D such that 20 divides 3D-1.
Simple testing (D = 1, 2, ...) gives D = 7
Check: (E x D)-1 = 3.7 - 1 = 20, which is divisible by Z.

5.      Public key = (N, E) = (33, 3)
Private key = (N, D) = (33, 7).

Now say we want to encrypt the message m = 7,

Cipher code = M^{^E} mod N

                    = 7^{^3} mod 33

                    = 343 mod 33

                    = 13.

    Hence the ciphertext c = 13.

To check decryption we compute Message’ = C^{^D} mod N

                                                           = 13^{^7} mod 33

                                                           = 7.

Here, we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that a = bc mod n = (b mod n).(c mod n) mod n so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.

Conclusion: Hence, we have implemented RSA algorithm.

Program Source Code :

Program to implement RSA Algorithm

import java.io.*;

import java.util.*;

class RSA

{

 public static void main(String args[])

 {

  Scanner ip=new Scanner(System.in);

  int p,q,n,e=1,j;

  int d=1,i1;

  int t1,t2;

  int pt[]= new int[10];

  int ct[]= new int[10];

  int rt[]= new int[10];

  String i=new String();

  System.out.println("Enter the two prime numbers:");

  p=ip.nextInt();

  q=ip.nextInt();

  System.out.println("Enter the message to be sent");

  i=ip.next();

  i1=i.length();

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

  {

   pt[j]=(i.charAt(j))-96;

  }

  n=p*q;

  t1=p-1;

  t2=q-1;

  while((t1*t2)%e==0)

  {

   e++;

  }

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

  {

   ct[j]=((int)Math.pow(pt[j],e))%n;

  }

  System.out.println("Sender Side:");

  System.out.println("----------------------");

  System.out.println("Public Key(e)= "+e);

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

  {

   System.out.println("Cipher Text= "+ct[j]);

  }

  System.out.println("Receiver Side:");

  System.out.println("----------------------");

  while((d*e)%(t1*t2)!=1)

  {

   d++;

  }

  System.out.println("Private Key(d)= "+d);

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

  {

   rt[j]=((int)Math.pow(ct[j],d))%n;

   System.out.println("Plain Text= "+rt[j]);

  }

  System.out.print("Decrypted Message:");

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

  {

   rt[j]=rt[j]+96;

   System.out.print((char)rt[j]);

  }

 }

}

C:\Program Files\Java\jdk1.6.0_02\bin>javac RSA.java

C:\Program Files\Java\jdk1.6.0_02\bin>java RSA

Enter the two prime numbers:

3

5

Enter the message to be sent

abcdefg

Sender Side:

------------------

Public Key(e)=3

Cipher Text= 1

Cipher Text= 8

Cipher Text= 12

Cipher Text= 4

Cipher Text= 5

Cipher Text= 6

Cipher Text= 13

Receiver Side:

------------------

Private key(d)=3

Plain Text= 1

Plain Text= 2

Plain Text= 3

Plain Text= 4

Plain Text= 5

Plain Text= 6

Plain Text= 7

Decrypted Message:abcdefg

C:\Program Files\Java\jdk1.6.0_02\bin>