-2o1o- An Example of RSA Algorithm

An example of RSA encryption algorithim quoted from www.wikipedia.org

(Click to enlarge)

RSA is an asymmetric encryption algorithm that features public key cryptography technology. I've written an example of RSA encryption in Java, you can download it here. Dont fret if you dont understand it at the first glance; It's not as hard as how it seems, I will go through part by part of the program with you.

import java.math.BigInteger;

Since the primitive data types in Java does not support huge integers that is essentially required in RSA, I've imported the BigInteger class as an approach for such deficiency. For more information about BigInteger. Click here. 

System.out.println("Generating Public and Private keys..");

n = p * q;

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

Note : In this case we assume the totient p(n) as z

RSA requires a pair of key called the public key and the private key pair. Public key is meant to be distributed over the world for encrypting purpose whereas private key is meant to be kept in personal for decrypting purpose. In order to achieve this, first we will have to define two prime numbers. I will use 11 and 13 for simplicity's sake, but bear in mind that in a real situation the primes are very likely to be over more than 100 digits, and the computation of the whole process usually takes lots of CPU resources and time, hence RSA is far slower than DES and other symmetric cryptosystem. The code n = p * q; describes the process of n = pq. On the other hand, z = (p-1) * (q-1) describes the process of computing (p-1)*(q-1). The processes above compute the values n and z and this completes the public key pair. 

for (int i=3;i<=z;i++) {

if ((z % i)!=0) e=i;

for (int x=0;x<=z*3;x++) { //x has to be at least 1 time larger than z which carries the value of (p-1) * (q-1)

if (((e*x) % z) == 1) {

d = x;

}

}

}

The code above shows the process of generating one of the private key entry e, which has to be relatively prime to the value z. It also shows the generation of the private key exponential where de = n mod 1. These two values has to be kept secret.

public BigInteger encrypt(int enc) {

enc2 = BigInteger.valueOf(enc);

n2 = BigInteger.valueOf(n);

encPowE=enc2.pow(e);

encPowEModN = encPowE.mod(n2);

return  encPowEModN; //returns the encrypted message

}

The program first assigns the value of enc into the BigInteger instance enc since the method pow() can only be invoked by an instance of BigInteger. Likewise, n2 carries the value of n for the purpose of invocation for the method mod(). The process above can be shown with the equation as follows

where 

enc = the message to be encrypted

e = the relative prime of the computation of (p-1) * (q-1), z

n = computation of pq

Encrypt(enc) = (enc^e) MOD n

Assume 52 is the value we are going to encrypt, so the equation would be

Encrypt(52) = (25^119) MOD 143

           

equivalent to 103. 

public BigInteger decrypt(int decr) {

decr2 = BigInteger.valueOf(decr);

decrPowD = decr2.pow(d);

decrPowDModN = decrPowD.mod(n2);

return  decrPowDModN ; //returns the decrypted message

}

Now it comes to the decrypting part, similar to the encrypting part, the decr2 instance holds the value of decr, also the ciphertext. The process is shown as follows

where 

decr = the ciphertext to be decrypted

d = the private key exponential

n = the computation of pq

Decrypt(decr) = (decr^d) MOD n

so it would be,

Decrypt(103) = (103^359) MOD 143

and Voila! You got the decrypted message 52!