Sormus allekirjoitus

Ring signature ( englanniksi  ring signature ) - sähköisen allekirjoituksen toteutusvaihtoehto , jossa tiedetään, että viestin on allekirjoittanut yksi potentiaalisten allekirjoittajien luettelon jäsenistä, mutta kuka ei paljasta sitä. Allekirjoittaja muodostaa itsenäisesti listan mielivaltaisesta määrästä eri henkilöitä, mukaan lukien itsensä siihen. Allekirjoituksen hakemiseen allekirjoittaja ei vaadi lupaa, apua tai apua luettelossa olevilta henkilöiltä - käytetään vain kaikkien listan jäsenten julkisia avaimia ja vain allekirjoittajan itsensä yksityistä avainta .

Rengasallekirjoituksen matemaattisen algoritmin kehittivät Ronald Rivest , Adi Shamir ja Yael Tauman vuonna  2001 kansainvälisessä konferenssissa Asiacrypt [1] . Kirjoittajien mukaan otsikossa he yrittivät korostaa keskeisen tai koordinoivan rakenteen puuttumista tällaisen allekirjoituksen muodostuksessa: "... renkaat ovat geometrisia kuvioita, joilla on yhtenäinen reuna ja ilman keskustaa."

Historia

Ajatus vetoomusten tai valitusten alla olevasta ryhmäallekirjoituksesta, joka vahvistaa, että kaikki allekirjoittajat tukevat vetoomusta, mutta ei salli sen tekijän tai aloitteentekijän tunnistamista, on peräisin menneisyydestä. Näin ollen englanninkielinen termi " round-robin " on tunnettu 1600-luvulta lähtien ja se tarkoittaa vetoomusta, joka allekirjoitettiin ympyrässä hierarkiaa kunnioittamatta, jotta allekirjoittajaa ei rangaistu ensin [2] - eräänlainen keskinäinen takuu . Vuonna 1898, kun Santiago de Cuban kaupunkia piiritettiin Espanjan ja Amerikan sodan aikana, 5. armeijajoukon korkea-arvoiset upseerit allekirjoittivat ympyrässä kirjeen armeijan päämajalle Washingtonissa vaatien joukkojen palauttamista Yhdysvaltoihin . hoitoon ja lepoon. Kirje pääsi lehdistöön ja tuli laajalti tunnetuksi ja aiheutti myös resonanssia presidentti McKinleyn hallituksessa [3] .

Monikertaisesta allekirjoituksesta on tullut ympyränmuotoisen paperiallekirjoituksen elektroninen analogi. Vuonna 1991 David Chaum ja Eugene Van Heyst ehdottivat ryhmäallekirjoitusjärjestelmää  [1] , jossa allekirjoittaja on yksi järjestelmänvalvojan muodostaman ryhmän jäsenistä . Todentaja voi varmistaa, että allekirjoittaja on ryhmän jäsen, mutta ei voi saada selville kuka. Tässä tapauksessa järjestelmänvalvojalla on mahdollisuus tunnistaa allekirjoittaja [4] .  

Soittoallekirjoitukset ovat pohjimmiltaan samanlaisia ​​kuin ryhmäallekirjoitukset, mutta toisin kuin jälkimmäisessä, allekirjoittajaa ei voida tunnistaa, ei ole ylläpitäjää tai koordinaattoria. Kaikki listan jäsenet allekirjoittajaa itseään lukuun ottamatta eivät välttämättä tiedä viestin sisältöä tai edes sitä tosiasiaa, että joku on käyttänyt heidän julkista avaimeansa sormusallekirjoituksen muodostamiseen [1] .

Yleinen kuvaus mekanismista rengasallekirjoituksen luomiseksi ja tarkistamiseksi

Oletetaan, että on olemassa tietty luettelo, joka osoittaa henkilön yksiselitteisen suhteen hänen julkiseen (julkiseen) avaimeensa (esimerkiksi kryptografinen avainpalvelin ). Syyllä julkisen avaimen esiintymiseen tässä luettelossa ei ole merkitystä. Henkilö on esimerkiksi saattanut luoda RSA -avaimet vain Internet - ostoksia varten, eikä hän välttämättä ole täysin tietoinen siitä, että joku käyttää hänen julkisia avaimiaan soittoäänen luomiseen viestiin, jota hän ei ole koskaan nähnyt eikä halunnut allekirjoittaa [1] . Yleinen rengasallekirjoitusalgoritmi mahdollistaa eri järjestelmien (algoritmien) generoimien julkisten avainten samanaikaisen käytön, mukaan lukien ne, joilla on erikokoiset avaimet ja allekirjoitukset [1] .

Luodessaan rengasallekirjoituksen viestille m allekirjoittaja muodostaa oman harkintansa mukaan listan julkisista avaimista ( P 1 , P 2 , …, P n ), johon hän sisällyttää myös numeronsa i (sen sarjanumeron listalla ei ole väliä). Kaikki tämä yhdessä allekirjoittajan Si salaisen avaimen kanssa syötetään parametreina allekirjoituksen päällekkäisfunktion ( m , Si , P1 , …, Pn ) sisäänmenoon , jolloin saadaan tulos σ lähdöstä . Vaikka jokaisella listan julkisella avaimella on oma yksilöllinen yksityinen avain ja vain yksi niistä (allekirjoittajalle kuuluva) on käytössä, tuloksena olevasta allekirjoituksesta on mahdotonta tietää, mitä yksityistä avainta käytettiin sen luomiseen. Jopa saman allekirjoittajan tekemällä rajattomalla määrällä rengasallekirjoituksia ei ole mahdollista tunnistaa häntä tai ainakaan varmuudella varmistaa, että joitain allekirjoituksia on käytetty samalla yksityisellä avaimella [1] .

Soiton allekirjoituksen aitous voidaan varmistaa käyttämällä σ , m ja vain julkisia avaimia P 1 , …, P n [5] .

Toteutusvaihtoehdot

Artikkelissaan Rivest, Shamir ja Tauman kuvasivat sormusallekirjoitusta tapana vuotaa salaisia ​​tietoja menettämättä uskottavuuttaan. Esimerkiksi "korkean Valkoisen talon virkamiehen " sormusallekirjoitus ei paljasta hänen henkilöllisyyttään, mutta takaa, että viestin on allekirjoittanut joku määritellystä virkamiesluettelosta, mikä vahvistaa pätevyyden tason. Samalla soittoäänen henkilöluettelo voidaan helposti koota ottamalla julkisia avaimia avoimista lähteistä [1] .

Toinen idean kirjoittajien kuvailema sovellus on moniselitteisten (kiistanalaisten) allekirjoitusten luominen . Yksinkertaisimmassa tapauksessa tätä käyttöä varten rengasallekirjoitus muodostetaan viestin lähettäjän ja vastaanottajan avainten perusteella. Silloin allekirjoitus on vastaanottajalle tärkeä, hän on varma, että lähettäjä loi viestin. Ulkopuoliselle tällainen allekirjoitus kuitenkin menettää uskottavuutensa ja yksiselitteisyytensä - ei ole varmuutta, kuka viestin tarkasti muotoili ja allekirjoitti, koska se voi olla vastaanottaja itse. Tällaista allekirjoitusta ei voi esimerkiksi käyttää tuomioistuimessa lähettäjän tunnistamiseen [1] .

Myöhemmin ilmestyi teoksia, joissa ehdotettiin uusia renkaan allekirjoitusten sovellusalueita ja vaihtoehtoisia algoritmeja niiden muodostamiseen [6] [7] .

Kynnysrenkaan allekirjoitukset

Toisin kuin tavallinen "t-out-of-n" kynnysallekirjoitus , jossa t n : stä käyttäjästä täytyy tehdä yhteistyötä viestin salauksen purkamiseksi , tämä soittoallekirjoitusmuunnelma edellyttää t käyttäjän yhteistyötä allekirjoitusprosessissa. Tätä varten t osallistujan ( i 1 , i 2 , …, i t ) on laskettava allekirjoitus σ viestille m toimittamalla t yksityistä ja n julkista avainta syötteeseen ( m , S i 1 , S i 2 , … , S i t , P 1 , …, P n ) [8] .

Linkitettävät sormusallekirjoitukset

Yhteysominaisuuden avulla voit määrittää, onko sama henkilö luonut kaksi soittoallekirjoitusta (käytettiinkö samaa yksityistä avainta), mutta määrittelemättä kuka. Yksi mahdollinen sovellus voisi olla offline- sähköisen rahan järjestelmä [9] .

Jäljitettävä sormusallekirjoitus

Liittyvän allekirjoituksen lisäksi allekirjoittajan julkinen avain saattaa paljastua, kun sitä käytetään uudelleen. Tällainen protokolla mahdollistaa salaisten sähköisten äänestysjärjestelmien toteuttamisen, jotka sallivat vain yhden allekirjoituksen olevan nimettömänä, mutta paljastavat kahdesti äänestäneen osallistujan [10] .

Kryptovaluutat

CryptoNote - järjestelmä sallii soittoäänen [11] . Tätä käytettiin ensimmäisen kerran heinäkuussa 2012 kryptovaluuttana Bytecoin [12] [13] (ei pidä sekoittaa Bitcoiniin ).

ShadowCash -kryptovaluutta käyttää jäljitettävää rengasallekirjoitusta tapahtuman lähettäjän anonymisoimiseksi [ 14 ] . Alkuperäinen toteutus oli kuitenkin virheellinen, mikä johti ShadowCashin osittaiseen deanonymisointiin ensimmäisestä toteutuksesta helmikuuhun 2016 [15] .

Tehokkuus

Useimmilla ehdotetuilla algoritmeilla on asymptoottinen tuloskoko , eli tuloksena olevan allekirjoituksen koko on suoraan verrannollinen käytettyjen julkisten avainten määrään. Jokainen käytetty julkinen avain soittoallekirjoituksen määräämisessä tai tarkistamisessa vaatii kiinteän määrän laskelmia, mikä on paljon parempi kuin protokollan luomishetkellä saatavilla olevat analogit [1] . Esimerkiksi CryptoNote- teknologia toteuttaa p2p -maksuissa soittoallekirjoituksia varmistaakseen lähettäjän anonymiteetin [10] .

Viime aikoina on ilmestynyt tehokkaampia algoritmeja. On olemassa malleja, joiden allekirjoituksen koko on sublineaarinen [16] , sekä vakiokokoinen [17] .

Algoritmi

Rivestin, Shamirin ja Taumanin ehdottaman rengasallekirjoitusalgoritmin olemus on seuraava [1] (katso kaavio).

Joidenkin sanomien soittoääni luodaan julkisten avainten luettelon perusteella (merkitty kaaviossa merkillä ), joiden joukossa allekirjoittajan avaimella on sarjanumero . Julkisilla avaimilla voit salata mielivaltaisia ​​tietoja ( avaimella salattu tietolohko on merkitty kaaviossa nimellä ). " Tietolohkot " eivät ole osa allekirjoitetun viestin käsittelyä tai sen käsittelyn tulosta, eikä niillä ole itsenäistä merkitystä, ne ovat generoituja satunnaisia ​​tietoja, joista tulee allekirjoituksen komponentteja.

On olemassa mielivaltaisen määrän argumentteja yhdistelmäfunktio , jonka arvon ja kaikkien argumenttien, yhtä lukuun ottamatta, arvojen perusteella voidaan yksiselitteisesti palauttaa yksi puuttuva argumentti. Esimerkki tällaisesta funktiosta on peräkkäinen summaus: jos kokonaissumma ja kaikki termit yhtä lukuun ottamatta ovat tiedossa, niin puuttuva termi voidaan laskea (vähentämällä kokonaissummaa kaikkien tunnettujen termien arvolla).

Yhdistelmäfunktiona algoritmin kirjoittajat ehdottivat seuraavaa toimintosarjaa: otetaan tietty aloitusarvo (osoitettu kaaviossa , se generoidaan satunnaisesti), jonka ja ensimmäisen argumentin päälle suoritetaan bittikohtaisesti poissulkeva "tai" ( merkitty kaaviossa symbolilla ). Sitten tulokseen sovelletaan tiettyä palautuvaa muunnosa (merkitty kaaviossa merkillä ), yksi yhteen liitettynä allekirjoitettavan viestin hash-summaan . Tulos XOR-korjataan bittikohtaisesti toisella argumentilla, muunnos otetaan uudelleen käyttöön ja niin edelleen. Argumentteina käytetään vastaavia julkisilla avaimilla salattuja tietolohkoja .

Valittu satunnaisarvo on sekä yhdistelmäfunktion aloitus- että tavoitearvo (lopullinen): kaikkien muunnosten tuloksen on "kierrettävä renkaan ympäri" ja oltava yhtä suuri kuin alkuarvo. Jokaisen avaimen tietolohkot, paitsi allekirjoittajan omaa avainta vastaava lohko , annetaan satunnaisina arvoina. Allekirjoittaja salaa tietolohkot vastaavilla julkisilla avaimilla. Allekirjoittajalla on nyt yhdistelmäfunktion tavoitearvo ja kaikki argumentit yhtä lukuun ottamatta, sen omaa avainta vastaava argumentti. Yhdistelmäfunktion ominaisuuksien ansiosta allekirjoittaja voi löytää puuttuvan argumentin ja omalla yksityisellä avaimellaan ( ) "purkaa" tämän argumentin salauksen ( ) saadakseen puuttuvan tietolohkon .

Valmiin sormusallekirjoituksen [1] osat :

Allekirjoituksen vahvistamiseksi tarvitset [1] :

Toteutusesimerkki

Esimerkkinä annetaan RSA -avaimia käyttävän perusalgoritmin Python -toteutus .

tuonti käyttöjärjestelmä tuonti hashlib tuonti satunnainen tuonti Crypto.PublicKey.RSA luokka Ring : def __init__ ( itse , k , L = 1024 ) : itse . k = k itse . l = L itse . n = len ( k ) itse . q = 1 << ( L - 1 ) def- merkki ( itse , m , z ): itse . permut ( m ) s = [ Ei mitään ] * itse . u = satunnainen . _ randint ( 0 , itse . q ) c = v = itse . E ( u ) i : lle in ( alue ( z + 1 , itse . n ) + alue ( z )): s [ i ] = satunnainen . randint ( 0 , itse . q ) e = itse . g ( s [ i ] , itse . k [ i ] . e , itse . k [ i ] . n ) v = itse . E ( v ^ e ) jos ( i + 1 ) % itse . n == 0 : c = v s [ z ] = itse . g ( v ^ u , itse . k [ z ] . d , itse . k [ z ] . n ) paluu [ c ] + s def verify ( itse , m , X ): itse . permutti ( m ) def _f ( i ): palauttaa itsensä . g ( X [ i + 1 ], itse . k [ i ] . e , itse . k [ i ] . n ) y = kartta ( _f , alue ( len ( X ) - 1 )) def _g ( x , i ) : palauta itsesi . E ( x ^ y [ i ]) r = vähennä ( _g , alue ( itse . n ), X [ 0 ]) palauttaa r == X [ 0 ] def permut ( itse , m ): itse . p = int ( hashlib . sha1 ( ' %s ' % m ) . heksadigesti ( ), 16 ) def E ( itse , x ): msg = ' %s %s ' % ( x , itse . p ) return int ( hashlib . sha1 ( msg ) . hexdigest ( ), 16 ) def g ( itse , x , e , n ): q , r = divmod ( x , n ) jos (( q + 1 ) * n ) <= (( 1 << itse . l ) - 1 ): rslt = q * n + pow ( r , e , n ) else : rslt = x return rslt

Kahden viestin allekirjoittaminen ja vahvistaminen 4 käyttäjän renkaalla:

koko = 4 msg1 = 'hei' msg2 = 'maailma!' def _rn ( _ ): palauta krypto . Julkinen avain . R.S.A. _ generoida ( 1024 , os . urandom ) avain = kartta ( _rn , alue ( koko )) r = Sormus ( avain ) i :lle alueella ( koko ) : s1 = r . merkki ( msg1 , i ) s2 = r . merkki ( msg2 , i ) assert r . verify ( msg1 , s1 ) ja r . vahvista ( msg2 , s2 ) eikä r . _ vahvista ( msg1 , s2 )

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. Kuinka vuotaa salaisuus  // Advances in Cryptology - ASIACRYPT 2001 / C. Boyd (toim.). - Berliini, Heidelberg: Springer-Verlag , 2001. - P. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
  2. ↑ I. Yu. Pavlovskaja . Puheen fonosemanttinen analyysi. - Pietari. : Publishing House of St. Petersburg University, 2001. - 290 s.
  3. ↑ Historical Dictionary of the Spanish American War / Donald H. Dyal, Brian B. Carpenter ja Mark A. Thomas, toim. - Westport, Conn.: Greenwood Press , 1996.
  4. ↑ B. Schneier . Sovellettu kryptografia  . - New York: John Wiley & Sons , 1996. - s. 98.
  5. ↑ Debnath A., Singaravelu P., Verma, S. Tehokas spatial privacy protection system for sensor network // Central European Journal of Engineering . - 2013. - Vol. 3, ei. 1. - s. 1-10. - doi : 10.2478/s13531-012-0048-7 .
  6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. Sormusallekirjoituksen kysely // Sähkö- ja elektroniikkatekniikan rajat Kiinassa. - 2008. - Voi. 3, ei. 1. - s. 10-19. - doi : 10.1007/s11460-008-0012-8 .
  7. ↑ Hu Xiong, Zhiguang Qin, Fagen Li. Sormusallekirjoitusjärjestelmien taksonomia: teoria ja sovellukset // IETE Journal of Research. - 2013. - Vol. 59, nro. 4. - s. 376-382. - doi : 10.4103/03772063.2013.10876518 .
  8. ↑ Bresson E., Stern J., Szydlo M. Kynnysrenkaiden allekirjoitukset ja sovellukset ad-hocryhmille // Advances in Cryptology: CRYPTO 2002 / Moti Yung. - Berliini, Heidelberg, Ney York, Barcelona, ​​Hongkong, Lontoo, Milano, Pariisi, 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 Linkitettävät rengasallekirjoitukset: Tietoturvamallit ja uudet järjestelmät // Computational Science and Its Applications - ICCSA 2005. - Berliini; New York: Springer, 2005. Voi. 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. - Berliini; Heidelberg; New York: Springer, 2007. - s. 181-200. - ( Lecture Notes in Computer Science . Vol. 4450).
  11. ↑ CryptoNote-filosofia . CryptoNoteTech. Haettu 24. marraskuuta 2017. Arkistoitu alkuperäisestä 24. marraskuuta 2017.
  12. ↑ CryptoNote-valuutat  (englanniksi) (2015). Haettu 29. marraskuuta 2017. Arkistoitu alkuperäisestä 13. heinäkuuta 2017.
  13. ↑ Onko CryptoNote Bitcoin-tappaja? (23. kesäkuuta 2014). Haettu 29. marraskuuta 2017. Arkistoitu alkuperäisestä 1. joulukuuta 2017.
  14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash jäljitettävien rengasallekirjoitusten kautta  (englanniksi) (pdf)  (linkki ei saatavilla) . www.shadow.cash (2015). Arkistoitu alkuperäisestä 1. joulukuuta 2017.
  15. ↑ Crypto Fun. Broken Crypto Shadowcashissa  (englanniksi)  (linkki ei saatavilla) (13.2.2016). Haettu 29. marraskuuta 2017. Arkistoitu alkuperäisestä 27. syyskuuta 2016.
  16. ↑ Fujisaki E. Sublineaarikokoiset jäljitettävät sormusallekirjoitukset ilman satunnaisia ​​oraakkeleita // Kryptologian aiheet - CT-RSA 2011. - Heidelberg; Dordrecht; Lontoo; 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. Vakiokokoinen ID-pohjainen linkitettävä ja peruutettava-iff-linkitetty rengasallekirjoitus // Progress in Cryptology - INDOCRYPT 2006. - Heidelberg; Dordrecht; Lontoo; New York: Springer, 2006. – s. 364-378. - ( Lecture Notes in Computer Science . Vol. 4329).

Kirjallisuus

  Siirry Wikidata-kohteeseen  Sanakirjat ja tietosanakirjat
 Julkisen avaimen salausjärjestelmät
Algoritmit
Kokonaislukujen faktorointi
Diskreetti logaritmi
Kryptografia ristikoilla
Muut
Teoria
Standardit
Aiheet