Schnorrin kaava

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2.9.2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Schnorr - järjestelmä on yksi tehokkaimmista ja teoreettisimmista todennusmenetelmistä . Piirin turvallisuus perustuu diskreettien logaritmien laskemisen vaikeuteen . Klaus Schnorrin ehdottama järjestelmä on muunnos ElGamal (1985) ja Fiat-Shamir (1986) skeemoista , mutta sen allekirjoituskoko on pienempi. Schnorr-järjestelmä perustuu Valko-Venäjän tasavallan standardiin STB 1176.2-99 ja Etelä-Korean standardeihin KCDSA ja EC-KCDSA. Se kuului US-patentin 4 999 082 piiriin , joka päättyi helmikuussa 2008.

Johdanto

Todennus- ja sähköiset allekirjoitukset ovat yksi tärkeimmistä ja yleisimmistä salausprotokollien tyypeistä, jotka varmistavat tiedon eheyden.

Todennusprotokollien tarkoitus on helppo ymmärtää seuraavasta esimerkistä. Oletetaan, että meillä on tietojärjestelmä, jossa on tarpeen erottaa pääsy erilaisiin tietoihin. Myös tässä järjestelmässä on järjestelmänvalvoja, joka tallentaa kaikki käyttäjätunnukset niihin liittyvine oikeuksineen, joiden avulla resurssien käyttö eriytetään. Yhdelle käyttäjälle voidaan samanaikaisesti antaa lupa lukea yhtä tiedostoa, muuttaa toista ja samalla evätä pääsy kolmanteen. Tässä esimerkissä tiedon eheyden varmistaminen tarkoittaa sitä, että estetään henkilöiden, jotka eivät ole sen käyttäjiä, pääsy järjestelmään, sekä estetään käyttäjiä pääsemästä niihin resursseihin, joihin heillä ei ole valtuuksia. Yleisimmällä kulunvalvontamenetelmällä, salasanasuojauksella , on paljon haittoja, joten siirrytään ongelman kryptografiseen muotoiluun.

Protokollassa on kaksi osallistujaa - Alice, joka haluaa vahvistaa henkilöllisyytensä, ja Bob, jonka on vahvistettava tämä vahvistus. Alicella on kaksi avainta , julkinen (julkinen) avain ja yksityinen (yksityinen) avain, jotka vain Alice tuntee. Itse asiassa Bobin on varmistettava, että Alice tuntee yksityisen avaimensa käyttämällä vain . $\mathrm {K} _{1}$ ${\displaystyle \mathrm {K} _{2))$ ${\displaystyle \mathrm {K} _{2))$ $\mathrm {K} _{1}$

Schnorr-malli on yksi tehokkaimmista tämän tehtävän toteuttavista käytännön todennusprotokollista. Se minimoi viestin allekirjoituksen luomiseen tarvittavan laskutoimituksen riippuvuuden. Tässä järjestelmässä tärkeimmät laskelmat voidaan tehdä prosessorin ollessa käyttämättömänä, mikä mahdollistaa allekirjoittamisen nopeuden lisäämisen. Kuten DSA , Schnorrin järjestelmä käyttää tilausalaryhmää . Tämä menetelmä käyttää myös hash-funktiota . $q$ $\mathbb {Z} _{p}^{*}$ ${\displaystyle h:\{0,1\}^{*}\to \mathbb {Z} _{p))$

Avaimen luominen

Avainten luominen Schnorr-allekirjoitusmallille on sama kuin avainten luominen DSA :lle , paitsi että kokorajoituksia ei ole. Huomaa myös, että moduuli voidaan laskea itsenäisesti. $s$

Valitaan alkuluku , joka on yleensä yhtä pitkä kuin bittejä. $s$ $1024$
Toinen alkuluku valitaan siten, että se on luvun jakaja . Tai toisin sanoen se pitäisi tehdä . On tapana valita koko bittejä vastaavalle luvulle. $q$ $p-1$ $p-1\equiv 0{\pmod {q))$ $q$ $160$
Valitse eri numero kuin , niin että . $g$ $yksi$ $g^{q}\equiv 1{\pmod {p))$
Peggy valitsee satunnaisen kokonaisluvun, joka on pienempi kuin . $w$ $q$
Peggy laskee . $y=g^{qw}{\pmod {p))$
Peggyn julkinen avain on , Peggyn yksityinen avain on . ${\näyttötyyli (p,q,g,y)}$ $w$

Todennusprotokolla

Protokollan toimintaalgoritmi

Esikäsittely . Alice valitsee satunnaisluvun , joka on pienempi kuin , ja laskee . Nämä laskelmat ovat alustavia ja voidaan tehdä kauan ennen Bobin saapumista. $r$ $q$ $x=g^{r}{\pmod {p}}$
Initiaatio. Alice lähettää Bobille. $x$
Bob valitsee satunnaisen luvun väliltä ja lähettää sen Alicelle. $e$ $0$ ${\näyttötyyli 2^{t}-1}$
Alice laskee ja lähettää Bobille. $s=r+me{\pmod {q))$ $s$
Vahvistus. Bob tarkistaa sen $x=g^{s}y^{e}{\pmod {p))$

Algoritmin turvallisuus riippuu parametrista t . Algoritmin avaamisen monimutkaisuus on suunnilleen yhtä suuri kuin . Schnorr neuvoo käyttämään t noin 72 bittiä, ja . Diskreetin logaritmin ongelman ratkaisemiseksi tarvitaan tässä tapauksessa ainakin tunnettujen algoritmien vaiheet. $2^{t}$ $p\geq 2^{512}$ $q\geq 2^{140}$ $2^{{72}}$

Esimerkki

Avaimen luominen:

Valitse alkuluku ja alkuluku ( ) $p=48731$ $q=443$ $q|p-1$
Laskettu ehdosta tässä tapauksessa $g$ $g^{q}=1{\pmod {p}}$ $g=11444$
Alice valitsee yksityisen avaimen ja laskee julkisen avaimen $w=357$ $y=g^{qw}{\pmod {p}}=7355$
Alice lähettää julkisen avaimen , joka on yhtä suuri kuin , yksityinen avain säilytetään - ${\näyttötyyli (p,q,g,y)}$ $(48731,443,11444,7355)$ $w=357$

Todennus:

Alice valitsee satunnaisen luvun ja lähettää sen Bobille. $r=274$ $x=g^{r}{\pmod {p}}=37123$
Bob lähettää numeron Alicelle $e=129$
Alice laskee ja lähettää Bobille. $s=(r+w*e){\pmod {q}}=255$ $s$
Bob laskee ja tunnistaa Alicen, koska . $z=g^{s}*y^{e}{\pmod {p}}=37123$ $z=x$

Hyökkäyksiä kaavamaiseen

Passiivinen vihollinen

Jos oletetaan Schnorrin kaavassa, että Alice on vastustaja, niin vaiheessa 1 hän voi valita satunnaisella mutta tehokkaalla tavalla. Olkoon Alicen välittämä numero. Oletetaan, että on mahdollista löytää kaksi satunnaislukua ja sellainen, että jokaiselle Alice voi löytää vastaavan ja jolle vahvistus antaa positiivisen tuloksen. Saamme: $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}}

Täältä tai . Koska , Sitten on olemassa ja siksi , Eli diskreetti logaritmi . Siten kumpikin sellainen, että Alice voi vastata molempiin asianmukaisesti (jos sama ) protokollan vaiheessa 3, on harvinainen, mikä tarkoittaa, että Alicen hyökkäys onnistuu vain merkityksettömällä todennäköisyydellä. Tai tällaisia arvoja tulee usein vastaan, ja sitten Alicen käyttämää algoritmia voidaan käyttää diskreettien logaritmien laskemiseen. $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$

Toisin sanoen on todistettu, että olettaen, että diskreetti logaritmiongelma on vaikea, Schnorr-autentikointimenetelmä on resistentti passiivista vastustajaa vastaan, eli oikea.

Aktiivinen vihollinen

Aktiivinen vastustaja voi suorittaa useita protokollan suoritusistuntoja todentajana rehellisen todistajan kanssa (tai salakuunnella tällaisia suorituksia) ja yrittää sitten hyökätä todennusjärjestelmää vastaan. Aktiivista vastustajaa vastaan vastustamiseen riittää, että todennusprotokolla on nolla-knowledge proof . Kukaan ei kuitenkaan ole vielä kyennyt todistamaan Schnorr-järjestelmän nollatietoominaisuutta.

Digitaalinen allekirjoitusprotokolla

Schnorr-algoritmia voidaan käyttää myös viestin digitaalisen allekirjoittamisen protokollana . Avainpari on sama, mutta yksisuuntainen hajautustoiminto on lisätty . $M$ $H(M)$

Allekirjoituksen luominen

Esikäsittely. Peggy valitsee satunnaisluvun , joka on pienempi kuin , ja laskee . Tämä on esilaskentavaihe. On syytä huomata, että samoilla julkisilla ja yksityisillä avaimilla voidaan allekirjoittaa eri viestejä, kun taas numero valitaan jokaiselle viestille uudelleen. $r$ $q$ $x=g^{r}{\pmod {p}}$ $r$
Peggy ketjuttaa viestin ja tiivistää tuloksen saadakseen ensimmäisen allekirjoituksen: $M$ $x$ $S_{1}=H(M|g^{r}{\bmod {p)))$
Peggy laskee toisen allekirjoituksen. On huomattava, että toinen allekirjoitus lasketaan modulo . $q$ $S_{2}=r+wS_{1}{\bmod {q))$ .
Peggy lähettää Victorille viestin ja kuvatekstin , . $M$ $S_{1}$ $S_{2}$

Allekirjoituksen vahvistus

Victor laskee (tai jos lasketaan muodossa ). $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 tarkistaa asian . Jos näin on, se pitää allekirjoitusta pätevänä. $H(M|X)=S_{1}$

Tehokkuus

Päälaskutoimitukset allekirjoituksen generoimiseksi suoritetaan esikäsittelyvaiheessa ja laskentavaiheessa , jossa numeroilla ja on bittijärjestys ja parametri on bitti. Viimeinen kertolasku on merkityksetön verrattuna RSA - mallin modulaariseen kertolaskuun . $wS_{1}{\bmod {q))$ $w$ $S_{1}$ $140$ $r$ $72$

Allekirjoituksen varmennus koostuu pääasiassa laskennasta , joka voidaan tehdä modulolaskutoimitusten keskiarvolla, jossa pituus on bitteinä. $X=g^{S_{2}}y^{S_{1}}$ $1,5l+0,25t$ $s$ $l=[log_{2}q]$ $q$

Lyhyempi allekirjoitus vähentää toimintojen määrää allekirjoituksen luomiseen ja vahvistamiseen: Schnorr- ja ElGamal -skeemoissa . $O(\log _{2}q\log _{2}^{2}p)$ $O(\log ^{3}p)$

Esimerkki

Avaimen luominen:

$q=103$ ja . Ja . $p=2267$ $p=22q+1$
Valitaan , joka on kentän elementti . Sitten ja $f=2$ $Z_{2267*}$ ${\frac {p-1}{q}}=22$ $g=2^{22}{\bmod {2}}267=354$
Peggy valitsee sitten avaimen $w=30$ $y=1206$
Peggyn yksityinen avain on , julkinen avain on . $30$ $(103 2267 354 1206)$

Viestin allekirjoitus:

Peggyn on allekirjoitettava viesti . $M = 1000$
Peggy valitsee ja laskee . $r=11$ $g^{r}=354^{11}=630mod2267$
Oletetaan, että viesti on , ja sarjayhteys tarkoittaa . Oletetaan myös, että tämän arvon hajautus tuottaa tiivistelmän . Tämä tarkoittaa . $1000$ $1000630$ $H(1000630)=200$ $S_{1}=200$
Peggy laskee . $S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37$
Peggy lähettää Victorin ja . $M = 1000$ $S_{1}=200$ $S_{2}=37$

Patentit

Schnorr-järjestelmällä on patentteja useissa maissa. Esimerkiksi US #4 995 082, päivätty 19. helmikuuta 1991 (vanhentunut 19. helmikuuta 2008). Vuonna 1993 Sunnyvalen Public Key Partners (PKP) hankki maailmanlaajuiset oikeudet tähän patenttiin. Yhdysvaltojen lisäksi tämä järjestelmä on patentoitu myös useissa muissa maissa.

Kaaviomuutokset

Ernie Brickellin ja Kevin McCurleyn vuonna 1992 tekemä piirimuutos paransi huomattavasti piirin turvallisuutta. Heidän menetelmänsä käyttää numeroa , joka, kuten , on vaikea hajottaa, luvun yksinkertaista jakajaa ja eksponenttielementtiä , joita käytetään myöhemmin allekirjoituksessa. Toisin kuin Schnorr-kaaviossa, heidän menetelmänsä allekirjoitus lasketaan yhtälön avulla $s$ $p-1$ $q$ $p-1$ $\alpha$ $q$ $\mathbb {Z} _{p}^{*}$

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

Edut

Vaikka Brickellin ja McCarleyn muunnos on laskennallisesti vähemmän tehokas kuin Schnorrin menetelmä, tällä menetelmällä on se etu, että se perustuu kahden monimutkaisen ongelman vaikeuteen:

logaritmin laskenta syklisessä alaryhmässä järjestyksen mukaan ; $q$ $\mathbb {Z} _{p}^{*}$
faktorointi . $p-1$

Katso myös

Muistiinpanot

Kirjallisuus

Schnorr CP Tehokas allekirjoitusten luominen älykorteilla. - J. Cryptology, 1991. - S. 161-174.
Schnorr CP Tehokas tunnistus ja allekirjoitukset älykorteille. Kryptologian edistysaskel - CRYPTO'89. Tietojenkäsittelytieteen luentomuistiinpanot 435. - 1990. - S. 239 - 252.
A. Menezes, P. van Oorschot, S. Vanstone. Sovellettavan kryptografian käsikirja. - CRC Press, 1996. - 816 s. - ISBN 0-8493-8523-7 .
Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Varnovsky N. P. Salausprotokollat // Johdatus kryptografiaan / Toimittanut V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkistoitu 25. helmikuuta 2008 Wayback Machinessa

Linkit

RFC 8235

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
Muut	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti