Ça arrive avec probabilité (cryptographiquement) faible si les nombres sont sur un nombre de bits correct. Par exemple, si on tire p et q premiers aléatoires sur 512 bits (soit une clef RSA de 1024 bits, déjà non recommandée car bien trop petite) correctement (c'est-à-dire qu'on les tire comme des nombres aléatoires sur 512 bits, puis s'ils ne sont pas premiers on recommence avec un nouveau nombre aléatoire sur 512 bits), alors la probabilité que p soit inférieur à 2256 est inférieure à 2-256. La probabilité que p - q soit inférieure à 2256 est inférieure à 2-128 (il faut que les deux nombres p et q coïncident sur leurs 256 bits de poids fort).
Cela dit générer une clef RSA reste piégeux : outre l'absence de biais sur l'aléa utilisé, il ne faut pas que p-1 ou q-1 aient trop de facteurs petits, et bien d'autres vérifications sont à faire.
[^] # Re: Vitesse d'utilisation seulement ou aussi sécurité?
Posté par khivapia . En réponse à la dépêche scdrand: alimenter le pool d’entropie du noyau à partir d’une carte à puce. Évalué à 2.
p ou q est petit (...) Si p-q est petit
Ça arrive avec probabilité (cryptographiquement) faible si les nombres sont sur un nombre de bits correct. Par exemple, si on tire p et q premiers aléatoires sur 512 bits (soit une clef RSA de 1024 bits, déjà non recommandée car bien trop petite) correctement (c'est-à-dire qu'on les tire comme des nombres aléatoires sur 512 bits, puis s'ils ne sont pas premiers on recommence avec un nouveau nombre aléatoire sur 512 bits), alors la probabilité que p soit inférieur à 2256 est inférieure à 2-256. La probabilité que p - q soit inférieure à 2256 est inférieure à 2-128 (il faut que les deux nombres p et q coïncident sur leurs 256 bits de poids fort).
Cela dit générer une clef RSA reste piégeux : outre l'absence de biais sur l'aléa utilisé, il ne faut pas que p-1 ou q-1 aient trop de facteurs petits, et bien d'autres vérifications sont à faire.