Jak jsou vlastně chráněné na internetu naše zprávy, bankovní detaily či hesla? V dnešních dobách naše data chrání šifrovací protokoly založené na matematických problémech jako je rozkládání přirozených čísel na prvočísla. Pokud totiž známe součin dvou velkých prvočísel, tak velmi těžko rekonstruujeme ona dvě prvočísla. Alespoň na klasickém počítači.
Na počítači kvantovém – tj. založeném na procesech z kvantové mechaniky, například principu „superpozice“ – totiž celé číslo rozložíme na prvočísla velmi rychle. Tak rychle, že známý protokol založený na rozkládání přirozených čísel, RSA, nemá šanci cokoliv ochránit. Od navržení systému RSA již uběhlo více než 40 let, v mezičase se objevily nové slibné nápady na kryptografické protokoly. Zmiňme ku příkladu Diffie-Hellmanovu výměnu, založenou na tzv. „problému diskrétního logaritmu“, problém v jistém smyslu podobný jako rozkládání na prvočísla. Diskrétní logaritmus počítáme na jistých speciálních množinách, které splňují jisté podmínky (tzv. grupy). Velmi zajímavým a netriviálním příkladem takové množiny je množina všech bodů na „eliptické křivce“, právě té jsem se v práci věnoval nejvíce.
Na eliptické křivce můžeme adaptovat Diffie-Hellmanovo schéma, přičemž problém nalezení diskrétního logaritmu je tentokrát velice těžký. Dokonce až tak, že protokol TLS, který pravě teď chrání většinu webových stránek, je na tomto problému založený. Bohužel, kvantový počítač vyzraje nad problémem diskrétního logaritmu i na eliptické křivce. A už teď se staví kvantové počítače více než milionkrát rychlejší, než naše klasické.
Představme si svět za 15 let, někdo postaví monstrózní kvantový „superpočítač“. RSA je nepoužitelné. Diffie-Hellman i jeho odolnější varianty? Mrtvé. Kvůli této skutečnosti vznikl obor tzv. post-kvantové kryptografie, kde hledáme nové matematické problémy a protokoly, které i před kvantovým počítačem obstojí. Matematici se ve snaze porazit kvantový počítač vydali různými směry, jeden z nejnovějších a zároveň nejslibnějších nás vrací k eliptickým křivkám. Nedíváme se tentokrát na křivky samotné, ale na zobrazení mezi nimi, která zachovají právě onu zajímavou strukturu, o které píšu výše. Taková zobrazení nazveme „isogenie“.
Představme si naše křivky jako ostrovy v moři a mějme dvě pirátské družiny začínající na stejném ostrově. Každá z nich podnikne tajnou spletitou cestu mezi ostrovy (totiž aplikuje svoji tajnou isogenii), na cíli své cesty zakotví. Poté obě zveřejní jakousi pirátskou mapu, která tajně popíše jejich cestu, to je čitelné pouze pirátskýma očima. Druhá družina si mapu přečte a ze svého nového ostrovu podnikne další cestu. Protože jsou piráti tuze rafinovaní, jejich mapy je tak šikovně vedly, že nakonec obě družiny budou opět stavět na stejném ostrově. V jazyce isogenií: máme dvě strany šifrovací výměny, obě začínají se stejnou křivkou. Každá strana si vybere isogenii a tím získá novou křivku. Zároveň však zveřejní malé množství informací o své isogenii. To bude stačit k tomu, že pomocí své nové křivky dokážou obě strany dojít ke stejné křivce, která je sdíleným tajemstvím.
Hrozba kvantových počítačů ve své podstatě znovu oživila snahu o hledání těžko řešitelných matematických problémů. Studium isogenií v kryptografickém světle je záležitostí posledních dvaceti let, z post-kvantových návrhů jsou protokoly na isogeniích založené jedny z nejmladších a zároveň teoreticky nejobtížnějších. Jejich studium a studium kryptografie obecně otevírá brány do velmi hluboké a krásné teorie s nimi spojené, taky ale do úžasné a vítající komunity nadšenců, amatérů i profesionálů, kteří se navzájem podporují a vytváří krásnou atmosféru.
„Účelem mého projektu bylo napsat první (český) úvod do studia isogenií eliptických křivek vhodný pro čtenáře, který s tématem nemá předchozí zkušenosti, později v práci jsem se jim věnoval na mnohem vyšší úrovni. Podstatnější však bylo, že jsem do podrobna studoval užití isogenií v praxi – primárně v kryptografii. V tomto ohledu jsem důkladně vysvětlil princip, chod a bezpečnost dvou prospektivních šifrovacích výměn. Ty jsem taky naprogramoval, aby si práci s nimi mohl čtenář vyzkoušet, přičemž poskytuji (s mým nejlepším vědomím) vůbec první implementaci protokolu SITH.“