Lamportův podpis

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 31. prosince 2014; kontroly vyžadují 16 úprav .

Lamportův podpis je digitální podpisový kryptosystém s veřejným klíčem. Může být postaven na libovolné jednosměrné funkci . Byl navržen v roce 1979 a pojmenován po svém autorovi, americkém vědci, Leslie Lamportovi [1] .

Popis

Ať má Alice 256bitovou kryptografickou hashovací funkci a kryptograficky silný generátor pseudonáhodných čísel . Chce vytvořit a používat Lamportův pár klíčů, soukromý klíč a jeho odpovídající veřejný klíč .

Vytvoření páru klíčů

K vygenerování tajného klíče používá Alice generátor náhodných čísel, který vygeneruje 256 párů náhodných čísel (celkem 2x256 čísel). Každé číslo se skládá z 256 bitů, takže celková velikost je 2x256x256 bitů = 16 KiB . Tato čísla budou Aliciným tajným klíčem a bude je uchovávat na tajném místě pro pozdější použití.

K vytvoření veřejného klíče Alice hashuje každé z 512 čísel soukromého klíče, čímž vytvoří 512 hashů po 256 bitech. Těchto 512 hashů tvoří Alicin veřejný klíč, který zveřejňuje.

Podpis zprávy

Nyní chce Alice zprávu podepsat. Nejprve zahašuje zprávu a získá 256bitový hash. Potom pro každý bit v tomto hashu vezme odpovídající číslo z tajného klíče. Pokud je například první bit v hash zprávy nula, vezme první číslo z prvního tajného páru klíčů. Pokud je první bit roven jedné, použije druhé číslo z prvního páru. A tak dále. Výsledkem je 256 náhodných čísel, jejichž velikost je 256 × 256 bitů = 8 KiB. Tato čísla tvoří podpis, který Alice posílá spolu se zprávou.

Všimněte si, že jakmile Alice použije svůj soukromý klíč, nesmí být už nikdy použit. Zbylých 256 čísel, která v podpisu nepoužila, Alice nesmí nikdy zveřejnit ani použít. Je lepší, aby je smazala, jinak se k nim někdo dostane a vygeneruje s nimi falešný podpis.

Ověření podpisu

Bob chce ověřit podpis, kterým Alice podepsala zprávu. Zprávu také zahashuje a získá 256bitový hash. Potom pro každý bit v tomto hashu vybere číslo z veřejného klíče Alice. Tato čísla jsou vybrána stejným způsobem, jakým Alice zvolila čísla pro svůj podpis. To znamená, že pokud je první bit hash zprávy nula, Bob vybere první číslo z prvního páru ve veřejném klíči. A tak dále.

Bob pak hashuje každé z 256 čísel z Alicina podpisu a získá 256 hashů. Pokud těchto 256 hashů přesně odpovídá 256 hashům, které právě získal z veřejného klíče Alice, Bob věří, že podpis je pravý. Pokud se neshodují, pak je to falešné.

Za zmínku stojí, že než Alice zveřejní podpis ke zprávě, nikdo nezná 2x256 náhodných čísel v tajném klíči. Nikdo tedy nemůže vytvořit správnou sadu 256 čísel k podepsání. Poté, co Alice publikuje podpis, nikdo stále nezná dalších 256 čísel, a tak nemůže vytvořit podpis pro zprávy, které mají jiný hash [2] .

Příklad

Nechte Alice poslat zprávu M = "Lamport" Bobovi, podepsat ji Lamportovým podpisem a použít 8bitovou hashovací funkci. To znamená, že původní zpráva bude převedena na 8bitový hash.

Generování klíčů

Pomocí generátoru náhodných čísel získá Alice osm párů náhodných čísel. Těchto 16 čísel je soukromý klíč Alice.

Soukromý klíč: $(13,$ $134)$ $(128,$ $67)$ $(25,$ $90) (78,$ $156)$ $(89,$ $37)$ $(234,$ $29)$ $(199,$ $74)$ $(12,$ $3)$

Aby Alice získala veřejný klíč, vypočítá hodnotu hash pro každé číslo ze soukromého klíče.

Veřejný klíč:

$(00101010,$ $10010101)$

$(01100111,$ $11010101)$

$(00101110,$ $11110111)$

$(00100101,$ $11011101)$

$(11100001,$ $00011000)$

$(11000110,$ $11001110)$

$(11001101,$ $11001001)$

$(11100011,$ $11111101)$

Alice zveřejní výsledný veřejný klíč veřejnosti.

Podpis zprávy

Alice chce podepsat zprávu M = "Lamport". Za tímto účelem vypočítá hašovací hodnotu této zprávy a přiřadí každý bit haše k jedné z hodnot v párech soukromých klíčů, čímž vytvoří podpis. $H(M)=01011010$

Podpis zprávy "Lamport": $(13,$ $67,$ $25,$ $156,$ $37,$ $234,$ $74,$ $12)$

Ověření podpisu

Bob obdrží podepsanou zprávu „Lamport“ a chce zkontrolovat, zda ji Alice skutečně poslala. K tomu používá veřejný klíč, který Alice zveřejnila. Převádí přijatou zprávu na hash a mapuje každý bit ve výsledném hashe na číslo z páru ve veřejném klíči. Poté zahašuje podpis zprávy a porovná výsledné dvě sady čísel. Pokud jsou si rovni, pak je podpis skutečný a zprávy skutečně odeslala Alice.

Sada čísel získaných z veřejného klíče:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Hash podpisu:

$00101010,$

$11010101,$

$00101110,$

$11011101,$

$00011000,$

$11000110,$

$11001001,$

$11100011$

Protože jsou tyto sady stejné, podpis je skutečný.

Matematický popis

Klíče

Nechť je kladné číslo, nechť je množina zpráv a nechť je jednosměrná funkce . $k$ $P=\{0,1\}^k$ $f:\,Y\šipka doprava Z$

Pro každé a strana podepisující zprávu náhodně vybere a vypočítá . $1\leq i\leq k$ $j\in\{0,1\}$ $y_{i,j}\v Y$ $z_{i,j}=f(y_{i,j})$

Tajný klíč se skládá z . Veřejný klíč se skládá z hodnot . [3] $K$ $2k$ $y_{i,j}$ $2k$ $z_{i,j}$

Podpis zprávy

Ať je to zpráva. $m = m_1\ldots m_k \in\{0,1\}^k$

Podpis zprávy je . $sign(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k)$

Ověření podpisu

Strana ověřující podpis ověřuje pro všechny . $f(s_i) = z_{i,m_i}$ $1\leq i\leq k$

K padělání podpisu zprávy by kryptoanalytik musel invertovat jednosměrnou funkci , což je považováno za výpočetně nemožné. $F$

Zabezpečení

Kryptografická síla podpisů Lamport je založena na kryptografické síle hashovací funkce .

Pro každou hashovací funkci, která generuje n-bitový výtah, ideální odolnost proti obnově předobrazu a obnově druhé předobrazy předpokládá 2 n operací a 2 n bitů paměti v klasickém výpočetním modelu pro každé provedení hašovací funkce . Pomocí Groverova algoritmu je obnovení ideální hašovací funkce před obrazem omezeno operacemi O(2 n / 2 ) v kvantovém výpočetním modelu [4] .

Více podpisů zpráv

Jediným soukromým klíčem Lamport lze podepsat pouze jednu zprávu. To znamená, že pokud je podepsán určitý počet zpráv, musí být zveřejněn stejný počet veřejných klíčů. Pokud však použijete strom Merkle složený z veřejných klíčů, pak namísto publikování všech veřejných klíčů můžete publikovat pouze horní část stromu. To zvětšuje velikost podpisu, protože část hash stromu musí být zahrnuta do podpisu, ale umožňuje to použít jeden hash k ověření více podpisů. Podle tohoto schématu můžete podepisovat zprávy, kde je hloubka stromu Merkle. Tzn., že teoreticky můžeme jeden veřejný klíč použít pro libovolný počet zpráv [5] . $N=2^n$ $n$

Generování klíčů

Nejprve musíte vygenerovat soukromé jednorázové klíče společnosti Lamport a veřejné jednorázové klíče společnosti Lamport . Dále, pro každý veřejný klíč , kde se vypočítá jeho hash . A na základě těchto hodnot je postaven Merkle strom . $2^{n}$ $X_{i}$ $Y_{i}$ $Y_{i}$ $1 \leq i \leq 2^n$ $h_{i}=H(Y_{i})$ $Ahoj}$

Uzly stromu očíslujeme tak, že index značí vzdálenost od tohoto uzlu k elementu listu a index označí pořadové číslo uzlu zleva doprava na stejné úrovni . $a_{i,j}$ $i$ $j$ $i$

V našem stromu jsou hodnoty hash listové prvky, tedy . Každý nelistový uzel stromu je hash hodnotou ze spojení dvou potomků, tj. , a tak dále. $Ahoj}$ $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})$

Máme tedy strom, jehož kořenovým prvkem je náš veřejný klíč . $hospoda$

Podepisování a ověřování zpráv

Chcete-li podepsat zprávu podle našeho schématu, musíte ji nejprve podepsat jednorázovým podpisem Lamport . To se provádí pomocí jednoho z párů veřejného/soukromého klíče . $sig'$ $(X_i, Y_i,)$

$a_{0,i}=H(X_i)$ je listový prvek stromu odpovídající veřejnému klíči . Cesta od prvku list stromu k jeho vrcholu se skládá z prvků , kde je prvek list a je vrchol stromu. K výpočtu této cesty potřebujeme všechny potomky uzlů . Víme, že uzel je potomkem uzlu . K výpočtu dalšího uzlu na cestě k vrcholu potřebujeme oba potomky node . Proto potřebujeme znát „bratra“ uzlu . Zavolejme mu . Takže, . Proto potřebujeme uzly pro výpočet vrcholu stromu. Vypočítáme je a uložíme. $X_{i}$ $a_{0,i}$ $A_0, ... A_n$ $A_0=a_{0,i}$ $A_n=a_{n,0}=hospoda$ $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}$

Tyto uzly spolu s jednorázovým podpisem zprávy tvoří konečný podpis . $sig'$ $M$ $sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})$

Příjemce zprávy má k dispozici veřejný klíč , zprávu a podpis . Nejprve zkontroluje jednorázový podpis zprávy . Pokud je pravý, příjemce vypočítá . A pak pro výpočty . Pokud se rovná , pak je podpis považován za autentický. $hospoda$ $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}$ $hospoda$

Různé optimalizace a implementace

Krátký tajný klíč

Namísto generování a ukládání všech náhodných čísel tajného klíče lze uložit jediné číslo příslušné velikosti. Obvykle se velikost volí tak, aby byla stejná jako velikost jednoho náhodného čísla v soukromém klíči. Tento klíč lze použít jako základ pro generátor náhodných čísel (CSPRNG), aby bylo možné v případě potřeby znovu vytvořit celou sekvenci tajných klíčů náhodných čísel.

Stejným způsobem lze klíč použít ve spojení s CSPRNG ke generování více klíčů Lamport. Preferovány jsou CSPRNG, které mají vysokou kryptografickou sílu, jako je BBS .

Krátký veřejný klíč

Lamportův podpis lze použít spolu se seznamem hashů, což umožňuje zahrnout pouze jeden hash do veřejného klíče. Tedy místo hodnot - . Aby bylo možné porovnat náhodná čísla v podpisu s hashem ve veřejném klíči, musí být v podpisu zahrnuty všechny hashe, které nejsou použity ve veřejném klíči, tedy hodnoty pro any . V důsledku toho se veřejný klíč výrazně zkrátí a velikost podpisu se přibližně zdvojnásobí. $2k$ $z_{{ij}}$ $(z_{ij})$ $j\neq m_i$

Hash zprávy

Schéma digitálního podpisu společnosti Lamport nevyžaduje, aby byla zpráva m před podpisem hašována. Hašování lze použít například pro podepisování dlouhých zpráv, kde se bude podepisovat hash zprávy, nikoli zpráva samotná [6] .

Srovnání s jinými kryptosystémy

Hlavní výhody schématu jednorázového podpisu společnosti Lamport spočívají v tom, že může být postaveno na jakékoli jednosměrné funkci a že jeho algoritmus podpisu a ověření zprávy je výrazně rychlejší než algoritmy opakovaně použitelných podpisových systémů. Současně má schéma řadu nevýhod. Za prvé, nevýhodou je jednorázovost klíčů. To znamená, že při podepisování každé nové zprávy musíte vygenerovat nový pár, což vede ke komplikacím systému. Za druhé má schéma nevýhodu velké velikosti podpisu a páru veřejného a soukromého klíče [7] .

Tento systém má potenciál ve světle skutečnosti, že potenciální vývoj kvantového počítače ohrožuje bezpečnost mnoha široce používaných algoritmů, jako je RSA , přičemž Lamportova signatura zůstane i v tomto případě bezpečná [8] . Spolu s Merkle stromy lze kryptosystém Lamport použít k ověření více zpráv, což funguje jako poměrně efektivní schéma digitálního podpisu [9] .

Poznámky

↑ Lamport, 1979 , s. 2.
↑ Lamport, 1979 , s. 3-5.
↑ Katz , str. 2.
↑ Schémata M. I. Anokhina, N. P. Varnovského, V. M. Sidelnikova, V. V. Jaščenka, Lamporta a Naor-Junga . Datum přístupu: 17. prosince 2013. Archivováno z originálu 17. prosince 2013. (neurčitý)
↑ Michael Szydlo, EFEKTIVNÍ VYUŽITÍ STROMŮ MERKLE . Získáno 24. listopadu 2013. Archivováno z originálu 17. dubna 2017. (neurčitý)
↑ Lamport, 1979 , s. 6.
↑ Zaverucha, 2010 , str. jeden.
↑ Garcia , str. deset.
↑ Vadim Malykh, „Dlouhodobé uchovávání elektronických dokumentů“ . Datum přístupu: 13. prosince 2013. Archivováno z originálu 13. prosince 2013. (neurčitý)

Literatura

Lamport L. Vytváření digitálních podpisů z jednosměrné funkce . - SRI International Computer Science Laboratory, 1979.
Peikert K. Teoretické základy kryptografie . - Georgia Tech, 2010. Archivováno19. prosince 2013 naWayback Machine
Katz J. Úvod do kryptografie . — University of Maryland.
Zaverucha G. Stinson R. Cheriton R. Krátké jednorázové podpisy . — University of Waterloo, 2010.
Garcia L. O bezpečnosti a účinnosti podpisového schématu Merkle . — Darmstadt.

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta