Ordning af ElGamal

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. maj 2018; checks kræver 43 redigeringer .

Elgamal - ordningen er et offentligt nøglekryptosystem baseret på vanskeligheden ved at beregne diskrete logaritmer i et begrænset felt . Kryptosystemet omfatter en krypteringsalgoritme og en digital signaturalgoritme. ElGamal-ordningen ligger til grund for de tidligere digitale signaturstandarder i USA ( DSA ) og Rusland ( GOST R 34.10-94 ).

Ordningen blev foreslået af Taher El-Gamal i 1985 . [1] ElGamal udviklede en variant af Diffie-Hellman-algoritmen . Han forbedrede Diffie-Hellman-systemet og opnåede to algoritmer, der blev brugt til kryptering og til autentificering. I modsætning til RSA var ElGamal-algoritmen ikke patenteret og blev derfor et billigere alternativ, da der ikke krævedes licensgebyrer. Algoritmen menes at være omfattet af Diffie-Hellman-patentet.

Nøglegenerering

Der genereres et tilfældigt primtal . $s$
Et heltal er valgt - den primitive rod . $g$ $s$
Et tilfældigt heltal vælges således, at . $x$ $(1<x<p-1)$
Beregnet . $y=g^{x}{\bmod {p}}$
Den offentlige nøgle er , den private nøgle er . $(y,g,p)$ $x$

Arbejder i krypteret tilstand

ElGamal-chiffersystemet er faktisk en af måderne at generere Diffie-Hellman offentlige nøgler på . ElGamal-kryptering må ikke forveksles med ElGamals digitale signaturalgoritme.

Kryptering

Beskeden skal være mindre end . Beskeden er krypteret som følger: $M$ $s$

Sessionsnøglen er valgt - et tilfældigt heltal coprime med , sådan at . $(s - 1)$ $k$ $1<k<p-1$
Tallene og er beregnet . $a=g^{k}{\bmod {p))$ $b=y^{k}M{\bmod {p}}$
Et par tal er en chiffertekst . $(a,b)$

Det er let at se, at længden af chifferteksten i ElGamal-skemaet er dobbelt så lang som den oprindelige besked . $M$

Dekryptering

Ved at kende den private nøgle kan den originale besked beregnes ud fra chifferteksten ved hjælp af formlen: $x$ $(a,b)$

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

Det er samtidig nemt at tjekke det

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

og derfor

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

Til praktiske beregninger er følgende formel mere egnet:

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

Krypteringsskema

Eksempel

Kryptering
1. Lad os sige, at vi vil kryptere en besked . $M=5$
2. Lad os generere nøglerne:
  1. Lad . Lad os vælge et tilfældigt heltal , sådan at . $p=11,g=2$ $x=8$ $x$ $1<x<p$
  2. Lad os beregne . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Så den offentlige nøgle er 3 og den private nøgle er nummer . $(p,g,y)=(11,2,3)$ $x=8$
3. Vælg et tilfældigt heltal , således at 1 < k < (p − 1). Lad . $k$ $k=9$
4. Vi beregner tallet . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Vi beregner tallet . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. Det resulterende par er chifferteksten. $(a,b)=(6,9)$
Dekryptering
1. Du skal modtage en besked ved hjælp af en kendt chiffertekst og privat nøgle . $M=5$ $(a,b)=(6,9)$ $x=8$
2. Vi beregner M ved formlen: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Fik den originale besked . $M=5$

Da en tilfældig variabel er indført i ElGamal-skemaet , kan ElGamal-chifferet kaldes en substitutionsciffer med flere værdier. På grund af tilfældigheden af valget af nummeret kaldes en sådan ordning også for en sandsynlig krypteringsordning. Den sandsynlige karakter af kryptering er en fordel for ElGamal-skemaet, da sandsynlighedskrypteringsskemaer udviser større styrke sammenlignet med skemaer med en specifik krypteringsproces. Ulempen ved ElGamal-krypteringsskemaet er, at chifferteksten er dobbelt så lang som almindelig tekst. For et probabilistisk krypteringsskema definerer selve meddelelsen og nøglen ikke entydigt chifferteksten. I ElGamal-skemaet er det nødvendigt at bruge forskellige værdier af en tilfældig variabel til at kryptere forskellige meddelelser og . Hvis du bruger det samme , er forholdet opfyldt for de tilsvarende chiffertekster . Ud fra dette udtryk kan man let regne , hvis man ved det . $k$ $k$ $M$ $k$ $M$ $M'$ $k$ $(a,b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $M'$ $M$

Arbejder i signaturtilstand

Den digitale signatur tjener til at gøre det muligt at identificere dataændringer og til at fastslå underskriverens identitet. Modtageren af en underskrevet besked kan bruge en digital signatur til at bevise over for en tredjepart, at signaturen faktisk er lavet af afsenderen. Når du arbejder i signaturtilstand, antages det, at der er en fast hash-funktion , hvis værdier ligger i intervallet . $h(\cdot )$ $\venstre(1,p-1\højre)$

Meddelelsessignaturer

For at underskrive en meddelelse udføres følgende handlinger: $M$

Beskedsammendraget beregnes : (Hash-funktionen kan være en hvilken som helst). $M$ $m=h(M).$
Et tilfældigt tal coprime med vælges og beregnes $1<k<p-1$ $p-1$ $r=g^{k}\,{\bmod {\,}}s.$
Tallet beregnes , hvor er den multiplikative inverse modulo , som for eksempel kan findes ved hjælp af den udvidede Euklidiske algoritme . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
Signaturen på beskeden er parret . $M$ $\venstre(r,s\højre)$

Signaturbekræftelse

Ved at kende den offentlige nøgle bekræftes meddelelsessignaturen som følger: $\venstre(p,g,y\højre)$ $\venstre(r,s\højre)$ $M$

Gennemførligheden af betingelserne kontrolleres: og . $0<r<p$ $0<s<p-1$
Hvis mindst én af dem mislykkes, betragtes signaturen som ugyldig.
Fordøjelsen beregnes $m=h(M).$
En signatur anses for gyldig, hvis der foretages en sammenligning: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Korrekthedskontrol

Den betragtede algoritme er korrekt i den forstand, at signaturen beregnet i henhold til ovenstående regler vil blive accepteret, når den er verificeret.

At transformere definitionen , har vi $s$

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

Yderligere følger det af Fermats lille sætning , at

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

Eksempel

Besked signatur.
1. Lad os sige, at vi vil underskrive en besked . $M=baaqab$
2. Lad os generere nøglerne:
  1. Lad variablerne være kendt for nogle samfund. $p=23$ $g=5$
  2. Den hemmelige nøgle er et tilfældigt heltal , sådan at . $x=7$ $x$ $1<x<p$
  3. Beregn den offentlige nøgle : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Så den offentlige nøgle er 3 . $(p,g,y)=(23,5,17)$
3. Nu beregner vi hash-funktionen: . $h(M)=h(baaqab)=m=3$
4. Lad os vælge et tilfældigt heltal , således at betingelsen er opfyldt . Lad . $k$ $1<k<p-1$ $k=5$
5. Beregn r = g^k mod p = 5^5 mod 23 = 20.
6. Vi finder . Et sådant tal eksisterer fordi GCD . Det kan findes ved hjælp af den udvidede Euclid-algoritme. Få $k^{-1}$ $(k,p-1)=1$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. At finde et nummer . Vi får pga $s\,\equiv \,(m-xr)k^{{-1}}{\pmod {p-1}}$ $s=21$ $s=\,(3-7\cdot 20)5^{-1}{\pmod {22}}=21$
8. Så vi underskrev beskeden: . $<baaqab,20,21>$

Godkendelse af den modtagne besked.
1. Vi beregner hash-funktionen: . $h(M)=h(baaqab)=m=3$
2. Lad os tjekke sammenligningen . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Beregn venstre side modulo 23 :. $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Beregn højre side modulo 23 :. $5^{3}{\bmod {2}}3=10$
5. Da højre og venstre del er ens, betyder det, at signaturen er korrekt.

Den største fordel ved ElGamals digitale signaturordning er evnen til at generere digitale signaturer til et stort antal meddelelser ved brug af kun én hemmelig nøgle. For at en angriber kan forfalske en signatur, skal han løse komplekse matematiske problemer med at finde logaritmen i feltet . Der skal fremsættes flere kommentarer:

\mathbb {Z} _{p}

Det tilfældige tal bør destrueres umiddelbart efter, at signaturen er beregnet, for hvis en angriber kender det tilfældige tal og selve signaturen, så kan han nemt finde den hemmelige nøgle ved hjælp af formlen: og fuldstændig falske signaturen. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

Nummeret skal være tilfældigt og må ikke duplikeres for forskellige signaturer opnået med den samme hemmelige nøgleværdi. $k$

Brugen af foldning forklares ved, at den beskytter signaturen mod opregning af meddelelser i henhold til signaturværdierne kendt af angriberen. Eksempel: hvis du vælger tilfældige tal , der opfylder betingelserne , gcd(j,p-1)=1 og antager, at $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)$

det er nemt at verificere, at parret er den rigtige digitale signatur for beskeden . $(r,s)$ $x=M$

ElGamals digitale signatur er blevet et eksempel på konstruktionen af andre signaturer, der ligner hinanden i deres egenskaber. De er baseret på sammenligningen: , hvor triplen tager værdierne af en af permutationerne ±r, ±s og ±m for nogle valg af tegn. For eksempel er den originale ElGamal-ordning opnået med , , , . De digitale signaturstandarder i USA og Rusland er baseret på dette princip om at konstruere en signatur. I den amerikanske DSS (Digital Signature Standard) bruges værdierne , , , og i den russiske standard: , , . $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$
En anden fordel er evnen til at reducere længden af signaturen ved at erstatte et par tal med et par tal ), hvor er en simpel divisor af tallet . I dette tilfælde bør sammenligningen for modulo signaturverifikation erstattes med en ny sammenligning modulo : . Dette gøres i den amerikanske DSS (Digital Signature Standard). $(s,m)$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(s-1)$ $s$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

Kryptografisk styrke og funktioner

I øjeblikket betragtes offentlige nøglekryptosystemer som de mest lovende. Disse inkluderer ElGamal-skemaet, hvis kryptografiske styrke er baseret på beregningskompleksiteten af det diskrete logaritmeproblem , hvor det, givet p , g og y , er påkrævet at beregne x , der opfylder sammenligningen:

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

GOST R34.10-1994 , vedtaget i 1994 i Den Russiske Føderation, som regulerede procedurerne for generering og verifikation af en elektronisk digital signatur, var baseret på ElGamal-ordningen. Siden 2001 har den nye GOST R 34.10-2001 været i brug ved at bruge aritmetikken af elliptiske kurver defineret over simple Galois-felter . Der er et stort antal algoritmer baseret på ElGamal-skemaet: disse er DSA , ECDSA , KCDSA-algoritmer, Schnorr-skema .

Sammenligning af nogle algoritmer:

Algoritme	Nøgle	Formål	Kryptografisk modstand, MIPS	Noter
RSA	Op til 4096 bit	Kryptering og signering	2,7•10 28 for 1300 bit nøgle	Baseret på sværhedsgraden af faktoriseringsproblemet med store tal ; en af de første asymmetriske algoritmer. Inkluderet i mange standarder
ElGamal	Op til 4096 bit	Kryptering og signering	For samme nøglelængde er den kryptografiske styrke lig med RSA, dvs. 2,7•10 28 for 1300 bit nøgle	Baseret på det vanskelige problem med at beregne diskrete logaritmer i et begrænset felt; giver dig mulighed for hurtigt at generere nøgler uden at gå på kompromis med sikkerheden. Anvendes i den digitale signaturalgoritme af DSA-standard DSS
DSA	Op til 1024 bit	Kun underskrift		Baseret på sværhedsgraden af det diskrete logaritmeproblem i et endeligt felt ; accepteret som stat amerikansk standard; bruges til hemmelig og uklassificeret kommunikation; Udvikleren er NSA.
ECDSA	Op til 4096 bit	Kryptering og signering	Kryptomodstand og operationshastighed er højere end RSA's	Moderne retning. Udviklet af mange førende matematikere

Noter

↑ Elgamal, 1985 .

Litteratur

Elgamal T. Et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer, et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - S. 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. Grundlæggende om kryptografi.[ afklare ]
B.A. Forouzan. ElGamal digital signaturordning // Håndtering af krypteringsnøgler og netværkssikkerhed / Pr. A. N. Berlin. - Foredragskursus.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 The ElGamal signature scheme // Handbook of Applied Cryptography (engelsk) - CRC Press , 1996. - 816 s. — ( Diskret matematik og dens anvendelser ) — ISBN 978-0-8493-8523-0

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort