RSASSA-PSS

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. ledna 2020; kontroly vyžadují 2 úpravy .

RSASSA- PSS ( schéma podpisu RSA s dodatkem – schéma pravděpodobnostního podpisu ) je asymetrický algoritmus digitálního podpisu . Založeno na principu kódování PSS , který v roce 1996 navrhli Mihir Bellare a Phillip Rogaway [1] . Zavedeno do standardu PKCS # 1 v2.1 z roku 2002, vyvinutého společností RSA Laboratories , USA .

Popis algoritmu

Nechte Alice ( A ) poslat zprávu M Bobovi ( B ) , která ji potvrdí elektronickým podpisem S. B po obdržení zprávy od A musí ověřit podpis (zkontrolovat pravost).

V tomto článku "vysoký bajt (bit)" odkazuje na úplně první levý bajt (bit). „Nejméně významný bajt (bit)“ odkazuje na poslední pravý bajt (bit).
Také "řetězec" by měl být chápán jako pole, jehož prvky jsou jednotlivé bajty. Tedy "řetězcová reprezentace čísla n " je řetězec N získaný rozdělením binárního zápisu n na bajty. Například:

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

V tomto případě je [1] horní bajt a [2] dolní bajt.
Funkce vytváření a ověřování elektronického podpisu jsou popsány níže.

Vytvoření podpisu

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

Vstupní data: (n, e, d)  - soukromý klíč M - zpráva k podpisu, řetězec Výstup: S  — podpis, řetězec délky k Možné chyby: "zpráva je příliš dlouhá"; "chyba kódování" Sekvenční řazení:
  1. PSS kódování: Aplikujme funkci PSS-Encode (která bude popsána níže) na řetězec M , abychom získali řetězec EM délky x . EM je taková, že bitová délka celočíselné reprezentace EM nepřesahuje emBits a zBits nejvýznamnějších bitů je 0 . EM = PSS-Encode(M,emBits) Všimněte si, že délka EM je (k-1) , pokud je emBits rovnoměrně dělitelný 8 a jinak se rovná k . Pokud kódování PSS vrátí chybu „příliš dlouhá zpráva“, zobrazí se chybová zpráva a práce se zastaví. Pokud kódování PSS vrátí chybu „chyba kódování“, zobrazí se chybová zpráva a práce se zastaví.
  2. Podpis RSA:
    • Přiřaďte m celočíselnou reprezentaci řetězce EM .
    m = str-to-int (EM) s = m d mod n
    • Představme s jako bajtový řetězec délky k .
    S = int-to-str(s, k)
  3. Výstup S
PSS kódování

PSS-Encode(M, emBits)

Možnosti: Hash  - hash function , vrací bajtový řetězec délky hLen MGF  - funkce generování masky. Převede vstupní bajtový řetězec na řetězec dané délky (podrobně popsáno níže). sLen  je délka soli bajtového řetězce Vstupní data: M  - zpráva k podpisu, řetězec emBits  je maximální délka v bitech reprezentace celého čísla výstupního řetězce EM , alespoň (8hLen + 8sLen + 9) Výstup: EM  - kódovaná zpráva, řetězec délky emLen Možné chyby: "zpráva je příliš dlouhá"; "chyba kódování" Sekvenční řazení:
  1. Pokud je délka M větší než maximální možná délka vstupního řetězce zvolené hashovací funkce ( bajt pro SHA-1 ), vrátí se zpráva „příliš dlouhá zpráva“ a operace je ukončena.
  2. mHash = Hash(M), řetězec délky hLen .
  3. Pokud emLen < (hLen + sLen + 2), vrátí se zpráva „chyba kódování“ a práce se zastaví.
  4. Vygeneruje se náhodná sůl řetězce délky sLen ; pokud sLen = 0 , salt  je prázdný řetězec .
  5. M' = (0x)00 00 00 00 00 00 00 00||mHash||salt , řetězec délky (8 + hLen + sLen), jehož prvních 8 bajtů je nula.
  6. H = Hash(M') , řetězec délky hLen .
  7. Vygeneruje se řetězec PS sestávající z (emLen - hLen - sLen - 2) prázdných bajtů. Délka PS může být nulová.
  8. DB = PS||0x01||sůl , řetězec délky (emLen - hLen - 1) .
  9. dbMask = MGF(H, emLen - hLen - 1) , řetězec délky (emLen - hLen - 1) .
  10. maskedDB = DB ⊕ dbMask .
  11. ZBits horních bitů ve vysokém bajtu maskedDB jsou nastaveny na 0 .
  12. TF=0xBC .
  13. EM = maskovanýDB||H||TF
  14. EM výstup .

Ověření podpisu

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

Vstupní data: (n, e)  - veřejný klíč M  - přijatá zpráva, řetězec S  je podpis, který má být ověřen, řetězec délky k Výstup: „podpis je platný“ nebo „podpis je neplatný“ Sekvenční řazení:
  1. Kontrola délky: Pokud je délka podpisu S větší než k bajtů, dojde k rozhodnutí „podpis je neplatný“ a práce je ukončena.
  2. Kontrola RSA:
    • Přiřaďte m celočíselnou reprezentaci řetězce S .
    m = str-to-int(S)
    • Používáme veřejný klíč.
    s = mě mod n
    • Představme si m jako bajtový řetězec délky emLen.
    EM = int-to-str(m, emLen) Všimněte si, že emLen je (k-1) , pokud je emBits rovnoměrně dělitelný 8 a jinak se rovná k . Pokud záznam čísla m zabere více než emLen bajtů, dojde k rozhodnutí „podpis je neplatný“ a práce se zastaví.
  3. Kontrola PSS: Použijme funkci PSS-Verify (která bude popsána níže). Konečné rozhodnutí je stejné jako rozhodnutí PSS-Verify . Výstup = PSS-Verify (M, EM, emBits)
Kontrola PSS

PSS-Verify (M, EM, emBits)

Možnosti: Hash  je hashovací funkce, která vrací bajtový řetězec délky hLen. MGF  - funkce generování masky. Převede vstupní bajtový řetězec na řetězec dané délky (podrobně popsáno níže). sLen  je délka řetězce bajtů soli. Vstupní data: M  — přijatá zpráva, řetězec. EM  - zakódovaná zpráva, řetězec délky emLen . emBits  je maximální délka v bitech celočíselné reprezentace EM řetězce, alespoň (8hLen + 8sLen + 9) . Výstup: „podpis je platný“ nebo „podpis je neplatný“ Sekvenční řazení:
  1. Pokud je délka M větší než maximální možná délka vstupního řetězce vybrané hashovací funkce ( bajtů pro SHA-1), dojde k rozhodnutí o "neplatnosti podpisu" a práce se zastaví.
  2. mHash = Hash(M) , řetězec délky hLen .
  3. Pokud emLen < (hLen + sLen + 2) , dojde k rozhodnutí o „neplatnosti podpisu“ a práce se zastaví.
  4. Pokud se dolní bajt EM (pole TF ) nerovná 0xBC , dojde k rozhodnutí "podpis je neplatný" a práce se zastaví.
  5. Vyšší ( emLen - hLen - 1) EM bajty jsou zapsány do maskedDB řetězce a následné hLen bajty jsou zapsány do H řetězce .
  6. Pokud jsou vysoké bity zBits vysokého bajtu maskovanéDB nenulové, pak je učiněno rozhodnutí o "neplatnosti podpisu" a práce je ukončena.
  7. dbMask = MGF(H, emLen - hLen - 1) , řetězec délky (emLen - hLen - 1) .
  8. DB = maskedDB ⊕ dbMask .
  9. ZBits horních bitů ve vysokém bajtu DB jsou nastaveny na 0 .
  10. Pokud vyšší (emLen - hLen - sLen - 2) bajty DB nejsou rovny 0 nebo pokud následující bajt (byte na pozici (emLen - hLen - sLen - 1) , za předpokladu, že pozice vysokého bajtu je 1 ) se nerovná 0x01 , pak se rozhodne "podpis je neplatný" a práce se zastaví.
  11. Poslední bajty sLen DB jsou zapsány do řetězce bajtů salt.
  12. M' = (0x)00 00 00 00 00 00 00 00||mHash||salt , řetězec délky (8 + hLen + sLen) , jehož prvních 8 bajtů je nula.
  13. H' = Hash(M') , řetězec délky hLen.
  14. Je-li H = H' , pak je učiněno rozhodnutí "podpis je platný", jinak rozhodnutí "podpis je neplatný".

Funkce generování masky

Pojďme si popsat MGF použitý ve funkcích PSS.
MGF přijímá jako vstup bajtový řetězec libovolné délky a požadovanou délku výstupního řetězce a vytváří bajtový řetězec požadované délky. Délkám vstupních a výstupních řetězců lze uložit omezení, ale obvykle jsou velmi velké. MGF je deterministický; výstupní řetězec je zcela určen vstupním řetězcem. Výstup MGF by měl být pseudonáhodný, to znamená, že při znalosti části výstupního řetězce by mělo být prakticky nemožné předpovědět zbytek výstupního řetězce. Toho lze dosáhnout vytvořením MGF založeného na hashovací funkci se stejnou vlastností. Tato vlastnost je nezbytná, protože se na ní spoléhá důkaz spolehlivosti algoritmu.
Standard PKCS#1 v2.1 navrhuje použít jako MGF následující funkci:

MGF1(M,maskaLen)

Možnosti: Hash  je hashovací funkce, která vrací bajtový řetězec délky hLen. Vstupní data: M  je řetězec, který se má převést. maskLen  je požadovaná délka výstupního bajtového řetězce, nepřesahuje 2 32 hLen . Výstup: mask  je řetězec délky maskLen. Možné chyby: "Maska je příliš dlouhá" Sekvenční řazení:
  1. Pokud maskLen > 2 32 hLen , zobrazí se zpráva „délka masky je příliš velká“ a operace se zastaví.
  2. Nechť T  je prázdný řetězec.
  3. VE smyčce FOR i OD 0 DO SE PROVÁDÍ:
    • Představme i jako C byte řetězec o délce 4 bajtů.
    C = int-to-str(i,4)
    • M' = M||C .
    • Přidejme výsledek hash M' na konec řetězce T.
    T = T||Hash(M')
  4. Zapišme horní maskLen bajty řetězce T do mask .
  5. Výstup masky .

Možnosti

Ve standardu PKCS#1 v2.1 je RSASSA-PSS přiřazen identifikátor id-RSASSA-PSS , se kterým musí být spojena sekvence čtyř parametrů. Mezi tyto parametry patří hashovací funkce, MGF, délka náhodně generovaného řetězce soli ( sLen ), trailerField ( pole TF ). Výchozí hodnoty těchto parametrů, uvedené v příslušné normě, jsou uvedeny v tabulce.

Parametr Typ Výchozí hodnota
hashAlgorithm HashAlgorithm sha1
maskGenAlgorithm MaskGenAlgorithm mgf1SHA1
sůlDélka CELÉ ČÍSLO dvacet
pole přívěsu TrailerField trailerFieldBC
  • Doporučuje se, aby hashovací funkce, na které je založen MGF (pokud existuje), byla stejná jako ta, která je specifikována parametrem hashAlgorithm .
  • Výchozí hodnota parametru saltLength je rovna délce výstupního řetězce vybrané hashovací funkce ( hLen ). Na rozdíl od ostatních možností nemusí být saltLength pro daný pár klíčů RSA fixována.
  • Pole TF je zavedeno kvůli kompatibilitě s návrhem IEEE P1363a . V uvažovaném standardu je podporována pouze hodnota trailerField rovna 0xBC . Může však mít i jinou formu, například HID||0xCC , kde HID  je identifikátor hashovací funkce specifikovaný v normě ISO/IEC 10118.

Funkce

Přípustná délka zprávy pro metodu RSA-PSS je buď neomezená, nebo omezená na velmi vysokou hodnotu kvůli hashovací funkci použité v kódování PSS.

RSA-PSS se liší od jiných schémat digitálního podpisu založených na RSA v tom, že je spíše pravděpodobnostní než deterministický. zahrnuje použití náhodně generované hodnoty ( sůl ). Hodnota soli zvyšuje spolehlivost obvodu [1] .

Spolehlivost

Za předpokladu, že výpočet libovolného kořenového modulu n je operace, která je neproveditelná a hašovací funkce a MGF mají potřebné vlastnosti, RSA-PSS zajišťuje bezpečnost podpisu. Robustnost je prokazatelná v tom smyslu, že obtížnost rozbití podpisu může přímo souviset s obtížností rozbití kryptografického primitiva (matematický problém, který je základem RSA ). Pravděpodobnost úspěšného praskání a doba běhu nejlepší krakovací metody RSA-PSS jsou velmi blízké stejným parametrům algoritmu pro nalezení inverzní funkce RSA .

Schéma podpisu popsané dříve se liší od původního algoritmu navrženého Mihirem Bellarem a Phillipem Rogawayem [1] . Potřebný důkaz pro toto schéma však poskytuje Jacob Jonsson [2] .

Poznámky

  1. ↑ 1 2 3 Mihir Bellare, Phillip Rogaway „Přesná bezpečnost digitálních podpisů – Jak podepisovat s RSA a Rabinem“ . Získáno 1. listopadu 2010. Archivováno z originálu 13. června 2010.
  2. ↑ Jacob Jonsson „Bezpečnostní důkazy pro schéma podpisu RSA-PSS a jeho varianty“ (PDF) . Získáno 1. listopadu 2010. Archivováno z originálu 6. března 2016.

Zdroje

 Kryptosystémy s veřejným klíčem
Algoritmy
Faktorizace celých čísel
Diskrétní logaritmus
Kryptografie na mřížkách
jiný
Teorie
Normy
Témata