8.1 Ciphers using modular exponentiation
Discrete log encryption
We can do rather better with ciphers based on Fermat’s Little Theorem.
The idea is as follows. We choose a large prime \(p\), and an integer \(e\) coprime to \(p-1\). For encoding, we use the transformation \({\mathbb Z}_p\to{\mathbb Z}_p\) given by \(x\mapsto x^e\) \(\text{mod}~(p)\).
(We saw in Chapter 6 how to calculate large powers efficiently in \({\mathbb Z}_p\).)
With \(p=29, e=5\)
ATTACK TOMORROW \(\to\) AVVADI VTMTRRTN
Deciphering the message
If \(0<x<p\) then \(x\) will be coprime to \(p\), so \(x^{p-1}\equiv 1\) \(\text{ mod}~(p)\). To decipher, we first find the multiplicative inverse \(f\) of \(e\text{ mod}~(p-1)\), that is, we solve the congruence \(ef\equiv 1 \text{ mod}~(p-1)\), using the method described in Chapter 6; this is possible since \(e\) is a unit \(\text{ mod}~(p-1)\). Then \(ef=(p-1)k+1\) for some integer \(k\), so \[(x^e)^f=x^{(p-1)k+1}=(x^{p-1})^k.x\equiv x\text{ deciphered efficiently}\].
Suppose that \(p=29\) (unrealistically small, but useful for a simple illustration). We must choose \(e\) coprime to \(p-1=28\), and then find \(f\) such that \(ef\equiv 1\text{ mod }(28)\). If we take \(e=5\), for example, so that encoding is given by \(x\mapsto x^5\text{ mod }(29)\), then \(f=17\) and decoding is given by \(x\mapsto x^{17}\text{ mod }(29)\). Note that \[(x^5)^{17}=x^{85}=(x^{28})^3.x\equiv x\text{ mod }(29)\] since \(x^{28}\equiv 1 \text{ mod }(29)\) for all \(x\) coprime to \(29\), so decoding is the inverse of encoding.
In Example 8.2, encipher \(9\) and decipher \(11\).
Block ciphers
Representing individual letters as numbers tends to be insecure, since an eavesdropper could use known frequencies of letters. A better method is to group the letters into blocks of length \(k\), and to represent each block as an integer \(x\). (If the length of the message is not divisible by \(k\), one can always add extra meaningless letters at the end.)
We choose \(p\) sufficiently large that the distinct blocks of length \(k\) can be represented by different congruence classes \(x\not\equiv 0\text{ mod}~(p)\), and then the encoding and decoding are given as before by \(x\mapsto x^e\text{ mod}~(p)\) and \(x\mapsto x^f\text{ mod}~(p)\).
Example: We encode pairs of letters as follows
AA\(\mapsto 1\), AB\(\mapsto 2\), \(\dots\), AZ\(\mapsto 26\), \(BA\mapsto 27\), \(\dots\), ZZ\(\mapsto 26^2=676\).
With \(p=677, e=7\) and \(k=2\)
ATTACK TOMORROW \(\to\) GFYOMA RHYDVRMH
Breaking this cipher seems to be very difficult. Suppose, for instance, that an eavesdropper has discovered the value of \(p\) being used, and also knows one pair \(x\) and \(y\equiv x^e\text{ mod}~(p)\).
To break the cipher, the eavesdropper needs to know the value of \(f\) (or equivalently \(e\)).
If \(p\) is sufficiently large (say a few hundred decimal digits) then there is no known efficient algorithm for calculating \(e\) from the congruence \(y\equiv x^e\text{ mod}~(p)\), where \(x, y\) and \(p\) are known. This is sometimes called the discrete logarithm problem, since we can regard this congruence as a modular version of the equation \(e=\log_x(y)\).
The whole point of this cipher is that, while exponentials are easy to calculate in modular arithmetic, logarithms are apparently difficult.
Find a value of \(e\) coprime to \(28\) such that \(27\equiv 10^e \text{ mod }(29)\).
Key exchange
The one weakness of this type of cipher is that the sender and receiver must first agree on the values of \(p\) and \(e\) (called the KEY of the cipher) before they can use it. How can they do this secretly, bearing in mind that they will probably need to change the key from time to time for security ? They could, of course exchange this information in enciphered form, but then they would have to agree about the details of the cipher used for discussing the key, so they are no nearer solving the problem.
Alice and Bob agree to use a prime number \(p\) and base \(g\). Alice chooses a secret number \(a\) and sends Bob the number \[ A=g^a\mod p. \] Bob chooses a secret number \(b\) and sends Alice \[ B= g^b\mod p. \] Alice calculates \(B^a\mod p\) and Bob calculates \(A^b\mod p\). This is their secret key.
For example, if \(p=29, g=5\). If Alice chooses \(a=7\) and Bob chooses \(b=11\), then \[ A=5^7\mod 29=28 \] while \[ B=5^{11}\mod 29 = 13. \] Now \(s=28^{11}\mod 29 = 28 = 13^7\mod 29\). This is referred to as the Diffie-Helman Key Exchange protocol or sometimes the Diffie-Helman-Merkle Key Exchange protocol.
Public key cryptography
One can avoid this difficulty by using a public-key cryptographic system. Each person using the system publishes numerical information which enables any other user to encipher messages, without giving away sufficient information to allow anyone but him/herself to decipher them.
The most famous of these systems is the RSA encryption system publicly described first by Rivest, Shamir and Adelman of MIT in 1977. An equivalent system had been described in a top secret document at GCHQ by Clifford Cocks in 1973.
Symmetric v Asymmetric encryption schemes
An encryption method is said to be symmetric if anyone in possession of the encryption algorithm and key is in a position to decrypt all messages encrypted with it.
Examples:
- Affine shift ciphers - given the algorithm \(x\rightarrow ax+b \mod{n}\) and the constants \(a,b,n\) one can compute the inverse function \(x\rightarrow c(x-b)\) by solving the equation \(ac\equiv 1\mod{n}\).
- Discrete log ciphers - given the algorithm \(x\rightarrow x^e \mod{p}\) and the constants \(e,p\) one can compute the inverse function \(x\rightarrow x^f\) by solving the equation \(ef\equiv 1\mod{p-1}\).
The Enigma Machine
Notice that some historical ciphers were symmetric in a stronger sense, in that the encryption and decryption functions were the same function! Simple examples are given by the shift cipher \(x\rightarrow x+13\), and the affine shift \(x\rightarrow -x\). A much more sophisticated example was given by the enigma machine. However it was setup to encrypt a message, the same setting (or key) would be used to decrypt it.
RSA encryption
As in the discrete log system the encryption is achieved by taking powers.
To set up an RSA cipher one chooses a distinct pair of large primes \(p\) and \(q\), calculates \(n=pq\), and chooses a positive integer \(e\) coprime to \(\phi(n)=(p-1)(q-1)\).
The encryption algorithm is given by \(x\rightarrow x^e\text{ mod}~(n)\) and the key, which is freely published is the pair \((e,n)\).
Example: The encryption key might be \((7,143)\), but it could not be \((3,143)\) or \((5,143)\). Why not?
Deciphering RSA
As with the discrete log cipher the decryption algorithm is given by \(x\rightarrow x^f\text{ mod}~(n)\) for a suitable choice of exponent \(f\).
This choice must satisfy \((x^e)^f\equiv x\text{ mod}~(n)\) for every \(x\), and it should be clear that Euler’s theorem tells us how to choose \(f\).
We know that for \(x\) coprime to \(n\), \(x^{t.\phi(n)+1}\equiv (x^{\phi(n)})^t.x\equiv 1^t.x\equiv x\text{ mod}~(n)\), so at least for these values of \(x\) it is sufficient to choose \(f\) so that \(ef\equiv 1\text{ mod}~(\phi(n))\).
In fact, whether or not \(x\) is coprime to \(n\), \(x^{ef}\equiv x^{t(p-1)(q-1)+1}\equiv x\mod{p}\) and \(x^{ef}\equiv x^{t(p-1)(q-1)+1}\equiv x\mod{q}\). So we see that both \(p\) and \(q\) divide the difference \(x^{ef}-x\), and since they are coprime Corollary 3.27 tells us that their product also divides this difference so \(x^{ef}\equiv x\mod{pq}\) as required, for all \(x\).
Now if we set up the RSA cipher then we know that \(n=pq\) so we can compute \(\phi(n)=(p-1)(q-1)\) and can therefore solve the equation for \(f\) in terms of \(e,p,q\). As we will next see this is essentially the only way we can compute \(f\)!
Why we (think we) know that RSA decryption is hard for the enemy
Suppose the enemy is able to compute \(\phi(n)\) and therefore to solve the equation \(ef\equiv 1\mod{\phi(n)}\) thereby finding the decryption key.
Then the enemy knows \(n\) and \(\phi(n)\). They therefore know the integers \(pq\) and \((p-1)(q-1)\). Taking the difference and adding \(1\) gives \(p+q\), so the enemy knows the two integers \(pq\) and \(p+q\). This is enough to compute the prime factorisation of \(n\).
To see this note that
\[(p-q)^2 =(p+q)^2-4pq.\]
From this we may extract \(p-q\) as well. Then knowing \(p+q\) and \(p-q\) we can compute both \(p\) and \(q\) as required.
The prime factorisation problem
Given an integer \(n\), how can we find the prime factors of \(n\)?
The prime factorisation problem is hard. The best methods currently take around \(18\) months of parallel processing (around \(50\) years of processor time) to factor an integer with around \(200\) digits. Typical \(1024\) bit RSA exponents have around \(300\) digits. In around 2007 Lenstra and his collaborators cracked a 200 digit number. Asked whether 1024 bit RSA ciphers were dead he replied:
“The answer to that question is an unqualified yes.”“
Suppose that \(p=89\) and \(q=97\) are chosen, so \(n=89\times97=8633\) is published, while \(\phi(n)=88\times96=8448=2^8\times3\times11\) is kept secret. The receiver chooses and publishes an integer \(e\) coprime to \(\phi(n)\), say \(e=71\). He then finds (and keeps secret) the multiplicative inverse \(f=119\) of \(71\text{ mod}~(8448)\).
This can be done using the Euclidean algorithm.
To check the answer, note that \(71\times119=8449\equiv 1 \text{ mod}~(8448)\).
To send a message, anyone can look up the pair \(n=8633, e=71\), and use the encoding \(x\mapsto x^{71}\text{ mod}~(8633)\). The receiver uses the decoding transformation \(x\mapsto x^{119}\text{ mod}~(8633)\), which is not available to anyone who does not know that \(f=119\). An eavesdropper would need to factorise \(n=8633\) in order to find \(\phi(n)\) and then \(f\). Of course, factorising \(8633\) is not so difficult, but this is just a simple illustration of the method, and significantly larger primes \(p\) and \(q\) would pose a much harder problem.
Factorising \(8633\), using the fact that \(\phi(8633)=8448\)
As in the description above we know \(pq=8633\) and \((p-1)(q-1)=8448\), so \(pq-(p+q)+1=8448\). From this we conclude that \(8633-8448+1=p+q\), so we put \(p+q=186\).
Now we see that \((p-q)^2=(p+q)^2-4pq=186^2-4.8633=64\) so \(p-q=\pm 8\). Now \(2p=(p+q)+(p-q)=186+8=194\) showing us that \(p=97\). Similarly \(2q=(p+q)-(p-q)=186-8=178\) so \(q=89\).
Of course our calculation has reversed the primes but this does not matter.
If my public key is the pair \(n=10147, e=119\), then what is my decoding transformation ?