RSA - Est $e = d$ un problème?

Question

Je travaille sur un petit projet RSA à l'université. En ce moment, j'ai fait ceci:

1. Un tableau de nombres premiers est généré à partir de la plage sélectionnée.
2. $p$ et $q$ sélectionné au hasard dans ce tableau
3. $n$ calculé
4. $\phi(n)$ calculé
5. $e$ calculé
6. $d$ calculé

Qu'en pensez-vous $e$ et $d$ dans ce cas?

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

Answer 1

Il serait désastreux si une procédure de génération de clé RSA avait une probabilité considérable de se terminer par $e=d$, car dans ce cas, la clé publique révèle la clé privée, qui doit être secrète du point de vue de la sécurité.

Mais $e=d$ est le symptôme d'un problème plus important se trouvant aux étapes 1 et 2 de la procédure de génération de clé: RSA ne peut être sécurisé que si $p$ et $q$ sont sélectionnés de telle sorte que l'affacturage $n$ est difficile, et cela signifie $p$ et $q$devrait être de grands nombres premiers. La ligne de base moderne est$n$ de $2048$ bits, c'est-à-dire $617$ chiffres décimaux, pas $4$chiffres décimaux. Pour ça,$p$ et $q$ sont choisis au hasard parmi un sous-ensemble considérable de nombres premiers d'environ $309$chiffres. Il y a plus de$10^{305}$ces nombres premiers, les générant ainsi tous, puis la sélection à l'intérieur de ce qui est impossible. La bonne procédure consiste à générer directement$p$ et $q$.

Avec $p$ et $q$ aléatoire prime ce grand, et un choix aléatoire de $e$ tel que $\gcd(e,\phi(n))=1$ (ou un choix aléatoire de nombres premiers $p$ et $q$ avec la seule dépendance de $e$ cette $\gcd(e,p-1)=1$ et $\gcd(e,q-1)=1$, comme c'est la pratique courante), il est infiniment improbable que $d=e$, ou plus généralement qu'un ou plusieurs recryptage (s) conduisent au décryptage. Voir ces questions sur l' attaque cycliste .

---

Il existe des procédures de génération de clé RSA dans l' annexe B.3 de la norme FIPS 186-4 . Ignorer la proposition$1024$-bit key size, qui est obsolète. La proposition$2048$ est la ligne de base, $3072$ de plus en plus courant, s'étendant à $4096$-bit pas déraisonnable. Ces procédures diffèrent de celles utilisées dans la question par plusieurs points, notamment:

• Générer de grands nombres premiers $p$ et $q$ de manière imprévisible dans un intervalle prescrit $[2^{(k-1)/2},2^{k/2}]$, où $k$ est la taille de bits souhaitée de $n$ (par exemple $3072$)
• Nécessitant bizarre $e$ avec $2^{16}<e<2^{256}$ (le plus bas parce que cela agit comme une garantie contre les mauvais choix de rembourrage RSA, le plus élevé pour l'interopérabilité et pour rendre certains autres mauvais choix impossibles)
• En utilisant $d=e^{-1}\bmod\lambda(n)$ (où $\lambda$est la fonction Carmichael ) plutôt que$d=e^{-1}\bmod\phi(n)$. Les deux sont mathématiquement corrects, mais en utilisant$\lambda$ assure la génération du plus petit exposant privé positif $d$ travailler pour un donné $(n,e)$.
• Nécessitant une taille minimale de $d$ (beaucoup plus grand que $2^{256}$, qui assure accessoirement $d>e$), plus comme une garantie contre les erreurs que par nécessité mathématique.