RSA - È $e = d$ un problema?

Question

Sto lavorando a un piccolo progetto RSA all'università. In questo momento ho fatto questo:

1. Viene generato un array di numeri primi dall'intervallo selezionato.
2. $p$ e $q$ selezionati casualmente da questo array
3. $n$ calcolato
4. $\phi(n)$ calcolato
5. $e$ calcolato
6. $d$ calcolato

Che cosa ne pensi $e$ e $d$ in quel caso?

• $p = 29$
• $q = 53$
• $n = 1537$
• $\phi(n) = 1456$
• $e = 545$
• $d = 545$

Answer 1

Sarebbe disastroso se una procedura di generazione di chiavi RSA avesse una considerevole probabilità di finire $e=d$, perché in quel caso la chiave pubblica rivela la chiave privata, che deve essere segreta dal punto di vista della sicurezza.

Ma $e=d$ è un sintomo di un problema più ampio che si trova nei passaggi 1 e 2 della procedura di generazione delle chiavi: RSA può essere sicuro solo se $p$ e $q$ sono selezionati in modo tale che il factoring $n$ è difficile, e questo significa $p$ e $q$dovrebbero essere numeri primi grandi. La linea di base moderna è$n$ di $2048$ bit, cioè $617$ cifre decimali, non $4$cifre decimali. Per questo,$p$ e $q$ sono scelti casualmente tra un sottoinsieme considerevole di numeri primi di circa $309$cifre. Ci sono più o meno$10^{305}$tali numeri primi, generandoli così tutti e poi raccoglierli all'interno di ciò non è possibile. La procedura giusta è generare direttamente$p$ e $q$.

Con $p$ e $q$ numeri primi casuali così grandi e una scelta casuale di $e$ tale che $\gcd(e,\phi(n))=1$ (o una scelta casuale di numeri primi $p$ e $q$ con l'unica dipendenza da $e$ quello $\gcd(e,p-1)=1$ e $\gcd(e,q-1)=1$, come è pratica comune), è infinitamente improbabile che $d=e$o, più in generale, che una o più crittografie portano alla decrittografia. Vedi queste domande sull'attacco ciclistico .

---

Ci sono procedure di generazione della chiave RSA nell'Appendice B.3 di FIPS 186-4 . Ignora la proposta$1024$dimensione della chiave in bit, che è obsoleta. La proposta$2048$ è la linea di base, $3072$ sempre più comune, che si estende a $4096$-bit non irragionevole. Queste procedure differiscono da quelle utilizzate nella domanda per diversi punti, tra cui:

• Generazione di numeri primi di grandi dimensioni $p$ e $q$ imprevedibilmente in un intervallo prescritto $[2^{(k-1)/2},2^{k/2}]$, dove $k$ è la dimensione in bit desiderata di $n$ (per esempio $3072$)
• Richiede dispari $e$ con $2^{16}<e<2^{256}$ (il più basso perché questo funge da salvaguardia contro scelte sbagliate di imbottitura RSA, più alto per l'interoperabilità e per rendere impossibili alcune altre scelte sbagliate)
• Utilizzando $d=e^{-1}\bmod\lambda(n)$ (dove $\lambda$è la funzione di Carmichael ) piuttosto che$d=e^{-1}\bmod\phi(n)$. Entrambi sono matematicamente a posto, ma usando$\lambda$ assicura la generazione del più piccolo esponente privato positivo $d$ lavorando per un dato $(n,e)$.
• Richiede una dimensione minima di $d$ (molto più grande di $2^{256}$, che tra l'altro assicura $d>e$), più come salvaguardia contro gli errori che per necessità matematica.