RASSSA-PSS

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

RSASSA-PSS ( RSA S ignature S scheme with A ppendix- P robabilistic S ignature S cheme ) on epäsymmetrinen digitaalisen allekirjoituksen algoritmi . Perustuu Mihir Bellaren ja Phillip Rogawayn vuonna 1996 ehdottamaan PSS -koodausperiaatteeseen [1] . Sisällytetty vuoden 2002 PKCS # 1 v2.1 -standardiin , jonka on kehittänyt RSA Laboratories , USA .

Algoritmin kuvaus

Anna Alice ( A ) lähettää Bobille ( B ) viestin M , joka varmentaa sen sähköisellä allekirjoituksella S. B :n, saatuaan viestin A :lta , tulee tarkistaa allekirjoitus (tarkistaa aitous).

Tässä artikkelissa "korkea tavu (bitti)" viittaa aivan ensimmäiseen vasempaan tavuun (bittiin). "Vähiten merkitsevä tavu (bitti)" tarkoittaa vastaavasti viimeistä oikeaa tavua (bittiä).
Myös "merkkijono" tulee ymmärtää taulukona, jonka elementit ovat yksittäisiä tavuja. Siten "luvun n merkkijonoesitys" on merkkijono N , joka saadaan jakamalla binäärimerkintä n tavuiksi. Esimerkiksi:

n = 258 {100000010} N = [1|2] {00000001|00000010}

Tässä tapauksessa [1] on korkea tavu ja [2] on alhainen tavu.
Sähköisen allekirjoituksen luomisen ja tarkistamisen toiminnot on kuvattu alla.

Allekirjoituksen luominen

RSASSA-PSS-Sign((n, e, d), M)

Syöttötiedot: (n, e, d)  - yksityinen avain M - allekirjoitettava viesti, merkkijono Lähtö: S  — allekirjoitus, merkkijono, jonka pituus on k Mahdolliset virheet: "viesti on liian pitkä"; "koodausvirhe" Jaksotus:
  1. PSS-koodaus: Sovelletaan PSS-Encode- funktiota (joka kuvataan alla) merkkijonoon M saadaksesi merkkijonon EM , jonka pituus on x . EM on sellainen, että EM:n kokonaislukuesityksen bittipituus ei ylitä emBittejä ja merkittävimpien bittien zBitit ovat 0 . EM = PSS-koodaus (M, emBits) Huomaa, että EM :n pituus on (k-1) , jos emBits on tasaisesti jaollinen 8 :lla ja muussa tapauksessa yhtä suuri kuin k . Jos PSS-koodaus palauttaa "viesti liian pitkä" -virheen, näyttöön tulee virheilmoitus ja työ pysähtyy. Jos PSS-koodaus palauttaa "koodausvirheen", näyttöön tulee virheilmoitus ja työ pysähtyy.
  2. RSA-allekirjoitus:
    • Määritä m kokonaislukuesitys merkkijonolle EM .
    m = str-to-int(EM) s = m d mod n
    • Esitetään s tavumerkkijonona, jonka pituus on k .
    S = int-to-str(s, k)
  3. Lähtö S
PSS-koodaus

PSS-koodaus (M, emBits)

Vaihtoehdot: Hash  - hash-funktio , palauttaa tavumerkkijonon, jonka pituus on hLen MGF  - maskin generointitoiminto. Muuntaa syötetyn tavumerkkijonon tietynpituiseksi merkkijonoksi (kuvattu yksityiskohtaisesti alla). sLen on tavumerkkijonon suolan  pituus Syöttötiedot: M  - allekirjoitettava viesti, merkkijono emBits on lähtömerkkijonon EM  kokonaislukuesityksen enimmäispituus bitteinä , vähintään (8hLen + 8sLen + 9) Lähtö: EM  - koodattu viesti, emLen- pituusmerkkijono Mahdolliset virheet: "viesti on liian pitkä"; "koodausvirhe" Jaksotus:
  1. Jos M :n pituus on suurempi kuin valitun hash-funktion syötemerkkijonon suurin mahdollinen pituus ( tavu SHA-1 : lle), palautetaan viesti "viesti liian pitkä" ja toiminto lopetetaan.
  2. mHash = Hash(M), merkkijono, jonka pituus on hLen .
  3. Jos emLen < (hLen + sLen + 2), "koodausvirhe" palautetaan ja työ pysähtyy.
  4. Syntyy satunnainen merkkijonosuola , jonka pituus on sLen ; jos sLen = 0 , suola  on tyhjä merkkijono .
  5. M' = (0x)00 00 00 00 00 00 00 00||mHash||suola , merkkijono, jonka pituus on (8 + hLen + sLen), jonka 8 ensimmäistä tavua ovat nollia.
  6. H = Hash(M') , merkkijono, jonka pituus on hLen .
  7. Luodaan PS -merkkijono, joka koostuu (emLen - hLen - sLen - 2) nollatavuista . PS:n pituus voi olla nolla.
  8. DB = PS||0x01||suola , merkkijono pituus (emLen - hLen - 1) .
  9. dbMask = MGF(H, emLen - hLen - 1) , merkkijono pituus (emLen - hLen - 1) .
  10. maskedDB = DB ⊕ dbMask .
  11. MaskedDB: n korkean tavun korkeiden bittien zBitit asetetaan arvoon 0 .
  12. TF=0xBC .
  13. EM = maskedDB||H||TF
  14. EM- lähtö .

Allekirjoituksen vahvistus

RSASSA-PSS-Verify((n, e), M, S)

Syöttötiedot: (n, e)  - julkinen avain M  - vastaanotettu viesti, merkkijono S  on varmennettava allekirjoitus, merkkijono, jonka pituus on k Lähtö: "allekirjoitus on voimassa" tai "allekirjoitus on virheellinen" Jaksotus:
  1. Pituuden tarkistus: Jos allekirjoituksen S pituus on yli k tavua, tehdään päätös "allekirjoitus virheellinen" ja työ lopetetaan.
  2. RSA-tarkastus:
    • Määritä m kokonaislukuesitys merkkijonolle S .
    m = str-to-int(S)
    • Käytämme julkista avainta.
    s = me mod n
    • Esitetään m tavumerkkijonona, jonka pituus on emLen.
    EM = int-to-str(m, emLen) Huomaa, että emLen on (k-1) , jos emBits on tasaisesti jaollinen 8 :lla ja muussa tapauksessa yhtä suuri kuin k . Jos luvun m tietue vie enemmän kuin emLen tavua, tehdään päätös "allekirjoitus virheellinen" ja työ pysähtyy.
  3. PSS-tarkistus: Käytetään PSS-Verify- toimintoa (joka kuvataan alla). Lopullinen päätös on sama kuin PSS-Verifyn tekemä päätös . Lähtö = PSS-Verify(M, EM, emBits)
PSS-tarkistus

PSS-Verify (M, EM, emBits)

Vaihtoehdot: Hash  on hash-funktio, joka palauttaa tavujonon, jonka pituus on hLen. MGF  - maskin generointitoiminto. Muuntaa syötetyn tavumerkkijonon tietynpituiseksi merkkijonoksi (kuvattu yksityiskohtaisesti alla). sLen  on suolatavumerkkijonon pituus. Syöttötiedot: M  — vastaanotettu viesti, merkkijono. EM  - koodattu viesti, merkkijono pituus emLen . emBits  on EM-merkkijonon kokonaislukuesityksen maksimipituus bitteinä, vähintään (8hLen + 8sLen + 9) . Lähtö: "allekirjoitus on voimassa" tai "allekirjoitus on virheellinen" Jaksotus:
  1. Jos pituus M on suurempi kuin valitun hash-funktion syötemerkkijonon suurin mahdollinen pituus ( tavuja SHA-1:lle), tehdään "allekirjoitusvirheellinen" päätös ja työ pysähtyy.
  2. mHash = Hash(M) , merkkijono, jonka pituus on hLen .
  3. Jos emLen < (hLen + sLen + 2) , tehdään "allekirjoitus virheellinen" päätös ja työ pysähtyy.
  4. Jos alhainen tavu EM (kenttä TF ) ei ole yhtä suuri kuin 0xBC , tehdään päätös "allekirjoitus on virheellinen" ja työ pysähtyy.
  5. Korkeammat ( emLen - hLen - 1) EM - tavut kirjoitetaan maskedDB -merkkijonoon ja seuraavat hLen- tavut kirjoitetaan H -merkkijonoon .
  6. Jos maskedDB:n korkean tavun korkeat zBits -bitit ovat nollasta poikkeavat, tehdään "allekirjoitusvirheellinen" päätös ja työ lopetetaan.
  7. dbMask = MGF(H, emLen - hLen - 1) , merkkijono pituus (emLen - hLen - 1) .
  8. DB = maskedDB ⊕ dbMask .
  9. DB:n korkean tavun korkeiden bittien zBitit asetetaan arvoon 0 .
  10. Jos DB : n korkeammat (emLen - hLen - sLen - 2) tavut eivät ole yhtä suuria kuin 0 tai jos seuraava tavu (paikassa oleva tavu (emLen - hLen - sLen - 1) , olettaen, että korkean tavun sijainti on 1 ) ei ole yhtä suuri kuin 0x01 , silloin tehdään päätös "allekirjoitus on virheellinen" ja työ pysähtyy.
  11. DB:n viimeiset sLen-tavut kirjoitetaan suolatavumerkkijonoon.
  12. M' = (0x)00 00 00 00 00 00 00 00||mHash||suola , merkkijono, jonka pituus on (8 + hLen + sLen) , jonka ensimmäiset 8 tavua ovat nollia.
  13. H' = Hash(M') , merkkijono, jonka pituus on hLen.
  14. Jos H = H' , niin tehdään päätös "allekirjoitus on voimassa", muuten päätös "allekirjoitus ei kelpaa".

Maskin luontitoiminto

Kuvataan PSS-funktioissa käytetty MGF.
MGF hyväksyy syötteeksi mielivaltaisen pituisen tavumerkkijonon ja halutun pituisen tulostejonon ja tuottaa halutun pituisen tavujonon. Syöttö- ja lähtömerkkijonojen pituuksille voidaan asettaa rajoituksia, mutta ne ovat yleensä hyvin suuria. MGF on deterministinen; lähtömerkkijono määräytyy täysin tulomerkkijonon mukaan. MGF:n lähdön tulee olla näennäissatunnainen, eli kun osa tulostemerkkijonosta tiedetään, lopputulosten merkkijonon ennustaminen on käytännössä mahdotonta. Tämä voidaan saavuttaa tekemällä MGF perustuen hash-funktioon, jolla on sama ominaisuus. Tämä ominaisuus on välttämätön, koska algoritmin luotettavuuden todiste perustuu siihen.
PKCS #1 v2.1 -standardi ehdottaa seuraavan funktion käyttöä MGF:nä:

MGF1 (M, maskiLen)

Vaihtoehdot: Hash  on hash-funktio, joka palauttaa tavujonon, jonka pituus on hLen. Syöttötiedot: M  on muunnettava merkkijono. maskLen  on vaadittu tulostetavumerkkijonon pituus, ei ylitä 2 32 hLen . Lähtö: maski  on merkkijono pituus maskLen. Mahdolliset virheet: "Naamari on liian pitkä" Jaksotus:
  1. Jos maskLen > 2 32 hLen , viesti "maskin pituus on liian suuri" tulee näkyviin ja toiminto pysähtyy.
  2. Olkoon T  tyhjä merkkijono.
  3. Silmukassa FOR i 0 - 0 SUORITAAN:
    • Esitetään i C - tavuisena merkkijonona , jonka pituus on 4 tavua.
    C = int-to-str(i,4)
    • M' = M||C .
    • Liitä hajautustulos M' merkkijonon T loppuun .
    T = T||Hash(M')
  4. Kirjoitetaan ylempi maskLen tavu merkkijonosta T maskiin .
  5. Maskin tulos .

Vaihtoehdot

PKCS#1 v2.1 -standardissa RSASSA-PSS: lle annetaan tunniste id-RSASSA-PSS , johon on liitettävä neljän parametrin sarja. Näitä parametreja ovat muun muassa hash-funktio, MGF, satunnaisesti luodun suolajonon pituus ( sLen ), trailerField ( TF -kenttä ). Näiden parametrien oletusarvot, jotka on annettu kyseisessä standardissa, on annettu taulukossa.

Parametri Tyyppi Oletusarvo
hashAlgoritmi HashAlgoritmi sha1
maskGenAlgoritm MaskGenAlgoritm mgf1SHA1
suolan pituus KOKONAISLUKU kaksikymmentä
trailerField TrailerField trailerFieldBC
  • On suositeltavaa, että hash-funktio, johon MGF perustuu (jos sellainen on), on sama kuin hashAlgorithm- parametrin määrittämä .
  • SaltLength- parametrin oletusarvo on yhtä suuri kuin valitun hash-funktion ( hLen ) tulostemerkkijonon pituus. Toisin kuin muut vaihtoehdot, saltLengthiä ei tarvitse määrittää tietylle RSA - avainparille.
  • TF - kenttä otetaan käyttöön yhteensopivuuden vuoksi IEEE-luonnoksen P1363a :n kanssa . Tarkasteltavassa standardissa tuetaan vain trailerField- arvoa, joka on yhtä suuri kuin 0xBC . Se voi kuitenkin olla myös muussa muodossa, kuten HID||0xCC , jossa HID  on ISO/IEC 10118 -standardissa määritetty hash-funktion tunniste.

Ominaisuudet

Sallittu viestin pituus RSA-PSS-menetelmälle on joko rajoittamaton tai rajoitettu erittäin suureen arvoon johtuen PSS-koodauksessa käytetystä hash-funktiosta.

RSA-PSS eroaa muista RSA-pohjaisista digitaalisista allekirjoitusmenetelmistä siinä, että se on todennäköisyyspohjainen eikä deterministinen. sisältää satunnaisesti luodun arvon ( suola ) käyttämisen. Suolan arvo lisää piirin luotettavuutta [1] .

Luotettavuus

Olettaen, että mielivaltaisen juurimoduulin laskeminen on operaatio, joka on mahdotonta toteuttaa ja että hash-funktiolla ja MGF:llä on tarvittavat ominaisuudet, RSA-PSS varmistaa allekirjoituksen turvallisuuden. Vakavuus on todistettavissa siinä mielessä, että allekirjoituksen rikkomisen vaikeus voi liittyä suoraan kryptografisen primitiivin rikkomisen vaikeuteen ( RSA :n taustalla oleva matemaattinen ongelma ). Onnistuneen krakkauksen todennäköisyys ja parhaan krakkausmenetelmän RSA-PSS ajoaika ovat hyvin lähellä RSA :n käänteisfunktion löytämisalgoritmin samoja parametreja .

Aiemmin kuvattu allekirjoitusmalli eroaa alkuperäisestä Mihir Bellaren ja Phillip Rogawayn ehdottamasta algoritmista [1] . Jacob Jonsson [2] tarjoaa kuitenkin tarvittavan todisteen tälle järjestelmälle .

Muistiinpanot

  1. ↑ 1 2 3 Mihir Bellare, Phillip Rogaway "Digitaalisten allekirjoitusten tarkka turvallisuus – kuinka allekirjoittaa RSA:n ja Rabinin kanssa" . Haettu 1. marraskuuta 2010. Arkistoitu alkuperäisestä 13. kesäkuuta 2010.
  2. ↑ Jacob Jonsson "Turvallisuustodisteet RSA-PSS-allekirjoitusjärjestelmälle ja sen muunnelmille" (PDF) . Haettu 1. marraskuuta 2010. Arkistoitu alkuperäisestä 6. maaliskuuta 2016.

Lähteet

 Julkisen avaimen salausjärjestelmät
Algoritmit
Kokonaislukujen faktorointi
Diskreetti logaritmi
Kryptografia ristikoilla
Muut
Teoria
Standardit
Aiheet