Les clefs RSA sont particulièrement vulnérables, car leur génération nécessite non pas un mais deux grands nombres premiers.
Ce qui rend les choses encore plus compliquée avec RSA, c'est que si on veut des clefs de bonne qualité, il ne faut pas simplement prendre deux nombres premier p et q au hasard.
Petit rappel, n=pq est un élément des clefs publiques et privées. Si on sait factoriser n, on est mort. Or, si il existe des algorithmes de factorisation qui fonctionnent bien dans des cas particuliers. Exemples:
Si p ou q est petit, c'est mort. Même le crible d'Ératosthène devient utilisable. Mais c'est aussi le cas de méthodes plus sophistiquée.
Si p-q est petit, c'est mort aussi. Preuve. On pose n=pq et k=p-q.
Comme (p+q)2=k2+4n, on a p+q=\sqrt(k2+4n). Donc 2p=\sqrt(k2+4n)-k. Il ne reste plus qu'à tester toutes les « petites » valeurs de k.
Bref, générer de bonnes clefs RSA, c'est TRÈS compliqué.
[^] # Re: Vitesse d'utilisation seulement ou aussi sécurité?
Posté par fmaz fmaz . En réponse à la dépêche scdrand: alimenter le pool d’entropie du noyau à partir d’une carte à puce. Évalué à 10.
Ce qui rend les choses encore plus compliquée avec RSA, c'est que si on veut des clefs de bonne qualité, il ne faut pas simplement prendre deux nombres premier p et q au hasard.
Petit rappel, n=pq est un élément des clefs publiques et privées. Si on sait factoriser n, on est mort. Or, si il existe des algorithmes de factorisation qui fonctionnent bien dans des cas particuliers. Exemples:
Si p ou q est petit, c'est mort. Même le crible d'Ératosthène devient utilisable. Mais c'est aussi le cas de méthodes plus sophistiquée.
Si p-q est petit, c'est mort aussi. Preuve. On pose n=pq et k=p-q.
Comme (p+q)2=k2+4n, on a p+q=\sqrt(k2+4n). Donc 2p=\sqrt(k2+4n)-k. Il ne reste plus qu'à tester toutes les « petites » valeurs de k.
Bref, générer de bonnes clefs RSA, c'est TRÈS compliqué.