Szyfr na krzywych eliptycznych

Szyfr na krzywych eliptycznych (ang. Elliptic Curve Cryptography, ECC) – algorytm wykorzystujący krzywe eliptyczne w celu szyfrowania informacji (istnieją także inne algorytmy np. algorytm rozkładu liczb złożonych na czynniki pierwsze wykorzystujące krzywe eliptyczne).

Krzywe eliptyczne są obiektem matematycznym pozwalającym w łatwy sposób na generację dużej liczby nietrywialnych grup abelowych. Elementami takich grup są punkty krzywej, zaś jako działanie służy pewna raczej złożona operacja arytmetyczna wymierna na ich współrzędnych. W tak zdefiniowanych grupach może występować wielka, choć skończona liczba elementów (rząd grupy może być skończony) jeśli zawęzić operacje do np. punktów o współrzędnych wymiernych, lub jeśli całą krzywą rozpatrywać wyłącznie w ramach arytmetyki modulo skończona liczba pierwsza p.

Aby zbudować system szyfrujący w oparciu o krzywe eliptyczne, stosuje się jeden ze znanych algorytmów szyfrowania, jak algorytm szyfrowania oparty na problemie logarytmu dyskretnego (porównaj ElGamal). W miejsce grupy modulo p, wprowadza się grupę E generowaną przez określona krzywą eliptyczną. W takim wypadku rolę działania multiplikatywnego pełni potęgowanie punktu w grupie E (które w grupie E polega po prostu na dodawaniu punktu do samego siebie P + P + P = 3 * P co jest równe P^{3} zależnie od sposobu zapisu działania grupowego), zaś wykładnik w takiej grupie może pełnić rolę klucza. Powstałe w ten sposób systemy szyfrowania należą do klasy kryptografii asymetrycznej. Osobą, która zaproponowała po raz pierwszy użycie krzywych eliptycznych, a następnie ich uogólnienia, krzywych hipereliptycznych, w algorytmach kryptograficznych był Neal Koblitz.

Znaczenie kryptografii opartej na krzywych eliptycznych wzrasta, gdyż przy tej samej długości klucza, z powodu złożoności arytmetyki grupowej, oferuje ona większe bezpieczeństwo (jej złamanie wymaga większej ilości obliczeń) w porównaniu z np. RSA. Odwrotnie, to samo bezpieczeństwo osiągamy przy mniejszej długości klucza niż w innych przypadkach szyfrowania asymetrycznego. Tym samym implementacja algorytmów szyfrujących w oparciu o krzywe eliptyczne dobrze nadaje się do użycia w np. kartach chipowych.

Adwersarze argumentują, że algorytmy starsze, takie jak RSA są lepiej przebadane oraz znacznie wydajniejsze (szybsze). Rzeczywiście porównanie szybkości szyfrowania wskazuje, ze DES (a więc szyfr symetryczny) jest ok. 100 razy szybszy niż RSA (asymetryczny), który jest ok. 10 razy szybszy niż kryptografia eliptyczna.

Prowadzone są prace nad standaryzacją szyfrowania opartego na krzywych eliptycznych oraz prace rozwojowe nad rozwojem uogólnienia tego typu szyfrów na krzywe hipereliptyczne. Szczególne miejsce w tych pracach zajmuje określenie jakie krzywe eliptyczne nadają się do stosowania w ramach algorytmów kryptograficznych znane są bowiem pewne ograniczenia czyniące szyfrowanie eliptyczne nieprzydatnym (łatwym do złamania) jeśli zostanie ono zbudowane w oparciu o niewłaściwą krzywą. Warto także zwrócić uwagę, że w dziedzinie matematycznej teorii krzywych eliptycznych notuje się szybki rozwój teoretyczny i może się okazać że za kilka lat opracowane zostaną skuteczne techniki łamania szyfrów tego typu lub że zmienione zostaną zalecenia co do stosowanych klas krzywych.