Classical methods in crypytography

Introduction

Looking back, the encryption methods concern the C (Confidentiality) in CIA.

The transmission and storage of confidential messages can be divided into two categories. This is shown in a graphic:

graph TD;
  uvn[Übertragung und Speicherung von vertraulicher Nachrichten]-->Steganographie;
  uvn[Übertragung und Speicherung von vertraulicher Nachrichten]-->Kryptographie;
  Kryptographie-->Substitution;
  Kryptographie-->Transposition;
  Substitution-->cw["Codierung (Wörter ersetzen)"];
  Substitution-->cb["Chiffrierung (Buchstaben ersetzen)"];

The steganography is the covered writing on a carrier. A third party is not aware that a message is hidden on the carrier.

Cryptography concerns secret writing, so that a third party cannot interpret the message. Cryptography can be further subdivided into substitution and transposition.

Important principles of cryptography

  • Kerckhoff’s principle: The security of the encryption process may only depend on the secrecy of the key, but not on the secrecy of the algorithm.
  • Shannon’s principles:
    • Confusion (shuffling): the ciphertext must resemble as closely as possible a random sequence. The statistical distribution in the plaintext should not be visible in the ciphertext.
    • Diffusion: A change of a part of the plaintext or of the key should influence the entire ciphertext.

Cryptography security

Cryptosystems are insecure if they can be cracked with less effort than with a brute force attack.

However, this definition can also be formulated more precisely. Ertel describes it as follows:

  • The amount of money required to crack the encryption should exceed the value of the encrypted data.
  • Furthermore, the time required to crack the encryption should be greater than the time the data must remain secret.
  • The volume of data encrypted with a given key shall be smaller than the amount of data required to crack it.

To be able to determine the security, a cryptanalysis is performed. Several assumptions are made.

  • Ciphertext-only analysis: Knows only cipher rate
  • Known-Plaintex analysis: Knows certain plaintext-chiffrat pairs
  • Choosen-Plaintext Analysis: Can choose plaintexts and analyze the resulting cipher
  • Brute-Force: The attacker can try all keys.
  • Attack on the secret keeper: The attacker obtains the key by force, blackmail or social engineering.

Information theory

Information theory is concerned with theoretical problems that arise in the storage, encryption and transmission of information. Claude Shannon laid the foundation for it already in the year 1948.

The information content can be described also with the degree of surprise. The smaller this is, the sooner the next character can be predicted. The formula for this is: $$I_i (x_i) = -log_2(p_i)$$ where Ii = information content of the character i and pi = probability of occurrence of character i.

Entropy

The definition of entropy in information theory also goes back to Shannon. In thermodynamics, as in information theory, it is a measure of disorder. In information theory, the entropy of a string gives the average information content of the characters and is measured accordingly in bits per character. If all characters in the string occur with the same frequently, the entropy is maximal. The difference between the effective and maximum entropy is the redundancy. In an alphabet (base64) with 64 characters, a character has an information content of 6 bits. The maximum entropy of a string is:

$$\sum_{i=0}^{n} (\frac{1}{64} * 6) = 64 * (\frac{1}{64} * 6) = 6 Bit/Zeichen$$

$$\sum_{i=0}^{n} (p_i * I_i)$$

or

$$\sum_{i=0}^{n} (p_i * -log_2(p_i))$$

Note that n = the number of characters in the alphabet, so there is a probability of occurrence for each character. The occurrence probability can of course also be 0.

Shannon calculated that the entropy for English texts, taking into account the single letter statistics, is 4.19 bits/character. If the consecutive letters and words are taken into account, the entropy is still 0.6 to 1.3 bits/character.

Transposition method

  • Garden fence cipher - the letters are written alternately in several lines. The resulting zigzag pattern is the plaintext and the individual lines are simply scrambled.
  • Scytale of Sparta - A strip of paper is wrapped around a rod with edges. Now the message is written down line by line around the staff.

Substitution method

  • Caesar Code - Each letter is replaced by the nth letter. If n = 1 the A becomes B, at n = 2 the A becomes C. So there are 26 keys to try.
  • Vigenère - As many alphabets are used as the key has characters. The plaintext letter determines the row and the key letter determines the column. The alphabet is written into the fields of this auxiliary table.
  • One-Time-Pad - Is a Vigenère encryption with a key length = plaintext length.
  • Enigma - Is a machine that was considered very secure for a long time.

The well-known encryption method AES (Advanced Encryption Standard) uses both transposition methods and substitution methods.

References

  • Wolfgang Ertel, “Angewandte Kryptographie”, 239 Seiten, ISBN 978-3-446-45468-2
  • Bruce Schneier, “Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd Edition”, 784 Seiten, ISBN 0-471-11709-9
  • Simon Sing, “The Code Book, a history of codes and code breaking from Ancient Egypt to the Internet", https://simonsingh.net/The_Black_Chamber/index.html
  • Dan Boneh and Victor Shoup, “A Graduate Course in Applied Cryptography”, https://toc.cryptobook.us/
Previous
Next