Schema för ElGamal

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 maj 2018; kontroller kräver 43 redigeringar .

Elgamal - schemat är ett kryptosystem med offentlig nyckel baserat på svårigheten att beräkna diskreta logaritmer i ett ändligt fält . Kryptosystemet inkluderar en krypteringsalgoritm och en digital signaturalgoritm. ElGamal-systemet ligger till grund för de tidigare digitala signaturstandarderna i USA ( DSA ) och Ryssland ( GOST R 34.10-94 ).

Systemet föreslogs av Taher El- Gamal 1985 . [1] ElGamal utvecklade en variant av Diffie-Hellman-algoritmen . Han förbättrade Diffie-Hellman-systemet och fick två algoritmer som användes för kryptering och för autentisering. Till skillnad från RSA var ElGamal-algoritmen inte patenterad och blev därför ett billigare alternativ, eftersom inga licensavgifter krävdes. Algoritmen tros omfattas av Diffie-Hellman-patentet.

Nyckelgenerering

Ett slumpmässigt primtal genereras . $sid$
Ett heltal väljs - den primitiva roten . $g$ $sid$
Ett slumpmässigt heltal väljs så att . $x$ $(1<x<p-1)$
Beräknat . $y=g^{x}{\bmod {p}}$
Den offentliga nyckeln är , den privata nyckeln är . $(y,g,p)$ $x$

Arbeta i krypterat läge

Chiffersystemet ElGamal är faktiskt ett av sätten att generera publika Diffie-Hellman- nycklar . ElGamal-kryptering ska inte förväxlas med ElGamals digitala signaturalgoritm.

Kryptering

Meddelandet måste vara mindre än . Meddelandet krypteras enligt följande: $M$ $sid$

Sessionsnyckeln väljs — ett slumpmässigt heltal med , så att . $(s - 1)$ $k$ $1<k<p-1$
Siffrorna och är beräknade . $a=g^{k}{\bmod {p))$ $b=y^{k}M{\bmod {p}}$
Ett par siffror är en chiffertext . $(a,b)$

Det är lätt att se att längden på chiffertexten i ElGamal-schemat är dubbelt så lång som det ursprungliga meddelandet . $M$

Dekryptering

Genom att känna till den privata nyckeln kan det ursprungliga meddelandet beräknas från chiffertexten med hjälp av formeln: $x$ $(a,b)$

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

Samtidigt är det lätt att kontrollera det

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

och därför

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

För praktiska beräkningar är följande formel mer lämplig:

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

Krypteringsschema

Exempel

Kryptering
1. Låt oss säga att vi vill kryptera ett meddelande . $M=5$
2. Låt oss skapa nycklarna:
  1. Låt . Låt oss välja ett slumpmässigt heltal så att . $p=11,g=2$ $x=8$ $x$ $1<x<p$
  2. Låt oss räkna ut . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Så den publika nyckeln är 3 och den privata nyckeln är nummer . $(p,g,y)=(11,2,3)$ $x=8$
3. Välj ett slumpmässigt heltal så att 1 < k < (p − 1). Låt . $k$ $k=9$
4. Vi beräknar antalet . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Vi beräknar antalet . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. Det resulterande paret är chiffertexten. $(a,b)=(6,9)$
Dekryptering
1. Du måste ta emot ett meddelande med en känd chiffertext och privat nyckel . $M=5$ $(a,b)=(6,9)$ $x=8$
2. Vi beräknar M med formeln: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Fick det ursprungliga meddelandet . $M=5$

Eftersom en slumpvariabel introduceras i ElGamal-schemat kan ElGamal-chifferet kallas ett substitutionschiffer med flera värden. På grund av slumpmässigheten i valet av numret kallas ett sådant schema också för ett probabilistiskt krypteringsschema. Den sannolikhetsmässiga karaktären hos krypteringen är en fördel för ElGamal-schemat, eftersom probabilistiska krypteringsscheman uppvisar större styrka jämfört med scheman med en specifik krypteringsprocess. Nackdelen med ElGamal-krypteringsschemat är att chiffertexten är dubbelt så lång som klartexten. För ett probabilistiskt krypteringsschema definierar inte själva meddelandet och nyckeln chiffertexten unikt. I ElGamal-schemat är det nödvändigt att använda olika värden av en slumpvariabel för att kryptera olika meddelanden och . Om du använder samma , då för motsvarande chiffertexter och relationen är uppfylld . Från detta uttryck kan man lätt räkna ut , om man vet . $k$ $k$ $M$ $k$ $M$ $M'$ $k$ $(a,b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $M'$ $M$

Arbeta i signaturläge

Den digitala signaturen tjänar till att möjliggöra identifiering av dataändringar och för att fastställa undertecknarens identitet. Mottagaren av ett signerat meddelande kan använda en digital signatur för att bevisa för en tredje part att signaturen verkligen gjordes av avsändaren. När du arbetar i signaturläge antas det att det finns en fast hashfunktion , vars värden ligger i intervallet . $h(\cdot )$ $\left(1,p-1\höger)$

Meddelandesignaturer

För att signera ett meddelande utförs följande åtgärder: $M$

Meddelandesammandraget beräknas : (Hashfunktionen kan vara vilken som helst). $M$ $m=h(M).$
Ett slumptalssamprimtal med väljs och beräknas $1<k<p-1$ $p-1$ $r=g^{k}\,{\bmod {\,}}s.$
Antalet beräknas , där är den multiplikativa inversa modulo , som kan hittas till exempel med den utökade Euklidiska algoritmen . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
Meddelandets signatur är paret . $M$ $\vänster(r,s\höger)$

Signaturverifiering

Genom att känna till den publika nyckeln verifieras meddelandesignaturen enligt följande: $\left(p,g,y\right)$ $\vänster(r,s\höger)$ $M$

Villkorens genomförbarhet kontrolleras: och . $0<r<p$ $0<s<p-1$
Om minst en av dem misslyckas anses signaturen vara ogiltig.
Smältningen beräknas $m=h(M).$
En signatur anses giltig om en jämförelse görs: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Korrekthetskontroll

Den övervägda algoritmen är korrekt i den meningen att signaturen beräknad enligt ovanstående regler kommer att accepteras när den är verifierad.

Att omvandla definitionen har vi $s$

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

Vidare följer det av Fermats lilla sats att

{\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}}

Exempel

Meddelandesignatur.
1. Låt oss säga att vi vill skriva under ett meddelande . $M=baaqab$
2. Låt oss skapa nycklarna:
  1. Låt variablerna vara kända för någon gemenskap. $p=23$ $g=5$
  2. Den hemliga nyckeln är ett slumpmässigt heltal så att . $x=7$ $x$ $1<x<p$
  3. Beräkna den publika nyckeln : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Så den publika nyckeln är 3 . $(p,g,y)=(23,5,17)$
3. Nu beräknar vi hashfunktionen: . $h(M)=h(baaqab)=m=3$
4. Låt oss välja ett slumpmässigt heltal så att villkoret är uppfyllt . Låt . $k$ $1<k<p-1$ $k=5$
5. Beräkna r = g^k mod p = 5^5 mod 23 = 20.
6. Vi finner . Ett sådant nummer finns eftersom GCD . Den kan hittas med den utökade Euklidiska algoritmen. Skaffa sig $k^{-1}$ $(k,p-1)=1$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. Att hitta ett 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 skrev under meddelandet: . $<baaqab,20,21>$

Autentisering av det mottagna meddelandet.
1. Vi beräknar hashfunktionen: . $h(M)=h(baaqab)=m=3$
2. Låt oss kolla jämförelsen . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Beräkna vänstra modulo 23: . $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Beräkna höger sida modulo 23: . $5^{3}{\bmod {2}}3=10$
5. Eftersom höger och vänster del är lika betyder det att signaturen är korrekt.

Den största fördelen med ElGamals digitala signaturschema är möjligheten att generera digitala signaturer för ett stort antal meddelanden med endast en hemlig nyckel. För att en angripare ska kunna förfalska en signatur måste han lösa komplexa matematiska problem med att hitta logaritmen i fältet . Flera kommentarer bör göras:

\mathbb {Z} _{p}

Slumptalet bör förstöras omedelbart efter att signaturen har beräknats, för om en angripare känner till slumptalet och signaturen själv kan han enkelt hitta den hemliga nyckeln med hjälp av formeln: och helt fejka signaturen. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

Numret måste vara slumpmässigt och får inte dupliceras för olika signaturer som erhålls med samma hemliga nyckelvärde. $k$

Användningen av vikning förklaras av det faktum att den skyddar signaturen från uppräkning av meddelanden enligt signaturvärdena som är kända för angriparen. Exempel: om du väljer slumptal som uppfyller villkoren , gcd(j,p-1)=1 och antar att $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 är lätt att verifiera att paret är rätt digital signatur för meddelandet . $(r,s)$ $x=M$

ElGamals digitala signatur har blivit ett exempel på konstruktionen av andra signaturer som liknar sina egenskaper. De är baserade på jämförelsen: , där trippeln tar värdena för en av permutationerna ±r, ±s och ±m för ett urval av tecken. Till exempel erhålls det ursprungliga ElGamal-schemat med , , . De digitala signaturstandarderna i USA och Ryssland är baserade på denna princip att konstruera en signatur. I den amerikanska DSS (Digital Signature Standard) används värdena , , , och i den ryska standarden: , , . $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 annan fördel är möjligheten att minska längden på signaturen genom att ersätta ett par siffror med ett par siffror ), där är någon enkel divisor av talet . I det här fallet bör jämförelsen för modulo signaturverifiering ersättas med en ny jämförelse modulo : . Detta görs i den amerikanska DSS (Digital Signature Standard). $(s,m)$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(p-1)$ $sid$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

Kryptografisk styrka och funktioner

För närvarande anses kryptosystem med publik nyckel vara de mest lovande. Dessa inkluderar ElGamal-schemat, vars kryptografiska styrka är baserad på beräkningskomplexiteten för det diskreta logaritmproblemet , där det, givet p , g och y , krävs för att beräkna x som uppfyller jämförelsen:

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

GOST R34.10-1994 , antagen 1994 i Ryska federationen, som reglerade förfarandena för att generera och verifiera en elektronisk digital signatur, baserades på ElGamal-systemet. Sedan 2001 har den nya GOST R 34.10-2001 använts, med hjälp av aritmetiken för elliptiska kurvor definierade över enkla Galois-fält . Det finns ett stort antal algoritmer baserade på ElGamal-schemat: dessa är DSA , ECDSA , KCDSA-algoritmer, Schnorr-schema .

Jämförelse av några algoritmer:

Algoritm	Nyckel	Ändamål	Kryptografiskt motstånd, MIPS	Anteckningar
RSA	Upp till 4096 bitar	Kryptering och signering	2,7•10 28 för 1300 bitars nyckel	Baserat på svårigheten med faktoriseringsproblemet med stort antal ; en av de första asymmetriska algoritmerna. Ingår i många standarder
ElGamal	Upp till 4096 bitar	Kryptering och signering	För samma nyckellängd är den kryptografiska styrkan lika med RSA, d.v.s. 2,7•10 28 för 1300 bitars nyckel	Baserat på det svåra problemet med att beräkna diskreta logaritmer i ett ändligt fält; låter dig snabbt generera nycklar utan att kompromissa med säkerheten. Används i den digitala signaturalgoritmen för DSA-standarden DSS
DSA	Upp till 1024 bitar	Endast signatur		Baserat på svårigheten med det diskreta logaritmproblemet i ett ändligt fält ; accepteras som stat amerikansk standard; används för hemlig och oklassificerad kommunikation; Utvecklare är NSA.
ECDSA	Upp till 4096 bitar	Kryptering och signering	Kryptomotstånd och operationshastighet är högre än för RSA	Modern regi. Utvecklad av många ledande matematiker

Anteckningar

↑ Elgamal, 1985 .

Litteratur

Elgamal T. Ett kryptosystem med offentlig nyckel och ett signaturschema baserat på diskreta logaritmer, ett kryptosystem med offentlig nyckel och ett signaturschema baserat på diskreta logaritmer // IEEE Trans . inf. Theory / 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. Grunderna i kryptografi.[ förtydliga ]
B.A. Forouzan. ElGamal digital signaturschema // Krypteringsnyckelhantering och nätverkssäkerhet / Per. A. N. Berlin. - Föreläsningskurs.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 The ElGamal signature scheme // Handbook of Applied Cryptography (engelska) - CRC Press , 1996. - 816 sid. — ( Diskret matematik och dess tillämpningar ) — ISBN 978-0-8493-8523-0

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort