Tekst źródłowy strony ElGamal

{{Dopracować|źródła=2012-12}}
'''ElGamal''' to jeden z dwóch najważniejszych [[Szyfr|algorytmów]] [[Kryptografia klucza publicznego|kryptografii asymetrycznej]] (obok [[RSA (kryptografia)|RSA]]). System jest oparty na trudności problemu [[logarytm dyskretny|logarytmu dyskretnego]] w [[Arytmetyka modularna|ciele liczb całkowitych modulo duża liczba pierwsza]]. Algorytm w połowie lat 80. XX wieku przedstawił [[Egipt|Egipcjanin]] [[Taher Elgamal]]<ref>[https://www.linkedin.com/in/taherelgamal/ Taher Elgamal] w serwisie [[LinkedIn]] {{lang|en}}.</ref>.

Algorytm ElGamala umożliwia [[Kryptografia klucza publicznego|szyfrowanie]] oraz obsługę [[podpis cyfrowy|podpisów cyfrowych]]. Setki modyfikacji algorytmu ElGamala (podobnie jak modyfikacje algorytmu RSA) mają różne inne zastosowania.

Na koncepcji algorytmu ElGamala jest też oparta [[kryptografia krzywych eliptycznych]] – w tym przypadku zamiast [[grupa multiplikatywna|grupy multiplikatywnej]] ciała <math>Z_p</math> używamy [[Krzywa eliptyczna|grupy punktów na krzywej eliptycznej]].

== Szyfrowanie ==
'''Generowanie klucza''': wybieramy dowolną liczbę pierwszą <math>p,</math> dowolną liczbę <math>\alpha</math> będącą [[Pierwiastek pierwotny|pierwiastkiem pierwotnym]] modulo <math>p</math> oraz dowolne całkowite <math>k</math> takie, że: <math>1 < k < p.</math><ref>[https://math.asu.edu/sample-ciphers  ElGamal] Część z serii dokumentów o algorytmach szyfrujących {{lang|en}}</ref>Liczymy <math>\beta{:}</math>
:: <math>\beta = \alpha^k \mod p,</math>

co potrafimy zrobić szybko za pomocą [[algorytm szybkiego potęgowania|potęgowania przez podnoszenie do kwadratu]].

<math>\alpha</math> jest wybierana w ten sposób, aby zapewnić równomierną dystrybucję <math>\alpha^k</math> (podobnie jak w [[Protokół Diffiego-Hellmana|protokole Diffiego-Hellmana]]<ref>[https://kulkarniamit.github.io/whatwhyhow/security/diffie-hellman-key-exchange.html#why-should-g-be-primitive-root-modulo-p] Wpis na what-why-how o protokole Diffiego-Hellmana {{lang|en}}</ref>).

Następnie publikujemy <math>(p, \alpha, \beta)</math> jako [[Kryptografia klucza publicznego|klucz publiczny]] i zachowujemy <math>(p, \alpha, \beta, k)</math> jako klucz prywatny.

'''Szyfrowanie''': mając do zaszyfrowania wiadomość <math>m,</math> przedstawiamy ją jako element grupy [<math>1 < m < p - 1</math>] wybieramy losowo liczbę <math>x</math> i liczymy (modulo <math>p</math>)
:: <math>(\alpha^x, m\times \beta^x).</math>

'''Deszyfrowanie''': podnosimy otrzymane <math>\alpha^x</math> do potęgi <math>k{:}</math>
:: <math>\left(\alpha^x\right)^k = \alpha^{kx} = \left(\alpha^k\right)^x = \beta^x.</math>

Następnie znajdujemy odwrotność <math>\beta^x</math> (nadal modulo <math>p</math>)
[[Algorytm Euklidesa|rozszerzonym algorytmem Euklidesa]]:
:: <math>\gamma \beta^x + \delta p = 1,</math>
:: <math>\gamma \beta^x \equiv 1 \mod p,</math>
:: <math>\gamma \equiv (\beta^x)^{-1} \mod p.</math>

W końcu dzielimy <math>m \times \beta^x</math> przez <math>\beta^x,</math> czyli mnożymy przez jej odwrotność – <math>\gamma{:}</math>
:: <math>(m \times \beta^x) \times \gamma \equiv m \times (\beta^x \times \gamma) \equiv m \times 1 \equiv m \mod p.</math>

== Podpis cyfrowy ==
Klucz jest generowany w ten sam sposób.

Żeby wygenerować podpis wiadomości <math>m,</math> losujemy liczbę <math>r</math> i liczymy:
:: <math>y = \alpha^r</math>'''(mod p)''',
:: <math>s = (H(m)-ky)r^{-1}</math> ('''mod(p-1))''', gdzie <math>H</math> jest [[Funkcja skrótu|funkcją haszującą]].

Podpisem jest para <math>(y,s)</math>

Żeby zweryfikować podpis, sprawdzamy równanie:
:: <math>\beta^y y^s = \alpha^{H(m)}.</math>

Dla prawidłowego podpisu będzie się zgadzać:
:: <math>\alpha^{ky} \alpha^{rs} = \alpha^{H(m)},</math>
:: <math>\alpha^{ky + r\left((H(m)-ky)r^{-1}\right)} = \alpha^{H(m)},</math>
:: <math>\alpha^{ky + H(m)- ky} = \alpha^{H(m)},</math>
:: <math>\alpha^{H(m)} = \alpha^{H(m)}.</math>

Ważne jest zachowanie tajności wylosowanego <math>r.</math> Jeśli <math>r</math> byłoby znane, to można by odzyskać klucz prywatny z podpisu:
:: <math>y^{-1}\left(H(m)-sr\right) = y^{-1}\left(H(m)-(H(m)-ky)r^{-1}r\right)=y^{-1}ky=k.</math>

== Poziom bezpieczeństwa ==
Jeżeli rząd grupy multiplikatywnej jest iloczynem [[Liczby pierwsze|liczb pierwszych]], spośród których nawet jedna nie jest odpowiednio duża, istnieje [[redukcja Pohliga-Hellmana|efektywna metoda]] obliczania wykładnika. Nie jest znana ogólna metoda szybkiego liczenia logarytmu dyskretnego, więc nie wiemy, jak za pomocą <math>\alpha^x</math> i <math>\alpha</math> uzyskać <math>x,</math> które w pełni wystarczyłoby do odszyfrowania wiadomości. Nie ma jednak dowodu, że taka nie istnieje. To ostatnie nie może raczej dziwić, gdyż takich dowodów nie ma dla żadnego znanego szyfru asymetrycznego.

Nie mamy jednak dowodu, że złamanie problemu logarytmu dyskretnego jest jedynym sposobem złamania tego szyfru. Być może istnieje szybki algorytm, który, znając <math>\alpha,</math> <math>\beta,</math> <math>p</math> i <math>\alpha^x,</math> <math>m\times\beta^x</math> (czyli [[Kryptografia klucza publicznego|klucz publiczny]] i [[szyfrogram (kryptografia)|szyfrogram wiadomości]]), jest w stanie odzyskać <math>m,</math> obchodząc w jakiś sposób ten problem.

== Przypisy ==
{{Przypisy}}

[[Kategoria:Algorytmy kryptograficzne]]