This is a study note of “Understanding Cryptography” ch01. It covers:

  • The general rules of cryptography
  • Key lengths for short-, medium- and long-term security
  • The difference between different types of attacks against ciphers
  • A few historical ciphers
  • Modular arithmetic
  • Why one should only use well-established encryption algorithms

1 Introudction

Cryptology splits into two main branches: Cryptography for building cryptosystem and Cryptanalysis for braking cryptosystem. Cryptography has three branches: symmetric algorithms, asymmetric algorihms and cryptographic protocols. The cryptographic protocols are applications built upon the primitives provided by symmetric and asymmetric algorithms.

2 Symmetric Cryptography

Symmetric cryptographic schemes are also referred to as symmetric-key, secret-key, and single-key schemes or algorithms.

The only way to find out whether an encryption method is strong, i.e., cannot be broken by a determined attacker, is to make it public and have it analyzed by other cryptographers.

Good ciphers should hide the statistical properties of the encrypted plaintext. The ciphertext symbols should appear to be random. Also, a large key space alone is not sufficient for a strong encryption function.

3 Cryptanalysis

Cryptanalysis has three branches: classic cryptanalysis, implementation attacks and social enginnering. Classic cryptanalysis has mathematical analysis and brute-force attacks. Implementation attacks include buffer overflow attacks and side-channel analysis that often targets hardware.

Kerckhoffs’ Principle: A cryptosystem should be secure even if the attacker (Oscar) knows all details about the system, with the exception of the secret key. In particular, the system should be secure when the attacker knows the encryption and decryption algorithms.

Security by Obscurity is a bad idea. An example is the Content Scrambling System (CSS) for DVD content protection, which was broken easily once it was reverseengineered.

4 Modular Arithmetic

Caesar cipher is a modular addition with a fixed value. Affine cipher uses multiplication and modular additions.

4.1 Modulo Operation

Modulo operation definition: Let a, r,mZ (where Z is a set of all integers) and m > 0. We write a ≡ r mod m if m divides a - r. m is called the modulus and r is called the remainder.

There are infinitely many valid remainders for any m and r. For example: 12 ≡ 3 mod 9,12 ≡ 21 mod 9, 12 ≡ −6 mod 9. Because 9 divides (12 - 3), 12 - 21 and 12 - (-6). They are call an equivalence class. There are a total nine eqivalence classes for the modulus 9.

By agreement, we usually choose r such that 0 <= r < m.

4.2 Ring

An integer ring Zm consists of:

  • The set Zm = {0,1,2, . . . ,m−1}
  • Two operations + and · for all a,b ∈ Zm such that:
    1. a+b ≡ c mod m , (c ∈ Zm)
    2. a·b ≡ d mod m , (d ∈ Zm)

A ring is closed and has the following properties:

  • Addition and multiplication are associative
  • The distributive law holds: a·(b + c) = (a·b) + (a·c).
  • There is the neutral element 0 with respect to addition, i.e., for every element a ∈ Zm it holds that a+0 ≡ a mod m.
  • For any element a in the ring, there is always the negative element −a such that a+(−a) ≡ 0 mod m, i.e., the additive inverse always exists.
  • There is the neutral element 1 with respect to multiplication, i.e., for every element a ∈ Zm it holds that a·1 ≡ a mod m.
  • The multiplicative inverse exists only for some, but not for all, elements. Let a ∈ Z, the inverse a^(−1) is defined such that a · a^(−1) ≡1 mod m. If an inverse exists for a, we can divide by this element since b/a ≡ b·a^(−1) mod m.
  • It takes some effort to find the inverse but it is easy to tell whether an inverse exists or not. An element a ∈ Z has a multiplicative inverse if and only if gcd(a,m) = 1,

In summary, roughly speaking, we can say that the ring Zm is the set of integers {0,1,2, . . . ,m−1} in which we can add, subtract, multiply, and sometimes divide.

4.3 Two Ciphers

Shift Cipher has a key space of 26:

  • Let x,y,k ∈ Z26
  • Encryption: ek(x) ≡ x+k mod 26
  • Decryption: dk(y) ≡ y−k mod 26

Affine Cipher has a key space of 12 * 26 = 312:

  • Let x,y,a,b ∈ Z26
  • Encryption: ek(x)= y ≡ a·x + b mod 26
  • Decryption: dk(y) ≡ a^(-1)·(y−b) mod 26

The key: k = (a,b) has the restriction: gcd(a,26) = 1. Thus a must be in the set {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} to make gcd(a, 26) = 1.