ElGamalin kaava

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. toukokuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 43 muokkausta .

Elgamal - malli on julkisen avaimen salausjärjestelmä , joka perustuu vaikeuteen laskea diskreettejä logaritmeja äärellisessä kentässä . Salausjärjestelmä sisältää salausalgoritmin ja digitaalisen allekirjoitusalgoritmin. ElGamal-järjestelmä on Yhdysvaltojen ( DSA ) ja Venäjän ( GOST R 34.10-94 ) aiempien digitaalisten allekirjoitusstandardien taustalla .

Järjestelmän ehdotti Taher El-Gamal vuonna 1985 . [1] ElGamal kehitti muunnelman Diffie-Hellman-algoritmista . Hän paransi Diffie-Hellman-järjestelmää ja sai kaksi algoritmia, joita käytettiin salaukseen ja todentamiseen. Toisin kuin RSA, ElGamal-algoritmia ei patentoitu, joten siitä tuli halvempi vaihtoehto, koska lisenssimaksuja ei vaadittu. Algoritmin uskotaan kuuluvan Diffie-Hellmanin patenttiin.

Avaimen luominen

Syntyy satunnainen alkuluku . $s$
Valitaan kokonaisluku - primitiivinen juuri . $g$ $s$
Satunnainen kokonaisluku valitaan siten, että . $x$ ${\näyttötyyli (1<x<p-1)}$
Laskettu . $y=g^{x}{\bmod {p}}$
Julkinen avain on , yksityinen avain on . ${\näyttötyyli (y,g,p)}$ $x$

Työskentely salatussa tilassa

ElGamalin salausjärjestelmä on itse asiassa yksi tavoista luoda Diffie-Hellmanin julkisia avaimia . ElGamal-salausta ei pidä sekoittaa ElGamalin digitaaliseen allekirjoitusalgoritmiin.

Salaus

Viestin on oltava pienempi kuin . Viesti on salattu seuraavasti: $M$ $s$

Istuntoavain valitaan — satunnainen kokonaisluku , jossa on . $(p - 1)$ $k$ $1<k<p-1$
Numerot ja lasketaan . $a=g^{k}{\bmod {p))$ $b=y^{k}M{\bmod {p}}$
Lukupari on salateksti . $(a, b)$

On helppo nähdä, että salatekstin pituus ElGamal-skeemassa on kaksi kertaa alkuperäisen viestin pituus . $M$

Salauksen purku

Kun tiedät yksityisen avaimen , alkuperäinen viesti voidaan laskea salatekstistä kaavalla: $x$ $(a, b)$

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

Samalla se on helppo tarkistaa

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

ja siksi

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

Käytännön laskelmia varten seuraava kaava on sopivampi:

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

Salausjärjestelmä

Esimerkki

Salaus
1. Oletetaan, että haluamme salata viestin . $M=5$
2. Luodaan avaimet:
  1. Anna . Valitaan satunnainen kokonaisluku siten, että . $p=11,g=2$ $x=8$ $x$ $1<x<p$
  2. Lasketaan . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Julkinen avain on siis 3 ja yksityinen avain numero . ${\näyttötyyli (p,g,y)=(11,2,3)}$ $x=8$
3. Valitse satunnainen kokonaisluku siten, että 1 < k < (p − 1). Anna . $k$ $k=9$
4. Laskemme numeron . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Laskemme numeron . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. Tuloksena oleva pari on salateksti. ${\näyttötyyli (a,b)=(6,9)}$
Salauksen purku
1. Sinun on vastaanotettava viesti käyttämällä tunnettua salatekstiä ja yksityistä avainta . $M=5$ ${\näyttötyyli (a,b)=(6,9)}$ $x=8$
2. Laskemme M kaavalla: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Alkuperäinen viesti tuli . $M=5$

Koska satunnaismuuttuja sisällytetään ElGamal-malliin , ElGamal-salausta voidaan kutsua moniarvoiseksi korvaussalaukseksi. Numeron valinnan satunnaisuuden vuoksi tällaista järjestelmää kutsutaan myös todennäköisyyspohjaiseksi salausmenetelmäksi. Salauksen todennäköisyyspohjainen luonne on etu ElGamal-menetelmälle, koska todennäköisyyspohjaiset salausmenetelmät ovat vahvempia verrattuna menetelmiin, joissa on tietty salausprosessi. ElGamal-salausmenetelmän haittana on, että salateksti on kaksi kertaa selkeän tekstin pituus. Todennäköisyyspohjaisessa salausmenetelmässä itse viesti ja avain eivät määritä salatekstiä yksiselitteisesti. ElGamal-järjestelmässä on tarpeen käyttää satunnaismuuttujan eri arvoja erilaisten viestien salaamiseen ja . Jos käytät samaa , niin vastaaville salateksteille ja relaatio täyttyy . Tästä lausekkeesta voidaan helposti laskea , jos tietää . $k$ $k$ $M$ $k$ $M$ $M'$ $k$ $(a, b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $M'$ $M$

Työskentely allekirjoitustilassa

Digitaalinen allekirjoitus mahdollistaa tietojen muutosten tunnistamisen ja allekirjoittajan henkilöllisyyden selvittämisen. Allekirjoitetun viestin vastaanottaja voi käyttää digitaalista allekirjoitusta todistaakseen kolmannelle osapuolelle, että allekirjoitus on todella lähettäjän tekemä. Allekirjoitustilassa työskennellessä oletetaan, että on olemassa kiinteä hash-funktio , jonka arvot ovat välissä . $h(\cdot )$ $\vasen(1,p-1\oikea)$

Viestien allekirjoitukset

Allekirjoittaaksesi viestin , suoritetaan seuraavat toiminnot: $M$

Viestin tiivistelmä lasketaan : (Hash-funktio voi olla mikä tahansa). $M$ $m=h(M).$
Satunnaisluvun koprime valitaan ja lasketaan $1<k<p-1$ $p-1$ $r=g^{k}\,{\bmod {\,}}p.$
Luku lasketaan , jossa on kertova käänteismodulo , joka voidaan löytää esimerkiksi käyttämällä laajennettua Euclid-algoritmia . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
Viestin allekirjoitus on pari . $M$ $\left(r,s\oikea)$

Allekirjoituksen vahvistus

Tietäen julkisen avaimen viestin allekirjoitus varmistetaan seuraavasti: $\vasen(p,g,y\oikea)$ $\left(r,s\oikea)$ $M$

Ehtojen toteutettavuus tarkistetaan: ja . $0<r<p$ $0<s<p-1$
Jos ainakin yksi niistä epäonnistuu, allekirjoitus katsotaan virheelliseksi.
Tiivistelmä lasketaan $m=h(M).$
Allekirjoitus katsotaan päteväksi, jos vertailu tehdään: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Oikeustarkistus

Tarkasteltu algoritmi on oikea siinä mielessä, että yllä olevien sääntöjen mukaan laskettu allekirjoitus hyväksytään, kun se varmistetaan.

Muuttaa määritelmää , meillä on $s$

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

Lisäksi Fermatin pienestä lauseesta seuraa, että

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

Esimerkki

Viestin allekirjoitus.
1. Oletetaan, että haluamme allekirjoittaa viestin . $M=baaqab$
2. Luodaan avaimet:
  1. Olkoon muuttujat jonkun yhteisön tiedossa. $p=23$ $g=5$
  2. Salainen avain on satunnainen kokonaisluku siten, että . $x=7$ $x$ $1<x<p$
  3. Laske julkinen avain : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Julkinen avain on siis 3 . ${\näyttötyyli (p,g,y)=(23,5,17)}$
3. Nyt lasketaan hash-funktio: . $h(M)=h(baaqab)=m=3$
4. Valitaan satunnainen kokonaisluku siten, että ehto täyttyy . Anna . $k$ $1<k<p-1$ $k=5$
5. Laske r = g^k mod p = 5^5 mod 23 = 20.
6. Me löydämme . Tällainen numero on olemassa, koska GCD . Se voidaan löytää käyttämällä laajennettua Euclid-algoritmia. Saada $k^{-1}$ $(k,p-1)=1$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. Numeron löytäminen . Saamme koska $s\,\equiv \,(m-xr)k^{{-1}}{\pmod {p-1}}$ $s=21$ $s=\,(3-7\cdot 20)5^{-1}{\pmod {22}}=21$
8. Allekirjoitimme siis viestin: . $<baaqab,20,21>$

Vastaanotetun viestin todennus.
1. Laskemme hash-funktion: . $h(M)=h(baaqab)=m=3$
2. Tarkastellaan vertailua . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Laske vasemman puolen modulo 23: . $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Laske oikeanpuoleinen modulo 23: . $5^{3}{\bmod {2}}3=10$
5. Koska oikea ja vasen osa ovat yhtä suuret, tämä tarkoittaa, että allekirjoitus on oikea.

ElGamalin digitaalisen allekirjoitusjärjestelmän tärkein etu on kyky luoda digitaalisia allekirjoituksia suurelle määrälle viestejä käyttämällä vain yhtä salaista avainta. Jotta hyökkääjä voi väärentää allekirjoituksen, hänen on ratkaistava monimutkaisia matemaattisia ongelmia logaritmin löytämisessä kentältä . On syytä esittää useita kommentteja:

\mathbb {Z} _{p}

Satunnaisluku tulee tuhota heti allekirjoituksen laskemisen jälkeen, koska jos hyökkääjä tietää satunnaisluvun ja itse allekirjoituksen, hän voi helposti löytää salaisen avaimen kaavalla: ja väärentää allekirjoituksen kokonaan. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

Numeron on oltava satunnainen, eikä sitä saa kopioida eri allekirjoituksille, jotka on saatu samalla salaisen avaimen arvolla. $k$

Taittamisen käyttö selittyy sillä, että se suojaa allekirjoitusta viestien luettelemiselta hyökkääjän tuntemien allekirjoitusarvojen mukaan. Esimerkki: jos valitset satunnaislukuja , jotka täyttävät ehdot , gcd(j,p-1)=1 ja oletetaan, että ${\näyttötyyli 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)$

on helppo varmistaa, että pari on oikea digitaalinen allekirjoitus viestille . $(r,s)$ $x=M$

ElGamalin digitaalisesta allekirjoituksesta on tullut esimerkki muiden ominaisuuksiltaan samanlaisten allekirjoitusten rakentamisesta. Ne perustuvat vertailuun: , jossa kolmois ottaa jonkin permutaatiosta ±r, ±s ja ±m arvot jollekin merkkivalikolle. Esimerkiksi alkuperäinen ElGamal-kaava saadaan , , , USA:n ja Venäjän digitaalisen allekirjoituksen standardit perustuvat tähän allekirjoituksen muodostamisperiaatteeseen. Amerikkalaisessa DSS:ssä (Digital Signature Standard) käytetään arvoja , , , ja venäläisessä standardissa: , , . $y^{A}\cdot r^{B}=g^{C}(modp)$ ${\näyttötyyli (A,B,C)}$ $A=r$ $B=s$ $C=m$ $A=r$ $B=-s$ $C=m$ $A=-x$ $B=-m$ $C=s$
Toinen etu on kyky lyhentää allekirjoituksen pituutta korvaamalla numeropari numeroparilla ), jossa on jokin yksinkertainen luvun jakaja . Tässä tapauksessa modulo-allekirjoituksen todentamisen vertailu tulee korvata uudella vertailulla modulo : . Tämä tehdään amerikkalaisessa DSS-standardissa (Digital Signature Standard). ${\näyttötyyli (s,m)}$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(p-1)$ $s$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

Kryptografinen vahvuus ja ominaisuudet

Tällä hetkellä julkisen avaimen salausjärjestelmiä pidetään lupaavimpana. Näitä ovat ElGamal-kaavio, jonka kryptografinen vahvuus perustuu diskreetin logaritmiongelman laskennalliseen monimutkaisuuteen , jossa p , g ja y on laskettava vertailua tyydyttävä x :

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

Venäjän federaatiossa vuonna 1994 hyväksytty GOST R34.10-1994 , joka säänteli sähköisen digitaalisen allekirjoituksen luomis- ja todentamismenettelyjä, perustui ElGamal-järjestelmään. Vuodesta 2001 lähtien uusi GOST R 34.10-2001 on ollut käytössä käyttämällä yksinkertaisten Galois-kenttien yli määriteltyjen elliptisten käyrien aritmetiikkaa . ElGamal-skeemaan perustuvia algoritmeja on suuri määrä: nämä ovat DSA , ECDSA , KCDSA-algoritmit ja Schnorr-malli .

Joidenkin algoritmien vertailu:

Algoritmi	Avain	Tarkoitus	Kryptografinen vastustuskyky, MIPS	Huomautuksia
RSA	Jopa 4096 bittiä	Salaus ja allekirjoitus	2.7•10 28 1300-bittiselle avaimelle	Perustuu vaikeussuurten tekijöiden jakaminen ongelma ; yksi ensimmäisistä epäsymmetrisistä algoritmeista. Sisältyy moniin standardeihin
ElGamal	Jopa 4096 bittiä	Salaus ja allekirjoitus	Samalla avaimen pituudella kryptografinen vahvuus on yhtä suuri kuin RSA, ts. 2.7•10 28 1300-bittiselle avaimelle	Perustuu vaikeaan ongelmaan diskreettien logaritmien laskemisesta äärellisessä kentässä; avulla voit luoda nopeasti avaimia turvallisuudesta tinkimättä. Käytetään DSA-standardin DSS:n digitaalisessa allekirjoitusalgoritmissa
DSA	Jopa 1024 bittiä	Vain allekirjoitus		Perustuu diskreetin logaritmitehtävän vaikeuteen äärellisessä kentässä ; hyväksytty valtioksi Yhdysvaltain standardi; käytetään salaiseen ja luokittelemattomaan viestintään; Kehittäjä on NSA.
ECDSA	Jopa 4096 bittiä	Salaus ja allekirjoitus	Kryptovastus ja toimintanopeus ovat korkeammat kuin RSA:ssa	Moderni suunta. Monien johtavien matemaatikoiden kehittämä

Muistiinpanot

↑ Elgamal, 1985 .

Kirjallisuus

Elgamal T. Julkisen avaimen salausjärjestelmä ja diskreeteihin logaritmiin perustuva allekirjoitusjärjestelmä, julkisen avaimen salausjärjestelmä ja diskreeteihin logaritmeihin perustuva allekirjoitusjärjestelmä // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1985. - Voi. 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. Salauksen perusteet.[ selventää ]
B. A. Forouzan. ElGamalin digitaalinen allekirjoitusmalli // Salausavainten hallinta ja verkon suojaus / Per. A. N. Berliini. - Luentokurssi.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 ElGamalin allekirjoitusjärjestelmä // Handbook of Applied Cryptography (englanti) - CRC Press , 1996. - 816 s. — ( Diskreetti matematiikka ja sen sovellukset ) — ISBN 978-0-8493-8523-0

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
muu	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti