Quali sono le chiavi private e pubbliche RSA più piccole possibili?
Sto cercando di capire quali sono le chiavi pubbliche e private RSA più piccole possibili. Quando si usa$p = 2, q = 3$, la funzione di crittografia non esegue la crittografia. Quindi devo spostare un numero primo per ottenere$p = 3, q = 3$ e quindi la chiave privata è $(9, 3)$ e anche la chiave pubblica $(9, 3)$. So che è banale fattorizzare il prodotto di due numeri primi uguali ed è un male avere la stessa chiave privata e pubblica. Tuttavia è la coppia di chiavi RSA più bassa (fattibile) o mi manca qualcosa qui?
Risposte
Secondo la definizione di RSA in PKCS # 1v2.2
In una chiave privata RSA valida , il modulo RSA$n$ è il prodotto di $u$ numeri primi dispari distinti $r_i$, $i=1$, $2$, ..., $u$, dove $u\ge2$.
Quello fa $n=3\cdot5=15$ il più piccolo modulo pubblico.
e l'esponente pubblico RSA $e$ è un numero intero compreso tra $3$ e $n–1$ soddisfacente $\operatorname{GCD}(e,\lambda(n))=1$, dove $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$
Quello fa $e=3$ il più piccolo esponente pubblico. $(n,e)=(15,3)$ sembra essere una chiave pubblica valida, poiché $\lambda(15)=4$ e $\operatorname{GCD}(3,4)=1$.
L'esponente privato RSA $d$ è un numero intero positivo minore di $n$ soddisfacente $e\cdot d\equiv1\pmod{\lambda(n)}\,$.
Quello fa $d=1$il più piccolo esponente privato. Corrisponde ad esempio a$(n,e)=(15,5)$. La crittografia (e la decrittografia) con quella chiave è l'identità, ma non esiste una prescrizione formulata contro quella.
Se proibiamo $d=1$, poi $d=3$ diventa il più piccolo esponente privato, matching $(n,e)=(15,3)$. Più in generale, definizioni diverse di RSA producono limiti inferiori diversi. Permettendo$u=1$, $e=1$e rimuovendo la prescrizione che $r_i$ è strano, fa $(n,e,d)=(2,1,1)$accettabile. Per FIPS 186-4 , il più piccolo$n$è 1024 bit, probabilmente A $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; il più piccolo$e$ è $65537\,$; e il più piccolo$d$è B $2^{512}+1$.
R: Nell'ipotesi plausibile che ciascuno di $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ e $\lfloor2^{1023/2}\rfloor+2^{412}+432$ ha almeno un fattore primo $2^{100}$, che non ho controllato.
B: Qualche chiave pubblica corrispondente valida $(n,e)$esiste con alta probabilità. È un problema leggermente interessante mostrarne uno.