Semnătura inelului

Semnătură de sunet ( ring sign în engleză  ) - o opțiune de implementare a unei semnături electronice , în care se știe că mesajul a fost semnat de unul dintre membrii listei potențialilor semnatari, dar nu este dezvăluit de către cine. Semnatarul formează în mod independent o listă cu un număr arbitrar de persoane diferite, inclusiv el însuși în ea. Pentru a aplica o semnătură, semnatarul nu necesită permisiunea, asistența sau asistența persoanelor incluse în listă - sunt folosite doar cheile publice ale tuturor membrilor listei și cheia privată numai a semnatarului însuși.

Algoritmul matematic al semnăturii inelului a fost dezvoltat de Ronald Rivest , Adi Shamir și Yael Tauman , prezentând  în 2001 la conferința internațională Asiacrypt [1] . Potrivit autorilor, în titlu au încercat să sublinieze absența unei structuri centrale sau coordonatoare în formarea unei astfel de semnături: „... inelele sunt figuri geometrice cu periferie uniformă și fără centru”.

Istorie

Ideea unei semnături de grup în cadrul petițiilor sau reclamațiilor, care confirmă că toți semnatarii susțin contestația, dar nu permite identificarea autorului sau inițiatorului acestuia, provine din trecut. Astfel, termenul englezesc „ round-robin ” este cunoscut încă din secolul al XVII-lea și denotă o petiție care a fost semnată în cerc fără a respecta ierarhia pentru a evita mai întâi pedeapsa pentru semnatar [2] - un fel de garanție reciprocă . În 1898, după asediul orașului Santiago de Cuba în timpul războiului hispano-american, ofițeri de rang înalt ai Corpului 5 de armată au semnat o scrisoare în cerc către cartierul general al armatei din Washington prin care cereau ca trupul să fie returnat în Statele Unite . State pentru tratament si odihna. Scrisoarea a intrat în presă și a devenit cunoscută pe scară largă și a provocat, de asemenea, o rezonanță în guvernul președintelui McKinley [3] .

Semnătura multiplă a devenit analogul electronic al semnăturii pe hârtie într-un cerc. În 1991, David Chaum și Eugene Van Heyst au propus o schemă de semnătură de grup  [1] , în care semnatarul este unul dintre membrii grupului format de administrator . Verificatorul poate verifica dacă semnatarul este membru al grupului, dar nu poate afla cine. În acest caz, administratorul are capacitatea de a identifica semnatarul [4] .  

Semnăturile ring sunt în esență similare cu semnăturile de grup, dar, spre deosebire de acestea din urmă, nu există nicio modalitate de a identifica semnatarul, nu există administrator sau coordonator. Toți membrii listei, cu excepția semnatarului însuși, pot să nu cunoască conținutul mesajului sau chiar faptul că cheia lor publică a fost folosită pentru a forma o semnătură de apel de către cineva [1] .

Descrierea generală a mecanismului de creare și verificare a unei semnături de inel

Se presupune că există o anumită listă care indică relația neechivocă a unei persoane cu cheia sa publică (publică) (de exemplu, un server de chei criptografice ). Motivul apariției cheii publice în această listă nu contează. De exemplu, este posibil ca o persoană să fi creat chei RSA numai pentru achiziții pe internet și să nu știe complet că cheile sale publice sunt folosite de cineva pentru a crea o semnătură de apel pe un mesaj pe care nu l-a văzut niciodată și nu a vrut să îl semneze [1] . Algoritmul general de semnătură inelă permite utilizarea simultană a cheilor publice generate de diferite sisteme (algoritmi), inclusiv cele cu dimensiuni diferite atât ale cheilor, cât și ale semnăturilor [1] .

Atunci când creează o semnătură de apel pentru un mesaj m , semnatarul, la propria discreție, formează o listă de chei publice ( P 1 , P 2 , …, P n ), în care include și numărul său i (numărul său de serie în lista nu contează). Toate acestea, împreună cu cheia secretă a semnatarului S i , sunt alimentate ca parametri la intrarea funcției de suprapunere a semnăturii ( m , Si , P 1 , …, P n ), obținându - se rezultatul σ la ieșire . Deși fiecare cheie publică din listă are propria sa cheie privată unică și este folosită doar una dintre ele (aparținând semnatarului), este imposibil de știut din semnătura rezultată care dintre cheile private a fost folosită pentru a o crea. Chiar și cu un număr nelimitat de semnături în inel realizate de același semnatar, nu există nicio modalitate de a-l identifica sau cel puțin de a stabili cu certitudine că unele semnături au fost aplicate folosind aceeași cheie privată [1] .

Autenticitatea semnăturii inelului poate fi verificată folosind σ , m și numai cheile publice P 1 , …, P n [5] .

Opțiuni de implementare

În articolul lor, Rivest, Shamir și Tauman au descris semnătura inelului ca pe o modalitate de a scurge informații secrete fără a-și pierde credibilitatea. De exemplu, semnătura inelului unui „funcționar de rang înalt de la Casa Albă ” nu îi va dezvălui identitatea, dar garantează că mesajul a fost semnat de cineva din lista de funcționari specificată, confirmând astfel nivelul de competență. În același timp, lista persoanelor pentru semnătura inelului poate fi alcătuită cu ușurință prin preluarea cheilor publice din surse deschise [1] .

O altă aplicație, descrisă și de autorii ideii, este pentru crearea de semnături ambigue (controversate) . În cel mai simplu caz, pentru această utilizare, semnătura de apel se formează pe baza cheilor expeditorului și destinatarului mesajului. Atunci semnătura este semnificativă pentru destinatar, acesta este sigur că expeditorul a creat mesajul. Cu toate acestea, pentru un străin, o astfel de semnătură își pierde credibilitatea și lipsa de ambiguitate - nu va exista nicio certitudine cine a format și a semnat exact mesajul, deoarece ar putea fi însuși destinatarul. O astfel de semnătură, de exemplu, nu poate fi folosită în instanță pentru a identifica expeditorul [1] .

Ulterior, au apărut lucrări în care s-au propus noi domenii de aplicare a semnăturilor de inel și algoritmi alternativi pentru formarea acestora [6] [7] .

Semnături de inel de prag

Spre deosebire de semnătura de prag standard „t-out-of-n” , unde t din n utilizatori trebuie să coopereze pentru a decripta un mesaj, această variantă de semnătură de inel necesită t utilizatori să coopereze în procesul de semnare. Pentru a face acest lucru, t participanții ( i 1 , i 2 , …, i t ) trebuie să calculeze semnătura σ pentru mesajul m furnizând t chei private și n chei publice la intrare ( m , S i 1 , S i 2 , ... , S i t , P 1 , …, P n ) [8] .

Semnături de inel care pot fi conectate

Proprietatea de conectivitate vă permite să determinați dacă două semnături de inel au fost create de aceeași persoană (dacă a fost folosită aceeași cheie privată), dar fără a specifica cine. O posibilă aplicație ar putea fi un sistem de monedă electronică offline [9] .

Semnătură de inel urmăribilă

Pe lângă semnătura asociată, cheia publică a semnatarului poate fi expusă atunci când este reutilizată. Un astfel de protocol permite implementarea unor sisteme secrete de vot electronic care permit ca o singură semnătură să fie anonimă, dar dezvăluie participantul care a votat de două ori [10] .

Criptomonede

Sistemul CryptoNote permite semnături de inel [11] . Acesta a fost folosit pentru prima dată în iulie 2012 în criptomoneda Bytecoin [12] [13] (a nu se confunda cu Bitcoin ).

Criptomoneda ShadowCash folosește o semnătură de inel urmăribilă pentru a anonimiza expeditorul unei tranzacții [14] . Cu toate acestea, implementarea inițială a fost greșită, ceea ce a dus la deanonimizarea parțială a ShadowCash de la prima implementare până în februarie 2016 [15] .

Eficiență

Majoritatea algoritmilor propuși au o dimensiune asimptotică a rezultatului , adică dimensiunea semnăturii rezultate este direct proporțională cu numărul de chei publice utilizate. Fiecare cheie publică utilizată atunci când se impune sau se verifică o semnătură de inel necesită o cantitate fixă ​​de calcule, care este mult mai bună decât analogii disponibili la momentul creării protocolului [1] . De exemplu, tehnologia CryptoNote implementează semnături de inel în plățile p2p pentru a asigura anonimatul expeditorului [10] .

Recent, au apărut algoritmi mai eficienți. Există scheme cu o dimensiune subliniară a semnăturii [16] , precum și cu o dimensiune constantă [17] .

Algoritm

Esența algoritmului de semnătură inelă propus de Rivest, Shamir și Tauman este următoarea [1] (vezi diagrama).

Semnătura de apel pentru un mesaj va fi generată pe baza listei de chei publice (indicate în diagramă ca ), printre care cheia semnatarului are un număr de serie . Cheile publice vă permit să criptați informații arbitrare (blocul de informații , criptat cu cheia , este indicat în diagramă ca ). „ Blocuri de informații ” de aici în continuare nu fac parte sau rezultatul prelucrării mesajului semnat și nu au semnificație independentă, ele sunt date aleatorii generate care devin componente ale semnăturii.

Există o funcție combinată a unui număr arbitrar de argumente , prin valoarea căruia și valorile tuturor argumentelor, cu excepția unuia, se poate restaura în mod unic un argument lipsă. Un exemplu de astfel de funcție este însumarea secvențială: dacă suma totală și toți termenii cu excepția unuia sunt cunoscuți, atunci termenul lipsă poate fi calculat (prin reducerea sumei totale cu valoarea tuturor termenilor cunoscuți).

Ca funcție de combinație, autorii algoritmului au propus următoarea secvență de acțiuni: se ia o anumită valoare de pornire (indicată în diagramă , este generată aleatoriu), peste care și primul argument se execută un „sau” exclusiv pe biți ( indicat în diagramă prin simbolul ). Apoi, rezultatului i se aplică o anumită transformare reversibilă (indicată în diagramă ca ), unu-la-unu asociată cu suma hash a mesajului care este semnat. Rezultatul este XOR pe biți cu al doilea argument, conversia este aplicată din nou și așa mai departe. Blocurile de informații corespunzătoare criptate cu chei publice sunt folosite ca argumente .

Valoarea aleatoare selectată este atât valoarea inițială, cât și valoarea țintă (finală) a funcției de combinație: rezultatul tuturor transformărilor trebuie să „ocolească inelul” și să devină egal cu valoarea inițială. Blocurile de informații pentru fiecare dintre chei, cu excepția blocului corespunzător cheii proprii semnatarului, sunt date ca valori aleatorii. Semnatarul criptează blocurile de informații cu cheile publice corespunzătoare. Semnatarul are acum valoarea țintă a funcției combinaționale și toate argumentele cu excepția unuia, cel corespunzător cheii proprii. Datorită proprietăților funcției combinaționale, semnatarul poate afla argumentul lipsă și, folosind propria sa cheie privată ( ), „decriptează” acest argument ( ), obținând blocul de informații lipsă .

Componentele semnăturii inelului finit [1] :

Pentru a verifica semnătura aveți nevoie de [1] :

Exemplu de implementare

Ca exemplu, este dată o implementare Python a unui algoritm de bază folosind chei RSA .

import os import hashlib import import aleatoriu Crypto.PublicKey.RSA clasa Ring : def __init__ ( self , k , L = 1024 ): self . k = k sine . l = L sine . n = len ( k ) sine . q = 1 << ( L - 1 ) semn def ( self , m , z ): self . permut ( m ) s = [ Nici unul ] * sine . u = aleatoriu . _ randint ( 0 , self . q ) c = v = self . E ( u ) pentru i în ( interval ( z + 1 , self . n ) + interval ( z )): s [ i ] = aleatoriu . randint ( 0 , self . q ) e = self . g ( s [ i ] , sine . k [ i ] . e , sine . k [ i ] . n ) v = sine . E ( v ^ e ) dacă ( i + 1 ) % sine . n == 0 : c = v s [ z ] = sine . g ( v ^ u , self . k [ z ] . d , self . k [ z ] . n ) return [ c ] + s def verify ( self , m , X ): self . permut ( m ) def _f ( i ): return self . g ( X [ i + 1 ], self . k [ i ] . e , self . k [ i ] . n ) y = hartă ( _f , interval ( len ( X ) - 1 )) def _g ( x , i ) : întoarce- te pe sine . E ( x ^ y [ i ]) r = reduce ( _g , interval ( self . n ), X [ 0 ]) return 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

Semnarea și verificarea a 2 mesaje cu un apel de 4 utilizatori:

dimensiune = 4 msg1 = „bună ziua” msg2 = „lumea!” def _rn ( _ ): returnează Crypto . PublicKey . R.S.A. _ genera ( 1024 , os . urandom ) key = map ( _rn , range ( size )) r = Ring ( key ) for i in range ( size ): s1 = r . semn ( msg1 , i ) s2 = r . semn ( msg2 , i ) afirmă r . verifica ( msg1 , s1 ) și r . verifica ( msg2 , s2 ) si nu r . verifica ( msg1 , s2 )

Note

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. How to leak a secret  // Advances in Cryptology - ASIACRYPT 2001 / C. Boyd (ed.). - Berlin, Heidelberg: Springer-Verlag , 2001. - P. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
  2. ↑ I. Yu. Pavlovskaya . Analiza fonosemantică a vorbirii. - Sankt Petersburg. : Editura Universităţii din Sankt Petersburg, 2001. - 290 p.
  3. ↑ Dicționar istoric al războiului hispano-american / Donald H. Dyal, Brian B. Carpenter și Mark A. Thomas, eds. - Westport, Connecticut: Greenwood Press , 1996.
  4. ↑ B. Schneier . Criptografie  aplicată . - New York: John Wiley & Sons , 1996. - P. 98.
  5. ↑ Debnath A., Singaravelu P., Verma, S. Efficient spatial privacy protection scheme for sensor network // Central European Journal of Engineering . - 2013. - Vol. 3, nr. 1. - P. 1-10. - doi : 10.2478/s13531-012-0048-7 .
  6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. Un studiu asupra semnăturii inelului // Frontierele ingineriei electrice și electronice în China. - 2008. - Vol. 3, nr. 1. - P. 10-19. - doi : 10.1007/s11460-008-0012-8 .
  7. ↑ Hu Xiong, Zhiguang Qin, Fagen Li. O taxonomie a schemelor de semnătură inelului: teorie și aplicații // Jurnalul de cercetare IETE. - 2013. - Vol. 59, nr. 4. - P. 376-382. - doi : 10.4103/03772063.2013.10876518 .
  8. ↑ Bresson E., Stern J., Szydlo M. Threshold ring signatures and applications to ad-hocgroups // Advances in Cryptology: CRYPTO 2002 / Moti Yung. - Berlin, Heidelberg, Ney York, Barcelona, ​​Hong Kong, Londra, Milano, Paris, Tokyo: Springer, 2002. - P. 465-480. - ( Lecture Notes in Computer Science . Vol. 2442). - doi : 10.1007/3-540-45708-9_30 .
  9. ↑ Liu JK, Wong DS Semnături de inel linkable: Modele de securitate și scheme noi // 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. Traceable Ring Signature // Public Key Cryptography - PKC 2007. - Berlin; Heidelberg; New York: Springer, 2007. - P. 181-200. - ( Lecture Notes in Computer Science . Vol. 4450).
  11. ↑ Filosofia CryptoNote . CryptoNoteTech. Consultat la 24 noiembrie 2017. Arhivat din original la 24 noiembrie 2017.
  12. ↑ CryptoNote Currencies  (engleză) (2015). Consultat la 29 noiembrie 2017. Arhivat din original la 13 iulie 2017.
  13. ↑ Este CryptoNote un Bitcoin Killer? (23 iunie 2014). Consultat la 29 noiembrie 2017. Arhivat din original la 1 decembrie 2017.
  14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash prin Traceable Ring Signatures  (engleză) (pdf)  (link nu este disponibil) . www.shadow.cash (2015). Arhivat din original la 1 decembrie 2017.
  15. ↑ Crypto Fun. Broken Crypto în Shadowcash  (engleză)  (link indisponibil) (13.02.2016). Consultat la 29 noiembrie 2017. Arhivat din original la 27 septembrie 2016.
  16. ↑ Fujisaki E. Sublinear size traceable ring signatures without random oracles // Topics in Cryptology - CT-RSA 2011. - Heidelberg; Dordrecht; Londra; New York: Springer, 2011. - P. 393-415. - ( Lecture Notes in Computer Science . Vol. 6558).
  17. ↑ Au, Man Ho; Liu JK; Susilo W.; Yuen, Tsz Hong. Semnătură de inel conectabilă și revocabilă, bazată pe ID-ul de dimensiune constantă // Progresul în criptologie - INDOCRYPT 2006. - Heidelberg; Dordrecht; Londra; New York: Springer, 2006.—P. 364-378. - ( Lecture Notes in Computer Science . Vol. 4329).

Literatură

  Accesați articolul Wikidata  Dicționare și enciclopedii
 Criptosisteme cu cheie publică
Algoritmi
Factorizarea numerelor întregi
Logaritm discret
Criptografia pe zăbrele
Alte
Teorie
Standarde
Subiecte