Schnorr ordning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. september 2021; checks kræver 3 redigeringer .

Schnorr- ordningen er en af de mest effektive og teoretisk baserede autentificeringsordninger . Kredsløbets sikkerhed er baseret på vanskeligheden ved at beregne diskrete logaritmer . Ordningen foreslået af Klaus Schnorr er en modifikation af ordningerne ElGamal (1985) og Fiat-Shamir (1986) , men har en mindre signaturstørrelse. Schnorr-ordningen ligger til grund for standarden for Republikken Belarus STB 1176.2-99 og de sydkoreanske standarder KCDSA og EC-KCDSA. Det var dækket af US Patent 4.999.082 , som udløb i februar 2008.

Introduktion

Autentificering og elektroniske signaturordninger er en af de vigtigste og mest almindelige typer kryptografiske protokoller, der sikrer informationens integritet.

Formålet med godkendelsesprotokoller kan let forstås af følgende eksempel. Antag, at vi har et informationssystem, hvor det er nødvendigt at differentiere adgangen til forskellige data. Også i dette system er der en administrator, som gemmer alle brugeridentifikatorer med et tilhørende sæt rettigheder, ved hjælp af hvilke adgangen til ressourcer differentieres. Én bruger kan samtidigt få lov til at læse én fil, ændre den anden og samtidig nægtes adgang til den tredje. I dette eksempel betyder sikring af informationens integritet at forhindre adgang til systemet af personer, der ikke er dets brugere, samt at forhindre brugere i at få adgang til de ressourcer, som de ikke har autoritet til. Den mest almindelige metode til adgangskontrol, adgangskodebeskyttelse , har mange ulemper, så lad os gå videre til den kryptografiske formulering af problemet.

Der er to deltagere i protokollen - Alice, som ønsker at bekræfte sin identitet, og Bob, som skal verificere denne bekræftelse. Alice har to nøgler , en offentlig (offentlig) nøgle og en privat (privat) nøgle, som kun Alice kender. Faktisk skal Bob bekræfte, at Alice kender sin private nøgle ved kun at bruge . $\mathrm {K} _{1}$ ${\displaystyle \mathrm {K} _{2))$ ${\displaystyle \mathrm {K} _{2))$ $\mathrm {K} _{1}$

Schnorr-ordningen er en af de mest effektive blandt praktiske godkendelsesprotokoller, der implementerer denne opgave. Det minimerer afhængigheden af den beregning, der kræves for at skabe en signatur på beskeden. I denne ordning kan de vigtigste beregninger udføres, mens processoren er inaktiv, hvilket giver dig mulighed for at øge underskrivelseshastigheden. Ligesom DSA bruger Schnorrs ordning en ordreundergruppe i . Denne metode bruger også en hash-funktion . $q$ $\mathbb {Z} _{p}^{*}$ ${\displaystyle h:\{0,1\}^{*}\to \mathbb {Z} _{p))$

Nøglegenerering

Nøglegenerering for Schnorr-signaturskemaet er det samme som nøglegenerering for DSA , bortset fra at der ikke er nogen størrelsesbegrænsninger. Bemærk også, at modulet kan beregnes autonomt. $s$

Der vælges et primtal , som normalt er lig med bits i længden. $s$ $1024$
Et andet primtal er valgt sådan, at det er en divisor af . Eller med andre ord, det skal gøres . Det er sædvanligt at vælge størrelsen for et tal svarende til bits. $q$ $p-1$ $p-1\equiv 0{\pmod {q))$ $q$ $160$
Vælg et andet tal fra , sådan at . $g$ $en$ $g^{q}\equiv 1{\pmod {p))$
Peggy vælger et tilfældigt heltal mindre end . $w$ $q$
Peggy beregner . $y=g^{qw}{\pmod {p))$
Peggys offentlige nøgle er , Peggys private nøgle er . $(p,q,g,y)$ $w$

Godkendelsesprotokol

Protokoloperationsalgoritme

Forbehandling . Alice vælger et tilfældigt tal mindre end , og beregner . Disse beregninger er foreløbige og kan gøres længe før Bob ankommer. $r$ $q$ $x=g^{r}{\pmod {p}}$
Indvielse. Alice sender til Bob. $x$
Bob vælger et tilfældigt tal fra til og sender det til Alice. $e$ $0$ $2^{t}-1$
Alice beregner og sender til Bob. $s=r+vi{\pmod {q))$ $s$
Bekræftelse. Bob tjekker det $x=g^{s}y^{e}{\pmod {p}}$

Algoritmens sikkerhed afhænger af parameteren t . Kompleksiteten ved at åbne algoritmen er omtrent lig med . Schnorr anbefaler at bruge t omkring 72 bit, til og . For at løse det diskrete logaritmeproblem, i dette tilfælde, kræves i det mindste trinene fra kendte algoritmer. $2^{t}$ $p\geq 2^{512}$ $q\geq 2^{140}$ $2^{{72}}$

Eksempel

Nøglegenerering:

Vælg prime og prime ( ) $p=48731$ $q=443$ $q|p-1$
Beregnet ud fra betingelsen , i dette tilfælde $g$ $g^{q}=1{\pmod {p}}$ $g=11444$
Alice vælger en privat nøgle og beregner en offentlig nøgle $w=357$ $y=g^{qw}{\pmod {p}}=7355$
Alice sender den offentlige nøgle , henholdsvis lig med , den private nøgle bevares - $(p,q,g,y)$ $(48731,443,11444,7355)$ $w=357$

Godkendelse:

Alice vælger et tilfældigt tal og sender det til Bob. $r=274$ $x=g^{r}{\pmod {p}}=37123$
Bob sender et nummer til Alice $e=129$
Alice tæller og sender til Bob. $s=(r+w*e){\pmod {q}}=255$ $s$
Bob beregner og identificerer Alice fordi . $z=g^{s}*y^{e}{\pmod {p}}=37123$ $z=x$

Angreb på det skematiske

Passiv fjende

Hvis vi i Schnorrs skema antager, at Alice er en modstander, så kan hun i trin 1 vælge på en tilfældig, men effektiv måde. Lad være nummeret, som Alice har passeret. Lad os antage, at det er muligt at finde to tilfældige tal og sådan, at for hver af dem kan Alice finde den tilsvarende , og for hvilken bekræftelse vil give et positivt resultat. Vi får: $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}}

Herfra eller . Siden , Så eksisterer og derfor, , Det vil sige den diskrete logaritme af . Således er enten sådan, at Alice kan reagere passende på dem begge (givet det samme ) i trin 3 i protokollen, sjældent, hvilket betyder, at Alices angreb kun lykkes med en ubetydelig sandsynlighed. Eller sådanne værdier støder ofte på, og så kan den algoritme, som Alice bruger, bruges til at beregne diskrete logaritmer. $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$ $e_{1},e_{2},e_{1}\neq e_{2}$ $x$

Med andre ord er det bevist, at under den antagelse, at det diskrete logaritmeproblem er vanskeligt, er Schnorr-autentificeringsskemaet modstandsdygtigt over for en passiv modstander, det vil sige korrekt.

Aktiv fjende

En aktiv modstander kan udføre et antal protokoludførelsessessioner som verifikator med en ærlig bevis (eller aflytte sådanne henrettelser) og derefter forsøge at angribe godkendelsesskemaet. For modstand mod en aktiv modstander er det tilstrækkeligt, at autentificeringsprotokollen er et nul-vidensbevis . Ingen har dog endnu kunne bevise nulviden-egenskaben for Schnorr-ordningen.

Digital signaturprotokol

Schnorr-algoritmen kan også bruges som en protokol til digital signering af en besked . Nøgleparret er det samme, men en envejs-hash-funktion er tilføjet . $M$ $H(M)$

Signaturgenerering

Foreløbig behandling. Peggy vælger et tilfældigt tal mindre end , og beregner . Dette er forudberegningsfasen. Det er værd at bemærke, at de samme offentlige og private nøgler kan bruges til at signere forskellige beskeder, mens nummeret vælges på ny for hver besked. $r$ $q$ $x=g^{r}{\pmod {p}}$ $r$
Peggy sammenkæder beskeden og hash resultatet for at få den første signatur: $M$ $x$ $S_{1}=H(M|g^{r}{\bmod {p)))$
Peggy beregner den anden signatur. Det skal bemærkes, at den anden signatur beregnes modulo . $q$ $S_{2}=r+wS_{1}{\bmod {q))$ .
Peggy sender Victor en besked og billedtekster . $M$ $S_{1}$ $S_{2}$

Signaturbekræftelse

Victor beregner (eller , hvis det beregnes som ). $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 tjekker det . Hvis det er tilfældet, anser den signaturen for at være gyldig. $H(M|X)=S_{1}$

Effektivitet

De vigtigste beregninger til generering af en signatur udføres på forbehandlingsstadiet og på beregningsstadiet , hvor tallene og har rækkefølgen af bit, og parameteren er en bit. Den sidste multiplikation er ubetydelig sammenlignet med den modulære multiplikation i RSA- skemaet . $wS_{1}{\bmod {q))$ $w$ $S_{1}$ $140$ $r$ $72$

Signaturverifikation består hovedsageligt af en beregning , der kan udføres på gennemsnittet af modulo-beregninger , hvor der er en længde i bit. $X=g^{S_{2}}y^{S_{1}}$ $1,5l+0,25t$ $s$ $l=[log_{2}q]$ $q$

En kortere signatur reducerer antallet af operationer til signaturgenerering og -verifikation: i Schnorr-ordningen og i ElGamal-ordningen . $O(\log _{2}q\log _{2}^{2}p)$ $O(\log ^{3}p)$

Eksempel

Nøglegenerering:

$q=103$ og . Og . $p=2267$ $p=22q+1$
Den er valgt , som er elementet i feltet . Så og $f=2$ $Z_{2267*}$ ${\frac {p-1}{q}}=22$ $g=2^{22}{\bmod {2}}267=354$
Peggy vælger derefter nøglen $w=30$ $y=1206$
Peggys private nøgle er , offentlige nøgle er . $30$ $(103,2267,354,1206)$

Meddelelsessignatur:

Peggy skal underskrive beskeden . $M=1000$
Peggy vælger og beregner . $r=11$ $g^{r}=354^{11}=630mod2267$
Antag, at meddelelsen er , og den serielle forbindelse betyder . Antag også, at hashing af denne værdi giver en digest . Dette betyder . $1000$ $1000630$ $H(1000630)=200$ $S_{1}=200$
Peggy beregner . $S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37$
Peggy sender Victor og . $M=1000$ $S_{1}=200$ $S_{2}=37$

Patenter

Schnorr-ordningen har patenter i flere lande. For eksempel US #4.995.082 dateret 19. februar 1991 (udløb 19. februar 2008). I 1993 erhvervede Public Key Partners (PKP) fra Sunnyvale de verdensomspændende rettigheder til dette patent. Ud over USA er denne ordning også patenteret i flere andre lande.

Skematiske ændringer

En kredsløbsmodifikation af Ernie Brickell og Kevin McCurley i 1992 forbedrede kredsløbets sikkerhed i høj grad. Deres metode bruger tallet , der ligesom , er svært at nedbryde, en simpel divisor af tallet , og et eksponentelement i , som efterfølgende bruges i signaturen. I modsætning til Schnorr-skemaet beregnes signaturen i deres metode af ligningen $s$ $p-1$ $q$ $p-1$ $\alfa$ $q$ $\mathbb {Z} _{p}^{*}$

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

Fordele

Mens Brickell og McCarleys modifikation er beregningsmæssigt mindre effektiv end Schnorr-skemaet, har denne metode den fordel, at den er baseret på vanskeligheden ved to komplekse problemer:

beregning af logaritmen i den cykliske undergruppe af orden i ; $q$ $\mathbb {Z} _{p}^{*}$
faktorisering . $p-1$

Se også

Noter

Litteratur

Schnorr CP Efficient Signature Generation af Smart Cards. - J. Cryptology, 1991. - S. 161-174.
Schnorr CP Effektiv identifikation og signaturer til smartkort. Fremskridt inden for kryptologi - CRYPTO'89. Lecture Notes in Computer Science 435. - 1990. - S. 239 - 252.
A. Menezes, P. van Oorschot, S. Vanstone. Håndbog i anvendt kryptografi. - CRC Press, 1996. - 816 s. - ISBN 0-8493-8523-7 .
Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Varnovsky N. P. Kryptografiske protokoller // Introduktion til kryptografi / Redigeret af V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkiveret 25. februar 2008 på Wayback Machine

Links

RFC 8235

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort