| Modulus | |
|---|---|
| Public exponent | |
| Private exponent | |
| Plaintext | |
| Ciphertext |
RSA is based on the difficulty of factoring integers. It is a public key cryptosystem, which means that there are separate encryption and decryption keys. We first form the modulus , where and are two distinct primes. Note that there are very quick algorithms for primality testing, so choosing random numbers and checking for primality suffices. But certain care should be taken, such as avoiding small primes, avoiding primes that are too close to each other (to guard against Fermat factorization), etc.
Next, choose a public exponent with gcd, and compute the private exponent . Sometimes people start by choosing and computing to ensure that isn't small and easy to guess. One common choice for is since this is a prime with certain nice properties. Thus, the public key is the pair , and the private key is .
Recall that is the number of integers with such that gcd. This is not easy to compute. There are some nice formulas if we can factor integers. For a prime . For a power of a prime, . One other nice property is whenever gcd. This tells us for with and distinct primes that . This can be also used to derive the more general formula .
Given the factorization of , we can clearly compute . In fact, if we know , we can also factor . Simply observe that , or . Since and are the roots of the quadratic equation $$(x - p)(x - q) = x^2 - (p + q)x + pq = x^2 - ((n+1) - \phi(n))x + n,$$ we can easily factor given knowledge of by applying the quadratic formula.
For example, suppose , and we're told that , but we don't know the factors and . We know that , so we form the polynomial . We can find the roots using the quadratic formula: . Thus, .
Now to encrypt a plaintext message , we simply compute the ciphertext as $$C = M^e \bmod{n}.$$ We similarly decrypt by computing $$M = C^d \bmod{n}.$$
We simply need to show that . Since , we can write for some integer . Recall Euler's Theorem, which says that if gcd, then . In other words, our numbers live mod , but the exponents live mod . So there are two cases: either gcd or .
In the first case, Euler's Theorem tells us that , so $$M^{1 + k\phi(n)} \equiv M{\left(M^{\phi(n)}\right)}^k \equiv M \cdot 1^k \equiv M \pmod{n}.$$
If gcd on the other hand, things are slightly trickier. Notice that since , the gcd can either be , or . If the gcd is , then both and any power of is , and there is nothing to prove. If the gcd is (the case for is symmetric), then , and . The simpler case of Euler's Theorem for prime moduli (i.e., Fermat's Little Theorem) is that if , then . Therefore, $$M^{1 + k(p-1)(q-1)} \equiv M{\left(M^{q-1}\right)}^{k(p-1)} \equiv M\cdot1^{k(p-1)} \equiv M \pmod{q}.$$
Since , and , we know that is a multiple of , and a multiple of . It is thus a multiple of since gcd (this is essentially the Chinese Remainder Theorem). So , or
In practice, RSA is used to send a key to use with a faster algorithm like AES. Although factoring is hard, there are subexponential-time algorithms for it, which means we need to use keys with over 3,000 bits just to match the security of 128-bit AES. To match the security of 256-bit AES, we require over 15,000-bit keys. This makes elliptic curve cryptography more attractive, since in the ECC setting, we can get away with 256-bit keys and 512-bit keys in these two situations, respectively. For example, it takes on the order of minutes to generate 15,000-bit RSA keys on a modern computer.
Nevertheless, RSA is still the main public-key system in use today. Although we require large keys, the math behind it is extremely simple. It is nothing more than modular exponentiation. In addition, RSA provides a very nice and simple scheme for digital signatures: simply sign with your private key, and the recipient will verify the signature using your public key.