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 tělesy. 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 Lenstry.

Úvod

Kryptografie veřejných klíčů je založena na neznalosti rychlých algoritmů pro některé matematické problémy. Nejstarší systémy kryptografie veřejných klíčů jsou bezpečné za předpokladu, že je obtížné rozdělit na prvočísla velké přirozené číslo, které je součinem dvou a více velkých prvočísel. Pro systémy na bázi eliptických křivek se naproti tomu předpokládá, že nalezení diskrétního logaritmu náhodného bodu 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


lišící se nevlastním bodem, označujeme ∞. (Souřadnice jsou zde vybírány z pevného konečného tělesa 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 matematické bezpečnosti ECC. 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é 384bitovými klíči. Zatímco 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í. Navíc standardizovaný generátor náhodných čísel (od NIST a NSA) může vytvářet zadní vrátka, známá jen tvůrcům algoritmu generátoru.[1]

Pak i Diffieho-Hellmanova výměna klíčů je napadnutelná.[2]

Roku 2015 oznámila NSA ústup od používání ECC, kterou má nahradit postkvantová kryptografie.[3] Spoluautor ECC spekuluje o důvodech k tomuto kroku.[4]

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 grupy grupou bodů nad eliptickou křivkou, tyto algoritmy pak mají anglickou zkratku s předponou EC:

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.

  1. ↑ http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/3/ - A (relatively easy to understand) primer on elliptic curve cryptography
  2. ↑ https://jiggerwit.wordpress.com/2013/09/25/the-nsa-back-door-to-nist/ - The NSA back door to NIST
  3. ↑ http://crypto-world.info/news/index.php?prispevek=22550&sekce=s - Why Is the NSA Moving Away from Elliptic Curve Cryptography?
  4. ↑ https://eprint.iacr.org/2015/1018.pdf - A RIDDLE WRAPPED IN AN ENIGMA, NEAL KOBLITZ AND ALFRED J. MENEZES