Schnorrovo schéma

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. září 2021; kontroly vyžadují 3 úpravy .

Schnorr schéma je jedním z nejúčinnějších a teoreticky založených autentizačních schémat . Bezpečnost obvodu je založena na obtížnosti výpočtu diskrétních logaritmů . Schéma navržené Klausem Schnorrem je modifikací schémat ElGamal (1985) a Fiat-Shamir (1986) , ale má menší velikost podpisu. Schéma Schnorr je základem standardu Běloruské republiky STB 1176.2-99 a jihokorejských standardů KCDSA a EC-KCDSA. Vztahuje se na něj americký patent 4 999 082 , jehož platnost vypršela v únoru 2008.

Úvod

Schémata autentizace a elektronického podpisu jsou jedním z nejdůležitějších a nejběžnějších typů kryptografických protokolů, které zajišťují integritu informací.

Účel autentizačních protokolů lze snadno pochopit z následujícího příkladu. Předpokládejme, že máme informační systém, ve kterém je nutné rozlišovat přístup k různým datům. I v tomto systému je administrátor, který ukládá všechny uživatelské identifikátory s přidruženou sadou práv, pomocí kterých se rozlišuje přístup ke zdrojům. Jednomu uživateli lze současně povolit čtení jednoho souboru, změnu druhého a zároveň odepřít přístup ke třetímu. V tomto příkladu zajištění integrity informací znamená zamezení přístupu do systému osobám, které nejsou jeho uživateli, a také zabránění uživatelům v přístupu k těm zdrojům, ke kterým nemají oprávnění. Nejběžnější způsob kontroly přístupu, ochrana heslem , má spoustu nevýhod, přejděme tedy ke kryptografické formulaci problému.

V protokolu jsou dva účastníci – Alice, která chce potvrdit svou identitu, a Bob, který toto potvrzení musí ověřit. Alice má dva klíče , veřejný (veřejný) klíč a soukromý (soukromý) klíč, který zná pouze Alice. Ve skutečnosti musí Bob ověřit, že Alice zná její soukromý klíč pouze pomocí . $\mathrm {K} _{1}$ ${\displaystyle \mathrm {K} _{2))$ ${\displaystyle \mathrm {K} _{2))$ $\mathrm {K} _{1}$

Schnorr schéma je jedním z nejúčinnějších mezi praktickými autentizačními protokoly, které tento úkol implementují. Minimalizuje závislost výpočtu potřebného k vytvoření podpisu na zprávě. V tomto schématu lze hlavní výpočty provádět, když je procesor nečinný, což umožňuje zvýšit rychlost podepisování. Stejně jako DSA používá Schnorrovo schéma podskupinu objednávek v . Tato metoda také používá hashovací funkci . $q$ $\mathbb {Z} _{p}^{*}$ ${\displaystyle h:\{0,1\}^{*}\to \mathbb {Z} _{p))$

Generování klíčů

Generování klíče pro schéma podpisu Schnorr je stejné jako generování klíče pro DSA , kromě toho, že neexistují žádná omezení velikosti. Všimněte si také, že modul lze vypočítat autonomně. $p$

Vybere se prvočíslo , jehož délka se obvykle rovná bitům. $p$ $1024$
Jiné prvočíslo je vybráno tak, že je dělitelem . Nebo jinými slovy, mělo by se to udělat . Je zvykem volit velikost pro číslo rovnající se bitům. $q$ $p-1$ $p-1\equiv 0{\pmod {q))$ $q$ $160$
Vyberte číslo odlišné od , např . . $G$ $jeden$ $g^{q}\equiv 1{\pmod {p))$
Peggy vybere náhodné celé číslo menší než . $w$ $q$
Peggy počítá . $y=g^{qw}{\pmod {p))$
Veřejný klíč Peggy je , soukromý klíč Peggy je . $(p,q,g,y)$ $w$

Autentizační protokol

Algoritmus provozu protokolu

Předzpracování . Alice vybere náhodné číslo menší než a vypočítá . Tyto výpočty jsou předběžné a lze je provést dlouho předtím, než Bob dorazí. $r$ $q$ $x=g^{r}{\pmod {p}}$
Zahájení. Alice posílá Bobovi. $X$
Bob vybere náhodné číslo od do a pošle ho Alici. $E$ $0$ $2^{t}-1$
Alice vypočítává a posílá Bobovi. $s=r+we{\pmod {q))$ $s$
Potvrzení. Bob to kontroluje $x=g^{s}y^{e}{\pmod {p))$

Bezpečnost algoritmu závisí na parametru t . Složitost otevření algoritmu je přibližně rovna . Schnorr doporučuje používat t kolem 72 bitů pro a . K vyřešení problému diskrétního logaritmu jsou v tomto případě nutné alespoň kroky známých algoritmů. $2^{t}$ $p\geq 2^{512}$ $q\geq 2^{140}$ $2^{{72}}$

Příklad

Generování klíče:

Vyberte prvočíslo a prvočíslo ( ) $p=48731$ $q=443$ $q|p-1$
V tomto případě počítáno z podmínky $G$ $g^{q}=1{\pmod {p}}$ $g=11444$
Alice vybere soukromý klíč a vypočítá veřejný klíč $w=357$ $y=g^{qw}{\pmod {p}}=7355$
Alice odešle veřejný klíč , respektive rovný , soukromý klíč je zachován - $(p,q,g,y)$ $(48731,443,11444,7355)$ $w=357$

Ověření:

Alice vybere náhodné číslo a pošle ho Bobovi. $r=274$ $x=g^{r}{\pmod {p}}=37123$
Bob pošle číslo Alici $e=129$
Alice počítá a posílá Bobovi. $s=(r+w*e){\pmod {q}}=255$ $s$
Bob počítá a identifikuje Alici, protože . $z=g^{s}*y^{e}{\pmod {p}}=37123$ $z=x$

Útoky na schéma

Pasivní nepřítel

Pokud ve Schnorrově schématu předpokládáme, že Alice je protivník, pak si v kroku 1 může vybrat náhodným, ale účinným způsobem. Nechť je číslo, které předala Alice. Předpokládejme, že je možné najít dvě náhodná čísla a taková, že pro každé z nich Alice dokáže najít odpovídající a pro které potvrzení dá kladný výsledek. Dostaneme: $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}}

Odtud nebo . Protože , Potom existuje , a proto , To je diskrétní logaritmus . Tedy buď takový, že Alice může na oba přiměřeně reagovat (za předpokladu, že je to stejné ) v kroku 3 protokolu, je vzácné, což znamená, že Alicin útok je úspěšný jen se zanedbatelnou pravděpodobností. Nebo se s takovými hodnotami setkávají často, a pak lze algoritmus, který Alice používá, použít k výpočtu diskrétních logaritmů. $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$ ${\displaystyle e_{1},e_{2},e_{1}\neq e_{2))$ $X$

Jinými slovy, je dokázáno, že za předpokladu, že problém diskrétního logaritmu je obtížný, Schnorrovo autentizační schéma je odolné vůči pasivnímu protivníkovi, tedy správné.

Aktivní nepřítel

Aktivní protivník může provést řadu relací provádění protokolu jako ověřovatel s poctivým dokazovatelem (nebo takové provádění odposlouchávat) a poté se pokusit napadnout autentizační schéma. Pro odolnost proti aktivnímu protivníkovi stačí, aby byl autentizační protokol důkazem nulových znalostí . Nikdo však dosud nebyl schopen prokázat vlastnost nulových znalostí pro Schnorrovo schéma.

Protokol digitálního podpisu

Algoritmus Schnorr lze také použít jako protokol pro digitální podepisování zprávy . Pár klíčů je stejný, ale je přidána jednosměrná hašovací funkce . $M$ $H(M)$

Generování podpisu

Předběžné zpracování. Peggy vybere náhodné číslo menší než a vypočítá . Toto je předvýpočetní fáze. Za zmínku stojí, že k podepisování různých zpráv lze použít stejný veřejný a soukromý klíč, přičemž číslo se pro každou zprávu volí nově. $r$ $q$ $x=g^{r}{\pmod {p}}$ $r$
Peggy zřetězí zprávu a výsledek hashuje, aby získala první podpis: $M$ $X$ $S_{1}=H(M|g^{r}{\bmod {p)))$
Peggy vypočítá druhý podpis. Je třeba poznamenat, že druhý podpis se počítá modulo . $q$ $S_{2}=r+wS_{1}{\bmod {q))$ .
Peggy pošle Victorovi zprávu a titulky , . $M$ $S_{1}$ $S_{2}$

Ověření podpisu

Victor počítá (nebo , pokud se počítá jako ). $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 to kontroluje . Pokud ano, považuje podpis za platný. $H(M|X)=S_{1}$

Účinnost

Hlavní výpočty pro generování podpisu se provádějí ve fázi předběžného zpracování a ve fázi výpočtu , kde čísla a mají pořadí bitů a parametr je bit. Poslední násobení je zanedbatelné ve srovnání s modulárním násobením ve schématu RSA . $wS_{1}{\bmod {q))$ $w$ $S_{1}$ $140$ $r$ $72$

Ověření podpisu sestává hlavně z výpočtu , který lze provést na průměru modulo výpočtů , kde je délka v bitech. $X=g^{S_{2}}y^{S_{1}}$ $1,5l+0,25t$ $p$ $l=[log_{2}q]$ $q$

Kratší podpis snižuje počet operací pro generování a ověřování podpisů: ve schématu Schnorr a ve schématu ElGamal . $O(\log _{2}q\log _{2}^{2}p)$ $O(\log ^{3}p)$

Příklad

Generování klíče:

$q=103$ a . A . $p=2267$ $p=22q+1$
Je vybráno , což je prvek v poli . Pak a $f=2$ $Z_{2267*}$ ${\frac {p-1}{q}}=22$ $g=2^{22}{\bmod {2}}267=354$
Peggy pak vybere klíč $w=30$ $y=1206$
Soukromý klíč Peggy je , veřejný klíč je . $30$ $(103,2267,354,1206)$

Podpis zprávy:

Peggy musí zprávu podepsat . $M=1000$
Peggy vybírá a počítá . $r=11$ $g^{r}=354^{11}=630mod2267$
Předpokládejme, že zpráva je a sériové připojení znamená . Předpokládejme také, že hašování této hodnoty poskytne výtah . To znamená . $1000$ $1000630$ $H(1000630)=200$ $S_{1}=200$
Peggy počítá . $S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37$
Peggy posílá Victora a . $M=1000$ $S_{1}=200$ $S_{2}=37$

Patenty

Schnorrův systém má patenty v několika zemích. Například US #4,995,082 ze dne 19. února 1991 (platnost vypršela 19. února 2008). V roce 1993 získala společnost Public Key Partners (PKP) ze Sunnyvale celosvětová práva na tento patent. Kromě Spojených států je tento systém patentován také v několika dalších zemích.

Schematické úpravy

Úprava okruhu Ernie Brickell a Kevin McCurley v roce 1992 výrazně zlepšila zabezpečení okruhu. Jejich metoda používá číslo , které je stejně jako , obtížné rozložit, jednoduchý dělitel čísla a exponent v , které jsou následně použity v podpisu. Na rozdíl od Schnorrova schématu je signatura v jejich metodě vypočítána rovnicí $p$ $p-1$ $q$ $p-1$ $\alpha$ $q$ $\mathbb {Z} _{p}^{*}$

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

Výhody

Zatímco modifikace Brickella a McCarleyho je výpočetně méně efektivní než Schnorrovo schéma, tato metoda má tu výhodu, že je založena na obtížnosti dvou komplexních problémů:

výpočet logaritmu v cyklické podskupině řádu v ; $q$ $\mathbb {Z} _{p}^{*}$
faktorizace . $p-1$

Viz také

Poznámky

Literatura

Schnorr CP Efektivní generování podpisu pomocí čipových karet. - J. Cryptology, 1991. - S. 161-174.
Schnorr CP Efektivní identifikace a podpisy pro čipové karty. Pokroky v kryptologii - CRYPTO'89. Poznámky k přednáškám z informatiky 435. - 1990. - S. 239 - 252.
A. Menezes, P. van Oorschot, S. Vanstone. Příručka aplikované kryptografie. - CRC Press, 1996. - 816 s. - ISBN 0-8493-8523-7 .
Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Varnovskij N. P. Kryptografické protokoly // Úvod do kryptografie / Editoval V. V. Yashchenko. - Petr, 2001. - 288 s. - ISBN 5-318-00443-1 . Archivováno 25. února 2008 na Wayback Machine

Odkazy

RFC 8235

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta