ElGamalin kryptosysteemi

Kryptosysteemi ElGamal , tai salauksen El Gamal (tai El Gamal järjestelmä ) on protokolla epäsymmetrinen keksi Taher ELGAMAL 1984 ja rakennettu ongelma diskreetin logaritmin .

Tätä protokollaa käyttää ilmainen ohjelmisto GNU Privacy Guard, jonka viimeisimmät versiot toteuttavat jopa sen version elliptisillä käyrillä . Toisin kuin RSA- salaus , se ei ole koskaan ollut patenttisuojan alla .

Taher Elgamalin perustamisartikkeli esittelee salausprotokollan , mutta myös digitaalisen allekirjoituksen , jota yhtäläisyydistään huolimatta (ne molemmat rakentuvat erillisen logaritmin ongelmaan ) ei pidä sekoittaa. Tämä artikkeli käsittelee vain kanssa salauksen protokollan .

Algoritmin kuvaus

Algoritmi on kuvattu rajalliselle sykliselle ryhmälle , jonka sisällä Diffie-Hellmanin päätösongelma (DDH) on vaikeaa. Tarkempia tietoja on kohdassa Resistanssi CPA-hyökkäyksille .

Voimme huomata, että DDH on vahvempi työhypoteesi kuin diskreetin logaritmin, koska se pitää paikkansa, jos koskaan, diskreetin logaritmin ongelma on vaikea. On myös ryhmiä, joissa DDH- ongelma on helppo, mutta joissa ei ole tehokasta algoritmia erillisen logaritmin ratkaisemiseksi .

Koska kyseessä on epäsymmetrinen salausmenetelmä , salausjärjestelmä koostuu kolmesta ( todennäköisyysperusteisesta ) algoritmista : GenClefs , Encrypt ja Decrypt .

Oletuksena on, että Bob haluaa lähettää viestin Alicelle . Mutta tämä viesti sisältää arkaluontoisia tietoja, joten Bob ei halua, että kukaan muu kuin Alice ymmärtää sen. Joten Bob salaa viestinsä.

Koska epäsymmetriset salausmenetelmät ovat yleensä hitaampia kuin niiden symmetriset analogit, ElGamalin salausta käytetään käytännössä usein osana hybridisalausta , kuten sen PGP-spesifikaatiota.

Yksi tapa tarkastella tätä salausjärjestelmää on vetää rinnakkain Diffie-Hellman- avaimenvaihtoprotokollan kanssa . Salausalgoritmin muodostuu tällöin lähettämällä viestin salattu jonka kertakäyttöinen maski alle jaetun avaimen , joka voidaan laskea Alice koska hän on (katso kuva viereisellä sivulla). $c_ {1}$ ${\ displaystyle h ^ {r} = g ^ {r \ cdot x}}$ ${\ displaystyle c_ {2} = g ^ {r}}$

Avainten luominen

Salausjärjestelmän ensimmäinen vaihe on tuottaa avainpari: julkinen avain ja salainen avain . Ensimmäistä käytetään viestien salaamiseen ja toista niiden salauksen purkamiseen.

Luodakseen avainparinsa Alice aloittaa ottamalla syklisen järjestyksen q ryhmän , jossa Diffie-Hellmanin päätöshypoteesiongelma on vaikea, sekä tämän ryhmän generaattorin . $G$ $g$
Alice vetää sitten kohteen , joka on hänen yksityinen avain , ja laskee . ${\ displaystyle {\ mathsf {sk}} \ triangleq x \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ ${\ displaystyle h = g ^ {x}}$
Lopuksi, Alice julkaisee kuin hänen julkinen avain . ${\ displaystyle {\ mathsf {pk}} \ triangleq (G, q, g, h)}$

Salausalgoritmi

Joten Bobilla on pääsy Alicen julkiseen avaimeen . Salataksesi ryhmän elementtinä koodatun viestin Bob aloittaa piirtämällä satunnaisluvun ja käyttää sitä peittämään viestin laskennan aikana . Sallimaan Alice purkaa viestin, Bob lisäävät tätä osa viestiä tietoa tuotteen aiheuttamasta vaarasta: . ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h)}$ $m$ $G$ ${\ displaystyle r \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ $m$ ${\ displaystyle c_ {2} = m \ cdot h ^ {r}}$ ${\ displaystyle c_ {1} = g ^ {r}}$

Lopuksi salaus koostuu näistä kahdesta kappaleesta : ja Bob lähettää Alicelle. ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle C \ G: ssä {2}}$

Salauksen purkualgoritmi

Pääsy ja Alice voi siten laskea: ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle {\ mathsf {sk}} = x}$

{\ displaystyle {\ frac {c_ {2}} {{c_ {1}} ^ {x}}} = {\ frac {m \ cdot h ^ {r}} {g ^ {r \ cdot x}}} = {\ frac {m \ cdot {\ peruuta {g ^ {x \ cdot r}}}} {\ peruuta {g ^ {r \ cdot x}}}} = m}

Ja pystyy siis löytämään viestin . $m$

turvallisuus

Valitut selkeät tekstihyökkäykset

Tarkastellaan julkista tietoa ; Ymmärrämme, että vain osan elementit tehdään näkyviksi eikä eksponentteja (tässä x ja s vastaavasti). Epävirallisesti voimme huomata, että erillisen logaritmin ongelma voidaan tulkita siten, että on vaikea löytää salaisia tietoja ( esimerkiksi), jotka mahdollistaisivat viestin löytämisen. ${\ displaystyle g ^ {x}, g ^ {s}}$ $G$ ${\ displaystyle {\ mathsf {sk}} = \ log _ {g} (h)}$

Tarkemmin sanottuna Diffie-Hellmannin (tai DDH ) päätösongelma mahdollistaa järjestelmän semanttisen turvallisuuden takaamisen .

Esittely Vähennys

Olettaen, että meillä on vastustaja ElGamal-salauksen semanttista turvallisuutta vastaan, joka voittaa ei vähäpätöisellä todennäköisyydellä ε . Sitten on mahdollista rakentaa vastustaja DDH: ta vastaan, mikä olisi ristiriidassa tämän ongelman oletetun vaikeuden kanssa. Tämä juuri kuvailema pienennys muodostaa kaavion turvatodistuksen. ${\ mathcal A}$ ${\ mathcal B}$

Tämän vastustajan rakentamiseksi, jota jäljempänä kutsutaan "  pelkistykseksi  ", oletetaan olevan kolminkertainen DDH  : n tarkoitus on sitten päättää, onko todennäköisyys vähäpätöinen vai ei. Tätä varten sillä on käyttöliittymä edellä kuvatun vastustajan kanssa ElGamalin krypto-järjestelmän semanttisen turvallisuuden edessä. ${\ displaystyle (g ^ {a}, g ^ {b}, g ^ {c})}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle c \ _ _ {R} \ mathbb {Z} _ {p}}$

Vähennys lähettää sen vuoksi julkisen avaimen vastustajalle ElGamalia vastaan . Tuottaessaan haaste vastustaja vastaan semanttinen turvallisuus on salausjärjestelmä, vähennys lähettää salatun: sillä hänen valintansa. Jos tripletti on koskaan DDH- tripletti , toisin sanoen jos , niin se muodostettaisiin kelvolliseksi salaukseksi ElGamalille julkisen avaimen suhteen . Toisaalta, jos eksponentti on satunnainen, niin vastustaja ElGamalia vastaan ei pysty erottamaan haasteen kahta viestiä muuten kuin vastaamalla satunnaisesti. ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h = g ^ {a})}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot g ^ {c})}$ ${\ displaystyle i \ sisään \ {0,1 \}}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot (g ^ {a}) ^ {b}) = (g ^ {b}, m_ {i} \ cdot h ^ {b}) }$ ${\ displaystyle {\ mathsf {pk}}}$ $vs.$

Meidän on vain vastattava "1" (vastaa sitä, että DDH: n haastaja lähetti DDH-tripletin), jos vastustajamme koskaan onnistuu, ja "0" (vastaa sitä, että DDH: n haastaja lähetti kolminkertaisen satunnaisuuden) muuten.

Analyysi

Tulemme nyt rajoittaa etu voittaa meidän vähennystä etu ε oletetun vastustajan vastoin järjestelmän.

Aloitamme huomauttamalla, että meillä on kaksi tapausta: joko haastajamme lähettämä haaste on todellinen DDH- tripletti tai se on tasaisesti piirretty tripletti.

{\ displaystyle {\ begin {tasattu} {\ textrm {Adv}} ^ {DDH} ({\ mathcal {B}}) & = | \ Pr [{\ mathcal {B}} \ 1 \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to 0 \ mid i = 0 \ land {\ text {DDH}}] \ Pr [i = 0] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH} }] \ Pr [i = 1] - {\ frac {1} {2}} | \\ & = | {\ frac {1} {2}} (1- \ Pr [{\ mathcal {A}} \ 1 \ mid i = 0 \ land {\ text {DDH}}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}]) - {\ frac {1} {2}} | \\ & = {\ frac {1} {2}} | - \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 0 \ land {\ text {DDH }}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}] | \\ & = {\ frac {1} {2}} {\ textrm {Adv}} ^ {\ text {ElGamal}} ({\ mathcal {A}}) \\ & = {\ frac {\ varepsilon} {2}} \ end {tasattu}}}

Siten meillä on etu, joka on edelleen merkittävä: saman turvallisuuden saavuttamiseksi DDH: n ja kryptojärjestelmämme välillä riittää, että DDH- ongelma pysyy turvassa ylimääräisellä suojausbitillä.

Edessä valitut salaushyökkäykset

Malleissa, joissa on enemmän voimaa käyttävä hyökkääjä, kuten valittujen salaushyökkäysten alla, ElGamal-salausjärjestelmä ei ole turvallinen sen muovattavuuden vuoksi ; todellakin, kun salaus viestille , voimme rakentaa salauksen , joka on voimassa viestille . ${\ displaystyle C = (c_ {1}, c_ {2})}$ $m$ ${\ displaystyle C '= (c_ {1}, 2 \ cdot c_ {2})}$ ${\ displaystyle 2 \ cdot m}$

Tämä muovattavuus (se on moninkertaistuva homomorfismi ) toisaalta mahdollistaa sen käytön esimerkiksi sähköisessä äänestyksessä .

On kuitenkin olemassa variantteja, jotka saavuttavat turvallisuuden valittuja salaushyökkäyksiä vastaan, kuten Cramer-Shoup-salausjärjestelmä, joka voidaan nähdä ElGamal-salauksen laajennuksena.

Esimerkki

Esimerkiksi voidaan ottaa ryhmä generaattorilla g = 5 ( Varoitus : tämä ei ole turvallinen ryhmä, nämä arvot otettiin vain yksinkertaisen esimerkin tuottamiseksi). ${\ displaystyle G = (\ mathbb {Z} / 100000007 \ mathbb {Z} ^ {*}, \ kertaa)}$

Mahdollinen julkinen avain voisi siis olla :, ja salainen avain . ${\ displaystyle {\ mathsf {pk}} = (G, 100000006,5,29487234)}$ ${\ displaystyle {\ mathsf {sk}} = 81996614}$

Huomaa, että koska salaus on todennäköisyysalgoritmi , samalle viestille on olemassa erilaisia mahdollisia lähtöjä. Mahdollinen salaus viestille 42 voisi siis olla (58086963, 94768547) , mutta myös (83036959, 79165157) riskeille r yhtä suuri kuin 6689644 ja 83573058 .

Siitä huolimatta, jos teemme laskun kahdelle luvullemme, saamme tuloksen 42 . ${\ displaystyle {\ dfrac {c_ {2}} {c_ {1} ^ {sk}}}}$

Huomautuksia ja viitteitä

(fr) Tämä artikkeli on osittain tai kokonaan otettu englanninkielisestä Wikipedia- artikkelista " ElGamal-salaus " ( katso luettelo tekijöistä ) .

ElGamal 1984 .
RFC4880 , (en) " OpenPGP-sanoman muoto "
GnuPG 2.1 -vaihtoloki
Joux ja Nguyen 2003 .
Katz ja Lindell 2014 , luku 10.5 ElGamalin salausjärjestelmä.
Belenios, (en) " Beleniosin tekniset tiedot "

Liitteet

Bibliografia

[ElGamal 1984] (en) Taher ElGamal, ” Julkisen avaimen salausjärjestelmä ja erillisiin logaritmeihin perustuva allekirjoitusjärjestelmä ” , Crypto , Springer,1984( DOI 10.1007 / 3-540-39568-7_2 )
[Katz ja Lindell 2014] (en) Jonathan Katz ja Yehuda Lindell, Johdatus moderniin salaukseen, 2. painos , Boca Raton, Chapman ja Hall ,2014, 583 Sivumäärä ( ISBN 978-1-4665-7026-9 , luettu verkossa ) , "Luku 10.5 El Gamalin salausjärjestelmä"
[Menezes, van Oorschot ja Vanstone 1996] (en) AJ Menezes , PC van Oorschot ja SA Vanstone , Käsikirja sovelletusta salauksesta , CRC Press,1996, 810 Sivumäärä ( ISBN 978-1-4398-2191-6 , lue verkossa [PDF] ) , "Luku 8.4 ElGamalin julkisen avaimen salaus"
[Joux ja Nguyen 2003] (en) Antoine Joux ja Kim Nguyen, " Separating Decision Diffie - Hellman from Computational Diffie - Hellman in Cryptographic Groups " , Journal of Cryptology , voi. 16,2003, s. 239-247 ( DOI 10.1007 / s00145-003-0052-4 )