The RSA Algorithm was developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman (hence the initials RSA). While MIT was granted a U.S. Patent for the algorithm in 1983, it has since been released into public domain.

The Algorithm:

Key Generation:

1. Choose two distinct prime numbers, p and q.
2. Compute n = p*q
3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) where φ(n) is the Totient Function.
4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. In other words, e and φ(n) are coprime.
5. Solve for d, given d*e= 1*(mod(φ(n)).
6. (n,e) is now the Public Key, and (n,d) is now the Private Key.

Encryption:

1. Convert the message M into an integer m where 0 ≤ m < n. This can easily done just by using ASCII or unicode numbers and concatenating the numbers together to form a large integer.
2. Compute the encrypted message (c) using the following formula: c ≡ (m^e) mod(n), where (n, e) is the public key.

Decryption:

1. Compute the decrypted message m by computing: m ≡ (c^d) mod(n), where (n, d) is the private key.
2. Then split up the message using the aformentoned encoding type (ASCII, unicode, etc.).

GMP Library Help

While this algorithm can be confusing to implement in C++, we can use a helpful library called GMP (GNU Multiple Precision Arithmetic Library. Specifically, we'll use the following classes and functions to help us:

• mpz_class(t) - A class that allows us to handle large integers
• mpz_mod(r, n, d) - Performs the modulo operation by setting r to n mod d.
• mpz_gcd(rop, op1, op2) - Sets rop to the greatest common divisor of op1 and op2.
• mpz_invert(rop, op1, op2) - Computes the inverse of op1 mod op2 and puts the result in rop.
• mpz_probab_prime_p(n, reps) - Determines whether n is prime. Returns 2 if definitely prime, 1 if probably prime, and 0 if n is definitely composite.

The C++ Code Explained

The following will be excerpts from the code found in the RSA.cc file.

Key Generation

// Generate the public and private keys
void generateKey(int size, mpz_class& n, mpz_class& d, mpz_class& e)
{
	bool prime = false;
	bool divisor = false;
	mpz_class PNUM, result, q, p, phiN;
	mpz_class one = mpz_class(1);

	// Compute p & q
	for(int i = 0; i < 2; ++i)
	{
		while(!prime)
		{
			PNUM = r.get_z_bits(size);
			int isPrime = 1;
			isPrime = mpz_probab_prime_p(PNUM.get_mpz_t(), 100);
			if(isPrime != 0) break;
		}
		if(i == 0) p = PNUM;
		if(i == 1) q = PNUM;
	}
	n = p * q;
	phiN = (p - 1) * (q - 1);

	while(!divisor)
	{
		d = r.get_z_bits(size * 2);
		mpz_gcd(result.get_mpz_t(), d.get_mpz_t(), phiN.get_mpz_t());
		if((d < phiN) && (result == one)) break;
	}

	// Compute e:
	mpz_invert(e.get_mpz_t(), d.get_mpz_t(), phiN.get_mpz_t());

}

Encryption:

// Encrypt Function
void encrypt(	  mpz_class& c, // Encrypted Message
			const mpz_class& m, // Message to be encrypted
			const mpz_class& e, // Keys
			const mpz_class& n)
{
	//Encrypt: c = (m ^ e) mod n
	mpz_powm(	c.get_mpz_t(), 	// Resulting Encrypted Message
				m.get_mpz_t(), 	// Message to be Encrypted
				e.get_mpz_t(), 	// Key Pair (n, e) private
				n.get_mpz_t());	// Key Pair (n, e) shared
}

Decryption:

// Decrypt Function
void decrypt(	  mpz_class& m, // Resulting Message
			const mpz_class& c, // Message
			const mpz_class& d, // Keys
			const mpz_class& n)
{
	//Decrypt: m = (c ^ d) mod n
	mpz_powm(	m.get_mpz_t(),	// Resulting Decrypted Message 
				c.get_mpz_t(),	// Encryted Message
				d.get_mpz_t(),	// 
				n.get_mpz_t());
}

Breaking RSA

To "break" RSA, you need a large amount of processing power. This can be as simple as using your computer's GPU, or a cloud cluster like Amazon's AWS. One way to break an RSA encrypted message is to factor n using a speedy algorithm. A great algorithm to factor a large number is Pollard's Rho Algorithm. If you're interested in using GPU power like CUDA, there are several GPU factoring tools available.

Using C++

// Pollard's rho algorithm
bool FactorRho(const mpz_class& n, mpz_class& result)
{
	mpz_class x = mpz_class(2);
	mpz_class y = mpz_class(2);
	mpz_class d = mpz_class(1);
 
	while(d == mpz_class(1))
	{
		// X <-- f(x)
		x = x * x + 1;
		mpz_mod(x.get_mpz_t(), x.get_mpz_t(), n.get_mpz_t());
 
		// Y <-- f(f(y))
		y = y * y + 1;
		mpz_mod(y.get_mpz_t(), y.get_mpz_t(), n.get_mpz_t());
		y = y * y + 1;
		mpz_mod(y.get_mpz_t(), y.get_mpz_t(), n.get_mpz_t());
 
		// D <-- GCD(abs(x-y), n)
		d = x - y;
		mpz_gcd(d.get_mpz_t(), d.get_mpz_t(), n.get_mpz_t());
	}
	if(d == n)
	{
		return false;
	}
	else
	{
		result = d;
		return true;
	}	
}

Conclusion

RSA is a popular cryptography algorithm that is widely used across many platforms. Hopefully this article gives some insight on how to implement a basic version of key generation, encryption, and decryption functions.