Przejdź do zawartości

Kryptografia krzywych eliptycznych

Z Wikipedii, wolnej encyklopedii

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(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

[edytuj | edytuj kod]

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

[edytuj | edytuj kod]

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

[edytuj | edytuj kod]

Biblioteki zawierające implementację algorytmów na krzywych eliptycznych:

Przypisy

[edytuj | edytuj kod]
  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.