Hlavní navigace

Bernsteinovy eliptické křivky

Ondrej Mikle

Křivka Curve25519 se v současnosti zabydluje ve více a více protokolech. Pojďme se podívat, co je na ní tak zvláštního. Snažil jsem se vybrat přednosti této křivky a křivek jí příbuzných a zajímavé implementační finty bez toho, aby se zabíhalo příliš do algebry. Řeč přijde i na úplnou novinku – Curve41417.

Daniel J. Bernstein je celkem známá osoba mezi programátory i matematiky. Mezi jeho programátorské počiny patří třeba qmail. Z matematických prací publikoval několik kryptosystémů založených na eliptických křivkách (dále jen ECC). Velmi často mezi jeho spolupracovníky patří Tanja Lange a pár dalších zvučných jmen.

Na co je která křivka dobrá

Křivka Curve25519 je jedna z Bernsteinových starších prací z 2005. Je určena pro Diffie-Hellman dohodu na sdíleném klíči. Tento systém se časem dost osvědčil, je už součástí software jako SSH, Tor a míří do dalších protokolů – dost se o něm například mluví v souvislosti s TLS 1.3.

Kryptosystém Ed25519 je založen na křivce příbuzné Curve25519 a slouží ke generování digitálních podpisů. Podpisy jsou deterministické a nehrozí tedy v průběhu používání prozrazení tajného klíče špatným náhodným generátorem (viz též RFC 6979).

Křivka Curve41417 je nová velká křivka určená opět k Diffie-Hellman dohodě na klíči. Díky obrovskému konečnému tělesu, nad kterým je postavena, má být určena k designování systémů, které budou například více než 10 let sloužit v embedded zařízeních.

Velmi důležitým znakem každé zmíněné křivky je rychlost a vysoká odolnost proti postranním kanálům.

Občas zmíníme porovnání s NIST křivkami, těmi jsou myšleny křivky, jejichž názvy začínají s „NIST P“ nebo „sec“, např. NIST P-224, secp256r1 nebo sect409k1. NIST křivky se používají jak na Diffie-Hellmana, tak pro podepisování.

Klíče na eliptické křivce

Pro osvěžení si připomeneme, jak se reprezentují klíče u eliptických křivek. Privátní klíč je typicky velké celé číslo k. Veřejný klíč k privátnímu dostaneme násobením privátního klíče s generátorem G, což je specifický, veřejně známý bod na eliptické křivce. Obtížnost získání privátního klíče z veřejného klíče k•G se označuje jako problém diskrétního logaritmu pro eliptické křivky.

Curve25519

Křivka Curve25519 je pojmenována podle prvočísla 2255 – 19, které označuje konečné těleso, nad kterým je kryptosystém Curve25519 vybudován.

Nejdůležitější vlastnost křivky Curve25519 je její jednoduchá použitelnost pro programátora, která odstraňuje pasti jako speciální případy v ECC aritmetice a postranní kanály. Některé vlastnosti plynou z algebraických vlastností, jiné jsou dány implementací.

Návod, jak použít Curve25519 ve vlastním software, je k dispozici na stránkách D. Bernsteina. Implementaci optimalizovanou pro současné x86 procesory a generickou portabilní verzi lze najít pod názvem curve25519-donna.

Výhody křivky Curve25519

První vlastností je rigidnost výběru parametrů křivky – neobsahuje žádná „neodůvodněná hausnumera“ jako různé NIST křivky. Parametry jsou zvoleny, aby byly buďto nejmenší nebo nejbližší číslo splňující určitou algebraickou vlastnost.

Křivka je imunní proti časovým, hyperthreading a cachovacím postranním kanálům, protože se implementace vyhýbá větvení závislém na vstupu, nepoužívá indexy pole závislé na vstupu ani jiné instrukce s časováním závislým na vstupu.

Privátní klíče mají 32 bajtů, běžných u ECDH funkcí se stejnou úrovní bezpečnosti. Veřejné klíče mají také 32 bajtů, což je polovina proti 64 bajtům u typických ECDH funkcí. Trik spočívá v tom, že se používá „komprimovaná“ forma bodu, obsahující jenom x souřadnici.

Koordinátu y lze z komprimovaného bodu dopočítat, ale algoritmy jsou stavěny tak, že to není potřeba (tzv. laddering algoritmy). U NIST křivek také existuje komprimovaná forma bodu, ale body se při počítání musí dekomprimovat. Zároveň nelze použít laddering algoritmy.

Možnost počítání s komprimovaným bodem má ale jeden zásadní vedlejší efekt – není potřeba vstupní body kontrolovat, zda leží na křivce. Tím odpadá jeden podstatný útok, tzv. fault útok, kde útočník může získat bity našeho privátního klíče tím, že nás nechá počítat s bodem mimo křivku a my si to nezkontrolujeme. Takto máme „validaci bodu zdarma“.

Generování privátních klíčů je podobně jednoduché – vygenerujeme libovolné náhodné číslo dlouhé 256 bitů, bity 255, 2, 1 a 0 se vynulují, bit 254 se nastaví. Nulování nejnižších třech bitů způsobí, že privátní klíč bude násobkem 8. To je další designový prvek odstraňující twist útok.

Jak si představit Diffie-Hellman protokol s křivkou Curve25519

Curve25519 Diffie-Hellman

Alice má svůj tajný klíč – velké celé číslo a, Bob má svůj tajný klíč – velké celé číslo b. Řetězec 9 je použit jako generátor (přesněji se tím určuje bod na křivce, který ma Xovou souřadnici 9).

Funkci Curve25519 si můžeme představit jako násobení. Alice si s Bobem vymění bod vzniklý po násobení tajného klíče s generátorem, po drátě tedy putují veřejné klíče Curve25519(a, 9) a Curve25519(b, 9). Po přijetí tohoto čísla ze sítě si každý z nich spočte:

  • Alice si spočte: Curve25519(a, Curve25519(b, 9))
  • Bob si spočte: Curve25519(b, Curve25519(a, 9))

Můžeme si to ilustrovat opět násobením – jako by se posílalo a•9 a b•9, obě strany pak přijaté číslo vynásobí svým privátním klíčem a skončí tak s a•b•9 == b•a•9 (operace je komutativní). Na konci se toto sdílené tajemství ještě zahashuje.

Implementační specifika Curve25519

První implementace pro Pentium a Athlon

Koordináty křivky Curve25519 a privátní klíče pocházejí z konečného pole Fp, kde p = 2255 – 19. Pro reprezentaci prvků konečného pole se používají FPU registry a neceločíselný radix 225.5.

Oproti „naivní“ implementaci, kde by se prvek „rozsekal“ na 32bitová slova, to má tu výhodu, že je možné zdržovat normalizaci a mít koeficienty dočasně větší než radix. Analogie k dvojkové soustavě by vypadala asi tak, že bychom používali občas číslice 2 a 3 v mezivýpočtech, protože to zlepšuje algoritmus.

Praxe s pozdržováním normalizace koeficientů je zdá se celkem běžná u implementace ECC aritmetiky. Urychlují se tím operace na křivce. U Curve25519 se normalizace pozdrží až do doby, než se musí vrátit výsledek.

Implementace s ARM NEON instrukční sadou

NEON je instrukční sada pro vektorové operace na mnoha ARM procesorech, které se běžně používají v modernějších telefonech a tabletech. Důvod výběru této platformy pro implementaci je tudíž zřejmý.

Trochu zvláštní je, že kód byl napsán v meta-assembleru qhasm, který by se dal označit jako „platformně nezávislá“ mezivrstva mezi C a CPU-specifickým assemblerem.

Asi nebude překvapením, že i na této platformě byly cíle rychlost a odolnost proti postranním kanálům.

Curve41417

Křivka Curve41417 je celkem novinka, byla publikována teprve v červenci 2014. Název následuje podobnou konvenci jako Curve25519, je nazvána po prvočísle 2414 – 17, podle prvočíselného tělesa, nad kterým je křivka definována.

Proč potřebujeme tak obrovskou křivku?

Úroveň bezpečnosti mezi 280 a 2128 operací je ta, na kterou většina dnešních aplikací míří. Spodní hranice 80 bitů je spíš už pokládána za překonanou – dokážou ji upočítat třeba dnešní botnety.

Nicméně někteří autoři pořád argumentují, že pro klíče s krátkým trváním to postačuje. Například u DNSSEC se pořád používají 1024-bitové RSA zone signing keys, které jsou asi na úrovni „80bitové bezpečnosti“.

CAB Forum vyžaduje pro nově vydávané HTTPS certifikáty 2048-bitový modulus v případě RSA klíče, což zhruba odpovídá 112bitové bezpečnosti. RSA klíče velikosti 1024 bit už označuje za slabé i známý Qualys SSL/TLS server test.

Snad nikdo momentálně nezpochybňuje, že 128bitová bezpečnost postačuje pro většinu současných aplikací (sem spadají i eliptické křivky s 256 bitů velikými konečnými tělesy).

Úroveň bezpečnosti křivky Curve41417 odpovídá asi 212 bitům. Je úroveň nad 200 bitů k něčemu?

Křivce Curve25519 trvalo téměř 10 let, než byla dostatečně prověřena a začala se víc používat. Je celkem očekávatelné, že stejně dlouho bude trvat křivce Curve41417, než se začne používat v systémech, kde se dělá obtížně upgrade – právě v embedded systémech.

V embedded systémech pravděpodobně minimálně dalších 10 let vydrží a pro vygenerovaný klíčový materiál může být požadováno dalších několik let, aby zůstal neprolomitelný. Požadovat tedy odolnost na 30, 40 nebo i více let dává v těchto případech smysl.

Kromě samotného zvyšování dostupného výpočetního výkonu časem se musí ještě myslet na algoritmické průlomy. Ty nenastávají často, ale můžou být o to výraznější.

Například relativně nedávno se prolomila bezpečnost jedné speciální instance diskrétního logaritmu pro speciální křivky nad tělesy s malou charakteristikou. Z očekávaných 2128 operací zůstalo pouhých 259 operací.

Eliptické křivky nad tělesy s velkou prvočíselnou charakteristikou – kam patří i všechny Bernsteinovy křivky zde zmiňované – jsou něčím diametrálně odlišným, nežli křivky nad tělesy s malou charakteristikou. Ale stejně nelze zaručit, že k nějakému matematickému průlomu nedojde.

Budoucnost se těžko odhaduje, ale pravděpodobně se velikost křivky Curve41417 bude ještě hodit. Většinou je důvod nenasazení kryptografických primitiv s obrovskými parametry pomalost – problém, který tato křivka řeší výborně.

Našli jste v článku chybu?

25. 7. 2014 8:04

Honz (neregistrovaný)

Konečně pravý rootovský článek jako za starých časů (které nepamatuju). Naštěstí z toho nerozumím jedinému slovu...

25. 7. 2014 18:44

Franta. (neregistrovaný)

Vždycky jsem se podivoval u zpráv o tom, že dnešní maturanti nedokážou interpretovat psaný text, ale implikace
"konečně pravý rootovský článek jako za starých časů" => "článek je dobrý"
a
"netvrdil nic o tom, že je článek dobrý" => "článek není dobrý"
mě dostaly do kolen.





Vitalia.cz: Poznáte poctivé suroviny na pečení cukroví?

Poznáte poctivé suroviny na pečení cukroví?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí