Nopea digitaalinen allekirjoitus

Nopea digitaalinen allekirjoitus on digitaalisen allekirjoituksen muunnelma , joka käyttää algoritmia , jossa on paljon pienempi (kymmeniä kertoja) määrä modulaarisia aritmeettisia laskutoimituksia perinteisiin EDS -menetelmiin verrattuna . Nopea sähköinen allekirjoitusjärjestelmä , kuten tavallinen, sisältää algoritmin käyttäjän avainparien luomiseksi , allekirjoituksen laskentatoiminnon ja allekirjoituksen vahvistustoiminnon.

EDS-ongelmat

EDS : n keksimisestä vuonna 1976 lähtien se on ollut lupaavin tutkimusalue julkisen avaimen salausjärjestelmissä . Yksi tavanomaisista matemaattisista ratkaisuista kryptografisten algoritmien rakentamiseen on diskreetti logaritmiongelma , jonka pohjalta on kehitetty monia algoritmeja digitaalisten allekirjoitusten saamiseksi . Perinteisten EDS - algoritmien , kuten ElGamal-mallin ja RSA :n , suurin haittapuoli on niiden laskennallinen monimutkaisuus. Eksponenttien laskeminen modulaarisessa aritmetiikassa on laskentaintensiivisintä julkisen avaimen salausjärjestelmäjärjestelmissä . Tällä hetkellä tehdään paljon työtä salausalgoritmien suorituskyvyn parantamiseksi vähentämällä eksponenttilaskelmien määrää. Lyhin tunnettu EDS -malli on elliptisiä käyriä käyttävä BLS (Boneh–Lynn–Shacham) , mutta se on rajoitettu ryhmiin , joilla on pariliitostoiminto . Algoritmien kehittäjät pyrkivät sekä parantamaan perinteisiä diskreettejä logaritmijärjestelmiä käyttämällä eksponentien rinnakkaislaskentaa että tutkimaan perustavanlaatuisia erilaisia lähestymistapoja, jotka perustuvat esimerkiksi graafiteoriaan modulaarisen aritmeettisen sijaan .

Jotkut nopeat digitaalisen allekirjoituksen algoritmit

Diffie-Hellman-algoritmiin perustuva nopea EDS-järjestelmä

Olkoon Abelin ryhmä , sen syklinen aliryhmä järjestysgeneraattorilla , jossa on suuri alkuluku . Olkoon ja suojausparametrit ja . Anna , ja on hash-funktiot . Allekirjoituskaavio on seuraava: $\G$ $\G_{g,q}$ $\g$ $\ q$ $\ q$ $\ l_q$ $\ l_p$ $\ l_q = |q|$ $H: { \{0, 1\}^* } \rightarrow\ G_{g,q}$ $L: { \{ 0, 1 \}^*}\rightarrow\ Z_q^*$ $G: { \{0, 1 \}^*}\rightarrow\ Z_q^*$

Avaimen sukupolvi

Käyttäjä valitsee satunnaisen salaisen avaimen ja laskee julkisen avaimen . $x \in\ Z_q^*$ $y = g^x$

Luo allekirjoitus

Syötteet ovat salainen avain ja viesti . $x \in\ Z_q^*$ $m \in \{ 0, 1 \}^*$

Seuraavaksi allekirjoituksen luova puoli:

1. valitsee satunnaisluvun ja satunnaisbitin ; $k \in \Z_q^*$ $b_m \in \{ 0, 1 \}$

2. laskee ; $\h=H(m,b_m)$

3. laskee ; $\ u = h^x$

4. laskee , missä ; $\ v = ( g^n*h)^k$ $\ n = L(m, g, h, y, u)$

5. laskee ; $\r = G(m, g, h, y, u, v)$

6. laskee . $s = k - xr\mod\q$

Viestin allekirjoitus on . $\m$ $\sigma\ = (u,r,s,b_m)$

Allekirjoituksen vahvistus

Voit tarkistaa viestin allekirjoituksen m seuraavasti: $\ \sigma$

1. edustettuna ; $\ \sigma$ $\ (u,r,s,b_m)$

2. ja lasketaan ; $\h = H(m,b_m)$ $\ n = L(m,g,h,y,u)$

3. laskettu ; $v \alkuluku \ = (g^n*h)^s* (y^n*u)^r$

4. tarkistetaan, onko . $\ r = G(m,g,h,y,u,v\alkuluku)$

Jos yhtäläisyys vaiheessa 4 on tosi, allekirjoitus läpäisee vahvistuksen.

Fiat-Shamir-algoritmiin perustuva nopea EDS-järjestelmä

ZN tarkoittaa kokonaislukujen rengasta modulo , ja ovat turvaparametreja , yleensä , $\N$ $\t$ $\p$ $\t \leqslant\ 4$ $\p \leqslant\ 20$

Key Authentication Centerin (KAC) rooli

SERT valitsee:

satunnaiset alkuluvut ja niin, että ; $\p$ $\ q$ $\p,q \geqslant\ 2^{256}$

yksisuuntainen hash-toiminto ; $\ h: Z_N\otimes Z \rightarrow\ {\{0,1\))^tk$

omat yksityiset ja julkiset avaimensa.

CAC julkaisee , ja julkinen avain . $\ N=p*q$ $\h$

CAC:n yksityistä avainta käytetään sen luomien julkisten avainten allekirjoittamiseen . Tällaisten allekirjoitusten luomiseen CAC voi käyttää mitä tahansa suojattua EDS - järjestelmää .

Käyttäjäavaimien luominen.

Jokainen käyttäjä valitsee salaisen avaimen , joka koostuu satunnaisluvuista , jotka vaihtelevat välillä 1 - , niin että GCD kaikille on 1 - . Allekirjoituksen luomista voidaan nopeuttaa valitsemalla pienet kokonaisluvut kuten . Tällaisen järjestelmän turvallisuus perustuu oletukseen, että juurien laskeminen on vaikeaa. Tällä hetkellä ei tiedetä juuret laskevien algoritmien olemassaolosta , jos juuret ovat järjestyksessä . $\s = (s_1,\cdots\,s_k)$ $\ s_i$ $\ s_i$ $\N$ $\ (si,N) = 1$ $\s$ $\k$ $\s_1,\cdots\,s_k$ $2^t \mod\ N$ $2^t \mod\ N$ $\N^{2^{-t+1}}$

Käyttäjän rekisteröinti.

CAC varmistaa, että käyttäjä täsmää, luo merkkijonon, joka sisältää nimen, osoitteen jne., ja luo allekirjoituksen parille , joka koostuu käyttäjän julkisesta avaimesta . $\I$ $\S$ $\ (I,v)$ $\I$ $\v$

Allekirjoituksen luominen.

Syöteviesti , salainen avain ja - moduuli , jota käytetään laskelmiin. $\m$ $\s = (s_1,\cdots\,s_k)$ $\N$

1. Satunnaisluku valitaan alueelta ja lasketaan . $\r$ $\ [1,N]$ $\ x = r^{2^t}$

2. Laskettu . $\ e = (e_11,\cdots\, e_tk) = h(x,m)$

3. Laskettu . $\ y = r \prod\nlimits_{j=1}^k s_j^{\sum\nolimits_{i=1}^t e_{ij}*2^{i-1}} \mod\ N$

Lähtöallekirjoitus on pari . $\ (e,y)$

Allekirjoituksen luominen vaatii korkeintaan modulo - kertoja , ja keskimäärin satunnainen vaatii vain kertolaskuja. $\{k*t+t-1}$ $\ e$ $\t(k+2)/2+1$

Allekirjoituksen vahvistus.

Syöttötiedot — allekirjoitus , viesti , , . $\ (e,y)$ $\m$ $\v = (v_1,\cdots\,v_k)$ $\ I,S,N$

1. Allekirjoitus henkilölle . $\S$ $\ (I,v)$

2. Laskettu . $\ z = y^{2^t}\prod\nolimits_{j=1}^k v_j^{\sum\nolimits_{i=1} e_{ij}*2^{i-1}} \mod\ N$

3. Tarkista, että . $\e=h(z,m)$

Allekirjoituksen tarkistamiseksi se vaaditaan keskimäärin satunnaisissa modulo-kertooperaatioissa enintään . $\ e$ $\t(k+2)/2+1$ $\ {k*t + t}$

Allekirjoituksen suojaus.

Väärentääkseen viestin allekirjoituksen kryptanalyytikon on ratkaistava yhtälö ja . $\m$ $\ e =h (y^{2^t}\prod\nolimits_{j=1}^k v_j^{\sum\nolimits_{i=1}^t e_{i,j}*2^{i-1 }},m) \mod\N$ $\ e$ $\y$

Tällä hetkellä ei ole tunnettuja algoritmeja tämän yhtälön ratkaisemiseksi.

Nopean EDS:n käyttö

Nopeat digitaalisen allekirjoituksen algoritmit ovat tehokkaimpia tapauksissa, joissa avaimen saamisen nopeus ja allekirjoituksen pieni koko ovat ensisijaisen tärkeitä. Samanlaisia vaatimuksia on mobiili-, anturi- tai henkilökohtaisissa verkoissa (joiden säde on rajoitettu yhteen huoneeseen) multimedialiikenteen siirron yhteydessä. Digitaalisen allekirjoituksen käyttö GSM-matkapuhelimissa antaa käyttäjälle mahdollisuuden luoda PIN-koodin itse sen sijaan, että saisit sen operaattorilta.

Nopeutetun digitaalisen allekirjoituksen luomisalgoritmien käyttöönotto laitteissa, joilla on rajalliset resurssit, kuten PDA:t, sulautetut älykortit ja matkapuhelimet, joiden laskentateho on paljon henkilökohtaisten tietokoneiden kykyjä heikompi, mahdollistaa vähemmän energian kulutuksen allekirjoituksen luomiseen ja tallentamiseen. ja siten pidentää laitteen käyttöaikaa ilman latausta.

Kirjallisuus

Nopeat digitaaliset allekirjoitusjärjestelmät yhtä turvallisia kuin Diffie-Hellmanin oletukset, Changshe Ma , Jian Weng ja Dong Zheng , 22. tammikuuta 2007

Fasr Signature Generation Fiat Shamirin kaltaisella järjestelmällä, H.Ong , CPSchnorr

Katso myös

Diffie-Hellman-algoritmi

Shamir-suunnitelma

Nopea julkisen avaimen salausjärjestelmä

Julkisen avaimen salausjärjestelmä

ElGamalin kaava

Digitaalinen allekirjoitus

Linkit

US-patentti 5,263,085