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
Fichier Détails
| Cartes-fiches | 31 |
|---|---|
| Langue | English |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 21.03.2017 / 17.08.2017 |
| Lien de web |
https://card2brain.ch/box/20170321_cyg_chapter_3_cryptanalysis_of_classical_systems
|
| Intégrer |
<iframe src="https://card2brain.ch/box/20170321_cyg_chapter_3_cryptanalysis_of_classical_systems/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Créer ou copier des fichiers d'apprentissage
Avec un upgrade tu peux créer ou copier des fichiers d'apprentissage sans limite et utiliser de nombreuses fonctions supplémentaires.
Connecte-toi pour voir toutes les cartes.
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
-
