Elliptic Curve Cryptography (ECC) – grupa technik kryptografii asymetrycznej, wykorzystująca jako podstawową technikę matematyczną krzywe eliptyczne[1]. Użycie krzywych eliptycznych w celach kryptograficznych zostało zasugerowane niezależnie przez dwójkę badaczy: Neala Koblitza oraz Victora S. Millera w roku 1985.
Bezpieczeństwo ECC jest oparte na złożoności obliczeniowej logarytmów dyskretnych na krzywych eliptycznych – Elliptic Curve Discrete Logarithm Problem (ECDLP). Algorytm podpisu cyfrowego przy użyciu ECC to ECDSA(inne języki).
ECC oferuje bezpieczeństwo porównywalne do RSA przy znacznie krótszych kluczach. Ocenia się, że bezpieczeństwo klucza RSA o długości 1024 bitów jest równoważne bezpieczeństwu klucza ECC o długości 160 bitów. Z tego powodu ECC jest bardzo atrakcyjnym algorytmem w zastosowaniach, które wymagają bardzo wysokiej wydajności szyfrowania asymetrycznego (algorytm RSA jest stosunkowo wolny) lub oferują bardzo ograniczone środowisko obliczeniowe (jak karty mikroprocesorowe).
ECC wykorzystuje działania matematyczne krzywych eliptycznych w ciałach, na liczbach całkowitych i w oparciu o duże liczby pierwsze. W rezultacie ich reprezentacja graficzna nie ma wiele wspólnego ani z krzywymi, ani z elipsami — są to przypominające chmurę zbiory punktów[2].
Wykorzystanie ECC w praktyce
Wygaśnięcie patentu na algorytm RSA w 2000 roku spowodowało chętne i masowe jego wykorzystywanie jako znajdującego się od tej pory w domenie publicznej, podczas gdy algorytmy oparte na ECC są objęte licznymi patentami. Właścicielem większości z nich jest kanadyjska firma Certicom, posiadająca ponad 130 patentów związanych z ECC.
Część z patentów jest publicznie podważana przez wiele firm (m.in. Sun) i niezależnych kryptologów, twierdzących, iż analogiczne techniki były znane i prezentowane przez innych autorów przed ich opatentowaniem. Budzi to nieufność dużych producentów oprogramowania, unikających technologii o niejasnym stanie prawnym. Poza tym implementacja algorytmów na krzywych eliptycznych jest bardziej pracochłonna i wymaga szerszej wiedzy niż w przypadku np. RSA.
W Polsce krzywe eliptyczne zaimplementowane są w systemie kryptograficznym pod nazwą „Narodowy szyfrator” stworzonym w ramach umowy konsorcjum naukowo-przemysłowego WAT i firmy WASKO S.A. pod kierownictwem profesora Jerzego Gawineckiego[3] oraz w szyfrujących telefonach GSM firmy Techlab2000[4].
Dostępność ECC
Stosowanie kryptografii opartej na krzywych eliptycznych jest nadal możliwe bez zgody Certicomu, ponieważ patenty obejmują tylko pewne techniki związane z implementacją algorytmów a nie algorytmy ECC jako takie. Istnieją darmowe i ogólnodostępne implementacje ECC nie objęte patentami (m.in. OpenSSL, NSS, GnuPG[5] i Libgcrypt[6]).
Algorytm ECC jest także podstawowym algorytmem podpisu elektronicznego w tzw. Suite B, czyli zestawie algorytmów kryptograficznych rekomendowanym przez amerykańską agencję NSA do zastosowań w biznesie.
W praktyce stosowane są parametry krzywych eliptycznych generowane przez organizacje standaryzacyjne: FIPS186-4 (NIST)[7], BrainPool (TeleTrust)[8] i SECG (Certicom)[9]. Część opisanych w literaturze krzywych nie nadaje się do zastosowań kryptograficznych ze względu na znane słabości[10].
Implementacje
Biblioteki zawierające implementację algorytmów na krzywych eliptycznych:
Przypisy