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
Kartei Details
| Karten | 31 |
|---|---|
| Sprache | English |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 21.03.2017 / 17.08.2017 |
| Weblink |
https://card2brain.ch/box/20170321_cyg_chapter_3_cryptanalysis_of_classical_systems
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20170321_cyg_chapter_3_cryptanalysis_of_classical_systems/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Lernkarteien erstellen oder kopieren
Mit einem Upgrade kannst du unlimitiert Lernkarteien erstellen oder kopieren und viele Zusatzfunktionen mehr nutzen.
Melde dich an, um alle Karten zu sehen.
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
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
-
- 1 / 31
-
