49 - Klasická kryptografie, substituční a transpoziční šifry, rotorové stroje.
neděle 28. května 2017
19:47
Typy klasických šifer
Steganografické
Ukryjí přenášený text uvnitř jiného textu
Substituční
Nahrazují jednotlivé znaky/symboli textu jinými znaky
Transpoziční
Mění pořadí znaků v textu (typicky pomocí nějakého geometrického obrazce, např. Matice)
Steganografie
-Ukrytí informace uvnitř něčeho jiného
-Příklady
Informace uvnitř textového souboru
Vodoznak
Berou například pouze poslední slova na řádcích
Moderní použití
Zpráva se zkládá z posloupnosti bitů
Některé bity jsou zpráva a zbytek tvoří vatu
Pomocí klíče jsme schopni zjistit, které jsou vata a ty vypustit
Šifrovaný text je delší (často významně) než otevřený text
Substituční
Kerckhoffův princip
Bezpečnost musí záviset pouze na utajení klíče
Freemason
Abaceda se nemusí zkládat pouze ze znaků ale obecně z jakýchkoli symbolů
Caesarova šifra
První známe algoritmické šifrování
Nahrazování písmena třetím následujícím písmenem v abecedě
Slabiny
Každý kdo zná algoritmus, může zprávu dešofrovat
Malý stavový prostor klíčů - ani při změně rotace si moc nepomůžeme
Je náchylná na frekvenční analýzu
Monoalfabetické substituční šifry
Substituční šifry nahrazují jednotlivé písmena textu pomocí klíče, kterým je permutace všech 26 písmen
Počet všech možných klíčů je 26! = 4*10na26
Nerozluštitelné během celého prvního tisíciletí našeho letopočtu
Zapamatovatelný klíč
Zapsání jednotlivých slov hesla po řádcích
Zapisování hesla po sloupcích s doplněním zbylích písmen abecedy
Anatomie jazyka: Frekvence
Nejčastější písmena pro angličtinu
Etaoinshrdlu
Kliky
E T AOIN SRH LD
Digramy
TH HE IN ER AN RE ED ON…
Trigramy
THE ING AND HER ERE ENT THA NTH WAS…
Anatomie jazyka: Patterns
Pro všechny jednoduché monoalfebetické substituční šifry je vzorek opakování jednotlivých znaků v textu invariantní k této substituci
Notace vzorku
NRGRN -> 12321, NRGRNON -> 1232142
Realizace vrozku je často jedinečná
1221 má asi 250 realizací, ale jenom málo z nich je z vojenského prostředí (assault, attack, battalion, barrack)
Opakování slov pro zdůraznění má vynikající vzorek
Metoda pravděpodobného slova
Pokud hledáme pravděpodobné slovo DIVISION, hledáme všechny výskyty vzorku 12131
Zvýšení odolnosti monoalfabetické substituce
Uříznutí vyrcholů tabulky frekvencí
Homofonní šifry - převádějí jeden znak textu na několik jiných znaků textu
Šifrování skupin znaků (např. Dvojic znaků)
Symbol abecedy se skládá z více znaků
Polygramové šifry - nahrazují skupinu znaků jinou skupinou znaků
Každý znak zprávy se zašifruje jinou transformací
Polyalfabetické šifry - různé znaky zprávy jsou převáděny různým způsobem
Nomenklátory
Od konce 15 století obsahují již mimo klasických substitučních homofonních záměn také
Znaky pro zdvojená písmena
Slabiky
Kódy pro nejfrekventovanější slova a jména
Klamače
Písmena a slova jsou přepsána na kódy
Playfair - digrafická substituce
1858 Charles Weatstone
25 znaků (kromě J), počínaje heslem je vepsáno do čtverce 5x5, který je chápán jako torus
am -> LE, dl -> KT
ag -> EC, ho -> QR
Pokud je v textu dvojice stejných znaků, je jeden znak vynechán
26 x 26 = 676 digramů -> pro frekvenční analýzu bychom potřebovali tabulku s 676 položkami -> více textu na analýzu
Polyalfabetické substituční šifry
Použití více různých substitucí
Každý znak je zašifrován jinou substituční funkcí
Zploštění frekvenční charakteristiky jazyka
Frekvenční analýzu ani jiné statistické metody nelze použít
Viginerova šifra
+-1600
Nerozlomitelná cca 300 let
Používá Caesarova principu
S rozdílnými posuvy pro jednotlivé znaky, aby se zakryla frekvence znaků
Znaky klíče definují posuv pro jednotlivá písmena
Klíč se periodicky opakován, aby obsáhl celou délku šifrovaného textu
Vigenerova tabulka
Autoklíč
Mechanismus, kdy je domluven pouze počáteční klíč (často jen jedno písmeno), ktešrý je pak modifikován
Samotnou zprávou (autoklíč otevřeného textu)
Zašifrovanou zprávou (autoklíč zašifrovaného textu)
Kryptoanalýza
Zjistit délku klíče
Kasiskiho test
Nalézt několik identických úseků textu a nalézt největšího společného dělitele - délka klíče
Index koincidence
Pravděpodobnost, že dva náhodné prvky v textu jsou identické
Index koincidence řetězce v angličtině je přibližně 0.065
Zkoušíme text rozdělovat po m písmenech a na ně udělat test koincidence
Vernamova šifra - One Time Pad
Polyalfabetická substituce bez opakování klíče
Tento systém je absolutně bezpečný - Calud Elwood Shannon
Šifra je nerozluštitelná pokud
Klíč má stejnou délku jako všechny šifrované zprávy
Klíč se nikdy nepoužije znovu
Klíč je náhodně zvolen (opravdu náhodně)
Transpoziční šifry
Scytale
Stará transpoziční šifra používaná v řecku
Proužek papíru na tyčy
Klíčem je průměr tyče
Rail Fence
Railfence: TRHCEEIETGSSMAIAEASS
Redfence (klíčovaná): IETGIAESHCEESSMATRSS
Sloupcová transpozice
Dvojitá sloupcová transpozice
Rotorové stroje
Posouvané abecedy
Substituce
Typy posouvaných abeced
Horizontálně posouvaná abeceda
Vertikálně posouvaná abeceda
Rotovaná abeceda
Rotorové stroje
Implementují polyalfabetické substituční šifry s dlouhou periodou pomocí sady rotorů
Každý rotor má 26 kontaktů na obou stranách. Kontaktý z přední strany jsou propojeny s kontakty ze zadní strany. Klíč je dán propojením kontaktů a počáteční pozicí rotorů.
Enigma
Tři rotory (vybrány z pěti možných)
Po každém znaku se první rotor pootočí
Po dojetí na zařážku se pootočí další rotor
Reflektor
Propojovací deska (Plugboard, Steckerbrett)
Slouží k prohození písmen
Rotory
Tři z pěti rotorů
Počáteční orientace rotorů
Posunutí - počáteční orientace
Kdy se pootočí další rotor - asi nastavení zarážky
Propojovací deska
Výměna páru znaků pomocí kabelu
Bletchley Park - dešifrování Enigmy - Alan Turing