5II117 Kryptografia a bezpečnosť

Cvičenia z predmetu Kryptografia a bezpečnosť

Oznamy

Dňa 1.11.2017 (streda) cvičenia odpadajú, lebo je štátny sviatok.

Dňa 8.11.2017 (streda) mám neodkladné povinnosti, preto budú cvičenia v náhradnom termíne. Na presnom dátume a čase sa dohodneme.

Podmienky na zápočet

Body zo semestra sa získavajú za vypracovanie semestrálnych prác - vyriešenie zadaného problému. Tento rok je zadaní šesť, za splnenie každého je možné získať (40/6) = 6,6 bodu. Na úspešné absolvovanie cvičení je potrebné získať aspoň 20 bodov, t.j. vypracovať a odovzdať aspoň tri zadania.

Semestrálne práce sa odovzdávajú osobne na cvičení alebo v individuálne dohodnutom termíne cez e-mail. K jednotlivým riešeniam úloh nie je potrebné vypracovať dokumentáciu, ale musíte rozumieť metóde a odpovedať na moje otázky pri odovzdávaní. Semestrálky je možné odovzdať aj v januári, posledný možný termín je deň pred skúškou.

Obsah cvičení:

  1. Monoalfabetické šifry, cézarovská a afínna šifra.
  2. Polyalfabetické šifry, viegenerovská šifra.
  3. Hillovská šifra, operácie v Galoisovom poli.
  4. Prúdové šifry, štatistické vlastnosti generátorov náhodných čísel.
  5. Lineárne spätnoväzobné registre.
  6. Šifrovacie algoritmy Feistellovho typu.
  7. Šifrovací algoritmus IDEA.
  8. Štúdium vlastností čísel a prvočísel.
  9. RSA algoritmus.
  10. Práca s programom PGP.
  11. Diskusné fórum.

Monoalfabetické šifry

Cézarovská šifra

Príklad cézarovskej šifry v tabuľkovom procesore: cezarovska_sifra.ods.

Afínna šifra

Príklad afínnej šifry v tabuľkovom procesore: afinna_sifra.ods.

Dešifrujte nasledovný text v telegrafnej abecede s medzerou zašifrovaný afínnou šifrou:

LIYGTOGDPOAUPDFQNVPVDAQV
Pôvodný text bol napísaný v slovenskom jazyku.

Kódovacia tabuľka znakov na čísla

A0J9S18
B1K10T19
C2L11U20
D3M12V21
E4N13W22
F5O14X23
G6P15Y24
H7Q16Z25
I8R17_26

Frekvenčná analýza jazyka

Príklad frekvenčnej analýzy slovenského textu (graf) v tabuľkovom procesore: frekvencna_analyza.ods.

Urobte frekvenčnú analýzu anglického a slovenského jazyka, určte pravdepodobnosti výskytov jednotlivých znakov referenčného textu v rôznych kódových abecedách (telegrafná, telegrafná s medzerou, ASCII, LATIN2, ...). Určte pravdepodobnosti dvojíc aj trojíc znakov. Na základe meraní navrhnite náhodný generátor slov daného jazyka.

Príklad anglického textu:

Príklad slovenského textu:

Polyalfabetické šifry

Index koincidencie

Určte Indexy koincidencie pre nasledovné texty. Na základe výsledku posúdte, či ide o monoalfabetickú príp. polyalfabetickú šifru. Priame texty sú napísané v slovenskom jazyku v telegrafnej abecede bez medzery. Pokúste sa texty dešifrovať.

Zašifrované texty:

Vigenerovská šifra

Príklad viegenerovskej šifry v tabuľkovom procesore: viegenerovska_sifra.ods

Dešifrujte text1.txt zašifrovaný viegenerovskou šifrou. Šifrovali sa len písmená telegrafnej abecedy programom v jazyku C vigen.c.

Hillovská šifra

Určte maticu K Hillovskej šifry šifrujúcej bigramy, ak viete, že FRIDAY sa zašifruje na PQCFKU. Používa sa telegrafná abeceda bez medzery.

Galoisove pole GF(28)

Naprogramujte operácie násobenia matíc a výpočtu lineárnych rovníc v poli GF(28).

Prúdové šifry

Naprogramujte algoritmus prúdovej šifry (využite vstavaný generátor pseudonáhodných čísel). Zašifrujte pomocou neho dostatočne dlhý text a urobte frekvenčnú analýzu zašifrovaného textu. Aké bude rozdelenie pravdepodobnosti znakov zašifrovaného textu? Vypočítajte index koincidencie zašifrovaného textu.

Pokúste sa dešifrovať správu zašifrovanú prúdovou šifrou s použitím lineárneho kongruetného generátora pseudonáhodných čísel. Šifrované boli len znaky telegrafnej abecedy súčtom modulo 26 so znakmi náhodnej postupnosti pomocou programu otp.c resp. otp.pas (s inou postupnosťou!).

Tu je šifrovaný text správy: sprava_enc.txt.

Vlastnosti generátorov pseudonáhodných čísel

Otestujte vstavaný generátor pseudonáhodných čísel podľa špecifikácie FIPS140-1. Otestujte prípadne aj ďalšie dostupné generátory.

Špecifikácia FIPS 140:

Posuvné registre s lineárnou spätnou väzbou

Naprogramujte generátor pseudonáhodnej postupnosti založený na lineárnom spätnoväzobnom registri. Overte štatistické vlastnosti takéhoto generátora (napr. pomocou FIPS testu).

Určte koeficienty 8-bitového lineárneho spätnoväzobného registra ak viete, že jeho výstup bol ...1110010011001111...

Šifry Feistellovho typu

Naprogramujte vlastnú šifru Feistllovho typu a pokúste sa urobiť jej kryptoanalýzu.

Šifra IDEA

Naprogramujte mini verziu blokovej šifry IDEA, t.j. všetky operácie budú vykonávané nad 4-bitovými blokmi. Pokúste sa naprogramovať útok s volenými priamymi textami a dešifrovať správu sprava.enc zašifrovanú pomocou programu miniidea. Pokúste sa určiť aj použité kľúče.

Štúdium vlastností čísel a prvočísel

Napíšte program, ktorý vypíše všetky prvočísla menšie ako 1.000.000.
Naprogramujte generátor veľkých prvočísel využitím pravdepodobnostného Miller-Rabinovho testu prvočíselnosti.
Naprogramujte rozšírený Euklidov algoritmus a použite ho na výpočet inverzného prvku v konečnom poli.

RSA algoritmus

Naprogramujte RSA algoritmus pre kľúče s modulom nanajvýš 65536 (16 bitov).
Dešifrujte správu sprava.enc zašifrovanú RSA algoritmom použitím verejného kľúča (43811, 7).

Zadania semestrálnych prác v aktuálnom akademickom roku 2017/2018

Úloha č. 1 (Vigenerovská šifra)

Dešifrujte všetky nižšie uvedené texty zašifrované vigenerovskou šifrou a určte použité heslá. Šifrujú sa len písmená veľkej telegrafnej abecedy (mod 26), všetky ostatné (väčšinou formátovacie) znaky ignorujte. Heslo je náhodne vygenerované, primerane dlhé (od 20 do 29 znakov vrátane). Pôvodné (priame texty) môžu byť v slovenskom aj anglickom jazyku!

Program použitý na zašifrovanie: vigenere.c.

Zašifrované texty: text1_enc.txt, text2_enc.txt, text3_enc.txt a text4_enc.txt.

Úloha č. 2 (Hillovská šifra)

Určte všetky štyri šifrovacie a dešifrovacie kľúče Hillovskej šifry šifrujúcej trigramy (matice rozmeru 3x3), ak sa priamy text "KRY PTO GRA FIA APO CIT ACO VAB EZP ECN OST" zašifruje na:

  1. "EBN ZJN OZX LSS ETT WQT EGG HCT YFA CSJ UKT"
  2. "AHX DXG KZX RIX EJL XZV EWY ARS TUM LZZ RLZ"
  3. "CBT JXX MXB HIU QFV SET QSI HEV SHU OQX YWT"
  4. "ZIR NRU BWN SRX BQF JZN OQS TOG AVO BNT XJV"

Šifrujú sa písmená veľkej telegrafnej abecedy (operácie sú modulo 26). Stačí vypočítať matice v tabuľkovom procesore (MS Excel, LibreOffice Calc, ...) alebo v Matlab-e (octave, sage, wolfram alpha, ...) alebo podobnom softvéri. Nemusíte (ale samozrejme môžete) výpočet naprogramovať.

Podľa zadania viete vytvoriť až 11 párov trojíc písmen, t.j. 33 rovníc. Keďže je 9 neznámych (matica 3x3 má 9 prvkov), zo všetkých 33 rovníc si treba vybrať takých 9, kedy sa bude dať sústava vyriešiť (bude mať jediné riešenie resp. viete urobiť inverznú maticu sústavy rovníc).

Úloha č. 3 (Prúdová šifra)

Určte všetky štyri použité kľúče prúdovej šifry (násadu generátora pseudonáhodných čísel) pre nasledujúce texty zašifrované pomocou programu stream.c.

Zašifrované texty: text1_enc.txt, text2_enc.txt, text3_enc.txt a text4_enc.txt.

Úloha č. 4 (RSA algoritmus)

Vypočítajte aspoň 3 privátne kľúče algoritmu RSA a dešifrujte správu (číslo):

  1. n = 13169004533; e = 65537; y = 6029832903;
  2. n = 1690428486610429; e = 65537; y = 22496913456008;
  3. n = 56341958081545199783; e = 65537; y = 17014716723435111315;
  4. n = 6120215756887394998931731; e = 65537; y = 5077587957348826939798388;
  5. n = 514261067785300163931552303017; e = 65537; y = 357341101854457993054768343508;
  6. n = 21259593755515403367535773703117421; e = 65537; y = 18829051270422357250395121195166553;
  7. n = 1371108864054663830856429909460283182291; e = 65537; y = 35962927026249687666434209737424754460;

Ak sú čísla príliš veľké na faktorizáciu hrubou silou, treba si pomôcť sofistikovaným algoritmom implementovaným v nejakej knižnici alebo napríklad aj Wolfram Alpha.

Úloha č. 5 (Autentifikácia heslom)

Pokúste sa určiť heslá niekoľkých používateľov systému, z ktorého sa podarilo skopírovať tabuľku s prihlasovacími údajmi. Tabuľka v textovej podobe obsahuje prihlasovacie meno, soľ a odtlačok hesla (so soľou). Odtlačok sa počíta algoritmom MD5, ktorého výsledok je konvertovaný na String pomocou Base64Encoding.

Vzorová implementácia funkcie na výpočet odtlačku v jazyku C# je v súbore Program.cs a v jazyku Python v súbore crypt.py.

Ako slabé heslá mohli byť použité:

  • krstné mená podľa slovenského kalendára alebo ich zdrobneniny, pričom môžu obsahovať najviac jedno veľké písmeno kdekoľvek v slove (napríklad zuzana, Zuzana, zuZana, zUzka, zuzkA, ...),
  • heslá s počtom znakov 6 alebo 7, pozostávajúce len z malých písmen (napríklad asdfgh, utywmk, klnrtus, ...),
  • heslá s malým počtom znakov 4 alebo 5 pozostávajúce z malých a veľkých písmen a číslic (napríklad w7H5, WnU8a, ...).

Malo by sa vám podariť prelomiť v každom súbore aspoň po jednom hesle z každej kategórie. Súbory s prihlasovacími údajmi si môžete stiahnuť tu:

Na oddelenie jednotlivých položiek bol použitý znak ":", každý riadok je teda v tvare "login:soľ:odtlačok".

Úloha č. 6 (Podpisovanie e-mailov pomocou PGP)

V systéme OpenPGP si pomocou ľuboľného softvéru alebo pluginu vytvorte dvojicu verejného a privátneho kľúča. Verejný kľúč mi pošlite e-mailom zašifrovaný pomocou môjho verejného kľúča 0xD93F5170.asc na adresu tomas.majer@fri.uniza.sk. Fingerprint môjho kľúča je 4D5C 4BD8 3100 7741 6953 D209 4F3A D031 D93F 5170, do tela mailu mi napíšte fingerprint Vášho kľúča.

Ako odpoveď na tento mail Vám pošlem zašifrovaný e-mail s ďalšími pokynmi.