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. Zadania z minulých rokov môžete nájsť nižšie. Pre tento rok predpokladám, že zadaní bude päť. Za každé bude možné získať osem bodov, na úspešné absolvovanie teda budete musieť spraviť aspoň tri.

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. Štúdium vlastností RSA algoritmu.
  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.

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)

Zadanie úlohy pripravujem.

Úloha č. 4 (Autentifikácia heslom)

Zadanie úlohy pripravujem.

Úloha č. 5 (RSA algoritmus)

Zadanie úlohy pripravujem.

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

Zadanie úlohy pripravujem.

Staršie zadania z predchádzajúceho akademického roku 2015/2016 nájdete tu.