Tonda Beneš Ochrana informace jaro 2011

Tonda Beneš

Ochrana informace – jaro 2011

Literatura PFLEEGER, "Security in Computing", Prentice-Hall, 1989 SCHNEIER, "Applied Cryptography", John Wiley & Sons, 1994 IBYL, "Ochrana dat v informatice", scriptum VUT, 1993 Frequently Asked Questions About Today's Cryptography, http://www.rsasecurity.com/rsalabs/faq/index.html MENEZES, OORSCHOT, VANSTONE, „Handbook of Applied Cryptography“, CRC Press, 1996 GOLDREICH, „The Foundations of Cryptography“, Cambridge University Press, 2001 (vol. 1), 2004 (vol 2.), http://www.wisdom.weizmann.ac.il/~oded/foc-book.html

Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

1/9

Tonda Beneš


Terminologie …

Otev ený text [Plaintext] - originální tvar zprávy Šifrovaný text, šifra [Ciphertext] – “zakódovaný” tvar zprávy po aplikaci šifrování Šifrování [Encryption, encoding, enciphering] je proces, p i kterém je zpráva zakódována tak, že její obsah není z ejmý Dešifrování [Decryption, decoding, deciphering] je pak proces opa ný Kryptosystém [Cryptosystem] je systém umož ující šifrování a dešifrování zpráv a generování klí . Formální zápis: (C - šifra, P - otev ený text, E,D - (de)šifrovací algoritmus, K - klí ) šifrování: C = E(P) resp. C = E(K, P) , C = E(KE, P) dešifrování: P = D(C) resp. P = D(K, C), C = D(KD, P) korektnost: P = D(E(P))

Figure 0.1 Šifrování (Encryption)


2/9

Tonda Beneš


Figure 0.2 Šifrovací systém s jedním klí em (Single-Key Cryptosystem)

Figure 0.3 Šifrovací systém s dv ma klí i (Two-Key Cryptosystem) Kryptografie [Cryptography] využívá šifrování k ukrytí dat Kryptoanalýza [Cryptoanalysis] se zabývá hledáním zp sob jak šifrované zprávy neautorizovan dešifrovat (encryption break) Kryptologie [Cryptology] - je v da o šifrování obecn edchozí odv tví

a zahrnuje tedy ob

Šifrovací algoritmus m ze být zlomen - znamená, že s dostatkem asu a prost edk m že být nalezen zp sob jak dešifrovat jím zašifrované zprávy bez znalosti klí e.


3/9

Tonda Beneš


Prakticky nezlomitelný - je znám postup jak se domoci otev eného textu, ale ne v rozumném ase (se sou asnou technologií a znalostmi! ). asto používaná reprezentace znak (výpo ty jsou modulo n=26) znak A B C D E F G H I J K L M N kód 0 1 2 3 4 5 6 7 8 9 10 11 12 13 znak O P Q R S T U V W X Y Z kód 14 15 16 17 18 19 20 21 22 23 24 25

Monoalfabetické šifry - substitu ní šifry, používající jednu substitu ní tabulku, která každému znaku abecedy p azuje jiný Caesarova šifra: ci=E(pi)=pi+3 Otev ený text ABCDEFGHIJKLMNOPQRSTUVWXYZ Šifrovaný text defghijklmnopqrstuvwxyzabc


4/9

Tonda Beneš


Substituce s klí em: Otev ený text ABCDEFGHIJKLMNOPQRSTUVWXYZ Šifrovaný text keyabcdfghijlmnopqrstuvwxz Kryptoanalýza - vyhledávání typických shluk znak pro daný jazyk, typických prvních/posledních znak slov a etnost výskytu jednotlivých znak (frekven ní analýza)

Polyalfabetické substituce nevýhodou monoalfabetických substitucí je, že odrážejí rozložení pravd podobnosti jednotlivých snake použitím více substitu ních tabulek polyalf. substituce dosahují rovnom rného rozložení pravd podobnosti výskytu jednotlivých znak v šifrovaném textu edp. k substitu ních tabulek znak pik+j je šifrován pomocí j-té tabulky

Vigenêre tableaux je p íkladem polyalf. substituce


5/9

Tonda Beneš


šifruje se nap . pomocí klí e: klí ové slovo K délky k napíšeme opakovan nad otev ený text. znak Ki mod k ur uje ádek tabulky, který bude použit znak pi zašifrujeme íslem sloupce, ve kterém se nachází 0 1 2 01234567890123456789012345 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

abcdefghijklmnopqrstuvwxyz abcdefghijklmnopqrstuvwxyz bcdefghijklmnopqrstuvwxyza cdefghijklmnopqrstuvwxyzab defghijklmnopqrstuvwxyzabc efghijklmnopqrstuvwxyzabcd fghijklmnopqrstuvwxyzabcde ghijklmnopqrstuvwxyzabcdef hijklmnopqrstuvwxyzabcdefg ijklmnopqrstuvwxyzabcdefgh jklmnopqrstuvwxyzabcdefghi klmnopqrstuvwxyzabcdefghij lmnopqrstuvwxyzabcdefghijk mnopqrstuvwxyzabcdefghijkl nopqrstuvwxyzabcdefghijklm opqrstuvwxyzabcdefghijklmn pqrstuvwxyzabcdefghijklmno qrstuvwxyzabcdefghijklmnop rstuvwxyzabcdefghijklmnopq stuvwxyzabcdefghijklmnopqr tuvwxyzabcdefghijklmnopqrs uvwxyzabcdefghijklmnopqrst vwxyzabcdefghijklmnopqrstu wxyzabcdefghijklmnopqrstuv xyzabcdefghijklmnopqrstuvw yzabcdefghijklmnopqrstuvwx zabcdefghijklmnopqrstuvwxy

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Analýza polyalfabetických substitucí základem je ur ení po tu použitých substitucí, dále dokument rozd líme na ásti, šifrované stejnou substitucí a na tyto ásti použijeme postupy analýzy monoalf. šifer Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

6/9

Tonda Beneš


ur ování po tu použitých substitucí -

Kasiského metoda pokud se v otev eném textu vyskytuje k-krát stejný et zec znak a k šifrování bylo použito n substitucí, které se cyklicky st ídají, bude daný et zec zašifrován ibližn k/n krát stejn . 1. prohledáváme zašifrovaný text na výskyt opakujících se et zc (délky aspo 3) 2. zjistíme vzdálenosti za átk jednotlivých et zc 3. ke každé vzdálenosti získané v p edchozím bod vytvo íme seznam všech litel tohoto ísla 4. po et použitých substitucí by m l odpovídat n kterému z asto se vyskytujících litel

Index koincidence ozna me Freqi definujeme

po et výskyt

i z

IC i a

symbulo i ve zpráv . Index koincidence IC

Freqi * Freqi 1 n* n 1

Pokud má odpovídající otev ený text rozložení znak blízké normálu, lze z IC usuzovat na po et použitých substitucí. # substitucí IC

1 .068

2 .052

3 .047

4 .044

5 .044

10 .041

>10 <.038

"Perfektní" substitu ní šifry složitost analýzy polyalfabetických šifer roste s po tem použitých substitucí. -> co eba použít každou substituci jen jednou


7/9

Tonda Beneš


One-time pad edpokládáme že máme k dispozici klí e v celkové délce v tší, než p enášená zpráva. Každý tento klí použijeme jen jednou, t.j. k zašifrování tolika znak , jakou má délku. Šifrovat m žeme nap . pomocí Vigenêrovy tabulky. K dešifrování je t eba mít stejnou sadu klí .

Dlouhé sekvence náhodných ísel … mohou být použity namísto klí

pro one-time pad systémy

Generátory náhodných ísel je nutné používat vhodné generátory pracující na základ náhodných veli in žné po íta ové generátory jsou nevhodné

m ení skute

Kongruen ní generátor náhodných ísel

ri

1

a * ri

b mod n

bohužel, pokud úto ník získá ri ,... , ri+3, m že dopo ítat a, b a n.

Sekvence text z knih mohou být použity namísto náhodných ísel. otev ený text a takto vytvo ený klí mají charakteristické rozložení pravd podobnosti výskytu znak . až 25% znak šifrovaného textu vzniká kombinací n kolika nej ast jších symbol . -> lze rozkrýt ást zprávy, což nám umožní efektivn odhadnout zbytek.

Vernamova šifra možná implementace one-time pad-u


8/9

Tonda Beneš


Transpozi ní šifry Sloupcové transpozice otev ený text zapíšeme do po ádcích matice šifrovaný text vznikne p tením této matice po sloupcích Základem je zjistit jak vypadala šifrovací matice. Analýza se provádí hledáním digram , trigram , p ípadn delších sekvencí a jejich frekven ní analýzou. tssohoa niwhaasolrsto

tssohoa niwhaasolrsto

Rotorové stroje Enigma

Na podobném principu fungovala celá ada dalších stroj Hagellin, ... Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

9/9

Tonda Beneš Ochrana informace jaro 2011

Recommend Documents