Combien de nombres premiers (disponible pour le chiffrement RSA)?
est-ce que je me trompe en pensant que la sécurité du cryptage RSA, en général, est limitée par la quantité de nombres premiers connus?
pour cracker (ou créer) une clé privée, il faut combiner la bonne paire de nombres premiers.
Est-il impossible de publier une liste de tous les nombres premiers dans la gamme utilisée par RSA? Ou est-ce que cette liste est assez large pour rendre cette attaque brutale peu probable? N'y aurait-il pas des nombres premiers" d'usage courant"?
3 réponses
RSA ne sélectionne pas d'une liste de nombres premiers connus: il génère un nouveau nombre très grand, puis applique un algorithme pour trouver un nombre proche qui est presque certainement premier. Voir cette description utile de la grande génération de prime ):
la méthode standard pour générer de grands nombres premiers est de prendre un nombre aléatoire présélectionné de la longueur désirée, appliquer un test de Fermat (mieux avec la base 2 car il peut être optimisé pour la vitesse) et puis appliquer un certain nombre de tests Miller-Rabin (en fonction de la longueur et du taux d'erreur autorisé comme 2-100) pour obtenir un nombre qui est très probablement un nombre premier.
(vous pourriez vous demander pourquoi, dans ce cas, nous n'utilisons pas cette approche lorsque nous essayons de trouver des nombres premiers de plus en plus grands. La réponse est que le plus Grand prime connu a plus de 17 millions de chiffres - bien au-delà même les très grands nombres généralement utilisés dans la cryptographie).
quant à savoir si les collisions sont possibles - les tailles de clés modernes (en fonction de votre sécurité souhaitée) vont de 1024 à 4096, ce qui signifie que les nombres premiers vont de 512 à 2048 bits. Cela veut dire que les nombres premiers sont de l'ordre de 2^512: plus de 150 chiffres.
nous pouvons estimer très grossièrement la densité des nombres premiers en utilisant 1 / ln(n) (voir ici ). Cela signifie que parmi ces 10^150 nombres, il y a environ 10^150/ln(10^150) nombres premiers, ce qui revient à 2.8x10^147 nombres premiers à choisir - certainement plus que vous pourriez entrer dans n'importe quelle liste!!
donc oui - le nombre de nombres premiers dans cette gamme est incroyablement énorme, et les collisions sont effectivement impossibles. (Même si vous avez généré un billion de nombres premiers possibles, formant des combinaisons de septillons, la chance que deux d'entre eux soient le même nombre premier serait 10^-123 ).
nouvelle recherche vient la réponse à votre question devient plus intéressant. Dans un article récent "Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice" de David Adrian et all found @ https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf consulté le 16/10/2015 les chercheurs montrent que bien qu'il y ait probablement un nombre suffisant de nombres premiers disponibles pour le jeu de clés 1024 bits de RSA il y a des groupes de clés à l'intérieur de l'ensemble qui sont plus susceptibles d'être utilisés en raison de la mise en œuvre.
nous estimons que même dans le cas de 1024 bits, les calculs sont plausible étant donné les ressources de l'État-nation. Un petit nombre de fixe ou les groupes standardisés sont utilisés par des millions de serveurs; la précomputation pour un seul groupe de 1024 bits permettrait 18% des sites populaires de HTTPS sont espionnés, et un second groupe permettre le décryptage du trafic à 66% des VPN IPsec et 26% de SSH serveur. Une lecture attentive des fuites publiées par la NSA montre que la les attaques de l'agence contre les VPN sont cohérentes avec le fait d'avoir réalisé une telle briser. Nous concluons que le passage à des méthodes d'échange clés plus être une priorité pour la communauté Internet.
la recherche montre également une faille dans TLS qui pourrait permettre à un attaquant homme-au-milieu de réduire le cryptage à 512 bits.
donc en réponse à votre question il y a probablement un quantité suffisante de nombres premiers dans le cryptage RSA sur papier, mais dans la pratique, Il ya un problème de sécurité si vous vous cachez d'un état de la nation.
les nombres premiers à utiliser dans RSA ne sont pas seulement grands. Il doit être 10-digité ou peut être 100-digité. Ce que je veux dire, ce n'est pas des milliards ou des billions, mais quelque chose au-delà de ce qui est difficile à exprimer ou même à imaginer.
donc pour répondre à la question, de tels nombres ne peuvent pas être des nombres premiers connus.