Gyűrűs aláírás

Ring signature ( angol  ring signature ) - egy elektronikus aláírás megvalósítási lehetősége , amelyben ismert, hogy az üzenetet a potenciális aláírók listájának egyik tagja írta alá, de azt nem hozták nyilvánosságra, hogy ki. Az aláíró önállóan összeállít egy listát tetszőleges számú különböző személyről, beleértve önmagát is. Az aláírás alkalmazásához az aláírónak nincs szüksége engedélyre, segítségre vagy segítségre a listán szereplő személyektől - csak a lista összes tagjának nyilvános kulcsát és csak az aláíró magánkulcsát használják fel.

A gyűrűs aláírás matematikai algoritmusát Ronald Rivest , Adi Shamir és Yael Tauman fejlesztette  ki 2001-ben az Asiacrypt [1] nemzetközi konferencián . A szerzők szerint a címben igyekeztek hangsúlyozni, hogy egy ilyen aláírás kialakításánál nincs központi vagy koordináló struktúra: "...a gyűrűk egységes perifériájú, középpont nélküli geometriai alakzatok."

Történelem

A petíciók vagy panaszok alatti csoportos aláírás gondolata, amely megerősíti, hogy minden aláíró támogatja a fellebbezést, de nem teszi lehetővé annak szerzőjének vagy kezdeményezőjének azonosítását, a múltból származik. Így az angol „ round-robin ” kifejezés a 17. század óta ismert, és olyan petíciót jelöl, amelyet körben írtak alá a hierarchia tiszteletben tartása nélkül, hogy elkerüljék az aláíró büntetését [2] - egyfajta kölcsönös garancia . 1898-ban, Santiago de Cuba városának a spanyol-amerikai háború alatti ostroma után, az 5. hadsereg magas rangú tisztjei körben írták alá a washingtoni hadsereg főhadiszállásának küldött levelet, amelyben azt követelték, hogy a hadtestet adják vissza az Egyesült Államoknak. kezelésre és pihenésre. A levél bekerült a sajtóba és széles körben ismertté vált, és McKinley elnök kormányában is visszhangot váltott ki [3] .

A többszörös aláírás a kör alakú papíraláírás elektronikus analógja lett. 1991-ben David Chaum és Eugene Van Heyst csoportos  aláírási sémát javasolt [ 1 ] , ahol az aláíró az adminisztrátor által alkotott csoport egyik tagja .  Az ellenőr tudja ellenőrizni, hogy az aláíró tagja-e a csoportnak, de nem tudja kideríteni, hogy ki. Ebben az esetben az adminisztrátornak lehetősége van azonosítani az aláírót [4] .

A gyűrűs aláírások lényegében hasonlóak a csoportos aláírásokhoz, de ez utóbbiakkal ellentétben nincs lehetőség az aláíró azonosítására, nincs rendszergazda vagy koordinátor. A lista minden tagja, magát az aláírót kivéve, nem tudhatja az üzenet tartalmát, de még azt sem, hogy a nyilvános kulcsával valaki gyűrűs aláírást alkotott [1] .

A gyűrűs aláírás létrehozásának és ellenőrzésének mechanizmusának általános leírása

Feltételezzük, hogy van egy bizonyos lista, amely jelzi egy személynek a nyilvános (nyilvános) kulcsával való egyértelmű kapcsolatát (például egy kriptográfiai kulcsszerver ). A nyilvános kulcs megjelenésének oka ebben a listában nem számít. Például előfordulhat, hogy egy személy csak internetes vásárlásokhoz hozott létre RSA -kulcsokat, és egyáltalán nem tudja, hogy a nyilvános kulcsait valaki arra használja, hogy gyűrűs aláírást hozzon létre egy olyan üzeneten, amelyet soha nem látott, és nem is akart aláírni [1] . Az általános gyűrűs aláírási algoritmus lehetővé teszi a különböző rendszerek (algoritmusok) által generált nyilvános kulcsok egyidejű használatát, beleértve azokat is, amelyek különböző méretű kulcsokkal és aláírásokkal rendelkeznek [1] .

Amikor egy üzenethez gyűrűs aláírást hoz létre , az aláíró saját belátása szerint létrehoz egy listát a nyilvános kulcsokról ( P 1 , P 2 , …, P n ), amelyben az i számát is tartalmazza ( sorszámát a a lista nem számít). Mindez az S i aláíró titkos kulcsával együtt paraméterként az aláírás-átfedő függvény ( m , S i , P 1 , …, P n ) bemenetére kerül , így a kimeneten a σ eredményt kapjuk . Bár a listán szereplő minden nyilvános kulcsnak megvan a maga egyedi titkos kulcsa, és ezek közül csak az egyiket (az aláíróhoz tartozót) használjuk, a kapott aláírásból nem lehet tudni, hogy a titkos kulcsok közül melyiket használták a létrehozásához. Még ha korlátlan számú csengőaláírást is készített ugyanaz az aláíró, nem lehet azonosítani őt, vagy legalábbis biztosan megállapítani, hogy egyes aláírásokat ugyanazzal a privát kulccsal alkalmaztak [1] .

A csengőaláírás hitelessége σ , m és csak P 1 , …, P n [5] nyilvános kulcsokkal ellenőrizhető .

Megvalósítási lehetőségek

Rivest, Shamir és Tauman cikkükben úgy írták le a gyűrűs aláírást, mint a titkos információk kiszivárogtatásának módját anélkül, hogy elveszítené hitelességét. Például egy "magas rangú Fehér Ház tisztviselőjének " gyűrűs aláírása nem fedi fel személyazonosságát, de garantálja, hogy az üzenetet valaki a tisztviselők meghatározott listájáról írta alá, ezzel megerősítve a kompetencia szintjét. Ugyanakkor a gyűrűs aláíráshoz szükséges személyek listája könnyen összeállítható nyílt forrásból származó nyilvános kulcsok felvételével [1] .

Egy másik alkalmazás, amelyet az ötlet szerzői is leírtak, kétértelmű (vitatott) aláírások létrehozására szolgál . A legegyszerűbb esetben erre a célra a csengőaláírást az üzenet küldőjének és címzettjének kulcsai alapján alakítják ki. Ekkor az aláírás jelentős a címzett számára, biztos abban, hogy a feladó hozta létre az üzenetet. Egy kívülálló számára azonban egy ilyen aláírás elveszti hitelességét és egyértelműségét – nem lesz biztos, hogy pontosan ki formálta és írta alá az üzenetet, mert lehet, hogy maga a címzett is. Ilyen aláírás például nem használható a bíróságon a feladó azonosítására [1] .

Később megjelentek olyan munkák, amelyekben a gyűrűs aláírások új alkalmazási területeit és alternatív algoritmusokat javasoltak kialakításukra [6] [7] .

Küszöb gyűrűs aláírások

Ellentétben a szabványos "t-out-of-n" küszöb-aláírással , ahol n - ből t felhasználónak kell együttműködnie az üzenet visszafejtésében , ez a gyűrűs aláírás-változat megköveteli, hogy t felhasználó működjön együtt az aláírási folyamatban. Ehhez t résztvevőnek ( i 1 , i 2 , …, i t ) ki kell számítania az m üzenet σ aláírását úgy, hogy t privát és n nyilvános kulcsot ad a bemenethez ( m , S i 1 , S i 2 , … , S i t , P 1 , …, P n ) [8] .

Összekapcsolható gyűrűs aláírások

A kapcsolódási tulajdonság lehetővé teszi annak meghatározását, hogy két csengőaláírást ugyanaz a személy hozott-e létre (ugyanazt a privát kulcsot használták-e), de anélkül, hogy meghatározná, hogy ki. Az egyik lehetséges alkalmazás egy offline elektronikus pénzrendszer [9] lehet .

Nyomon követhető gyűrűs aláírás

A társított aláíráson kívül az aláíró nyilvános kulcsa is megjelenhet újrafelhasználáskor. Egy ilyen protokoll lehetővé teszi olyan titkos elektronikus szavazórendszerek megvalósítását , amelyek csak egy aláírás névtelenségét teszik lehetővé, de felfedik a kétszer szavazó résztvevőt [10] .

Kriptovaluták

A CryptoNote rendszer lehetővé teszi a gyűrűs aláírásokat [11] . Ezt először 2012 júliusában használták a Bytecoin [12] [13] kriptovalutában (nem tévesztendő össze a Bitcoinnal ).

A ShadowCash kriptovaluta nyomon követhető gyűrűs aláírást használ a tranzakció feladójának anonimizálására [14] . A kezdeti megvalósítás azonban hibás volt, ami a ShadowCash részleges anonimizálásához vezetett az első implementációtól 2016 februárjáig [15] .

Hatékonyság

A legtöbb javasolt algoritmus aszimptotikus eredménymérettel rendelkezik , azaz az eredményül kapott aláírás mérete egyenesen arányos a felhasznált nyilvános kulcsok számával. A csengőaláírás előírásakor vagy ellenőrzésekor használt nyilvános kulcsok mindegyike meghatározott mennyiségű számítást igényel, ami sokkal jobb, mint a protokoll létrehozásakor rendelkezésre álló analógok [1] . A CryptoNote technológia például csengőaláírásokat valósít meg a p2p fizetéseknél , hogy biztosítsa a feladó anonimitását [10] .

Az utóbbi időben hatékonyabb algoritmusok jelentek meg. Léteznek olyan sémák, amelyek szublineáris méretű aláírással rendelkeznek [16] , valamint állandó méretűek [17] .

Algoritmus

A Rivest, Shamir és Tauman által javasolt gyűrű aláírási algoritmus lényege a következő [1] (lásd az ábrát).

Egyes üzenetek csengőaláírása a nyilvános kulcsok listája alapján jön létre (az ábrán jelzéssel jelöljük ), amelyek között az aláíró kulcsának sorozatszáma van . A nyilvános kulcsok lehetővé teszik tetszőleges információ titkosítását ( a kulccsal titkosított információs blokk a diagramon jelöléssel van ellátva ). Az " információs blokkok " a továbbiakban nem részei vagy annak eredménye az aláírt üzenet, és nincs önálló jelentésük, véletlenszerűen generált adatok, amelyek az aláírás összetevőivé válnak.

Létezik tetszőleges számú argumentum kombinációs függvénye , amelyek értékével és az összes argumentum értékével, egy kivételével, egyedileg visszaállíthat egy hiányzó argumentumot. Ilyen függvény például a szekvenciális összegzés: ha a teljes összeg és egy kivételével minden tag ismert, akkor a hiányzó tag kiszámítható (az összes ismert tag értékével csökkentve a teljes összeget).

Kombinációs függvényként az algoritmus szerzői a következő műveletsort javasolták: egy bizonyos kezdőértéket veszünk (a diagramon feltüntetve , véletlenszerűen generálódik), amelyen és az első argumentum felett bitenkénti exkluzív „vagy” kerül végrehajtásra ( az ábrán a szimbólum jelzi ). Ezután egy bizonyos reverzibilis transzformációt alkalmazunk az eredményre (amelyet a diagramban jelölünk ), egy az egyhez az aláírandó üzenet hash összegéhez társítva . Az eredmény bitenkénti XOR-re kerül a második argumentummal, a konverzió újra alkalmazásra kerül, és így tovább. A megfelelő, nyilvános kulccsal titkosított információs blokkok argumentumként használatosak .

A kiválasztott véletlen érték a kombinációs függvény kezdő és cél (végső) értéke is: minden transzformáció eredményének „körbe kell kerülnie”, és egyenlővé kell válnia a kezdeti értékkel. Az egyes kulcsokhoz tartozó információs blokkok , kivéve az aláíró saját kulcsának megfelelő blokkot, véletlenszerű értékként vannak megadva. Az aláíró titkosítja az információs blokkokat a megfelelő nyilvános kulcsokkal. Az aláíró most már rendelkezik a kombinációs függvény célértékével és egy kivételével az összes argumentummal, amely a saját kulcsának felel meg. A kombinációs függvény tulajdonságainak köszönhetően az aláíró megtudhatja a hiányzó argumentumot, és saját privát kulcsával ( ) „dekódolja” ezt az argumentumot ( ), megszerezve a hiányzó információs blokkot .

A kész gyűrűs aláírás összetevői [1] :

Az aláírás ellenőrzéséhez [1] szükséges :

Megvalósítási példa

Példaként egy RSA -kulcsokat használó alapalgoritmus Python -megvalósítását mutatjuk be .

import os import hashlib import véletlenszerű import Crypto.PublicKey.RSA osztály Gyűrű : def __init__ ( self , k , L = 1024 ): self . k = k self . l = L self . n = len ( k ) én . q = 1 << ( L - 1 ) def jel ( self , m , z ): én . permut ( m ) s = [ Nincs ] * self . u = véletlenszerű . _ randint ( 0 , saját . q ) c = v = self . E ( u ) i - re in ( tartomány ( z + 1 , saját . n ) + tartomány ( z )): s [ i ] = véletlenszerű . randint ( 0 , self . q ) e = self . g ( s [ i ] , én . k [ i ] . e , én . k [ i ] . n ) v = én . E ( v ^ e ) ha ( i + 1 ) % self . n == 0 : c = v s [ z ] = saját . g ( v ^ u , saját . k [ z ] . d , saját . k [ z ] . n ) return [ c ] + s def verify ( self , m , X ): self . permut ( m ) def _f ( i ): önmagát adja vissza . g ( X [ i + 1 ], self . k [ i ] . e , self . k [ i ] . n ) y = térkép ( _f , tartomány ( len ( X ) - 1 )) def _g ( x , i ) : visszaadja önmagát . E ( x ^ y [ i ]) r = csökkenti ( _g , tartomány ( self . n ), X [ 0 ]) return r == X [ 0 ] def permut ( self , m ): én . 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

2 üzenet aláírása és ellenőrzése 4 felhasználó gyűrűjével:

size = 4 msg1 = 'helló' msg2 = 'világ!' def _rn ( _ ): visszaadja a Crypto -t . PublicKey . R.S.A. _ generál ( 1024 , os . urandom ) kulcs = térkép ( _rn , tartomány ( méret )) r = Gyűrű ( kulcs ) for i tartományban ( méret ) : s1 = r . jel ( msg1 , i ) s2 = r . jel ( msg2 , i ) assert r . verify ( msg1 , s1 ) és r . verify ( msg2 , s2 ) és nem r . ellenőrzés ( msg1 , s2 )

Jegyzetek

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. Hogyan szivárogtassunk ki egy titkot  // Advances in Cryptology - ASIACRYPT 2001 / C. Boyd (szerk.). - Berlin, Heidelberg: Springer-Verlag , 2001. - P. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
  2. ↑ I. Yu. Pavlovskaya . A beszéd fonoszemantikai elemzése. - Szentpétervár. : St. Petersburg University Publishing House, 2001. - 290 p.
  3. ↑ Historical Dictionary of the Spanish American War / Donald H. Dyal, Brian B. Carpenter és Mark A. Thomas, szerk. – Westport, Conn.: Greenwood Press , 1996.
  4. ↑ B. Schneier . Alkalmazott kriptográfia  . - New York: John Wiley & Sons , 1996. - 98. o.
  5. ↑ Debnath A., Singaravelu P., Verma, S. Efficient spatial privacy protection system for sensor network // Central European Journal of Engineering . - 2013. - Kt. 3, sz. 1. - P. 1-10. - doi : 10.2478/s13531-012-0048-7 .
  6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. A gyűrűs aláírás felmérése // Az elektromos és elektronikai tervezés határai Kínában. - 2008. - Vol. 3, sz. 1. - P. 10-19. - doi : 10.1007/s11460-008-0012-8 .
  7. ↑ Hu Xiong, Zhiguang Qin, Fagen Li. A gyűrűs aláírási sémák taxonómiája: elmélet és alkalmazások // IETE Journal of Research. - 2013. - Kt. 59, sz. 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, ​​Hongkong, London, Milánó, Párizs, Tokió: 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 Összekapcsolható gyűrűs aláírások: Biztonsági modellek és új sémák // Számítástechnika és alkalmazásai - ICCSA 2005. - Berlin; New York: Springer, 2005. évf. 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 // Nyilvános kulcsú kriptográfia - PKC 2007. - Berlin; Heidelberg; New York: Springer, 2007. - 181-200. - ( Lecture Notes in Computer Science . Vol. 4450).
  11. ↑ CryptoNote filozófia . CryptoNoteTech. Letöltve: 2017. november 24. Az eredetiből archiválva : 2017. november 24..
  12. ↑ CryptoNote pénznemek  (angol) (2015). Letöltve: 2017. november 29. Az eredetiből archiválva : 2017. július 13.
  13. ↑ A CryptoNote Bitcoin-gyilkos? (2014. június 23.). Letöltve: 2017. november 29. Az eredetiből archiválva : 2017. december 1..
  14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash Traceable Ring Signatures  (angol) (pdf)  (hivatkozás nem érhető el) . www.shadow.cash (2015). Az eredetiből archiválva : 2017. december 1.
  15. ↑ Crypto Fun. Broken Crypto in Shadowcash  (angol)  (nem elérhető link) (2016.02.13.). Letöltve: 2017. november 29. Az eredetiből archiválva : 2016. szeptember 27..
  16. ↑ Fujisaki E. Sublinear size traceable ring signatures without random oracle // Topics in Cryptology - CT-RSA 2011. - Heidelberg; Dordrecht; London; 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. Állandó méretű, azonosító alapú linkelhető és visszavonható iff-kapcsolt gyűrűs aláírás // Progress in Cryptology - INDOCRYPT 2006. - Heidelberg; Dordrecht; London; New York: Springer, 2006. – 364-378. o. - ( Lecture Notes in Computer Science . Vol. 4329).

Irodalom

  Ugrás a Wikidata elemre  Szótárak és enciklopédiák
 Nyilvános kulcsú kriptorendszerek
Algoritmusok
Egész számok faktorizálása
Diszkrét logaritmus
Kriptográfia rácsokon
Egyéb
Elmélet
Szabványok
Témák