Ring signatur

Ringsignatur ( engelsk  ringsignatur ) - en implementeringsmulighed for en elektronisk signatur , hvor det er kendt, at meddelelsen blev underskrevet af et af medlemmerne af listen over potentielle underskrivere, men det oplyses ikke af hvem. Underskriveren danner uafhængigt en liste over et vilkårligt antal forskellige personer, inklusive sig selv i den. For at anvende en signatur kræver underskriveren ikke tilladelse, assistance eller assistance fra de personer, der er optaget på listen - kun de offentlige nøgler for alle medlemmer af listen og den private nøgle for kun underskriveren selv, der bruges.

Den matematiske algoritme for ringsignaturen blev udviklet af Ronald Rivest , Adi Shamir og Yael Tauman , der præsenterede  i 2001 på den internationale konference Asiacrypt [1] . Ifølge forfatterne forsøgte de i titlen at understrege fraværet af en central eller koordinerende struktur i dannelsen af ​​en sådan signatur: "... ringene er geometriske figurer med en ensartet periferi og uden et center."

Historie

Ideen om en gruppesignatur under andragender eller klager, der bekræfter, at alle underskrivere støtter appellen, men ikke tillader at identificere dens forfatter eller initiativtager, stammer fra fortiden. Således har det engelske udtryk " round-robin " været kendt siden det 17. århundrede og betegner et andragende, der blev underskrevet i en cirkel uden at respektere hierarkiet for først at undgå straf til underskriveren [2] - en slags gensidig garanti . I 1898, efter belejringen af ​​byen Santiago de Cuba under den spansk-amerikanske krig, underskrev højtstående officerer fra 5. armékorps et brev i en cirkel til hærens hovedkvarter i Washington , hvori de krævede, at korpset skulle returneres til De Forenede Stater . stater for behandling og hvile. Brevet kom i pressen og blev bredt kendt , og det vakte også resonans i præsident McKinleys regering [3] .

Multisignaturen er blevet den elektroniske analog til papirsignaturen i en cirkel. I 1991 foreslog David Chaum og Eugene Van Heyst en gruppesignaturordning [  1] , hvor underskriveren er et af medlemmerne af gruppen dannet af administratoren . Verifikatoren kan verificere, at underskriveren er medlem af gruppen, men kan ikke finde ud af hvem. I dette tilfælde har administratoren mulighed for at identificere underskriveren [4] .  

Ringsignaturer ligner i det væsentlige gruppesignaturer, men i modsætning til sidstnævnte er der ingen måde at identificere underskriveren på, der er ingen administrator eller koordinator. Alle medlemmer af listen, med undtagelse af underskriveren selv, kender muligvis ikke indholdet af meddelelsen, eller endda det faktum, at deres offentlige nøgle blev brugt til at danne en ringesignatur af nogen [1] .

Generel beskrivelse af mekanismen til at oprette og verificere en ringesignatur

Det antages, at der er en bestemt liste, der angiver en persons utvetydige forhold til sin offentlige (offentlige) nøgle (for eksempel en kryptografisk nøgleserver ). Årsagen til forekomsten af ​​den offentlige nøgle på denne liste er ligegyldig. For eksempel kan en person kun have oprettet RSA- nøgler til internetkøb og kan være fuldstændig uvidende om, at deres offentlige nøgler bliver brugt af nogen til at oprette en ringesignatur på en besked, som de aldrig har set og ikke ønskede at underskrive [1] . Den generelle ringsignaturalgoritme tillader samtidig brug af offentlige nøgler genereret af forskellige systemer (algoritmer), inklusive dem med forskellige størrelser af både nøgler og signaturer [1] .

Ved oprettelse af en ringesignatur for en meddelelse m , danner underskriveren efter eget skøn en liste over offentlige nøgler ( P 1 , P 2 , …, P n ), hvori han også inkluderer sit nummer i (dets serienummer i listen er ligegyldig). Alt dette, sammen med den hemmelige nøgle for underskriveren Si , føres som parametre til input af signaturoverlejringsfunktionen ( m , Si , P1 , …, Pn ) , hvilket opnår resultatet σ ved udgangen . Selvom hver offentlige nøgle fra listen har sin egen unikke private nøgle, og kun én af dem (der tilhører underskriveren) bruges, er det umuligt at vide ud fra den resulterende signatur, hvilken af ​​de private nøgler der blev brugt til at oprette den. Selv med et ubegrænset antal ringesignaturer lavet af den samme underskriver, er der ingen måde at identificere ham på eller i det mindste at fastslå med sikkerhed, at nogle signaturer blev anvendt ved hjælp af den samme private nøgle [1] .

Ægtheden af ​​ringesignaturen kan verificeres ved hjælp af σ , m og kun offentlige nøgler P 1 , …, P n [5] .

Implementeringsmuligheder

I deres artikel beskrev Rivest, Shamir og Tauman ringsignaturen som en måde at lække hemmelig information uden at miste dens troværdighed. For eksempel vil ringsignaturen fra en "højtstående embedsmand i Det Hvide Hus " ikke afsløre hans identitet, men garanterer, at beskeden blev underskrevet af en person fra den specificerede liste over embedsmænd, hvilket bekræfter kompetenceniveauet. Samtidig kan listen over personer til ringesignaturen nemt kompileres ved at tage offentlige nøgler fra åbne kilder [1] .

En anden applikation, også beskrevet af forfatterne af ideen, er til at skabe tvetydige (kontroversielle) signaturer . I det enkleste tilfælde, til denne brug, dannes ringesignaturen baseret på nøglerne til afsenderen og modtageren af ​​beskeden. Så har signaturen betydning for modtageren, han er sikker på, at afsenderen har skabt beskeden. Men for en udenforstående mister en sådan signatur troværdighed og utvetydighed – der vil ikke være nogen sikkerhed, hvem der præcist har dannet og underskrevet beskeden, for det kan være modtageren selv. En sådan underskrift kan for eksempel ikke bruges i retten til at identificere afsenderen [1] .

Senere dukkede værker op, hvor nye anvendelsesområder for ringsignaturer og alternative algoritmer til deres dannelse blev foreslået [6] [7] .

Tærskelringsignaturer

I modsætning til standard "t-ud-af-n" -tærskelsignaturen , hvor t ud af n brugere skal samarbejde for at dekryptere en meddelelse, kræver denne ringesignaturvariant, at t brugere samarbejder i underskriftsprocessen. For at gøre dette skal t deltagere ( i 1 , i 2 , …, i t ) beregne signaturen σ for meddelelsen m ved at levere t private og n offentlige nøgler til inputtet ( m , S i 1 , S i 2 , … , S i t , P 1 , …, P n ) [8] .

Ringsignaturer, der kan linkes

Tilslutningsegenskaben giver dig mulighed for at bestemme, om to ringesignaturer blev oprettet af den samme person (om den samme private nøgle blev brugt), men uden at angive hvem. En mulig anvendelse kunne være et offline elektronisk pengesystem [9] .

Sporbar ringsignatur

Ud over den tilknyttede signatur kan underskriverens offentlige nøgle blive afsløret, når den genbruges. En sådan protokol tillader implementering af hemmelige elektroniske afstemningssystemer , der tillader kun én signatur at være anonym, men afslører deltageren, der har stemt to gange [10] .

Kryptovalutaer

CryptoNote - systemet tillader ringesignaturer [11] . Dette blev første gang brugt i juli 2012 i Bytecoin [12] [13] kryptovaluta (ikke at forveksle med Bitcoin ).

ShadowCash cryptocurrency bruger en sporbar ringesignatur til at anonymisere afsenderen af ​​en transaktion [14] . Den indledende implementering var dog fejlbehæftet, hvilket førte til den delvise deanonymisering af ShadowCash fra den første implementering og frem til februar 2016 [15] .

Effektivitet

De fleste af de foreslåede algoritmer har en asymptotisk resultatstørrelse , dvs. størrelsen af ​​den resulterende signatur er direkte proportional med antallet af anvendte offentlige nøgler. Hver brugt offentlig nøgle, når der pålægges eller verificeres en ringesignatur, kræver en fast mængde beregninger, hvilket er meget bedre end analoge tilgængelige på det tidspunkt, hvor protokollen blev oprettet [1] . For eksempel implementerer CryptoNote- teknologien ringesignaturer i p2p -betalinger for at sikre afsenderens anonymitet [10] .

For nylig er der dukket mere effektive algoritmer op. Der er skemaer med en sublineær størrelse af signaturen [16] , samt med en konstant størrelse [17] .

Algoritme

Essensen af ​​ringsignaturalgoritmen foreslået af Rivest, Shamir og Tauman er som følger [1] (se diagram).

Ringesignaturen for nogle meddelelser vil blive genereret baseret på listen over offentlige nøgler (angivet i diagrammet som ), blandt hvilke underskriverens nøgle har et serienummer . Offentlige nøgler giver dig mulighed for at kryptere vilkårlig information (informationsblokken , krypteret med nøglen , er angivet i diagrammet som ). " Informationsblokke " herefter er ikke en del af eller resultatet af behandlingen af ​​den signerede meddelelse og har ingen selvstændig betydning, de er genereret tilfældige data, der bliver komponenter af signaturen.

Der er en kombinationsfunktion af et vilkårligt antal argumenter , ved hvilken værdi og værdierne af alle argumenter, undtagen ét, kan man entydigt gendanne et manglende argument. Et eksempel på en sådan funktion er sekventiel summering: hvis den samlede sum og alle led undtagen én er kendt, så kan det manglende led beregnes (ved at reducere den samlede sum med værdien af ​​alle kendte led).

Som en kombinationsfunktion foreslog forfatterne af algoritmen følgende sekvens af handlinger: en vis startværdi tages (angivet i diagrammet , den genereres tilfældigt), over hvilken og det første argument udføres et bitvist eksklusivt "eller" ( angivet i diagrammet med symbolet ). Derefter anvendes en vis reversibel transformation på resultatet (angivet i diagrammet som ), en-til-en forbundet med hash-summen af ​​den besked, der signeres. Resultatet XORed bitvis med det andet argument, konverteringen anvendes igen, og så videre. De tilsvarende informationsblokke krypteret med offentlige nøgler bruges som argumenter .

Den valgte tilfældige værdi er både start- og målværdien (endelig) for kombinationsfunktionen: Resultatet af alle transformationer skal "gå rundt om ringen" og blive lig med startværdien. Informationsblokkene for hver af nøglerne, bortset fra den blok, der svarer til underskriverens egen nøgle, er givet som tilfældige værdier. Underskriveren krypterer informationsblokkene med de tilsvarende offentlige nøgler. Underskriveren har nu målværdien for kombinationsfunktionen og alle argumenterne undtagen ét, det der svarer til dens egen nøgle. Takket være egenskaberne for kombinationsfunktionen kan underskriveren finde ud af det manglende argument og ved hjælp af sin egen private nøgle ( ), "dekryptere" dette argument ( ), få ​​den manglende informationsblok .

Komponenter af den færdige ringsignatur [1] :

• underskrevet besked;
• liste over alle brugte offentlige nøgler;
• værdier af alle informationsblokke ;
• værdien af ​​kombinationsfunktionen .

For at bekræfte signaturen skal du bruge [1] :

• brug af offentlige nøgler til at kryptere informationsblokke;
• ved hjælp af hash-summen af ​​meddelelsen, der skal signeres, beregne værdien af ​​kombinationsfunktionen ved at bruge som argumenter (indstilling af startværdien) og krypterede informationsblokke (resultater af det foregående trin);
• sørg for, at den modtagne værdi matcher .

Implementeringseksempel

Som et eksempel er der givet en Python- implementering af en grundlæggende algoritme, der bruger RSA- nøgler .

import os import hashlib import tilfældig import Crypto.PublicKey.RSA klasse Ring : def __init__ ( selv , k , L = 1024 ): selv . k = k selv . l = L selv . n = len ( k ) selv . q = 1 << ( L - 1 ) def tegn ( selv , m , z ): selv . permut ( m ) s = [ Ingen ] * selv . u = tilfældig . _ randint ( 0 , selv . q ) c = v = selv . E ( u ) for i in ( område ( z + 1 , selv . n ) + område ( z ) ): s [ i ] = tilfældig . randint ( 0 , selv . q ) e = selv . g ( s [ i ], selv . k [ i ] . e , selv . k [ i ] . n ) v = selv . E ( v ^ e ) if ( i + 1 ) % selv . n == 0 : c = v s [ z ] = selv . g ( v ^ u , selv . k [ z ] . d , selv . k [ z ] . n ) returner [ c ] + s def verificere ( selv , m , X ): selv . permut ( m ) def _f ( i ): returnere selv . g ( X [ i + 1 ], selv . k [ i ] . e , selv . k [ i ] . n ) y = map ( _f , interval ( len ( X ) - 1 )) def _g ( x , i ) : returnere selv . E ( x ^ y [ i ]) r = reducere ( _g , rækkevidde ( selv . n ), X [ 0 ]) returnere r == X [ 0 ] def permut ( selv , m ): selv . 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 ( selv , x , e , n ): q , r = divmod ( x , n ) if (( q + 1 ) * n ) <= (( 1 << self . l ) - 1 ): rslt = q * n + pow ( r , e , n ) andet : rslt = x returner rslt

Signering og bekræftelse af 2 beskeder med en ring på 4 brugere:

størrelse = 4 msg1 = 'hej' msg2 = 'verden!' def _rn ( _ ): returner Crypto . PublicKey . R.S.A. _ generere ( 1024 , os . urandom ) nøgle = kort ( _rn , rækkevidde ( størrelse )) r = Ring ( nøgle ) for i i rækkevidde ( størrelse ): s1 = r . tegn ( msg1 , i ) s2 = r . tegn ( msg2 , i ) hævde r . verify ( msg1 , s1 ) og r . verify ( msg2 , s2 ) og ikke r . verificere ( msg1 , s2 )

Noter

1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. Sådan lækker du en hemmelighed  // Fremskridt i kryptologi - ASIACRYPT 2001 / C. Boyd (red.). - Berlin, Heidelberg: Springer-Verlag , 2001. - S. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
2. ↑ I. Yu. Pavlovskaya . Fonosemantisk analyse af tale. - Sankt Petersborg. : Publishing House of St. Petersburg University, 2001. - 290 s.
3. ↑ Historical Dictionary of the Spanish American War / Donald H. Dyal, Brian B. Carpenter og Mark A. Thomas, red. — Westport, Conn.: Greenwood Press , 1996.
4. ↑ B. Schneier . Anvendt kryptografi  . - New York: John Wiley & Sons , 1996. - S. 98.
5. ↑ Debnath A., Singaravelu P., Verma, S. Effektiv spatial beskyttelse af privatlivets fred for sensornetværk // Central European Journal of Engineering . - 2013. - Bd. 3, nr. 1. - S. 1-10. - doi : 10.2478/s13531-012-0048-7 .
6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. En undersøgelse af ringsignatur // Frontiers of Electrical and Electronic Engineering i Kina. - 2008. - Bd. 3, nr. 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. - Bd. 59, nr. 4. - S. 376-382. - doi : 10.4103/03772063.2013.10876518 .
8. ↑ Bresson E., Stern J., Szydlo M. Threshold-ringsignaturer og applikationer til ad-hoc-grupper // 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 Linkbare ringsignaturer: Sikkerhedsmodeller og nye skemaer // Computational Science and Its Applications - ICCSA 2005. - Berlin; New York: Springer, 2005. Vol. 2. - S. 614-623. - ( Lecture Notes in Computer Science . Vol. 3481). - doi : 10.1007/11424826_65 .
10. ↑ 1 2 Fujisaki E., Suzuki K. Sporbar 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. Hentet 24. november 2017. Arkiveret fra originalen 24. november 2017. (ubestemt)
12. ↑ CryptoNote-valutaer  (engelsk) (2015). Hentet 29. november 2017. Arkiveret fra originalen 13. juli 2017.
13. ↑ Er CryptoNote en Bitcoin-morder? (23. juni 2014). Hentet 29. november 2017. Arkiveret fra originalen 1. december 2017. (ubestemt)
14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash via Traceable Ring Signatures  (engelsk) (pdf)  (link ikke tilgængeligt) . www.shadow.cash (2015). Arkiveret fra originalen den 1. december 2017.
15. ↑ Kryptosjov. Broken Crypto in Shadowcash  (engelsk)  (utilgængeligt link) (13/02/2016). Hentet 29. november 2017. Arkiveret fra originalen 27. september 2016.
16. ↑ Fujisaki E. Sporbare ringsignaturer i sublineær størrelse uden tilfældige orakler // Emner 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-størrelse ID-baseret linkbar og genkaldelig-iff-linket ringsignatur // Fremskridt i kryptologi - INDOCRYPT 2006. - Heidelberg; Dordrecht; London; New York: Springer, 2006.—P. 364-378. - ( Lecture Notes in Computer Science . Vol. 4329).

Litteratur

• Chikishev G. O. Engangs-ringsignatur og dens anvendelse i elektroniske kontanter // Applied Discrete Mathematics. - 2012. - Nr. 5. - S. 56-58. - Ansøgning.
• Zapechnikov SV og andre . Ringsignaturer og deres anvendelser i Encyclopedia of Theoretical and Applied Cryptography, MEPhI

Ordbøger og encyklopædier	stor kinesisk

Offentlig nøgle kryptosystemer
Algoritmer	Faktorisering af heltal Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa Diskret logaritme BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS Kryptografi på gitter NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb Andet AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR
Teori	Diskret logaritme på en elliptisk kurve Elliptisk kryptografi Hash-baseret kryptografi Ikke-kommutativ kryptografi RSA problem Envejsfunktion med hemmelig indgang
Standarder	CRYPTREC IEEE P1363 NESSIE NSA Suite B Post kvantekryptering
Emner	Elektronisk signatur OAEP Fingeraftryk PKI web af tillid Nøglestørrelse Identitetsbaseret kryptografi Postkvantekryptografi OpenPGP-kort