Ringsignatur

Ringsignatur ( engelsk  ringsignatur ) - ett implementeringsalternativ för en elektronisk signatur , där det är känt att meddelandet undertecknades av en av medlemmarna i listan över potentiella undertecknare, men det avslöjas inte av vem. Undertecknaren bildar självständigt en lista över ett godtyckligt antal olika personer, inklusive sig själv i den. För att applicera en signatur kräver undertecknaren inte tillstånd, hjälp eller hjälp från personerna som ingår i listan - endast de offentliga nycklarna för alla medlemmar i listan och den privata nyckeln för endast undertecknaren själv används.

Den matematiska algoritmen för ringsignaturen utvecklades av Ronald Rivest , Adi Shamir och Yael Tauman , som presenterade  2001 vid den internationella konferensen Asiacrypt [1] . Enligt författarna försökte de i titeln betona frånvaron av en central eller koordinerande struktur i bildandet av en sådan signatur: "... ringarna är geometriska figurer med en enhetlig periferi och utan ett centrum."

Historik

Idén med en gruppsignatur under framställningar eller klagomål, som bekräftar att alla undertecknare stöder överklagandet, men inte tillåter att identifiera dess författare eller initiativtagare, har sitt ursprung i det förflutna. Det engelska uttrycket ” round-robin ” har alltså varit känt sedan 1600-talet och betecknar en petition som undertecknades i en cirkel utan att respektera hierarkin för att undvika straff för undertecknaren först [2] - en sorts ömsesidig garanti . 1898, efter belägringen av staden Santiago de Cuba under det spansk-amerikanska kriget, undertecknade högt uppsatta officerare från 5:e armékåren ett brev i en cirkel till arméns högkvarter i Washington med krav på att kåren skulle återföras till Förenta staterna. stater för behandling och vila. Brevet hamnade i pressen och blev allmänt känt och orsakade också en resonans i president McKinleys regering [3] .

Multipelsignaturen har blivit den elektroniska analogen till papperssignaturen i en cirkel. 1991 föreslog David Chaum och Eugene Van Heyst ett gruppsignaturschema  [1] , där undertecknaren är en av medlemmarna i gruppen som bildas av administratören . Verifieraren kan verifiera att undertecknaren är medlem i gruppen, men kan inte ta reda på vem. I det här fallet har administratören möjlighet att identifiera undertecknaren [4] .  

Ringsignaturer liknar i huvudsak gruppsignaturer, men till skillnad från de senare finns det inget sätt att identifiera undertecknaren, det finns ingen administratör eller samordnare. Alla medlemmar i listan, med undantag av undertecknaren själv, kanske inte känner till innehållet i meddelandet, eller ens det faktum att deras offentliga nyckel användes för att bilda en ringsignatur av någon [1] .

Allmän beskrivning av mekanismen för att skapa och verifiera en ringsignatur

Det antas att det finns en viss lista som anger en persons entydiga relation till sin offentliga (offentliga) nyckel (till exempel en kryptografisk nyckelserver ). Orsaken till att den publika nyckeln visas i den här listan spelar ingen roll. Till exempel kan en person ha skapat RSA- nycklar endast för internetköp och kan vara helt omedveten om att deras publika nycklar används av någon för att skapa en ringsignatur på ett meddelande som de aldrig har sett och inte ville signera [1] . Den allmänna ringsignaturalgoritmen tillåter samtidig användning av publika nycklar som genereras av olika system (algoritmer), inklusive de med olika storlekar på både nycklar och signaturer [1] .

När man skapar en ringsignatur för ett meddelande m , bildar undertecknaren, efter eget gottfinnande, en lista med publika nycklar ( P 1 , P 2 , …, P n ), i vilken han även inkluderar sitt nummer i (dess serienummer i listan spelar ingen roll). Allt detta, tillsammans med den hemliga nyckeln för signeraren Si , matas som parametrar till ingången av signaturöverlagringsfunktionen ( m , Si , P1 , … , Pn ) , vilket ger resultatet σ vid utgången . Även om varje publik nyckel från listan har sin egen unika privata nyckel och endast en av dem (som tillhör undertecknaren) används, är det omöjligt att veta från den resulterande signaturen vilken av de privata nycklarna som användes för att skapa den. Även med ett obegränsat antal ringsignaturer gjorda av samma undertecknare, finns det inget sätt att identifiera honom eller åtminstone att med säkerhet fastställa att vissa signaturer användes med samma privata nyckel [1] .

Äktheten av ringsignaturen kan verifieras med σ , m och endast publika nycklar P 1 , …, P n [5] .

Implementeringsalternativ

I sin artikel beskrev Rivest, Shamir och Tauman ringsignaturen som ett sätt att läcka hemlig information utan att förlora sin trovärdighet. Till exempel kommer ringsignaturen för en "högt uppsatt tjänsteman i Vita huset " inte att avslöja hans identitet, men garanterar att meddelandet undertecknades av någon från den angivna listan över tjänstemän, vilket bekräftar kompetensnivån. Samtidigt kan listan över personer för ringsignaturen enkelt sammanställas genom att ta publika nycklar från öppna källor [1] .

En annan applikation, som också beskrivs av idéförfattarna, är för att skapa tvetydiga (kontroversiella) signaturer . I det enklaste fallet, för denna användning, bildas ringsignaturen baserat på nycklarna för avsändaren och mottagaren av meddelandet. Då är signaturen betydelsefull för mottagaren, han är säker på att avsändaren skapat meddelandet. Men för en utomstående förlorar en sådan signatur trovärdighet och otvetydighet - det kommer inte att finnas någon säkerhet vem som exakt har format och undertecknat meddelandet, eftersom det kan vara mottagaren själv. En sådan signatur kan till exempel inte användas i domstol för att identifiera avsändaren [1] .

Senare dök verk upp där nya tillämpningsområden för ringsignaturer och alternativa algoritmer för deras bildande föreslogs [6] [7] .

Tröskelringsignaturer

Till skillnad från standardtröskelsignaturen "t-ut-av-n" , där t av n användare måste samarbeta för att dekryptera ett meddelande, kräver denna ringsignaturvariant att t användare samarbetar i signeringsprocessen . För att göra detta måste t deltagare ( i 1 , i 2 , …, i t ) beräkna signaturen σ för meddelandet m genom att tillhandahålla t privata och n publika nycklar till ingången ( m , S i 1 , S i 2 , … , S i t , P 1 , …, P n ) [8] .

Länkbara ringsignaturer

Connectivity-egenskapen låter dig avgöra om två ringsignaturer har skapats av samma person (om samma privata nyckel användes), men utan att ange vem. En möjlig tillämpning skulle kunna vara ett offlinesystem för elektroniska pengar [9] .

Spårbar ringsignatur

Förutom den associerade signaturen kan undertecknarens publika nyckel exponeras när den återanvänds. Ett sådant protokoll tillåter implementering av hemliga elektroniska röstningssystem som tillåter endast en signatur att vara anonym, men avslöjar deltagaren som röstade två gånger [10] .

Kryptovalutor

CryptoNote - systemet tillåter ringsignaturer [11] . Detta användes första gången i juli 2012 i kryptovalutan Bytecoin [12] [13] ( inte att förväxla med Bitcoin ).

ShadowCash -kryptovalutan använder en spårbar ringsignatur för att anonymisera avsändaren av en transaktion [14] . Den initiala implementeringen var dock felaktig, vilket ledde till en partiell deanonymisering av ShadowCash från den första implementeringen till februari 2016 [15] .

Effektivitet

De flesta av de föreslagna algoritmerna har en asymptotisk resultatstorlek , dvs storleken på den resulterande signaturen är direkt proportionell mot antalet använda publika nycklar. Varje använd offentlig nyckel när man pålägger eller verifierar en ringsignatur kräver ett fast antal beräkningar, vilket är mycket bättre än analoger tillgängliga vid den tidpunkt då protokollet skapades [1] . Till exempel implementerar CryptoNote- tekniken ringsignaturer i p2p- betalningar för att säkerställa avsändarens anonymitet [10] .

Nyligen har mer effektiva algoritmer dykt upp. Det finns scheman med en sublinjär storlek på signaturen [16] , såväl som med en konstant storlek [17] .

Algoritm

Kärnan i ringsignaturalgoritmen som föreslagits av Rivest, Shamir och Tauman är följande [1] (se diagram).

Ringsignaturen för något meddelande kommer att genereras baserat på listan över publika nycklar (anges i diagrammet som ), bland vilka undertecknarens nyckel har ett serienummer . Med offentliga nycklar kan du kryptera godtycklig information (informationsblocket , krypterat med nyckeln , anges i diagrammet som ). " Informationsblock " härefter är inte en del av eller resultatet av behandlingen av det signerade meddelandet och har ingen oberoende betydelse, de är genererade slumpmässiga data som blir komponenter i signaturen.

Det finns en kombinationsfunktion av ett godtyckligt antal argument , med värdet av vilka och värdena för alla argument, utom ett, kan man unikt återställa ett saknat argument. Ett exempel på en sådan funktion är sekventiell summering: om den totala summan och alla termer utom en är kända, kan den saknade termen beräknas (genom att minska den totala summan med värdet av alla kända termer).

Som en kombinationsfunktion föreslog författarna till algoritmen följande sekvens av åtgärder: ett visst startvärde tas (indikeras i diagrammet , det genereras slumpmässigt), över vilket och det första argumentet ett bitvis exklusivt "eller" utförs ( visas i diagrammet med symbolen ). Sedan tillämpas en viss reversibel transformation på resultatet (indikerat i diagrammet som ), en-till-en förknippad med hashsumman för meddelandet som signeras. Resultatet XORed bitvis med det andra argumentet, konverteringen tillämpas igen, och så vidare. Motsvarande informationsblock krypterade med publika nycklar används som argument .

Det valda slumpmässiga värdet är både start- och målvärdet (slutvärdet) för kombinationsfunktionen: resultatet av alla transformationer måste "gå runt ringen" och bli lika med startvärdet. Informationsblocken för var och en av nycklarna, förutom blocket som motsvarar undertecknarens egen nyckel, ges som slumpmässiga värden. Undertecknaren krypterar informationsblocken med motsvarande publika nycklar. Signeraren har nu målvärdet för kombinationsfunktionen och alla utom ett av argumenten, det som motsvarar dess egen nyckel. Tack vare egenskaperna hos kombinationsfunktionen kan undertecknaren ta reda på det saknade argumentet och, med sin egen privata nyckel ( ), "dekryptera" detta argument ( ), erhålla det saknade informationsblocket .

Komponenter i den färdiga ringsignaturen [1] :

För att verifiera signaturen behöver du [1] :

Implementeringsexempel

Som ett exempel ges en Python- implementering av en grundläggande algoritm som använder RSA- nycklar .

import os import hashlib import slumpmässig import Crypto.PublicKey.RSA klass Ring : def __init__ ( själv , k , L = 1024 ): själv . k = k själv . l = L själv . n = len ( k ) själv . q = 1 << ( L - 1 ) def tecken ( själv , m , z ): själv . permut ( m ) s = [ Ingen ] * själv . u = slumpmässigt . _ randint ( 0 , själv . q ) c = v = själv . E ( u ) för i in ( område ( z + 1 , själv . n ) + område ( z ) ): s [ i ] = slumpmässigt . randint ( 0 , själv . q ) e = själv . g ( s [ i ], själv . k [ i ] . e , själv . k [ i ] . n ) v = själv . E ( v ^ e ) if ( i + 1 ) % själv . n == 0 : c = v s [ z ] = själv . g ( v ^ u , själv . k [ z ] . d , själv . k [ z ] . n ) returnera [ c ] + s def verifiera ( själv , m , X ): själv . permut ( m ) def _f ( i ): returnera själv . g ( X [ i + 1 ], själv . k [ i ] . e , själv . k [ i ] . n ) y = karta ( _f , intervall ( len ( X ) - 1 )) def _g ( x , i ) : returnera själv . E ( x ^ y [ i ]) r = reducera ( _g , range ( self . n ), X [ 0 ]) return r == X [ 0 ] def permut ( själv , m ): själv . 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 ( själv , x , e , n ): q , r = divmod ( x , n ) if (( q + 1 ) * n ) <= (( 1 << själv . l ) - 1 ): rslt = q * n + pow ( r , e , n ) else : rslt = x return rslt

Signera och verifiera 2 meddelanden med en ring för 4 användare:

storlek = 4 msg1 = 'hej' msg2 = 'världen!' def _rn ( _ ): returnera Krypto . PublicKey . R.S.A. _ generera ( 1024 , os . urandom ) nyckel = karta ( _rn , intervall ( storlek )) r = Ring ( nyckel ) för i i intervall ( storlek ): s1 = r . tecken ( msg1 , i ) s2 = r . tecken ( msg2 , i ) hävda r . verifiera ( msg1 , s1 ) och r . verifiera ( msg2 , s2 ) och inte r . verifiera ( msg1 , s2 )

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. Hur man läcker en hemlighet  // Advances in Cryptology - ASIACRYPT 2001 / C. Boyd (red.). - Berlin, Heidelberg: Springer-Verlag , 2001. - P. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
  2. ↑ I. Yu. Pavlovskaya . Fonosemantisk analys av tal. - St Petersburg. : Publishing House of St. Petersburg University, 2001. - 290 sid.
  3. ↑ Historical Dictionary of the Spanish American War / Donald H. Dyal, Brian B. Carpenter och Mark A. Thomas, red. — Westport, Connecticut: Greenwood Press , 1996.
  4. ↑ B. Schneier . Tillämpad kryptografi  . - New York: John Wiley & Sons , 1996. - S. 98.
  5. ↑ Debnath A., Singaravelu P., Verma, S. Effektivt spatial integritetsskyddssystem för sensornätverk // Central European Journal of Engineering . - 2013. - Vol. 3, nr. 1. - S. 1-10. - doi : 10.2478/s13531-012-0048-7 .
  6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. En undersökning av ringsignatur // Frontiers of Electrical and Electronic Engineering i Kina. - 2008. - Vol. 3, nr. 1. - P. 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. - Vol. 59, nr. 4. - s. 376-382. - doi : 10.4103/03772063.2013.10876518 .
  8. ↑ Bresson E., Stern J., Szydlo M. Tröskelringsignaturer och applikationer till ad-hocgroups // Advances in Cryptology: CRYPTO 2002 / Moti Yung. - Berlin, Heidelberg, Ney York, Barcelona, ​​​​Hong Kong, London, Milano, Paris, Tokyo: 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 Länkbara ringsignaturer: Säkerhetsmodeller och nya scheman // Computational Science and its Applications - ICCSA 2005. - Berlin; New York: Springer, 2005. Vol. 2. - P. 614-623. - ( Lecture Notes in Computer Science . Vol. 3481). - doi : 10.1007/11424826_65 .
  10. ↑ 1 2 Fujisaki E., Suzuki K. Spårbar ringsignatur // Public Key Cryptography - PKC 2007. - Berlin; Heidelberg; New York: Springer, 2007. - S. 181-200. - ( Lecture Notes in Computer Science . Vol. 4450).
  11. ↑ CryptoNote Filosofi . CryptoNoteTech. Hämtad 24 november 2017. Arkiverad från originalet 24 november 2017.
  12. ↑ CryptoNote Currencies  (engelska) (2015). Hämtad 29 november 2017. Arkiverad från originalet 13 juli 2017.
  13. ↑ Är CryptoNote en Bitcoin-mördare? (23 juni 2014). Hämtad 29 november 2017. Arkiverad från originalet 1 december 2017.
  14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distribuerad ECash via spårbara ringsignaturer  (engelska) (pdf)  (länk ej tillgänglig) . www.shadow.cash (2015). Arkiverad från originalet den 1 december 2017.
  15. ↑ Kryptokul. Brutna krypto i Shadowcash  (engelska)  (inte tillgänglig länk) (2016-02-13). Hämtad 29 november 2017. Arkiverad från originalet 27 september 2016.
  16. ↑ Fujisaki E. Spårbara ringsignaturer av sublinjär storlek utan slumpmässiga orakel // Ämnen i kryptologi - CT-RSA 2011. - Heidelberg; Dordrecht; London; 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. Konstant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signatur // Progress in Cryptology - INDOCRYPT 2006. - Heidelberg; Dordrecht; London; New York: Springer, 2006.—P. 364-378. - ( Lecture Notes in Computer Science . Vol. 4329).

Litteratur

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk
 Public key kryptosystem
Algoritmer
Faktorisering av heltal
Diskret logaritm
Kryptografi på galler
Övrig
Teori
Standarder
Ämnen