So A transmits the message
What properties are desirable in E, D, e and d?
Traditionally, the keys were kept secret; more accurately, as the same key was used for both encryption and decryption, the key was kept secret. A and B have to agree on the key -- which must be pre-determined, as they cannot always communicate in secret [else there would be no need for encryption at all!]. This was always a danger point for spies in the field, or even for for more normal units -- possession of a code-book was proof to the enemy that you were a spy, and the capture of a code-book was an ever-present danger, which could lead to the enemy reading your messages or transmitting misleading messages for days or weeks until the loss was discovered. In addition, in the modern computer age, there is always the danger that a computer may be able to try all possible [or plausible!] keys using brute-force methods.
Here is the 9 o'clock news. The password for all spies in France today is ....So A [or anyone else] can generate [and, if necessary, broadcast] n = E (e, m). But only B [who is the only person to know d] can generate the decrypted message p = D (d, n) from n.
Obvious snag: e and d are functionally related, because
Minor digression: We have only defined classes such as NP for decision problems, for which the answer is just one bit [yes/no] of information. It is an abuse of notation, but only a small one, to use the same notations to describe functions which generate keys as their results.The trick is to have available a suitable function f. We invent d, the secret key, `at random', and use this function to generate e = f(d). For this to work, f must satisfy:
Note that, since e = f(d) is tractable, f -1 is in NP. For, if an oracle guesses d, then we can verify by computing e that d indeed was the secret key. If NP = P, then there are no trapdoor fuctions.
Even if NP /= P, this doesn't, of itself, show that trapdoor functions exist; and, of course, we don't know any trapdoor functions [for if we did, that would show that NP /= P]; but there are some strong and plausible candidates.
A typical such candidate is given by multiplication. To multiply, say, 7×11×13 = 1001, is a very simple routine calculation, with a simple algorithm which is clearly polynomial in the numbers of digits of the answer. But the inverse process of factorisation is, apparently, much harder. A systematic test of all possible factors in polynomial not in the number of digits but in the actual values. There are all sorts of efficiency hacks, but none yet known which put factorisation clearly into P. The most difficult case is where a number is the product of two large primes. So the secret key, d consists essentially of two large [well over 100 digits] primes, and the public key consists of their product.
Note that factorisation is in both NP and co-NP [this is not trivial -- it depends on some advanced number theory], so it is thought very unlikely to be NP-complete; indeed, it is probably too likely to be in P to be an ideal candidate, but it remains the best-known one. We might like our candidate trapdoor function to have an NP-complete inverse, for the NP-complete problems are, in some sense, the hardest in NP, but there are theoretical reasons why this is actually unlikely. One of these is the fact that f is required to be bijective -- you need to be able to invert the encryption -- corresponding very loosely to the idea that there has to be a unique lucky oracle; but the NP-complete problems typically have lots of possible oracles -- for example, there may be many Hamiltonian circuits for a given network. [This idea, and others, can be made more precise.]
Another consideration is that tractability is defined in terms of worst-case behaviour; but we need to be able to construct public keys quickly and easily. Here again, the NP-complete problems are unhelpful; for example, most instances of 3SAT can be disposed of very easily -- there is a very fine line between instances that are very quickly shown to be unsatisfiable and those that have lots of satisfying assignations. We need suitable keys to be common, so that an average intractability is more relevant.
Finally, thinking of a clever trapdoor function f is insufficient; we also need to design tractable algorithms D and E such that D (d, E (f(d), m)) = m for all m. An intractable D would be particularly useless!
There is much more about this topic in the third-year Coding and Cryptography module.
So, the idea is that the possessor and only the possessor of the decryption key can send a message which encrypts to the original. So A too can have keys d' and e' = f(d'), where e' is freely announced; A's `signature' is the decryption D (d', m') of some suitable message m', which can [and should!] change with every message [`timed at 12:34 on ...']. A includes a signature as part of the message to B. When B decrypts the received message, it reads something like `ENEMY WILL ATTACK AT DAWN, SEND REINFORCEMENTS gIbBeRiSh', whereupon encrypting `gIbBeRiSh' with A's public key reveals A's message m'.
If A's message is not secret, but its authenticity is important, then the same idea can be used to sign any message; these days, e-mail messages or news articles often come with PGP [`Pretty Good Privacy'] codes, which consist of several lines of gibberish which you can encrypt with the author's public key to verify authenticity. However this doesn't solve all problems -- how do you know that the public key really came from A? And how do you know that A's secret key has not been revealed [e.g. under torture] to the enemy? And how can A prove that he did not send a message [e.g. as a defence to libel]?
Hooke's Law, that the extension of a spring is proportional to the force, or in Latin ut vis ut extensio, was originally published in the anagrammatic form eeiinosstttuuvx, so that he could establish his priority without revealing his discovery. Today he could use a zero-knowledge proof; this is a probabilistic proof that you know something without revealing what it is that you know.
Example: Graph 3-colourability is an NP-complete decision problem. Suppose I have a 3-colouring of a graph; you are suitably amazed, but demand proof; I don't want to reveal the actual 3-colouring. How to proceed?
For this particular problem, the number of repetitions needed to make the chance small is likely to be large and hence to involve a prohibitive amount of work. There are number-theoretic problems where the chance of being caught out is around 0.5, which makes the method realistic. Nevertheless, there is an element of fraud about the whole exercise. If I can tractably solve an arbitrary case of an apparently difficult problem, then NP = P, there are no trapdoor functions, and the encryptions in the proof are tractably decryptable. But at least I become very famous.
G12FCO home page.
Previous lecture.
Next lecture.
Problem Class 4 .