Program 11 (Java)

11.WRITE A PROGRAM FOR SIMPLE RSA ALGORITHM TO ENCRYPT AND DECRYPT THE DATA.

RSA is an example of public key cryptography. It was developed by Rivest, Shamir and Adelman. 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.

The RSA algorithm's efficiency requires a fast method for performing the modular exponentiation operation. A less efficient, conventional method includes raising a number (the input) to a power (the secret or public key of the algorithm, denoted e and d, respectively) and taking the remainder of the division with N. A straight-forward implementation performs these two steps of the operation sequentially: first, raise it to the power and second, apply modulo. The RSA algorithm comprises of three steps, which are depicted below:

Key Generation Algorithm:

Ø Generate two large random primes, p and q, of approximately equal size such that their product n = p*q

Ø Compute n = p*q and Euler‟s totient function (φ) phi(n) = (p-1)(q-1).

Ø Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1.

Ø Compute the secret exponent d, 1 < d < phi, such that e*d ≡ 1 (mod phi).

Ø The public key is (e, n) and the private key is (d, n). The values of p, q, and phi should also be kept secret.

Encryption:

Sender A does the following:

Ø Using the public key (e,n)

Ø Represents the plaintext message as a positive integer M

Ø Computes the cipher text C = M^e mod n.

Ø Sends the cipher text C to B (Receiver).

Decryption:

Recipient B does the following:

Ø Uses his private key (d, n) to compute M = C^d mod n.

Ø Extracts the plaintext from the integer representative m.

RSA KEY GENERATION

RSA.java

package rsa;

import java.math.BigInteger;

import java.util.Random;

import java.util.Scanner;

public class RSA {

    public static void main(String[] args) {

        // Each public and private key consists of an exponent and a modulus

        BigInteger n;             // n is the modulus for both the private and public keys

        BigInteger e;             // e is the exponent of the public key

        BigInteger d;             // d is the exponent of the private key

        int bitlength = 512;

        Random r = new Random();

         // Step 1: Generate two large random primes.

         // We use 512 bits here, but best practice for security is 2048 bits.

         // Change 512 to 2048, recompile, and run the program again and you will

         // notice it takes much longer to do the math with that many bits.

        BigInteger p = BigInteger.probablePrime(bitlength, r);

        BigInteger q = BigInteger.probablePrime(bitlength, r);

       

         // Step 2: Compute n by the equation n = p * q.

        n = p.multiply(q);           

       

         // Step 3: Compute phi(n) = (p-1) * (q-1)

        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));             

       

         // Step 4: Select a small odd integer e that is relatively prime to phi(n).

         // By convention the prime 65537 is used as the public exponent.

        e = new BigInteger("65537");   

       

         // Step 5: Compute d as the multiplicative inverse of e modulo phi(n).

        d = e.modInverse(phi);

        Scanner in = new Scanner(System.in);

        String s;

         // Enter a simple message to be Encrypted

        System.out.println("Enter the plain text:");

        s = in.nextLine();

        

         //m is the byte representation of the message to be encrypted

        BigInteger m = new BigInteger(s.getBytes());

         // Step 8: To encrypt a message m compute c = m^e (mod n)

        BigInteger c = m.modPow(e, n);    

         // Step 9: To decrypt a message c compute m = c^d (mod n)

        BigInteger decrypt = c.modPow(d, n);

        String decryptedText = new String(decrypt.toByteArray());                   // Decode to a string

        //Display encrypted and Decrypted Text

        System.out.println("Encrypted text = " + c);

        System.out.println("Decrypted text = " + decryptedText);

    }

}

Sample Output

Run 2: (with 512 bit length)

Enter the plain text:

Hi

Encrypted text = 50103541608902977714830787067336423528693428112542451321662351307703238988804091377813045118337788875236867053906253106107774066498343223025242498039945783616334368008373436765270106440836251272261312958541836420077143796150889590605720718009223754637616515096158219963336603732720981018779883280372434260244

Decrypted text = Hi

BUILD SUCCESSFUL (total time: 2 seconds)