Kryptografia a bezpečnosť, akademický rok 2024/2025
Prednášky
Termín prednášky
- Utorok o 10:00 AR1A3 (NR3)
Stručná osnova predmetu
- História kryptografie. Všeobecný model šifrovacieho systému, kryptoanalýza a základné typy útokov. (kab_1.pdf)
- Klasická kryptografia, monoalfabetické a polyalfabetické šifry. (kab_2.pdf), (kab_3.pdf)
- Výpočtová a bezpodmienečná bezpečnosť, perfektné šifrovanie (one time pad).
- Generátory pseudonáhodnej postupnosti v kryptografii, prúdové šifry.
- Symetrická kryptografia, kryptosystémy Feistellovho typu DES a GOST.
- Blokové šifry IDEA a AES (Rijndael).
- Asymetrická kryptografia, algoritmus RSA.
- Hashovacie funkcie a digitálny podpis.
- Diffie – Hellmanova výmena kľúčov.
- Kryptografický protokol Transport Layer Security (TLS).
Cvičenia
Termíny cvičení
Ing. Tomáš Majer, PhD.
- Pondelok o 12:00 RA301
- Pondelok o 14:00 RA301
- Utorok o 12:00 RA301
- Štvrtok o 12:00 RA301
Ing. Maroš Janovec, PhD.
- Pondelok o 10:00 RA301
- Streda o 13: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ť najneskôr do konca zimného semestra, zvyšné úlohy bude možné odovzdať aj v januári, aj keď samozrejme odporúčam ich odovzdať čo najskôr. 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.
Oznamy
Prosba o vyplnenie dotazníka
Moja obľúbená kolegyňa Lucka Pančíková s kolektívom robí prieskum o štúdiu na našej Fakulte FRI a tak Vás veľmi pekne prosím o vyplnenie anonymného dotazníka na adrese https://shorturl.at/0e6d9.
Ďakujem.
Nižšie už sú len staršie materiály z minulych akademických rokov.
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í:
- Monoalfabetické šifry, cézarovská a afínna šifra.
- Polyalfabetické šifry, viegenerovská šifra.
- Hillovská šifra, operácie v Galoisovom poli.
- Prúdové šifry, štatistické vlastnosti generátorov náhodných čísel.
- Lineárne spätnoväzobné registre.
- Šifrovacie algoritmy Feistellovho typu.
- Šifrovací algoritmus IDEA.
- Štúdium vlastností čísel a prvočísel.
- RSA algoritmus.
- Práca s programom PGP.
- 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:
LIYGTOGDPOAUPDFQNVPVDAQVPôvodný text bol napísaný v slovenskom jazyku.
Kódovacia tabuľka znakov na čísla
A | 0 | J | 9 | S | 18 |
---|---|---|---|---|---|
B | 1 | K | 10 | T | 19 |
C | 2 | L | 11 | U | 20 |
D | 3 | M | 12 | V | 21 |
E | 4 | N | 13 | W | 22 |
F | 5 | O | 14 | X | 23 |
G | 6 | P | 15 | Y | 24 |
H | 7 | Q | 16 | Z | 25 |
I | 8 | R | 17 | _ | 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
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.
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
Šifra IDEA
Štúdium vlastností čísel a prvočísel
RSA algoritmus
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".
- "BALQTGFGYNFUHVLOIVCGPRZJUTHGWOVWCWAJGWN"
- "PCPOVZOJYEJXJLVINLJMIAVAVEUKZLERO"
- "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):
- n = 2164267772327; e = 65537; y = 1325266873785;
- n = 16812615098258879; e = 65537; y = 1990249581724467;
- n = 181052234309092978339; e = 65537; y = 147885702766350471578;
- n = 1327612780145399205245813; e = 65537; y = 1075593273482743198269527;
- n = 329897251897125970254396723194243; e = 65537; y = 22712629296843271867140518185260;
- n = 26845416039893360305516015851501077574841; e = 65537; y = 6820997247850432766042868007364587250604;
- 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ú:
Certifikát | Fingerprint | |
---|---|---|
tomas.majer@fri.uniza.sk | 0x0F6EE504E07064AF.asc | DCE0 1354 AEBA 0AEC E7A2 566A 0F6E E504 E070 64AF |
maros.janovec@fri.uniza.sk | OpenPGP_0xEFE717C1.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.