Schnorrův podpis - Schnorr signature

v kryptografie, a Schnorrův podpis je digitální podpis produkoval Algoritmus podpisu Schnorr který popsal Claus Schnorr. Jedná se o schéma digitálního podpisu známé svou jednoduchostí,^[1] mezi prvními, jejichž bezpečnost je založena na neřešitelnosti určitých diskrétní logaritmus problémy.^[1] Je efektivní a generuje krátké podpisy.^[1] Bylo to pokryto US patent 4 995 082 jehož platnost vypršela v únoru 2008.

Algoritmus

Volba parametrů

Všichni uživatelé podpisového schématu souhlasí s a skupina, ${ displaystyle G}$ , hlavního řádu, ${ displaystyle q}$ , s generátorem, ${ displaystyle g}$ , ve kterém diskrétní log problém se považuje za těžký. Typicky a Skupina Schnorr se používá.
Všichni uživatelé souhlasí s a kryptografická hashovací funkce ${ displaystyle H: {0,1 } ^ {*} rightarrow mathbb {Z} _ {q}}$ .

Zápis

V následujícím,

Exponentiace znamená opakovanou aplikaci skupinové operace
Juxtaposition znamená multiplikaci na množině tříd shody nebo aplikaci skupinové operace (podle potřeby)
Odčítání znamená odčítání na množině skupin ekvivalence
${ displaystyle M in {0,1 } ^ {*}}$ , sada konečných bitových řetězců
${ displaystyle s, e, e_ {v} in mathbb {Z} _ {q}}$ , sada tříd kongruence modulo ${ displaystyle q}$
${ displaystyle x, k in mathbb {Z} _ {q} ^ { times}}$ , multiplikativní skupina celých čísel modulo ${ displaystyle q}$ (pro hlavní ${ displaystyle q}$ , ${ displaystyle mathbb {Z} _ {q} ^ { times} = mathbb {Z} _ {q} setminus { overline {0}} _ {q}}$ )
${ displaystyle y, r, r_ {v} v G}$ .

Generování klíčů

Vyberte soukromý podpisový klíč, ${ displaystyle x}$ , z povolené sady.
Veřejný ověřovací klíč je ${ displaystyle y = g ^ {x}}$ .

Podepisování

Chcete-li podepsat zprávu, ${ displaystyle M}$ :

Vyberte si náhodný ${ displaystyle k}$ z povolené sady.
Nechat ${ displaystyle r = g ^ {k}}$ .
Nechat ${ displaystyle e = H (r paralelní M)}$ , kde ${ displaystyle paralelní}$ označuje zřetězení a ${ displaystyle r}$ je reprezentován jako bitový řetězec.
Nechat ${ displaystyle s = k-xe}$ .

Podpis je dvojice, ${ displaystyle (s, e)}$ .

Všimněte si, že ${ displaystyle s, e in mathbb {Z} _ {q}}$ ; -li ${ displaystyle q <2 ^ {160}}$ , pak se podpisová reprezentace vejde do 40 bajtů.

Ověření

Nechat ${ displaystyle r_ {v} = g ^ {s} y ^ {e}}$
Nechat ${ displaystyle e_ {v} = H (r_ {v} paralelní M)}$

Li ${ displaystyle e_ {v} = e}$ pak je podpis ověřen.

Důkaz správnosti

Je to relativně snadné vidět ${ displaystyle e_ {v} = e}$ pokud se podepsaná zpráva rovná ověřené zprávě:

${ displaystyle r_ {v} = g ^ {s} y ^ {e} = g ^ {k-xe} g ^ {xe} = g ^ {k} = r}$ , a tedy ${ displaystyle e_ {v} = H (r_ {v} paralelní M) = H (r paralelní M) = e}$ .

Veřejné prvky: ${ displaystyle G}$ , ${ displaystyle g}$ , ${ displaystyle q}$ , ${ displaystyle y}$ , ${ displaystyle s}$ , ${ displaystyle e}$ , ${ displaystyle r}$ . Soukromé prvky: ${ displaystyle k}$ , ${ displaystyle x}$ .

To ukazuje pouze to, že správně podepsaná zpráva bude správně ověřena; pro zabezpečený podpisový algoritmus je vyžadováno mnoho dalších vlastností.

Únik klíče z opakovaného použití

Stejně jako u úzce souvisejících podpisových algoritmů DSA, ECDSA, a ElGamal, opětovné použití tajné nonce hodnoty ${ displaystyle k}$ na dvou Schnorrových podpisech různých zpráv umožní pozorovatelům obnovit soukromý klíč.^[2] V případě Schnorrových podpisů to jednoduše vyžaduje odečtení ${ displaystyle s}$ hodnoty:

{ displaystyle s'-s = (k'-k) -x (e'-e)}

.

Li ${ displaystyle k '= k}$ ale ${ displaystyle e ' neq e}$ pak ${ displaystyle x}$ lze jednoduše izolovat. Ve skutečnosti dokonce i mírné odchylky v hodnotě ${ displaystyle k}$ nebo částečný únik ${ displaystyle k}$ může odhalit soukromý klíč po shromáždění dostatečně mnoha podpisů a vyřešení problém se skrytým číslem.^[2]

Bezpečnostní argument

Podpisové schéma bylo vytvořeno použitím Transformace Fiat – Shamir^[3] podle Schnorrova identifikačního protokolu.^[4] Proto (podle argumentů Fiat a Shamir) je bezpečné, pokud ${ displaystyle H}$ je modelován jako a náhodný věštec.

O jeho bezpečnosti lze hovořit také v obecný model skupiny, za předpokladu, že ${ displaystyle H}$ je „odolný před náhodným předponou preimage“ a „odolný před náhodným předponou druhý preimage“.^[5] Zejména, ${ displaystyle H}$ dělá ne potřebuje být odolný proti kolizi.

V roce 2012 Seurin^[1] poskytl přesný důkaz schématu podpisu Schnorra. Seurin zejména ukazuje, že bezpečnostní důkaz pomocí rozvětvení lemma je nejlepším možným výsledkem jakýchkoli jednosměrných podpisových schémat skupinové homomorfismy včetně podpisů typu Schnorr a Podpisová schémata Guillou – Quisquater. Konkrétně, za předpokladu ROMDL, jakákoli algebraická redukce musí ztratit faktor ${ displaystyle f ({ epsilon} _ {F}) q_ {h}}$ v poměru času k úspěchu, kde ${ displaystyle f leq 1}$ je funkce, která zůstane blízko 1, pokud ${ displaystyle { epsilon} _ {F}}$ je znatelně menší než 1 ", kde ${ displaystyle { epsilon} _ {F}}$ je pravděpodobnost padělání chyby ${ displaystyle q_ {h}}$ dotazy náhodnému věštci.

Krátké podpisy Schnorra

Výše uvedený proces dosahuje a t-bitová úroveň zabezpečení s 4t-bitové podpisy. Například 128bitová úroveň zabezpečení by vyžadovala 512bitové (64bajtové) podpisy. Zabezpečení je omezeno diskrétními logaritmickými útoky na skupinu, které jsou složité odmocnina velikosti skupiny.

V původním dokumentu Schnorr z roku 1991 bylo navrženo, že jelikož není vyžadována odolnost proti kolizi v hash, mohou být tedy stejně bezpečné i kratší hash funkce, a skutečně nedávný vývoj naznačuje, že t-bitovou úroveň zabezpečení lze dosáhnout pomocí 3t-bitové podpisy.^[5] 128bitová úroveň zabezpečení by pak vyžadovala pouze 384bitové (48bajtové) podpisy, čehož lze dosáhnout zkrácením velikosti E až do poloviny délky s bitfield.

Viz také

Poznámky

^ ^A ^b ^C ^d Seurin, Yannick (2012-01-12). „Přesné zabezpečení podpisů typu Schnorr v náhodném modelu Oracle“ (PDF). Archiv kryptologie ePrint. Mezinárodní asociace pro kryptologický výzkum. Citováno 2014-08-11.
^ ^A ^b https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf
^ Fiat; Shamir (1986). „Jak se prokázat: praktická řešení problémů s identifikací a podpisem“ (PDF). Sborník CRYPTO '86. Přednášky z informatiky. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0. S2CID 4838652.
^ Schnorr (1989). „Efektivní identifikace a podpisy pro čipové karty“ (PDF). Sborník CRYPTO '89. Přednášky z informatiky. 435: 239–252. doi:10.1007/0-387-34805-0_22. ISBN 978-0-387-97317-3. S2CID 5526090.
^ ^A ^b Neven, chytrý, Warinschi. "Požadavky na hashovací funkci pro podpisy Schnorr". IBM Research. Citováno 19. července 2012.CS1 maint: více jmen: seznam autorů (odkaz)

Reference

Menezes, Alfred J. a kol. (1996), Příručka aplikované kryptografie, CRC Stiskněte.
C.P. Schnorr (1990), „Efektivní identifikace a podpisy pro čipové karty“, G. Brassard, ed. Pokroky v kryptologii - kryptoměna '89, 239-252, Springer-Verlag. Přednášky z informatiky, č. 435
Claus-Peter Schnorr (1991), „Efektivní generování podpisu pomocí čipových karet“, Journal of Cryptology 4(3), 161–174 (PS) (PDF).

externí odkazy

RFC 8235

[:0-1] A ^b ^C ^d Seurin, Yannick (2012-01-12). „Přesné zabezpečení podpisů typu Schnorr v náhodném modelu Oracle“ (PDF). Archiv kryptologie ePrint. Mezinárodní asociace pro kryptologický výzkum. Citováno 2014-08-11.

[tibouchi-2] A ^b https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf

[3] Fiat; Shamir (1986). „Jak se prokázat: praktická řešení problémů s identifikací a podpisem“ (PDF). Sborník CRYPTO '86. Přednášky z informatiky. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0. S2CID 4838652.

[4] Schnorr (1989). „Efektivní identifikace a podpisy pro čipové karty“ (PDF). Sborník CRYPTO '89. Přednášky z informatiky. 435: 239–252. doi:10.1007/0-387-34805-0_22. ISBN 978-0-387-97317-3. S2CID 5526090.

[neven-5] A ^b Neven, chytrý, Warinschi. "Požadavky na hashovací funkci pro podpisy Schnorr". IBM Research. Citováno 19. července 2012.CS1 maint: více jmen: seznam autorů (odkaz)

[1]

[2]

[3]

[4]

[5]