c2b_default

CYG Chapter 3 Cryptanalysis of Classical Systems

Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 3 Cryptanalysis of Classical Systems

Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 3 Cryptanalysis of Classical Systems

31
0.0 (0)
R. B.
Étudier
R. B.
This flashcard set delves into the cryptanalysis of classical systems, suitable for university-level learners. It covers key concepts like the Kasiski-Babbage and Friedman tests, focusing on tools such as frequency analysis, index of coincidence, and the Vigenère cipher. The set explores definitions, proofs, and practical applications, including determining cipher types and breaking codes. Ideal for cryptography students, it provides insights into attacks and security principles, helping them understand and apply cryptanalytic techniques effectively.
Cartes-fiches
31
Utilisateurs
1
Langue
Anglais
Catégorie
Informatique
Niveau
Université
Créé / Mis à jour
21.03.2017 / 17.08.2017
  • 1  / 31

Cartes-fiches

What is ‘Kerckhoffs’ principle’?

[cryptanalysis]

“The security of a cryptosystem shall not be based on the premise that the system itself is unknown to an opponent.”

What is the assumption?

[levels.cryptanalysis]

Oskar knows about the cryptosystem except of the key

What are the attacks?

[levels.cryptanalysis, 4]

1. CO

2. KP

3. CP

4. CC

What is the definition?

[CO.levels.cryptanalysis]

Only a string of ciphertext

What is the definition?

[KP.levels.cryptanalysis]

A string of ciphertext and the corresponding plaintext

What is the definition?

[CP.levels.cryptanalysis]

Access to the encryption function for any plaintext

What is the definition?

[CC.levels.cryptanalysis]

Access to the decryption function for any ciphertext

Which attacks are minimal requirements for a cryptosystem?

[levels.cryptanalysis, 2]

1. CO and 2. KP

Which attacks are the hardets requirements for a cryptosystem?

[levels.cryptanalysis, 2]

1. CP and 2. CC // All but Vernam fail

For which ciphers can this technique be used?

[frequceny.cryptanalysis]

Monoalphabetic ciphers

What are the steps?

[frequceny.cryptanalysis, 2]

1. Determine frequencies of characters, diagrams and trigrams of the cipher

2. Identify frequencies to characters, diagrams and trigrams of the NL

What would be a shortcut?

[frequceny.cryptanalysis]

Get half of the text with identifying six most frequent characters in English language // E,T,A,O,I,N make 51.75% of all frequencies

Who is the inventor?

[friedmanntest.cryptanalysis]

Colonel Friedmann 1891-1969

What is the outcome?

[friedmanntest.cryptanalysis]

Determine if a cryptogram was encrypted by a monoalphabetic cipher

What are the tools?

[friedmanntest.cryptanalysis, 4]

1. Alphabet X:={1,…,m}

2. Random variables C=(C1,…,Cn) with P(Ci=l)=ql and iid

3. Number of components equal to l Nl = |{i| Ci=l}|

4. Strong law of large numbers ql = limn→inf Nl/n

What are the special cases?

[indexcoincidence.friedmanntest.cryptanalysis]

1. IC = 1 ↔ C1 = … = Cn

2. IC = 0 ↔ All Ci are different

What is the definition?

[KM.indexcoincidence.friedmanntest.cryptanalysis]

IC ~ Suml=1m ql² =: KC with strong law of large numbers

What is the definition?

[Yij.indexcoincidence.friedmanntest.cryptanalysis]

Yij = {1 if Ci=Cj; 0 otherwise}

What is the definition?

[indexcoincidence.friedmanntest.cryptanalysis, 3]

1. Ic = I(C1,…,Cn) = |{(i,j)| Ci=Cj, i<j}| / (n over 2)

2. Ic = 1/n*(n-1) Suml=1m Nl*(Nl-1)

3. IC = Sumi<j Yij / (n over 2)

What is the definition?

[lemma33.friedmanntest.cryptanalysis]

E(IC) = K

What is the proof?

[lemma33.friedmanntest.cryptanalysis, 5]

1. E(Yij) = 1*P(Yij=1) + 0*P(Yij=0)

2. = P(Ci=Cj)

3. = Suml=1m P(Ci=l, Cj=l)

4. = Suml=1m ql²

5. = K

How does it work?

[application.friedmanntest.cryptanalysis, 3]

1. Compute IC

2. If Ic~KL of language L then we have monoalphabetic cipher over L

3. If IC~0.0385=KU then we have a polyalphabetic cipher

What is the idea?

[kasiskibabbage.cryptanalysis, 3]

1. Vigenère is not monoalphabetic but can still be broken with low effort

2. Estimate keylength k

3. Use that length is probably a divisor of the distance of equal sequences

List them!

[tools.kasiskibabbage.cryptanalysis, 6]

 

1. Alphabet X:={0,…,m-1}

2. Plaintext M=(M1,…,Mn) with P(Mi=l)=pl, iid and k|n

3. Keyword K=(K0,…,Kk-1) with P(Ki=l)=1/m and iid on X

4. Ciphertext C=(C1,…,Cn) with Ci=(Mi+K(i-1)mod k) mod m

5. Yij = {1 if Ci=Cj; 0 otherwise}

6. k = n(KM – 1/m) / (n-1)*E(IC)+KM-(n/m) // If E(IC)=KM then k=1

What are the cases?

[Yij.tools.kasiskibabbage.cryptanalysis, 2]

1. If i~j ↔ i=j (mod k) then E(Yij) = KM

2. If i!~j then E(Yij) = 1/m

What is the definition?

[lemma35.kasiskibabbage.cryptanalysis]

E(IC) = 1/k(n-1) * ((n-k)*KM + n(k-1)*1/m)

What is the proof?

[lemma35.kasiskibabbage.cryptanalysis, 4]

1. E(IC) = Sumi<j E(Yij) / (n over 2)

2. = [Sumi<j,i~j E(Yij) + Sumi<j,i!~j E(Yij)] / (n over 2)

3. = [Sumi<j,i~j KM + Sumi<j,i!~j 1/m] / (n over 2)

4. = [n/2 * (n/k -1) * KM + n/2 * (n- n/k) * 1/m] * 2/n(n-1)

How does it work?

[application.kasiskibabbage.cryptanalysis, 2]

1. Estimate E(IC) by 1/n(n-1) * Suml=0m-1 nl(nl-1)

2. Further perform frequency analysis on the obtained rows

What has to be avoided?

[vernam.application.kasiskibabbage.cryptanalysis, 2]

1. Avoid by using key chosen randomly

2. Avoid by never using same key twice

What could happen?

[randomkey.vernam.application.kasiskibabbage.cryptanalysis]

Else simply use frequency analysis for the combination of the most frequent characters // P(Mi,Ki from {E,T,A,O,I,N,S}~57%²~33%

What could happen?

[twicekey.vernam.application.kasiskibabbage.cryptanalysis]

Else compute ci-di mod m = mi-ni mod m

Étudier