V prvním díle tohoto mini seriálu jsem si shrnuli nezbytné minimum teorie potřebné k pochopení celého algoritmu. Dnes přejdeme k zajímavější části a vygenerujeme si veřejný a soukromý klíč.
Celá implementace v tomto miniseriálu bude probíhat v javascriptu s použitím knihovny BigInt.js pro zpracování a používání velkých čísel.
Začneme jednoduše. Vygenerujeme si dvě veliká prvočísla a ty mezi sebou vynásobíme. Čím vyšší budou prvočísla, tím bezpečnější a odolnější naše klíče budou, ale tím složitější bude jejich generování. Pro ukázku nám bude stačit 512 bitů, ale v praxi bychom měli začínat minimálně na dvojnásobku.
p = randTruePrime(512); q = randTruePrime(512); n = mult(p,q); |
Pro generování a násobení používáme funkce ze zmíněné knihovny, protože potřebujeme zpracovat tak velká čísla, která už javascript sám o sobě neumí. Číslo n má speciální význam a je společné pro oba klíče.
Prozatím je to jednoduché že? Tak trošku přitvrdíme.
phi = mult(sub(p,one),sub(q,one)); |
Číslo phi získáme jako výsledek Eurelovy funkce, která je sama o sobě dost složitá, ale díky tomu, že používáme prvočísla, stačí obě zmenšit o jedničku a vynásobit mezi sebou.
A teď konečně vygenerujeme veřejný exponent.
function public_exponent(phi) { // vygenerujeme si nahodne cislo o ktere zmensime zaklad, abychom dodali prvek nahodnosti tmp = sub(phi,randBigInt(56,0)); // najdeme ve smycce cislo nesoudelne s phi a mensi nez phi while(true) { tmp = sub(tmp,one); gcd = GCD(phi,tmp); if (bigInt2str(gcd,10) == "1") { return tmp; } } } |
Výpočet veřejného exponentu e budeme odvozovat od čísla phi. Začneme tím, že jej o náhodné číslo zmenšíme, protože e musí být menší než phi. Druhá podmínka je, že e a phi musí být nesoudělné, takže jediné číslo, kterým jsou e a phi beze zbytku dělit, musí být jednička. Takže číslo e zmenšujeme po jedničce tak dlouho, dokud nebudou splněny obě podmínky.
A teď to přijde.
d = inverseMod(e,phi); |
Vypadá to jednoduše? Není. Číslo d je námi hledaná část privátního klíče, který nikdy nikomu nedáme. Operace, kterou jej hledáme se jmenuje multiplikativní inverze a znamená, že hledáme řešení následující rovnice d = NSD(A,B)=A*X+B*Y, kde NSD znamená nalezení nejmenšího společného dělitele. K nalezení takového čísla se používá rozšířená verze Eukleidova algoritmu.
Důležité je vědět, že operace pro výpočet výše zmíněných čísel jsou relativně matematicky jednoduché, když se provádí tímto směrem. Pokud bychom ale zkusili získat z veřejného klíče dvojici čísel e a n, museli bychom použít faktorizaci, tedy rozklad čísla na součin jeho prvočíselných faktorů. Faktorizace je dost komplikovaný problém a při faktorizaci vysokého čísla i velmi výpočetně náročný. Použijeme-li při generování klíčů dostatečně veliká čísla, je rozklad veřejného klíče na prvočíselné faktory téměř nemožný, na čemž je založena bezpečnost našich informací. Pokud by se totiž někomu faktorizace podařila, získal by z první části veřejného klíče (exponentu) právě ta prvočísla, ze kterých jsme celý výpočet začali, což jsou čísla, s jejichž pomocí lze získat soukromý klíč a následně dešifrovat naše tajné informace.
Výsledkem našeho dnešního snažení je veřejný klíč, který obsahuje veřejný exponent e a modulo n a privátní klíč, který obsahuje privátní exponent d a modulo n.
Příště se podíváme na to, jak pomocí našich nových klíčů konečně zašifrovat nějakou informaci.
Kategorie:
Okomentovat