Substitution ciphers

Question 1

What is a substitution cipher?

Answer 1

1. A substitution cipher is one in which the letters of plaintext are replaced by other letters or by numbers or symbols.
2. If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns.

Question 2

What is the Caesar cipher?

Answer 2

1. each plaintext character is replaced by character 3 to the right modulo 26.
2. For example, A in plaintext replaced with D in ciphertext.
3. Give each letter in the plaintext a number from 0 to 25 so, C = E(3, P) = (P + 3) mod 26
4. In general, for K ∈ {1, . . . , 25}:
   C = E(K, P) = (P + K) mod 26
   P = D(K, C) = (C − K) mod 26
5. modulo 26 is used because from 0 to 25 there are 26 numbers - wrap around after 26.

Question 3

What is ROT13?

Answer 3

1. shift each letter in the plaintext by 13 places to obtain the ciphertext.

Question 4

What is alpha-numeric?

Answer 4

1. substitute numbers for letters - if the plaintext is of letters - label alphabets from 0 -> 25 and substitute each alphabet with a number to obtain ciphertext.

Question 5

Why is brute-force cryptanalysis possible for current Caesar cipher? why is it still easy to decrypt?

Answer 5

Three reasons making the attack possible:
1. The encryption and decryption algorithms are known.

2. There are only 25 keys to try.
3. The language of the plaintext is known and is easily recognisable.

BUT if the language of plaintext is unknown, then output may not be recognizable AND there could also be two possible sensible plaintexts in two different languages.

Question 6

What makes a brute-force attack impractical?

Answer 6

1. use an algorithm that uses a large number of keys such as DES - 168 bit key (2^168) possible keys.

Question 7

What is the mono-alphabetic substitution cipher?

Answer 7

1. Generalises the Caesar cipher by allowing arbitrary substitutions via permutation.

Question 8

What is permutation?

Answer 8

1. Permutation of a finite set S of elements: an ordered sequence of all elements of S, each element appearing exactly once.
   For example: 6 permutations of S = {a, b, c}: abc, acb, bac, bca, cab, cba.
2. In general: n! permutations of a set of n elements
3. For the caesar cipher, there are 26 elements so, 26! permutations/possible keys.

Question 9

What is the mathematic definition of monoalphabetic suubstitution ciphers?

Answer 9

1. K be the set of all permutations on the alphabet A.
2. Define for each e ∈ K an encryption transformation Ee on strings m = m1 m2 · · ·mn ∈ M as
   Ee(m) = e(m1) e(m2)· · · e(mn) = c1 c2 · · · cn = c (encrypting each letter m to obtain c)
3. To decrypt c, compute the inverse permutation
   d = e^−1 and compute Dd(c) = d(c1) d(c2)· · · d(cn) = m
4. Ee is a mono-alphabetic substitution cipher.

Question 10

What is the security of mono-alphabetic ciphers?

Answer 10

1. Easy to crack using frequency-analysis as the structure is preserved.
2. If the plaintext has a lot of “e” -> the ciphertext would have a lot of the same alphabet that corresponds to e in the plaintext.