Chapter 7 Applications to cryptography
Secret ciphers have been used since ancient times to send messages securely, for instance in times of war or diplomatic tension.
Nowadays sensitive information of a medical or financial nature is often stored in computers, and it is important to keep it secret.
Throughout this section, we shall assume that the alphabet that we are working with only consists of the upper case letters A,B,\(\ldots\),Z.
Caesar shift ciphers
Figure 7.1: Julius Caesar
the letters as integers, say A=\(0\), B=\(1\), \(\ldots\), Z=\(25\), and then adding \(1\) to each. In order to encipher Z as A, we must add \(\text{mod}~(26)\), so that \(25+1\equiv 0\). Similar ciphers are obtained by adding some fixed integer \(k\) (known as the key), rather than \(1\): Julius Caesar used the key \(k=3\). To decipher, we simply apply the reverse transformation, subtracting \(k\text{ mod }~(26)\).
Frequency Analysis
There are two problems with the Caesar Shift cipher. The first is that the key space is small. There are only 25 non-trivial values for the key and we can easily exhaust all values in order to test which one was actually used.
The second problem concerns frequency analysis. In an ‘average’ piece of English language text, the letters tend to appear with a definite frequency. The letter ‘E’ is usually the most frequent, followed by the letter ‘T’, then ‘A’ and so on.
If we shift each character by a set amount, then the shifted value of ‘E’ is likely to be the most frequent, followed by the shifted value of the letter ‘T’ etc.
We only need to have an educated guess as to what one character has been shifted by, to discover the key used.
Affine shift ciphers
A slightly more secure class of ciphers uses affine transformations of the form \(x\mapsto ax+b\) \(\text{mod}~(26)\), for various integers \(a\) and \(b\).
To decipher successfully, we need to be able to recover the value of \(x\) uniquely from \(ax+b\). More precisely we need to know that if \(ax+b\equiv ay+b\) \(\text{mod}~26\) then \(x\equiv y\) \(\text{mod}~26\).
In the language of functions we want the affine transformation \(f:\mathbb Z_{26}\longrightarrow \mathbb Z_{26}\) defined by the rule \(x\mapsto ax+b\) to be one to one, or injective.
If we take \(a=5, b=3\) we have
ATTACK TOMORROW \(\to\) DUUDNB UVLVKKVJ
When is an affine shift injective?
Suppose that \(ax+b\equiv ay+b\) \(\text{mod}~26\). Then, subtracting \(b\) from both sides we see that \(ax\equiv ay\) \(\text{mod}~26\), and so \(a(x-y)\equiv 0\) \(\text{mod}~26\). This equation has the obvious solution \(x=y\), and if \(a\) is coprime to \(26\), then this is the only solution, since we may cancel the unit \(a\). If on the other hand \(a\) is not a unit, then \(\gcd(a,26)=d>1\) and we may choose \(r\) such that \(rd=26\) and \(s\) such that \(a=sd\). Now it is clear that \(ra=rds=26s\equiv 0\) \(\text{mod}~26\), and so for any \(x\) there is a \(y=x-r\) such that \(a(x-y)=ar\equiv 0\) \(\text{mod}~26\), yielding a second solution to the equation.
We conclude that the affine shift is injective if and only if \(a\) is a unit \(\text{mod }(26)\).
By counting the pairs \(a, b\) we see that there are \(\phi(26)\times26=12\times26=312\) such ciphers. Breaking such a cipher by trying all the possibilities for \(a\) and \(b\) would be tedious by hand (though simple with a computer), but again frequency searches can make the task much easier.
If the enciphering transformation is \(x\mapsto 7x+3 \text{ mod }(26)\), encipher GAUSS and decipher MFSJDG.
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 5 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 5; 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 7.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)\).
With \(p=677, e=7\) and \(k=2\)
ATTACK TOMORROW \(\to\) HQLAOX WEIWUHTF
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 2.25 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 ?
Cryptographic signatures/digital certificates
This system also gives a way of signing a message, to prove to a receiver that it comes from you and from nobody else.
The fundamental problem with digital signatures is the question of how you stop them being cut and paste from one document you did send onto another one you didn’t. Once this problem is solved (which is done using hash functions, described below) the idea is to turn public key encryption on its head, publishing a decryption key that everyone knows and keeping secret an encryption key.
Digests
The first stage in digitally signing the document is to produce a so called digest (also known as a hash), that is, a short summary of the document, typically 1024 bits long. The method of producing the digest varies between the different secure signature systems, but it is an algorithm chosen to make it unlikely that two different messages will produce the same digest. This digest is attached to the message and proves that it has not been tampered with.
So long as the message and its digest match we have reason to believe the message is authentic.
But the digest algorithm is public so anyone tampering with the message just has to also replace the digest too. To prevent that, the digest is encrypted using the secret encryption algorithm.
Verifying the message
On receipt of the message the recipient deciphers the digest using the published decryption key, and then uses the digest algorithm to produce their own version of the message digest directly from the message contents. If the decrypted digest matches the new one then the signature and the message (almost certainly) belong together and the message is genuine. The security of these systems relies in part on the reliability of the digest used.
The Birthday Attack
This is a method to circumvent digital signatures based on the Birthday paradox. The classical birthday paradox states that in a group of 23 people there is a probability of 1/2 that at least two of them share the same birthday. In a larger group the odds are even higher.
Assuming that birth dates are uniformly distributed (actually they are not) and ignoring leap years there are 365 possible birthday dates. Consider all the possible collections of birthdays assuming that no two people in a group of size \(n\) share a birthday.
The first person in the group has 365 possible birthdays, the second has 364 and so on. Hence there are \(365!/(365-n)!\) possibilities for the list of birthdays, so the probability that no two people share a birthday is:
\[ \frac{365!/(365-n)!}{365^n}. \]
It follows that the probability that at least two people have a shared birthday is
\[ 1-\frac{365!/(365-n)!}{365^n}. \]
Attacking the digital signature
The security of the digital signature depends on the assumption that different messages have different hashes. If you have a large collection of messages then, as with birthdays, the odds that two messages have the same hash is higher than you might think. The birthday attack exploits this weakness.
If a 64 bit hash is used, that is each message is converted to a digest which is stored as a binary number with 64 digits, there are \(2^{64}\) (or approximately \(1.8 \times 10^{19}\)) different digests. If these are all equally probable (the best case), then given only \(5.1 \times 10^9\) different messages there is a probability of more than \(0.5\) that two of them have the same digest. We say that we have a probability of more than \(1/2\) of generating a collision.
The attack in practice
Alice wants to get Bob to sell his house for five pounds. She needs to get his digital signature on a contract to this effect. She produces a fair contract in which he agrees to sell his house for, say, three hundred and fifty thousand pounds, and an unfair contract in which he agrees to sell for five pounds.
She now pads the two contracts by adding spaces, punctuation and florid legal phrases in lots of different ways producing an enormous number of fair and of unfair contracts. Eventually she hopes a version (contract A) of the fair contract will have the same hash as some version (contract B) of the unfair contract. This is slightly different from the true Birthday paradox and the calculation is more delicate, but essentially the same idea works.
In practice this does not mean that Alice can force Bob to sell the house for five pounds. If she tries to do so Bob can produce the fair contract, and show that his signature fits it too. The real importance of the attack is that once it has been exhibited the signature system is no longer regarded as fully trustworthy.
Modern digital signature keys are chosen to be so long that even this attack is infeasible. Nonetheless the calculations of feasibility rely on the assumption that hash values are evenly distributed. This assumption may be false among the space of messages to be hashed, and at the CRYPT2004 conference collisions were announced in the widely used SHA-0, MD4, MD5, HAVAL-128, and RIPEMD hash algorithms.
Weakening the discrete logarithm
The same paradox weakens discrete log encryption. Recall that the security of the system relies on the fact that it is hard to find a value \(n\) such that \(y=x^n\text{ mod}~(p)\). Trying a brute force attack we would expect to need to test around \(p/2\) values of \(n\) to have a \(50\%\) chance of finding the correct value.
Instead we can compute values of \(x^r\) and \(yx^{-s}\). Because of the birthday paradox it takes only about \(1.2\sqrt p\) steps on average to find a pair \(x^r=yx^{-s}\) and so \(y=x^{r+s}\) solving the discrete log problem.
Note that computationally we have traded time for storage. The programme we write to implement such an attack will not take as long as a brute force attack to run, however it will need a lot of storage (Hard disc or RAM) in which to store the values of \(x^r\) and \(yx^{-s}\) for comparison. This trade off, of time against space, is a common one in algorithm design.