6II0020 - Kryptografia a bezpečnosť

Cvičenia z predmetu Kryptografia a bezpečnosť, akademický rok 2023/2024

Oznamy

Termín prednášky

  • Štvrtok o 16:00 AR1A3 (NR3)

Termíny cvičení

Ing. Tomáš Majer, PhD.

  • Utorok o 10:00 RA301
  • Utorok o 15:00 RA301
  • Streda o 10:00 RA301

Ing. Maroš Janovec, PhD.

  • Pondelok o 12:00 RA301
  • Pondelok o 14:00 RA301

Podmienky na zápočet

Body zo semestra sa získavajú za vypracovanie domácich úloh - vyriešenie zadaného problému. Počet bodov, ktoré za vypracovanie úlohy môžete získať je uvedený v zadaní. Na úspešné absolvovanie cvičení je potrebné získať aspoň 20 bodov z celkovo možných 40 bodov.

Vyriešené úlohy sa odovzdávajú osobne na cvičení (v jeho druhej polovici) alebo v individuálne dohodnutom termíne cez e-mail. K jednotlivým riešeniam nie je potrebné vypracovať dokumentáciu, ale musíte rozumieť metóde a odpovedať na moje otázky pri odovzdávaní. Prvé tri úlohy je potrebné odovzdať do konca zimného semestra, zvyšné úlohy bude možné odovzdať aj v januári. Termíny na odovzdanie úloh v januári budú vypísané v e-vzdelávaní.

Zadania (zatiaľ len z minulého akademického roku) nájdete na tejto stránke dole.

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.

Odvodenie dešifrovacieho vzorca: afinna_sifra_odvodenie.pdf.

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. Tento program by súbor block.txt so všetkými možnými blokmi zašifroval na súbor block.enc. 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).
Výpočet v Jupyter notebook-u: RSA-1.ipynb.

Zadania semestrálnych prác v akademickom roku 2023/2024

Úloha č. 1, Viegenerovská šifra (8 bodov)

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 15 do 25 znakov vrátane). Pôvodné (priame texty) môžu byť v slovenskom aj anglickom jazyku!

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

Úloha č. 2, Hillovská šifra (6 bodov)

Dešifrujte všetky tri nižšie uvedené texty zašifrované pomocou Hillovskej šifry šifrujúcej trigramy (kľúčom je matica rozmeru 3x3), ak sa priamy text vždy začínal na "DRAHYJURAJ".

  1. "BALQTGFGYNFUHVLOIVCGPRZJUTHGWOVWCWAJGWN"
  2. "PCPOVZOJYEJXJLVINLJMIAVAVEUKZLERO"
  3. "NMUSMRFJGRWSWVKKDJKYTYTNSVMOJW"

Šifrujú sa písmená veľkej telegrafnej abecedy (operácie sú modulo 26). Matice stačí vypočítať 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ť.

Pozor! Násobenie matíc nie je komutatívne!

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

Určte všetky štyri použité násady prúdovej šifry (heslo pre inicializáciu 256 bajtového kľúča RC4 generátora) pre nasledujúce texty zašifrované pomocou programu stream.c. Verím, že si program ľahko prepíšete do akéhokoľvek iného programovacieho jazyka, pozor ale na implementáciu funkcie getKey.

Použité heslo je 6-ciferné číslo zadané ako reťazec, t.j. v rozsahu "100000" až "999999".

Súbory síce majú príponu TXT, ale treba s nimi narábať ako s binárnymi súbormi, t.j. stiahnuť odkaz a nepoužívať Ctrl+C, Ctrl+V. Zašifrované texty:
text1_enc.txt, text2_enc.txt, text3_enc.txt a text4_enc.txt.

MD5SUM odtlačky zašifrovaných textov na kontrolu, či ste ich dobre stiahli:

4622c7bcb17d81c081baec766fb6fdc2  text1_enc.txt
95048f6ded12b35a87015078c236abf2  text2_enc.txt
be5401874206c8066a255ad39f127ca2  text3_enc.txt
8314a669612496867c3388c76e783bf7  text4_enc.txt

Úloha č. 4, RSA algoritmus (8 bodov)

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

  1. n = 2164267772327; e = 65537; y = 1325266873785;
  2. n = 16812615098258879; e = 65537; y = 1990249581724467;
  3. n = 181052234309092978339; e = 65537; y = 147885702766350471578;
  4. n = 1327612780145399205245813; e = 65537; y = 1075593273482743198269527;
  5. n = 329897251897125970254396723194243; e = 65537; y = 22712629296843271867140518185260;
  6. n = 26845416039893360305516015851501077574841; e = 65537; y = 6820997247850432766042868007364587250604;
  7. n = 2146776870009792253322117406137065611833216495831; e = 65537; y = 604615692674313046352476676786807225671015935385;

Aspoň prvé 3 úlohy vypočítajte vlastným programom a na zvyšné čísla (príliš veľké na faktorizáciu hrubou silou), použite nejaký sofistikovaný algoritmus (môže byť aj implementovaný v nejakej knižnici alebo v programe ako napríklad Wolfram Alpha).

Úloha č. 5, Autentifikácia heslom (6 bodov)

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 (6 bodov)

V systéme OpenPGP si pomocou ľuboľného softvéru alebo pluginu vytvorte dvojicu verejného a privátneho kľúča. Verejný kľúč pošlite šifrovaným a digitálne podpísaným e-mailom mne alebo Ing. Janovcovi. Naše e-mailové adresy a verejné kľúče sú:

E-mailCertifikátFingerprint
tomas.majer@fri.uniza.sk 0x0F6EE504E07064AF.asc DCE0 1354 AEBA 0AEC E7A2 566A 0F6E E504 E070 64AF
maros.janovec@fri.uniza.sk 0xD21AA1A4EFE717C1.asc C7AC 151F 5419 3C08 9748 FF88 D21A A1A4 EFE7 17C1

V zašifrovanej a digitálne podpísanej odpovedi na tento mail Vám pošleme ďalšie pokyny.