Kryptografia krzywych eliptycznych

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 dyskretnych logarytmów na krzywych eliptycznych – Elliptic Curve Discrete Logarithm Problem (ECDLP). Algorytm podpisu cyfrowego przy użyciu ECC to ECDSA.

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

  1. ↑ D. McGrew, K. Igoe, M. Salter: Fundamental Elliptic Curve Cryptography Algorithms. IETF, 2010.
  2. ↑ Johannes Bauer: Elliptic Curve Cryptography Tutorial.
  3. ↑ Narodowy szyfrator nagrodzony. [dostęp 2010-12-29]. [zarchiwizowane z tego adresu (2011-05-15)].
  4. ↑ Szyfrujący telefon od Techlab 2000. IPSec.pl, 2009. [dostęp 2011-05-27]. [zarchiwizowane z tego adresu (2012-04-15)].
  5. ↑ Werner Koch: ECC code now in GnuPG master.
  6. ↑ Werner Koch: ECC code now in Libgcrypt master.
  7. ↑ Digital Signature Standard (DSS). NIST, 2013.
  8. ↑ ECC Brainpool Standard Curves and Curve Generation. ECC Brainpool, 2005. [dostęp 2013-10-31]. [zarchiwizowane z tego adresu (2018-04-17)].
  9. ↑ Certicom: SECG Released Standards. 2000.
  10. ↑ SafeCurves: choosing safe curves for elliptic-curve cryptography.