Now, we all like RSA, it's simple to remember, not-so-simple to actually understand, but very elegant, nonetheless. This sample code shows how easily RSA keys can be generated in with code. Keep in mind: Java isn't the most efficient language, so this setup would run much more quickly in C++ when using large numbers, but hey, this is just for learning, yes? Speaking of which, if you're unfamiliar with modulus arithmetic and number theory, brush up on it here, in particular Chapter 5.

Feel free to poke around with it, use it in your own projects, whatever, Here's how it works:

• Pick two prime numbers, 'p and q'. Multiply them together to get 'n'. Put n in your back pocket for later.
• Subtract one from 'p', subtract one from 'q', and multiply those two together to get 'n2' (it's usually called 'fi of n', fi being a greek symbol). Put n2 in a bank vault, and never, never tell anyone about it.
• Chose a number that's greater than two, and relatively prime to n2 (meaning the greatest common divisor of this number and n2 = 1), and call that 'e'.

That was the easy part. 'e' is your encryption exponent and 'n' is your modulus, and together they make your public key (e,n) . So, when letters are represented as numbers, all you need to do is raise those numbers to the power of 'e' and reduce that mod 'n'. The result is your ciphertext! But, how do you decrypt this..?

You need a decryption exponent. We'll get you one, but this is where simple math goes away. Remember 'e' and 'n2'? Well, we need the multiplicative inverse of e mod n2. What that means is a number, when multiplied by e and reduced mod n2 results in 1. In other words d · e (mod n2) = 1. To get there, with any set of numbers, we employ the Euclidean Algorithm. I'm not getting into that here. Follow the links to learn more. 'd' and 'n' form your private key (d,n) - and as such, don't share that. Again, with the ciphertext you created above raised to the power 'd' reduced modulus 'n' results in your original clear text!

You'll notice I use the BigInteger class a lot.. it's great for manipulating (you guessed it) big integers. You'll also notice it finds multiplicative inverses and greatest common divisors easily. Also notice that most of it's arguments are taken in the form of strings, so I create a new BigInteger as such: BigInteger x = new BigInteger("150"); See? Easy.

Sorry about the indenting, HTML has its limitations... If you'd like to just snag the .java file, it's right here.

/*
* @author Greg M. Bednarski
* @ver 1.0
*/
public class ToyRSA {

public static void main(String[] args) {
BigInteger p = new BigInteger("13"); // Here's one prime number..
BigInteger q = new BigInteger("31"); // ..and another.
BigInteger n = p.multiply(q);
BigInteger n2 = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger e = generateE(n2);
BigInteger d = e.modInverse(n2); // Here's the multiplicitave inverse

System.out.println("Encryption keys are: " + e + ", " + n);
System.out.println("Decryption keys are: " + d + ", " + n);
}

public static BigInteger generateE(BigInteger fiofn) {
int y, intGCD;
BigInteger e;
BigInteger gcd;
Random x = new Random();
// Ok, this is NOT the most effective way to generate 'e'. Deal with it.
do {
y = x.nextInt(fiofn.intValue()-1);
String z = Integer.toString(y);
e = new BigInteger(z);
gcd = fiofn.gcd(e);
intGCD = gcd.intValue();
}
while(y <= 2 || intGCD != 1);
return e;
}
}