Some aspects of secure communication

For at least two thousand years there have been people who wanted to send messages which could only be read by the people for whom they were intended. When a message is sent by hand, carried from the sender to the recipient, whether by a slave, as in ancient Greece or Rome, or by the Post Office today, there is a risk of it going astray. The slave might be captured or the postman might deliver to the wrong address. If the message is written in clear, that is, in a natural language without any attempt at concealment, anyone getting hold of it will be able to read it and, if they know the language, understand it.

In more recent times messages might be sent by telegraph, radio, telephone, fax or e-mail but the possibility of them being intercepted is still present and, indeed, has increased enormously since, for example, a radio transmission can be heard by anyone who is within range and tuned to the right frequency whilst an e-mail message might go to a host of unintended recipients if a wrong key on a computer keyboard is pressed or if a ‘virus’ is lurking in the computer.

Virtually anyone who can read will have come across codes or ciphers in some form. Even an occasional attempt at solving crosswords, for example, will ensure that the reader is acquainted with anagrams, which are a form of cipher known as transpositions. Enciphered messages also appear in children's comics, the personal columns of newspapers and in stories by numerous authors from at least as far back as Conan Doyle and Edgar Allan Poe.

Nowadays large numbers of people have personal computers and use the internet and know that they have to provide a password that is enciphered and checked whenever they send or receive e-mail. In business and commerce, particularly where funds are being transferred electronically, authentication of the contents of messages and validation of the identities of those involved are crucial and encipherment provides the best way of ensuring this and preventing fraud.

It is not surprising then that the subject of codes and ciphers is now much more relevant to everyday life than hitherto. In addition, public interest has been aroused in ‘codebreaking’, as it is popularly known, by such books and TV programmes as those that have been produced following the declassification of some of the wartime work at Bletchley, particularly on the Enigma machine.

Cipher systems range in sophistication from very elementary to very advanced.

A spy operating in country X on behalf of country Y has the problem of communicating with his controller in such a way as to protect both himself and the contents of his messages. No matter how he sends his messages they will have to be ‘modified’ somehow so that their true meaning is hidden from anyone but the intended recipient. There are methods, such as the use of microdots or ‘invisible’ ink, which do not, per se, involve encipherment although some ‘modification’ of the text even in such cases would probably be used to provide extra security. When we say that a text has been ‘modified’ we do not necessarily mean that it has been enciphered but that the ‘secret’ text is not simply sent in an unaltered form: it might, for example, be hidden inside an apparently innocuous message.

Hiding a secret text inside an innocuous one has the advantage that, being apparently unenciphered, it will not automatically attract the interest of unintended recipients or interceptors, such as the security forces of country X. A disadvantage is that it may not be too easy to construct a realistic non-secret text in which to embed it. Here is a simple illustration.

Example 7.1 (‘Part of a letter from Agent 63’)

As I was walking through the centre of town yesterday morning at about eleven thirty I chanced to see Ron Kingston. He was alone, driving a newish-looking ultramarine car, a Ford Escort. Previously he's had only second-hand cars, not often less than three years old.

Historical background

In Chapter 2 we looked at simple substitution ciphers and we saw how these can be solved by the use of frequency counts if ‘sufficient’ cipher text is available. How many letters are always ‘sufficient’ is a matter for debate, but it is probably true that 200 letters will normally suffice whereas 50 might not. For our purposes let us assume that if only 25 letters of cipher are available then the cipher is safe. Since a limitation of message lengths to no more than 25 letters would be too restrictive we conclude that the use of a simple substitution cipher is impractical. If, however, we use not one but several different simple substitution alphabets, switching between the alphabets every time we encipher a letter, we can increase the security of the system. As a rough guide: if we use N different alphabets it should be possible to make the cipher safe for single messages of up to 25N cipher letters; but this simple rule needs qualification. If the substitution alphabets are related in some way the recovery of any one of them may lead to recovery of the others. On the other hand, in some systems, additional features may ensure that cipher messages of much greater length than 25N are secure.

Characteristics of codes

As was mentioned in Chapter 1, the distinction between codes and ciphers is not always clear, but one might reasonably say that whereas most codes tend to be static most ciphers are dynamic. That is to say that a letter or phrase enciphered simply by means of a code will produce the same cipher each time the code is used, whereas a letter or phrase enciphered by a cipher system will generally produce different cipher text at different times. This is because most cipher systems involve one or more parameters, such as keywords or, as we shall see later, wheel settings, which are changed at regular or irregular intervals and so cause the cipher outputs from the same plaintext to be different. The basic mechanism, or algorithm, for generating the cipher doesn't change, but the parameters do. In general, a code has no such parameters though the entire code may itself be changed, in which case it becomes a different code. In practice this is achieved by issuing a new code-book every now and then. Using this criterion the Julius Caesar cipher would be classed as a code, because the encipherment of a fixed letter across many messages is invariably the same.

Strengthening Julius Caesar: Vigenère ciphers

The weakness of the Julius Caesar system is that there are only 25 possible decrypts and so the cryptanalyst can try them all. Life can obviously be made more difficult for him if we increase the number of cases that must be tried before success can be assured. We can do this if, instead of shifting each letter by a fixed number of places in the alphabet, we shift the letters by a variable amount depending upon their position in the text. Of course there must be a rule for deciding the amount of the shift in each case otherwise even an authorised recipient won't be able to decrypt the message. A simple rule is to use several fixed shifts in sequence. For example, if instead of a fixed shift of 19 as was used in the message

COME AT ONCE

in the last chapter and which enciphered to

VHFX TM HGVX

we use two shifts, say 19 and 5, alternately, so that the first, third, fifth etc. letters are shifted 19 places and the second, fourth etc. are shifted 5 places then the cipher now becomes

VTFJ TY HSVJ.

If we replace the space character by Z in the message and use three shifts, say 19, 5 and 11, in sequence the plaintext becomes

COMEZATZONCE.

The cipher is now

VTXXELMEZGHP

and the key which provides the encipherment is 19–5–11.

Generalisation of simple substitution

In a simple substitution cipher the letters of the alphabet are replaced by a permutation of themselves. We have seen that such a cipher is easily solved, given as few as 200 letters, by counting their frequencies and using knowledge of the language. To use such a cipher simply requires a 26-long table of the permuted alphabet. If, say, A was replaced by R, N by C and T by H then AN would become RC in the cipher and AT would become RH. Thus R, the substitution for A, would appear both times.

Since a simple substitution cipher replaces single letters by the same letter each time, irrespective of whatever letter precedes or follows them, the frequency count attack will ultimately succeed. To counteract this if we had a system where the encipherment of a letter depended on some of the letters on either side of it then AN might encipher to RC whereas AT might encipher to, say, KW and the monograph frequency count method would fail. Such a system could be based upon a substitution table which listed all 676 (=26×26) digraphs and their cipher equivalents. Effectively we would have a two-part code-book; the first part would list all 676 plaintext digraphs in alphabetical order on the left of the pages with their cipher equivalents listed opposite them on the right. The second part would list the 676 cipher digraphs in alphabetical order on the left with their plaintext equivalents on the right.

The SZ42: a pre-electronic machine

The Enigma and Hagelin machines provided a much greater degree of security than any earlier systems of encipherment other than the unbreakable one-time pad. The cryptographic principles on which these two machines were based were quite simple. The Enigma provided a large number of substitution alphabets whilst the Hagelin generated a very long stream of pseudo-random key. In theory either machine could be modified in order to make it even more secure. The number of wheels could be increased and in the Hagelin the wheels could be made longer. In practice, modification of an existing cipher machine may present major difficulties of manufacture, distribution and compatibility with the original machine, which may be vital. A four-wheel Enigma was, in fact, introduced in 1942 and compatibility with the original three-wheel version achieved by arranging that with the new components in specified positions the old and new versions were the same cryptographically. Several new models of the Hagelin were produced by that company in the 1950s with different sized wheels and other features, but these were genuinely different machines and no attempt was made to provide compatibility with the original.

It might seem obvious that increasing the number of components in, or increasing the complexity of, a cipher machine will make it more secure, but this is not necessarily so. The more components there are, the more likely it becomes that operators will make errors. The greater the complexity, the greater the chance of a machine malfunction.

Historical background

The first general purpose computers were built in the 1940s. They were large, filling big rooms. They used hundreds of valves and consumed many kilowatts of electricity. They performed about a thousand instructions a second, which was considered amazing at that time, and they were popularly referred to as ‘giant brains’. A few people, including Alan Turing, discussed ‘whether machines could think’ and laid bets as to whether a machine would defeat the World Chess Champion in the next 25 years. The former question remains a matter for debate; the latter was settled about 45 years later when a World Chess Champion did lose a match to a computer.

These early machines had very small direct access memories, only a thousand or so ‘words’, based upon cathode ray tubes or mercury delay lines. They rarely functioned for more than a few minutes before breaking down. Their input and output were primitive: paper tape or punched cards and a typewriter. They also cost a great deal of money; £100 000 in 1948 which was equivalent to several millions 30 years later. Very few people knew how to write programs for them. There was virtually no software (as it later became known) and all programs had to be written in ‘absolute machine code’.

Even the instruction codes of these machines were very limited. The first machine at Manchester University in 1948, for example, had no division instruction [12.2], so division had to be programmed by repeated subtraction.

This first volume contains only material on the basic tools of modern cryptography, that is, one-way functions, pseudorandomness, and zero-knowledge proofs. These basic tools are used in the construction of the basic applications (to be covered in the second volume). The latter will cover encryption, signatures, and general cryptographic protocols. In this appendix we provide brief summaries of the treatments of these basic applications.

Encryption: Brief Summary

Both private-key and public-key encryption schemes consist of three efficient algorithms: key generation, encryption, and decryption. The difference between the two types of schemes is reflected in the definition of security: The security of a public-key encryption scheme should also hold when the adversary is given the encryption key, whereas that is not required for private-key encryption schemes. Thus, public-key encryption schemes allow each user to broadcast its encryption key, so that any other user can send it encrypted messages (without needing to first agree on a private encryption key with the receiver). Next we present definitions of security for private-key encryption schemes. The public-key analogies can be easily derived by considering adversaries that get the encryption key as additional input. (For private-key encryption schemes, we can assume, without loss of generality, that the encryption key is identical to the decryption key.)

Definitions

For simplicity, we consider only the encryption of a single message; however, this message can be longer than the key (which rules out information-theoretic secrecy [200]). We present two equivalent definitions of security.

In this chapter we define and study one-way functions. One-way functions capture our notion of “useful” computational difficulty and serve as a basis for most of the results presented in this book. Loosely speaking, a one-way function is a function that is easy to evaluate but hard to invert (in an average-case sense). (See the illustration in Figure 2.1.) In particular, we define strong and weak one-way functions and prove that the existence of weak one-way functions implies the existence of strong ones. The proof provides a good example of a reducibility argument, which is a strong type of “reduction” used to establish most of the results in the area. Furthermore, the proof provides a simple example of a case where a computational statement is much harder to prove than its “information-theoretic analogue.”

In addition, we define hard-core predicates and prove that every one-way function has a hard-core predicate. Hard-core predicates will play an important role in almost all subsequent chapters (the chapter on signature scheme being the exception).

Organization. In Section 2.1 we motivate the definition of one-way functions by arguing informally that it is implicit in various natural cryptographic primitives. The basic definitions are given in Section 2.2, and in Section 2.3 we show that weak one-way functions can be used to construct strong ones. A more efficient construction (for certain restricted cases) is postponed to Section 2.6.