Semnătura Merkle

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 noiembrie 2016; verificările necesită 46 de modificări .

Semnătura Merkle este un algoritm de semnătură digitală post-cuantică și reutilizabil , bazat pe utilizarea unui arbore Merkle și a unui fel de semnătură digitală unică. [unu]

Istorie

Semnătura a fost publicată pentru prima dată de Ralph Merkle în 1979 în articolul său „Secrecy, authentication, and public key systems” [2] ca semnătură digitală reutilizabilă folosind semnătura unică a lui Lamport . [3]

Descrierea algoritmului

Pregătire

Semnătura Merkle se bazează pe o semnătură digitală unică deja existentă, a cărei putere criptografică trebuie să se bazeze pe o funcție hash sigură criptografic . Exemple de astfel de semnături ar fi Schema de semnătură unică Winternitz sau semnătura lui Lamport . [4] O semnătură digitală unică ar trebui să conțină trei operațiuni principale: [5]

Generarea unei chei secrete și a unei chei publice . $X$ $Y$
Generarea unei semnături dintr-un mesaj utilizând o cheie secretă . $b$ $d$ $X$
Verificarea semnăturii cu cheie publică . $b$ $Y$

De asemenea, este necesar să se decidă asupra unei funcții hash rezistente la cripto , care va fi folosită ulterior pentru a calcula cheia publică. [patru] $H:\{0,1\}^{*}\rightarrow \{0,1\}^{s)$

Generare cheie

Sunt generate matrice de chei și lungimi . Lungimea este aleasă să fie o putere de doi, deoarece este necesar să construiți un arbore Merkle. Fiecare pereche este folosită ca o pereche de chei private-publice pentru o semnătură unică de bază. Array - este cheia privată a semnăturii Merkle, un arbore Merkle este construit pentru a genera cheia publică: $X$ $Y$ $N=2^{n}$ $(X_{i}, Y_{i})$ $X$

Pentru fiecare , calculăm valoarea hash - acesta va fi stratul zero al copacului, adică frunzele sale. Să numim acest strat . Totalul conține articole. După aceea, calculăm următorul strat, care are o dimensiune : fiecare --lea element al stratului este calculat prin două elemente din stratul anterior , unde este operația de concatenare. Astfel, fiecare al i- lea strat următor are o lungime și este calculat prin stratul i-lea. Ca rezultat, vom ajunge la ultimul strat al copacului , care are o lungime și este rădăcina copacului. $Y_{i}$ $H(Y_{i})$ $a_{0}$ $a_{0}$ $l_{0}=2^{n)$ $a_{1}$ $l_{1}=2^{n-1}$ $j$ $a_{1}$ $a_{1,j}=H(a_{0,j*2}||a_{0,j*2+1})$ $||$ $i$ $l_{i}=2^{ni)$ $i-1$ $un$ $l_{n}=1$

Rădăcina arborelui Merkle construit este luată ca cheie publică: . [6] $pub\_key=a_{n)$

Generarea semnăturii

Pentru a genera o semnătură din matrice și , este selectată a treia pereche de chei .Se calculează o semnătură digitală unică pentru mesaj folosind cheia privată . Apoi, luați în considerare calea de la rădăcina arborelui Merkle până la frunza corespunzătoare cheii . Să notăm vârfurile prin care trece această cale ca o matrice de lungime , unde este rădăcina arborelui și este . Valoarea fiecărui vârf , cu excepția , este calculată ca , unde și sunt copii imediati ai . Astfel, pentru a calcula calea de la rădăcina arborelui, este suficient să cunoaștem șirul de vârfuri , pe care îl vom numi cale de autentificare. Astfel, semnătura mesajului include: o cheie de verificare , o semnătură unică și o cale de autentificare pentru calcularea căii către rădăcina arborelui. [7] $X$ $Y$ $i$ $(X_{i}, Y_{i})$ $d$ $b_{i}$ $X_{i}$ $a_{0,n)$ $a_{0,i}$ $Y_{i}$ $A$ $n+1$ $Un}$ $A_0$ $a_{0,i}$ $A_{j}$ $A_{0}=H(Y_{i})$ $H(A_{j-1}||auth_{j-1})$ $auth_{j-1}$ $A_{j-1}$ $A_{{j}}$ $Y_{i}$ $auth_{1},auth_{2},...,auth_{n)$ $d$ $Y_{i}$ $b_{i}$

Verificarea semnăturii

În primul rând, destinatarul verifică semnătura unică cu mesajul . Dacă verificarea a avut succes, începe să construiască calea de la rădăcina arborelui. Mai întâi, apoi, și așa mai departe. Dacă , atunci verificarea semnăturii a avut succes. [opt] $b_{i}$ $d$ $H(Y_{i})$ $A_{0}=H(Y_{i})$ $A_{1}=H(A_{0}||auth_{0})$ $A_{n}=pub\_key$

Beneficii

Post-cuantic

Algoritmii de semnătură digitală folosiți în mod obișnuit, cum ar fi RSA și DSA , profită de complexitatea factorizării numerelor și de complexitatea calculării logaritmului discret . Cu toate acestea, folosind algoritmul lui Shor și un computer cuantic , aceste semnături pot fi sparte în timp polinomial. În schimb, semnătura Merkle este post-cuantică, deoarece puterea sa criptografică se bazează pe puterea funcției hash criptografice și pe puterea semnăturii digitale unice. [unu]

Reutilizabilitate

Una dintre principalele probleme ale semnăturilor digitale bazate pe funcții hash puternice este că acestea sunt utilizate de obicei în contextul semnăturilor digitale unice, adică semnături în care o pereche de chei este folosită pentru a semna un singur mesaj. Cu toate acestea, există modalități de a extinde astfel de semnături pentru a fi reutilizabile. O astfel de metodă este de a construi un arbore Merkle, care este folosit pentru a autentifica diferite semnături unice. [9]

Dezavantaje

Problema traversării arborelui

Această problemă este legată de găsirea unui algoritm eficient pentru calcularea datelor de autentificare. Soluția banală - de a păstra toate datele în memorie - necesită prea multă memorie. Pe de altă parte, abordarea calculării căii de autentificare în zona în care este nevoie va fi prea costisitoare pentru unele noduri arbore. [10] Dacă lungimea matricelor X și Y este mai mare de 2^25, utilizarea semnăturii Merkle devine nepractică. [opt]

Criptanaliză

Este dovedit că algoritmul de semnătură digitală Merkle este puternic din punct de vedere criptografic împotriva unui atac de selecție adaptivă a mesajelor dacă folosește o funcție hash care este rezistentă la coliziunile de tip 2 . [11] [12] Cu toate acestea, pentru a sparge semnătura Merkle, criptoanalistul trebuie fie să reconstruiască imaginea prealabilă a funcției hash, fie să calculeze o coliziune de tip I. Aceasta înseamnă că, din punct de vedere practic, puterea criptografică a unei semnături Merkle se bazează pe ireversibilitatea funcției hash utilizate și pe rezistența acesteia la coliziuni de primă clasă. [12]

Note

↑ 12 CMSS , 2006 , p. 349-350.
↑ Merkle, 1979 .
↑ Securitate, 2005 , p. unu.
↑ 12 CMSS , 2006 , p. 352.
↑ CMSS, 2006 , p. 351.
↑ Securitate, 2005 , p. 3.
↑ CMSS, 2006 , p. 352-353.
↑ 12 CMSS , 2006 , p. 353.
↑ dods2005hash, 2005 , p. 96.
↑ szydlo2004merkle, 2004 , p. 541.
↑ Securitate, 2005 , p. patru.
↑ 1 2 rohde2008fast, 2008 , p. 109.

Literatură

Merkle, Ralph Charles. Sisteme de secretizare, autentificare și cheie publică : Raport tehnic nr. 1979-1. - Citeseer, 1979. - doi : 10.1.1.637.3952 .

Garcia, LC Coronado. Despre securitatea și eficiența schemei de semnătură Merkle : Raport tehnic 2005/192. — Cryptology ePrint Archive, 2005.

Buchmann, Johannes. CMSS – o schemă de semnătură Merkle îmbunătățită // Conferința internațională despre criptologie din India. - Springer Berlin Heidelberg, 2006. - S. 349-363 . - doi : 10.1007/11941378_25 . (link indisponibil)

Dods, Chris și Smart, Nigel P și Stam, Martijn. Scheme de semnătură digitală bazate pe hash // IMA International Conference on Criptography and Coding. - Springer Berlin Heidelberg, 2005. - S. 96-115 . - doi : 10.1007/11586821_8 .

Szydlo, Michael. Merkle tree traversal in log space and time // Conferința internațională privind teoria și aplicațiile tehnicilor criptografice. - Springer Berlin Heidelberg, 2004. - S. 541-554 . - doi : 10.1007/978-3-540-24676-3_32 .

Rohde, Sebastian și Eisenbarth, Thomas și Dahmen, Erik și Buchmann, Johannes și Paar, Christof. Semnături rapide bazate pe hash pe dispozitive constrânse // Conferință internațională privind cercetarea cardurilor inteligente și aplicații avansate. - Springer Berlin Heidelberg, 2008. - S. 104-117 . - doi : 10.1007/978-3-540-85893-5_8 .

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ