Rabinin allekirjoituksen todennäköisyyskaavio

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

Rabinin todennäköisyyspohjainen allekirjoitusmenetelmä on Michael O. Rabinin vuonna 1979 alun perin ehdottama digitaalinen allekirjoitusmenetelmä [1] . Rabinin allekirjoitusmalli oli yksi ensimmäisistä ehdotetuista digitaalisista allekirjoitusmenetelmistä, ja se on ainoa, joka yhdistää suoraan allekirjoituksen väärentämisen monimutkaisuuden kokonaislukujen tekijöiden jakamisongelmaan . Rabinin allekirjoitusalgoritmi ei sovellu satunnaiseen oraakkelilaskentamalliin , jossa oletetaan, että kokonaislukujen tekijöiden muodostusongelma on ratkaisematon. Rabinin allekirjoitusjärjestelmä liittyy myös läheisesti Rabinin salausjärjestelmään .

Alkuperäinen algoritmi

Avaimen sukupolvi
- Alkuluvut valitaan , kukin suunnilleen bitin kokoinen, ja tulo lasketaan . $s$ $q$ $k/2$ $n=p\cdot q$
- Seuraavaksi valitaan satunnainen joukosta . $b$ $\{1,\ldots ,n\}$
- Julkinen avain on pari . ${\näyttötyyli (n,b)}$
- yksityinen avain, vastaavasti . $(p,q)$
Allekirjoitus
- Viestin allekirjoittamista varten valitaan ja lasketaan satunnaisluku . $m$ $U$ $m\cdot U\mod n$
- Sitten yhtälö on ratkaistu . $x(x+b)\mod n=m\cdot U\mod n$
- Jos yhtälölle ei ole ratkaisua, valitaan uusi arvo ja yhtälö ratkaistaan uudelleen. $U$
- Viestin allekirjoitus on pariskunta $m$ ${\näyttötyyli (U,x)}$
Tutkimus
- Viestin ja allekirjoituksen perusteella todentaja suorittaa laskelmia ja tarkistaa sitten, että ne ovat yhtä suuret. $m$ ${\näyttötyyli (U,x)}$ $V$ $x(x+b)modn$ $m\cdot U\mod n$

Alkuperäinen algoritmi ei käytä hash-funktioita ja sitä pidetään epäluotettavana. [2]

Turvallinen ja yksinkertaistettu algoritmi

Turvallinen algoritmi [3] perustuu törmäyksenkestävään hash-funktioon . $H:\{0,1\}^{*}\rightarrow \{0,1\}^{k}$

Useimmissa näkymissä algoritmi on yksinkertaistettu valitsemalla . Oletetaan, että hajautusfunktio tulosbittien lukumäärällä on satunnainen oraakkeli ja algoritmi toimii seuraavasti: $b=0$ $H$ $k$

Avaimen sukupolvi

Valitaan alkuluvut , joista jokainen on suunnilleen bitin kokoinen, ja mod 4 on yhtä suuri kuin 3. Seuraavaksi lasketaan tulo . $s$ $q$ $k/2$ $s$ $q$ $n=p\cdot q$
Julkinen avain tässä tapauksessa on . $n$
Yksityinen avain on pari . $(p,q)$

Allekirjoitus

Viestin allekirjoittamista varten valitaan ja lasketaan satunnaisluku . $m$ $U$ $H(m,U)$
Jos ei ole neliömoduuli , valitaan uusi arvo . $H(m,U)$ $n$ $U$
Sen jälkeen löydetään yksi x-arvo, joka on yhtälön ratkaisu . $x^{2}=H(m,U)\mod n$
Viestin allekirjoitus on pari . $m$ ${\näyttötyyli (U,x)}$

Tutkimus

Viestin ja allekirjoituksen perusteella todentaja suorittaa laskelmia ja tarkistaa sitten, että ne ovat yhtä suuret. $m$ ${\näyttötyyli (U,x)}$ $V$ $x^{2}modn$ $H(m,U)$

Muistiinpanot

Joissakin algoritmin toteutuksissa arvoa ei käytetä. Sen sijaan on mahdollista kertoa hash-arvo kahdella numerolla a tai b ominaisuuksilla ja , jossa tarkoittaa Legendre-symbolia . Tällöin mille tahansa modulolle vain yksi neljästä numerosta on neliön muotoinen modulo , ja juuri tämä numero valitaan viestin digitaaliseen allekirjoitukseen. $U$ $\left({\tfrac {a}{p}}\right)=-\left({\tfrac {a}{q}}\right)=-1$ $\left({\tfrac {b}{q}}\right)=-\left({\tfrac {b}{p}}\right)=-1$ $(\cdot )$ $H$ $n$ ${\näyttötyyli H,aH,bH,abH}$ $n$

Algoritmin yksinkertaistamiseksi entisestään sinun on muutettava viestiä, kunnes allekirjoitus läpäisee vahvistuksen. $m$

\\ Viestinmuutostoiminto allekirjoituksen vahvistukselle def root ( m : str , p , q ) : while True : x = h ( m ) sig = pow ( p , q - 2 , q ) * p * pow ( x , ( q ) _ + 1 ) / 4 , q ) sig = ( pow ( q , p - 2 , p ) * q * pow ( x , ( p + 1 ) / 4 , p ) + sig ) % ( nrabin ) if ( sig * sig ) ) % nrabin == x : print ( "Kirjoita laajennettu viesti tiedostoon m.txt" ) f = open ( 'm.txt' , 'w' ) f . kirjoita ( m ) f . sulje () tauko m = m + ' ' paluu sig

Turvallisuus

Jos hash-funktio on satunnainen oraakkeli, eli sen tulos on todella satunnainen paikassa , niin allekirjoituksen väärentäminen mille tahansa viestille on yhtä vaikeaa kuin satunnaiselementin neliöjuuren laskeminen kohteesta . $H$ $\mathbb {Z} /n\mathbb {Z}$ $m$ $\mathbb {Z} /n\mathbb {Z}$

Sen todistamiseksi [4] , että satunnaisen neliöjuuren saaminen on yhtä vaikeaa kuin tekijöiden laskeminen, on huomattava, että useimmissa tapauksissa neliöjuuria on neljä, koska sillä on kaksi neliöjuurta modulo ja kaksi neliöjuurta modulo , ja jokainen pari antaa neliöjuuren modulo kiinalaisen jäännöslauseen mukaan . Joillakin juurilla voi olla sama arvo, mutta tämän todennäköisyys on erittäin pieni. $n$ $s$ $q$ $n$

Jos on mahdollista löytää kaksi erilaista neliöjuurta niin, että mutta , niin tämä johtaa välittömästi tekijöihin , koska alkutekijät ovat jaollisia : llä , mutta eivät jaollisia. Joten laskelma johtaa ei-triviaaliin tekijöihin . $x$ $y$ $x^{2}=y^{2}\mod n$ $x\neq \pm y\mod n$ $n$ $n$ $x^{2}-y^{2}=(xy)(x+y)$ $\operaattorin nimi {gcd} (x\pm y,n)$ $n$

Nyt oletetaan, että on olemassa tehokas algoritmi ainakin yhden neliöjuuren löytämiseksi. Sitten valitaan satunnainen modulo ja neliötetään , algoritmin käytön jälkeen otetaan modulon neliöjuuri ja saadaan uusi juuri , joka todennäköisyydellä 50 % . $r$ $n$ $r^{2}=R\mod n$ $R$ $n$ $r^\prime$ $r\neq \pm r^{\prime }\mod n$

Katso myös

Muistiinpanot

↑ Digitalisoidut allekirjoitukset ja julkisen avaimen toiminnot yhtä vaikeasti hoidettavissa kuin faktorointi (linkkiä ei ole saatavilla)
↑ | Michele Elia, Davide Schipani, On the Rabin Signature c.1-3 . Haettu 13. joulukuuta 2019. Arkistoitu alkuperäisestä 22. syyskuuta 2019. (määrätön)
↑ | Michele Elia, Davide Schipani, On the Rabin Signature n.5-9 . Haettu 13. joulukuuta 2019. Arkistoitu alkuperäisestä 22. syyskuuta 2019. (määrätön)
↑ Digitaaliset allekirjoitukset ja julkisen avaimen toiminnot yhtä vaikeasti hoidettavissa kuin faktorointi c.15-19 (linkki ei ole käytettävissä)

Kirjallisuus

Michele Elia, Davide Schipani, On the Rabin Signature , 2011 PDF
Buchmann, Johannes. Einführung in die Kryptographie . toinen painos. Berliini: Springer, 2001. ISBN 3-540-41283-2
Menezes, Alfred; van Oorschot, Paul C.; ja Vanstone, Scott A. Handbook of Applied Cryptography . CRC Press, lokakuu 1996. ISBN 0-8493-8523-7
Rabin, Michael. Digitalisoidut allekirjoitukset ja julkisen avaimen toiminnot yhtä vaikeasti hoidettavissa kuin faktorointi (PDF-muodossa). MIT Laboratory for Computer Science, tammikuu 1979.
Scott Lindhurst, Shankin algoritmin analyysi neliöjuurien laskemiseksi äärellisissä kentissä. julkaisussa R Gupta ja KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, osa 19 CRM Proc & Lec Notes, AMS, elokuu 1999.
R Kumanduri ja C Romero, Number Theory w/ Computer Applications, Alg 9.2.9, Prentice Hall, 1997. Todennäköisyys neliöjuurelle neliöjuurelle modulo a alkuluku.

Linkit

Lähde

Smart N. Kryptografia. - M .: Technosfera, 2005. S. 525.