Lamportin allekirjoitus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 31. joulukuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 16 muokkausta .

Lamport - allekirjoitus on digitaalisen allekirjoituksen salausjärjestelmä julkisella avaimella. Voidaan rakentaa mihin tahansa yksisuuntaiseen toimintoon . Sitä ehdotettiin vuonna 1979 ja se nimettiin sen kirjoittajan, amerikkalaisen tiedemiehen Leslie Lamportin [1] mukaan .

Kuvaus

Olkoon Alicella 256-bittinen kryptografinen hash-funktio ja kryptografisesti vahva näennäissatunnaislukugeneraattori . Hän haluaa luoda ja käyttää Lamportin avainparia, yksityistä avainta ja sitä vastaavaa julkista avainta .

Avainparin luominen

Alice käyttää satunnaislukugeneraattoria luodakseen salaisen avaimen 256 paria satunnaislukuja (yhteensä 2x256 numeroa). Jokainen numero koostuu 256 bitistä, joten kokonaiskoko on 2x256x256 bittiä = 16 KiB . Nämä numerot ovat Alicen salainen avain, ja hän säilyttää ne salaisessa paikassa myöhempää käyttöä varten.

Julkisen avaimen luomiseksi Alice tiivistää jokaisen 512 yksityisen avaimen numerosta, mikä tekee 512 tiivistettä, joissa kussakin on 256 bittiä. Nämä 512 tiivistettä muodostavat Alicen julkisen avaimen, jonka hän julkaisee.

Viestin allekirjoitus

Nyt Alice haluaa allekirjoittaa viestin. Ensin se tiivistää viestin ja saa 256-bittisen tiivisteen. Sitten jokaiselle hash-bitille se ottaa vastaavan numeron salaisesta avaimesta. Jos esimerkiksi viestin hajautusarvon ensimmäinen bitti on nolla, se ottaa ensimmäisen numeron ensimmäisestä salaisesta avainparista. Jos ensimmäinen bitti on yhtä suuri kuin yksi, se käyttää toista numeroa ensimmäisestä parista. Ja niin edelleen. Tuloksena saadaan 256 satunnaislukua, joiden koko on 256 × 256 bittiä = 8 KiB. Nämä numerot muodostavat allekirjoituksen, jonka Alice lähettää viestin mukana.

Huomaa, että kun Alice on käyttänyt yksityistä avaimeansa, sitä ei saa koskaan käyttää uudelleen. Loput 256 numeroa, joita hän ei käyttänyt allekirjoituksessa, Alice ei saa koskaan julkaista tai käyttää. On parempi, että hän poistaa ne, muuten joku voi käyttää niitä ja luoda väärennetyn allekirjoituksen niillä.

Allekirjoituksen vahvistus

Bob haluaa vahvistaa allekirjoituksen, jolla Alice allekirjoitti viestin. Se myös tiivistää viestin ja saa 256-bittisen tiivisteen. Sitten hän valitsee jokaiselle tiivisteen bitille numeron Alicen julkisesta avaimesta. Nämä numerot valitaan samalla tavalla kuin Alice valitsi numerot allekirjoitukselleen. Toisin sanoen, jos viestin hashin ensimmäinen bitti on nolla, Bob valitsee ensimmäisen numeron julkisen avaimen ensimmäisestä parista. Ja niin edelleen.

Sitten Bob tiivistää kaikki Alicen allekirjoituksen 256 numeroa ja saa 256 tiivistettä. Jos nämä 256 tiivistettä vastaavat täsmälleen niitä 256 tiivistettä, jotka hän juuri sai Alicen julkisesta avaimesta, Bob uskoo allekirjoituksen olevan aito. Jos ne eivät täsmää, se on väärennös.

On syytä huomata, että ennen kuin Alice julkaisee viestin allekirjoituksen, kukaan ei tiedä 2x256 satunnaislukua salaisessa avaimessa. Näin ollen kukaan ei voi luoda oikeaa 256 numeron joukkoa allekirjoitettavaksi. Sen jälkeen, kun Alice on julkaissut allekirjoituksen, kukaan ei vieläkään tiedä muita 256 numeroa, eikä näin ollen voi luoda allekirjoitusta viesteille, joilla on erilainen hash [2] .

Esimerkki

Anna Alice lähettää viesti M = "Lamport" Bobille, allekirjoittaen se Lamportin allekirjoituksella ja käyttämällä 8-bittistä hash-funktiota. Eli alkuperäinen viesti muunnetaan 8-bittiseksi hashiksi.

Avaimen luominen

Satunnaislukugeneraattorin avulla Alice saa kahdeksan paria satunnaislukuja. Nämä 16 numeroa ovat Alicen yksityinen avain.

Yksityinen avain: $(13,$ $134)$ $(128,$ $67)$ $(25,$ $90 ) (78,$ $156)$ $(89,$ $37)$ $(234,$ $29)$ $(199,$ $74)$ $(12,$ $3)$

Saadakseen julkisen avaimen Alice laskee hajautusarvon jokaiselle numerolle yksityisestä avaimesta.

Julkinen avain:

$(00101010,$ $10010101)$

$(01100111,$ $11010101)$

$(00101110,$ $11110111)$

$(00100101,$ $11011101)$

$(11100001,$ $00011000)$

$(11000110,$ $11001110)$

$(11001101,$ $11001001)$

$(11100011,$ $11111101)$

Alice julkaisee tuloksena olevan julkisen avaimen yleisölle.

Viestin allekirjoitus

Alice haluaa allekirjoittaa viestin M = "Lamport". Tätä varten se laskee tämän viestin hash-arvon ja yhdistää jokaisen tiivisteen bitin johonkin yksityisten avainparien arvoista muodostaen siten allekirjoituksen. $H(M) = 01011010$

Viestin allekirjoitus "Lamport": $(13,$ $67,$ $25,$ $156,$ $37,$ $234,$ $74,$ $12)$

Allekirjoituksen vahvistus

Bob saa allekirjoitetun viestin "Lamport" ja haluaa tarkistaa, lähettikö Alice todella sen. Tätä varten hän käyttää julkista avainta, jonka Alice julkaisi. Se muuntaa vastaanotetun viestin hashiksi ja yhdistää tuloksena olevan tiivisteen jokaisen bitin julkisessa avaimessa olevan parin numeroksi. Sitten se tiivistää viestin allekirjoituksen ja vertaa tuloksena saatuja kahta numerosarjaa. Jos ne ovat yhtä suuret, allekirjoitus on todellinen, ja viestit todellakin lähetti Alice.

Julkisesta avaimesta saatu numerosarja:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Allekirjoituksen tiiviste:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Koska nämä joukot ovat yhtä suuret, allekirjoitus on todellinen.

Matemaattinen kuvaus

Avaimet

Antaa olla positiivinen luku, antaa olla joukko viestejä ja antaa olla yksisuuntainen funktio . $k$ $P=\{0,1\}^k$ $f:\,Y\oikeanuoli Z$

Jokaisen ja viestin allekirjoittava osapuoli valitsee ja laskee satunnaisesti . $1\leq i\leq k$ $j\in\{0,1\}$ $y_{i,j}\in Y$ $z_{i,j}=f(y_{i,j})$

Salainen avain koostuu . Julkinen avain koostuu arvoista . [3] $K$ $2k$ $y_{i,j}$ $2k$ $z_{i,j}$

Viestin allekirjoitus

Olkoon viesti. $m = m_1\lpisteet m_k \in\{0,1\}^k$

Viestin allekirjoitus on . $merkki(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k)$

Allekirjoituksen vahvistus

Allekirjoituksen vahvistava osapuoli varmistaa kaikkien . $f(s_i) = z_{i,m_i}$ $1\leq i\leq k$

Väärentääkseen viestin allekirjoituksen kryptanalyytikon olisi käännettävä yksisuuntainen funktio , jonka oletetaan olevan laskennallisesti mahdotonta. $f$

Turvallisuus

Lamport - allekirjoitusten kryptografinen vahvuus perustuu hajautusfunktion kryptografiseen vahvuuteen .

Jokaiselle n-bittisen tiivisteen luovalle tiivistefunktiolle ihanteellinen esikuvan palautuksen ja toisen esikuvan palautuksen vastus edellyttää 2 n operaatiota ja 2 n bittiä muistia klassisessa laskentamallissa jokaista hash-funktion suoritusta kohti . Groverin algoritmia käyttäen ideaalisen hash-funktion esikuvan palautus rajoittuu edellä O(2 n /2 ) -operaatioihin kvanttilaskentamallissa [4] .

Useita viestien allekirjoituksia

Vain yksi viesti voidaan allekirjoittaa yhdellä Lamportin yksityisellä avaimella. Tämä tarkoittaa, että jos tietty määrä viestejä allekirjoitetaan, sama määrä julkisia avaimia on julkaistava. Mutta jos käytät julkisista avaimista koostuvaa Merkle-puuta , voit julkaista vain puun yläosan sen sijaan, että julkaiset kaikki julkiset avaimet. Tämä kasvattaa allekirjoituksen kokoa, koska osa tiivistepuusta on sisällytettävä allekirjoitukseen, mutta se mahdollistaa yhden hajautusarvon käyttämisen useiden allekirjoitusten tarkistamiseen. Tämän järjestelmän mukaan voit allekirjoittaa viestejä, missä on Merkle-puun syvyys . Eli teoriassa voimme käyttää yhtä julkista avainta kuinka monta viestiä tahansa [5] . $N = 2^n$ $n$

Avaimen luominen

Ensin sinun on luotava Lamportin yksityiset kerta-avaimet ja Lamportin julkiset kerta-avaimet . Lisäksi jokaiselle julkiselle avaimelle , jossa , sen hash lasketaan . Ja näiden arvojen pohjalta rakennetaan Merkle-puu . $2^{n}$ $X_{i}$ $Y_{i}$ $Y_{i}$ $1 \leq i \leq 2^n$ $h_{i}=H(Y_{i})$ $Hei}$

Numeroimme puun solmut siten, että indeksi ilmaisee etäisyyden tästä solmusta lehtielementtiin ja indeksi osoittaa solmun järjestysnumeron vasemmalta oikealle samalla tasolla . $a_{i,j}$ $i$ $j$ $i$

Puussamme hash-arvot ovat lehtielementtejä, eli . Jokainen puun ei-lehtisolmu on hash-arvo kahden lapsen liittämisestä yhteen, eli , ja niin edelleen. $Hei}$ $h_i=a_{0,i}$ $a_{1,0}=H(a_{0,0}||a_{0,1})$ $a_{2,0}=H(a_{1,0}||a_{1,1})$

Näin ollen meillä on puu, jonka juurielementti on julkinen avaimemme . $pub$

Viestin allekirjoitus ja vahvistus

Allekirjoittaaksesi viestin mallimme mukaisesti, sinun on ensin allekirjoitettava se kertaluonteisella Lamport-allekirjoituksella . Tämä tehdään käyttämällä jotakin julkisen/yksityisen avainpareista . $sig'$ $(X_i, Y_i,)$

$a_{0,i}=H(X_i)$ on julkista avainta vastaavan puun lehtielementti. Polku puun lehtielementistä sen latvaan koostuu elementeistä , missä on lehtielementti ja puun latva. Tämän polun laskemiseksi tarvitsemme kaikki solmujen lapset . Tiedämme, että solmu on solmun lapsi . Jotta voimme laskea seuraavan solmun polulla huipulle, tarvitsemme solmun molemmat jälkeläiset . Siksi meidän on tiedettävä solmun "veli" . Soitetaan hänelle . Joten ,. Siksi tarvitsemme solmuja laskeaksemme puun huipun. Laskemme ne ja tallennamme ne. $X_{i}$ $a_{0,i}$ $A_0, ... A_n$ $A_0=a_{0,i}$ $A_n=a_{n,0}=pub$ $A_{1}, ..., A_{n}$ $A_{i}$ $A_{{i+1}}$ $A_{{i+1}}$ $A_{i}$ $auth_i$ $A_{i+1}=H(A_i||auth_i)$ $n$ $auth_0,...,auth_{n-1}$

Nämä solmut yhdessä viestin kertaluonteisen allekirjoituksen kanssa muodostavat lopullisen allekirjoituksen . $sig'$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$

Viestin vastaanottajalla on käytössään julkinen avain , viesti ja allekirjoitus . Se tarkistaa ensin viestin kertaluonteisen allekirjoituksen . Jos se on aito, vastaanottaja laskee . Ja sitten laskelmiin . Jos se on yhtä suuri kuin , allekirjoitusta pidetään autenttisena. $pub$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$ $sig'$ $M$ $A_0=H(X_i)$ $j = 1,..., n-1$ $A_j=H(A_{j-1}||auth_{j-1})$ $A_{n}$ $pub$

Erilaisia optimointeja ja toteutuksia

Lyhyt salainen avain

Sen sijaan, että luotaisiin ja tallennettaisiin kaikki salaisen avaimen satunnaisluvut, voidaan tallentaa yksi sopivan kokoinen numero. Tyypillisesti koko valitaan niin, että se on sama kuin yksityisen avaimen yhden satunnaisluvun koko. Tätä avainta voidaan käyttää satunnaislukugeneraattorin (CSPRNG) siemenenä, jotta koko satunnaislukujen salainen avainsarja voidaan tarvittaessa luoda uudelleen.

Samalla tavalla avainta voidaan käyttää yhdessä CSPRNG:n kanssa useiden Lamport-avaimien luomiseen. Suosittuja ovat CSPRNG:t, joilla on korkea kryptografinen vahvuus, kuten BBS .

Lyhyt julkinen avain

Lamport-allekirjoitusta voidaan käyttää yhdessä tiivisteluettelon kanssa, mikä mahdollistaa vain yhden tiivisteen sisällyttämisen julkiseen avaimeen. Eli arvojen sijasta - . Jotta allekirjoituksen satunnaislukuja voidaan verrata julkisen avaimen tiivisteeseen, kaikki julkisessa avaimessa käyttämättömät tiivisteet eli minkä tahansa arvot on sisällytettävä allekirjoitukseen. Tämän seurauksena julkinen avain lyhenee huomattavasti ja allekirjoituksen koko noin kaksinkertaistuu. $2k$ $z_{{ij}}$ $(z_{ij})$ $j\neq m_i$

Viestin hajautus

Lamportin digitaalinen allekirjoitusmalli ei vaadi sanoman m tiivistämistä ennen sen allekirjoittamista. Hashingilla voidaan allekirjoittaa esimerkiksi pitkiä viestejä, joissa allekirjoitetaan viestin hash, ei itse viestiä [6] .

Vertailu muihin kryptojärjestelmiin

Lamportin kerta-allekirjoitusjärjestelmän tärkeimmät edut ovat, että se voidaan rakentaa mille tahansa yksisuuntaiselle funktiolle ja että sen allekirjoituksen ja sanoman varmistusalgoritmi on huomattavasti nopeampi kuin uudelleenkäytettävien allekirjoitusjärjestelmien algoritmit. Samaan aikaan järjestelmällä on useita haittoja. Ensinnäkin haittana on avainten kertakäyttöisyys. Toisin sanoen jokaista uutta viestiä allekirjoitettaessa on luotava uusi pari, mikä johtaa järjestelmän monimutkaisuuteen. Toiseksi järjestelmän haittapuolena on suuri allekirjoituksen koko ja julkisten ja yksityisten avainten pari [7] .

Tällä järjestelmällä on potentiaalia, kun otetaan huomioon, että kvanttitietokoneen mahdollinen kehitys uhkaa monien laajalti käytettyjen algoritmien, kuten RSA :n, turvallisuutta , kun taas Lamport-allekirjoitus säilyy myös tässä tapauksessa [8] . Yhdessä Merkle-puiden kanssa Lamport-salausjärjestelmää voidaan käyttää useiden viestien todentamiseen, mikä toimii varsin tehokkaana digitaalisena allekirjoituksena [9] .

Muistiinpanot

↑ Lamport, 1979 , s. 2.
↑ Lamport, 1979 , s. 3-5.
↑ Katz , s. 2.
↑ M. I. Anokhin, N. P. Varnovsky, V. M. Sidelnikov, V. V. Yashchenko, Lamport ja Naor-Jungin kaaviot . Käyttöpäivä: 17. joulukuuta 2013. Arkistoitu alkuperäisestä 17. joulukuuta 2013. (määrätön)
↑ Michael Szydlo, MERKLE-PUIEN TEHOKAS KÄYTTÖ . Haettu 24. marraskuuta 2013. Arkistoitu alkuperäisestä 17. huhtikuuta 2017. (määrätön)
↑ Lamport, 1979 , s. 6.
↑ Zaverucha, 2010 , s. yksi.
↑ Garcia , s. kymmenen.
↑ Vadim Malykh, "Sähköisten asiakirjojen pitkäaikainen varastointi" . Käyttöpäivä: 13. joulukuuta 2013. Arkistoitu alkuperäisestä 13. joulukuuta 2013. (määrätön)

Kirjallisuus

Lamport L. Digitaalisten allekirjoitusten rakentaminen yksisuuntaisesta funktiosta . - SRI International Computer Science Laboratory, 1979.
Peikert K. Kryptografian teoreettiset perusteet . - Georgia Tech, 2010. Arkistoitu19. joulukuuta 2013Wayback Machinessa
Katz J. Johdatus kryptografiaan . - Marylandin yliopisto.
Zaverucha G. Stinson R. Cheriton R. Lyhyet kerta-allekirjoitukset . – Waterloon yliopisto, 2010.
Garcia L. Merklen allekirjoitusjärjestelmän turvallisuudesta ja tehokkuudesta . – Darmstadt.

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
Muut	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

Lamportin allekirjoitus

Kuvaus

Avainparin luominen

Viestin allekirjoitus

Allekirjoituksen vahvistus

Esimerkki

Avaimen luominen

Viestin allekirjoitus

Allekirjoituksen vahvistus

Matemaattinen kuvaus

Avaimet

Viestin allekirjoitus

Allekirjoituksen vahvistus

Turvallisuus

Useita viestien allekirjoituksia

Avaimen luominen

Viestin allekirjoitus ja vahvistus

Erilaisia ​​optimointeja ja toteutuksia

Lyhyt salainen avain

Lyhyt julkinen avain

Viestin hajautus

Vertailu muihin kryptojärjestelmiin

Muistiinpanot

Kirjallisuus

Erilaisia optimointeja ja toteutuksia