Textbook RSA – asymmetric encryption with Java

Hello!

Welcome to another Cryptology 101 article!

Today I would like to present one of the most popular public-key cryptosystems that are still in use.

We will focus on the textbook version of RSA, so let’s check this one out!

RSA in public-key cryptosystem planet

RSA is a public-key cryptosystem that was first published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. The name of the cryptosystem comes from the surnames of its designers.

The high-level idea of public-key cryptosystem I’ve described in the article Cryptology 101: Encryption so check it out before further reading 😊

Security of public-key cryptosystem relies on computational problems – problems that might be solved but are incredibly complex (requires a lot of time, computer memory, or arithmetic operation).

Some of these problems are:

• Integer factorization (prime factorization) – multiplying two big prime numbers is easy – guessing what numbers were multiplied (looking for factors) is difficult.
• Discrete logarithm – they are quickly computable in a few cases but over carefully chosen groups to have no efficient solution.
• Lattice problems – here we have, e.g., shortest vector problem (SVP), closest vector problem (CVP), or shortest independent vector problem. In this problem, we are looking for (non-zero) vectors in the particular lattices (considered in Euclidean norm). Kind of brain-washing math (be careful!)
• Learning with errors – in the LWE problem, we are asked to recover a secret from a set of equations. It would be trivial using Gaussian elimination. That’s why we are adding errors there, which makes it significantly more difficult.

RSA security is based on integer factorization – factoring large composite integers. If you want to find out more, check the related wiki page – RSA problem.

Textbook RSA

Why do we call it “textbook” RSA instead of “just” RSA?
Because it is malleable.

Does it mean it is vulnerable?
Yes and no. Doing simple math operation, an attacker can make predictable changes do ciphertexts. Also, doing the same simple math operation, we can multiply two valid ciphertexts and get a third valid ciphertext.

It is also deterministic and not semantic secure – we can easily distinguish between encrypted 0 vs. encrypted 1.

As we can read in Twenty years of attacks on the RSA cryptosystem by D. Boneh (published in 1999, so 20 years ago), there are many more issues with textbook RSA.

Is it simple to fix? It is not so hard – but I’ll write another article about RSA in use: @placeholder

Let’s finally focus on implementation in Java.

Implementation

I’ll use the RSA wiki page as a source because I believe they have a detailed and strict description. So let’s start with the key generation.

Key generation

In the first step, we have to choose two distinct prime numbers p and q – approximately equal size such that their product n = p*q is of the required bit length.

I’m going to use BigIntegers in Java:

Random rnd = new Random();
BigInteger p = BigInteger.probablePrime(size / 2, rnd);
BigInteger q = BigInteger.probablePrime(size / 2, rnd);

The second step is to compute n = p*q. N is used as the modulus for both public and private keys – so it’s crucial.

BigInteger n = p.multiply(q);

The third step is to compute Euler’s totient function φ(n) OR Carmichael’s totient function λ(n) (which is more secure). Euler’s totient function is in the original algorithm – which is basically (p-1)*(q-1), Carmichael’s totient function is least common multiple – LCM(p-1, q-1). We have to KEEP this value IN SECRET!

BigInteger fi = (p.subtract(BigInteger.ONE)).multiply(q
				.subtract(BigInteger.ONE));
BigInteger lcm = getLcm(p.subtract(BigInteger.ONE), 
q.subtract(BigInteger.ONE));

In forth step we have to choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1 (that is, e and λ(n) are coprime). (I’m going to generate e1 and e2 for both λ(n) and φ(n)).

BigInteger e1 = getCoprime(fi);
BigInteger e2 = getCoprime(lcm);

The fifth and final step is to compute d as d ≡ e−1 (mod λ(n)); that is, d is the modular multiplicative inverse of e modulo λ(n) or φ(n) (and it is a built-in function) (is our very important private key exponent).

BigInteger d1 = e1.modInverse(fi);
BigInteger d2 = e2.modInverse(lcm);

So my very simple implementation is:

public ArrayList<BigInteger> genKey(){
	Random rnd = new Random();
	BigInteger p = BigInteger.probablePrime(size / 2, rnd);
	BigInteger q = BigInteger.probablePrime(size / 2, rnd);
	
	return genKey(p,q);
}

public ArrayList<BigInteger> genKey(BigInteger p, BigInteger q){
	ArrayList<BigInteger> keys = new ArrayList<BigInteger>();
	
	BigInteger n = p.multiply(q);
	BigInteger fi = (p.subtract(BigInteger.ONE)).multiply(q
		.subtract(BigInteger.ONE));
	BigInteger lcm = getLcm(p.subtract(BigInteger.ONE), 
q.subtract(BigInteger.ONE));
	BigInteger e1 = getCoprime(fi);
	BigInteger e2 = getCoprime(lcm);
	BigInteger d1 = e1.modInverse(fi);
	BigInteger d2 = e2.modInverse(lcm);
	
	keys.add(e1);
	keys.add(d1);
	keys.add(e2);
	keys.add(d2);
	keys.add(n);
	
	return keys;
}

I also used two functions: getLcm, and getCoprime. Implementation below:

public static BigInteger getCoprime(BigInteger m) {
	Random rnd = new Random();
	int length = m.bitLength() - 1;
	BigInteger e = BigInteger.probablePrime(length, rnd);
	while (!(m.gcd(e)).equals(BigInteger.ONE)) {
		e = BigInteger.probablePrime(length, rnd);
	}
	
	return e;
}
	
public static BigInteger getLcm(BigInteger a, BigInteger b){
	if (a.signum() == 0 || b.signum() == 0)
	    return BigInteger.ZERO;

	return a.divide(a.gcd(b)).multiply(b).abs();
}

Encryption

To encrypt the message M, we have to turn it into an integer m, which easy constrains (1<m<n), and then compute ciphertext c by simple math:

Our BigInteger class suports power modulu operation. Encryption is very simple:

public static String Encrypt(String message, BigInteger e, 
BigInteger n){
	String m = toHexString(message.getBytes()); // message to Hex
	BigInteger big1 = new BigInteger(m, 16); // hex to BigInteger
	big1 = big1.modPow(e, n); // m^e mod n
	
	return big1.toString();
}

To decrypt the data, we have to do similar operation, but using a private key.

So to decrypt we will compute:

And extract the plaintext:

public static String Decrypt(String ciphertext, BigInteger d, 
BigInteger n){
	String m=ciphertext.replaceAll("\\s", "");
	try{
		BigInteger big1 = new BigInteger(m);
		big1 = big1.modPow(d, n);
		String tmp = big1.toString(16);
		m = fromHexString(tmp);
	}catch(Exception e){
		m="";
	}
	
	return m;	
}

Playground

Let’s presume our message going to be “HFOC” – just like Head Full Of Ciphers. I would like to compare the results in the end. In the main function we are going to do everything step by step:

String message = "HFOC"; // our message
String mHex = RSA.toHexString(message.getBytes()); // message Hex
System.out.println("HFOC as hex: " +mHex);
BigInteger bigM = new BigInteger(mHex, 16);
System.out.println("HFOC as int: " + bigM.toString());

We will keep everything in variables and display them, to make sure it goes well. Then, let’s generate a key for us:

System.out.println("RSA CHECK");
RSA r = new RSA();
r.setSize(512); // do not ever use such small key!

ArrayList<BigInteger> keys = r.genKey();
BigInteger e1 = keys.get(0);
BigInteger d1 = keys.get(1);
BigInteger n = keys.get(4);
BigInteger e2 = keys.get(2);
BigInteger d2 = keys.get(3);

As you can review above, I added these integers to ArrayList, so now I have to assign it correctly, and we can check if done:

System.out.println("KEY 1:");
System.out.println("public: (" + e1.toString()+", "+ n.toString()+")");
System.out.println("priv: (" + d1.toString()+", "+ n.toString()+")");

System.out.println("KEY 2:");
System.out.println("public: (" + e2.toString()+", "+ n.toString()+")");
System.out.println("priv: (" + d2.toString()+", "+ n.toString()+")");

And finally we are able to confirm that both Euluer’s totient fuction and Carmichael’s totient function produces valid ciphertext that is reversable:

System.out.println("\nENC&DEC KEY 1:");
String enc1 = RSA.Encrypt(message, e1, n);
System.out.println("enc = " + enc1);
String dec1 = RSA.Decrypt(enc1, d1, n);
System.out.println("dec = " + dec1);

System.out.println("\nENC&DEC KEY 2:");
String enc2 = RSA.Encrypt(message, e2, n);
System.out.println("enc = " + enc2);
String dec2 = RSA.Decrypt(enc2, d2, n);
System.out.println("dec = " + dec2);

Now let’s do the quick check on the paper:

HFOC as hex: 48464f43

Why? Because in hex H = 48, F = 46, O = 4F, C = 43. So we have to glue the values.

HFOC as int: 1212567363

Using windows calc we can confirm that 4846 4f43 hex = 1 212 567 363 dec

Then we have just simple math. We have two keys (generated for me) and one message.

m = 1 212 567 363
K1: e = (1940504233, 2494830449), d = (1903524553, 2494830449)
K2: e = (21671869, 2494830449), d = (54991969, 2494830449)

Java code output:

ENC&DEC KEY 1:
enc = 1624901165
dec = HFOC

ENC&DEC KEY 2:
enc = 127418471
dec = HFOC

Let’s use WolframAlpha to encrypt the message with the first key:

The results are the same!

Let’s check decryption results:

Exactly as our message 😊

Let’s do a quick check for K2:

Works like a charm 🙂

Love Story

Do you remember my story about the secret love message between Alice and Bob from the previous article?

If the answer is no, you can refresh your memory by reading Cryptology 101: Encryption again.

Having public-private key pair Alice and Bob can exchange public keys via an unsecured channel (email, Whatsapp, Messenger, or whatever), and they can use Java functions from above to pass the secret message just as described in the mentioned article 🙂

They only have to bear in mind that the size of n (in the example above is 64) has to be bigger than the size of a message after conversion to number.

For the message: “I have a crush on you. Would you like to go out on a date with me?” setSize(512) is too small, but 1024 it’s just fine.

Alice can also send two messages one after another

1. I have a crush on you.
2. Would you like to go out on a date with me?

And the 512-bit key will do the job 🙂

Also, as of 2016, NSA recommends to use 3072-bit size keys or more extensive, so we better let our doves 💑 know 🙂

Note: If you want to find out more about proper key size, open position 4 from reference list.

Summary

To be honest, there is still a lot to say about RSA.

It is one of the most popular cryptosystems still out there, being deployed on PROD every they. RSA is used, e.g., in SSL – it means you are using it every day (even now!)

Source code for this project on my Github: HeadFullOfCiphers/TextbookRSA

I enjoy writing about anything related to cryptology! There is so much more to describe and discover, so I strongly encourage you to follow my blog and stay tuned – some crypto-related stuff (with practical examples and appliances) is going to appear here sooner or later – stay tuned. 😊

If you would like to reach out to me, do not hesitate and go to contact me!

This article is part of the #cryptology101 series. Please check out related posts:

Reference list:

1. RSA (cryptosystem) – Wikipedia
2. RSA problem – Wikipedia
3. Twenty Years of Attacks on the RSA Cryptosystem – Dan Boneh
4. Key size – Wikipedia
5. Applied Cryptography: Protocols, Algorithms and Source Code in C, 20th Anniversary Edition – Bruce Schneier
6. Introduction to Cryptography with Coding Theory, 3rd Edition – Wade Trappe, Lawrence C. Washington
7. Modern Cryptography: Applied Mathematics for Encryption and Information Security – Chuck Easttom