A3/Classical cryptography

Aus QuaNTH
Wechseln zu: Navigation, Suche

A3

Communication
Introduction

Lektionen


The task of secret communication is probably as old as communication itself. We will mainly be interested in communication over large distances that should be secure against eavesdropping.

The origin of the word "cryptography" comes from Greek and translates to "secret writing". There is also the word "cryptology" for “study of secrets” in use, but we will only use cryptography, as it is more common in quantum information.

History of cryptography

The history of cryptography can be traced back to ancient times. One prominent example is the Caesar-encryption, which is named after the Roman statesman Gaius Julius Caesar. According to his biographer Sueton, when communicating with his generals he would not simply write a text, but would shift every letter by tree in the alphabet. This means, that instead of an A he would write D, instead of a B a E and so on. This encryption scheme is an example of a transposition cipher, in which every letter is transposed within the alphabet.

With the advent of telegraphy also cryptography became more important. In the 19th century the cryptologist A. Kerckhoffs defined a number of criteria that should be fulfilled by any cryptographic system. One of these (which is today simply called Kerckhoffs’ principle) states that the secrecy of the encryption of the cryptographic system may not depend on keeping details of the encryption technique secret.

This implies, that one must separate the encryption device (or algorithm) and the key used by the communicating parties. We have depicted the scheme in Fig. 3. Alice and Bob want to communicate in private. To do this, Alice holds a key and possesses an encryption device. From the message combined with the key she will then generate the cryptogram, which is transferred to Bob over the insecure channel. Bob also holds a key and a decrypting device which lets him reconstruct Alice’s original message. If Alice and Bob use the same key, we call it a symmetric encryption, if the keys are different we call it an asymmetric encryption.

As the classical channel is considered insecure, an eavesdropper (called Eve) is assumed to have a copy of the cryptogram. This means, that the key Alice and Bob holds represents their advantage over Eve. The key itself does not contain information. Alice and Bob should take care to destroy the keys after communication so that Eve may not get hold of them at a later time.

Examples

We start again with the Caesar-encryption (or transposition) scheme. Here, each letter will be replaced by the letter that comes a certain number of steps later in the alphabet, where the alphabet is considered to be cyclical, so after Z comes A again. Each number of steps defines a different encryption, so one can use the image of the letter A as a key for this encryption. The original Caesar-encryption would have the Key “D” (as the Letter “A” is transposed to “D”), but in total there are 25 different keys possible.

One device to perform such an encryption is the Caesar-wheel (depicted in Fig. 4). It consists of two rings, each representing the complete alphabet that can be aligned in such a way, that the letter on the outer ring representing the message is always opposite the letter of the cryptogram.

A simple extension of this cipher would be, not to use the same key for every letter of the message, but to alternate according to a given rule. For instance, one could use one Cesar-encryption of all letters on odd places (so the first, third, fifth,... letter) and another one for letters in even places (the second, fourth etc). The number of different keys in this scheme would then be 25^2=625. If one would use three key symbols, the number of different keys would be more then fifteen thousand.

General scheme

In order to perform secret communication, Alice and Bob need to agree on a cryptographic protocol and on the key to be used. In a symmetric encryption scheme, these keys have to be transmitted in private, which means that the two need to meet in person and exchange the keys, which furthermore need to be kept protected until they are used for communication. We have seen in our first examples that the security of the scheme depends on the length of the key. The longer the key the better is the encryption.

One-time pad

In the optimal case, the key used by Alice and Bob has the same length as the message to be sent. If one uses the scheme described above, this means that every letter of the message is transposed by a different amount. The key in this scheme may only be used one, in order not to compromise the security, hence the name of the scheme. If the key was drawn at random, this also implies that this encryption is unbreakable without the correct key.

To see this, consider how one would try and break a transposition code. One course of action would be, to simply all possible keys until one of them decodes the cryptogram to a meaningful message. In the simple Caesar-cipher it is highly unlikely that two of the possible 25 keys would decode a cryptogram to a readable message. But if one uses a one-time pad, all possible messages are equal likely. So if a for example a cryptogram can be deciphered with one key to “attack at dawn” there is a second key that will decode it to “attack at dusk” and as both are equally likely, the eavesdropper has no way of knowing which the original message was.

To summarize: If Alice and Bob ménage do distribute enough key, they are able to perform a one-time pad encryption which is completely unbreakable for any eavesdropper.

Key distribution

But how do Alice and Bob distribute the key? One possibility that was already mentioned would be that they meet at a safe location and exchange the keys there. In classical physics this is also the only possibility for them, as any public communication could be intercepted by an eavesdropper there can be no establishment of secret key over public communication. We will see later, that this is made possible by using quantum physics, so the main gain of using quantum signals is to enable remote key generation (also called quantum key distribution, QKD).