RSASSA-PSS

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

RSASSA -PSS ( RSA S ignature S cheme with A ppendix- P robabilistic Signature S cheme ) este un algoritm de semnătură digitală asimetric . Pe baza principiului de codificare PSS propus în 1996 de Mihir Bellare și Phillip Rogaway [1] . Introdus în standardul PKCS # 1 v2.1 din 2002, dezvoltat de RSA Laboratories , SUA .

Descrierea algoritmului

Fie ca Alice ( A ) să dorească să-i trimită un mesaj M lui Bob ( B ) care îl certifică cu o semnătură electronică S. B , după ce a primit un mesaj de la A , trebuie să verifice semnătura (verifică autenticitatea).

În acest articol, „octetul mare (bit)” se referă la primul octet (bit) din stânga. „octetul (bit) cel mai puțin semnificativ” se referă, respectiv, la ultimul octet (bit) din dreapta.
De asemenea, un „șir” trebuie înțeles ca o matrice, ale cărei elemente sunt octeți unici. Astfel, „reprezentarea șir a numărului n ” este șirul N obținut prin împărțirea notației binare n în octeți. De exemplu:

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

În acest caz, [1] este octetul înalt, iar [2] este octetul scăzut.
Funcțiile de creare și verificare a unei semnături electronice sunt descrise mai jos.

Crearea unei semnături

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

Date de intrare: (n, e, d)  - cheie privată M - mesaj de semnat, șir Ieșire: S  — semnătură, șir de lungime k Posibile greșeli: „mesajul este prea lung”; "eroare de codare" Secvențiere:
  1. Codare PSS: Să aplicăm funcția PSS-Encode (care va fi descrisă mai jos) șirului M pentru a obține șirul EM de lungime x . EM este astfel încât lungimea de biți a reprezentării întregi a EM nu depășește emBits , iar zBits ai celor mai semnificativi biți sunt 0 . EM = PSS-Encode(M,emBits) Rețineți că lungimea EM este (k-1) dacă emBits este divizibil egal cu 8 și egal cu k în caz contrar. Dacă codificarea PSS returnează o eroare „mesaj prea lung”, este afișat un mesaj de eroare și lucrul se oprește. Dacă codificarea PSS returnează o eroare de „eroare de codificare”, este afișat un mesaj de eroare și lucrul se oprește.
  2. Semnătura RSA:
    • Atribuiți m o reprezentare întreagă a șirului EM .
    m = str-to-int(EM) s = m d mod n
    • Să reprezentăm s ca un șir de octeți de lungime k .
    S = int-to-str(s, k)
  3. Ieșire S
Codificare PSS

PSS-Cod (M, emBits)

Opțiuni: Hash  - funcția hash , returnează un șir de octeți de lungime hLen MGF  - funcție de generare a măștilor. Convertește un șir de octeți de intrare într-un șir de lungime dată (descris în detaliu mai jos). sLen  este lungimea șirului de octeți sare Date de intrare: M  - mesaj de semnat, șir emBits  este lungimea maximă în biți a reprezentării întregi a șirului de ieșire EM , cel puțin (8hLen + 8sLen + 9) Ieșire: EM  - mesaj codificat, șir de lungime emLen Posibile greșeli: „mesajul este prea lung”; "eroare de codare" Secvențiere:
  1. Dacă lungimea lui M este mai mare decât lungimea maximă posibilă a șirului de intrare al funcției hash selectate ( octet pentru SHA-1 ), mesajul „mesaj prea lung” este returnat și operația este încheiată.
  2. mHash = Hash(M), șir de lungime hLen .
  3. Dacă emLen < (hLen + sLen + 2), este returnat un mesaj de „eroare de codificare” și lucrul se oprește.
  4. Este generată o sare aleatorie de lungime sLen ; dacă sLen = 0 , sarea  este un șir gol .
  5. M' = (0x)00 00 00 00 00 00 00 00||mHash||salt , un șir de lungime (8 + hLen + sLen), primii 8 octeți sunt zero.
  6. H = Hash(M') , șir de lungime hLen .
  7. Se generează un șir PS format din (emLen - hLen - sLen - 2) octeți nuli. Lungimea PS poate fi zero.
  8. DB = PS||0x01||sare , șir de lungime (emLen - hLen - 1) .
  9. dbMask = MGF(H, emLen - hLen - 1) , șir de lungime (emLen - hLen - 1) .
  10. maskedDB = DB ⊕ dbMask .
  11. ZBiții biților înalți din octetul înalt al maskedDB sunt setați la 0 .
  12. TF=0xBC .
  13. EM = mascatDB||H||TF
  14. Ieșire EM .

Verificarea semnăturii

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

Date de intrare: (n, e)  - cheie publică M  - mesaj primit, șir S  este semnătura de verificat, un șir de lungime k Ieșire: „semnătura este validă” sau „semnătura este invalidă” Secvențiere:
  1. Verificare lungime: Dacă lungimea semnăturii S este mai mare de k octeți, atunci se ia decizia „semnătura este invalidă” și lucrarea este încheiată.
  2. Verificare RSA:
    • Atribuiți m o reprezentare întreagă a șirului S .
    m = str-to-int(S)
    • Folosim cheia publică.
    s = eu mod n
    • Să reprezentăm m ca un șir de octeți de lungime emLen.
    EM = int-to-str(m, emLen) Rețineți că emLen este (k-1) dacă emBits este divizibil egal cu 8 și egal cu k în caz contrar. Dacă înregistrarea numărului m durează mai mult de emLen octeți, atunci se ia decizia „semnătura este invalidă” și lucrul se oprește.
  3. Verificare PSS: Să folosim funcția PSS-Verify (care va fi descrisă mai jos). Decizia finală este aceeași cu decizia luată de PSS-Verify . Ieșire = PSS-Verify(M, EM, emBits)
Verificare PSS

PSS-Verify(M, EM, emBits)

Opțiuni: Hash  este o funcție hash care returnează un șir de octeți de lungime hLen. MGF  - funcție de generare a măștilor. Convertește un șir de octeți de intrare într-un șir de lungime dată (descris în detaliu mai jos). sLen  este lungimea șirului de octeți de sare. Date de intrare: M  — mesaj primit, șir. Mesaj codificat EM  , șir de lungime emLen . emBits  este lungimea maximă în biți a unei reprezentări întregi a unui șir EM, cel puțin (8hLen + 8sLen + 9) . Ieșire: „semnătura este validă” sau „semnătura este invalidă” Secvențiere:
  1. Dacă lungimea M este mai mare decât lungimea maximă posibilă a șirului de intrare al funcției hash selectate ( octeți pentru SHA-1), se ia o decizie de „semnătură invalidă” și lucrul se oprește.
  2. mHash = Hash(M) , un șir de lungime hLen .
  3. Dacă emLen < (hLen + sLen + 2) , se ia o decizie de „semnătură invalidă” și lucrul se oprește.
  4. Dacă octetul mic EM (câmpul TF ) nu este egal cu 0xBC , atunci decizia „semnătura este invalidă” este luată și lucrul se oprește.
  5. Octeții EM mai mari ( emLen - hLen - 1 ) sunt scrieți în șirul maskedDB , iar octeții hLen următori sunt scrieți în șirul H .
  6. Dacă biții zBits înalți ai octetului înalt al maskedDB sunt non-zero, atunci se ia o decizie de „semnătură invalidă” și lucrul este încheiat.
  7. dbMask = MGF(H, emLen - hLen - 1) , șir de lungime (emLen - hLen - 1) .
  8. DB = maskedDB ⊕ dbMask .
  9. ZBiții biților înalți din octetul înalt al DB sunt setați la 0 .
  10. Dacă octeții mai mari ( emLen - hLen - sLen - 2) ai DB nu sunt egali cu 0 sau dacă octetul următor (octetul la poziția (emLen - hLen - sLen - 1) , presupunând poziția octetului înalt este 1 ) nu este egal cu 0x01 , atunci se ia o decizie „semnătura este invalidă” și lucrarea se oprește.
  11. Ultimii sLen octeți ai DB sunt scrieți în șirul de octeți de sare.
  12. M' = (0x)00 00 00 00 00 00 00 00||mHash||salt , un șir de lungime (8 + hLen + sLen) , dintre care primii 8 octeți sunt zero.
  13. H' = Hash(M') , un șir de lungime hLen.
  14. Dacă H = H' , atunci se ia decizia „semnătura este valabilă”, în caz contrar se ia decizia „semnătura este nevalidă”.

Funcția de generare a măștilor

Să descriem MGF utilizat în funcțiile PSS.
MGF acceptă un șir de octeți de lungime arbitrară și o lungime dorită a șirului de ieșire ca intrare și produce un șir de octeți de lungimea dorită. Limitări pot fi impuse lungimii șirurilor de intrare și de ieșire, dar acestea sunt de obicei foarte mari. MGF este determinist; șirul de ieșire este complet determinat de șirul de intrare. Ieșirea MGF ar trebui să fie pseudo-aleatoare, adică cunoscând o parte a șirului de ieșire, ar trebui să fie practic imposibil să se prezică restul șirului de ieșire. Acest lucru poate fi realizat făcând MGF bazat pe o funcție hash cu aceeași proprietate. Această proprietate este necesară, deoarece dovada fiabilității algoritmului se bazează pe ea.
Standardul PKCS#1 v2.1 propune utilizarea următoarei funcții ca MGF:

MGF1(M,maskLen)

Opțiuni: Hash  este o funcție hash care returnează un șir de octeți de lungime hLen. Date de intrare: M  este șirul care trebuie convertit. maskLen  este lungimea necesară a șirului de octeți de ieșire, nu depășește 2 32 hLen . Ieșire: mask  este un șir de lungime maskLen. Posibile greșeli: „Masca este prea lungă” Secvențiere:
  1. Dacă maskLen > 2 32 hLen , este afișat mesajul „lungimea măștii este prea mare” și operațiunea se oprește.
  2. Fie T  un șir gol.
  3. ÎN bucla PENTRU i DE LA 0 LA SE Efectuează:
    • Să reprezentăm i ca un șir de octeți C cu lungimea de 4 octeți.
    C = int-to-str(i,4)
    • M' = M||C .
    • Să anexăm rezultatul hash M' la sfârșitul șirului T.
    T = T||Hash(M')
  4. Să scriem în maskLen octeții superiori ai șirului T în mask .
  5. Ieșirea măștii .

Opțiuni

În standardul PKCS#1 v2.1 , RSASSA-PSS primește identificatorul id-RSASSA-PSS , cu care trebuie asociată o secvență de patru parametri. Acești parametri includ funcția hash, MGF, lungimea șirului de sare generat aleatoriu ( sLen ), trailerField ( câmp TF ). Valorile implicite ale acestor parametri, date în standardul în cauză, sunt date în tabel.

Parametru Tip de Valoare implicită
hashAlgorithm HashAlgorithm sha1
maskGenAlgorithm MaskGenAlgorithm mgf1SHA1
sareLungime ÎNTREG douăzeci
TrailerField TrailerField trailerFieldBC
  • Se recomandă ca funcția hash pe care se bazează MGF (dacă există) să fie aceeași cu cea specificată de parametrul hashAlgorithm .
  • Valoarea implicită a parametrului saltLength este egală cu lungimea șirului de ieșire al funcției hash selectate ( hLen ). Spre deosebire de celelalte opțiuni, saltLength nu trebuie să fie fixată pentru o anumită pereche de chei RSA .
  • Câmpul TF este introdus pentru compatibilitate cu proiectul IEEE P1363a . În standardul considerat, este acceptată numai valoarea trailerField egală cu 0xBC . Cu toate acestea, poate lua și o altă formă, cum ar fi HID||0xCC , unde HID  este un identificator de funcție hash specificat în standardul ISO/IEC 10118.

Caracteristici

Lungimea permisă a mesajului pentru metoda RSA-PSS este fie nelimitată, fie limitată la o valoare foarte mare datorită funcției hash utilizate în codificarea PSS.

RSA-PSS diferă de alte scheme de semnătură digitală bazate pe RSA prin faptul că este mai degrabă probabilistică decât deterministă. implică utilizarea unei valori generate aleatoriu ( sare ). Valoarea sării sporește fiabilitatea circuitului [1] .

Fiabilitate

Presupunând că calcularea unei rădăcini arbitrare modulo n este o operație care este impracticabilă, iar funcția hash și MGF au proprietățile necesare, RSA-PSS asigură securitatea semnăturii. Robustitatea este dovedibilă în sensul că dificultatea de a sparge o semnătură poate fi direct legată de dificultatea de a sparge o primitivă criptografică (problema matematică care stă la baza RSA ). Probabilitatea de cracare reușită și timpul de rulare a celei mai bune metode de cracare RSA-PSS sunt foarte apropiate de aceiași parametri ai algoritmului de găsire a funcției inverse a RSA .

Schema de semnătură descrisă mai devreme diferă de algoritmul original propus de Mihir Bellare și Phillip Rogaway [1] . Totuși, dovada necesară pentru această schemă este oferită de Jacob Jonsson [2] .

Note

  1. ↑ 1 2 3 Mihir Bellare, Phillip Rogaway „Securitatea exactă a semnăturilor digitale – Cum să semnezi cu RSA și Rabin” . Consultat la 1 noiembrie 2010. Arhivat din original pe 13 iunie 2010.
  2. ↑ Jacob Jonsson „Dovezi de securitate pentru schema de semnătură RSA-PSS și variantele sale” (PDF) . Consultat la 1 noiembrie 2010. Arhivat din original pe 6 martie 2016.

Surse

 Criptosisteme cu cheie publică
Algoritmi
Factorizarea numerelor întregi
Logaritm discret
Criptografia pe zăbrele
Alte
Teorie
Standarde
Subiecte