Prstenový podpis

Ring signature ( anglicky  ring signature ) - možnost implementace elektronického podpisu , u kterého je známo, že zprávu podepsal některý z členů seznamu potenciálních podepisujících, ale není to zveřejněno kým. Podepisující samostatně tvoří seznam libovolného počtu různých osob, včetně sebe. K uplatnění podpisu nepotřebuje podepisující svolení, asistenci či asistenci osob zařazených do seznamu – jsou použity pouze veřejné klíče všech členů seznamu a soukromý klíč pouze samotného podepisujícího.

Matematický algoritmus prstenového podpisu vyvinuli Ronald Rivest , Adi Shamir a Yael Tauman a představili  jej v roce 2001 na mezinárodní konferenci Asiacrypt [1] . Podle autorů se v názvu snažili zdůraznit absenci centrální nebo koordinační struktury při vytváření takového podpisu: "...prsteny jsou geometrické obrazce s jednotným okrajem a bez středu."

Historie

Myšlenka skupinového podpisu pod peticemi nebo stížnostmi, který potvrzuje, že všichni signatáři výzvu podporují, ale neumožňuje identifikovat jejího autora nebo iniciátora, pochází z minulosti. Anglický výraz „ round-robin “ je tedy znám již od 17. století a označuje petici, která byla podepsána v kruhu bez respektování hierarchie, aby se vyhnul trestu pro signatáře jako první [2] - jakási vzájemná záruka . V roce 1898, po obléhání města Santiago de Cuba během španělsko-americké války, vysocí důstojníci 5. armádního sboru podepsali v kruhu dopis adresovaný armádnímu velitelství ve Washingtonu , v němž požadovali, aby byl sbor navrácen Spojeným státům . státy pro léčbu a odpočinek. Dopis se dostal do tisku a stal se široce známým a také způsobil ohlas ve vládě prezidenta McKinleyho [3] .

Vícenásobný podpis se stal elektronickou obdobou papírového podpisu v kruhu. V roce 1991 David Chaum a Eugene Van Heyst navrhli schéma skupinového  podpisu [1] , kde podepisovatel je jedním z členů skupiny tvořené administrátorem . Ověřovatel může ověřit, že podepisující osoba je členem skupiny, ale nemůže zjistit kdo. V tomto případě má administrátor možnost identifikovat podepisujícího [4] .  

Kruhové podpisy jsou v podstatě podobné skupinovým podpisům, ale na rozdíl od těch druhých neexistuje žádný způsob, jak identifikovat podepisujícího, neexistuje žádný administrátor ani koordinátor. Všichni členové seznamu, s výjimkou samotného podepisujícího, nemusí znát obsah zprávy nebo dokonce skutečnost, že jejich veřejný klíč byl někým použit k vytvoření kruhového podpisu [1] .

Obecný popis mechanismu pro vytváření a ověřování vyzváněcího podpisu

Předpokládá se, že existuje určitý seznam, který naznačuje jednoznačný vztah osoby k jejímu veřejnému (veřejnému) klíči (například server kryptografických klíčů ). Na důvodu výskytu veřejného klíče v tomto seznamu nezáleží. Osoba si například mohla vytvořit klíče RSA pouze pro internetové nákupy a nemusí si být vůbec vědoma toho, že její veřejné klíče někdo používá k vytvoření vyzváněcího podpisu na zprávě, kterou nikdy neviděl a nechtěl ji podepsat [1] . Obecný algoritmus kruhového podpisu umožňuje současné použití veřejných klíčů generovaných různými systémy (algoritmy), včetně těch s různou velikostí klíčů i podpisů [1] .

Při vytváření vyzváněcího podpisu pro zprávu m si podepisující podle vlastního uvážení vytvoří seznam veřejných klíčů ( P 1 , P 2 , …, P n ), do kterého uvede i své číslo i (jeho pořadové číslo v na seznamu nezáleží). To vše, spolu s tajným klíčem podepisujícího Si , je přivedeno jako parametry na vstup funkce překrytí podpisu ( m , Si , P1 , … , Pn ), přičemž na výstupu se získá výsledek σ . Každý veřejný klíč ze seznamu má sice svůj jedinečný soukromý klíč a je použit pouze jeden z nich (patřící podepisujícímu), ale z výsledného podpisu nelze poznat, který ze soukromých klíčů byl použit k jeho vytvoření. I při neomezeném počtu prstenových podpisů provedených stejným signatářem neexistuje způsob, jak jej identifikovat nebo alespoň s jistotou prokázat, že některé podpisy byly použity pomocí stejného soukromého klíče [1] .

Pravost prstenového podpisu lze ověřit pomocí σ , ma pouze veřejných klíčů P 1 , …, P n [5] .

Možnosti implementace

Rivest, Shamir a Tauman ve svém článku popsali podpis prstenu jako způsob úniku tajných informací, aniž by ztratili svou důvěryhodnost. Například prstenový podpis „vysokého úředníka Bílého domu “ neprozradí jeho identitu, ale zaručí, že zprávu podepsal někdo z uvedeného seznamu úředníků, čímž se potvrdí úroveň kompetence. Seznam osob pro prstenový podpis lze přitom snadno sestavit převzetím veřejných klíčů z otevřených zdrojů [1] .

Další aplikace, kterou také popsali autoři nápadu, je pro vytváření nejednoznačných (kontroverzních) podpisů . V nejjednodušším případě je pro toto použití vyzváněcí podpis tvořen na základě klíčů odesílatele a příjemce zprávy. Pak je podpis pro příjemce významný, má jistotu, že odesílatel zprávu vytvořil. Pro člověka zvenčí však takový podpis ztrácí na důvěryhodnosti a jednoznačnosti – nebude jistota, kdo přesně zprávu vytvořil a podepsal, protože to může být sám příjemce. Takový podpis nelze například u soudu použít k identifikaci odesílatele [1] .

Později se objevily práce, ve kterých byly navrženy nové oblasti aplikace prstencových podpisů a alternativní algoritmy pro jejich tvorbu [6] [7] .

Podpisy prahových prstenů

Na rozdíl od standardního prahového podpisu „t-out-of-n“ , kde t z n uživatelů musí spolupracovat na dešifrování zprávy, tato varianta kruhového podpisu vyžaduje , aby na procesu podepisování spolupracovalo t uživatelů. K tomu musí t účastníků ( i 1 , i 2 , …, i t ) vypočítat podpis σ pro zprávu m zadáním t soukromých a n veřejných klíčů na vstup ( m , S i 1 , S i 2 , … , Si t , P 1 , …, P n ) [8 ] .

Propojitelné prstenové podpisy

Vlastnost konektivity umožňuje určit, zda byly nějaké dva vyzváněcí podpisy vytvořeny stejnou osobou (zda byl použit stejný soukromý klíč), ale bez určení kdo. Jednou z možných aplikací by mohl být offline systém elektronických peněz [9] .

Sledovatelný prstenový podpis

Kromě přidruženého podpisu může být při opětovném použití odhalen veřejný klíč podepisujícího. Takový protokol umožňuje implementaci tajných elektronických hlasovacích systémů , které umožňují anonymní pouze jeden podpis, ale odhalí účastníka, který hlasoval dvakrát [10] .

Kryptoměny

Systém CryptoNote umožňuje vyzváněcí podpisy [11] . To bylo poprvé použito v červenci 2012 v kryptoměně Bytecoin [12] [13] (neplést s bitcoinem ).

Kryptoměna ShadowCash používá k anonymizaci odesílatele transakce sledovatelný kruhový podpis [14] . Počáteční implementace však byla chybná, což vedlo k částečné deanonymizaci ShadowCash od první implementace až do února 2016 [15] .

Účinnost

Většina navržených algoritmů má asymptotickou výslednou velikost , tj. velikost výsledného podpisu je přímo úměrná počtu použitých veřejných klíčů. Každý použitý veřejný klíč při ukládání nebo ověřování vyzváněcího podpisu vyžaduje pevné množství výpočtů, což je mnohem lepší než analogy dostupné v době vytvoření protokolu [1] . Technologie CryptoNote například implementuje vyzváněcí podpisy v platbách p2p , aby byla zajištěna anonymita odesílatele [10] .

V poslední době se objevily efektivnější algoritmy. Existují schémata se sublineární velikostí signatury [16] , stejně jako s konstantní velikostí [17] .

Algoritmus

Podstata algoritmu prstencového podpisu navrženého Rivestem, Shamirem a Taumanem je následující [1] (viz diagram).

Vyzváněcí podpis pro některé zprávy bude vygenerován na základě seznamu veřejných klíčů (v diagramu označených jako ), mezi nimiž má klíč podepisujícího sériové číslo . Veřejné klíče umožňují šifrovat libovolné informace (informační blok , zašifrovaný klíčem , je v diagramu označen jako ). " Informační bloky " dále nejsou součástí ani výsledkem zpracování podepsané zprávy a nemají samostatný význam, jsou generovány náhodnými daty, které se stávají součástí podpisu.

Existuje kombinační funkce libovolného počtu argumentů , jejichž hodnotou a hodnotami všech argumentů, kromě jednoho, lze jednoznačně obnovit jeden chybějící argument. Příkladem takové funkce je sekvenční sčítání: pokud jsou známy celkový součet a všechny členy kromě jednoho, pak lze chybějící člen vypočítat (snížením celkového součtu o hodnotu všech známých členů).

Jako kombinační funkci navrhli autoři algoritmu následující posloupnost akcí: je přijata určitá počáteční hodnota (uvedena v diagramu , je generována náhodně), nad kterou a prvním argumentem je provedeno bitové exkluzivní „nebo“ ( označeno v diagramu symbolem ). Poté je na výsledek aplikována určitá reverzibilní transformace (označená v diagramu jako ), jedna ku jedné spojené s hashovacím součtem podepisované zprávy. Výsledek je bitově XORed s druhým argumentem, převod se použije znovu a tak dále. Jako argumenty se používají odpovídající informační bloky zašifrované veřejnými klíči .

Vybraná náhodná hodnota je jak počáteční, tak i cílová (konečná) hodnota kombinační funkce: výsledek všech transformací musí „objíždět kruh“ a musí se rovnat počáteční hodnotě. Informační bloky pro každý z klíčů, kromě bloku odpovídajícímu vlastnímu klíči podepisujícího, jsou uvedeny jako náhodné hodnoty. Podepisující osoba zašifruje informační bloky odpovídajícími veřejnými klíči. Signatář má nyní cílovou hodnotu kombinační funkce a všechny argumenty kromě jednoho, který odpovídá jeho vlastnímu klíči. Díky vlastnostem kombinační funkce může podepisující zjistit chybějící argument a pomocí vlastního soukromého klíče ( ) tento argument „dešifrovat“ ( ), čímž získá chybějící informační blok .

Součásti hotového prstenového podpisu [1] :

K ověření podpisu potřebujete [1] :

Příklad implementace

Jako příklad je uvedena implementace základního algoritmu pomocí RSA klíčů v Pythonu .

import os import hashlib import náhodný import Crypto.PublicKey.RSA class Ring : def __init__ ( self , k , L = 1024 ): self . k = k sebe . l = L sebe . n = len ( k ) self . q = 1 << ( L - 1 ) def znak ( self , m , z ): self . permut ( m ) s = [ žádné ] * vlastní . u = náhodný . _ randint ( 0 , self . q ) c = v = self . E ( u ) pro i v ( rozsah ( z + 1 , vlastní . n ) + rozsah ( z )): s [ i ] = náhodný . randint ( 0 , self . q ) e = self . g ( s [ i ], self . k [ i ] . e , self . k [ i ] . n ) v = self . E ( v ^ e ) if ( i + 1 ) % self . n == 0 : c = v s [ z ] = vlastní . g ( v ^ u , self . k [ z ] . d , self . k [ z ] . n ) return [ c ] + s def ověřit ( self , m , X ): self . permut ( m ) def _f ( i ): návrat self . g ( X [ i + 1 ], self . k [ i ] . e , self . k [ i ] . n ) y = mapa ( _f , rozsah ( len ( X ) - 1 )) def _g ( x , i ) : vrátit se . E ( x ^ y [ i ]) r = snížit ( _g , rozsah ( self . n ), X [ 0 ]) vrátit r == X [ 0 ] def permut ( self , m ): self . p = int ( hashlib . sha1 ( ' %s ' % m ) . hexdigest (), 16 ) def E ( self , x ): msg = ' %s%s ' % ( x , self . p ) return int ( hashlib . sha1 ( msg ) . hexdigest (), 16 ) def g ( self , x , e , n ): q , r = divmod ( x , n ) if ( ( q + 1 ) * n ) <= ( ( 1 << self . l ) - 1 ): rslt = q * n + pow ( r , e , n ) else : rslt = x return rslt

Podepsání a ověření 2 zpráv pomocí kruhu 4 uživatelů:

size = 4 msg1 = 'ahoj' msg2 = 'svět!' def _rn ( _ ): return Crypto . Veřejný klíč . R.S.A. _ generovat ( 1024 , os . urandom ) klíč = mapa ( _rn , rozsah ( velikost )) r = Prsten ( klíč ) pro i v rozsahu ( velikost ): s1 = r . znaménko ( msg1 , i ) s2 = r . podepsat ( msg2 , i ) tvrdit r . ověřit ( msg1 , s1 ) a r . ověřit ( msg2 , s2 ) a ne r . ověřit ( msg1 , s2 )

Poznámky

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. Jak prozradit tajemství  // Pokroky v kryptologii - ASIACRYPT 2001 / C. Boyd (ed.). - Berlin, Heidelberg: Springer-Verlag , 2001. - S. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
  2. ↑ I. Yu.Pavlovská . Fonosemantická analýza řeči. - Petrohrad. : Nakladatelství Petrohradské univerzity, 2001. - 290 s.
  3. ↑ Historický slovník španělské americké války / Donald H. Dyal, Brian B. Carpenter a Mark A. Thomas, ed. — Westport, Connecticut: Greenwood Press , 1996.
  4. ↑ B. Schneier . Aplikovaná kryptografie  . - New York: John Wiley & Sons , 1996. - S. 98.
  5. ↑ Debnath A., Singaravelu P., Verma, S. Efektivní schéma prostorové ochrany soukromí pro senzorovou síť // Central European Journal of Engineering . - 2013. - Sv. 3, č. 1. - S. 1-10. - doi : 10.2478/s13531-012-0048-7 .
  6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. Průzkum prstenového podpisu // Hranice elektrického a elektronického inženýrství v Číně. - 2008. - Sv. 3, č. 1. - S. 10-19. - doi : 10.1007/s11460-008-0012-8 .
  7. ↑ Hu Xiong, Zhiguang Qin, Fagen Li. A Taxonomy of Ring Signature Schemes: Theory and Applications // IETE Journal of Research. - 2013. - Sv. 59, č.p. 4. - S. 376-382. - doi : 10.4103/03772063.2013.10876518 .
  8. ↑ Bresson E., Stern J., Szydlo M. Threshold ring signatures and application to ad-hocgroups // Advances in Cryptology: CRYPTO 2002 / Moti Yung. - Berlín, Heidelberg, Ney York, Barcelona, ​​​​Hong Kong, Londýn, Milán, Paříž, Tokio: Springer, 2002. - S. 465-480. - ( Lecture Notes in Computer Science . Vol. 2442). - doi : 10.1007/3-540-45708-9_30 .
  9. ↑ Liu JK, Wong DS Linkable ring signatures: Security models and new schemes // Computational Science and Its Applications - ICCSA 2005. - Berlin; New York: Springer, 2005. Sv. 2. - S. 614-623. - ( Lecture Notes in Computer Science . Vol. 3481). - doi : 10.1007/11424826_65 .
  10. ↑ 1 2 Fujisaki E., Suzuki K. Traceable Ring Signature // Kryptografie veřejného klíče - PKC 2007. - Berlín; Heidelberg; New York: Springer, 2007. - S. 181-200. - ( Lecture Notes in Computer Science . Vol. 4450).
  11. ↑ CryptoNote Philosophy . CryptoNoteTech. Získáno 24. listopadu 2017. Archivováno z originálu dne 24. listopadu 2017.
  12. ↑ CryptoNote Currencies  (anglicky) (2015). Získáno 29. listopadu 2017. Archivováno z originálu 13. července 2017.
  13. ↑ Je CryptoNote zabijákem bitcoinů? (23. června 2014). Získáno 29. listopadu 2017. Archivováno z originálu 1. prosince 2017.
  14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash prostřednictvím sledovatelných prstenových podpisů  (anglicky) (pdf)  (odkaz není k dispozici) . www.shadow.cash (2015). Archivováno z originálu 1. prosince 2017.
  15. ↑ Krypto zábava. Broken Crypto in Shadowcash  (anglicky)  (nedostupný odkaz) (02/13/2016). Získáno 29. listopadu 2017. Archivováno z originálu dne 27. září 2016.
  16. ↑ Fujisaki E. Sublinear size sledovatelné prstenové podpisy bez náhodných věštců // Témata v kryptologii - CT-RSA 2011. - Heidelberg; Dordrecht; Londýn; New York: Springer, 2011. - S. 393-415. - ( Lecture Notes in Computer Science . Vol. 6558).
  17. ↑ Au, Man Ho; Liu JK; Susilo W.; Yuen, Tsz Hong. Propojitelný a odvolatelný-iff-Linked prstenový podpis na základě ID konstantní velikosti // Pokrok v kryptologii - INDOCRYPT 2006. - Heidelberg; Dordrecht; Londýn; New York: Springer, 2006.—S. 364-378. - ( Lecture Notes in Computer Science . Vol. 4329).

Literatura

  Přejděte na položku Wikidata  Slovníky a encyklopedie
 Kryptosystémy s veřejným klíčem
Algoritmy
Faktorizace celých čísel
Diskrétní logaritmus
Kryptografie na mřížkách
jiný
Teorie
Normy
Témata