Quelles sont les plus petites clés privées et publiques RSA possibles?

Aug 18 2020

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

9 fgrieu Aug 18 2020 at 09:56

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.