Quelles sont les plus petites clés privées et publiques RSA possibles?
J'essaie de comprendre quelles sont les plus petites clés publiques et privées RSA possibles. Lors de l'utilisation$p = 2, q = 3$, la fonction de cryptage ne crypte pas. Alors je dois changer d'un premier pour obtenir$p = 3, q = 3$ puis la clé privée est $(9, 3)$ et la clé publique est également $(9, 3)$. Je sais qu'il est trivial de factoriser le produit de deux nombres premiers égaux et qu'il est mauvais d'avoir la même clé privée et publique. Cependant, est-ce la paire de clés RSA la plus basse (faisable) ou est-ce que je manque quelque chose ici?
Réponses
Selon la définition de RSA dans PKCS # 1v2.2
Dans une clé privée RSA valide , le module RSA$n$ est le produit de $u$ nombres premiers impairs distincts $r_i$, $i=1$, $2$,…, $u$, où $u\ge2$.
Qui fait $n=3\cdot5=15$ le plus petit module public.
et l'exposant public RSA $e$ est un entier entre $3$ et $n–1$ satisfaisant $\operatorname{GCD}(e,\lambda(n))=1$, où $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$
Qui fait $e=3$ le plus petit exposant public. $(n,e)=(15,3)$ se trouve être une clé publique valide, car $\lambda(15)=4$ et $\operatorname{GCD}(3,4)=1$.
L'exposant privé RSA $d$ est un entier positif inférieur à $n$ satisfaisant $e\cdot d\equiv1\pmod{\lambda(n)}\,$.
Qui fait $d=1$le plus petit exposant privé. Cela correspond par exemple à$(n,e)=(15,5)$. Le cryptage (et le décryptage) avec cette clé est une identité, mais il n'y a pas de prescription formulée contre cela.
Si nous interdisons $d=1$, puis $d=3$ devient le plus petit exposant privé, correspondant $(n,e)=(15,3)$. Plus généralement, différentes définitions du RSA donnent des limites inférieures différentes. Permettant$u=1$, $e=1$et en supprimant la prescription qui $r_i$ est étrange, fait $(n,e,d)=(2,1,1)$acceptable. Pour FIPS 186-4 , le plus petit$n$est 1024 bits, probablement A $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; le plus petit$e$ est $65537\,$; et le plus petit$d$est B $2^{512}+1$.
R: Sous l'hypothèse plausible que chacun des $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ et $\lfloor2^{1023/2}\rfloor+2^{412}+432$ a au moins un facteur premier $2^{100}$, que je n'ai pas vérifié.
B: une clé publique correspondante valide $(n,e)$existe avec une forte probabilité. C'est un problème légèrement intéressant d'en exposer un.