Kryptografie nad eliptickými křivkami

Kryptografie eliptických křivek (ECC) je metoda šifrování veřejných klíčů založená na algebraických strukturách eliptických křivek nad konečnými poli. Použití eliptických křivek v kryptografii navrhli nezávisle na sobě Neal Koblitz a Victor S. Miller v roce 1985.

Eliptické křivky se také používají v několika algoritmech pro prvočíselný rozklad, které nacházejí uplatnění v kryptografii, jako například metoda eliptických křivek od Hendrika Lenstra.

Úvod

Kryptografie veřejných klíčů je založena na nepoddajnost některých matematických problémů. Systémy založené na veřejných klíčích jsou bezpečné za předpokladu, že je obtížné rozdělit velké celočíselné číslo složené ze dvou a více velkých prvočísel. Pro systémy na bázi eliptických křivek se předpokládá, že nalezení diskrétního logaritmu náhodného elementu eliptické křivky s ohledem na známý základní bod je nemožné. Velikost eliptické křivky určuje složitost problému. Předpokládá se, že stejné úrovně zabezpečení jakou nabízejí RSA systémy s velkým modulem, lze dosáhnout s podstatně menší skupinou eliptických křivek. Použití malé skupiny eliptických křivek znamená snížení nároků na přenos i místo.

Pro současné kryptografické účely se používá rovinná křivka, která se skládá z bodů vyhovujících rovnici

$y^2 = x^3 + ax + b, \,$

lišící se nevlastním bodem, označujeme ∞. (Souřadnice jsou zde vybírány z pevného konečného pole neobsahujícího 2 a 3, jinak by křivka byla poněkud komplikovanější).

Toto tvoří společně se skupinou operací nad teorií množin eliptických křivek Abelovu grupu, s bodem v nekonečnu jako neutrálním prvkem. Struktura grupy se dědí z množiny dělitele ze základních algebraických variet.

Stejně jako pro ostatní populární šifrovací metody založené na veřejném klíči není publikován žádný matematický důkaz o bezpečnosti ECC ještě v roce 2009. Avšak Americká Národní bezpečnostní agentura schválila ECC včetně schémat na něm založených ve své sadě kryptografických algoritmů Suite B a povolila jejich použití k šifrování informací označených jako přísně tajné 384-bitovými klíči. Zatím co patent RSA vypršel v roce 2000, jsou zde v platnosti patenty týkající se určitých aspektů ECC technologie, i když někteří tvrdí že Protokol digitálního podpisu s využitím eliptických křivek (ECDSA; NIST FIPS 186-3) a některé praktické programy pro výměnu veřejných klíčů na bázi ECC (včetně ECDH) mohou být implementovány bez jejich porušení.

Kryptografické algoritmy

Několik algoritmů založených na výpočtu diskrétního logaritmu bylo přizpůsobeno pro použití eliptických křivek nahrazením množiny $(\mathbb{Z}_{p})^\times$ eliptickou křivkou:

• ECDH (anglicky: Elliptic curve Diffie–Hellman), česky: Diffie-Hellman protokol s využitím eliptických křivek je založen na protokolu Diffie-Hellman
• ECIES (anglicky: Elliptic Curve Integrated Encryption Scheme)
• ECDSA (anglicky: Elliptic Curve Digital Signature Algorithm) založený na algoritmu DSA (anglicky: Digital Signature Algorithm)
• ECMQV
• ECQV

Na RSA konferenci v roce 2005 představila Národní bezpečnostní agentura balíček nazvaný Suite B který pro generování digitálního podpisu a výměnu veřejných klíčů používá výhradně technologii ECC. Tento balíček je určen k ochraně jak klasifikovaných tak i neklasifikovaných národních bezpečnostních systémů a informací.

Reference

V tomto článku byl použit překlad textu z článku Elliptic curve cryptography na anglické Wikipedii.