Lamport aláírása

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. december 31-én felülvizsgált verziótól ; az ellenőrzések 16 szerkesztést igényelnek .

A Lamport aláírás egy nyilvános kulccsal rendelkező digitális aláírási titkosítási rendszer . Bármilyen egyirányú funkcióra építhető . 1979-ben javasolták, és szerzőjéről, egy amerikai tudósról, Leslie Lamportról nevezték el [1] .

Leírás

Legyen Alice -nek egy 256 bites kriptográfiai hash függvénye és egy kriptográfiailag erős pszeudo-véletlenszám-generátora . Létre akarja hozni és használni a Lamport kulcspárját, egy privát kulcsot és a hozzá tartozó nyilvános kulcsot .

Kulcspár létrehozása

A titkos kulcs generálásához Alice véletlenszám-generátorral 256 véletlenszámpárt generál (összesen 2x256 számot). Mindegyik szám 256 bitből áll, tehát a teljes méret 2x256x256 bit = 16 KiB . Ezek a számok Alice titkos kulcsai lesznek, és egy titkos helyen fogja őket későbbi felhasználás céljából.

A nyilvános kulcs létrehozásához Alice kivonatolja mind az 512 privát kulcsszámot, így 512, egyenként 256 bites kivonatot készít. Ez az 512 hash alkotja Alice nyilvános kulcsát, amelyet közzétesz.

Üzenet aláírása

Most Alice alá akarja írni az üzenetet. Először is kivonatolja az üzenetet, és 256 bites hash-t kap. Ezután a hash minden egyes bitjéhez kiveszi a megfelelő számot a titkos kulcsból. Ha például az üzenetkivonat első bitje nulla, akkor az első titkos kulcspárból veszi az első számot. Ha az első bit egyenlő eggyel, akkor az első párból származó második számot használja. Stb. Ennek eredményeként 256 véletlen számot kapunk, amelyek mérete 256 × 256 bit = 8 KiB. Ezek a számok alkotják az aláírást, amelyet Alice az üzenettel együtt küld.

Vegye figyelembe, hogy ha Alice már használta a privát kulcsát, soha többé nem szabad használni. A fennmaradó 256 számot, amelyeket nem használt az aláírásban, Alice soha nem teheti közzé vagy használhatja. Javasoljuk, hogy törölje őket, különben valaki hozzáférhet hozzájuk, és hamis aláírást generálhat velük.

Aláírás ellenőrzése

Bob ellenőrizni akarja az aláírást, amellyel Alice aláírta az üzenetet. Ezenkívül kivonatolja az üzenetet, és 256 bites hash-t kap. Ezután a hash minden bitjéhez választ egy számot Alice nyilvános kulcsából. Ezeket a számokat ugyanúgy választják ki, ahogy Alice az aláírásához választotta a számokat. Ez azt jelenti, hogy ha az üzenet hash első bitje nulla, Bob kiválasztja az első számot a nyilvános kulcs első párjából. Stb.

Ezután Bob kivonatolja az Alice aláírásából származó 256 számot, és 256 kivonatot kap. Ha ez a 256 hash pontosan megegyezik azzal a 256 kivonattal, amelyet most kapott Alice nyilvános kulcsából, Bob úgy véli, hogy az aláírás eredeti. Ha nem egyeznek, akkor hamis.

Érdemes megjegyezni, hogy mielőtt Alice közzéteszi az üzenet aláírását, senki sem tud 2x256 véletlen számot a titkos kulcsban. Így senki sem tudja létrehozni a megfelelő 256 számból álló készletet, amelyet aláírhat. Miután Alice közzétette az aláírást, senki sem ismeri a többi 256 számot, így nem tud aláírást létrehozni olyan üzenetekhez, amelyek más hash-t tartalmaznak [2] .

Példa

Alice küldjön egy M = " Lamport " üzenetet Bobnak, aláírva azt Lamport aláírásával és egy 8 bites hash függvény használatával. Ez azt jelenti, hogy az eredeti üzenet 8 bites hash-re lesz konvertálva.

Kulcsgenerálás

Egy véletlenszám-generátor segítségével Alice nyolc véletlen számpárt kap. Ez a 16 szám Alice privát kulcsa.

Privát kulcs: $(13,$ $134)$ $(128,$ $67)$ $(25,$ $90 ) (78,$ $156)$ $(89,$ $37)$ $(234,$ $29)$ $(199,$ $74)$ $(12,$ $3)$

A nyilvános kulcs megszerzéséhez Alice minden egyes számhoz kivonatértéket számít ki a privát kulcsból.

Nyilvános kulcs:

$(00101010,$ $10010101)$

$(01100111,$ $11010101)$

$(00101110,$ $11110111)$

$(00100101,$ $11011101)$

$(11100001,$ $00011000)$

$(11000110,$ $11001110)$

$(11001101,$ $11001001)$

$(11100011,$ $11111101)$

Alice nyilvánosságra hozza a kapott nyilvános kulcsot.

Üzenet aláírása

Alice alá akarja írni az üzenetet M = "Lamport". Ehhez kiszámítja ennek az üzenetnek a hash értékét, és a hash minden bitjét társítja a privát kulcspárok egyik értékéhez, ezáltal aláírást hoz létre. $H(M)=01011010$

"Lamport" üzenet aláírása: $(13,$ $67,$ $25,$ $156,$ $37,$ $234,$ $74,$ $12)$

Aláírás ellenőrzése

Bob egy aláírt "Lamport" üzenetet kap, és szeretné ellenőrizni, hogy Alice valóban küldte-e. Ehhez az Alice által közzétett nyilvános kulcsot használja. A kapott üzenetet hash-vé alakítja, és az eredményül kapott hash minden bitjét leképezi a nyilvános kulcsban lévő párból származó számokra. Ezután kivonatolja az üzenet aláírását, és összehasonlítja a kapott két számkészletet. Ha egyenlők, akkor az aláírás valódi, és az üzeneteket valóban Alice küldte.

A nyilvános kulcsból kapott számok halmaza:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Aláírás hash:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Mivel ezek a halmazok egyenlőek, az aláírás valódi.

Matematikai leírás

Billentyűk

Legyen pozitív szám, legyen üzenetek halmaza, és legyen egyirányú függvény . $k$ $P=\{0,1\}^k$ $f:\,Y\jobbra Z$

Mindegyik és esetén az üzenetet aláíró fél véletlenszerűen választ és kiszámít . $1\leq i\leq k$ $j\in\{0,1\}$ $y_{i,j}\Y-ban$ $z_{i,j}=f(y_{i,j})$

A titkos kulcs a következőkből áll . A nyilvános kulcs értékekből áll . [3] $K$ $2k$ $y_{i,j}$ $2k$ $z_{i,j}$

Üzenet aláírása

Legyen üzenet. $m = m_1\lpontok m_k \in\{0,1\}^k$

Az üzenet aláírása . $sign(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k)$

Aláírás ellenőrzése

Az aláírást érvényesítő fél mindenre ellenőrzi . $f(s_i) = z_{i,m_i}$ $1\leq i\leq k$

Üzenetaláírás hamisításához a kriptoanalizátornak meg kell invertálnia az egyirányú függvényt , ami számításilag lehetetlennek számít. $f$

Biztonság

A Lamport - aláírások kriptográfiai erőssége a hash függvény kriptográfiai erősségén alapul .

Minden egyes n-bites kivonatot generáló hash-függvény esetében az előkép-helyreállítással és a második előkép-helyreállítással szembeni ideális ellenállás 2 n műveletet és 2 n bit memóriát jelent a klasszikus számítási modellben a hash-függvény minden egyes végrehajtásához . Grover algoritmusát használva egy ideális hash függvény kép előtti helyreállítását egy kvantumszámítási modellben O(2 n /2 ) műveletek határolják [4] .

Több üzenet aláírása

Egyetlen Lamport privát kulccsal csak egyetlen üzenet írható alá. Ez azt jelenti, hogy ha bizonyos számú üzenetet írnak alá, akkor ugyanannyi nyilvános kulcsot kell közzétenni. De ha nyilvános kulcsokból álló Merkle-fát használ , akkor az összes nyilvános kulcs közzététele helyett csak a fa tetejét teheti közzé. Ez növeli az aláírás méretét, mivel a hash-fa egy részét bele kell foglalni az aláírásba, de lehetővé teszi egyetlen hash használatát több aláírás ellenőrzéséhez. E séma szerint írhat alá üzeneteket, hol van a Merkle-fa mélysége. Azaz elméletileg tetszőleges számú üzenethez használhatunk egy nyilvános kulcsot [5] . $N=2^n$ $n$

Kulcsgenerálás

Először létre kell hoznia a Lamport privát egyszeri kulcsait és a Lamport nyilvános egyszeri kulcsait . Továbbá minden nyilvános kulcshoz , ahol , a hash kiszámításra kerül . És ezekre az értékekre alapozva felépül egy Merkle fa . $2^{n}$ $X_{i}$ $Y_{i}$ $Y_{i}$ $1 \leq i \leq 2^n$ $h_{i}=H(Y_{i})$ $Szia}$

A fa csomópontjait úgy számozzuk meg, hogy az index a csomópont és a levélelem közötti távolságot, az index pedig a csomópont sorszámát jelölje balról jobbra, azonos szinten . $a_{i,j}$ $én$ $j$ $én$

Fánkban a hash értékek levélelemek, azaz . A fa minden nem leveles csomópontja egy hash érték, amely két gyermek összekapcsolásából származik, azaz , és így tovább. $Szia}$ $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})$

Így van egy fánk, amelynek gyökéreleme a nyilvános kulcsunk . $kocsma$

Üzenet aláírása és érvényesítése

Egy üzenet sémánk szerinti aláírásához először egyszeri Lamport-aláírással kell aláírnia . Ez a nyilvános/privát kulcspárok egyikével történik . $aláír$ $(X_i, Y_i,)$

$a_{0,i}=H(X_i)$ a nyilvános kulcsnak megfelelő fa levéleleme. A fa levélelemétől a tetejéig vezető út az elemekből áll , ahol a levélelem és a fa teteje. Ennek az útvonalnak a kiszámításához szükségünk van a csomópontok összes gyermekére . Tudjuk, hogy a csomópont a csomópont gyermeke . A csúcsra vezető útvonal következő csomópontjának kiszámításához szükségünk van a csomópont mindkét gyermekére . Ezért ismernünk kell a csomópont "testvérét" . Hívjuk őt . Szóval, . Ezért a fa tetejének kiszámításához csomópontokra van szükségünk . Kiszámoljuk és elmentjük őket. $X_{i}$ $a_{0,i}$ $A_0, ... A_n$ $A_0=a_{0,i}$ $A_n=a_{n,0}=közzététel$ $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}$

Ezek a csomópontok az üzenet egyszeri aláírásával együtt alkotják a végső aláírást . $aláír$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$

Az üzenet címzettjének rendelkezésére áll a nyilvános kulcs , az üzenet és az aláírás . Először az üzenet egyszeri aláírását ellenőrzi . Ha eredeti, akkor a címzett kiszámítja a . És akkor a számításokhoz . Ha egyenlő a -val, akkor az aláírás hitelesnek minősül. $kocsma$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$ $aláír$ $M$ $A_0=H(X_i)$ $j=1,...,n-1$ $A_j=H(A_{j-1}||auth_{j-1})$ $A_{n}$ $kocsma$

Különféle optimalizálások és megvalósítások

Rövid titkos kulcs

A titkos kulcs összes véletlenszámának generálása és tárolása helyett egyetlen megfelelő méretű szám tárolható. Általában a méretet úgy választják ki, hogy megegyezzen a privát kulcsban lévő véletlen szám méretével. Ez a kulcs egy véletlenszám-generátor (CSPRNG) magjaként használható, így a véletlenszámok teljes titkos kulcssorozata szükség esetén újra létrehozható.

Ugyanígy egy kulcs használható a CSPRNG-vel együtt több Lamport-kulcs létrehozásához. Előnyben részesítik a nagy kriptográfiai erősségű CSPRNG-ket, például a BBS -t .

Rövid nyilvános kulcs

A Lamport-aláírás a hashek listájával együtt használható, lehetővé téve, hogy egy nyilvános kulcsban csak egy hash szerepeljen. Vagyis értékek helyett - . Ahhoz, hogy az aláírásban lévő véletlen számokat össze lehessen hasonlítani a nyilvános kulcsban lévő hash-sel, minden, a nyilvános kulcsban nem használt hash-t, azaz bármely értékét szerepeltetni kell az aláírásban. Ennek eredményeként a nyilvános kulcs jelentősen lerövidül, és az aláírás mérete körülbelül megkétszereződik. $2k$ $z_{{ij}}$ $(z_{ij})$ $j\neq m_i$

Üzenetkivonat

A Lamport digitális aláírási sémája nem követeli meg az m üzenet kivonatolását az aláírás előtt. A kivonatolás használható például hosszú üzenetek aláírására, ahol az üzenet hash-je lesz aláírva, nem pedig maga az üzenet [6] .

Összehasonlítás más kriptorendszerekkel

A Lamport egyszeri aláírási sémájának fő előnye, hogy bármilyen egyirányú függvényre építhető , valamint, hogy aláírás- és üzenetellenőrző algoritmusa lényegesen gyorsabb, mint az újrafelhasználható aláírási rendszerek algoritmusai. Ugyanakkor a rendszernek számos hátránya van. Először is, a hátránya a kulcsok eldobhatósága. Azaz minden új üzenet aláírásakor új párt kell generálni, ami a rendszer bonyolításához vezet. Másodszor, a séma hátránya a nagy aláírásméret, valamint egy pár nyilvános és privát kulcs [7] .

Ebben a rendszerben van potenciál annak fényében, hogy egy kvantumszámítógép lehetséges fejlesztése számos széles körben használt algoritmus, például az RSA biztonságát veszélyezteti , míg a Lamport aláírás ebben az esetben is biztonságos marad [8] . A Merkle fákkal együtt a Lamport kriptorendszer több üzenet hitelesítésére is használható, és meglehetősen hatékony digitális aláírási sémaként működik [9] .

Jegyzetek

↑ Lamport, 1979 , p. 2.
↑ Lamport, 1979 , p. 3-5.
↑ Katz , p. 2.
↑ M. I. Anokhin, N. P. Varnovszkij, V. M. Szidelnyikov, V. V. Jascsenko, Lamport és Naor-Jung sémák . Hozzáférés időpontja: 2013. december 17. Az eredetiből archiválva : 2013. december 17. (határozatlan)
↑ Michael Szydlo, A MERKLE FÁK HATÉKONY HASZNÁLATA . Letöltve: 2013. november 24. Az eredetiből archiválva : 2017. április 17.. (határozatlan)
↑ Lamport, 1979 , p. 6.
↑ Zaverucha, 2010 , p. egy.
↑ Garcia , p. tíz.
↑ Vadim Malykh, "Elektronikus dokumentumok hosszú távú tárolása" . Hozzáférés dátuma: 2013. december 13. Az eredetiből archiválva : 2013. december 13. (határozatlan)

Irodalom

Lamport L. Digitális aláírás létrehozása egyirányú függvényből . - SRI Nemzetközi Számítástechnikai Laboratórium, 1979.
Peikert K. A kriptográfia elméleti alapjai . - Georgia Tech, 2010. Archiválva: 2013. december 19. aWayback Machine
Katz J. Bevezetés a kriptográfiába . — Marylandi Egyetem.
Zaverucha G. Stinson R. Cheriton R. Rövid egyszeri aláírások . – Waterloo Egyetem, 2010.
Garcia L. A Merkle aláírási rendszer biztonságáról és hatékonyságáról . – Darmstadt.

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya