Puncte:0

Cum generează SSH chei pentru algoritmul RSA?

drapel nz

Din câte am înțeles, nucleul algoritmului RSA este de a avea 2 numere prime (mari) âpâ și âqâ, astfel încât ân=pqâ. Apoi ânâ este cheia publică, iar âpâ cea privată. Securitatea provine din faptul că dat ânâ nu este ușor de obținut âpâ și âqâ, în timp ce este trivial să verificați dacă âpâ factorizează ânâ.

Întrebarea mea este cum obține SSH aceste numere în mai puțin de o secundă? Are o „bibliotecă de numere prime”? Cum se asigură că âpâ și âqâ sunt unice pentru dvs.? Există atât de multe „numere prime mari” care îndeplinesc cerințele algoritmului fără ciocniri evidente?

kelalaka avatar
drapel in
https://github.com/openssl/openssl/blob/4cedf30e995f9789cf6bb103e248d33285a84067/crypto/bn/bn_prime.c
kelalaka avatar
drapel in
Pentru coliziune [Prof. Lindell a dat răspunsul standard aici](https://crypto.stackexchange.com/a/76766/18298)
Puncte:3
drapel mu
Dan

Să presupunem că doriți ca „n” să fie de 2048 de biți (RSA 2048). Atunci „p” și „q” ar fi fiecare de 1024 de biți.

Calculatorul generează un număr aleatoriu de 1024 de biți (aproape instantaneu) și îl testează pentru primalitate. Există diferite tipuri de teste de primalitate, majoritatea sunt statistice. Sunt foarte rapidi (știu că acest lucru nu este cuantificat, dar lucrez pe microcontrolere încorporate care rulează la 100MHz fără cache, așa că habar n-am despre viteză pe desktop).

Așadar, generând o grămadă de numere de 1024 de biți, în cele din urmă veți atinge unul care trece mai multe iterații ale testelor de primalitate. (fără a intra aici în detalii despre statistici și despre ce este „destul de bun”, totul este destul de ușor de găsit). Faceți același lucru pentru a obține „q”, înmulțiți-le, aveți modulul „n”. „n” plus „e” (probabil 65537) sunt cheia dumneavoastră publică.

După cum vă puteți imagina, densitatea primelor scade pe măsură ce numerele devin mai mari; există modalități de a estima densitatea primelor pe baza mărimii primului pe care încercați să îl generați. 40% dintre numerele sub 10 sunt prime, dar numai 25% densitate pentru numerele sub 100 și chiar mai puțin pentru numerele de 1024 de biți. Dacă îmi amintesc corect, in medie, va trebui să încercați ciclul de testare de generare/primalitate de ~360 de ori pentru a găsi un număr de 1024 de biți care testează ca prim. Nu sunt mii sau milioane. Și pentru numerele de 512 biți, probabil că este sub 100 de încercări.

Deoarece spațiul numeric 2^1024 este atat de mare, este incredibil de puțin probabil ca p&q-ul tău să se potrivească cu al altcuiva. De fapt, fiecare dintre acele șiruri de 1024 de biți nu a existat probabil niciodată pe niciun computer în istoria pământului.

Sper că asta vă oferă suficientă idee despre cum funcționează. Practic este atât de simplu. Am omis câteva detalii, discuții despre numere prime puternice etc., deoarece intră în detalii care sunt în afara domeniului de aplicare al întrebării dvs.

kelalaka avatar
drapel in
În primul rând, aceasta: [GCD-ul revine la RSA în 2019 - O bună aleatorie este singura soluție?](https://crypto.stackexchange.com/q/76757/18298) și în al doilea rând, OP întreabă ssh, răspunsul tău este generic , nu oferă detalii în ssh!
drapel mu
Dan
Puncte bune. Dar în ceea ce privește primul, sunt multe, mult mai multe de spus despre generația de chei și puteți merge într-o groapă de iepure, dar am încercat să răspund la ceea ce credeam că este esența întrebării lui OP. Și m-am uitat la o mulțime de coduri RSA keygen în multe stive TLS, toate au fost foarte asemănătoare, nu am niciun motiv să cred că o implementare SSH ar proceda diferit. Aveți informații care să spună contrariul?
kelalaka avatar
drapel in
de exemplu, practica obișnuită alege mai întâi $e$ apoi selectează prim și dacă $\gcd(\lambda(pq),e) \neq 1$ atunci sunt selectate noi prime. unele q vechi [1](https://crypto.stackexchange.com/a/27294/18298)
Pythonist avatar
drapel nz
Mulțumesc, acesta este exact nivelul de detaliu pe care îl căutam. Va trebui să caut acele teste de primalitate... Mi se pare extrem de contraintuitiv că este atât de ușor să găsești numere prime aleatorii. Aș fi ghicit că șansa de a găsi un prim generând numere aleatorii de mărimea 1024 este aproape zero. Am nevoie de aproximativ 360 de încercări îmi ului.De asemenea, mă încurcă complet faptul că puteți testa primalitatea atât de ieftin, în timp ce găsirea factorilor unui număr este, în practică, imposibil de informat. Lucruri cu adevărat contraintuitive se întâmplă aici!
kelalaka avatar
drapel in
Deoarece folosesc OpenSSL https://github.com/openssl/openssl/blob/4cedf30e995f9789cf6bb103e248d33285a84067/crypto/bn/bn_prime.c
Swashbuckler avatar
drapel mc
Care SSH? OpenSSH? Chit? JSCh? Paramiko? Sau oricare dintre zecile de alții?

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.