înregistrare Logare
Puncte:11
Farzad Sadeghi avatar Crypto

RSA Private Exponent Generation conform FIPS 186-4 în openssl v1

drapel us
Farzad Sadeghi

Bănuiesc că aceasta este mai degrabă o problemă de matematică într-un context criptografic, așa că îmi cer scuze înainte dacă nu este locul potrivit pentru a întreba.Practic, trebuie să verific dacă o anumită implementare a generării perechilor de chei RSA aderă la FIPS 186-4. Mai precis, Anexa B-3-1. FIPS 186-4 necesită acest lucru $d$ (exponentul privat) să fie creat astfel:

$d = (e^{-1})\bmod(\text{LCM}(p-1, \space q-1))$

Biblioteca în cauză (openssl v1.0.1) calculează $d$ ca astfel:

$d = (e^{-1})\bmod((p-1)(q-1))$

Nu pot dovedi sau infirma dacă acestea două creează același set de răspunsuri pentru $d$.
Condiția de generare a $p$ și $q$ este asta $(p-1)$ și $(q-1)$ ambele sunt relativ prime pentru $e$ (exponentul public) deci ambele formule au răspunsuri.
Tot de atunci $p$ și $q$ ambele sunt prime, $(p-1)$ și $(q-1)$ vor fi ambele numere pare și de la $a \times b=\text{GDC}(a, \space b) \times \text{LCM}(a, \space b)$ noi stim aia $\text{GCD}(p-1, \space q-1) \geq 2$ asa de $\text{LCM}(p-1, \space q-1) \neq (p-1)(q-1)$.

Întrebarea mea este sunt aceleași sau diferite?

De asemenea, aș aprecia dacă ați putea să mă îndreptați în direcția corectă din punct de vedere matematic, astfel încât să pot rezolva singur acest lucru.

P.S.: Am înțeles că pentru openssl v1 există un modul FIPS și, de asemenea, că openssl v3.0 va încerca să aplice pentru un certificat FIPS 140-2. Din păcate, am rămas blocat cu versiunea pe care am menționat-o și nu o pot schimba (nu depinde de mine).

592
2 + 3
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Cred că ai un mod destul de lung de a-ți explica și răspunsul lui fgrieu este, practic, confirmare + câteva informații suplimentare despre FIPS.Rețineți că ~50% real este foarte greu de restrâns deoarece depinde de $(p-1)(q-1)$ și, eventual, chiar de distribuția primelor. Cu toate acestea, dacă aveți nevoie doar ca calculul să fie compatibil FIPS, ar însemna că puteți încerca să utilizați eșantionarea de respingere la generarea perechii de chei RSA (generați, verificați dacă cerințele suplimentare FIPS sunt îndeplinite și reporniți dacă nu). Cheile private în OpenSSL (cu motor software intern) sunt generate cu parametrii CRT
2
Răspunde
dave_thompson_085 avatar
drapel cn
dave_thompson_085
Nit: OpenSSL „v1” nu este un singur lucru; actualul modul OpenSSL FIPS 2.0.x ar trebui să funcționeze cu OpenSSL 1.0.1 și 1.0.2, dar nu cu 1.0.0 1.1.0 1.1.1. OpenSSL 3.0.x este conceput pentru a fi validabil, dar nu sub FIPS 140-2, deoarece acesta nu mai este disponibil; trebuie să meargă pentru 140-3 în schimb. Mai semnificativ, Politica de securitate actuală (2.0.16) listează conformitatea RSA ca 186-2, nu -4 și _keygen_ numai ca X9.31 per -2 (dar _sign_ și _verify_ ca atât X9.31 pe -2, cât și PKCS1v2 pe -3 /4), și face referire la certificatele CAVP care listează „RSA KeyGen FIPS186-2” cu o baraj care indică „nu mai este aprobat”.
0
Răspunde
Farzad Sadeghi avatar
drapel us
Farzad Sadeghi
În retragere, da. poate v1 din titlul întrebării ar putea induce în eroare. ai dreptate. În ceea ce privește validarea FIPS, openssl 3 va opta pentru validarea FIPS 140-2, deoarece aceasta este disponibilă până în septembrie 2021. Nu vor fi utilizate pentru FIPS 140-3. Am aruncat o privire la gândul de cod. ei merg totuși pentru conformitatea cu FIPS 186-4.
0
Răspunde
Puncte:10
fgrieu avatar Crypto
drapel ng
fgrieu

FIPSÂ 186-4 $d_1=e^{-1}\bmod m_1$ cu $m_1=\operatorname{lcm}(p-1,q-1)$, și OpenSSL $d_2=e^{-1}\bmod m_2$ cu $m_2=(p-1)(q-1)$, sunt diferite cu probabilitatea $>1/2$ pentru alegerea aleatorie a $p$ și $q$ și fie fix $e$ adăugând constrângeri suplimentare asupra $p$ și $q$ (ca obișnuit), sau $e$ ales oarecum la întâmplare după $p$ și $q$.

Justificare: se menține $m_2=g\,m_1$ pentru număr întreg $g=\gcd(p-1,q-1)$. Acea $g$ este cel puțin un număr întreg $2$ (și vizibil adesea un număr întreg mai mare). Urmează $d_2\bmod m_1=d_1$. Este bine verificat că $d_2$ este distribuit aproximativ uniform pe interval [0,m_2)$ în limita constrângerii de a fi coprim cu $m_2$. Astfel reducerea modulară de la $d_2$ la $d_1$ provoacă o schimbare cu probabilitate lângă $1-1/g$, ceea ce este întotdeauna cel puțin $1/2$. Este ușor să faci un exemplu unde se întâmplă asta. Legatul $1/2$ pentru probabilitatea ca $d_1\ne d_2$ ar putea fi îmbunătățit (creștet, puțin peste $2/3$ de fapt) prin luarea în considerare a distribuţiei de $g$.

O astfel de discrepanță frecventă nu este atât de rău pe cât pare, pentru că

  • Pentru ce este cu adevărat nevoie $d$ pentru a funcționa (când și dacă este folosit ca exponent privat RSA, sau pentru a calcula sau verifica $d_p$ și $d_q$ ) este asta $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$ (presupunând $p$ și $q$ sunt numere prime distincte). Ambii $d_1$ și $d_2$ potriviți acest lucru și conformați-vă PKCS#1 care în plus necesită $0<d<n$ (asta decurge din $d_1<m_1<m_2<n$ și $d_2<m_2<n$).
  • In practica $d$ este rar folosit, deoarece operarea cheii private este mai rapidă cu teorema chineză a restului, care de obicei utilizează numai $(n,e,p,q,d_p,d_q,q_\text{inv})$ sau un subset al acestuia, caz în care singurele probleme posibile cu $d_1$ sau $d_2$ este momentul în care a fost verificat pentru prima dată, iar acest lucru va fi detectat prin importarea cheii și o singură utilizare.
  • Orice cheie FIPS 186-4 RSA este acceptată de orice versiune de OpenSSL. Nu aș paria casa în cealaltă direcție, dar atunci este rar să importați o cheie de la OpenSSL într-un dispozitiv FIPSÂ 140. Acest lucru ar putea fi chiar interzis în modul FIPS și un dispozitiv FIPS (cel puțin în modul non-FIPS) ar putea să accepte orice dispozitiv valid din punct de vedere matematic. $d$ inclusiv $d_2$, sau ignorați ceea ce este dat $d$.
0 + 2
poncho avatar
drapel my
poncho
De asemenea, rețineți că, în practică, valoarea reală a $d$ este de obicei ignorată. În schimb, folosim de obicei parametrii CRT ($p, q, dp, dq, qinv$), iar aceștia se dovedesc a fi toți la fel, indiferent dacă utilizați $\phi(n)$ sau $\operatorname{ lcm}(p-1,q-1)$ definiția lui $d$...
3
Răspunde
dave_thompson_085 avatar
drapel cn
dave_thompson_085
FWIW, FIPS186-4 (și -3) 5.1 afirmă în mod explicit că reprezentarea CRT este „permise”; nu menționează în mod explicit utilizarea lui, dar face referire la PKCS1v2.1 și, desigur, PKCS1 înapoi la v1.5, cel puțin are CRT preferat atât pentru stocare, cât și pentru operațiuni.
1
Răspunde
Puncte:2
avatar Crypto
drapel cn
j.p.

După înțelegerea mea, cerința din FIPS 186-4 de utilizat pentru calcularea cheii private $d$ cel mai mic multiplu comun al $p-1$ și $q-1$ în loc de produsul lor are scopul de a preveni atacurile împotriva micilor $d$ ca Atacul lui Wiener. Credința comună printre experți este că cineva este în siguranță împotriva oricărei îmbunătățiri a atacului lui Wiener, dacă durata $d$ este cel puțin jumătate din lungimea modulului $m$.

Ca toate variantele (cunoscute) de atacuri împotriva cheii private mici $d$ functioneaza in functie de marimea cel mai mic posibil $d$ (cel calculat folosind cel mai mic multiplu comun), NIST insista sa foloseasca cel mai mic multiplu comun, astfel incat se poate verifica ca cel mai mic multiplu posibil $d$ este suficient de mare.

După cum NIST cere asta $p$ și $q$ au aproximativ aceeași dimensiune, puteți verifica cerința de lungime pt $d$ tot în schimb pur și simplu verificând asta $d_p$, $d_p+p-1$, $d_q$ și $d_q+q-1$ sunt diferite pe perechi. Dacă atacurile pe canalul lateral reprezintă o problemă pentru dvs., acest test poate fi protejat mult mai ușor decât calculul celui mai mare divizor comun al $p-1$ și $q-1$, care a devenit în ultimii ani ținta mai multor atacuri publicate. Care $d$ pe care îl utilizați în calculele dvs. nu ar trebui să conteze prea mult, deoarece adăugarea unui multiplu de $(p-1)(q-1)$ la exponent este folosită în mod obișnuit contramăsura împotriva atacurilor pe canale laterale.

0 + 4
fgrieu avatar
drapel ng
fgrieu
Într-adevăr, testul pentru un minim $d$ făcut în FIPS 186-4 ar avea și mai puțin sens dacă $d$ nu ar fi specificat ca fiind minimul pozitiv $d$, așa cum este.Dar acest test oricum are puțin sens, deoarece (A) acest test eșuează cu o probabilitate neglijabilă atunci când sunt utilizate metodele generale de generare impuse (maxim $e$ + numere prime aleatoare) și (B) există o mulțime de metode pentru a manipula o cheie RSA generator într-un mod care nu este detectabil de la ieșire. Printre alte teste greu de justificat în FIPS 186-4 se numără minimul $\lvert p-q\rvert$; dar cel puțin aceasta ulterioară este o modalitate redundantă de a prinde un generator blocat.
0
Răspunde
drapel cn
j.p.
$d$ mic ar putea fi o modalitate inocentă de a „macheta” keygen-ul pentru o performanță mai bună (în cazul în care cineva se teme de atacul bellcore). Folosirea unei site pentru ambele prime pentru a economisi ceva timp (obținerea mici, nesigure $|p-q|$) pare să fie într-adevăr mai puțin probabilă.
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
FIPS 186-4 necesită $n$ de cel puțin 1024 de biți, cu $p$ și $q$ jumătate și $e$ de cel mult 256 de biți. Cu aceasta, este greu să creați $p$ și $q$ cu $d$ mai puțin de jumătate de $n$ (limita necesară); și cred că imposibil cu $p$ și $q$ oriunde aproape de aleatoriu și independent, chiar dacă $e$ este ales ulterior. Asta ar face ca minimul $d$ să fie relevant doar pentru $p$ sau/și $q$ creat; dar numerele prime create sunt periculoase în multe moduri diferite, inclusiv câteva care ar putea trece ca (sau chiar să fie) accidente accidentale. Prin urmare, cerința minimă $d$ are o justificare dubioasă.
0
Răspunde
drapel cn
j.p.
Cred că toată lumea ar fi de acord că, pentru $p$ și $q$ cu adevărat aleatorii, care necesită $e$ nu prea mult ar trebui să fie suficient pentru a evita ca lucrurile rele să se întâmple. Singurul mod pe care îl știu pentru a obține $d$ scurt (pentru scurt $e$) este să impun un divizor comun mare pentru $p-1$ și $q-1$ (aceasta se întâmplă rar prin alegere aleatorie), așa că bănuiesc că unele dintre cerințele NIST sunt la fel de „dubioase” precum era utilizarea anterioară a „primelor sigure”...
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.