Treti prednaska z Kodovani a sifrovani
Zaklady kryptoanalyzy
Obsah
Zaklady kryptoanalyzy
Zakladni ulohou kryptoanalyzy je odhaleni inverzniho zobrazeni ke kryptograficke
transofrmaci, tedy k zobrazeni Tk n-tic prvku okruhu Zm do sebe.
Existuje tri zakladni typy teto ulohy
Ciphertext only attack
Desifrovani na zaklade znalosti zasifrovaneho textu --- to je
nejklasictejsi uloha kryptoanalyzy
Known plaintext attack
Desifrovani s castecnou znalosti primeho textu (a uplnou znalosti
textu zasifrovaneho). Protivnik ma k dispozici nejakym zpusobem
ziskane nektere prime texty a veskere texty zasifrovane.
Chosen plaintext attack
Desifrovani s neomezenou znalosti zasifrovaneho textu. Protivnik
ma k dispozici libovolny jim zvoleny primy text a jeho
zasifrovanou verzi. Napriklad spravce systemu muze vyrobit
libovolneho uzivatele a jeho heslo prohlizet v prime i
zasifrovane podobe.
Kryptoanalyza monoalfabetickych sifer
Metody kryptoanalyzy monoalfabetickych sifer jsou v zasade
statisticke. Pro ruzne jazyky existuji tabulky udavajici
pravdepodobnost vyskytu jednotlivych znaku. Nap[riklad pro ceskou
abecedu s mezerou vypada takova tabulka takto:
| A | 5.4% |
| A | 2.1% |
| B | 1.4% |
| C | 1.9% |
| C | 0.8% |
| D | 2.6% |
| D | 0.5% |
| E | 7.3% |
| E | 1.0% |
| E | 0.7% |
| F | 0.2% |
| G | 0.2% |
| H | 2.0% |
| I | 3.4% |
| I | 2.5% |
| J | 2.2% |
| K | 3.3% |
| L | 3.4% |
| M | 2.9% |
| N | 4.0% |
| N | 1.5% |
| O | 6.8% |
| P | 2.7% |
| Q | 0.0% (po zaokrouhleni) |
| R | 2.9% |
| R | 0.9% |
| S | 4.0% |
| S | 0.8% |
| T | 3.9% |
| T | 0.7% |
| U | 3.0% |
| U | ,U 0.5% |
| V | 3.9% |
| W | 0.0% |
| X | 0.1% |
| Y | 1.6% |
| Y | 0.8% |
| Z | 1.9% |
| Z | 0.9% |
| m | ezera 16.3% |
Tato tabulka byla ovsem ziskana analyzou velkeho mnozstvi ceskych
textu ruzneho charakteru. V textech nejakym smerem zamerenym lze
ocekavat vyssi frekvenci nekterych slov a tim padem mirne jine
rozlozeni frekvence jednotlivych znaku. Ani u monoalfabeticke
sifry tedy nelze postupovat prostym prirazenim ekvivalentu
zasifrovanym znakum.
Dalsim krokem muze byt pouziti tabulky vyskytu dvojic, ci trojic
za sebou nasledujicich znaku.
Index koincidence.
Index koincidence je hodnota, ktera muze pomoci rozhodnout, zda
byla pro zasifrovani textu pouzita monoalfabeticka ci
polyalfabeticka sifra.
Index koincidence pro dany jazyk je roven sume p(c)^2 pres vsechny
znaky c dane abecedy. Pritom p(c) je pravdepodobnost vyskytu
znaku c v textu.
Pozorovani
Necht n je velikost nejake abecedy a I index koincidence jazyka
nad touto abecedou.
Plati I-1/n = suma p(c)^2 - 1/n = suma (p(c)^2 - 1/n^2) = suma
(p(c) - 1/n)^2,
nebot suma p(c) = 0.
Plati tedy
- I >= 1/n
- 1/n je stredni hodnota nahodne veliciny p(c)
- I-1/n je smerodatna odchylka nahodne veliciny p(c)
Tabulka indexu koincidence
pro nektere jazyky prevedene do
anglicke abecedy (26 znaku ABCDEFGHIJKLMNOPQRSTUVWXYZ)
| nahodne generovana slova | 1/26 =
0.03846 |
| cestina/slovenstina | 0.06027 |
| anglictina | 0.06689 |
| danstina | 0.07073 |
| finstina | 0.07380 |
| francouzstina | 0.07460 |
| holandstina | 0.07981 |
| nemcina | 0.07667 |
| italstina | 0.07329 |
| rustina | 0.05607 |
| spanelstina | 0.07661 |
Jak vyuzit index koincidence
Je-li text zasifrovan monoalfabetickou sifrou, mel by se jeho
index koincidence blizit indexu koincidence jazyka, ve kterem byl
napsan. Je-li text zasifrovan polyalfabetickou sifrou, bude se
jeho index koincidence blizit indexu koincidence nahodne
generovaneho jazyka.
Tuto stranku vytvoril
Tomas Vanicek a jedna se o soucast volitelnych prednasek z
Kodovani a sifrovani pro
vsechny obory
Stavebni fakulty
Ceskeho vysokeho uceni technickeho v Praze.