Public Key Encryption, Perfect (Forward) Secrecy and Backdoors

Textbook RSA

The first thing discussed here is textbook RSA, to illustrate how simply a secure system can be understood. Having said that, textbook RSA as presented here is not secure. In terms of mathematics, all we need to be familiar with is multiplication since anything else we need can be covered minimally. Having some intuition into what public key encryption looks like will be helpful in some of the discussion later.

Some Quick Notation

First, we say \(a\) evenly divides \(b\) if when \(b\) is divided by \(a\) there is no remainder left. For example, \(\frac{10}{5}=2\), so \(5\) evenly divides \(10\). This is written as \(a | b\) and if \(a|b\) we say \(a\) is a divisor of \(b\).

Now for \(5 \times 5 \times ... \times 5\) where we have multiplied \(k\;5\)'s we write this as \(5^k\), we will refer to this as exponentiation by \(k\). Some may also need to refamiliarise themselves with prime numbers (wiki link).

On top of this, we can say two numbers are co-prime if they do not share any divisors. \(7\) and \(10\) are co-prime because the divisors of \(10\) (\(2\) and \(5\)) are not divisors of \(7\). We will write the number of numbers that are less than a number \(N\) and co-prime to that number \(N\) as \(\phi{(N)}\). So as above \(\phi{(7)}=6\) since the numbers co-prime to (and less than) \(7\) are \(1,2,3,4,5\textrm{ and }6\). You will probably notice that for a prime number \(p\) we have \(\phi{(p)}=p-1\) since the only non-one divisor of \(p\) is itself, which obviously isn't less than \(p\). We will use the result \(\phi{(pq)} =(p-1)(q-1)\) where \(p,q\) are both prime when we describe RSA - note that this isn't true if they aren't both prime.

Lastly, when we reduce a number \(\mod N\) we get it's remainder when divided by \(N\). For example: $$10 \equiv 3 \mod 7, \\ 12 \equiv 5 \mod 7.$$

The RSA Cryptosystem

To set up RSA we need two different prime numbers which we will refer to the first as \(p\) and second as \(q\), in a real world setting these numbers would be huge numbers (typically more than 300 digits each in base 10) so that it would take a long time for computers to factor their product \(N=pq\). There are easy, efficient methods to find candidates for \(p,q\) which I won't cover here.

Now for an important theorem: If \(a\) and \(N\) are co-prime, then \(a^{\phi{(N)}}\equiv1 \mod N\). I won't cover the proof of this here because it requires more background. This theorem is the key to RSA encryption and decryption. We now have all the tools we need to understand how to encrypt and decrypt with RSA.

For some message \(M < N\) we encrypt to encrypted text \(c\) with \(c = M^e \mod N\) where \(e\) is some number co-prime to \(N\) that we can choose freely. When we have decided on \(e\) we can use Euclid's Algorithm to find a \(d\) such that \(e \times d \equiv 1 \mod \phi{(N)}\) where we have found \(\phi{(N)}\) by \(\phi{(N)}=(p-1)(q-1)\). We can use such a \(d\) to decrypt since $$\begin{aligned} (M^e)^d &\equiv M^{1+k\phi{(N)}} &\mod (N) &\hspace{3em} \textrm{for some integer }k\\ &\equiv M(M^{k\phi{(N)}}) &\mod (N) &\\ &\equiv M(M^{\phi{(N)}})^k &\mod (N) &\\ &\equiv M \cdot 1^k &\mod (N) &\hspace{3em} \textrm{by the theorem}\\ &\equiv M &\mod (N) \end{aligned}$$

Hence it follows that exponentiation by \(d\) is the inverse of exponentiation by \(e\), so we can use these operations to encrypt and decrypt. The key to this system is that given some \(e\), we cannot find \(d\) such that \(ed \equiv 1 \mod \phi{(N)}\) unless we know what \(\phi{(N)}\) is. The value of \(\phi{(N)}\) cannot be calculated without first knowing \(p,q\) such that \(N=pq\). So as long as we keep \(p,q\) and \(d\) secret we can publicly share \(N,e\) so that other people can encrypt messages, but only we can decrypt them. For just anyone to decrypt they would need the value of \(\phi{(N)}\), to do this it would be necessary to first find \(p,q\) by factoring \(N\).

Example

Setup: \(p=3, q=11, N=p \times q=33,\,\,\phi{(33)} = 2 \times 10 = 20\) and we choose \(e = 3\) so by the euclidean algorithm \(d = 7\) since \(e \times d \equiv 3 \times 7 \equiv 1 \mod (\phi{(N)} = 20)\). We then publish \(N\) and \(e\) and keep \(d\) private.

Encrypt: Someone wishes to send us the message \(5\). Using the public values of \(N\) and \(e\) our encrypted message is then \(c \equiv m^e \equiv 5^3 \equiv 125 \equiv 26 \mod (N = 33)\). So they would then send the encrypted message, \(26\) which we will refer to as \(c\).

Decrypt: To retrieve the message we can then use our private value \(d\) to calculate \(c^d \equiv 26^7 \mod 33 \equiv 5 \mod 33\) and we have retrieved the secret message \(5\).

With our small values of \(p\) and \(q\) we can easily find what was encrypted by checking every value, for example if \(16\) was sent we could simply calculate every value \(1^3, 2^3, 3^3, 4^3, ...\) until we find one that equals \(16\). This doesn't require the secret value of \(d\), but when we use large enough values of \(p\) and \(q\) the number of possibilities to check becomes computationally infeasible.

Real-world RSA

I have covered RSA here in a very basic way which is ideally accessible to those without any mathematical background, there are many nuances and improvements that are considered in RSA as it is used today but they all hinge on the above theorem and calculations. Many of the problems with textbook RSA can be solved by padding schemes such as OAEP padding. There are some performance improvements that are also considered such as using the Chinese Remainder Theorem for decryption and recommendations on parameter choices that are also considered in real world cases, but these are not covered here. The details of these are easy to find online or in many textbooks on the matter if one wished to implement the RSA cryptosystem themselves - although it is advised an open source, widely vetted implementation such as in OpenSSL is used.

What is Perfect Secrecy and Perfect Forward Secrecy?

Perfect secrecy is the idea that encrypted ciphertext conveys no information about the original message - that it is just as likely that you sent any message as you sending any other message. Perfect forward secrecy is the idea that even if a private key is leaked at a later date, the previously sent messages are still unable to be decoded because a specific session key was generated and then discarded for that session.

Encryption Backdoors, Kerckhoffs's principle and Open Source Cryptography

There is much talk of Governments introducing so called 'backdoors' into cryptography, but there's a few key problems with this:

• Mathematics is mathematics, we can't change the algorithm to support this idea and since these algorithms are widely known and published anyone can create secure encryption using them. In the case of AES many processors already include instruction sets to implement AES.
• In cryptography we have Kerchhoff's principle - a cryptosystem should be secure even if everything, except the key, is public knowledge. This means that for us to be even moderately convinced that a cryptosystem is secure, all of it's inner workings and details are public. Now when we pair this idea with Open Source...
• All widely used encryption software is Open Source. Following from the last point it's much more secure to use an Open Source encryption package than a proprietary one, because more eyes have been able to spot and fix flaws. It also means that an introduction of a backdoor into the software side isn't ever going to be inconspicuous.

Considering the above, backdooring the cryptosystems themselves doesn't really make sense. If one were backdoored it would be seen and fixed, or if necessary anyone could simply go and create their own. The answer to encryption isn't to backdoor the encryption itself, it's up to companies to design their systems in a way that doesn't hinder law enforcement. Ultimately, if encryption is being used by ne'er do wells, there is not much that can be done to stop them from having access to encryption.