polimd/Cryptography/exe_01.md

If the frequency graph has the same shape of the english language, it is a permutation cipher, if the shape is the same but labels are different, it is a substitution cipher, or a combination of the two.

The permutation cipher does not affects the frequency graph because the analisys is done on the text as a whole which ignores the scrambling.

Growing the keylenght in a vigenere cipher, i expect to see the frequency curve flattening, until it become completely flat when the key is long as the text (one time pad)

To have a bigram that remains from the plaintext to the cyphertext, the beginning of the n-grams should be aligned with the key.

If in a vigenere cipher we have the frequencies 6, 24, 30 the key lenght candidates are 3, 6, 2,1. We start loogin from the longest key.

If the vigenere is using a key lenght of 3 and i pick 6, i will still find a key with is a double repetition of 3 lenght key.

SMS example

If i'm encrypting sms messages (160bytes) with a 256B key:

• if I use every time a different key, the cipher is not breakable because is akin to a onetimepad.
• if I use always the same key I will be using actually 160bytes of the key, so it's a matter of collecting enough ciphertexts and concatenating them to run a classic vigenere breaking

Unicity distance: Even if we are using bruteforce, if we have less that the unicity distance in ciphertext, i will be unable to tell apart the actual plaintext from a group of texts that pass the test.

Defined as: $n_0 = {log_2{|k|}/{R_L * log2{|M|}}$

Redundancy $R_L = 1 - {H_L}/{log_2{|M|}}$

Entropy of english $H(M) \le 1.5b$

• Best case, the message has an extremely redundant message,

High redundancy what dinstinguishes english from random data.

With more redundancy is is more difficult to distinguish a meaningful message from one that it isn't.

Entropy of a random (lowercase) letter $H(rnd letter) = -\Sum{s}p_s * log(p_s)$ $- (26*1/26 * log(1/26)) = log_2(26)$ $$log_2(16) < log_2(26) < log_2(32)$$

So using lowercase letters as key I have an entropy of 160b, between 640 and 800.

$$n_0 = \frac{log_2(|K|)}{R_L * log|M|}$$ $$n_0 = \frac{800)}{0.75 * 4.7}$$ $$n_0 = \frac{800}{3.5}$$ $$n_0 = 200$$

I need at least 2KB of text to at least get a unique plaintext when doing bruteforce.

Honey encryption Takes a meaningful plaintext and a source of random number, and outputs a uniform distribution of characters, which even when bruteforcing decrypts to a bunch of random numbers. This encryption scheme is used in credit cards to avoid the risk of bruteforce attacks.

Playfair cipher

• Start with a 5x5 grid
• Fill with keyword, avoiding letters already present
• Fill with english alphabet, still avoiding repetitions. W | I | N | T | E ---|---|---|---|--- R | M | U | A | B C | D | F | G | H K | L | O | P | Q S | V | X | Y | Z

I take the plaintext crypto Take two letter and replace them with their neighbors

Missing encryption procedure

The keyspace is $25!$ because it is a still a permutation of the english letters even if it is folded.

$$ln(n!) = nln(n) - n + O(ln(n))$$ Shorthand formula $$n! = e^(nlog(n)) - e^n + e^log(n)$$

$$25! -> 25*4 ~= s^120$$

Bruteforce reference Powers of two:

• 0-40 laptop
• 40-50 GPU
• 50-60 bunch of GPUs
• 60-70 calculus center
• more than 80 unlikely
• 100 the energy obtained burning all the oil is not sufficient.

The table rule is encrypting a digram into a given digram, so I can use a large lookup table to compare the digrams.

Nihilist cipher A variation of the playfair cipher used by the U.S. war prisoners, Has two keys:

• k1: build the polybius square
• k2: run it through the table
  • for example "chair" look it up in the square and report the coordinates 31-33-24-12-21

Procedure

• Run the plaintext through the table PTX= "Test" 14-15-51-14
• Add the key (non modular) to the plaintext
• 31-35-24-12 45-50-75-26

Is the thing breakable? what is the keyspace? can i run a bruteforce? The two keys are independent so I will need to bruteforce both of them. Keyspace The second key will be the entropy of a symbol times the number of symbols The keyspace of the first key is 25! as before

The first encoding can be seen as a funny substitution cipher Also there's a bias in the number, it is more frequent to find higher numbers, I can compare the distribution of cyphertext histogram to the plain english one.

In the playfair cipher, a letter can be never envrypted as itself.

Enigma The enigma machine had three cogs that applied three substitutions and again in reverse order thanks to a reflector. A peculirarity was that the signal of a letter could never be sent back to the same letter because it would cause a short circuit.

The only position that mattered was the first one because the remaining positions were obtained by rotating the rotors. The commercial version of enigma has three rotors, or 26³ keyspace, While an enhanced version has three rotors to be picked out of 5 thus getting a 26³*5*4*3 The plugboard added a 26*24*23...*15 This is more than was done by the rotors alone, and a version with 10 cables was introduced by just adding more cables.

A contradiction is when a single ciphertext letter gets mapped to wto different letters, with can't be done in a single wiring machine. The military version had a plugboard with 26 sockets and 6 cables.

6 face die 3 random variables

• x = {1...6}
• y = {odd, even}
• z = {result<=3, result>3}

Compute the entropy of these guys and at least the joint entropy of (x,y), (z,y) H(x) = -6*1/6*log2(1/6i)= log2(6) Rolling a dice gives 2.6b of entropy H(y) and H(z) gives 1bit of entropy, the dice become equivalent to a coin

H(xy) We make the table of the thwo wariable, so the joint entropy of XY is as Y, because there is a correlation

H(zy) gives a different correlation