Kryptografie s eliptickými křivkami představuje rozšíření standardních asymetrických kryptosystémů. Zvyšuje bezpečnost při jejich využívání (tj. využívá se v kombinaci s nimi). Níže je představen obecný princip tohoto způsobu šifrování.
Eliptická křivka je množina všech bodů splňujících rovnici:
y2 = ax3 + bx2 + cx + d
Obecně pro nějaká konečná reálná čísla a,b,c a d (tato čísla jsou tzv. parametry křivky). Křivka zadaná právě touto rovnicí je v tzv. Weierstrassově formě (tj. je v určité normální formě). Speciálním případem jsou tzv. singulární Eliptické křivky, které splňují rovnici: 4a3 + 27b2 = 0 (ty jsou pro kryptografii nepoužitelné).
Množina všech těchto bodů je zajímavá tím, že tvoří komutativní grupu (též Abelovu grupu), tedy množinu, kde platí určité axiomy (tvrzení, které se nedokazují). Mějme tedy množinu bodů eliptické křivky a operaci sčítání bodů + (vůči které je množina uzavřená, to znamená, že součet libovolných bodů v množině je opět v této množině), dále nulový bod 0, který geometricky odpovídá nekonečnu (bodu na rovině xy, který je v jakémkoli směru v nekonečnu).
Dále uvažujeme libovolné body A, B, C v této množině, pro ně určitě musí platit následující tvrzení:
A + B = B + A (axiom komutativity; můžeme prohazovat pořadí sčítanců, toto definuje Abelovskou grupu, obecná grupa tento axiom nemá)
A + (B + C) = (A + B) + C (axiom asociativity; výrazy můžeme libovolně uzávorkovat = nezáleží na pořadí závorek)
Existuje prvek 0, takový, že: A + 0 = 0 + A = A (axiom existence nulového prvku; je definován tak, jak je uvedeno výše, jedná se o libovolný bod v nekonečnu)
Ke každému prvku A z množiny existuje prvek opačný (-A) takový, že A + (-A) = 0, zkráceně prostě A - A = 0 (axiom existence inverzního prvku; jeho součet s výchozím prvkem je nulový prvek)
Bod 0 (nulový bod množiny) se v geometrii nazývá NEVLASTNÍ bod.
Sčítání (operace +) bodů je definováno takto:
Mějme dva body s příslušnými souřadnicemi: P[xP, yP] a Q[xQ, yQ]. Dále bod R = P + Q má souřadnice R[xR, yR] ve tvaru:
xR = m2 - xP - xQ
yr = -yP - m(xR - xP) = -yQ - m(xR - xQ)
Kde parametr m nabývá následující hodnoty, pokud P≉Q (body se liší, tj. nemají identické souřadnice):
m = (yP - yQ) / (xP - xQ)
a parametr m nabývá následující hodnoty, pokud P = Q (body splývají):
m = (3xP2 + a) / (2yP)
V rámci kryptografie jsou významné pouze Eliptické křivky, které mají koeficienty (čísla a,b,c a d) zbytkové třídy modulo prvočíslo. Všechny operace jsou stejné, počítá se pouze modulo prvočíslo (standardní modulární aritmetika). Hlavní rozdíl je, že namísto dělení se násobí inverzní hodnotou modulo prvočíslo (multiplikativní inverze).
Jedná se o klíčovou operaci, mějme bod P na křivce a přirozené číslo r, skalární násobení zapisujeme r × P a má význam:
r × P = P + P + ··· + P (počet sčítanců je právě r)
kde operace sčítání je definována tak, jak je vysvětleno výše.
Pokud máme bod P a náhodné přirozené číslo r, pak můžeme snadno vypočítat hodnotu souřadnic bodu Q = r × P (pohybujeme se na diskrétní množině modulo prvočíslo). Vypočítat však ze znalosti hodnoty Q zpátky číslo r je však mimořádně obtížné. Na tomto principu je právě postavena kryptografie s eliptickými křivkami. Princip takového šifrování se podobá principu Diffie–Hellmanovy výměny klíčů (předpokládáme, že Alice započne komunikaci):
Alice zvolí eliptickou křivku s celočíselnými koeficienty mod p (které také zvolí). Dále vybere na křivce bod P.
Nyní vybere náhodné přirozené číslo a vypočte hodnotu A = a × P. Hodnotu A, jakož i definici křivky (tj. koeficienty a hodnotu p) zašle Bobovi, představují veřejný klíč, privátní klíč je pouze hodnota a.
Bob po přijetí parametrů pracuje se stejnou křivkou, zvolí si náhodné číslo b a vypočítá bod B = b × P. Tuto hodnotu (tj. bod B) zašle zpátky Alici, privátní klíč Boba je opět pouze hodnota b.
Oba nyní mohou vypočítat společný tajný klíč K (též bod eliptické křivky).
Alice jej vypočte jako: K = a × B
Bob jej vypočte jako: K = b × A
(funguje to s ohledem na jednoduchý důkaz: K = a × B = ab × P = ba × P = b × A = K)
Tím algoritmus výměny klíčů končí.
Pro další pěkné čtení včetně ilustrací (v anglickém jazyce) doporučuji navštívit stránku, kterou vytvořila paní Andrea Corbellini, viz ZDE.