Helló, Habr!
A A cikkben megvitatjuk, hogy miért lehet szükséges véletlenszámokat generálni olyan résztvevők számára, akik nem bíznak meg egymásban, milyen követelményeket támasztanak az ilyen véletlenszám-generátorokkal szemben, és két megközelítést vizsgálunk a megvalósításukhoz.
A cikk ezen részében részletesen megvizsgálunk egy másik megközelítést, amely küszöb-aláírásokat használ.
Néhány alapvető kriptográfia
Ahhoz, hogy megértsük, hogyan működnek a küszöb-aláírások, kicsit értenünk kell az alapvető kriptográfiához. Két fogalmat fogunk használni: skalárokat, vagyis egyszerűen számokat, amelyeket kisbetűkkel (x, y) és pontokat az elliptikus görbén, amelyeket nagybetűkkel fogunk megjelölni.
A küszöb-aláírások alapjainak megértéséhez nem szükséges tudni, hogyan működnek az elliptikus görbék, csak néhány alapvető dolgot kell tudni:
Az elliptikus görbén lévő pontokat össze lehet adni és skalárral szorozni (a skalárral való szorzást így fogjuk jelölni: xG, bár a Gx jegyzés is gyakran előfordul a szakirodalomban). Az összegzés és a skalárral való szorzás eredménye egy pont az elliptikus görbén.
Csak a pont ismerete, G és annak skalárral való szorzata xG nem teszi lehetővé a kiszámítást. x.
Használni fogjuk a polinom fogalmát is p(x) fokú k-1. Különösen a polinomok alábbi tulajdonságát fogjuk használni: ha tudjuk a p(x) értékét bármilyen k különböző x (és nincs más információnk a p(x)), képesek vagyunk kiszámítani a p(x) bármely más x.
értekét. p(x) Érdekes, hogy bármely polinomra Gés egy adott pontra a görbén, ha tudjuk a p(x)G értékét bármilyen k különböző értékeit, azt is ki lehet számítani, hogy xmilyen értéke lesz p(x)G bármelyik x.
. Ezen információ elegendő ahhoz, hogy belemerüljünk a küszöb-aláírások működésének részleteibe, és hogy hogyan lehet őket felhasználni véletlenszámok generálására.
Küszöb-aláírás alapú véletlenszám-generátor
Tegyük fel, hogy a résztvevők véletlenszámot akarnak generálni, és azt szeretnénk, hogy bármelyikük részvétele elegendő legyen a szám generálásához, de a támadók, akik -1 vagy kevesebb résztvevőt irányítanak, ne tudják megjósolni vagy befolyásolni a generált számot. n Tegyük fel, hogy létezik egy polinom k -1, amit az első résztvevő ismer kp(1),
a második ismeri p(x) fokú kp(2), és így tovább (-ik tudja p(n)). Azt is feltételezzük, hogy egy meghatározott pontban mindenki tudjanminden értékét. Ezt hívjukmindenki ismeri G az összes értékét p(x)G . Ezt nevezzük xAzt fogjuk mondani p(i) „privát komponens“ i-dik résztvevő (mivel csak i-ik résztvevő ismeri azt), és p(i)G „nyilvános komponens“ i-dik résztvevő (mivel minden résztvevő ismeri azt). Ahogy emlékezhet, a tudás p(i)G nem elegendő a helyreállításhoz p(i).
Olyan polinom létrehozása, hogy csak i--ik résztvevő és senki más tudja a saját privát komponensét – ez a protokoll legnehezebb és legérdekesebb része, és ezt alább tárgyaljuk. Jelenleg feltételezzük, hogy ilyen polinomunk van, és minden résztvevő ismeri a saját privát komponenseit.
Hogyan használhatjuk ezt a polinomot véletlen szám generálására? Először is szükségünk van egy olyan sztringre, amely korábban még nem szolgált belépőként a generátor számára. A blokklánc esetében az utolsó blokk hash-e h – jó jelölt erre a sztringre. Tegyük fel, hogy a résztvevők véletlen számot szeretnének létrehozni, használva h seed-ként. Először a résztvevők h bepontozzák
H = scalarToPoint(h)
Ezután minden résztvevő i kiszámítja és közzéteszi Hi = p(i)H, amit megtehetnek, mert ismerik p(i) és H. A felfedés Hi nem engedi meg a többi résztvevőnek, hogy helyreállítsa a privát komponenst i-dik résztvevő, így egy készlet privát komponens felhasználható blokkról blokkra. Így a lent leírt polinom létrehozási algoritmust csak egyszer kell végrehajtani.
Amikor k a résztvevők felfedték Hi = p(i)H, mindenki kiszámíthatja Hx = p(x)H mindenki számára x a polinomok tulajdonságai miatt, amelyeket a múltbeli fejezetben tárgyaltunk. Ebben a pillanatban minden résztvevő kiszámítja H0 = p(0)H, és ez az eredményül kapott véletlen szám. Vegye figyelembe, hogy senki sem tudja p(0), ezért az egyetlen módja annak, hogy kiszámítsuk p(0)H – az interpoláció p(x)H, ami csak akkor lehetséges, ha k az értékek p(i)H ismertek. Bárminemű kisebb mennyiség felfedése p(i)H nem ad információt p(0)H-hoz.
A fenti generátor rendelkezik minden olyan tulajdonsággal, amelyet szeretnénk: a támadók, akik csak k-1 résztvevőt, vagy kevesebb mint ők, semmilyen információval és hatással nincsenek a kimenetre, míg bármelyik k résztvevő kiszámíthatja az eredményül kapott számot, és bármilyen alkészlet a k résztvevőkből mindig ugyanahhoz az eredményhez jut a megfelelő seed esetén.
Van egy probléma, amit óvatosan kikerültünk az előbbiekben. Az interpolációnak működnie kell, fontos, hogy az érték Hi, amelyet minden résztvevő közzétett i valójában egyenlő legyen p(i)H. Mivel senki más i-tól résztvevő nem tudja p(i), senki más i--tól résztvevő nem ellenőrizheti, hogy Hi valóban helyesen lett kiszámítva, és valamilyen kriptográfiai bizonyíték nélkül, Hi, a támadó bármilyen értéket közzétehet mint Hi, és önkényesen befolyásolhatja a véletlenszám-generátor kimenetét.:
A különböző H_1 értékek, amelyeket az első résztvevő küldött, különböző H_0 eredményekhez vezetnek.
Minimum két módja van a helyesség bizonyításának Hi, ezeket megvizsgáljuk, miután átbeszéltük a polinomszámlálást.
Polinomszámlálás
Az előző részben feltételeztük, hogy van egy olyan polinomunk, p(x) fokú k-1 amelyet a résztvevő i tudja p(i), és senki más nem tud semmilyen információval rendelkezni erről az értékről. A következő részben szükséges, hogy egy előre meghatározott pontban G mindenki tudja, p(x)G mindenki számára x.
Ebben a részben azt fogjuk feltételezni, hogy minden résztvevő helyben rendelkezik egy privát kulccsal, xi, így a megfelelő nyilvános kulcs mindenki számára ismert Xi.
Egy lehetséges polinomszámlálási protokoll a következő:
Minden résztvevő i helyben létrehoz egy tetszőleges polinomot pi(x) k-1 fokon. Ezt követően minden résztvevőnek j értéket pi(j), a nyilvános kulccsal titkosítva Xj. Így csak i-j- és tól résztvevő tudjaj- i(j). A résztvevő pnyilvánosan bejelenti i pi(j)G beleértve. mindenki számára j tól 1 tól k Minden résztvevő egy konszenzust használ, hogy kiválassza
azokat a résztvevőket, akiknek polinomait felhasználják. Mivel egyes résztvevők offline lehetnek, nem várhatjuk meg, hogy minden k résztvevő közzétegye a polinomját. Ennek a lépésnek az eredménye – egy halmaz n amely legalább Z polinomot tartalmaz, amelyek az (1) lépésben készültek. k A résztvevők meggyőződnek arról, hogy a nyilvánosan bejelentett.
pi(j)G-hez ismert értékek pi(j) megfelelnek. E lépés után a csak azok a polinomok maradnak, amelyekhez priváton átadott Z kiszámítja a privát komponensét pi(j) megfelelnek. E lépés után a
Minden résztvevő j p(j) mint az összeg i(j) mindenki számára. pA résztvevők emellett kiszámítják az összes értéket i be. Zpi(x)G minden i-hez. p(x)G i(j) mindenki számára. Kérjük, vegye figyelembe, hogy be. Z.
p(x) – valójában egy k-1 fokú polinom, mivel ez az egyes i(x) összegéből származik, mindegyik fokú polinom. mivel ez az egyes pi(x) polinomok összegéből áll. k-1. Ezután vegye figyelembe, hogy míg minden résztvevő j tudja p(j), nincs információjuk a p(x) a x ≠ j. Valójában ahhoz, hogy ezt az értéket kiszámítsák, szükségük van arra, hogy tudják az összes pi(x), és amíg a résztvevő j nem tud legalább egy kiválasztott polinomot, nincs elegendő információjuk a p(x)-ról.
Ez az egész polinomgenerálási folyamat, amely a korábbi részben szükséges volt. Az 1., 2. és 4. lépéseknek nyilvánvaló megvalósítása van. A 3. lépés azonban nem annyira triviális.
Konkrétan bizonyítanunk kell, hogy a titkosított pi(j) valóban megfelel a közzétett E lépés után a Ha nem tudjuk ezt bizonyítani, a támadó i küldhet szemét a pi(j) résztvevőnek, jés a résztvevő j nem tudja megkapni a valódi értéket pi(j), és nem fogja tudni kiszámítani a saját privát komponensét..
Van egy kriptográfiai protokoll, amely lehetővé teszi egy további üzenet proofi(j) létrehozását, amely lehetővé teszi, hogy bármely résztvevő, akinek van egy értéke e, valamint proofi(j) és pi(j)G, helyben ellenőrizhesse, hogy e – ez valóban pi(j), a résztvevő j kulcsával titkosított. Sajnos az ilyen bizonyítékok mérete hihetetlenül nagy, és figyelembe véve, hogy O(nk) ilyen bizonyítékokat kell közzétenni, nem lehet őket erre a célra használni.
Ahelyett, hogy bizonyítanánk, hogy pi(j) megfelel pi(j)G, a polinom generálási protokoll során nagyon hosszú időt tölthetünk, amely alatt minden résztvevő ellenőrzi a kapott titkosított pi(j), és ha a dekódolt üzenet nem felel meg a nyilvános pi(j)G-nek, közzéteszik a kriptográfiai bizonyítékot, hogy a kapott titkosított üzenet téves. Bizonyítani, hogy az üzenet nem megfelel pi(G) sokkal egyszerűbb, mint bizonyítani, hogy az megfelel. Meg kell jegyezni, hogy ez megköveteli, hogy minden résztvevő legalább egyszer megjelenjen a hálózatban azokon az időkereteken belül, amelyek az ilyen bizonyítékok létrehozására vannak fenntartva, és azt a feltevést követeli meg, hogy ha közzétették ezt a bizonyítékot, az eljut a többi résztvevőhöz is ugyanebben az időkeretben.
Ha egy résztvevő nem jelent meg a hálózatban ezen idő alatt, és valóban volt legalább egy hibás komponense, akkor ez a konkrét résztvevő nem tud részt venni a további számok generálásában. A protokoll azonban továbbra is működni fog, ha van legalább k résztvevők, akik vagy csak megkapták a helyes összetevőket, vagy sikerült bizonyítaniuk a helytelenséget a megadott időn belül.
A H_i helyességének bizonyítékai
Az utolsó rész, amelyet meg kell vitatni, az az, hogyan lehet bizonyítani a közzétett Hi, nevezetesen, hogy Hi = p(i)H, feltárás nélkül p(i).
Emlékezzünk vissza, hogy az értékek H, G, p(i)G nyilvánosak és mindenki számára ismertek. A megszerzés folyamata p(i) ismerve p(i)G és G diszkrét logaritmusnak vagy dlog-nak nevezik, és bizonyítani szeretnénk, hogy:
dlog(p(i)G, G) = dlog(Hi, H)
felfedés nélkül. p(i)Az ilyen bizonyítékok konstrukciói léteznek, például a.
Ilyen konstrukcióval minden résztvevő együtt, Hi küldi a helyességi bizonyítékot a konstrukciónak megfelelően.
Amikor a véletlenszámot generálják, azt gyakran más résztvevőknek is el kell küldeni, nem csak azoknak, akik generálták. Ezeknek a résztvevőknek együtt a számmal minden Hi és a kapcsolódó bizonyítékokat el kell küldeni.
A kíváncsi olvasó megkérdezheti: mivel a végső véletlenszám – ez H0, és p(0)G – ez egy nyilvános információ, miért szükséges a bizonyíték minden egyes Hi-re, miért nem küldünk inkább bizonyítékot arról, hogy
dlog(p(0)G, G) = dlog(H0, H)
A probléma az, hogy a Schnorr protokollal nem lehet ilyen bizonyítékot létrehozni, mert senki sem ismeri a p(0) értékét,amely szükséges a bizonyíték létrehozásához, és ami még fontosabb, az egész véletlenszám-generátor azon alapul, hogy senki sem ismeri ezt az értéket. Ezért szükséges, hogy minden értéket Hi és az egyedi bizonyítékokat együttesen bemutassuk a helyesség bizonyításához. H0.
Viszont, ha az elliptikus görbék pontjain lenne valamilyen művelet, amely szemantikailag hasonlít a szorzásra, akkor a helyesség bizonyítása H0 triviális lenne, egyszerűen csak biztosítanánk, hogy
H0 × G = p(0)G × H
Ha a választott görbe támogatja az akkor ilyen bizonyíték működik. Ebben az esetben H0 – ez nemcsak a véletlenszám-generator kimenete, amit bármely résztvevő ellenőrizhet, aki ismeri G, H, és p(0)G. H0 – ez egy üzenet aláírása is, amelyet a seedként használtak, megerősítve, hogy k és n a résztvevők aláírták ezt az üzenetet. Így, ha seed – ez egy blokk hash a blokklánc protokollban, akkor H0 ez egyidejűleg több aláírás a blokkra, és egy nagyon jó véletlenszám.
Végül
Ez a cikk a blogon található technikai cikkek sorozatának része. . NEAR – egy blokklánc protokoll és platform decentralizált alkalmazások fejlesztésére, amely a fejlesztés egyszerűségére és a végfelhasználók számára a használat egyszerűségére helyezi a hangsúlyt.
A protokoll kódja nyílt forráskódú, a megvalósításunk Rust nyelven íródott, és megtalálható itt .
Megnézheti, hogyan néz ki a NEAR fejlesztése, és kísérletezhet az online IDE-ben .
Minden hír követhető oroszul a és a , angolul pedig a hivatalos .
Hamarosan találkozunk!
Forrás: habr.com
