ElGamal séma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. május 10-én felülvizsgált verziótól ; az ellenőrzések 43 szerkesztést igényelnek .

Az Elgamal-séma egy nyilvános kulcsú kriptorendszer , amely a diszkrét logaritmusok véges mezőben történő kiszámításának nehézségén alapul . A kriptorendszer tartalmaz egy titkosítási algoritmust és egy digitális aláírási algoritmust. Az ElGamal-séma a korábbi digitális aláírási szabványok alapja az Egyesült Államokban ( DSA ) és Oroszországban ( GOST R 34.10-94 ).

A sémát Taher El-Gamal javasolta 1985 - ben . [1] ElGamal kifejlesztette a Diffie-Hellman algoritmus egy változatát . Javította a Diffie-Hellman rendszert, és kapott két algoritmust, amelyeket titkosításra és hitelesítésre használtak. Az RSA-val ellentétben az ElGamal algoritmust nem szabadalmazták, így olcsóbb alternatívává vált, mivel nem kellett licencdíjat fizetni. Úgy gondolják, hogy az algoritmus a Diffie-Hellman szabadalom hatálya alá tartozik.

Kulcsgenerálás

Egy véletlenszerű prímszám generálódik . $p$
Egy egész szám van kiválasztva - a primitív gyök . $g$ $p$
Egy véletlenszerű egész számot választunk úgy, hogy . $x$ $(1<x<p-1)$
Kiszámolva . $y=g^{x}{\bmod {p}}$
A nyilvános kulcs , a privát kulcs pedig . ${\megjelenítési stílus (y,g,p)}$ $x$

Titkosított módban végzett munka

Az ElGamal titkosítási rendszer valójában az egyik módja a Diffie-Hellman nyilvános kulcsok előállításának . Az ElGamal titkosítás nem tévesztendő össze az ElGamal digitális aláírási algoritmussal.

Titkosítás

Az üzenetnek kisebbnek kell lennie, mint . Az üzenet a következőképpen van titkosítva: $M$ $p$

A szekciókulcs kerül kiválasztásra — egy véletlenszerű egész szám koprím -val , úgy , hogy . $(p - 1)$ $k$ $1<k<p-1$
A és számok kiszámítása . $a=g^{k}{\bmod {p))$ $b=y^{k}M{\bmod {p}}$
A számpár titkosított szöveg . $(a,b)$

Könnyen belátható, hogy az ElGamal sémában a rejtjelezett szöveg hossza kétszerese az eredeti üzenet hosszának . $M$

Dekódolás

A titkos kulcs ismeretében az eredeti üzenet a rejtjelezett szövegből a következő képlet segítségével számítható ki : $x$ $(a,b)$

M=b(a^{x})^{-1}{\bmod {p)).

Ugyanakkor ez könnyen ellenőrizhető

(a^{x})^{-1}=g^{-kx}{\bmod {p))

és ezért

b(a^{x})^{-1}=(y^{k}M)g^{-xk}\equiv (g^{xk}M)g^{-xk}\equiv M {\pmod {p}}

A gyakorlati számításokhoz a következő képlet alkalmasabb:

M=b(a^{x})^{-1}=ba^{(p-1-x)}{\pmod {p))

Titkosítási séma

Példa

Titkosítás
1. Tegyük fel, hogy titkosítani szeretnénk egy üzenetet . $M=5$
2. Létrehozzuk a kulcsokat:
  1. Hadd . Válasszunk egy véletlenszerű egész számot úgy, hogy . $p=11,g=2$ $x=8$ $x$ $1<x<p$
  2. Számoljunk . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Tehát a nyilvános kulcs 3 , a privát kulcs pedig a szám . ${\megjelenítési stílus (p,g,y)=(11,2,3)}$ $x=8$
3. Válasszunk egy véletlenszerű egész számot úgy, hogy 1 < k < (p − 1). Hadd . $k$ $k=9$
4. Kiszámoljuk a számot . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Kiszámoljuk a számot . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. A kapott pár a titkosított szöveg. ${\megjelenítési stílus (a,b)=(6,9)}$
Dekódolás
1. Ismert titkosított szöveget és privát kulcsot használó üzenetet kell fogadnia . $M=5$ ${\megjelenítési stílus (a,b)=(6,9)}$ $x=8$
2. Az M-et a következő képlettel számítjuk ki: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Megkaptam az eredeti üzenetet . $M=5$

Mivel az ElGamal-sémába egy valószínűségi változó kerül be , az ElGamal-rejtjel többértékű helyettesítési rejtjelnek nevezhető. A számválasztás véletlenszerűsége miatt az ilyen sémát valószínűségi titkosítási sémának is nevezik. A titkosítás valószínűségi jellege az ElGamal séma előnye, mivel a valószínűségi titkosítási sémák erősebbek, mint egy adott titkosítási eljárást alkalmazó sémák. Az ElGamal titkosítási séma hátránya, hogy a titkosított szöveg kétszerese a nyílt szövegnek. Valószínűségi titkosítási séma esetén maga az üzenet és a kulcs nem határozza meg egyértelműen a rejtjelezett szöveget. Az ElGamal sémában egy véletlen változó különböző értékeit kell használni a különböző üzenetek titkosításához és . Ha ugyanazt használod , akkor a megfelelő rejtjelezett szövegekre és a kapcsolat teljesül . Ebből a kifejezésből könnyen kiszámolható , ha tudja . $k$ $k$ $M$ $k$ $M$ $M'$ $k$ $(a,b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $M'$ $M$

Munka aláírás módban

A digitális aláírás az adatváltozások azonosítását és az aláíró személyazonosságának megállapítását szolgálja. Az aláírt üzenet címzettje digitális aláírással bizonyíthatja harmadik félnek, hogy az aláírást valóban a feladó írta. Ha aláírási módban dolgozik, feltételezzük, hogy van egy rögzített hash függvény , amelynek értékei az intervallumban vannak . $h(\cdot )$ $\bal(1,p-1\jobb)$

Üzenet aláírások

Egy üzenet aláírásához a következő műveleteket kell végrehajtani: $M$

Az üzenet kivonatának kiszámítása : (A hash függvény bármilyen lehet). $M$ $m=h(M).$
Kiválasztunk és kiszámítunk egy véletlenszám -koprímet $1<k<p-1$ $p-1$ $r=g^{k}\,{\bmod {\,}}p.$
A szám kiszámítása , ahol a multiplikatív inverz modulo , amely megtalálható például a kiterjesztett Euklidész algoritmus segítségével . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
Az üzenet aláírása a pár . $M$ $\left(r,s\jobb)$

Aláírás ellenőrzése

A nyilvános kulcs ismeretében az üzenet aláírását a következőképpen ellenőrizzük: $\left(p,g,y\jobb)$ $\left(r,s\jobb)$ $M$

A feltételek teljesíthetőségét ellenőrzik: és . $0<r<p$ $0<s<p-1$
Ha legalább az egyik sikertelen, akkor az aláírás érvénytelennek minősül.
A kivonat kiszámítása megtörténik $m=h(M).$
Az aláírás érvényesnek minősül, ha összehasonlítják: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Helyességi ellenőrzés

A figyelembe vett algoritmus abban az értelemben helyes, hogy a fenti szabályok szerint számított aláírást az ellenőrzéskor elfogadjuk.

Átalakítva a definíciót , megvan $s$

m\,\equiv \,xr+sk{\pmod {p-1)).

Továbbá Fermat kis tételéből az következik, hogy

{\begin{aligned}g^{m}&\equiv g^{xr}g^{ks}\\&\equiv (g^{x})^{r}(g^{k}) ^{s}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{igazított}}

Példa

Üzenet aláírása.
1. Tegyük fel, hogy alá akarunk írni egy üzenetet . $M=baaqab$
2. Létrehozzuk a kulcsokat:
  1. Ismertesse a változókat valamilyen közösséggel. $p=23$ $g=5$
  2. A titkos kulcs egy véletlenszerű egész szám , amely . $x=7$ $x$ $1<x<p$
  3. Számítsa ki a nyilvános kulcsot : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Tehát a nyilvános kulcs a 3 . ${\megjelenítési stílus (p,g,y)=(23,5,17)}$
3. Most kiszámítjuk a hash függvényt: . $h(M)=h(baaqab)=m=3$
4. Válasszunk egy véletlenszerű egész számot úgy, hogy a feltétel teljesüljön . Hadd . $k$ $1<k<p-1$ $k=5$
5. Számítsuk ki r = g^k mod p = 5^5 mod 23 = 20.
6. találunk . Létezik ilyen szám, mert a GCD . Megtalálható a kiterjesztett Euklidész algoritmussal. Kap $k^{-1}$ $(k,p-1)=1$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. Szám keresése . Kapunk, mert $s\,\equiv \,(m-xr)k^{{-1}}{\pmod {p-1}}$ $s=21$ $s=\,(3-7\cdot 20)5^{-1}{\pmod {22}}=21$
8. Tehát aláírtuk az üzenetet: . $<baaqab,20,21>$

A fogadott üzenet hitelesítése.
1. Kiszámoljuk a hash függvényt: . $h(M)=h(baaqab)=m=3$
2. Nézzük az összehasonlítást . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Számítsa ki a bal oldali modulo 23: . $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Számítsa ki a jobb oldali modulo 23: . $5^{3}{\bmod {2}}3=10$
5. Mivel a jobb és a bal rész egyenlő, ez azt jelenti, hogy az aláírás helyes.

Az ElGamal digitális aláírási séma fő előnye, hogy képes digitális aláírást generálni nagyszámú üzenethez egyetlen titkos kulcs használatával. Ahhoz, hogy a támadó aláírást hamisíthasson, összetett matematikai problémákat kell megoldania a logaritmus mezőben történő megtalálásával . Számos megjegyzést kell tenni:

\mathbb {Z} _{p}

A véletlen számot az aláírás kiszámítása után azonnal meg kell semmisíteni, mert ha a támadó ismeri a véletlen számot és magát az aláírást, akkor könnyen megtalálja a titkos kulcsot a következő képlet segítségével: és teljesen meghamisítja az aláírást. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

A számnak véletlenszerűnek kell lennie, és nem szabad megkettőznie ugyanazzal a titkos kulcsértékkel kapott különböző aláírásokat. $k$

A hajtogatást az magyarázza, hogy megvédi az aláírást az üzenetek felsorolásától a támadó által ismert aláírási értékek szerint. Példa: ha olyan véletlen számokat választ , amelyek megfelelnek a feltételeknek , gcd(j,p-1)=1, és feltételezzük, hogy ${\megjelenítési stílus m=ó(M)}$ $i,j$ $0<i<{p-1},0<j<{p-1}$ $r=g^{i}\cdot y^{-j}{\bmod {p}}$ $s=r\cdot j^{-1}{\bmod {(}}p-1)$ $m=r\cdot i\cdot j^{-1}{\bmod {(}}p-1)$

könnyen ellenőrizhető, hogy a pár a megfelelő digitális aláírás az üzenethez . $(r,s)$ $x=M$

Az ElGamal digitális aláírása más, tulajdonságaikban hasonló aláírások felépítésének példája lett. A következő összehasonlításon alapulnak: , amelyben a hármas felveszi az egyik ±r, ±s és ±m permutáció értékét valamilyen előjelválasztáshoz. Például az eredeti ElGamal sémát a , , -vel kapjuk meg.Az USA és Oroszország digitális aláírási szabványai az aláírás létrehozásának ezen az elvén alapulnak. Az amerikai DSS-ben (Digital Signature Standard) a , , , értékeket használják , az orosz szabványban pedig: , , . $y^{A}\cdot r^{B}=g^{C}(modp)$ ${\megjelenítési stílus (A,B,C)}$ $A=r$ $B=s$ $C=m$ $A=r$ $B=-s$ $C=m$ $A=-x$ $B=-m$ $C=s$
Egy másik előny az aláírás hosszának csökkentése , ha egy számpárt egy számpárra cserélünk ), ahol a szám néhány egyszerű osztója . Ebben az esetben a modulo aláírás-ellenőrzés összehasonlítását egy új összehasonlító modulo-ra kell cserélni : . Ez az amerikai DSS-ben (Digital Signature Standard) történik. ${\megjelenítési stílus (s,m)}$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(p-1)$ $p$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

A kriptográfiai erősség és jellemzők

Jelenleg a nyilvános kulcsú kriptorendszerek számítanak a legígéretesebbnek. Ezek közé tartozik az ElGamal-séma, amelynek kriptográfiai erőssége a diszkrét logaritmus - probléma számítási bonyolultságán alapul , ahol p , g és y mellett ki kell számítani x -et , amely kielégíti az összehasonlítást:

y\equiv g^{x}{\pmod {p)).

Az Orosz Föderációban 1994 -ben elfogadott GOST R34.10-1994 , amely szabályozta az elektronikus digitális aláírás generálására és ellenőrzésére vonatkozó eljárásokat, az ElGamal sémán alapult. 2001 óta használják az új GOST R 34.10-2001 szabványt , amely az egyszerű Galois-mezőkön meghatározott elliptikus görbék aritmetikáját használja . Az ElGamal sémára épülő algoritmusok nagy száma létezik: ezek a DSA , ECDSA , KCDSA algoritmusok, Schnorr séma .

Néhány algoritmus összehasonlítása:

Algoritmus	Kulcs	Célja	Kriptográfiai ellenállás, MIPS	Megjegyzések
RSA	Akár 4096 bit	Titkosítás és aláírás	2,7•10 28 1300 bites kulcshoz	A nagyszámú faktorizációs probléma nehézsége alapján ; az egyik első aszimmetrikus algoritmus. Számos szabványban szerepel
ElGamal	Akár 4096 bit	Titkosítás és aláírás	Ugyanazon kulcshosszúság esetén a kriptográfiai erősség megegyezik az RSA-val, azaz. 2,7•10 28 1300 bites kulcshoz	A diszkrét logaritmusok véges mezőben történő kiszámításának nehéz feladatán alapul; lehetővé teszi a kulcsok gyors generálását a biztonság veszélyeztetése nélkül. A DSA szabványú DSS digitális aláírási algoritmusában használatos
DSA	Akár 1024 bit	Csak aláírás		A diszkrét logaritmus -feladat nehézsége alapján véges mezőben ; államként fogadják el amerikai szabvány; titkos és nem minősített kommunikációra használják; A fejlesztő az NSA.
ECDSA	Akár 4096 bit	Titkosítás és aláírás	A kriptográfiai ellenállás és a működési sebesség magasabb, mint az RSA-é	Modern irány. Számos vezető matematikus fejlesztette ki

Jegyzetek

↑ Elgamal, 1985 .

Irodalom

Elgamal T. Egy nyilvános kulcsú kriptorendszer és egy diszkrét logaritmuson alapuló aláírási séma, egy nyilvános kulcsú kriptorendszer és egy diszkrét logaritmuson alapuló aláírási séma // IEEE Trans . inf. Elmélet / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - P. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Alferov A.P., Zubov A.Yu., Kuzmin A.S., Cheremushkin A.V. A kriptográfia alapjai.[ pontosítás ]
B. A. Forouzan. ElGamal digitális aláírási séma // Titkosítókulcs-kezelés és hálózati biztonság / Per. A. N. Berlin. - Előadó tanfolyam.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 Az ElGamal aláírási séma // Handbook of Applied Cryptography (angolul) - CRC Press , 1996. - 816 p. — ( Diszkrét matematika és alkalmazásai ) — ISBN 978-0-8493-8523-0

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya