Asymetická kryptografie s veřejným klíčem

V této lekci se podíváme na asymetickou kryptografii s veřejným klíčem, která tvoří základ mnoha bezpečných síťových interakcí v současnosti.

Na konci lekce si projdeme:

• Co je asymetická kryptografie s veřejným klíčem
• Využití asymetické kryptografie s veřejným klíčem, včetně výměny klíčů a digitálních podpisů
• Bezpečnost asymetické kryptografie s veřejným klíčem obecně
• Další podrobnosti o algoritmech RSA, DSA a eliptických křivkách a jejich bezpečnosti
• Některé příklady kódu v Pythonu ukazující, jak algoritmy fungují v praxi
• Hrozby pro tyto algoritmy jak od klasických, tak kvantových počítačů

Úvod do asymetické kryptografie s veřejným klíčem

Jak jsme se dozvěděli v předchozí lekci, symetrická kryptografie s tajným klíčem je velmi rychlá a efektivní pro ochranu informací, ale má několik omezení:

1. S rostoucím počtem stran, které chtějí bezpečně vyměňovat informace, počet potřebných klíčů roste kombinatoricky. Neposkytuje žádný mechanismus pro bezpečnou distribuci těchto klíčů mezi odesílateli a příjemci.
2. Neexistuje žádné ustanovení pro nepopiratelnost. Jakákoli strana je schopna dešifrovat nebo šifrovat zprávy bez možnosti zaručit, že zpráva byla přijata nebo odkud pochází.

Řešení obou těchto problémů poskytuje asymetrická kryptografie s veřejným klíčem (AKC), také známá jako kryptografie s veřejným klíčem (PKC), která proto tvoří základní kámen moderní digitální bezpečnosti.

Asymetrická kryptografie s veřejným klíčem (AKC) zahrnuje použití páru klíčů – jednoho veřejného a jednoho soukromého. Veřejný a soukromý klíč jsou kryptograficky propojeny a obvykle jsou generovány současně jako pár klíčů pomocí specializovaného matematického algoritmu. Veřejný klíč, jak naznačuje jeho název, je pak určen k volné distribuci, zatímco soukromý klíč zůstává v tajnosti u strany, která pár klíčů vygenerovala. Bezpečnost komunikace využívající asymetrické páry klíčů je zaručena, pokud soukromý klíč zůstane důvěrný.

Obrázek 1. Asymetrické šifrování s veřejným klíčem

AKC nabízí několik užitečných funkcí, jako jsou:

1. Šifrování a dešifrování pro zajištění důvěrnosti komunikace.
2. Digitální podpisy pro zajištění autenticity, integrity a nepopiratelnosti.
3. Bezpečná výměna klíčů pro usnadnění následného využití symetrických kryptosystémů.

V moderních aplikacích se AKC primárně používá pro digitální podpisy a bezpečnou výměnu klíčů. V této lekci tyto dvě klíčové funkce představíme a pak probereme několik variant kryptografických protokolů pro tyto funkce.

Výměna klíčů pomocí asymetrické kryptografie s veřejným klíčem

Jedním ze základních problémů v kryptografii je bezpečná výměna klíčů. Například pokud dvě strany chtějí používat symetrické šifrování, obě strany potřebují stejný klíč pro šifrování a dešifrování zpráv. Ale jak bezpečně vyměnit klíč? Asymetrická kryptografie s veřejným klíčem to řeší pomocí interaktivních a neinteraktivních mechanismů výměny klíčů.

Interaktivní výměna klíčů

Interaktivní protokol výměny klíčů označuje metodu, při níž dvě strany spolupracují na vytvoření sdíleného tajného klíče přes nezabezpečený komunikační kanál. Tento sdílený tajný klíč lze pak použít pro úlohy symetrického šifrování a dešifrování.

Nejznámějším z takových protokolů je algoritmus Diffie-Hellman (DH), který byl navržen speciálně pro usnadnění výměny klíčů. V tomto protokolu každá strana generuje pár klíčů (veřejný a soukromý) a zveřejňuje svůj veřejný klíč. Pak každá strana použije svůj soukromý klíč a veřejný klíč druhé strany k vygenerování sdíleného tajného klíče. DH využívá principy modulární aritmetiky k zajištění toho, aby obě strany skončily se stejným sdíleným tajemstvím, i když každá strana má přístup pouze k veřejnému klíči druhé strany.

Moderní kryptosystémy založené na kryptografii eliptických křivek (ECC) rozšiřují tento koncept pomocí výměny klíčů Diffie-Hellman na eliptické křivce (ECDH). ECDH funguje podobně jako DH, ale využívá vlastnosti eliptických křivek, což má za výsledek bezpečnější a efektivnější systém.

Obrázek 2. Protokol výměny klíčů

Neinteraktivní výměna klíčů

Na rozdíl od protokolů výměny klíčů jako DH a ECDH, které jsou interaktivní a vyžadují komunikaci tam a zpět k dohodnutí symetrického klíče, AKC také poskytuje neinteraktivní způsoby ustanovení sdíleného tajného klíče. V takových schématech jedna strana generuje pár klíčů (veřejný a soukromý) a sdílí veřejný klíč s druhou stranou. Tato druhá strana pak vygeneruje náhodný symetrický klíč, zašifruje ho přijatým veřejným klíčem a pošle ho zpět první straně. První strana použije svůj soukromý klíč k dešifrování přijaté zprávy, čímž získá sdílený symetrický klíč. Toto schéma je neinteraktivní v tom smyslu, že symetrický klíč je určen jednou stranou a jednoduše bezpečně sdílen druhé straně v zašifrované podobě.

Důležitým aspektem neinteraktivní výměny klíčů je rozdíl v délce v bitech mezi symetrickým klíčem, který strany chtějí vyměnit, a doporučenými velikostmi zpráv v AKC. Moderní symetrické klíče jsou obvykle v rozsahu 128–256 bitů, zatímco asymetrické kryptosystémy jako RSA pracují s velikostmi zpráv kolem 1024–4096 bitů. Proto při použití AKC k přenosu symetrického klíče musí být z bezpečnostních důvodů zakódován do delší zprávy o délce 1024–4096 bitů. Toho lze dosáhnout dvěma přístupy:

• Výměna klíčů pomocí zarovnání (paddingu): V tomto přístupu je nejprve vygenerován kratší (128–256 bitový) symetrický klíč a poté je použito dohodnuté reverzibilní schéma zarovnání, jako je OAEP, pro jeho vložení do delší (1024–4096 bitové) zprávy. Tato delší zpráva je zašifrována pomocí AKC a vysílána jako šifrový text. Příjemce nejprve dešifruje šifrový text a poté odstraní zarovnání, aby získal kratší symetrický klíč.

• Mechanismy zapouzdření klíčů (KEM): Při výměně klíčů pomocí KEM je nejprve vygenerována náhodná, dlouhá (1024–4096 bitová) zpráva v čistém textu, z níž lze extrahovat kratší (128–256 bitový) symetrický klíč pomocí dohodnuté funkce odvozování klíčů (KDF). Delší text v čistém textu je zašifrován pomocí AKC a vysílán příjemci jako šifrový text. Příjemce dekóduje šifrový text pomocí svého soukromého klíče a poté použije KDF k extrakci kratšího (128–256 bitového) symetrického klíče. Populární kryptosystémy jako RSA, se schopností přímo šifrovat data, lze použít k implementaci KEM.

Obrázek 3. Mechanismus zapouzdření klíčů

Digitální podpisy s asymetrickou kryptografií s veřejným klíčem

Digitální podpisy jsou další výkonnou aplikací asymetrické kryptografie s veřejným klíčem. Poskytují autentizaci, integritu a nepopiratelnost, což je umožněno tím, že v AKC entity vlastní jedinečné soukromé klíče. Základní myšlenkou protokolů podpisů je, že odesílatelé bezpečných zpráv budou zprávy navíc digitálně podepisovat pomocí svého jedinečného soukromého klíče. Příjemce pak ověří digitální podpis pomocí veřejného klíče odesílatele. V rámci AKC mohou být digitální podpisy implementovány pomocí algoritmů speciálně navržených pro tento účel nebo pomocí obecných kryptosystémů.

Obrázek 4. Digitální podpisy s asymetrickou kryptografií s veřejným klíčem

Dedikované algoritmy digitálního podpisu

V současnosti je americký federální standard zpracování informací (FIPS) pro digitální podpisy dedikované schéma jednoduše nazvané Algoritmus digitálního podpisu (DSA). Poněkud podobně jako Diffie-Hellmanův protokol používá DSA algebraické vlastnosti modulárního umocňování a multiplikativních inverzních prvků pro generování a ověřování podpisů.

Algoritmus digitálního podpisu na eliptické křivce (ECDSA) je varianta DSA pro ECC poskytující stejnou funkčnost, ale s výrazně kratšími klíči. To vede ke zlepšení efektivity, díky čemuž je oblíbenou volbou pro systémy s omezenými prostředky.

Oba algoritmy DSA a ECDSA budou podrobněji ilustrovány později.

Schémata digitálního podpisu využívající obecné kryptosystémy

Kromě dedikovaných algoritmů lze digitální podpisy generovat také pomocí obecných asymetrických kryptosystémů, jako je RSA.

RSA, které bude podrobně probráno v pozdější části, také využívá modulární multiplikativní inverzní prvky a modulární umocňování jako základní operace, ale kombinuje je v jiném pořadí než DSA. V RSA podepisující typicky vytvoří hash zprávy a pak zašifruje hash svým soukromým klíčem, čímž vytvoří digitální podpis. Jakákoli strana pak může tento podpis ověřit dešifrováním pomocí veřejného klíče podepisujícího a porovnáním s hashovanou zprávou.

Aplikace asymetrické kryptografie s veřejným klíčem

Asymetrická kryptografie s veřejným klíčem je všudypřítomná v moderních aplikacích digitálních technologií. Základní funkce AKC popsané výše tvoří stavební kameny mnoha aplikačních protokolů vyšší úrovně, včetně:

1. Internetová komunikace: Bezpečná komunikace přes internet, jako je HTTPS, se do velké míry opírá o asymetrickou kryptografii s veřejným klíčem. Protokol Transport Layer Security (TLS) a jeho předchůdce Secure Sockets Layer (SSL) používají asymetrickou kryptografii s veřejným klíčem při počátečním handshake procesu k ustanovení symetrického klíče, který se pak používá po zbytek komunikační relace.

2. Autentizace: Asymetrická kryptografie s veřejným klíčem se používá k vytváření digitálních podpisů, které umožňují entitě ověřit digitální dokument nebo zprávu jako pocházející od konkrétního odesílatele. To se používá v mnoha scénářích, od ověřování aktualizací softwaru až po právně závazné digitální smlouvy.

3. Šifrování e-mailů: Protokoly šifrování e-mailů, jako je PGP (Pretty Good Privacy) a jeho open-source alternativa GPG (GNU Privacy Guard), používají asymetrickou kryptografii s veřejným klíčem k zajištění toho, aby obsah e-mailu mohl číst pouze zamýšlený příjemce.

4. Secure shell (SSH): SSH je protokol pro bezpečné vzdálené přihlašování a další bezpečné síťové služby přes nezabezpečenou síť. Používá asymetrickou kryptografii s veřejným klíčem k autentizaci serveru vůči klientovi a volitelně i klienta vůči serveru.

5. VPN (virtuální privátní síť): Asymetrické šifrování s veřejným klíčem se používá k navazování bezpečných připojení v VPN, čímž zajišťuje bezpečnou komunikaci přes veřejné sítě.

6. Blockchain a kryptoměny: Technologie blockchain, včetně Bitcoinu a Etherea, využívají asymetrickou kryptografii s veřejným klíčem. Například vlastnictví Bitcoinu je prokázáno pomocí digitálních podpisů za použití asymetrické kryptografie s veřejným klíčem.

7. Certifikační autority: Asymetrická kryptografie s veřejným klíčem se používá certifikačními autoritami (CA) k vydávání a podepisování digitálních certifikátů, které se používají v TLS komunikaci, podepisování kódu, šifrování e-mailů a dalším. Digitální certifikát váže veřejný klíč ke konkrétní entitě (například osobě nebo serveru).

Obrázek 5. Vydávání a podepisování digitálních certifikátů pomocí asymetrické kryptografie s veřejným klíčem

Bezpečnost asymetrické kryptografie s veřejným klíčem

K umožnění bezpečné asymetrické kryptografie s veřejným klíčem přispívá několik kryptografických konceptů, včetně:

Utajení soukromého klíče: Nejzákladnějším bezpečnostním požadavkem AKC je, aby soukromý klíč zůstal tajný. Protože však soukromý klíč musí být matematicky propojen s veřejným klíčem, utajení soukromého klíče také vyžaduje, aby bylo výpočetně neproveditelné odvodit soukromý klíč ze znalosti veřejného klíče. Schémata generování klíčů v AKC se opírají o výpočetně obtížné matematické problémy, aby tento požadavek splnila.

Funkce padacích dveří: V AKC zahrnují operace šifrování a dešifrování různé komplementární klíče z jednoho páru klíčů. Šifrový text generovaný šifrováním pomocí jednoho z klíčů (například veřejného klíče) musí být nesrozumitelný třetím stranám, přičemž majitel komplementárního klíče (v tomto případě soukromého klíče) ho může snadno dešifrovat. Jinými slovy, šifrování by mělo připomínat jednosměrnou funkci s padacími dveřmi tak, aby třetí strany nemohly invertovat operaci a obnovit čistý text, ale soukromý klíč poskytuje tajné padací dveře umožňující snadnou inverzi. Populární algoritmy AKC používají modulární umocňování k nastavení chování jednosměrné funkce s padacími dveřmi.

Náhodnost: Proces generování klíčů by také měl využívat náhodnost k zajištění toho, aby klíče byly nepředvídatelné, protože jakýkoli vzor nebo předvídatelnost v generování klíčů by mohl být zneužit útočníkem. Náhodnost se také používá pro zarovnání během šifrování k generování sémanticky bezpečných šifrových textů a v rámci schémat digitálního podpisu k produkci jedinečných podpisů i při opakovaném podepisování stejné zprávy. Z tohoto důvodu je používání silných generátorů náhodných čísel důležitou součástí AKC.

Velká velikost klíče: Stejně jako v případě SKC, velké velikosti klíčů zajišťují ochranu před útoky hrubou silou. Protože však velké velikosti klíčů také zvyšují výpočetní náklady procesu šifrování a dešifrování, optimální řešení musí vyvážit bezpečnostní a výkonnostní hlediska. Následující tabulka ukazuje typické velikosti klíčů pro různé protokoly a aplikace asymetrické kryptografie s veřejným klíčem:

Protokol	Typické velikosti klíčů (v bitech)	Aplikace
RSA	1024 (zastaralé), 2048, 3072, 4096	Šifrování, digitální podpisy
DSA	1024 (zastaralé), 2048, 3072	Digitální podpisy
DH	2048, 3072, 4096	Výměna klíčů
ECDH	224, 256, 384, 521	Výměna klíčů
ECDSA	224, 256, 384, 521	Digitální podpisy

Infrastruktura veřejných klíčů: V AKC musí být soukromé klíče uchovávány v tajnosti jejich vlastníky, zatímco veřejné klíče jsou sdíleny. Musí existovat bezpečný mechanismus pro správu a distribuci těchto veřejných klíčů mezi uživateli. Infrastruktura veřejných klíčů (PKI) poskytuje způsob, jak toho dosáhnout pomocí digitálních certifikátů. Digitální certifikát poskytuje důkaz o identitě vlastníka veřejného klíče a je vydáván důvěryhodnou autoritou, jako je certifikační autorita (která je součástí PKI). PKI proto hraje nedílnou roli v bezpečnosti moderních aplikací využívajících AKC tím, že umožňuje správu klíčů ve velkém měřítku (vytvářením, správou, distribucí a odvoláváním digitálních certifikátů).

Bezpečnostní rizika pro asymetickou kryptografii s veřejným klíčem

Jak je uvedeno ve výše uvedené tabulce, moderní asymetrické klíčové algoritmy jako RSA typicky používají mnohem větší velikosti klíčů než běžně používané symetrické klíčové protějšky jako AES-128. Dokonce i protokoly založené na ECC (ECDH a ECDSA) s menšími velikostmi klíčů používají minimum alespoň 224 bitů pro klíče. To zase znamená, že útok hrubou silou zahrnující vyčerpávající prohledávání prostoru soukromých klíčů za účelem identifikace správného klíče je výpočetně neproveditelný v předvídatelné budoucnosti. To platí i v případě nasazení kvantových počítačů pro tento úkol. Útoky na AKC se proto obvykle zaměřují na využívání jiných potenciálních slabostí konkrétních kryptosystémů. Některé dobře zdokumentované režimy útoků cílí na:

1. Algoritmické slabosti pomocí sofistikovaných matematických a výpočetních prostředků k narušení předpokladů obtížnosti používaných k formulaci algoritmů asymetrických klíčů. Bezpečnost RSA například vychází z obtížnosti faktorizace velkých prvočísel a nedávné výpočetní pokroky umožnily úspěšnou faktorizaci 829-bitových klíčů RSA. Proto je 1024-bitové RSA v současnosti zastaralé. Jak bude diskutováno později, primární riziko, které kvantové počítače představují pro AKC, také spadá do této kategorie.

2. Nedokonalou náhodnost, která může vést ke slabosti v procesu generování klíčů. Pokud je například generátor náhodných čísel použitý k vytvoření klíčů vadný a generuje klíče, které nejsou skutečně náhodné, útočník by mohl být schopen klíče předpovědět.

3. Implementační chyby, jako jsou chyby v implementaci kryptografických algoritmů, které neúmyslně odhalují informace o klíčích. Například nesprávné zarovnání může potenciálně odhalit podrobnosti o klíčích.

4. Postranní kanály, které se týkají úniku informací z fyzického systému provádějícího kryptografii. Tyto úniky mohou být ve formě časových informací, spotřeby energie nebo dokonce zvuku, které lze zneužít v tzv. útoku postranním kanálem. Analýza toho, jak dlouho trvá provádění kryptografických operací, by například mohla odhalit počet jedniček v binárním klíči. Tento zdánlivě nevinný únik výrazně zužuje prostor pro hledání, čímž odhaluje potenciální řešení problémů, které se zpočátku zdály nepřekonatelné.

5. Výměnu klíčů zachycením klíčů při jejich výměně, například v rámci útoku man-in-the-middle (MITM). Protokol DH je náchylný k útokům MITM, pokud nejsou začleněny další kroky autentizace.

6. Uložení klíčů zaměřením na krádež klíčů ze špatně zabezpečeného úložiště. To zahrnuje fyzické útoky, jako je manipulace nebo krádež úložných zařízení.

Zabezpečení asymetrických kryptosystémů s veřejným klíčem před různými možnými útoky je proto významným úkolem zahrnujícím matematické, hardwarové, softwarové, logistické a právní aspekty.

RSA

Algoritmus RSA (Rivest-Shamir-Adleman) je jedním z prvních kryptosystémů s veřejným klíčem a je široce používán pro bezpečný přenos dat. Jde o všestranný kryptosystém, který poskytuje operace potřebné pro šifrování, dešifrování, digitální podpisy a výměnu klíčů v rámci společného rámce.

V této části si ukážeme asymetrické šifrování s klíčem (AKC) pomocí RSA na jednoduchých příkladech.

Budeme používat standardní scénář dvou účastníků, Alice a Boba, kteří chtějí bezpečně komunikovat pomocí AKC.

Algoritmus RSA

Základní algoritmus RSA zahrnuje čtyři operace: generování klíčů, distribuci klíčů, šifrování a dešifrování:

1. Generování klíčů:

   Veřejný a soukromý klíč jsou generovány na základě matematických principů prvočísel, kde jejich výpočet je snadný, ale zpětný postup je obtížný.

   Budeme používat tato označení:

   • Veřejný klíč: $(e, n)$
   • Soukromý klíč: $(d, n)$

   Všimni si, že $n$ je společné pro veřejný i soukromý klíč a nazývá se modulus. Budeme ho potřebovat později.

Matematický detail

• Vyber dvě různá prvočísla $p$ a $q$.
  • Vybrána náhodně (z bezpečnostních důvodů).
  • Měla by být přibližně stejně velká, ale lišit se délkou o několik číslic, aby bylo faktorování obtížnější.
  • Prvočísla lze efektivně vybírat pomocí testu prvočíselnosti.
• Vypočítej $n = p*q$.
  • $n$ je modulus pro veřejný i soukromý klíč.
• Vypočítej Eulerovu funkci $φ$$(n) = (p-1)*(q-1)$.
  • Eulerova funkce má zůstat tajná a zpravidla se zahodí po generování klíčů.
• Zvol celé číslo $e$ tak, aby $1 < e <$$φ$$(n)$ a $gcd$$(e,$$φ$$(n)) = 1$.
  • tedy $e$ a $φ$$(n)$ musí být nesoudělná.
  • Číslo $e$ tvoří exponent veřejného klíče a obvykle se volí jako malé číslo pro výpočetní efektivitu.
  • Často se používá prvočíslo $65537 = 2^{16} + 1$.
  • Vypočítej $d$ tak, aby splňovalo kongruenci $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • To znamená, že $d$ je multiplikativní inverz čísla $e$ modulo $φ$$(n)$.
    • To lze efektivněji vypočítat pomocí rozšířeného Euklidova algoritmu.
    • Toto číslo $d$ je exponent soukromého klíče.
• Veřejný klíč tvoří $(e, n)$ a soukromý klíč je $(d, n)$.

2. Distribuce klíčů:

   • Veřejný klíč $(e, n)$ je zveřejněn pro ty, kdo chtějí poslat zprávu.
   • Soukromý klíč $(d, n)$ zůstává tajný.

3. Šifrování:

   • Alice chce poslat zprávu $M$ Bobovi. V tomto případě jde o jednoduché celé číslo.
   • Alice použije Bobův veřejný klíč $(e, n)$ k zašifrování zprávy na šifrovaný text $C$.

   Matematický detail

   • $M$ je celé číslo $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, kde $C$ je šifrovaný text.

4. Dešifrování:

   • Bob obdrží šifrovaný text $C$.
   • Bob použije svůj soukromý klíč $(d, n)$ k dešifrování zprávy zpět na zprávu $M$.

   Matematický detail

   • $M ≡ C^d (mod n)$.

Toto je základní přehled RSA. V praxi se na prostý text $M$ před šifrováním aplikují sofistikovanější schémata paddingu, aby se zajistilo, že stejné prosté texty vedou k různým šifrovaným textům. To brání řadě možných útoků na naivní implementace RSA a umožňuje sémantické zabezpečení.

Ilustrace RSA v Pythonu

V následujících buňkách kódu ilustrujeme jednoduchý příklad algoritmu RSA s použitím malých celých čísel a poté demonstrujeme praktické aplikace distribuce klíčů a digitálních podpisů pomocí Pythonových knihoven implementujících RSA.

poznámka

Poznámka: V této části ukážeme matematické výpočty podrobně jako součást kódu Python.

Generování klíčů RSA

Projdeme si jednoduchý příklad algoritmu RSA s použitím malých prvočísel.

Budeme potřebovat umět vypočítat největší společný dělitel dvou celých čísel, protože ho budeme potřebovat k testování, zda jsou dvě celá čísla nesoudělná.

Vysvětlíme jeden jednoduchý způsob, jak to vypočítat, ale pro větší celá čísla je mnohem efektivnější použít funkci math.gcd v Pythonu.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

První fází pracovního postupu RSA je generování klíčů. To začíná výběrem dvou prvočísel, která musí zůstat tajná pro entitu generující klíče.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Dále se vypočítá modulus $n$, který je prostým součinem dvou zvolených prvočísel. Tento modulus bude zveřejněn jako součást veřejného klíče.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Dále se vypočítá Eulerova funkce fi $\varphi(n)$, která je potřeba pro operaci modulárního multiplikativního inverzu používanou k určení klíčů v RSA. Hodnota $phi$ je rovněž tajná a zpravidla se zahodí po generování klíčů.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Nyní jsme připraveni vypočítat veřejný a soukromý klíč. V RSA je každý z nich specifikován dvojicí dvou celých čísel. První prvek každé dvojice je odlišné celé číslo a druhý prvek je modulus $n$, který je společný pro oba klíče.

První prvek veřejného klíče může být libovolné celé číslo větší než 1, které je nesoudělné s hodnotou $phi$. Dvě celá čísla jsou nesoudělná, pokud je jejich největší společný dělitel roven 1. Použijeme tedy funkci math.gcd k nalezení celého čísla $e$ nesoudělného s hodnotou $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Soukromý klíč vyžaduje celé číslo $d$, které je multiplikativním inverzem čísla $e$ modulo $phi$; to znamená, že splňuje kongruenci $d*e\equiv 1 \pmod{\varphi(n)}$. Pro tuto jednoduchou ilustraci s malými celými čísly stačí procházet kladná celá čísla a hledat vhodné $d$. V reálném prostředí se pro tento účel používá výpočetně efektivní rozšířený Euklidův algoritmus.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Nyní sestavíme dvojice $(e, n), (d, n)$, které tvoří veřejný a soukromý klíč. Veřejný klíč se pak zveřejní, zatímco soukromý klíč zůstane tajný.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Šifrování a dešifrování v RSA využívají operaci modulárního umocňování. Veřejný a soukromý klíč jsou navíc komplementární — každý z nich lze použít k zašifrování zprávy, kterou pak ten druhý dokáže dešifrovat.

Zde ilustrujeme případ, kdy se veřejný klíč $(e,n)$ používá pro šifrování a soukromý klíč $(d, n)$ pro dešifrování, a to definováním Pythonové funkce pro každou operaci.

Poté zašifrujeme a dešifrujeme celou číselnou zprávu $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Zatímco malá celá čísla použitá výše jsou užitečná pro snadné objasnění klíčových myšlenek algoritmu RSA, v reálných aplikacích RSA vyžaduje použití velmi velkých celých čísel. Například 2048bitové RSA využívá modulus $n$ délky 2048 bitů, jehož desetinné ekvivalenty jsou řádově 10$^{616}$. Tato skutečně obrovská čísla jsou nezbytná pro praktickou bezpečnost RSA.

Výměna symetrického klíče pomocí RSA

Jak jsme probrali dříve, AKC umožňuje dvěma stranám, které chtějí komunikovat, bezpečně ustanovit sdílené tajemství, které lze použít například jako tajný klíč pro následné symetrické šifrování objemného prostého textu.

Uvažujme následující scénář. Alice a Bob chtějí použít SKC k šifrování a dešifrování zpráv. Aby však tento proces mohl začít, musí se dohodnout na společném tajném klíči. Jednou z možností je, aby jedna strana — řekněme Alice — vygenerovala tajný klíč a bezpečně ho předala Bobovi. K dosažení tohoto bezpečného přenosu se Alice rozhodne použít RSA jako mechanismus zapouzdření klíčů (KEM).

Postup zahrnuje tyto kroky:

• Nejprve Alice vygeneruje náhodný symetrický klíč, který chce sdílet s Bobem.
• Poté Bob vygeneruje asymetrický pár klíčů a zveřejní svůj veřejný klíč na vhodném kanálu.
• Alice pak použije Bobův veřejný klíč k zašifrování symetrického klíče, čímž ho zapouzdří do šifrovaného textu.
• Alice poté rozešle šifrovaný text přes spolehlivý, ale ne nutně bezpečný kanál.
• Nakonec Bob obdrží šifrovaný text a dešifruje ho pomocí svého soukromého klíče. Tím získá přístup k symetrickému klíči, který vygenerovala Alice.

Obrázek 1. Výměna symetrického klíče pomocí RSA

Příklad výměny klíčů s paddingem v Pythonu

Praktický pracovní postup využívající RSA pro neinteraktivní výměnu klíčů na základě paddingu je nyní ilustrován pomocí Pythonové knihovny cryptography.

Importujeme potřebné moduly z Pythonové knihovny cryptography. V případě potřeby lze tuto knihovnu nainstalovat příkazem pip install cryptography.

Alice poté vygeneruje náhodný tajný klíč, který chce předat Bobovi.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Pomocí modulu rsa z knihovny cryptography Bob vygeneruje pár klíčů a poté zveřejní svůj veřejný klíč. Kdokoli může veřejný klíč zachytit a přečíst si veřejná čísla $(e,n)$, která tvoří klíč.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

V tuto chvíli předpokládáme, že Alice obdržela veřejný klíč, který Bob zveřejnil. Alicin symmetric_key výše lze nyní zašifrovat pomocí Bobova veřejného klíče a vytvořit tak šifrovaný text. V reálném prostředí Alice použije také další metody paddingu, jako je OAEP, aby zajistila sémantické zabezpečení své komunikace s Bobem.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice poté rozešle šifrovaný text přes otevřený kanál s jistotou, že ho bude moci dešifrovat pouze Bob s odpovídajícím soukromým klíčem. Předpokládáme, že Bob obdržel šifrovaný text a může ho nyní dešifrovat pomocí svého důvěrného soukromého klíče.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

V tuto chvíli mají Alice i Bob přístup k tajnému symetrickému klíči, který mohou použít pro aplikace SKC.

Simulace mechanismu zapouzdření klíčů (KEM) pomocí RSA v Pythonu

V následujícím pracovním postupu ilustrujeme použití RSA k simulaci mechanismu zapouzdření klíčů (KEM), při němž je bezpečně vyměněna dostatečně dlouhá náhodná tajná zpráva a následně převedena na sdílené tajemství odpovídající délky pomocí KDF.

Opět chtějí Alice a Bob neinteraktivně ustanovit sdílené tajemství a Alice je ta strana, která rozhoduje o tom, jaké tajemství použít.

Začneme importem potřebných Pythonových knihoven.

Bob poté vygeneruje svůj pár klíčů RSA a zveřejní svůj veřejný klíč.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice nejprve vygeneruje dlouhé náhodné tajemství, z něhož bude nakonec odvozeno sdílené tajemství. V čistém KEM bude tímto dlouhým tajemstvím náhodný prvek algebraické struktury, na níž je kryptosystém postaven. V případě 2048bitového RSA by to bylo náhodné celé číslo modulo 2048bitový RSA modulus. Takový čistý KEM nevyžaduje další padding, ale v tomto příkladu pouze simulujeme KEM pomocí RSA a knihovna cryptography vyžaduje použití paddingu při šifrování s RSA. Proto použijeme poněkud kratší dlouhé tajemství, které je však stále mnohem delší než standardní 256bitový klíč AES.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Alice poté zašifruje dlouhé tajemství pomocí Bobova veřejného klíče a zašifrované tajemství je předáno Bobovi.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob dešifruje zašifrované tajemství obdržené od Alice pomocí svého soukromého klíče.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Nakonec Alice i Bob samostatně aplikují dohodnutou funkci odvozování klíčů (KDF) na dlouhé tajemství, aby odvodili symetrický klíč.

Všimni si, že postup zahrnuje hashovací protokol a použití náhodné soli, což zajišťuje jedinečnost a nepředvídatelnost sdíleného symetrického klíče v případě, že by bylo dlouhé tajemství znovu použito (nedoporučuje se). Samotná sůl však nemusí být tajná — jakmile ji Alice náhodně vygeneruje, může ji Bobovi sdělit spolu se zašifrovaným dlouhým tajemstvím.

Proto předpokládáme, že Alice i Bob mají přístup ke stejné náhodné soli.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Digitální podpisy pomocí RSA

Nyní rozšíříme výše popsaný scénář důvěrné komunikace mezi Alice a Bobem o validaci pomocí digitálního podpisu.

Jako dříve Alice důvěrně pošle Bobovi zprávu se zapouzdřeným symetrickým klíčem, ale navíc zprávu digitálně podepíše, aby Bob po jejím obdržení mohl ověřit, že ji odeslala Alice a že obsah zprávy nebyl při přenosu pozměněn.

Obecněji je žádoucí umožnit validaci bez narušení důvěrnosti, přičemž jakákoli zainteresovaná strana je schopna ověřit integritu, autenticitu a neodmítnutelnost (non-repudiation) dané komunikace, i když tato strana nemá přístup k samotnému prostému textu zprávy.

Budeme uvažovat toto obecné nastavení, které zahrnuje následující kroky:

• Nejprve Bob i Alice zveřejní své veřejné klíče přes otevřený kanál.
• Alice poté zašifruje prostý text pomocí Bobova veřejného klíče a vytvoří šifrovaný text.
• Alice dále vytvoří hash šifrovaného textu pomocí hashovací funkce a výsledný hashovaný šifrovaný text dále zašifruje svým soukromým klíčem. Tento zašifrovaný hash je podpisem.
• Alice poté přenese šifrovaný text i podpis přes otevřený kanál.
• Bob použije Alicin veřejný klíč k dešifrování podpisu, čímž odhalí hashovaný šifrovaný text.
• Protože má Bob přístup i k samotnému šifrovanému textu, použije stejnou hashovací funkci jako Alice a vytvoří druhou instanci hashovaného šifrovaného textu. Pokud se tato shoduje s tou získanou dešifrováním Alicina podpisu, je zpráva validována, přestože samotný šifrovaný text ještě nebyl dešifrován.
• Nakonec Bob, poté co ověřil zprávu, dešifruje šifrovaný text pomocí svého soukromého klíče.

Obrázek 2. Digitální podpisy pomocí RSA

Tento pracovní postup pro digitální podpis je ilustrován níže.

Opět importujeme některé užitečné moduly z knihovny cryptography. Stejně jako dříve chce Alice bezpečně poslat symetrický klíč Bobovi, ale chce ho také digitálně podepsat. V tomto případě potřebujeme veřejné klíče od Alice i od Boba. Proto je prvním krokem, aby Alice i Bob vytvořili vlastní pár klíčů pomocí RSA a zveřejnili svůj veřejný klíč.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

V dalším kroku Alice použije Bobův veřejný klíč k zašifrování symetrického klíče a připraví šifrovaný text, jako tomu bylo dříve.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

V této fázi, místo aby Alice pouze rozeslala šifrovaný text, chce k němu připojit digitální podpis, aby mohla Bobovi dokázat, že je odesílatelem zprávy. To se provede ve dvou krocích:

1. Vytvoř hash šifrovaného textu pomocí hashovacího algoritmu.
2. Zašifruj hash pomocí Alicina soukromého klíče — to je podpis.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice poté rozešle šifrovaný text a podpis přes síť, aby je Bob mohl zachytit.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Na Bobově straně je prvním úkolem ověřit integritu a autenticitu šifrovaného textu. K tomu Bob vytvoří hash obdrženého šifrovaného textu pomocí stejného hashovacího algoritmu, který použila Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Bob poté dešifruje obdržený podpis pomocí Alicina veřejného klíče. Protože Alice použila svůj soukromý klíč k vytvoření podpisu, Bob ho může dešifrovat pomocí Alicina veřejného klíče. Dešifrovaný podpis není nic jiného než hash šifrovaného textu vytvořeného na Alicině straně. Pokud hash vytvořený Bobem odpovídá dešifrovanému podpisu, Bob ověřil, že šifrovaný text, který obdržel, nebyl pozměněn, a že to byla Alice, kdo šifrovaný text podepsal.

V kódu Python níže jsou tyto operace kombinovány do užitečné pomocné funkce verify poskytované objektem přidruženým k Alicinu veřejnému klíči.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Poté, co Bob ověřil integritu a autenticitu obdrženého šifrovaného textu, může ho dešifrovat pomocí svého soukromého klíče, protože Alice vytvořila šifrovaný text pomocí Bobova veřejného klíče.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

Ve výše popsaném scénáři digitálního podpisu může kdokoli — nejen Bob — ověřit, že Alice je odesílatelem šifrovaného textu, protože všichni mají přístup k Alicinu veřejnému klíči, šifrovanému textu a digitálnímu podpisu. Navíc poté, co Alice odeslala šifrovaný text a podpis, ho nemůže později popřít, protože podpis lze dešifrovat na smysluplný hash pouze pomocí jejího veřejného klíče. To zajišťuje neodmítnutelnost (non-repudiation).

Tím, že kryptografie s veřejným klíčem umožňuje bezpečnou distribuci klíčů a podporuje neodmítnutelnost, poskytuje pevný základ pro bezpečnou digitální komunikaci.

Prolomení RSA

Užitečnost a bezpečnost algoritmu RSA popsaného výše spočívá na dvou matematických předpokladech:

1. Nalezení modulárního multiplikativního inverzu $d$ při přístupu pouze k $(e, n)$ je výpočetně neproveditelné.

2. V kontextu RSA se operace modulárního umocňování chová jako jednosměrná trapdoor funkce. Při šifrování produkuje šifrový text, který je nerozluštitelný, a bez přístupu k soukromému klíči je invertování operace za účelem obnovení prostého textu ze šifrového textu neproveditelné. Avšak s přístupem k soukromému klíči, který funguje jako trapdoor, lze šifrový text snadno dešifrovat.

Nejznámější útok na algoritmus RSA se snaží podkopat předpoklad 1 tím, že efektivně obnoví soukromé klíčové číslo $d$ prostřednictvím faktorizace modulu $n$. Jak bude ukázáno níže, je snadné obnovit $d$, pokud má člověk přístup k prvočíselným faktorům $p$ a $q$ čísla $n$ nebo k totientovi $φ$$(n)$. Připomeňme, že $p$, $q$ a $φ$$(n)$ jsou při generování klíčů udržovány v tajnosti a po té zahozeny. Třetí strana, která tyto informace získá pomocí klasického nebo kvantového počítače, v podstatě odhalí soukromý klíč a prolomí RSA. Prvočíselná faktorizace je tedy klíčovým výpočetním primitivem nezbytným pro prolomení RSA.

Klasické počítače a RSA

Prvočíselná faktorizace velkých celých čísel je na klasických počítačích známa jako problém s super-polynomiálním nebo subexponenciálním škálováním. Nejznámější klasický algoritmus pro faktorizaci celých čísel větších než $10^{100}$ je obecné síto číselného tělesa (GNFS)

Matematický detail

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

jako funkce celého čísla $n$, které má být faktorizováno.

Toto škálování je super-polynomiální v počtu bitů potřebných k reprezentaci $n$.

Proto je prvočíselná faktorizace na klasických počítačích považována za neefektivní.

V současnosti jsou největší celá čísla faktorizovaná na klasickém hardware v rozsahu 829 bitů nebo 250 desetinných číslic. S ohledem na exponenciální růst výpočetního výkonu klasických počítačů v posledních několika desetiletích již 1024-bitové RSA není v krátkodobém horizontu považováno za bezpečné a je zastaralé. Nicméně v dohledné budoucnosti je faktorizace 2048-bitových celých čísel, jejichž velikost se pohybuje v rozsahu $10^{617}$, v současnosti na klasických systémech považována za neproveditelnou, což naznačuje trvalou životaschopnost. Příchod kvantových počítačů však toto hodnocení ruší.

Shorův kvantový algoritmus a RSA

Pravděpodobně nejznámějším kvantovým algoritmem dnes je Shorův algoritmus pro nalezení prvočíselných faktorů celých čísel. Když ho Peter Shor představil v roce 1994, byl uznán jako první kvantový algoritmus nabízející super-polynomiální zrychlení oproti klasickým algoritmům u problému velké praktické důležitosti, konkrétně prvočíselné faktorizace.

Shorův algoritmus dokáže faktorizovat prvočísla s $O(n^2)$, kde $n$ je počet bitů.

Matematické vysvětlení Shorova algoritmu

V kontextu RSA funguje Shorův algoritmus využitím periodicity modulární exponenciální funkce $f(x) = a^x (mod~n)$ a poskytuje kvantový primitiv pro hledání periody, který umožňuje efektivní prvočíselnou faktorizaci modulu $n$.

Zjednodušený přehled Shorova celkového schématu pro prolomení RSA je následující:

1. Při zadaném modulu $n$, který je zveřejněn jako součást veřejného klíče, zvolíme číslo $a$ nesoudělné s $n$, tedy $gcd(a,n) = 1$. Protože víme, že $n = p*q$ má přesně dva prvočíselné faktory $(p, q)$, téměř libovolné číslo menší než $n$, které náhodně vybereme, bude pravděpodobně nesoudělné s $n$.

2. Po zvolení $a$ najdeme exponent $r$ takový, že $a^r \equiv 1 (mod~n)$. To implikuje $a^r - 1 \equiv 0 (mod~n)$. Existence exponentu $r$ takového, že výše uvedená kongruence platí, je zaručena vlastností periodicity modulárního umocňování.

3. Pokud je $r$ sudé, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ pro nějaké celé číslo $\gamma$. Levá strana tohoto posledního rovnice musí obsahovat $p$ a $q$ jako dva ze svých prvočíselných faktorů, protože pravá strana je obsahuje. Pokud je $r$ liché, vrátíme se ke kroku 1 a zkusíme jiné $a$.

4. Použijeme rozšířený Eukleidův algoritmus pro nalezení $gcd((a^{r/2} - 1), n)$ nebo $gcd((a^{r/2} + 1), n)$. Vypočtený NSD s největší pravděpodobností identifikuje jeden z prvočíselných faktorů $p$ nebo $q$. Vydělíme $n$ tímto prvočíselným faktorem a získáme druhý.

5. Jakmile jsou $p, q$ známé, použijeme kroky z původního algoritmu RSA pro rekonstrukci totientu $\phi(n)$ a generování soukromého klíčového čísla $d$ jako modulárního inverzu známého veřejného klíčového čísla $e$.

V srpnu 2023 Oded Regev zveřejnil vylepšení Shorova originálního algoritmu pomocí vícerozměrného přístupu, výsledkem čehož je $O(n^{1.5})$. Výzkum v této oblasti pokračuje, včetně práce Ragavana a Vaikuntanatana, která může zlepšit čas, náklady nebo počet potřebných qubitů. I když nemůžeme říci, kdy se spuštění takových algoritmů proti reálnému RSA šifrování stane skutečně proveditelným, je to stále blíže.

Příklad v Pythonu demonstrující prolomení RSA šifrování

V následujících buňkách kódu ukazujeme příklad nalezení soukromého klíče ze samotného veřejného klíče. Využívá to hrubou silou klasický výpočet, ale ukazuje, jak by mohl být použit Shorův algoritmus — včetně velkých klíčů.

poznámka

V této části ukážeme matematické výpočty podrobně jako součást kódu v Pythonu

V příkladu máme veřejný klíč $(5, 247)$ a obnovíme soukromý klíč.

Krok 1: Prvním krokem je zvolit číslo nesoudělné s 247. Téměř libovolné číslo, které uhodneme, bude fungovat. Zvolme 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Krok 2: Dále musíme najít periodu $r$ takovou, že $6^r \equiv 1 (mod~247)$. V tomto příkladu vypočteme $r$ klasicky hrubou silou, ale mohli bychom také použít Shorův algoritmus na kvantovém počítači pomocí Qiskitu.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Krok 3: Protože perioda $r = 36$ je sudá, můžeme vypočítat $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Krok 4: Najdeme NSD jednoho z těchto faktorů s $n$. Vydělíme $n$ již nalezeným prvočíselným faktorem a získáme druhý prvočíselný faktor.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Krok 5: Poté, co jsme obnovili prvočíselné faktory $n = 247$ jako $p_{found}=13$ a $q_{found}=19$, vypočítáme totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

Soukromý klíč je modulárním inverzem veřejného klíčového čísla $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

Ve výše uvedeném schématu je krok 2 klíčovou operací hledání periody, pro kterou Shorův algoritmus využívá dva základní kvantové primitivy, konkrétně kvantovou Fourierovu transformaci a kvantový odhad fáze. Podrobné vysvětlení kvantových aspektů Shorova algoritmu najdeš v lekci Odhad fáze a faktorizace v kurzu Fundamentals of Quantum Algorithms. Kroky 1 a 3 až 5 zahrnují relativně nenákladné operace, které lze snadno provést na klasických počítačích.

Volitelně si tu je podrobný vizuální průvodce implementací Shorova algoritmu.

Na kvantových počítačích může Shorův algoritmus vykazovat polylogaritmické škálování příznivé jako $O((log~n)^2 (log~log~n))$ z hlediska modulu $n$, nebo polynomiální škálování z hlediska počtu bitů potřebných k reprezentaci $n$. To je super-polynomiální zrychlení ve srovnání s klasickým algoritmem GNFS.

Nedávné odhady zdrojů naznačují, že na základě určitých předpokladů ohledně konfigurace hardware bude k prolomení 2048-bitového RSA pomocí Shorova algoritmu nutných několik desítek tisíc až několik milionů qubitů. Není nepředstavitelné, že kvantové počítače s několika desítkami tisíc qubitů budou k dispozici v průběhu příštích několika let, čímž se dolní konec odhadu zdrojů stane dostupným.

Diffie-Hellmanův výměna klíčů a algoritmus digitálního podpisu

V předchozí části jsme diskutovali o kryptosystému RSA, jehož bezpečnost je založena na výpočetní obtížnosti prvočíselné faktorizace. Zde budeme diskutovat o dvou populárních protokolech asymetrické kryptografie, výměně klíčů Diffie-Hellman (DH) a Algoritmu digitálního podpisu (DSA), oba jsou založeny na jiném matematickém problému, konkrétně na problému diskrétního logaritmu (DLP).

Problém diskrétního logaritmu

V následující rovnici musíme najít $a$ ze samotných $e$, $M$, $c$

$a^e$ $mod$ $M = c$

Věří se, že to je na klasických počítačích obtížné kvůli použití modulární aritmetiky, a proto je to dobrým matematickým základem pro šifrovací algoritmus.

Toto je známé jako problém diskrétního logaritmu (DLP).

Matematické podrobnosti problému diskrétního logaritmu

DLP je typicky formulován v kontextu cyklických grup a je formulován následovně.

Uvažujeme cyklickou grupu $G$ generovanou prvkem grupy $g \in G$ a daným libovolným prvkem $h \in G$, najdeme celé číslo $k$ takové, že $h = g^{k}$.

Zde celé číslo $k \equiv log_{g}h$ je diskrétní logaritmus. Cyklická vlastnost $G$ zaručuje, že pro každé $h$ existuje platné celé číslo $k$.

Pro kryptografii se ukazuje jako užitečný DLP na multiplikativní grupě celých čísel modulo prvočíslo $p$, označované $(\mathbb{Z}_p)^{\times}$. Prvky $(\mathbb{Z}_p)^{\times}$ jsou třídy kongruence označené celými čísly modulo $p$, která jsou nesoudělná s $p$.

Například:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{a}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Operace násobení $(\times)$ na těchto grupách je jednoduše obyčejné celočíselné násobení následované redukcí modulo $p$ a umocňování celým číslem $k$ je jen opakované násobení $k$-krát a redukce modulo $p$.

Pojďme ilustrovat instanci DLP na $(\mathbb{Z}_7)^{\times}$.

Tato multiplikativní grupa má dva generátory ${[3],[5]}$, také známé jako primitivní kořeny. Budeme používat $[5]$ jako generátor; tedy generovat každý prvek $(\mathbb{Z}_7)^{\times}$ pomocí po sobě jdoucích celočíselných mocnin 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Vidíme, že v modulární aritmetice modulo 7 dává umocňování 5 na po sobě jdoucí celočíselné mocniny každý prvek $(\mathbb{Z}_7)^{\times}$ přesně jednou, než se cyklus opakuje donekonečna s periodou $p-1 =6$.

DLP na $(\mathbb{Z}_7)^{\times}$ s generátorem [5] je tedy:

$\mathrm{Dáno}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, najdi~} k \mathrm{~takové, že~} 5^{k} \equiv h~(mod~7)$.

Z výstupu výše uvedené buňky Pythonu vidíme, že:

$h = 2 \implies k=4 \mathrm{~nebo~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~nebo~} 3 = log_5(6) (mod~7)$

V běžné aritmetice reálných čísel je umocňování monotónní funkce a nalezení logaritmu libovolného čísla k libovolnému základu je výpočetně snadné. Naproti tomu, jak je patrné z jednoduchého příkladu $(\mathbb{Z}_7)^{\times}$ výše, modulární umocňování je nemonotónní, a i když je periodické s periodou $p-1$, je jinak velmi netriviální. Výpočet jeho inverzu, diskrétního logaritmu, se proto ukáže jako neefektivní pro velká $p$ na klasických počítačích.

Toto pozorování je základem jak Diffie-Hellmanovy (DH) výměny klíčů, tak Algoritmu digitálního podpisu (DSA), o nichž se diskutuje v další části.

DLP lze rozšířit na cyklické podgrupy takto:

• Uvažujme $(\mathbb{Z}_p)^{\times}$ definované výše a prvek $g \in (\mathbb{Z}_p)^{\times}$ prvočíselného řádu $r$, tedy $g^r \equiv 1 (~mod~p)$.
• Množina celočíselných mocnin $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ je cyklická podgrupa $(\mathbb{Z}_p)^{\times}$ s řádem grupy $r$.
• DLP lze specifikovat na $\langle g \rangle$ zvolením $h \in \\langle g \rangle$ a hledáním $1 \le a \le r$ takového, že $g^a~(mod~p) = h$

Diffie-Hellmanova výměna klíčů

V roce 1976 Whitfield Diffie a Martin Hellman navrhli protokol výměny klíčů umožňující vytvoření sdíleného tajného klíče přes nezabezpečené komunikační kanály. Tajný klíč mohl být poté použit stranami, které ho sdílely, pro symetrické šifrování. Algoritmus se spoléhá na DLP.

Obrázek 1. Diffie-Hellmanova výměna klíčů

Matematické podrobnosti Diffie-Hellmanovy výměny klíčů

S Alicí a Bobem jako dvěma komunikujícími stranami funguje protokol takto:

• Nejprve se Alice a Bob dohodnou na velkém prvočísle $p$ a primitivním kořeni nebo generátoru $a$.
• Poté Alice náhodně zvolí tajný exponent $k_A$ s $1 \le k_A \le p-2$ a vypočítá $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ jsou Alicin soukromý a veřejný klíč.
• Dále Bob náhodně zvolí tajný exponent $k_B$ s $1 \le k_B \le p-2$ a vypočítá $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ jsou Bobův soukromý a veřejný klíč.
• Poté Alice pošle Bobovi $h_A$ a Bob pošle Alici $h_B$ přes spolehlivý, ale ne nutně bezpečný kanál.
• Alice pak použije přijatý $h_B$ k výpočtu sdíleného tajného klíče $\kappa = h_B^{k_A}~(mod~p)$.
• Nakonec Bob mezitím použije přijatý $h_A$ k výpočtu sdíleného tajného klíče $\kappa = h_A^{k_B}~(mod~p)$.

S tímto protokolem:

• Alice a Bob mají zaručeno, že skončí se stejným tajným klíčem $\kappa$, protože $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• Třetí strana, která zachytí $h_A$ nebo $h_B$, nemůže sestavit tajný klíč $\kappa$, protože nemá přístup k $k_B$ nebo $k_A$.
• Extrahování $k_A$ nebo $k_B$ pomocí veřejných informací $a$, $p$, $h_A$ a $h_B$ je výpočetně obtížné, neboť je ekvivalentní řešení DLP na $(\mathbb{Z}_p)^{\times}$.

Ilustrace protokolu Diffie-Hellman v Pythonu

Podívejme se na jednoduchý příklad protokolu DH v Pythonu s použitím malých prvočísel:

poznámka

V této části ukážeme matematické výpočty podrobně jako součást kódu v Pythonu

Krok 1: Alice a Bob se dohodnou na prvočísle $p$ a primitivním kořeni $a$. Zvolme $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Kroky 2, 3: Alice zvolí tajný exponent $k_A$ a vypočítá $h_A = a^{k_A}~(mod~p)$. Podobně Bob zvolí tajný exponent $k_B$ a vypočítá $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Krok 4: Obě strany zveřejní své veřejné klíče $h_A$ a $h_B$.

Kroky 5, 6: Každá strana kombinuje svůj soukromý klíč s veřejným klíčem druhé strany a vytvoří sdílený tajný klíč.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice a Bob nyní mohou používat sdílený tajný klíč pro symetrické šifrování.

Bezpečnost Diffie-Hellmanovy výměny klíčů

Jak bylo uvedeno výše, bezpečnost DH závisí na výpočetní obtížnosti řešení DLP s velkými prvočísly $p$. V typických aplikacích NIST doporučuje 2048- nebo 3072-bitová prvočísla pro DH výměnu klíčů, což je považováno za dostatečně bezpečné proti pokusům o řešení DLP pomocí klasických počítačů.

Útok man-in-the-middle (MITM): Skutečnost, že DH je interaktivní schéma, kde sdílený tajný klíč závisí na kombinaci soukromého klíče jedné strany s veřejným klíčem druhé strany, ho činí zranitelným vůči tzv. útoku man-in-the-middle (MITM).

Matematické podrobnosti bezpečnosti DH a útoků MITM

V tomto scénáři třetí strana — řekněme Eva — zachytí veřejné klíče $h_A, h_B$ během přenosu a nahradí svým vlastním veřejným klíčem $h_E$ každý z $h_A$ a $h_B$ před jejich přeposláním Bobovi a Alici.

Místo použití $h_B$ k vytvoření svého sdíleného tajného klíče pak Alice použije $h_E$, zatímco si bude myslet, že používá Bobův veřejný klíč. Podobně místo použití $h_A$ k vytvoření svého sdíleného tajného klíče Bob použije $h_E$, zatímco si bude myslet, že používá Alicin veřejný klíč.

Protože $h_E$ bylo použito k vytvoření Alicina (Bobova) sdíleného tajného klíče, prostý text zašifrovaný Alicí (Bobem) může Eva dešifrovat.

DH výměna klíčů je proto typicky používána ve spojení s algoritmem digitálního podpisu, aby bylo zajištěno, že každá strana použije pro vytvoření svého sdíleného tajného klíče ověřený veřejný klíč.

Algoritmus digitálního podpisu (DSA)

I když generické kryptosystémy jako RSA poskytují funkci digitálního podpisu, v roce 1994 NIST přijal specializované schéma podpisu založené na modulárním umocňování a problému diskrétního logaritmu jako federální standard pro digitální podpisy. Toto schéma, které se jednoduše stalo známým jako Algoritmus digitálního podpisu (DSA), zahrnuje čtyři odlišné fáze:

1. Generování klíčů:

   DSA klíče jsou generovány z:

   • 2 prvočísel, která splňují určitá pravidla
     • $p$ — typicky 256 bitů (tuto délku budeme nazývat $N$)
     • $q$ — typicky 3072 bitů (tuto délku budeme nazývat $L$)
   • Kryptografické hashovací funkce, která převede řetězce délky $L$ na $N$
   • Dalšího parametru $g$ (viz podrobnosti níže)

   Z toho vybereme náhodné číslo $x$ jako soukromý klíč a jsme schopni vypočítat veřejný klíč $y$

   Matematické podrobnosti generování klíčů

   • Generování parametrů: Matematicky DSA zahrnuje cyklickou podgrupu $(\mathbb{Z}_p)^{\times}$ generovanou prvkem $g$ prvočíselného řádu q < p. Prvním krokem v DSA je proto výběr dvou prvočísel p, q pro nastavení nezbytných matematických struktur.

     • Zvolíme $N$-bitové prvočíslo $q$.
     • Zvolíme $L$-bitové prvočíslo $p$ takové, že $p-1$ je násobkem $q$. Volba $p$ specifikuje grupu $(\mathbb{Z}_p)^{\times}$
     • Náhodně zvolíme celé číslo $1 < h < p-1$ a vypočítáme $g = h^{(p-1)/q}~mod~p$. Pokud $g=1$, což se stává zřídka, zkusíme jiné h.
     • Ověříme, že $g^q~mod~p = 1$. g je tedy generátor cyklické podgrupy $\langle g \rangle$ z $(\mathbb{Z}_p)^{\times}$ prvočíselného řádu q.

     Parametry $(q, p, g)$ specifikují instanci algoritmu a jsou veřejné informace. Typicky $N \sim 256$ a $L \sim 3072$ v realistických aplikacích.

     Protokol také vyžaduje kryptografickou hashovací funkci $H : \{0,1\}^L \rightarrow \{0, 1\}^N$, která mapuje binární $L$-bitové řetězce na $N$-bitové řetězce, například SHA-256.

   • Generování páru klíčů: Podepisující musí na svém konci vygenerovat pár klíčů.

     • Zvolíme náhodné tajné celé číslo $x \in \{1,2...q-1\}$. $x$ je soukromý klíč.
     • Vygenerujeme $y = g^{x}~mod~p$. $y$ je veřejný klíč podepisujícího.

2. Distribuce klíčů:

   Následující informace jsou sdíleny s každým, kdo chce ověřit podpis

   • Použité parametry $(p,q,g)$, které popisují algoritmus
   • Hashovací funkce $H$
   • Veřejný klíč $y$

3. Podepisování:

   • Podepisující nyní může podepsat zprávu $m$. Výsledný podpis je $(r,s)$
   • Zpráva i podpis jsou nyní zaslány příjemci

   Matematické podrobnosti podepisování zprávy

   Podepisující podepíše zprávu $m$ takto:

   • Náhodně zvolí tajné celé číslo k z $\{1,2...q-1\}$
   • Vypočítá $r = (g^k~mod~p)~mod~q$. V vzácném případě, kdy $r=0$, zkusí jiné náhodné k.
   • Vypočítá $s = (k^{-1} (H(m) + xr))~mod~q$. Ve vzácných případech, kdy $s=0$, zkusí jiné náhodné k.
   • Podpis je dvojice $(r, s)$.
   • Podepisující přenáší zprávu $m$ a také podpis $(r,s)$ ověřovateli.

   Protože $r, s$ jsou celá čísla, modulo $q$ je velikost podpisu řádově $N$-bitová, nikoli delší $L$-bitová.

4. Ověření:

   Příjemce nyní chce ověřit pravost odesílatele. Má přístup k veřejným informacím $(q, p, g, H, y, (r,s), m)$ Může provést výpočet, který dokazuje, že odesílatel měl přístup k soukromému klíči $x$

   a snaží se zjistit, zda je podepisující někdo s přístupem k soukromému klíči $x$.

   Matematické podrobnosti schématu ověření DSA

   • Ověříme, že $0 \lt r \lt q$ a $0 \lt s \lt q$, tedy $r, s$ jsou platná celá čísla modulo~q.
   • Vypočítáme $w = s^{-1}~mod~q$.
   • Vypočítáme $u_1 = H(m)w~mod~q$.
   • Vypočítáme $u_2 = rw~mod~q$.
   • Vypočítáme $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • Podpis je ověřen, pokud $v = r$.

   Pro legitimní podpisy lze správnost algoritmu DSA snadno demonstrovat takto:

   • Na straně podepisujícího: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • Uvažujeme-li pravou stranu posledního rovnice, ověřovatel může vypočítat $s^{-1}, H(m)$, protože $s, q, m, H$ jsou veřejné informace.
   • Ověřovatel tedy vypočítá $w = s^{-1}~mod~q$ a $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • Ověřovatel také vypočítá $u_2 = rw~mod~q = rs^{-1}~mod~q$, protože $r$ je také veřejné.
   • Všimněte si, že $k = (u_1 + xu_2)~mod~q$.
   • Ověřovatel však nemá přístup k $x$, protože je to soukromý klíč podepisujícího, takže $k$ samo nemůže být přímo vypočteno. Schéma se místo toho spoléhá na skutečnost, že i když ověřovatel nemůže vypočítat $k$, s legitimním podepisujícím by měl být ověřovatel schopen přepočítat $(g^k~mod~p)~mod~q = r$ s pomocí veřejného klíče podepisujícího $y = g^{x}~mod~p$.
   • Ověřovatel tedy vypočítá $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • Poslední rovnost plyne z toho, že $g$ má řád $q$ a zakládá $v = r$ pro platné podpisy.

Ilustrace DSA v Pythonu

V tomto příkladu použijeme malá prvočísla k ilustraci procesu DSA ve scénáři, kde Alice posílá podepsanou zprávu Bobovi. V tomto příkladu použijeme malá celá čísla. Reálný scénář by využíval mnohem větší prvočísla řádově 2048–3072 bitů.

poznámka

Tento příklad můžeš zkusit spustit znovu s různými hodnotami a zjistit, jak se algoritmus chová, ale ujisti se, že začínáš od první buňky v této části.

Začneme importem potřebných knihoven a výběrem našich parametrů. Celočíselné parametry $p$, $q$, $g$ jsou veřejné informace a splňují tato pravidla:

• $p$, $q$ jsou obě prvočísla
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Dále podepisující, Alice, vygeneruje svůj soukromý klíč.

Soukromý klíč, k (alice-private-key v kódu Pythonu) musí splňovat:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice udržuje svůj soukromý klíč v tajnosti.

Dále Alice vypočítá svůj veřejný klíč pomocí modulárního umocňování. Invertování tohoto kroku k obnovení soukromého klíče je instancí DLP, tedy obtížné vypočítat na klasických počítačích tam, kde jsou použita velká prvočísla.

Z matematického vysvětlení výše víme, že to lze vypočítat pomocí vzorce:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Jak obvykle, Alice zpřístupní svůj veřejný klíč přes ne nutně tajný kanál.

Nyní může Alice podepsat zprávu.

Pro schéma digitálního podpisu musíme vygenerovat hash $H(m)$ zprávy $m$, která má být podepsána.

Předpokládejme, že Alice a Bob se dohodnou na použití konkrétního hashovacího algoritmu s délkou hashe $N$ rovnou počtu bitů v $q$. V tomto jednoduchém příkladu budeme ohraničovat výstupy naší mock hashovací funkce hodnotou $q$. Hashovací funkce je zde triviální, jednoduše generuje náhodné celé číslo.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Dále Alice potřebuje vygenerovat náhodné číslo per-zprávy $k$ a jeho multiplikativní inverz modulo $q$ k výpočtu podpisu.

K výpočtu modulárního inverzu lze použít jednoduchý algoritmus hrubé síly. Je však lepší použít některou z vestavěných funkcí Pythonu pow, jak je ukázáno níže.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice nyní může vypočítat podpis.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Všimni si, že existují určité zvláštní podmínky, které nás budou nutit zvolit jinou hodnotu $k$ v případě, kdy se $r$ nebo $s$ vypočítají jako $0$. V takovém případě vygenerujeme novou hodnotu a opakujeme.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice zveřejní zprávu a svůj podpis příjemci nebo ověřovateli, Bobovi.

Bob dříve zachytil Alicin veřejný klíč a nyní může ověřit podpis pro autentizaci její zprávy.

Za tímto účelem provede několik kontrol, poté znovu vygeneruje hash Aliciny zveřejněné zprávy a vypočítá pomocné hodnoty $w, u_1, u_2$ a $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Nakonec Bob zkontroluje, zda $v$ rovná se $r$. Pokud jsou si rovny, podpis je ověřen.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Bezpečnost DSA

U klasického počítání může být bezpečnost DSA ovlivněna několika faktory:

1. Velikost klíče: Jako vždy, velikost klíče poskytuje základní ochranu proti útokům hrubou silou. Moderní aplikace, které používají DSA, používají velikosti klíčů alespoň 2048 bitů.

2. Kvalita $k$: V DSA každý podpis potřebuje jedinečnou, náhodnou a tajnou hodnotu $k$ (viz výše). Jedinečnost, entropie a tajnost $k$ jsou kritické, a slabost v kterémkoli z těchto aspektů by mohla vést ke kompromitaci soukromého klíče $x$. Generátory náhodných čísel používané pro generování $k$ musí být samy o sobě bezpečné.

3. Síla hashovací funkce: Protože DSA používá hashovací funkci jako součást procesu generování a ověřování podpisu, slabá hashovací funkce by mohla ohrozit bezpečnost digitálního podpisu. Například použití SHA-1 s DSA je zastaralé a doporučuje se SHA-2 nebo vyšší.

Kromě toho by robustní implementace DSA měla také chránit před jinými typy útoků zaměřených na asymetrickou kryptografii, jak bylo dříve nastíněno.

Autentizovaná výměna klíčů s Diffie-Hellmanem a DSA

Moderní protokoly síťové bezpečnosti, jako je Transport Layer Security (TLS) a mnoho dalších, zahrnují kombinování funkcionalit výměny klíčů a autentizace. V kontextu Diffie-Hellmana je autentizace potřebná k ochraně před útoky MITM. V následujících buňkách kódu ilustrujeme příklad, kde Alice a Bob provádějí autentizovanou výměnu klíčů kombinací protokolů Diffie-Hellman a DSA. K tomu použijeme knihovnu cryptography v Pythonu.

Obrázek 2. Autentizovaná výměna klíčů s Diffie-Hellmanem a DSA

Nejprve se Alice a Bob dohodnou na sadě DH parametrů a vygenerují sadu párů veřejný-soukromý klíč pro DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

DH veřejné klíče jsou zveřejněny. Dále Alice i Bob každý vygenerují samostatný pár klíčů pro použití s DSA. Tyto klíče budou zase použity k podpisu DH veřejných klíčů, které mají být vyměněny.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice podepíše svůj DH veřejný klíč pomocí svého DSA soukromého klíče.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Podobně Bob podepíše svůj DH veřejný klíč pomocí svého DSA soukromého klíče.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

DH veřejné klíče a odpovídající podpisy jsou nyní zveřejněny oběma Alicí a Bobem. Po obdržení veřejného klíče a podpisu jejich protistran každá strana ověří platnost podpisu. Tímto způsobem lze zabránit útoku MITM, protože Alice například ví, že Bobův DH veřejný klíč byl skutečně podepsán Bobem a naopak.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Po ověření podpisu Alice a Bob vygenerují sdílený tajný klíč, čímž se dokončí výměna klíčů.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Volitelně, pro dodatečnou bezpečnost, mohou Alice a Bob použít specializovanou funkci derivace klíčů, jako je HKDF, k vygenerování bezpečnějšího symetrického klíče ze svého sdíleného tajného klíče pomocí technik key stretching.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Prolomení Diffie-Hellmana a DSA

Oba protokoly Diffie-Hellman (DH) i DSA zahrnují generování veřejných klíčů ve tvaru $y = g^{x}~mod~p$, kde soukromý klíč $x$ je diskrétní logaritmus.

Útočník, který dokáže vyřešit instanci DLP, může odhalit soukromý klíč jedné ze dvou stran a kombinací s veřejným klíčem druhé strany získat přístup ke sdílenému tajnému klíči. V případě DSA může útočník, který dokáže vyřešit DLP, obnovit soukromý klíč podepisujícího, čímž ruší základní předpoklad digitálního podpisu.

Na klasických výpočetních systémech se věří, že DLP nemá polynomiální řešení. Ale jak Peter Shor ukázal ve svém původním článku z roku 1994, Shorův algoritmus také řeší DLP v polynomiálním čase na kvantových počítačích.

Shorův algoritmus a problém diskrétního logaritmu

Shorův algoritmus je schopen vyřešit problém diskrétního logaritmu v polynomiálním čase. Svou efektivitu primárně dosahuje použitím kvantových algoritmů, které dokáží najít periodu funkce závislé na vstupu problému — což je pak kombinováno s konvenčnějšími operacemi.

Matematické podrobnosti Shorova algoritmu

Shorův algoritmus poskytuje efektivní řešení DLP mapováním na obecnější problém v teorii grup známý jako problém skryté podgrupy (HSP).

V HSP je dána algebraická grupa $G$ a funkce $f: G \rightarrow X$ z $G$ do nějaké množiny $X$ taková, že $f$ je konstantní na každém cosetu nějaké podgrupy $H$ grupy $G$ (a různá na různých cosetech). Úkolem je pak určit $H$. Je známo, že kvantové počítače mohou vyřešit HSP na konečných Abelových grupách v čase polynomiálním v $log~|G|$, kde $|G|$ je řád grupy.

V případě celočíselného DLP diskutovaného v této lekci je mapování na HSP následující:

• Nechť $p$ je prvočíslo a uvažujme DLP dané $y = g^r~mod~p$, kde $g$ je generátor $(\mathbb{Z}_p)^{\times}$. Protože $g^{p-1} \equiv 1~mod~p$, má $g$ řád $p-1$.
• Zvolme $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$, kde $\mathbb{Z}_{p-1}$ je grupa celých čísel modulo $(p-1)$.
• Zvolme $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ danou jako $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$.
• Jádro $f$ je pak podgrupa $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ je konstantní na cosetech $(\delta, 0) + H_0$ a "skrývá" podgrupu $H_0$, čímž nastavuje HSP.

Při výše uvedeném nastavení Shorův kvantový algoritmus pro celočíselný DLP používá kvantový orákl k vyhodnocení funkce $f$ na stavu reprezentujícím uniformní superpozici nad $G$, a poté používá kvantovou Fourierovu transformaci a měření s odhadem fáze k produkci kvantových stavů umožňujících identifikaci generátoru $(r, 1)$ grupy $H_0$. Z toho lze extrahovat $r$, diskrétní logaritmus zájmu.

Shorův původní článek obsahuje podrobný popis algoritmu.

Kryptografie na eliptických křivkách

Kryptografie na eliptických křivkách (ECC), založená na matematice eliptických křivek, nabízí silný přístup k asymetrické kryptografii s veřejným klíčem. ECC je známá tím, že poskytuje podobnou úroveň bezpečnosti jako metody jako RSA, ale s kratšími klíči, což ji činí efektivnější a zvláště vhodnou pro systémy s omezenými prostředky, jako jsou vestavěné systémy a mobilní zařízení, kde jsou úspory v úložišti a výpočetní náklady při menší délce klíčů velmi žádoucí.

Základní principy kryptografie na eliptických křivkách

Eliptická křivka má obvykle tvar $y^2 = x^3 + ax + b$ a má několik zajímavých vlastností.

• Je horizontálně symetrická. Takže pro každý bod $(x,y)$ na křivce je i jeho odraz $(x,-y)$ na křivce.
• Každá nesvislá přímka protne křivku nejvýše ve třech bodech.

Obrázek 1. Operace sčítání a zdvojení bodu na eliptické křivce. Faset 1 definuje P + Q = -R. Faset 2 ilustruje zdvojení bodu 2Q = -P. Faset 3 definuje aditivní inverzi bodu jako jeho odraz okolo osy x, tj. P = -Q

Kryptografie na eliptických křivkách využívá sérii aritmetických operací aplikovaných na body křivky. Každá taková operace efektivně naviguje na nový bod na křivce. Tento postup je v jednom směru snadný, a s kratšími klíči je efektivnější než jiné algoritmy jako RSA, ale obrácení tohoto procesu je velmi obtížné, a proto se ECC využívá v kryptografii.

Matematické principy kryptografie na eliptických křivkách

Eliptická křivka nad algebraickým tělesem $K$ je definována matematickou rovnicí, obvykle ve tvaru $y^2 = x^3 + ax + b$ s koeficienty $a, b \in K$, a popisuje body $(x, y) \in K \otimes K$ s dalším požadavkem, že křivka nemá žádné zlomy ani vlastní průsečíky.

Vlastnosti eliptických křivek umožňují definovat operace „sčítání" a „skalárního násobení" pro body na křivce.

Sčítání: Pokud jsou $P$ a $Q$ dva body na eliptické křivce, pak $P + Q$ popisuje jedinečný třetí bod určený takto: Veď přímku procházející body $P$ a $Q$ a najdi třetí bod $R$, ve kterém tato přímka protíná křivku. Pak definujeme $P + Q = −R$, tedy bod $R$ odražený přes osu $x$ (viz obrázek níže). Pokud přímka procházející body $P, Q$ neprotíná křivku v žádném konečném bodě $(x, y)$, říkáme, že protíná křivku v bodě v nekonečnu $\mathbf{O}$.

Sčítání na eliptické křivce splňuje algebraické vlastnosti grupy s bodem v nekonečnu jako aditivní identitou.

Zdvojení a skalární násobení: Operace zdvojení bodu, která odpovídá skalárnímu násobení číslem $2$, se získá dosazením $P = Q$ do operace sčítání a graficky zahrnuje tečnu v bodě $P$. Obecné skalární násobení celým číslem $n$ definované jako $nP = P + P + ...~n$-krát se získá opakovaným zdvojením a sčítáním.

Problém diskrétního logaritmu na eliptické křivce

Problém diskrétního logaritmu na eliptické křivce (ECDLP) má mnoho podobností s dříve diskutovaným problémem diskrétního logaritmu, neboť je také založen na obtížnosti nalezení faktorů.

Operace skalárního násobení na eliptických křivkách umožňuje definovat problém diskrétního logaritmu na eliptické křivce:

Dány body $P, Q$ na eliptické křivce tak, že $Q = nP$, urči $n$.

Pro klasické počítače je tento problém při velkém $n$ považován za neřešitelný a tvoří základ kryptografické bezpečnosti.

Matematický popis ECDLP

Kryptografie na eliptických křivkách je primárně založena na ECDLP formulovaném na určitých algebraických konečných tělesech. V roce 1999 NIST doporučil deset konečných těles pro použití v ECC. Jsou to:

• Pět prvočíselných těles $\mathbb {F} _{p}$ pro prvočísla $p$ o velikosti $\{192, 224, 256, 384, 521\}$ bitů.
• Pět binárních těles $\mathbb {F} _{2^{n}}$ pro $n \in \{163, 233, 283, 409, 571\}$.

S výše uvedeným nastavením lze asymetrický kryptosystém založený na ECC v případě prvočíselných těles specifikovat takto:

• Vyber $p$ ze seznamu doporučených hodnot NIST pro specifikaci $\mathbb {F} _{p}$.

• Zvolte parametry $a, b$ eliptické křivky.

• Vyber základní bod $G$, který „generuje" cyklickou podgrupu na křivce s řádem $n$; tedy nejmenší celé číslo takové, že $nG = \mathbf{O}$.

• Vypočítej kofaktor $h = |E(\mathbb {F} _{p})|/n$, kde $|E(\mathbb {F} _{p})|$ je počet bodů na křivce. $h$ je obvykle malé celé číslo.

• Doménové parametry $(p, a, b, G, n, h)$ umožňují specifikaci asymetrických klíčů takto:

  • Soukromý klíč je náhodně zvolené celé číslo $d$ se stejným počtem bitů jako prvočíslo $p$. Musí být uchováno v tajnosti.
  • Veřejný klíč je výsledkem „násobení" základního bodu $G$ soukromým klíčem $d$. Obvykle se označuje jako $Q = dG$.

Získat zpět $d$ je ekvivalentní vyřešení ECDLP, který je pro velká $d$ považován za neřešitelný. ECDLP tedy tvoří základ pro schémata výměny klíčů a digitálních podpisů v přímé analogii se schématy Diffie-Hellman a DSA definovanými nad $(\mathbb{Z}_p)^{\times}$, která byla diskutována dříve.

Výměna klíčů pomocí ECC

Jedním z hlavních využití ECC je protokol výměny klíčů známý jako Diffie-Hellman na eliptické křivce (ECDH). V ECDH každá strana vygeneruje pár soukromý–veřejný klíč a poté si vymění veřejné klíče. Každá strana pak použije svůj vlastní soukromý klíč a veřejný klíč druhé strany k výpočtu sdíleného tajemství, které lze použít jako klíč pro symetrické šifrování.

Zatímco provést sčítání bodů na eliptické křivce a odvodit veřejný klíč ze soukromého je relativně snadné, obrátit tento proces a odvodit soukromý klíč z veřejného je výpočetně neproveditelné. Toto „jednosměrné" chování zajišťuje bezpečnost výměny klíčů ECDH.

Zde si ukážeme příklad, jak by bylo možné provést výměnu klíčů ECDH pomocí Pythonu a knihovny cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Digitální podpisy pomocí ECC

ECC lze také použít ke generování digitálních podpisů pomocí Algoritmu digitálního podpisu na eliptické křivce (ECDSA). V ECDSA podepisující vytvoří podpis pomocí svého soukromého klíče a ostatní mohou podpis ověřit pomocí podepisujícího veřejného klíče. Stejně jako u ECDH je bezpečnost ECDSA závislá na ECDLP. Pro někoho bez přístupu k soukromému klíči podepisujícího je výpočetně neproveditelné podpis zfalšovat.

Níže je příklad jednoduché transakce podepisování a ověřování pomocí ECDSA s Pythonem a cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

Pokud ve výše uvedeném kódu upravíš zprávu poté, co byla podepsána, ověření selže, čímž je zajištěna autenticita a integrita zprávy.

Prolomení ECDH a ECDSA

Analogicky k problému diskrétního logaritmu nad celými čísly se ukazuje, že ECDLP je pro klasické počítače obtížný, ale na kvantových počítačích má efektivní řešení opět prostřednictvím Shorova algoritmu. Odkazujeme tě na novější literaturu pro diskusi o zobecnění Shorova algoritmu na případ ECDLP.

Shrnutí

V této lekci jsme začali pohledem na hlavní charakteristiky asymetrické kryptografie s veřejným klíčem (AKC) a diskutovali jsme základní bezpečnostní aspekty, které jsou základem asymetrických kryptosystémů. Zejména jsme představili dvě hlavní aplikace AKC — výměnu klíčů a digitální podpisy — které jsou oba nezbytné součásti moderní internetové komunikace.

Poté jsme se zaměřili na kryptosystém RSA, který od 70. let 20. století prokázal svou obrovskou hodnotu při zabezpečování moderní digitální komunikace tím, že umožňuje výměnu klíčů a digitální podpisy v jednoduchém a všestranném rámci. Kryptografická bezpečnost RSA vůči klasickým počítačům je založena na obtížnosti faktorizace velkých celých čísel a vyžaduje délky klíčů v rozsahu 2048 bitů, aby celá čísla používaná v praktických aplikacích byla dostatečně velká na to, aby odolala faktorizaci.

Poté jsme se podívali na výměnu klíčů Diffie-Hellman (DH) a Algoritmus digitálního podpisu (DSA). Bezpečnost těchto schémat je závislá na problému diskrétního logaritmu nad celými čísly (DLP), přičemž soukromý klíč je výpočetně obtížné extrahovat ze veřejného klíče bez polynomiálního řešení na klasických počítačích. Použití náhodných a jedinečných klíčů poskytuje dodatečnou bezpečnost proti útokům. Jak varianty nad konečným polem celých čísel, tak varianty na eliptické křivce protokolů DH a DSA se v současnosti hojně využívají v mnoha moderních protokolech digitální komunikace, jako jsou TLS, SSH a další.

Nakonec jsme se zabývali kryptografií na eliptických křivkách. Díky efektivní délce klíčů a silným bezpečnostním vlastnostem v současnosti představuje vynikající volbu pro mnoho kryptografických aplikací, od výměny klíčů po digitální podpisy.

Všechny tyto algoritmy jsou zranitelné vůči útokům kvantových algoritmů, protože lze vyvinout řešení matematických problémů, které tvořily základ jejich návrhu. Jedním takovým příkladem je Shorův algoritmus. Proto budou muset být nahrazeny kvantově bezpečnými asymetrickými kryptosystémy, které jsou odolnější vůči útokům z kvantových počítačů — a přitom stejně bezpečné vůči klasickým algoritmům. Matematické problémy, na nichž tyto algoritmy závisí, mohou být kvantovými počítači efektivně vyřešeny, což si vyžaduje vývoj kvantově bezpečných asymetrických kryptosystémů, které odolají kvantovým útokům při zachování klasické bezpečnosti.

Budoucí lekce se zaměří na kvantově bezpečné kryptosystémy a prodiskutuje požadovaný přístup k zachování kryptografické bezpečnosti.