DES

DES is a symmetric key algorithm created in the 1970s, when we just started to use computer to run encryption and decryption algorithms.

DES is a block cipher of size 64 bits. With 56 bits key, 64 bits plaintext, DES starts with a initial permutation in a designed, fixed way that reorganize the plaintext, ends with a inverse permutation which is literally the inverse of the initial permutation that recover the order of the text.

Except for the initial permutation and final inverse permutation, DES has identical structure with the Feistel cipher, which I don’t want to write the process in detail:) So let’s focus on the function F and subkey generation parts.

Subkey generation: The 56 bits key will firstly run through a permutation (note that there are a lot of permutations in DES, they are all fixed, published and designed), this will reorder the bits of the key, and break it in two halves of 28 bits, let’s call it C₀ and D₀, for each round i, C_i-1 and D_i-1 will shift one or two bits left (e.g. one bit shift: 10000 to 00001) given i to become C_i and D_i, again there is a given table that tells you one or two. C_i and D_i, 56 bits togerher, then get another permutation each round (same permutation table for each round), which output 48 bits subkey of each round.

Function F: The 32 bits text (right half of the 64 bits, refer to Feistel cipher) firstly go through an expansion table, in order to XOR with the 48 bits subkey. After applying XOR to the subkey, it goes through a S-box that shorten the text to 32 bits again. The S-box produce 4 bits from every 6 bits, with the first and last bit decide the row of the designed table, and the rest 4 bits decide the column, which gives a 4-bit number in the table.
Finally it goes through a permutation and gives the output. In this function, the expansion, S-box and final permutation use the same table every round, the only difference each round is the subkey.

Decryption for DES is exactly same as encryption except the subkey is used in inverse order.

AES

AES is more recent and still widely used today. It’s a block cipher of size 128 bits. There are three options for the key, 128 bits, 192 bits, 256 bits, corresponding to 10 rounds, 12 rounds and 14 rounds of encryption and decryption. AES works in the unit of bytes instead of bits, so a 128-bit key encryption will have 16 bytes of plaintext and 16 bytes of key.

For a 10 rounds encryption, we firstly take the plaintext and XOR with the original key (not counted as a round), then we start with the first round.

Each round consist of 4 steps, first of all we write the original text as a 4×4 matrix, each element is a byte, the matrix is filled from top to bottom, left to right.
After preparation of the matrix, the first step is to go through a permutation given by a table, similar to those in DES, with the first 4 bits determine the row and last 4 bits determine the column.
Second step is a row transformation, the first row does not move, the second row move 1 bit to the left (the left most bit becomes the right most bit), third row move by 2 bits and last row move by 3 bits.
Third step is a column transformation, the matrix is multiplied by a fixed matrix, but in this matrix multiplication applies different addition and multiplication as we normally do, it is based on a Galois field GF(2⁸), which means no number should be bigger than 2⁸. in a nutshell, addition is simply XOR, multiplication is as follow:
00000010 x a7 a6 a5 a4 a3 a2 a1 a0 = a6 a5 a4 a3 a2 a1 a0 0 if a7 is 0,
else = a6 a5 a4 a3 a2 a1 a0 0 XOR 00011011.
From this we can compute multiplication of any other number, for example, times 00000100 is equal to times 00000010 twice.
Finally comes to the last step, which is simply an XOR with the subkey.

Subkey generation: The initial 128-bit key is devided into 4 parts, each contains 32 bits, name as W0 to W3. Our aim is to generate all the way to W 43 to encrypt 10 rounds.
The rule is: For Wi, if i mod 4 is not 0, then W[i]=W[i-4]⨁W[i-1],
else, W[i]=W[i-4]⨁T(W[i-1]), where T is a three step function:
firstly, leftshift by one, i.e. abcd -> bcda. Secondly, permutation, use the same table as the one in first step encryption to permute the text. At last, XOR with a number given by a table that has different value for different round.

FINALLY DONE.

Decryption of AES apply the inverse of each single step in a reverse order, for the table there is an inverse table, for the matrix there is an inverse matrix, for the row transformation we shift right instead of left.

Substitution ciphers and transposition ciphers both belong to symmetric cryptographic system, where encryption key and decryption key are the same, or one can be deducted from the other.

Substitution ciphers

1. Caeser cipher

Ceaser cipher is simply substitute all letters to k letters afterwards, where k is the encryption and decryption key, if the plaintext is English then it will be a number between 0 to 25. Easy to use, very easy to break.

Example: ceaser -> fhdvhu, k = 3.

2. Mono-alphabetic subsitution ciphers

Give every letter in the alphabet a subsitution letter, every letter should be use once and only once. So there are 26! possibilities (considering English letters alphabet).

Example:

Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Compared to Ceaser cipher, Mono-alphabetic subsitution is harder to break in terms of brute-force attack, but still very week because frequency of letters remains, for example the highest frequency letter is more likely to be letter E than any other letters because it is the most frequently used letter in English.

3. Homophonic subsitution cipher

Similar to Mono-alphabetic subsitution ciphers, but provides more than one possible ciphertexts to each plaintext letter.

Example: A = {x, y}, H(x) = {00, 10}, and H(y) = {01, 11}. Then the plaintext xy can be encrypted as 0001 or 1001 or 0011 or 1011.

Although frequency of single letter can be hide, diagram frequencies (pattern of multiple letter) still exist, especially in longer text. Because the provided subsitutes are finite will be reused, at some point some patterns shown before will show again in the ciphertext.

4. Playfair cipher

Make a 5×5 matrix, each box contains one letter (i and j in one box), by selecting a keyword, put the letters of the keyword in the boxes starting at the top left, and fill in the rest boxes with the rest letters.

Example: keyword MONARCHY, matrix as follows

M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z

After constructing the matrix, break the plaintext into two letters each block, if number of letters are odd, add a selected letter at the end, for example X. Then the rule is:

If both letters fall in the same row, replace each with letter to right, wrapping back to start from end (e.g., “AR” is encrypted as “RM”).
If both letters fall in the same column, replace each with the letter below it, wrapping to top from bottom (e.g., “MU” is encrypted as “CM”).
Otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the pair (e.g., “HS” becomes “BP” and “EA” becomes “IM”, or “JM”, as the encipherer wishes).

Playfair cipher is better than homophonic subsitution, but still the structure of the plaintext is left intact, and not very hard for computer to brute-froce.

5. Polyalphabetic substitution ciphers (Vigenère cipher)

Select a keyword, repeat the keyword until it is as long as the message, there we formed a key where each letter stands for a ceaser cipher, for example, d=3.

Example:

keyword: deceptive
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

this is again better than playfair, but cryptoanalysis methods are still available, for example Kasiski method and Index of coincidence.

6. Vernam cipher and one-time pad

Needs a key as long as the plaintext in terms of bits, do XOR operation, and due to the feature of the XOR operation, when apply XOR to the ciphertext with the key again, plaintext is recovered.

One-time pad is to use the Vernam cipher method, use the key once, then discard and find another one to use.

One-time pad is absolutely safe because it is encrypted in the unit of bits, so no information contains in the ciphertext, and the key is only use once. But it is not to expensive to apply in real life.

Transposition ciphers

1. Rail fence cipher

The key of rail fence cipher is a number, the number of depth of the fence. Write the plaintext in the shape of V with the given depth (the key).

Example:

plaintext: WE ARE DISCOVERED FLEE AT ONCE
key: 3
W E C R L T E
E R D S O E E F E A O C
A I V D E N
cipher text:W E C R L T E E R D S O E E F E A O C A I V D E N

Rail fence use the same idea with the Scytale, very week to break.

2. Rotating (turning) grille

Much easier to illustrate with example.

Example:

Plaintext: The Lord is my shepherd. I shall not be in want.
Cut out 9 grid from a 6×6 square, select one from the four of each number to cut, each number should be cut once and only coce.

once prepared, fill the plantext letters in the empty grid one by one, then rotate the paper conterclockwise 90 degree, and continue filling in, until the grille is finished.
ciphertext: mtdhyeisthlbehoeapirhldnelwrainnostt.

Rotating grille is also easy to break since again the frequency of letters remains.

3. Columnar transposition cipher

write the message in a retangle row by row, give a number of sequence to each column and reorganize the text to get the ciphertext, the sequence is the key.

Example:

Key: 4 3 1 2 5 6 7
Plaintext:
a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ