Schnorr hitelesítési protokoll
A kriptográfiában a Schnorr (in) hitelesítési protokoll (gyakran rövidítve Schnorr protokoll ) egy nulla ismeretelméleti bizonyíték, amelyet Schnorr írt le 1989-ben, és amelynek biztonsága a diszkrét logaritmus problémájának nehézségére támaszkodik, és egy diszkrét logaritmus ismeretének bizonyítására szolgál, azaz adott , bizonyítsa be, hogy ismerjük a kitevőt egy által generált csoportban .
gnál nél{\ displaystyle g ^ {a}}nál nél{\ displaystyle a} G{\ displaystyle G}g{\ displaystyle g}
Ez a protokoll digitális aláírássá alakítható, ha a bizonyítást nem interaktívvá teszi a Fiat-Shamir heurisztika . Ez a digitális aláírás rendszerének ben szabadalmaztatta az Egyesült Államok mellett US Patent 4995082 lejárt2008. február.
A többi nulla tudású bizonyításhoz hasonlóan Schnorr protokollja Σ protokoll: két P és V interaktív algoritmus (a Prover és a Verifier számára) protokoll három fázisban: elkötelezettség, kihívás és válasz.
Nyilvános beállítások
- A prime szám . Megjegyezzük, hogy ez határozza meg egy megbízás csoport által generált , jelöljük szorzás a következő.q{\ displaystyle q}G{\ displaystyle G}q{\ displaystyle q}g{\ displaystyle g}
- Csoportjának egy elemét , a rend Ez a generátor egy alcsoportja érdekében ag{\ displaystyle g}q.{\ displaystyle q.}q{\ displaystyle q}G{\ displaystyle G}
-
q,g{\ displaystyle q, g} nyilvánosak.
Csak a közmondás által ismert adatok
- Véletlen egész szám a .s{\ displaystyle s}Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}
- A Prover kiszámítja és nyilvánosságra hozza, megbízható hatóság tanúsítja , miközben titokban tartják.v=gs{\ displaystyle v = g ^ {s}}v{\ displaystyle v}s{\ displaystyle s}
Először P indít egy elköteleződési lépést:
-
P véletlenszerűen egész számot von le .r{\ displaystyle r}Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}
-
P kiszámítja , és elküldi a VR=gr{\ displaystyle R = g ^ {r}}R{\ displaystyle R}
Ezután kezdődik a kihívás fázisa:
-
V húz egy egész szám a , és megküldi azt a Pvs.{\ displaystyle c}Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}
Végül a válaszfázis:
-
P kiszámítja és elküldi V-nek .nál nél=r-vs.⋅s{\ displaystyle a = rc \ cdot s}
V akkor és csak akkor fogadja el, ha a protokoll végén ellenőrzik a kapcsolatot .
R=gnál nél⋅vvs.{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}
Biztonsági bizonyítékok
A protokoll biztonságának igazolásához elegendő a teljesség, a különleges robusztusság és a tudástulajdon őszinte hitelesítő általi nyilvánosságra hozatalának bizonyítása.
Teljesség
A teljesség (vagy javítás) megköveteli, hogy a protokoll őszinte menetéhez az ellenőr mindig elégedett legyen.
Ezt igazolja a V elfogadási feltétele, amely ezt megadja , amelyet mindig ellenőriznek, ha a protokollt őszintén hajtották végre.
gnál nél⋅vvs.=gr-vs.⋅s⋅gs⋅vs.=gr=R{\ displaystyle g ^ {a} \ cdot v ^ {c} = g ^ {rc \ cdot s} \ cdot g ^ {s \ cdot c} = g ^ {r} = R}
Különleges robusztusság
A speciális robusztusság azt mondja, hogy van egy tudás páraelszívó , hogy működik a polinomiális megadott két elfogadó átiratokat és ugyanolyan állami paramétereket, akkor az elszívó visszatér a titkos .
(R,vs.,nál nél){\ displaystyle (R, c, a)}(R,vs.′,nál nél′){\ displaystyle (R, c ', a')}s{\ displaystyle s}
Ez az extraktor a következőképpen épül fel a Schnorr protokoll esetében: kiszámít és visszatér , mert ez az érték megfelel a par diszkrét logaritmusának . Valójában az átírások és elfogadói viszonyok és a kapcsolatok ellenőrzése megtörtént, így adva azóta .
nál nél-nál nél′vs.′-vs.{\ displaystyle {\ frac {a-a '} {c'-c}}}v{\ displaystyle v}g{\ displaystyle g}(R,vs.,nál nél){\ displaystyle (R, c, a)}(R,vs.′,nál nél′){\ displaystyle (R, c ', a')}R=gnál nél⋅vvs.{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}R=gnál nél′⋅vvs.′{\ displaystyle R = g ^ {a '} \ cdot v ^ {c'}}g(nál nél-nál nél′vs.′-vs.)=v{\ displaystyle g ^ {\ balra ({\ frac {a-a '} {c'-c}} \ jobbra)} = v}vs.≠vs.′{\ displaystyle c \ not = c '}
Az ismeretek nyilvánosságra hozatala becsületes hitelesítő alatt
Ez a tulajdonság jellemzi, hogy létezik egy valószínűségi szimulátor működő polinomiális időben , amely adott , ahol eloszlik, mint egy megfelelő kihívást, akkor a szimulátor visszatér transzkripciós elosztva, mint egy igazi átírás . Vegye figyelembe, hogy a szimulátornak nincs szüksége titoktartásra.
(v,vs.){\ displaystyle (v, c)}vs.{\ displaystyle c}(R,vs.,nál nél){\ displaystyle (R, c, a)}v{\ displaystyle v}
Itt tehát a szimulátor az elkötelezettség előtt generálja a választ: egységesen behúzódik és generál , hogy ellenőrizze az elfogadási feltételt, vagyis visszatérjen . Észrevehetjük, hogy egyenletesen oszlik el, mivel az alapja szerinti diszkrét logaritmusa az. Az építkezés pedig elfogadó válaszként oszlik meg .
nál nél{\ displaystyle a}Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}R{\ displaystyle R}R=gnál nél⋅vvs.{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}(R,vs.,nál nél){\ displaystyle (R, c, a)}R{\ displaystyle R}g{\ displaystyle g}nál nél{\ displaystyle a}(R,vs.){\ displaystyle (R, c)}
Paraméter mérete
A szabadalmi leírás azt jelzi, hogy a csoportot egy olyan csoport legalább 140 bites alcsoportjaként kell megválasztani, ahol a 72 bites biztonság 512 bites prímszáma.
G{\ displaystyle G}Zo{\ displaystyle \ mathbb {Z} _ {p}}o{\ displaystyle p}
Aláírási séma
A Fiat-Shamir heurisztika felhasználható az azonosítási séma digitális aláírássá alakítására .
Ehhez egy kriptográfiai (család) hash függvényt vezetnek be a nyilvános paraméterekbe, és a kihívás időpontjában a véletlenszerű kiválasztását helyettesíti az értékelés, amely megfelel az aláírandó üzenetnek. Az aláírás megfelel a házaspárnak ; a hitelesítéskor újraszámolják, mivel a hitelesítő teszteli, és elfogadja-e, ha ez a hitelesítés sikeres. A teljes leírást az alábbiakban adjuk meg.
H:G×{0,1}∗→Zq⋆{\ displaystyle {\ mathcal {H}}: G \ szor \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ star}}vs.{\ displaystyle c}vs.←H(R,m){\ displaystyle c \ kap {\ mathcal {H}} (R, m)}m∈{0,1}∗{\ displaystyle m \ in \ {0,1 \} ^ {*}}(vs.,nál nél){\ displaystyle (c, a)}R{\ displaystyle R}R′=gnál nél⋅vvs.{\ displaystyle R '= g ^ {a} \ cdot v ^ {c}}H(R′,m)=vs.{\ displaystyle {\ mathcal {H}} (R ', m) = c}
Leírás
A digitális aláírást algoritmusok hármasa adja (GenClefs, Signer, Verify) .
Kulcsgenerálás:
- A nyilvános paramétereket ( és ) ugyanúgy generálják, mint a Σ protokollhoz.q{\ displaystyle q}g{\ displaystyle g}
- Ezután egy hash függvény jön létre és hozzáadódik a nyilvános paraméterekhez.H:G×{0,1}∗→Zq⋆{\ displaystyle {\ mathcal {H}}: G \ szor \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ star}}
- Egy kulcspár (vk, sk) generálásához ( v az ellenőrzéshez és az s az aláíráshoz) az aláíró azzal kezdi, hogy egyenletesen meghúzza a számot , és titkos kulcsként fogja meghatározni.s∈Zq⋆{\ displaystyle s \ in \ mathbb {Z} _ {q} ^ {\ star}}
- Ezután az aláíró kiszámítja és közzéteszi nyilvános kulcsaként.v=gs{\ displaystyle v = g ^ {s}}
Aláírás ( sk, m ):
- Üzenet aláírásához az aláíró egy véletlen szám megrajzolásával kezdi és meghatározza .r∈Zq⋆{\ displaystyle r \ in \ mathbb {Z} _ {q} ^ {\ star}}R=gr{\ displaystyle R = g ^ {r}}
- A "kihívás" ekkor generálódik , és a válasz kiszámítása .vs.=H(R,m){\ displaystyle c = {\ mathcal {H}} (R, m)}nál nél=r-vs.⋅sk∈Zq{\ displaystyle a = rc \ cdot {\ mathsf {sk}} \ in \ mathbb {Z} _ {q}}
- Végül az aláírás vissza: .σ=(vs.,nál nél){\ displaystyle \ sigma = (c, a)}
Ellenőrzés ( vk, m, σ ):
- Aláírásának ellenőrzésére , a felhasználó először újraszámolja a nyilvános kulcs: .σ=(vs.,nál nél){\ displaystyle \ sigma = (c, a)}R{\ displaystyle R}R′=gnál nél⋅vkvs.{\ displaystyle R '= g ^ {a} \ cdot {\ mathsf {vk}} ^ {c}}
- A felhasználó akkor és csak akkor fogadja el .H(R′,m) =? vs.{\ displaystyle {\ mathcal {H}} (R ', m) ~ {\ overset {?} {=}} ~ c}
Hatékonyság
Ennek eredményeként az aláírás mérete megfelel a minimális szabadalmi ajánlásoknak a 72 bit biztonságra vonatkozóan.
|vs.|+|nál nél|=280 bitek=35 bájtokat{\ displaystyle | c | + | a | = 280 {\ mbox {bits}} = 35 {\ mbox {bájt}}}
Bizonyított biztonság
Pointcheval és Stern 1996-ban kimutatták, hogy a Fiat-Shamir heurisztika biztonságos a véletlenszerű orákulum modellben, ha az alapul szolgáló azonosítási séma biztonságos.
Megjegyzések és hivatkozások
-
Schnorr 1989 .
-
Feige, Fiat és Shamir 1988 .
-
Fiat és Shamir 1986 .
-
Damgård 2010 .
-
Pointcheval és Stern 1996 .
Függelékek
Bibliográfia
- [Feige Fiat és Shamir 1988] (en) Uriel Feige, Amos Fiat és Adi Shamir , „ Az identitás nulla ismeretének igazolása ” , Journal of Cryptology ,1988( DOI 10.1007 / BF02351717 )
- [Fiat és Shamir 1986] (en) Amos Fiat és Adi Shamir , „ Hogyan igazolhatjuk magunkat: gyakorlati megoldások az azonosítási és aláírási problémákra ” , Crypto 1986 ,1986( olvasható online [PDF] )
- [Schnorr 1989] (en) Claus-Peter Schnorr , „ Hatékony azonosítás és aláírás az intelligens kártyák számára ” , A kriptológia elmélete és alkalmazása , Springer,1989( online olvasás )
- [Pointcheval és Stern 1996] (en) David Pointcheval és Jacques Stern , " Biztonsági igazolások az aláírási rendszerekhez " , Eurocrypt ,1996( olvasható online [PDF] )
Kapcsolódó cikkek
Külső linkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">