September 24, 2019

The RSA CryptoSystem

In this post we take a break from Cryptopals and investigate the RSA cryptosystem!

The RSA CryptoSystem

Introduction

Taking a break from the Cryptopals challenges, this week we are going to examine the basic theory behind RSA encryption.  Unlike most of the ciphers in previous crypto posts, these systems are known as asymmetric ciphers.  An asymmetric cipher, in very basic terms, uses a public and private key pair to perform encryption and decryptions, respectively.  To further simplify, RSA uses the mathematical constructs of multiplication, modular exponentiation (exponents in a modulo field), and inverse modulo to transform one number into another number.  This can be used to encrypt messages/data by converting a string into a number, typically seen using hex encoding in CTF problems.  With that, let's jump into the theory!

The Basis of RSA - Primes!

RSA utilizes two concepts in math to craft an encryption scheme.  The first of these principles is the difficulty of factoring large numbers into their prime components.  In both systems, we take two very large primes called p and q.  These primes constitute the private key of the system, that is:

$$k_{private} = (p,q)$$

This is used to construct a public key, which is the product of p and q:

$$n = p*q$$

$$k_{public} = (n, e)$$

The number e is known as the exponent, which is discussed in the next section.

The key takeaway from this is that the public key encodes information about the private key.  The reason that we can share this public key with others is due to the integer factorization problem.  Multiplication is not a very costly operation, making calculation of n a cheap process.  Finding two primes which multiply to n, however, can be very difficult.  Say you wanted to find a factor of a number m by naive brute force.  You would have to potentially loop over all numbers i where i < m. It may be tempting to assume this would have time complexity O(m), but we must consider that the input is not the number itself, but the number of bits. Thus, if we let w be the number of bits in m:

$$O(log_2(m))$$

$$O(2^w)$$

The best known algorithm is the general number field sieve (GNFS), which still has a non-polynomial time complexity.  Thus, for an n with many bits we can share the public key freely without much worry!  Of course, this assumes no other vulnerabilities are introduced by the user's encryption patterns.

The Basis of RSA - Exponents!

Before I mentioned that RSA uses modular exponentiation.  After crafting an n, this is the final decision to be made before the system is determined and ready for use. This exponent, named e, is chosen such that it is co-prime to another construct called the totient.  Calculating the totient is simple and involves p and q:

$$\phi (n) = (p-1)*(q-1)$$

The exponent e is chosen such that it is less than and co-prime to this totient.  Once e is found, we calculate one final value before having all the tools needed to encrypt and decrypt information.  This number, d, is the modular multiplicative inverse of e modulo n:

$$d = \frac{1}{e}mod(\phi)$$

With that calculation complete, we have all the tools needed to use the RSA system.

RSA Encryption

Encrypting a message m with RSA to get the ciphertext c is as simple as calculating:

$$c = m^e mod(n)$$

This operation is efficient with e values which are relatively small to p and q.  Common values for e include 3 and 65537.  Once encrypted, the data can be sent to someone with the private key and safely decrypted.

RSA Decryption

To decrypt an RSA encrypted message we reverse the process by calculating:

$$m = c^d mod(n)$$

Like encryption, this number can be efficiently computed using modular power functions.  As mentioned earlier, for many CTF problems the message will be encoded in hex, so you may have to change the value to ASCII to get a flag.

Conclusion

That wraps up our discussion about RSA.  As you can see, the system is relatively simple.  Once you define three parameters, you have all the tools to encrypt data easily using simple arithmetic operations.  In future articles we will take a look at some past CTF problems which involve poorly implemented RSA or insecure usage of RSA.  This will be the basis for examining the flaws of the system and how information leaks can occur.