Schnorr-séma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 2-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Schnorr séma az egyik leghatékonyabb és elméletileg megalapozott hitelesítési séma . Az áramkör biztonsága a diszkrét logaritmusok kiszámításának nehézségén alapszik . A Klaus Schnorr által javasolt séma az ElGamal (1985) és a Fiat-Shamir (1986) sémák módosítása , de kisebb aláírásmérettel rendelkezik. A Schnorr-séma a Fehérorosz Köztársaság STB 1176.2-99 szabványa, valamint a dél-koreai KCDSA és EC-KCDSA szabványok alapja. A 4 999 082 számú amerikai szabadalom lefedte , amely 2008 februárjában járt le.

Bevezetés

A hitelesítési és elektronikus aláírási sémák az információ integritását biztosító kriptográfiai protokollok egyik legfontosabb és leggyakoribb típusa.

A hitelesítési protokollok célja könnyen érthető a következő példából. Tegyük fel, hogy van egy információs rendszerünk, amelyben meg kell különböztetni a különféle adatokhoz való hozzáférést. Ebben a rendszerben is van egy adminisztrátor, aki az összes felhasználói azonosítót tárolja a hozzá tartozó jogosultságokkal, amelyek segítségével megkülönböztethető az erőforrásokhoz való hozzáférés. Egy felhasználónak egyszerre engedélyezhető egy fájl elolvasása, a második módosítása, és egyidejűleg megtagadható a hozzáférés a harmadikhoz. Ebben a példában az információk integritásának biztosítása azt jelenti, hogy megakadályozzuk a rendszerhez való hozzáférést olyan személyek számára, akik nem annak felhasználói, valamint megakadályozzuk, hogy a felhasználók hozzáférjenek azokhoz az erőforrásokhoz, amelyekre nincs jogosultságuk. A legelterjedtebb hozzáférés-szabályozási módszer, a jelszavas védelem számos hátránnyal rendelkezik, ezért térjünk át a probléma kriptográfiai megfogalmazására.

A protokollnak két résztvevője van - Alice, aki meg akarja erősíteni a személyazonosságát, és Bob, akinek ellenőriznie kell ezt a megerősítést. Alice-nek két kulcsa van , egy nyilvános (nyilvános) és egy privát (privát) kulcsa, amelyet csak Alice ismer. Valójában Bobnak csak a használatával kell ellenőriznie, hogy Alice ismeri-e a privát kulcsát . $\mathrm {K} _{1}$ ${\displaystyle \mathrm {K} _{2))$ ${\displaystyle \mathrm {K} _{2))$ $\mathrm {K} _{1}$

A Schnorr-séma az egyik leghatékonyabb a gyakorlati hitelesítési protokollok között, amely ezt a feladatot valósítja meg. Minimálisra csökkenti az üzenet aláírásának létrehozásához szükséges számítások függőségét. Ebben a sémában a fő számításokat a processzor tétlensége közben lehet elvégezni, ami lehetővé teszi az aláírás sebességének növelését. A DSA -hoz hasonlóan Schnorr séma egy rendelési alcsoportot használ a -ban . Ez a módszer hash függvényt is használ . $q$ $\mathbb {Z} _{p}^{*}$ ${\displaystyle h:\{0,1\}^{*}\to \mathbb {Z} _{p))$

Kulcsgenerálás

A Schnorr aláírási séma kulcsgenerálása ugyanaz, mint a DSA kulcsgenerálása , kivéve, hogy nincsenek méretkorlátozások. Vegye figyelembe azt is, hogy a modulus önállóan is kiszámítható. $p$

Egy prímszámot választunk, amely általában bitekkel egyenlő . $p$ $1024$
Egy másik prímszámot választunk úgy, hogy az osztója legyen . Vagy más szóval, meg kell tenni . A bitekkel egyenlő szám méretét szokás választani . $q$ $p-1$ $p-1\equiv 0{\pmod {q))$ $q$ $160$
Válasszon egy számtól eltérő számot úgy, hogy . $g$ $egy$ $g^{q}\equiv 1{\pmod {p))$
Peggy egy nál kisebb véletlenszerű egész számot választ . $w$ $q$
Peggy kiszámolja . $y=g^{qw}{\pmod {p))$
Peggy nyilvános kulcsa , Peggy privát kulcsa . ${\megjelenítési stílus (p,q,g,y)}$ $w$

Hitelesítési protokoll

Protokollműveleti algoritmus

Előfeldolgozás . Alice kiválaszt egy véletlenszámot , amely kisebb, mint , és kiszámítja . Ezek a számítások előzetesek, és jóval Bob érkezése előtt elvégezhetők. $r$ $q$ $x=g^{r}{\pmod {p}}$
Megindítás, inicializálás. Alice elküldi Bobnak. $x$
Bob kiválaszt egy véletlen számot , és elküldi Alice-nek. $e$ $0$ $2^{t}-1$
Alice kiszámolja és elküldi Bobnak. $s=r+we{\pmod {q))$ $s$
Megerősítés. Bob ellenőrzi $x=g^{s}y^{e}{\pmod {p}}$

Az algoritmus biztonsága a t paramétertől függ . Az algoritmus megnyitásának bonyolultsága megközelítőleg egyenlő . Schnorr azt tanácsolja , hogy 72 bit körüli t -t használjon, és esetén . A diszkrét logaritmus probléma megoldásához ebben az esetben legalább az ismert algoritmusok lépései szükségesek. $2^{t}$ $p\geq 2^{512}$ $q\geq 2^{140}$ $2^{{72}}$

Példa

Kulcsgenerálás:

Prím és prím kiválasztása ( ) $p=48731$ $q=443$ $q|p-1$
Ebben az esetben a feltételből számítva $g$ $g^{q}=1{\pmod {p}}$ $g=11444$
Alice kiválaszt egy privát kulcsot , és kiszámol egy nyilvános kulcsot $w=357$ $y=g^{qw}{\pmod {p}}=7355$
Alice elküldi a nyilvános kulcsot , illetve egyenlő értékkel , a privát kulcs megmarad - ${\megjelenítési stílus (p,q,g,y)}$ $(48731,443,11444,7355)$ $w=357$

Hitelesítés:

Alice kiválaszt egy véletlen számot , és elküldi Bobnak. $r=274$ $x=g^{r}{\pmod {p}}=37123$
Bob küld egy számot Alice-nek $e=129$
Alice megszámolja és elküldi Bobnak. $s=(r+w*e){\pmod {q}}=255$ $s$
Bob kiszámítja és azonosítja Alice-t, mert . $z=g^{s}*y^{e}{\pmod {p}}=37123$ $z=x$

Támadások a séma ellen

Passzív ellenség

Ha Schnorr sémájában feltételezzük, hogy Alice egy ellenfél, akkor az 1. lépésben véletlenszerűen, de hatékonyan választhat. Legyen az Alice által átadott szám. Tegyük fel, hogy lehetséges két véletlen számot találni, és olyan, hogy Alice mindegyikhez megtalálja a megfelelőt , és amely megerősítése pozitív eredményt ad. Kapunk: $x$ $x$ $e_{1}$ $e_{2}$ ${\displaystyle e_{1}\neq e_{2))$ $s_{1}$ $s_{2}$

x=g^{s_{1}}y^{e_{1}}{\bmod {p}}

x=g^{s_{2}}y^{e_{2}}{\bmod {p}}

Innen ill . Mivel , akkor létezik , és ezért , vagyis a diszkrét logaritmusa . Így a protokoll 3. lépésében ritka az olyan, hogy Alice mindkettőjükre megfelelően tud válaszolni (amennyiben ugyanaz ) , ami azt jelenti, hogy Alice támadása csak elhanyagolható valószínűséggel sikeres. Vagy gyakran előfordulnak ilyen értékek, és akkor az Alice által használt algoritmus felhasználható a diszkrét logaritmusok kiszámítására. $g^{s_{1}}y^{e_{1}}=g^{s_{2}}y^{e_{2}}{\pmod {p}}$ $y^{e_{1}-e_{2}}=g^{s_{2}-s_{1}}{\pmod {p}}$ ${\displaystyle e_{1}\neq e_{2))$ $(e_{2}-e_{1})^{-1}{\bmod {q))$ $(s_{1}-s_{2})(e_{2}-e_{1})^{-1}=w{\bmod {q))$ $y$ $e_{1},e_{2},e_{1}\neq e_{2}$ $x$

Más szóval, bebizonyosodott, hogy feltételezve, hogy a diszkrét logaritmus probléma nehéz, a Schnorr hitelesítési séma ellenáll a passzív ellenfélnek, azaz helyes.

Aktív ellenség

Egy aktív ellenfél számos protokoll-végrehajtási munkamenetet lebonyolíthat hitelesítőként egy becsületes bizonyítóval (vagy lehallgathatja az ilyen végrehajtásokat), majd megkísérelheti megtámadni a hitelesítési sémát. Az aktív ellenféllel szembeni ellenálláshoz elegendő, ha a hitelesítési protokoll nulla tudásalapú . A Schnorr-séma nulla tudástulajdonságát azonban még senki sem tudta bizonyítani.

Digitális aláírási protokoll

A Schnorr algoritmus protokollként is használható egy üzenet digitális aláírásához . A kulcspár ugyanaz, de hozzáadásra került egy egyirányú hash funkció . $M$ $H(M)$

Aláírás generálása

Előzetes feldolgozás. Peggy kiválaszt egy véletlenszámot , amely kisebb, mint , és kiszámítja . Ez az előszámítási szakasz. Érdemes megjegyezni, hogy ugyanazok a nyilvános és privát kulcsok különböző üzenetek aláírására használhatók, miközben minden üzenethez új szám kerül kiválasztásra. $r$ $q$ $x=g^{r}{\pmod {p}}$ $r$
Peggy összefűzi az üzenetet , és kivonatolja az eredményt, hogy megkapja az első aláírást: $M$ $x$ $S_{1}=H(M|g^{r}{\bmod {p)))$
Peggy kiszámolja a második aláírást. Meg kell jegyezni, hogy a második aláírás modulo számít . $q$ $S_{2}=r+wS_{1}{\bmod {q))$ .
Peggy üzenetet küld Victornak, és feliratokat ír : . $M$ $S_{1}$ $S_{2}$

Aláírás ellenőrzése

Victor kiszámítja (vagy , ha úgy számítja ). $X=g^{S_{2}}y^{S_{1}}{\bmod {p}}$ $X=g^{S_{2}}y^{-S_{1}}{\bmod {p}}$ $y$ $y=g^{w}{\pmod {p}}$
Victor ellenőrzi . Ha igen, akkor az aláírást érvényesnek tekinti. $H(M|X)=S_{1}$

Hatékonyság

Az aláírás generálásához szükséges fő számításokat az előfeldolgozási szakaszban és a számítási szakaszban hajtják végre , ahol a és számok bitsorrendűek , a paraméter pedig egy bit. Az utolsó szorzás elhanyagolható az RSA séma moduláris szorzásához képest . $wS_{1}{\bmod {q))$ $w$ $S_{1}$ $140$ $r$ $72$

Az aláírás-ellenőrzés főként egy olyan számításból áll, amelyet a modulo számítások átlagával lehet elvégezni, ahol bitben van megadva a hosszúság . $X=g^{S_{2}}y^{S_{1}}$ $1,5l+0,25t$ $p$ $l=[log_{2}q]$ $q$

A rövidebb aláírás csökkenti az aláírás-generáláshoz és ellenőrzéshez szükséges műveletek számát: a Schnorr-sémában és az ElGamal-sémában . $O(\log _{2}q\log _{2}^{2}p)$ $O(\log ^{3}p)$

Példa

Kulcsgenerálás:

$q=103$ és . És . $p=2267$ $p=22q+1$
A ki van választva , amely a mező eleme . Aztán és $f=2$ $Z_{2267*}$ ${\frac {p-1}{q}}=22$ $g=2^{22}{\bmod {2}}267=354$
Peggy ekkor kiválasztja a kulcsot $w=30$ $y=1206$
Peggy privát kulcsa , nyilvános kulcsa . $30$ $(103,2267,354,1206)$

Üzenet aláírása:

Peggynek alá kell írnia az üzenetet . $M=1000$
Peggy választ és kiszámol . $r=11$ $g^{r}=354^{11}=630mod2267$
Tegyük fel, hogy az üzenet , és a soros kapcsolat azt jelenti, hogy . Tegyük fel azt is, hogy ennek az értéknek a kivonatolása egy kivonatot eredményez . Ez azt jelenti . $1000$ $1000630$ $H(1000630)=200$ $S_{1}=200$
Peggy kiszámolja . $S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37$
Peggy elküldi Victort és . $M=1000$ $S_{1}=200$ $S_{2}=37$

Szabadalmak

A Schnorr-séma több országban rendelkezik szabadalmakkal. Például az 1991. február 19-én kelt US 4 995 082 számú (2008. február 19-én lejárt). 1993-ban a Sunnyvale-i Public Key Partners (PKP) megszerezte a szabadalom világszintű jogait. Ez a rendszer az Egyesült Államokon kívül számos más országban is szabadalmaztatott.

Sematikus módosítások

Ernie Brickell és Kevin McCurley 1992-ben végrehajtott módosítása nagymértékben javította az áramkör biztonságát. Módszerük a számot használja , amelyhez hasonlóan nehéz felbontani , a szám egyszerű osztóját és a -ben lévő kitevő elemet , amelyeket ezt követően az aláírásban használnak. A Schnorr-sémától eltérően a módszerükben az aláírást az egyenlet számítja ki $p$ $p-1$ $q$ $p-1$ $\alpha$ $q$ $\mathbb {Z} _{p}^{*}$

s=e\alpha +k{\bmod {(}}p-1)

Előnyök

Míg Brickell és McCarley módosítása számításilag kevésbé hatékony, mint a Schnorr-séma, ennek a módszernek az az előnye, hogy két összetett probléma nehézségén alapul:

a logaritmus számítása a sorrendben ciklikus alcsoportban ; $q$ $\mathbb {Z} _{p}^{*}$
faktorizálás . $p-1$

Lásd még

Jegyzetek

Irodalom

Schnorr CP Hatékony aláírásgenerálás intelligens kártyákkal. - J. Cryptology, 1991. - S. 161-174.
Schnorr CP Hatékony azonosítás és aláírások intelligens kártyákhoz. Előrelépések a kriptológiában - CRYPTO'89. Számítástechnikai előadásjegyzetek 435. - 1990. - S. 239 - 252.
A. Menezes, P. van Oorschot, S. Vanstone. Alkalmazott kriptográfia kézikönyve. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7 .
Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .
Varnovsky N. P. Kriptográfiai protokollok // Bevezetés a kriptográfiába / Szerkesztette V. V. Yashchenko. - Péter, 2001. - 288 p. - ISBN 5-318-00443-1 . Archivált : 2008. február 25. a Wayback Machine -nél

Linkek

RFC 8235

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya