KIB - Projekt 2

Opravujíci: Ing. Dominik Breitenbacher

Termín odevzdání

• 10.11.2015 23:59:59

Zadání

Vygenerujte si vlastní pár RSA klíčů tak, jak bylo prezentováno na cvičení. Abeceda, kterou budete používat, vypadá následovně:

0 - 00, ... , 9 - 09, A - 10, ..., Z - 35, mezera - 36

Z toho vyplývá, že při šifrování zadaného textu budete používat pouze číslice, velká písmena bez diakritiky a mezeru. Ze zadaného textu musíte šifrovat vždy minimálně 2 znaky abecedy na zprávu. To znamená, že pokud budete mít text (zprávu, kterou chcete předat druhé straně):

KOCKOPES

musíte si ji rozdělit na menší zprávy:

KO
CK
OP
ES

Vzhledem k této podmínce je nutné přizpůsobit i velikost klíčů. Pokud byste museli zašifrovat dvě mezery, znamenalo by to zašifrovat číslo 3636. Z cvičení víte, že veřejný modulus n musí být vždy větší než hodnota zprávy. Veřejný modulus n tak nemůže být menší než 3637!

Na cvičení bylo dále zmíněno, že při generování klíčů může nastat problém s výpočtem hodnoty d. Jak bude ukázáno na příkladu, hodnota d může nabýt poměrně vysoké hodnoty. Ručně nalézt takovou hodnotu by tak bylo velice náročné a zdlouhavé. Proto, pokud se dostanete k bodu, kdy bude potřeba spočítat hodnotu d, jděte na WolframAlpha a zadejte tento příkaz:

PowerMod[e,-1,EulerPhi[n]]

Obecně silně doporučuji používat pro výpočty stránku WolframAlpha.
Po vygenerování klíčů bude vaším úkolem zašifrovat následující text:

KIB PROJEKT 2 Osobní_číslo_VUT

V mém případě by to bylo:

KIB PROJEKT 2 119366

Po zašifrování zašifrovaný text opět dešifrujte, abyste si ověřili, že jste text správně zašifrovali příp. správně jste vygenerovali klíče.

Až budete mít předešlé úkoly splněny, provedete faktorizaci veřejného modulu tak, jak bylo prezentováno na cvičení. Zvolit si můžete jakoukoli z prezentovaných faktorizačních metod, tzn. Zkusmé dělení, Fermatovu metodu nebo Pollardovu p-1 metodu.

Veškeré své kroky pečlivě zdokumentujte, a to jak u generování klíčů, šifrování/dešifrování, tak u faktorizace. Stejně jako v předešlém projektu platí, že forma vypracování projektu je stejně důležitá jako obsah, a při opravování na to bude brán zřetel. Čím tedy vaše dokumentace bude bohatší, tím lépe.

Odevzdaná dokumentace by měla obsahovat titulní stranu se jménem a ID studenta, postup vypracování a závěr.

V závěru bych velice rád, abyste diskutovali bezpečnost Vámi vytvořeného páru RSA klíčů, a proč jste zvolili vámi použitou faktorizační metodu. Co se týče bezpečnosti klíče, rád bych, abyste vytvořili veřejný modulus n tak, aby byl, samozřejmě v rozumné míře, odolný vůči všem prezentovaným faktorizačním metodám (co si představuji pod pojmem "v rozumné míře", je uvedeno v příkladu níže) nebo alespoň proti Zkusmému dělení a Fermatově metodě. Takto vytvořený veřejný modulus n samozřejmě bude náročnější faktorizovat. Uvědomte si ale, že když tvoříte RSA klíče, snažíte se vždy útočníkovi co nejvíce ztížit práci, aby získání vašich citlivých dat bylo pro něj co nejnáročnější, proto by na to měl být brán zřetel při vytváření RSA klíčů. Při faktorizaci budete v podstatě tím útočníkem vy, a proto byste to neměli mít jednoduché.

Velice uvítám, pokud napíšete svůj názor na tento projekt a co byste pro příště změnili/vylepšili/přidali, aby byl projekt zajímavější. Zpětná vazba je opravdu velice důležitá...

Bodové shrnutí požadavků:

• Vygenerujte si vlastní pár RSA klíčů
• Zašifrujte zadanou zprávu
• Dešifrujte zašifrovanou zprávu
• Faktorizujte veřejný modulus n jednou z prezentovaných metod na cvičení
• Vše pečlivě zdokumentujte

Vypracovaný dokument odevzdávejte ve formátu PDF. Text projektu může být jak česky, slovensky, tak anglicky.

Příklad

Pro vygenerování RSA klíčů si zvolím prvočísla p = 29 a q = 131.
Veřejný modulus tak bude n = 3799.
Dále postupuji tak, jak bylo prezentováno na cvičení:
sigma = (p - 1)*(q - 1) = 28*130 = 3640
e = 17
d = 1713

Veřejný klíč k_pub = (n, e) = (3799, 17)
Soukromý klíč k_priv = (n, d) = (3799,1713)

Text k zašifrování:

KIB PROJEKT 2 119366

Rozděleno na menší zprávy:

KI  B_  PR  OJ  EK  T_  2_  11  93  66

kde "_" zastupuje mezeru původního textu

Zašifrování textu:

2018^17 mod 3799 = 0713
1136^17 mod 3799 = 0705
2527^17 mod 3799 = 2645
2419^17 mod 3799 = 0708
1420^17 mod 3799 = 2841
2936^17 mod 3799 = 3446
0236^17 mod 3799 = 0557
0101^17 mod 3799 = 0649
0903^17 mod 3799 = 0963
0606^17 mod 3799 = 1825

Výsledná šifra:

0713  0705  2645  0708  2841  3446  0557  0649  0963  1825

Dešifrování:

0713^1713 mod 3779 = 2018
0705^1713 mod 3779 = 1136
2645^1713 mod 3779 = 2527
0708^1713 mod 3779 = 2419
2841^1713 mod 3779 = 1420
3446^1713 mod 3779 = 2936
0557^1713 mod 3779 = 0236
0649^1713 mod 3779 = 0101
0963^1713 mod 3779 = 0903
1825^1713 mod 3779 = 0606

Dešifrovaná zpráva:

KIB PROJEKT 2 119366

Faktorizaci přeskakuji.

Závěr:
Osobně si myslím, že mnou vybraný veřejný modulus n lze v rámci tohoto projektu považovat za bezpečný vůči faktorizaci, protože při útoku Zkusmým dělením bych musel provést až 28 kroků, u Fermatovy metody pak kroků 19.

Samozřejmě takovéto okomentování projektu je nedostatečné, vaše dokumentace musí být pečlivější!

Zároveň se zakazuje použití n = 29 * 131, protože tento veřejný modulus byl použit na příkladu!

Bodové hodnocení

• Za projekt je možné získat až 7 bodů.
• Bonusové body za vytvoření programu/skriptu provádějící faktorizaci pomocí jedné z prezentovaných metod: až +2 body (bude záviset na zvolené metodě a případně i na implementovaných vylepšeních dané metody)
  Pokud takový program/skript vytvoříte, je nutné při odevzdávání projektu přiložit i okomentovaný zdrojový kód.
• Maximální bodový zisk (tzn. včetně bonusových bodů) je tedy 9

Termín odevzdání

• 10.11.2015 23:59:59

Způsob odevzdání

Emailem na adresu ibreiten@fit.vutbr.cz. Jako předmět mailu uveďte KIBProjekt2

V případě jakýchkoli nesrovnalostí či dotazů mě neváhejte kontaktovat na výše uvedenou e-mailovou adresu.

Nechť vám jde vypracování projektu od ruky!