ESIGN

ESIGN ( englanniksi Efficient digital SIGNature - Efektiivinen digitaalinen allekirjoitus) on julkisen avaimen digitaalinen allekirjoitusmalli, joka perustuu numerotekijöiden ongelmaan . Tämän järjestelmän erottuva piirre on kyky luoda nopeasti allekirjoitus. [yksi]

Historia

Digitaalisen allekirjoituksen kehitti japanilainen yritys NTT vuonna 1985. [2] Järjestelmä osoittautui tehokkaaksi digitaalisen allekirjoituksen luomisnopeuden kannalta. Ensimmäiset versiot kuitenkin mursivat Ernie Btickel ja John DeLaurentis , minkä jälkeen suositeltuja algoritmiparametreja muutettiin . [3] Myöhemmät hakkerointiyritykset epäonnistuivat. Kirjoittajat väittävät , että ESIGN : n uusimman version murtamisen monimutkaisuus on verrattavissa useiden muotojen tekijöihinjakoongelman monimutkaisuuteen , jossa ja ovat alkulukuja . [neljä] $n$ $p^{2}q$ $s$ $q$

Protokollan kuvaus

Johdanto

Protokollassa on mukana kaksi entiteettiä: entiteetti , jonka tarkoituksena on osoittaa, että viestin kirjoittaja on , ja aihe , jonka tarkoituksena on varmistaa kirjoittaja. ESIGN:ssä asetettujen tavoitteiden toteuttamiseksi ja on suoritettava seuraavat toimet [5] . $A$ $m$ $B$ $A$ $B$

Aiemmin se luo avaimia : julkisia, jotka ovat kaikkien tiedossa, ja yksityisiä , jotka ovat vain kohteen tiedossa . $A$ $A$
Aihe luo viestille digitaalisen allekirjoituksen yksityisen avaimen perusteella. $A$ $s$ $m$
$A$ lähettää viestin ja allekirjoituksen aiheelle . $m$ $s$ $b$
Kohde vahvistaa allekirjoituksen julkisen avaimen perusteella. $B$

Julkisten ja yksityisten avainten luominen

ESIGN-avaimet luodaan seuraavasti [6] .

Kaksi saman bitin pituista alkulukua valitaan satunnaisesti. $s$ $q$
Luku lasketaan . $n=p^{2}q$
Positiivinen kokonaisluku valitaan . $k\geqslant 4$
Numeropari on julkinen avain. $(n,k)$
Numeropari on yksityinen avain. $(p,q)$

Allekirjoituksen luominen

Allekirjoittaaksesi viestin , jossa on mielivaltaisen pituinen binääriluku , suoritetaan seuraavat vaiheet [6] . $m$ $m$

, jossa on esivalittu hash - funktio , joka ottaa arvot välillä - . ${\näyttötyyli \mu=h(m)}$ $h$ $0$ $n-1$
Väliltä valitaan satunnaisluku . $x$ $[0,pq)$
Ja lasketaan , jossa on funktio pyöristää pienimpään kokonaislukuun, suurempi argumentti. $\chi =\left\lceil {\frac {\mu -(x^{k}{\bmod {n)))}{pq))\right\rceil$ $\varkappa =\left({\frac {\chi }{k*x^{k-1}}}\oikea){\bmod {p}}$ $\lceil \cdot \rceil \colon \mathbb {R} \to \mathbb {Z}$
Allekirjoitus lasketaan . $s=x+\varkappa pq$

Allekirjoituksen vahvistus

Sen varmistamiseksi, että allekirjoitus todellakin allekirjoittaa viestin , suoritetaan seuraavat vaiheet [6] . $s$ $m$

, jossa on sama hash-funktio, jota käytettiin allekirjoituksen luomiseen. ${\näyttötyyli \mu=h(m)}$ $h$
Laskettu . $\xi =\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil$
Epätasa-arvotesti suoritetaan . $\mu \leqslant s^{k}{\bmod {n}}\leqslant \mu +2^{\xi }$
Allekirjoitus katsotaan päteväksi, jos eriarvoisuus täyttyy.

Aiemmat versiot

Alun perin ehdotetussa ESIGN-versiossa parametri oli yhtä suuri kuin kaksi. [5] Kuitenkin Ernie Brickellin ja John DeLaurentisin onnistuneen hyökkäyksen jälkeen, joka ulottui myös piirimuunnelmaan kanssa , kirjoittajat muuttivat tämän parametrin vaatimuksen olemassa olevaksi . [7] $k$ $k = 3$ $k\geqslant 4$

Kryptanalysis

Hyökkäys hash-funktioon

Hajautusfunktioon kohdistuvat hyökkäykset allekirjoituksen väärentämiseksi perustuvat sen epätäydellisyyteen eli hajautusfunktion yhteensopimattomuuteen yhden tai useamman kryptografisen vahvuuskriteerin kanssa sillä ehdolla, että ESIGN:n tapauksessa kriteerien tasa-arvo tulee ymmärtää merkittävimpiin bitteihin asti. Tämä lievennys johtuu allekirjoituksen vahvistusehdosta, joka täyttyy alkuperäisen hash-arvon lisäksi myös muiden ensimmäisten korkeiden bittien kohdalla. $h$ $(\log _{2}{n})/3$ $(\log _{2}{n})/3$

Oletetaan, että funktio on epävakaa törmäysten etsinnässä, eli voit löytää niin erilaiset ja vastaavat ensimmäisistä korkeista biteistä. Sitten allekirjoittaessaan viestin kirjoittaja , epäilemättä mitään, allekirjoittaa viestin automaattisesti , koska epätasa-arvo $h$ $m$ $m'$ $h(m)$ $h(m')$ $(\log _{2}{n})/3$ $m$ $A$ $m'$ $h(m')\leqslant s^{k}{\bmod {n}}\leqslant h(m')+2^{\left\lceil {\frac {2}{3}}\log _ {2}{n}\right\rceil}$

Jos valittu hash-funktio on kryptografisesti suojattu, törmäyshyökkäys suorittaa hash-funktion laskentaoperaatiot, toista esikuvaa käyttävä hyökkäys toteuttaa operaatioita, joita ei pidetä toteuttamiskelpoisina, suurille . [8] [9] $2^{(\log _{2}{n})/3}$ $2^{(\log _{2}{n})/6}$ $n$

Julkisen avaimen hyökkäys

Hyökkäys julkiseen avaimeen on yritys saada siitä yksityinen avain . Tämä voidaan tehdä ratkaisemalla yhtälö , eli laskemalla luku . Voit nähdä, että RSA :ssa luku generoidaan samalla tavalla, mutta nykyään kysymys siitä, missä tapauksissa faktorointi yksinkertaistuu tai vaikeutuu, jää avoimeksi, koska tehokkaita faktorointialgoritmeja ei vielä ole. Tällä hetkellä nopein tapa kertoa luku joko ESIGN:lle tai RSA:lle on numerokenttäseulamenetelmä , joka tekee tämän bitin pituudesta riippuvalla nopeudella . Kuitenkin, jos luvun bittipituus on suuri , tekijöiden jakamisesta tulee mahdotonta. [10] [9] $(n,k)$ $(p,q)$ $n=p^{2}q$ $n$ $n$ $n = pq$ $n$ $n$ $n$

Suositellut asetukset

ESIGN-kuvauksessa jo esitettyjen rajoitusten lisäksi turvallisuuden lisäämiseksi on suositeltavaa valita koko ja yhtä suuri tai suurempi kuin bitti, koko yhtä suuri tai suurempi vastaavasti ja parametri suurempi tai yhtä suuri kuin 8 [ 11] : $s$ $q$ $320$ $n$ $960$ $k$

$\log _{2}{p}\geqslant 320$ ;
$k\geqslant 8$ ;

Suojaustaso suhteessa muihin digitaalisiin allekirjoitusmenetelmiin

Alla on taulukko ESIGN-suojaustason sekä RSA- ja ECDSA -suojaustasojen välisestä vastaavuudesta eri parametrikokoille bitteinä. Näet, että samoilla kooilla RSA ja ESIGN ovat vertailukelpoisia turvallisuuden suhteen. [12] $n$ $n$

Koko ESIGN, bittiä $n$	Koko RSA, bittiä $n$	Koko ECDSA:ssa, bittejä $n$
960	960	152
1024	1024	160
2048	2048	224
3072	3072	256
7680	7680	384

Edut

ESIGN-järjestelmän avulla voit luoda nopeasti allekirjoituksen. Koska laskennallisesti monimutkaiset toiminnot, kuten eksponentio ja käänteisen elementin löytäminen , eivät riipu allekirjoitetusta viestistä , ne voidaan suorittaa etukäteen ja tallentaa muistiin. Näin ollen viestin allekirjoittamiseen riittää, että suoritetaan loput yhteen-, kerto- ja jakooperaatiot, joiden osuus allekirjoituksen luomisalgoritmin laskennallisesta monimutkaisuudesta on pieni. Siinä tapauksessa , että ja bitin pituus on yhtä suuri kuin , allekirjoituksen luomisen nopeus sisään on suurempi kuin RSA :lla vastaavilla parametreilla. Mitä tulee allekirjoituksen todentamiseen, sen nopeus on verrattavissa allekirjoituksen varmennusnopeuteen RSA-algoritmissa , jonka avoin eksponentti on pieni. [13] [9] $(x^{k}{\bmod {n)))$ ${\näyttötyyli (k*x^{k-1})^{-1))$ $m$ $k = 4$ $n$ $768$ $10\div 100$

ESIGN-pohjaiset todennusprotokollat

ESIGN:n avulla voit toteuttaa nollatiedontunnistusprotokollia, joiden avulla koehenkilö ( English Prover - proving ) voi todistaa tutkittavalle ( English Verifier - checking) tiedon olemassaolon ja pitää sen salassa . ESIGN-pohjaiset tunnistusprotokollat ovat yhtä tehokkaita kuin Feig-Fiat-Shamir-protokolla . Harkitsemme kahta tällaista protokollaa: kolmikierrosta ja kaksikierrosta. [neljätoista] $P$ $V$ $V$

Kolmen kierroksen tunnistusjärjestelmä

$P$ luo julkisia ja yksityisiä ESIGN-avaimia. $(n,k)$ $(p,q)$
$P$ valitsee satunnaisesti numerot ja laskee , jossa on yksisuuntainen funktio , on ketjutusoperaatio ja lähettää todentajalle . $r$ $u$ $x=f(r\|u)$ $f$ $\|$ $x$ $V$
$V$ valitsee satunnaisesti luvun ja lähettää sen todistajalle. $y$
$P$ laskee , luo allekirjoituksen ja lähettää kolminkertaisen varmentajalle. $m=r\oplus y$ $s$ $m$ ${\näyttötyyli (s,r,u)}$
$V$ varmistaa, että viestin allekirjoitus on sama ja kelvollinen . $x=f(r\|u)$ $s$ $m$

Kahden kierroksen tunnistusjärjestelmä

$P$ luo julkisia ja yksityisiä ESIGN-avaimia. $(n,k)$ $(p,q)$
$V$ valitsee satunnaisesti luvun ja lähettää sen todistajalle. $r$
$P$ valitsee satunnaisesti luvun , laskee , luo allekirjoituksen ja lähettää sen todentajalle. $u$ $m=f(r\|u)$ $s$ $m$ $(s,u)$
$V$ varmistaa, että viestin allekirjoitus on sama ja kelvollinen . $m=f(r\|u)$ $s$ $m$

Yllä olevissa protokollissa salaiset tiedot ovat avaimet , joiden tunteminen todistaa aiheen . Jos kaikkien tarkastusten tulokset viimeisissä vaiheissa onnistuvat, katsotaan, että hänellä todella on salaisuus. $(p,q)$ $P$ $P$

Muistiinpanot

↑ Menezes, Oorschot, Vanstone, 1996 , §11.7, s. 2, s. 473-474.
↑ Minghua, 2001 , s. yksi.
↑ Schneier, 2002 , luku 20, s. 6.
↑ Atsushi, 1991 , luku 2, kappale 3: "Oletamme, että korkeamman asteen versiomme (ESIGN) rikkominen on yhtä vaikeaa kuin N:n laskeminen".
↑ 1 2 Schneier, 2002 , luku 2, s. 6.
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , §11.7, s. 2, s. 473.
↑ Menezes, Oorschot, Vanstone, 1996 , §11.9, s. 486-487.
↑ Minghua, 2001 , s. 3.
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , §11.7, s. 2, s. 474.
↑ Minghua, 2001 , s. neljä.
↑ Minghua, 2001 , s. 6.
↑ Minghua, 2001 , s. 7.
↑ Atsushi, 1991 , luku 3.
↑ Atsushi, 1991 , luku 4.

Kirjallisuus

Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Alfred J. Menezes, Paul C. van Oorschot ja Scott A. Vanstone. Luku 11. Digitaaliset allekirjoitukset // Handbook of Applied Cryptography . - 5. painos - CRC Press , 1996. - S. 473-474. — 816 s. - ISBN 0-8493-8523-7 .
Atsushi Fujioka, Tatsuaki Okamoto, Shoji Miyaguchi. ESIGN: Tehokas digitaalisen allekirjoituksen toteutus älykorteille // Advances in Cryptology - EUROCRYPT '91 : Proceedings of Conf. / Advances in Cryptology - EUROCRYPT '91, Brighton, UK, 8.-11. huhtikuuta 1991. - Springer Berlin Heidelberg, 1991. - P. 446-457 . — ISBN 978-3-540-54620-7 . (linkki ei saatavilla)
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang Salauksen turvallisuustason arviointi: ESIGN-allekirjoitusmalli : projektimateriaalit / CRYPREC Project, Japani. - 2001. - tammikuuta. Arkistoitu alkuperäisestä 9. elokuuta 2017.