Schema lui ElGamal

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 mai 2018; verificările necesită 43 de modificări .

Schema Elgamal este un criptosistem cu cheie publică bazat pe dificultatea de a calcula logaritmi discreti într-un câmp finit . Criptosistemul include un algoritm de criptare și un algoritm de semnătură digitală. Schema ElGamal stă la baza fostelor standarde de semnătură digitală din Statele Unite ( DSA ) și Rusia ( GOST R 34.10-94 ).

Schema a fost propusă de Taher El-Gamal în 1985 . [1] ElGamal a dezvoltat o variantă a algoritmului Diffie-Hellman . El a îmbunătățit sistemul Diffie-Hellman și a obținut doi algoritmi care au fost folosiți pentru criptare și pentru autentificare. Spre deosebire de RSA, algoritmul ElGamal nu a fost brevetat și, prin urmare, a devenit o alternativă mai ieftină, deoarece nu erau necesare taxe de licență. Se crede că algoritmul este acoperit de brevetul Diffie-Hellman.

Generare cheie

Se generează un număr prim aleatoriu . $p$
Se alege un număr întreg - rădăcina primitivă . $g$ $p$
Un număr întreg aleatoriu este ales astfel încât . $X$ $(1<x<p-1)$
Calculat . $y=g^{x}{\bmod {p}}$
Cheia publică este , cheia privată este . $(y,g,p)$ $X$

Lucrul în modul criptat

Sistemul de criptare ElGamal este de fapt una dintre modalitățile de a genera chei publice Diffie-Hellman . Criptarea ElGamal nu trebuie confundată cu algoritmul de semnătură digitală ElGamal.

Criptare

Mesajul trebuie să fie mai mic de . Mesajul este criptat după cum urmează: $M$ $p$

Se alege cheia de sesiune — un întreg coprim aleatoriu cu , astfel încât . $(p - 1)$ $k$ $1<k<p-1$
Numerele și sunt calculate . $a=g^{k}{\bmod {p)}$ $b=y^{k}M{\bmod {p}}$
O pereche de numere este un text cifrat . $(a,b)$

Este ușor de observat că lungimea textului cifrat în schema ElGamal este de două ori mai mare decât lungimea mesajului original . $M$

Decriptare

Cunoscând cheia privată , mesajul original poate fi calculat din textul cifrat folosind formula: $X$ $(a,b)$

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

În același timp, este ușor de verificat

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

prin urmare

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

Pentru calcule practice, următoarea formulă este mai potrivită:

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

Schema de criptare

Exemplu

Criptare
1. Să presupunem că vrem să criptăm un mesaj . $M=5$
2. Să generăm cheile:
  1. Lasă . Să alegem un număr întreg aleatoriu astfel încât . $p=11,g=2$ $x=8$ $X$ $1<x<p$
  2. Să calculăm . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Deci cheia publică este 3 și cheia privată este numărul . $(p,g,y)=(11,2,3)$ $x=8$
3. Alegeți un număr întreg aleatoriu astfel încât 1 < k < (p − 1). Lasă . $k$ $k=9$
4. Calculăm numărul . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Calculăm numărul . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. Perechea rezultată este textul cifrat. $(a,b)=(6,9)$
Decriptare
1. Trebuie să primiți un mesaj folosind un text cifrat cunoscut și o cheie privată . $M=5$ $(a,b)=(6,9)$ $x=8$
2. Calculăm M cu formula: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Am primit mesajul original . $M=5$

Deoarece o variabilă aleatorie este introdusă în schema ElGamal , cifrul ElGamal poate fi numit cifr de substituție cu mai multe valori. Datorită caracterului aleatoriu al alegerii numărului, o astfel de schemă este numită și schemă de criptare probabilistică. Natura probabilistică a criptării este un avantaj pentru schema ElGamal, deoarece schemele de criptare probabilistică prezintă o putere mai mare în comparație cu schemele cu un proces de criptare specific. Dezavantajul schemei de criptare ElGamal este că textul cifrat este de două ori mai lung decât textul simplu. Pentru o schemă de criptare probabilistică, mesajul în sine și cheia nu definesc în mod unic textul cifrat. În schema ElGamal, este necesar să folosiți diferite valori ale unei variabile aleatorii pentru a cripta diferite mesaje și . Dacă utilizați același lucru , atunci pentru textele cifrate corespunzătoare și relația este îndeplinită . Din această expresie se poate calcula cu ușurință , dacă se știe . $k$ $k$ $M$ $k$ $M$ $M'$ $k$ $(a,b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $M'$ $M$

Lucrul în modul semnătură

Semnătura digitală servește pentru a permite identificarea modificărilor datelor și pentru a stabili identitatea semnatarului. Destinatarul unui mesaj semnat poate folosi o semnătură digitală pentru a dovedi unei terțe părți că semnătura a fost într-adevăr făcută de expeditor. Când lucrați în modul semnătură, se presupune că există o funcție hash fixă , ale cărei valori se află în intervalul . $h(\cdot )$ $\left(1,p-1\dreapta)$

Semnături mesaj

Pentru a semna un mesaj , se efectuează următoarele operații: $M$

Rezumatul mesajului este calculat : (funcția Hash poate fi oricare). $M$ $m=h(M).$
Un număr aleator coprim cu este ales și calculat $1<k<p-1$ $p-1$ $r=g^{k}\,{\bmod {\,}}p.$
Se calculează numărul , unde este modul invers multiplicativ , care poate fi găsit, de exemplu, folosind algoritmul Euclid extins . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
Semnătura mesajului este perechea . $M$ $\left(r,s\dreapta)$

Verificarea semnăturii

Cunoscând cheia publică , semnătura mesajului este verificată după cum urmează: $\left(p,g,y\dreapta)$ $\left(r,s\dreapta)$ $M$

Se verifică fezabilitatea condiţiilor: şi . $0<r<p$ $0<s<p-1$
Dacă cel puțin unul dintre ele eșuează, atunci semnătura este considerată nevalidă.
Rezumatul este calculat $m=h(M).$
O semnătură este considerată validă dacă se face o comparație: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Verificarea corectitudinii

Algoritmul considerat este corect în sensul că semnătura calculată conform regulilor de mai sus va fi acceptată în momentul verificării.

Transformând definiția , avem $s$

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

Mai mult, din Mica Teoremă a lui Fermat rezultă că

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

Exemplu

Semnătura mesajului.
1. Să presupunem că vrem să semnăm un mesaj . $M=baaqab$
2. Să generăm cheile:
  1. Lasă variabilele să fie cunoscute unei comunități. $p=23$ $g=5$
  2. Cheia secretă este un număr întreg aleatoriu astfel încât . $x=7$ $X$ $1<x<p$
  3. Calculați cheia publică : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Deci cheia publică este 3 . $(p,g,y)=(23,5,17)$
3. Acum calculăm funcția hash: . $h(M)=h(baaqab)=m=3$
4. Să alegem un număr întreg aleatoriu astfel încât condiția să fie îndeplinită . Lasă . $k$ $1<k<p-1$ $k=5$
5. Calculați r = g^k mod p = 5^5 mod 23 = 20.
6. Găsim . Un astfel de număr există deoarece GCD . Poate fi găsit folosind algoritmul extins Euclid. obține $k^{-1)$ $(k,p-1)=1$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. Găsirea unui număr . Primim pentru că $s\,\equiv \,(m-xr)k^{{-1}}{\pmod {p-1}}$ $s=21$ $s=\,(3-7\cdot 20)5^{-1}{\pmod {22}}=21$
8. Așadar, am semnat mesajul: . $<baaqab,20,21>$

Autentificarea mesajului primit.
1. Calculăm funcția hash: . $h(M)=h(baaqab)=m=3$
2. Să verificăm comparația . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Calculați partea stângă modulo 23: . $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Calculați partea dreaptă modulo 23: . $5^{3}{\bmod {2}}3=10$
5. Deoarece părțile din dreapta și din stânga sunt egale, aceasta înseamnă că semnătura este corectă.

Principalul avantaj al schemei de semnătură digitală ElGamal este capacitatea de a genera semnături digitale pentru un număr mare de mesaje folosind o singură cheie secretă. Pentru ca un atacator să falsească o semnătură, el trebuie să rezolve probleme matematice complexe cu găsirea logaritmului în câmp . Ar trebui făcute mai multe comentarii:

\mathbb {Z} _{p}

Numărul aleatoriu ar trebui să fie distrus imediat după calcularea semnăturii, deoarece dacă un atacator cunoaște numărul aleatoriu și semnătura în sine, atunci poate găsi cu ușurință cheia secretă folosind formula: și falsează complet semnătura. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

Numărul trebuie să fie aleatoriu și nu trebuie să fie duplicat pentru semnături diferite obținute cu aceeași valoare a cheii secrete. $k$

Folosirea plierii se explică prin faptul că protejează semnătura de enumerarea mesajelor în funcție de valorile semnăturii cunoscute de atacator. Exemplu: dacă alegeți numere aleatoare care îndeplinesc condițiile , gcd(j,p-1)=1 și presupuneți că $m=h(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)$

este ușor să verificați dacă perechea este semnătura digitală corectă pentru mesaj . $(r,s)$ $x=M$

Semnătura digitală a ElGamal a devenit un exemplu de construcție a altor semnături care sunt similare în proprietățile lor. Ele se bazează pe comparația: , în care triplul ia valorile uneia dintre permutările ±r, ±s și ±m pentru o anumită alegere de semne. De exemplu, schema originală ElGamal este obținută cu , , . Standardele de semnătură digitală din SUA și Rusia se bazează pe acest principiu de construire a unei semnături. În DSS american (Standardul de semnătură digitală), sunt utilizate valorile , , , iar în standardul rus: , , . $y^{A}\cdot r^{B}=g^{C}(modp)$ $(A,B,C)$ $A=r$ $B=s$ $C=m$ $A=r$ $B=-s$ $C=m$ $A=-x$ $B=-m$ $C=s$
Un alt avantaj este capacitatea de a reduce lungimea semnăturii prin înlocuirea unei perechi de numere cu o pereche de numere ), unde este un simplu divizor al numărului . În acest caz, comparația pentru verificarea semnăturii modulo ar trebui înlocuită cu o nouă comparație modulo : . Acest lucru se face în American DSS (Digital Signature Standard). $(s,m)$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(p-1)$ $p$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

Puterea și caracteristicile criptografice

În prezent, criptosistemele cu cheie publică sunt considerate cele mai promițătoare. Acestea includ schema ElGamal, a cărei putere criptografică se bazează pe complexitatea de calcul a problemei logaritmului discret , unde, având în vedere p , g și y , este necesar să se calculeze x care satisface comparația:

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

GOST R34.10-1994 , adoptat în 1994 în Federația Rusă, care reglementa procedurile de generare și verificare a semnăturii digitale electronice, se baza pe schema ElGamal. Din 2001, noul GOST R 34.10-2001 a fost utilizat, folosind aritmetica curbelor eliptice definite pe câmpuri Galois simple . Există un număr mare de algoritmi bazați pe schema ElGamal: acestea sunt DSA , ECDSA , algoritmi KCDSA, schema Schnorr .

Comparația unor algoritmi:

Algoritm	Cheie	Scop	Rezistență criptografică, MIPS	Note
RSA	Până la 4096 de biți	Criptare și semnare	2.7•10 28 pentru cheie de 1300 de biți	Bazat pe dificultatea problemei de factorizare a numărului mare ; unul dintre primii algoritmi asimetrici. Inclus în multe standarde
ElGamal	Până la 4096 de biți	Criptare și semnare	Pentru aceeași lungime a cheii, puterea criptografică este egală cu RSA, adică 2.7•10 28 pentru cheie de 1300 de biți	Bazat pe problema dificilă a calculării logaritmilor discreti într-un câmp finit; vă permite să generați rapid chei fără a compromite securitatea. Folosit în algoritmul de semnătură digitală al standardului DSA DSS
DSA	Până la 1024 de biți	Doar semnătura		Bazat pe dificultatea problemei logaritmului discret într-un câmp finit ; acceptat ca stat standard american; utilizat pentru comunicații secrete și neclasificate; Dezvoltatorul este NSA.
ECDSA	Până la 4096 de biți	Criptare și semnare	Rezistența criptografică și viteza de operare sunt mai mari decât cele ale RSA	Direcția modernă. Dezvoltat de mulți matematicieni de seamă

Note

↑ Elgamal, 1985 .

Literatură

Elgamal T. Un criptosistem cu cheie publică și o schemă de semnătură bazată pe logaritmi discreti, un criptosistem cu cheie publică și o schemă de semnătură bazată pe logaritmi discreti // IEEE Trans . inf. Teorie / 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. Fundamentele criptografiei.[ clarifica ]
B. A. Forouzan. Schema de semnătură digitală ElGamal // Gestionarea cheilor de criptare și securitatea rețelei / Per. A. N. Berlin. - Curs de curs.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 Schema de semnătură ElGamal // Handbook of Applied Cryptography (engleză) - CRC Press , 1996. - 816 p. — ( Matematică discretă și aplicațiile sale ) — ISBN 978-0-8493-8523-0

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP