RSASSA-PSS

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 januari 2020; kontroller kräver 2 redigeringar .

RSASSA - PSS ( RSA signatursystem med bilaga - P robabilistiskt signatursystem ) är en asymmetrisk digital signaturalgoritm . Baserat på PSS- kodningsprincipen som föreslogs 1996 av Mihir Bellare och Phillip Rogaway [1] . Infört i PKCS # 1 v2.1- standarden från 2002, utvecklad av RSA Laboratories , USA .

Beskrivning av algoritmen

Låt Alice ( A ) vilja skicka ett meddelande M till Bob ( B ) som intygar det med en elektronisk signatur S . B , efter att ha fått ett meddelande från A , måste verifiera signaturen (kontrollera äktheten).

I den här artikeln hänvisar "hög byte (bit)" till den allra första, vänstra byten (biten). Den "minst signifikanta byten (biten)" hänvisar till den sista högra byten (biten).
En "sträng" ska också förstås som en array, vars element är enkla byte. Således är "strängrepresentationen av talet n " strängen N som erhålls genom att dela upp den binära notationen n i byte. Till exempel:

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

I det här fallet är [1] den höga byten och [2] den låga byten.
Funktionerna för att skapa och verifiera en elektronisk signatur beskrivs nedan.

Skapa en signatur

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

Indata: (n, e, d)  - privat nyckel M - meddelande som ska signeras, sträng Produktion: S  — signatur, sträng med längden k Möjliga misstag: "meddelandet är för långt"; "kodningsfel" Sekvensering:
  1. PSS-kodning: Låt oss tillämpa PSS-Encode- funktionen (som kommer att beskrivas nedan) på strängen M för att få strängen EM med längden x . EM är sådan att bitlängden för heltalsrepresentationen av EM inte överstiger emBits , och zBits för de mest signifikanta bitarna är 0 . EM = PSS-Encode(M,emBits) Observera att längden på EM är (k-1) om emBits är jämnt delbart med 8 och lika med k annars. Om PSS-kodning returnerar ett "meddelande för långt"-fel, visas ett felmeddelande och arbetet stannar. Om PSS-kodning returnerar ett "kodningsfel"-fel, visas ett felmeddelande och arbetet stannar.
  2. RSA-signatur:
    • Tilldela m en heltalsrepresentation av strängen EM .
    m = str-to-int(EM) s = m d mod n
    • Låt oss representera s som en bytesträng med längden k .
    S = int-till-str(s, k)
  3. Utgång S
PSS-kodning

PSS-kodning (M, emBits)

Alternativ: Hash  - hash-funktion , returnerar en bytesträng med längden hLen MGF  - maskgenereringsfunktion. Konverterar en indatabytesträng till en sträng med den givna längden (beskrivs i detalj nedan). sLen  är längden på bytesträngsaltet Indata: M  - meddelande som ska signeras, sträng emBits  är den maximala längden i bitar av heltalsrepresentationen av utmatningssträngen EM , åtminstone (8hLen + 8sLen + 9) Produktion: EM  - kodat meddelande, emLen-längdsträng Möjliga misstag: "meddelandet är för långt"; "kodningsfel" Sekvensering:
  1. Om längden på M är större än den maximalt möjliga längden på inmatningssträngen för den valda hashfunktionen ( byte för SHA-1 ), returneras meddelandet "meddelande för långt" och operationen avslutas.
  2. mHash = Hash(M), sträng med längden hLen .
  3. Om emLen < (hLen + sLen + 2), returneras ett "kodningsfel"-meddelande och arbetet stannar.
  4. Ett slumpmässigt strängsalt med längden sLen genereras ; om sLen = 0 är salt  en tom sträng .
  5. M' = (0x)00 00 00 00 00 00 00 00||mHash||salt , en sträng med längd (8 + hLen + sLen), vars första 8 byte är noll.
  6. H = Hash(M') , sträng med längden hLen .
  7. En PS - sträng genereras bestående av (emLen - hLen - sLen - 2) nollbyte. PS- längden kan vara noll.
  8. DB = PS||0x01||salt , längdsträng (emLen - hLen - 1) .
  9. dbMask = MGF(H, emLen - hLen - 1) , längdsträng (emLen - hLen - 1) .
  10. maskedDB = DB ⊕ dbMask .
  11. ZBits för de höga bitarna i den höga byten av maskedDB är satt till 0 .
  12. TF=0xBC .
  13. EM = maskedDB||H||TF
  14. EM -utgång .

Signaturverifiering

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

Indata: (n, e)  - offentlig nyckel M  - mottaget meddelande, sträng S  är signaturen som ska verifieras, en sträng med längden k Produktion: "signaturen är giltig" eller "signaturen är ogiltig" Sekvensering:
  1. Längdkontroll: Om längden på signaturen S är mer än k byte, fattas beslutet "signaturen är ogiltig", och arbetet avslutas.
  2. RSA-kontroll:
    • Tilldela m en heltalsrepresentation av strängen S .
    m = str-till-int(S)
    • Vi använder den publika nyckeln.
    s = mig mod n
    • Låt oss representera m som en bytesträng med längden emLen.
    EM = int-till-str(m, emLen) Observera att emLen är (k-1) om emBits är jämnt delbart med 8 och lika med k annars. Om posten med numret m tar mer än emLen-byte, fattas beslutet "signaturen är ogiltig", och arbetet stannar.
  3. PSS-kontroll: Låt oss använda PSS-Verify- funktionen (som kommer att beskrivas nedan). Det slutliga beslutet är detsamma som det beslut som PSS-Verify tog . Output = PSS-Verify(M, EM, eBits)
PSS check

PSS-Verifiera(M, EM, eBits)

Alternativ: Hash  är en hashfunktion som returnerar en bytesträng med längden hLen. MGF  - maskgenereringsfunktion. Konverterar en indatabytesträng till en sträng med den givna längden (beskrivs i detalj nedan). sLen  är längden på saltbytesträngen. Indata: M  — mottaget meddelande, sträng. EM  -kodat meddelande, sträng med längd emLen . emBits  är den maximala längden i bitar av en heltalsrepresentation av en EM-sträng, åtminstone (8hLen + 8sLen + 9) . Produktion: "signaturen är giltig" eller "signaturen är ogiltig" Sekvensering:
  1. Om längden M är större än den maximalt möjliga längden på inmatningssträngen för den valda hashfunktionen ( byte för SHA-1), fattas ett "signatur ogiltig" beslut och arbetet stannar.
  2. mHash = Hash(M) , en sträng med längden hLen .
  3. Om emLen < (hLen + sLen + 2) , fattas ett "signatur ogiltig" beslut och arbetet stannar.
  4. Om den låga byten EM (fältet TF ) inte är lika med 0xBC , fattas beslutet "signaturen är ogiltig" och arbetet stoppas.
  5. Högre ( emLen - hLen - 1) EM - byte skrivs till den maskeradeDB- strängen och efterföljande hLen- byte skrivs till H - strängen .
  6. Om de höga zBits- bitarna i den höga byten av maskedDB är icke-noll, så fattas ett "signatur ogiltig"-beslut och arbetet avslutas.
  7. dbMask = MGF(H, emLen - hLen - 1) , längdsträng (emLen - hLen - 1) .
  8. DB = maskedDB ⊕ dbMask .
  9. ZBits för de höga bitarna i den höga byten i DB är satta till 0 .
  10. Om de högre (emLen - hLen - sLen - 2) byten i DB :n inte är lika med 0 eller om den efterföljande byten (byten vid position (emLen - hLen - sLen - 1) , om man antar positionen för den höga byten är 1 ) är inte lika med 0x01 , då fattas ett beslut "signaturen är ogiltig" och arbetet stoppas.
  11. De sista sLen-bytena i DB:n skrivs till saltbytesträngen.
  12. M' = (0x)00 00 00 00 00 00 00 00||mHash||salt , en sträng med längd (8 + hLen + sLen) , vars första 8 byte är noll.
  13. H' = Hash(M') , en sträng med längden hLen.
  14. Om H = H' , så fattas beslutet "signaturen är giltig", annars fattas beslutet "signaturen är ogiltig".

Maskgenereringsfunktion

Låt oss beskriva MGF som används i PSS-funktionerna.
MGF accepterar en bytesträng av godtycklig längd och en önskad längd på utmatningssträngen som inmatning, och producerar en bytesträng med önskad längd. Begränsningar kan införas på längden på ingångs- och utgångssträngarna, men de är vanligtvis mycket stora. MGF är deterministisk; utgångssträngen bestäms helt av ingångssträngen. Utsignalen från MGF bör vara pseudo-slumpmässig, det vill säga, om man känner till en del av utmatningssträngen, bör det vara praktiskt taget omöjligt att förutsäga resten av utmatningssträngen. Detta kan uppnås genom att göra MGF baserad på en hashfunktion med samma egenskap. Denna egenskap är nödvändig, eftersom beviset på algoritmens tillförlitlighet är beroende av den.
Standarden PKCS#1 v2.1 föreslår att följande funktion ska användas som MGF:

MGF1(M,maskLen)

Alternativ: Hash  är en hashfunktion som returnerar en bytesträng med längden hLen. Indata: M  är strängen som ska konverteras. maskLen  är den erforderliga längden på utdatabytesträngen, överstiger inte 2 32 hLen . Produktion: mask  är en sträng av längd maskLen. Möjliga misstag: "Masken är för lång" Sekvensering:
  1. Om maskLen > 2 32 hLen visas meddelandet "masklängden är för stor" och operationen stoppas.
  2. Låt T  vara en tom sträng.
  3. I slingan FÖR i FRÅN 0 TILL UTFÖRS:
    • Låt oss representera i som en C -bytesträng med längden 4 byte.
    C = int-till-str(i,4)
    • M' = M||C .
    • Låt oss lägga till hashresultatet M' i slutet av strängen T.
    T = T||Hash(M')
  4. Låt oss skriva den övre maskenLen byte av sträng T till mask .
  5. Utgången av mask .

Alternativ

I PKCS#1 v2.1 -standarden ges RSASSA-PSS identifieraren id-RSASSA-PSS , med vilken en sekvens av fyra parametrar måste associeras. Dessa parametrar inkluderar hash-funktionen, MGF, längden på den slumpmässigt genererade saltsträngen ( sLen ), trailerField ( TF -fält ). Standardvärdena för dessa parametrar, angivna i standarden i fråga, anges i tabellen.

Parameter Sorts Standardvärde
hashAlgorithm HashAlgorithm sha1
maskGenAlgorithm MaskGenAlgorithm mgf1SHA1
saltLängd HELTAL tjugo
trailerField TrailerField trailerFieldBC
  • Det rekommenderas att hashfunktionen som MGF är baserad på (om någon) är densamma som den som anges av parametern hashAlgorithm .
  • Standardvärdet för parametern saltLength är lika med längden på utgångssträngen för den valda hashfunktionen ( hLen ). Till skillnad från de andra alternativen behöver saltLength inte fixas för ett givet RSA- nyckelpar.
  • TF - fältet introduceras för kompatibilitet med IEEE-utkastet P1363a . I den övervägda standarden stöds endast trailerField- värde lika med 0xBC . Det kan dock också ha en annan form, såsom HID||0xCC , där HID  är en hashfunktionsidentifierare som specificeras i ISO/IEC 10118-standarden.

Funktioner

Den tillåtna meddelandelängden för RSA-PSS-metoden är antingen obegränsad eller begränsad till ett mycket stort värde på grund av hashfunktionen som används i PSS-kodningen.

RSA-PSS skiljer sig från andra RSA-baserade digitala signatursystem genom att det är probabilistiskt snarare än deterministiskt. innebär att man använder ett slumpmässigt genererat värde ( salt ). Värdet på salt ökar kretsens tillförlitlighet [1] .

Tillförlitlighet

Om man antar att beräkning av en godtycklig rotmodul är en operation som är ogenomförbar, och att hashfunktionen och MGF har de nödvändiga egenskaperna, säkerställer RSA-PSS signaturens säkerhet. Robusthet är bevisbar i den meningen att svårigheten att bryta en signatur kan vara direkt relaterad till svårigheten att bryta en kryptografisk primitiv (det matematiska problemet som ligger bakom RSA ). Sannolikheten för framgångsrik sprickning och körtiden för den bästa krackningsmetoden RSA-PSS är mycket nära samma parametrar för algoritmen för att hitta den inversa funktionen av RSA .

Signaturschemat som beskrivits tidigare skiljer sig från den ursprungliga algoritmen som föreslagits av Mihir Bellare och Phillip Rogaway [1] . Det nödvändiga beviset för detta schema tillhandahålls dock av Jacob Jonsson [2] .

Anteckningar

  1. ↑ 1 2 3 Mihir Bellare, Phillip Rogaway "Den exakta säkerheten för digitala signaturer - hur man signerar med RSA och Rabin" . Hämtad 1 november 2010. Arkiverad från originalet 13 juni 2010.
  2. ↑ Jacob Jonsson "Säkerhetsbevis för RSA-PSS-signaturschemat och dess varianter" (PDF) . Hämtad 1 november 2010. Arkiverad från originalet 6 mars 2016.

Källor

 Public key kryptosystem
Algoritmer
Faktorisering av heltal
Diskret logaritm
Kryptografi på galler
Övrig
Teori
Standarder
Ämnen