A3/Classical cryptography

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.