Implementing RSA in Java (BigInteger approach)

05Jun08

Asymmetric encryption is a form of cyptosystem in which encryption and decryption are performed using the different keys. One is considered as public key while the other as private key. It is also known as public key cyptosystem. The most widely used public key cryptosystem is RSA. In this article, I will show you a very simple implementation of RSA in Java.

But, first, lets go through a simple rundown of the algorithm.

Step 1: Select two large prime numbers. Say p and q.
Step 2: Calculate n = p.q
Step 3: Calculate ø(n) = (p – 1).(q – 1)
Step 4: Find e such that, it is relatively prime with ø(n), i.e. gcd(e, ø(n)) = 1 ; 1 < e < ø(n)
Step 5: Calculate d such that e.d = 1 (mod ø(n)) i.e. multipicative inverse of e.(mod ø(n))

This is the initialization part. In this part we have deduced a public key and a private key for ourselves.
Public Key is (n, e) and Private Key is (d, n).

Encryption: ciphertext = (plaintext ^ e) mod n
Decryption: plaintext = (ciphertext ^ d) mod n

We will make use of BigInteger class of Java.

/*
BigInteger (int bitLength, int certainty, Random rnd) 

bitLength - bitLength of the returned BigInteger.

certainty - a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed
(1 - 1/2certainty). The execution time of this constructor is proportional to the value of this parameter.

rnd - source of random bits used to select candidates to be tested for primality.
*/

import java.util.*;
import java.math.*;
import java.io.IOException;

public class TestRsa
{
private BigInteger p, q;
private BigInteger n;
private BigInteger PhiN;

private BigInteger e, d;

public TestRsa()
{
Initialize();
}

public void Initialize()
{
int SIZE = 512;

/* Step 1: Select two large prime numbers. Say p and q. */
p = new BigInteger(SIZE, 15, new Random());
q = new BigInteger(SIZE, 15, new Random());

/* Step 2: Calculate n = p.q */
n = p.multiply(q);

/* Step 3: Calculate ø(n) = (p - 1).(q - 1) */
PhiN = p.subtract(BigInteger.valueOf(1));
PhiN = PhiN.multiply( q.subtract( BigInteger.valueOf(1)));

/* Step 4: Find e such that gcd(e, ø(n)) = 1 ; 1 < e < ø(n) */
do
{
e = new BigInteger(2*SIZE, new Random());

}
while( (e.compareTo(PhiN) != 1)
||
(e.gcd(PhiN).compareTo(BigInteger.valueOf(1)) != 0));

/* Step 5: Calculate d such that e.d = 1 (mod ø(n)) */
d = e.modInverse(PhiN);
}

public BigInteger encrypt(BigInteger plaintext)
{
return plaintext.modPow(e, n);
}

public BigInteger decrypt(BigInteger ciphertext)
{
return ciphertext.modPow(d, n);
}

public static void main(String[] args) throws IOException
{
TestRsa app = new TestRsa();

int plaintext;
System.out.println("Enter any character : ");
plaintext = System.in.read();

BigInteger bplaintext, bciphertext;
bplaintext = BigInteger.valueOf((long)plaintext);

bciphertext = app.encrypt(bplaintext);
System.out.println("Plaintext : " +  bplaintext.toString());
System.out.println("Ciphertext : " +  bciphertext.toString());

bplaintext = app.decrypt(bciphertext);
System.out.println("After Decryption Plaintext : " +  bplaintext.toString());
}
}

In the next post, I will show another way of implementing RSA.

Filed under: Java   |  Leave a Comment
Tags: asymmetric cryptosystem, BigInteger, cryptography, Java, private key, public key, RSA, security