ElGamal

Ten artykuł od 2012-12 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

ElGamal to jeden z dwóch najważniejszych algorytmów kryptografii asymetrycznej (obok RSA). System jest oparty na trudności problemu logarytmu dyskretnego w ciele liczb całkowitych modulo duża liczba pierwsza. Algorytm w połowie lat 80. XX wieku przedstawił Egipcjanin Taher Elgamal^[1].

Algorytm ElGamala umożliwia szyfrowanie oraz obsługę 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 grupy multiplikatywnej ciała ${\displaystyle Z_{p}}$ używamy grupy punktów na krzywej eliptycznej.

Szyfrowanie

Generowanie klucza: wybieramy dowolną liczbę pierwszą ${\displaystyle p,}$ dowolny generator ${\displaystyle \alpha }$ podgrupy multiplikatywnej, tzn. taki element, którego rząd jest równy ${\displaystyle p-1,}$ oraz dowolne ${\displaystyle k}$ takie, że: ${\displaystyle 1<k<p.}$ Liczymy ${\displaystyle \beta {:}}$

${\displaystyle \beta =\alpha ^{k}\mod p,}$

co potrafimy zrobić szybko za pomocą potęgowania przez podnoszenie do kwadratu.

Gdyby ${\displaystyle \alpha }$ było dowolne to przykładowo dla:

${\displaystyle p=41,\ \alpha =14,\ k=16}$ otrzymalibyśmy:

${\displaystyle \beta =14^{16}\mod \ 41=1,}$

co spowodowałoby, że kryptosystem byłby bezużyteczny (gdyż przy szyfrowaniu zawsze otrzymywalibyśmy 1).

Następnie publikujemy ${\displaystyle (p,\alpha ,\beta )}$ jako klucz publiczny i zachowujemy ${\displaystyle (p,\alpha ,\beta ,k)}$ jako klucz prywatny.

Szyfrowanie: mając do zaszyfrowania wiadomość ${\displaystyle m,}$ przedstawiamy ją jako element grupy [${\displaystyle 1<m<p-1}$] wybieramy losowo liczbę ${\displaystyle x}$ i liczymy (modulo ${\displaystyle p}$)

${\displaystyle (\alpha ^{x},m\times \beta ^{x}).}$

Deszyfrowanie: podnosimy otrzymane ${\displaystyle \alpha ^{x}}$ do potęgi ${\displaystyle k{:}}$

${\displaystyle \left(\alpha ^{x}\right)^{k}=\alpha ^{kx}=\left(\alpha ^{k}\right)^{x}=\beta ^{x}.}$

Następnie znajdujemy odwrotność ${\displaystyle \beta ^{x}}$ (nadal modulo ${\displaystyle p}$) rozszerzonym algorytmem Euklidesa:

${\displaystyle \gamma \beta ^{x}+\delta p=1,}$

${\displaystyle \gamma \beta ^{x}\equiv 1\mod p,}$

${\displaystyle \gamma \equiv (\beta ^{x})^{-1}\mod p.}$

W końcu dzielimy ${\displaystyle m\times \beta ^{x}}$ przez ${\displaystyle \beta ^{x},}$ czyli mnożymy przez jej odwrotność – ${\displaystyle \gamma {:}}$

${\displaystyle (m\times \beta ^{x})\times \gamma \equiv m\times (\beta ^{x}\times \gamma )\equiv m\times 1\equiv m\mod p.}$

Podpis cyfrowy

Klucz jest generowany w ten sam sposób.

Żeby wygenerować podpis wiadomości ${\displaystyle m,}$ losujemy liczbę ${\displaystyle r}$ i liczymy:

${\displaystyle y=\alpha ^{r}}$(mod p),

${\displaystyle s=(H(m)-ky)r^{-1}}$ (mod(p-1)), gdzie ${\displaystyle H}$ jest funkcją haszującą.

Podpisem jest para ${\displaystyle (y,s)}$

Żeby zweryfikować podpis, sprawdzamy równanie:

${\displaystyle \beta ^{y}y^{s}=\alpha ^{H(m)}.}$

Dla prawidłowego podpisu będzie się zgadzać:

${\displaystyle \alpha ^{ky}\alpha ^{rs}=\alpha ^{H(m)},}$

${\displaystyle \alpha ^{ky+r\left((H(m)-ky)r^{-1}\right)}=\alpha ^{H(m)},}$

${\displaystyle \alpha ^{ky+H(m)-ky}=\alpha ^{H(m)},}$

${\displaystyle \alpha ^{H(m)}=\alpha ^{H(m)}.}$

Ważne jest zachowanie tajności wylosowanego ${\displaystyle r.}$ Jeśli ${\displaystyle r}$ byłoby znane, to można by odzyskać klucz prywatny z podpisu:

${\displaystyle y^{-1}\left(H(m)-sr\right)=y^{-1}\left(H(m)-(H(m)-ky)r^{-1}r\right)=y^{-1}ky=k.}$

Poziom bezpieczeństwa

Jeżeli rząd grupy multiplikatywnej jest iloczynem liczb pierwszych, spośród których nawet jedna nie jest odpowiednio duża, istnieje efektywna metoda obliczania wykładnika. Nie jest znana ogólna metoda szybkiego liczenia logarytmu dyskretnego, więc nie wiemy, jak za pomocą ${\displaystyle \alpha ^{x}}$ i ${\displaystyle \alpha }$ uzyskać ${\displaystyle x,}$ 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 ${\displaystyle \alpha ,}$ ${\displaystyle \beta ,}$ ${\displaystyle p}$ i ${\displaystyle \alpha ^{x},}$ ${\displaystyle m\times \beta ^{x}}$ (czyli klucz publiczny i szyfrogram wiadomości), jest w stanie odzyskać ${\displaystyle m,}$ obchodząc w jakiś sposób ten problem.

Referencje

• ElGamal encryption materiały naukowe Allison Chaney z Princeton (ang.)

Przypisy