Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 58

Cryptography is an old subject dating back at least as far as 1500 BCE. A technique developed by Porta associated also with Vigenère in the Middle Ages is close to the cutting edge of part of modern cryptography. Additionally, cryptography is closely connected to information theory and error‐correction, with many fundamental ideas going back to Claude Shannon. Further details about Shannon and the history of cryptography are provided in Chapter 1.

Cryptography is the art of keeping messages secret. Imagine that A, B are two entities who wish to communicate in secret. Assume A wants to send a secret message to B.

The procedure is as follows (Figure 3.1). First, A scrambles the message using a cryptographic key. The process of scrambling the message is called encryption: alternatively, A enciphers the message.

Figure 3.1 General encryption.

The encryption or enciphering scrambles the message , that is, the plain text, into unintelligible output called the cipher text. Next, the sender A transmits in the open (publicly) the cipher text to the receiver B. When B receives the cipher text, B descrambles or deciphers the cipher text using a key that may or may not be the same as the original key used by A. B can now recover the original message that was transmitted by A.

In summary, the sender A encrypts or enciphers the message into unintelligible cipher text using an encrypting or enciphering key. The enciphering is done by a specific procedure involving a sequence of steps or rules called the enciphering algorithm (or encryption algorithm).

Using the decryption or deciphering key, and using the deciphering algorithm (decryption algorithm), the receiver B then decrypts or deciphers and thus recovers the original message that was transmitted by the transmitter A. Moreover, at least in theory, an intruder Eve cannot access the message since Eve will not have the decryption key that is needed for decrypting (deciphering, inverting) to recover .

Evidently, everything depends on B being the sole possessor of the decryption key, apart possibly from A. (If the decryption and encryption keys are the same – as they are in symmetric encryption, then A also has the decryption key).

Generally speaking, a key is a mathematical object such as a number (or several numbers) or a string of zeros and ones, i.e. a binary string such as the binary string (1 1 0 1) of length 4.

The enciphering and deciphering operations are usually mathematical procedures. For example, let us suppose that the enciphering key is the number 7 and that the enciphering operation is “add 7.” Suppose the secret message that A wants to transmit to B is the number 6. (For example A might be directing her stockbroker B to buy six thousand shares of a given security on the stock market).

Then, A calculates the cipher text 13 ( = 6 plus 7) and transmits this to B. Now, B knows that the enciphering transformation is “add 7.” To undo, or invert this, B subtracts 7 from 13 (as this is the deciphering operation) and ends up recovering the original message transmitted by A, namely 6.

It should be mentioned that the cryptographic keys above need not be mathematical objects: in fact, historically, they often were not. A famous example, mentioned in Chapter 1, occurred in World War II when, in effect, the key was an entire language! This was the Navajo language used by the Navajo tribe in Arizona and adapted for encryption purposes by the US armed forces around 1942. Enciphering consisted of translating messages from English into the Navajo language, while deciphering simply meant translating Navajo back to English at the other end. At that time, this symmetric encryption was extremely effective.

Using encryption for storing messages and files is another important function of encryption in today's society. As an example, we mention the encryption of a file – or even an entire hard drive (or solid state drive) – in a computer so that, if it is set aside (or stolen) an individual other than the owner cannot access the contents. (Apple and Windows both have encryption applications that use XTS‐AES‐128 encryption with a 256‐bit key. Apple's MacOS uses it in FileVault 2, [App18], and Windows 10 version 1511 uses it in their Bitlocker feature, [Win19].) We can fit this into our previous general situation with the owner of the computer playing the role of both A and B.

We have been silent on how A and B get their enciphering and deciphering keys. This is discussed in a later chapter, but will depend on the kind of encryption being used. The two fundamentally different possibilities for cryptography are as follows:

1 Symmetric Cryptography

2 Asymmetric Cryptography, i.e. Public Key Cryptography.

Figure 3.2 Symmetric encryption.

Recall that as before A, B are the communicating entities and A wants to send a secret message to B (Figure 3.2). In symmetric encryption, there are three features.

1 The enciphering key used by the transmitter A is equal to the deciphering key used by the receiver B and this key is known only to A and B.

2 The enciphering algorithm, converting the plain text to cipher text, is such that the cipher text can be calculated immediately given and .

3 The deciphering algorithm, converting back to , can be calculated immediately given and .

The security depends on the fact that the secret key is known only to A and B.

Public key cryptography works differently (Figure 3.3). The procedure is as follows:

1 The enciphering key used by A (or anybody else) to send a message to B is publicly known, and is called the public key of B. However, the deciphering key used by B to decrypt the cipher text is known only to B and is the private key of B. So the two keys are quite different.

2 The enciphering procedure, converting the plain text to cipher text , can be immediately calculated given M and .

3 The deciphering procedure, converting back to M, can be calculated immediately by B using . However, it is not possible for somebody else who is not in possession of to convert back to M in a reasonable amount of time.The security of public key cryptography rests on the assumption that it is not feasible to convert back to M without knowledge of the private key .Thus, in public key cryptography each user B in a network has a public key and a private key , which are supplied by a public key authority (PKA).

Symmetric cryptography (encryption) is also called secret key cryptography (encryption). The security depends, as stated above, on the assumption that only the communicating parties A and B know the (common) key. Note that A, B could also denote groups of entities on a network and that B can also send a secret message to A using their common secret key.

Figure 3.3 Asymmetric or public encryption.

Historically, cryptography meant symmetric cryptography. Nowadays, important symmetric algorithms in use are AES and the One‐Time Pad which is sometimes derived from a shift register (see Chapter 16).