Schema Schnorr

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 septembrie 2021; verificările necesită 3 modificări .

Schema Schnorr este una dintre cele mai eficiente și bazate teoretic scheme de autentificare . Securitatea circuitului se bazează pe dificultatea calculării logaritmilor discreti . Schema propusă de Klaus Schnorr este o modificare a schemelor ElGamal (1985) și Fiat-Shamir (1986) , dar are o dimensiune mai mică a semnăturii. Schema Schnorr stă la baza standardului Republicii Belarus STB 1176.2-99 și standardelor sud-coreene KCDSA și EC-KCDSA. A fost acoperit de brevetul american 4.999.082 , care a expirat în februarie 2008.

Introducere

Schemele de autentificare și semnătură electronică sunt unul dintre cele mai importante și comune tipuri de protocoale criptografice care asigură integritatea informațiilor.

Scopul protocoalelor de autentificare poate fi ușor de înțeles prin următorul exemplu. Să presupunem că avem un sistem informațional în care este necesar să diferențiem accesul la diverse date. Tot în acest sistem există un administrator care stochează toți identificatorii de utilizator cu un set de drepturi asociat, cu ajutorul căruia se diferențiază accesul la resurse. Un utilizator i se poate permite simultan să citească un fișier, să schimbe al doilea și, în același timp, să i se interzică accesul la al treilea. În acest exemplu, asigurarea integrității informațiilor înseamnă împiedicarea accesului la sistem de către persoane care nu sunt utilizatorii acestuia, precum și împiedicarea utilizatorilor să acceseze acele resurse pentru care nu au autoritate. Cea mai comună metodă de control al accesului, protecția prin parolă , are o mulțime de dezavantaje, așa că să trecem la formularea criptografică a problemei.

Există doi participanți la protocol - Alice, care vrea să-și confirme identitatea și Bob, care trebuie să verifice această confirmare. Alice are două chei , o cheie publică (publică) și o cheie privată (privată) cunoscută doar de Alice. De fapt, Bob trebuie să verifice că Alice își cunoaște cheia privată folosind doar . $\mathrm {K} _{1}$ $\mathrm {K} _{2)$ $\mathrm {K} _{2)$ $\mathrm {K} _{1}$

Schema Schnorr este una dintre cele mai eficiente dintre protocoalele practice de autentificare care implementează această sarcină. Minimizează dependența de calcul necesar pentru a crea o semnătură pe mesaj. În această schemă, principalele calcule pot fi făcute în timp ce procesorul este inactiv, ceea ce vă permite să creșteți viteza de semnare. La fel ca DSA , schema lui Schnorr folosește un subgrup de ordine în . Această metodă folosește și o funcție hash . $q$ $\mathbb {Z} _{p}^{*}$ $h:\{0,1\}^{*}\la \mathbb {Z} _{p)$

Generare cheie

Generarea cheilor pentru schema de semnătură Schnorr este aceeași cu generarea cheilor pentru DSA , cu excepția faptului că nu există restricții de dimensiune. De asemenea, rețineți că modulul poate fi calculat autonom. $p$

Se alege un număr prim , care este de obicei egal cu lungimea biților. $p$ $1024$
Un alt număr prim este ales astfel încât să fie un divizor al lui . Sau, cu alte cuvinte, ar trebui făcut . Este obișnuit să alegeți dimensiunea pentru un număr egal cu biți. $q$ $p-1$ $p-1\equiv 0{\pmod {q)}$ $q$ $160$
Alegeți un număr diferit de , astfel încât . $g$ $unu$ $g^{q}\equiv 1{\pmod {p)}$
Peggy alege un număr întreg aleatoriu mai mic decât . $w$ $q$
Peggy calculează . $y=g^{qw}{\pmod {p)}$
Cheia publică a lui Peggy este , cheia privată a lui Peggy este . $(p,q,g,y)$ $w$

Protocol de autentificare

Algoritm de operare a protocolului

Preprocesare . Alice alege un număr aleatoriu mai mic decât și calculează . Aceste calcule sunt preliminare și pot fi făcute cu mult înainte de sosirea lui Bob. $r$ $q$ $x=g^{r}{\pmod {p}}$
Iniţiere. Alice îi trimite lui Bob. $X$
Bob alege un număr aleatoriu de la până și îl trimite lui Alice. $e$ $0$ $2^{t}-1$
Alice calculează și îi trimite lui Bob. $s=r+we{\pmod {q)}$ $s$
Confirmare. Bob verifică asta $x=g^{s}y^{e}{\pmod {p}}$

Securitatea algoritmului depinde de parametrul t . Complexitatea deschiderii algoritmului este aproximativ egală cu . Schnorr recomandă utilizarea t în jur de 72 de biți, pentru și . Pentru a rezolva problema logaritmului discret, în acest caz, sunt necesari cel puțin pașii algoritmilor cunoscuți. $2^{t}$ $p\geq 2^{512}$ $q\geq 2^{140}$ $2^{{72}}$

Exemplu

Generare cheie:

Selectați prim și prim ( ) $p=48731$ $q=443$ $q|p-1$
Calculat din condiția , în acest caz $g$ $g^{q}=1{\pmod {p}}$ $g=11444$
Alice alege o cheie privată și calculează o cheie publică $w=357$ $y=g^{qw}{\pmod {p}}=7355$
Alice trimite cheia publică , respectiv, egală cu , se păstrează cheia privată - $(p,q,g,y)$ $(48731,443,11444,7355)$ $w=357$

Autentificare:

Alice alege un număr aleatoriu și îl trimite lui Bob. $r=274$ $x=g^{r}{\pmod {p}}=37123$
Bob îi trimite un număr lui Alice $e=129$
Alice numără și îi trimite lui Bob. $s=(r+w*e){\pmod {q}}=255$ $s$
Bob calculează și identifică Alice deoarece . $z=g^{s}*y^{e}{\pmod {p}}=37123$ $z=x$

Atacurile la Schematic

Inamic pasiv

Dacă presupunem în schema lui Schnorr că Alice este un adversar, atunci la pasul 1 ea poate alege într-un mod aleatoriu, dar eficient. Fie numărul trecut de Alice. Să presupunem că este posibil să găsim două numere aleatorii și astfel încât pentru fiecare dintre ele Alice să găsească cel corespunzător și pentru care confirmarea va da un rezultat pozitiv. Primim: $X$ $X$ $e_{1}$ $e_{2}$ $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}}

De aici sau . Deoarece , atunci există și, prin urmare, , adică logaritmul discret al lui . Astfel, fie așa încât Alice să poată răspunde în mod corespunzător la ambele (având în vedere același ) la pasul 3 al protocolului este rar, ceea ce înseamnă că atacul lui Alice are succes doar cu o probabilitate neglijabilă. Sau astfel de valori se întâlnesc des, iar apoi algoritmul pe care îl folosește Alice poate fi folosit pentru a calcula logaritmi discreti. $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}}$ $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$

Cu alte cuvinte, se demonstrează că, în ipoteza că problema logaritmului discret este dificilă, schema de autentificare Schnorr este rezistentă împotriva unui adversar pasiv, adică corectă.

Inamic activ

Un adversar activ poate desfășura un număr de sesiuni de execuție a protocolului ca verificator cu un probator onest (sau să asculte cu urechea la astfel de execuții) și apoi să încerce să atace schema de autentificare. Pentru rezistența împotriva unui adversar activ, este suficient ca protocolul de autentificare să fie o dovadă a cunoștințelor zero . Cu toate acestea, nimeni nu a reușit încă să demonstreze proprietatea zero-cunoștințe pentru schema Schnorr.

Protocol de semnătură digitală

Algoritmul Schnorr poate fi folosit și ca protocol pentru semnarea digitală a unui mesaj . Perechea de chei este aceeași, dar este adăugată o funcție hash unidirecțională . $M$ $H(M)$

Generarea semnăturii

Prelucrare preliminară. Peggy alege un număr aleatoriu mai mic decât și calculează . Aceasta este etapa de precalculare. Este de remarcat faptul că aceleași chei publice și private pot fi folosite pentru a semna mesaje diferite, în timp ce numărul este ales din nou pentru fiecare mesaj. $r$ $q$ $x=g^{r}{\pmod {p}}$ $r$
Peggy concatenează mesajul și șterge rezultatul pentru a obține prima semnătură: $M$ $X$ $S_{1}=H(M|g^{r}{\bmod {p)))$
Peggy calculează a doua semnătură. Trebuie remarcat faptul că a doua semnătură este calculată modulo . $q$ $S_{2}=r+wS_{1}{\bmod {q))$ .
Peggy îi trimite lui Victor un mesaj și legende , . $M$ $S_{1}$ $S_{2}$

Verificarea semnăturii

Victor calculează (sau , dacă este calculat ca ). $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 verifică asta . Dacă da, consideră că semnătura este valabilă. $H(M|X)=S_{1}$

Eficiență

Principalele calcule pentru generarea unei semnături sunt efectuate în etapa de preprocesare și în etapa de calcul , unde numerele și au ordinea biților, iar parametrul este un bit. Ultima multiplicare este neglijabilă în comparație cu înmulțirea modulară din schema RSA . $wS_{1}{\bmod {q)}$ $w$ $S_{1}$ $140$ $r$ $72$

Verificarea semnăturii constă în principal într-un calcul care se poate face pe media calculelor modulo unde există o lungime în biți. $X=g^{S_{2}}y^{S_{1}}$ $1,5l+0,25t$ $p$ $l=[log_{2}q]$ $q$

O semnătură mai scurtă reduce numărul de operațiuni pentru generarea și verificarea semnăturii: în schema Schnorr și în schema ElGamal . $O(\log _{2}q\log _{2}^{2}p)$ $O(\log ^{3}p)$

Exemplu

Generare cheie:

$q=103$ și . Și . $p=2267$ $p=22q+1$
Este selectat , care este elementul din câmp . Apoi și $f=2$ $Z_{2267*}$ ${\frac {p-1}{q}}=22$ $g=2^{22}{\bmod {2}}267=354$
Peggy alege cheia atunci $w=30$ $y=1206$
Cheia privată a lui Peggy este , cheia publică este . $30$ $(103,2267,354,1206)$

Semnătura mesajului:

Peggy trebuie să semneze mesajul . $M=1000$
Peggy alege și calculează . $r=11$ $g^{r}=354^{11}=630mod2267$
Să presupunem că mesajul este , iar conexiunea în serie înseamnă . De asemenea, să presupunem că prin hashing această valoare se obține un rezumat . Aceasta înseamnă . $1000$ $1000630$ $H(1000630)=200$ $S_{1}=200$
Peggy calculează . $S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37$
Peggy îl trimite pe Victor și . $M=1000$ $S_{1}=200$ $S_{2}=37$

Brevete

Schema Schnorr are brevete în mai multe țări. De exemplu, US #4.995.082 din 19 februarie 1991 (a expirat la 19 februarie 2008). În 1993, Public Key Partners (PKP) din Sunnyvale a achiziționat drepturile la nivel mondial asupra acestui brevet. Pe lângă Statele Unite, această schemă este brevetată și în alte câteva țări.

Modificări schematice

O modificare a circuitului de către Ernie Brickell și Kevin McCurley în 1992 a îmbunătățit considerabil securitatea circuitului. Metoda lor folosește numărul , care, la fel ca , este greu de descompus, un simplu divizor al numărului și un element exponent în , care sunt ulterior utilizate în semnătură. Spre deosebire de schema Schnorr, semnătura din metoda lor este calculată prin ecuație $p$ $p-1$ $q$ $p-1$ $\alfa$ $q$ $\mathbb {Z} _{p}^{*}$

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

Beneficii

În timp ce modificarea lui Brickell și McCarley este mai puțin eficientă din punct de vedere computațional decât schema Schnorr, această metodă are avantajul că se bazează pe dificultatea a două probleme complexe:

calculul logaritmului în subgrupul ciclic de ordin în ; $q$ $\mathbb {Z} _{p}^{*}$
factorizarea . $p-1$

Vezi și

Note

Literatură

Generare eficientă de semnături Schnorr CP prin carduri inteligente. - J. Criptologie, 1991. - S. 161-174.
Identificare și semnături eficiente Schnorr CP pentru carduri inteligente. Avansuri în criptologie - CRYPTO'89. Note de curs în Informatică 435. - 1990. - S. 239 - 252.
A. Menezes, P. van Oorschot, S. Vanstone. Manual de Criptografie Aplicată. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7 .
Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Varnovsky N. P. Protocoale criptografice // Introducere în criptografie / Editat de V. V. Yashchenko. - Petru, 2001. - 288 p. - ISBN 5-318-00443-1 . Arhivat pe 25 februarie 2008 la Wayback Machine

Link -uri

RFC 8235

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP