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.