Je joue et j'essaie d'écrire une mise en œuvre de RSA. Le problème est que je suis bloqué sur la génération des nombres premiers massifs impliqués dans la génération d'une paire de clés. Quelqu'un pourrait-il me signaler à un moyen rapide de générer d'énormes nombres premiers / probables?
5 Réponses :
Jetez un coup d'œil à la façon dont Truecrypt le fait-il. Aussi, jetez un coup d'œil à RABIN-MILLER pour tester de gros pseudoprimes.
Pourquoi supposez-vous que Truecrypt génère des nombres premiers? Pour autant que je sache, il n'utilise que Crypto symétrique.
Vous n'avez pas mentionné quelle langue vous utilisez. Certains ont une méthode pour faire cela intégré. Par exemple, en Java, cela est aussi simple que d'appeler NextProbablePRime () sur un BigInteger.
Selon la manière dont cette fonctionnalité est mise en œuvre, vous pouvez compromettre votre choix clé si l'espace de recherche est réduit.
Mono a une classe de Biginteger qui est open source, tout comme Java. Vous pourriez jeter un coup d'œil à ceux-ci. Ils sont probablement portables :) g'luck
Vous ne générez pas de nombres premiers exactement. Vous générez un grand nombre impair au hasard, puis testez si ce nombre est prime, sinon générer un autre au hasard. Il existe des lois de nombres premiers qui indiquent essentiellement que vos chances de "frapper" une prime via des essais aléatoires sont (2 / ln n)
par exemple, si vous souhaitez un numéro de qualité aléatoire de 512 bits, vous en trouverez un en 2 / (512 * ln (2)) Donc, environ 1 sur 177 des nombres que vous essayez sera d'amorcer.
Il existe de multiples façons de tester si un numéro est préféré, un bon est le "Miller-Rabin Test" Comme indiqué dans une autre réponse à cette question .
En outre, OpenSSL a un bel utilitaire à tester pour les nombres premiers:
Merci. Cela explique beaucoup de problèmes que j'avais eu.
Vous pouvez également générer des nombres premiers dans OpenSSL: OpenSSL Prime -Generate -Bits -Bits 512
Le plus grand 512 bits Prime est 2 ** 512-569 , trouvé à l'aide de: Python -C 'Imprimer ("\ n" .join ([STR (2 ** 512- (x * 2 +1)) pour x dans la plage (1000)])) '| xargs -n 1 openssl Prime
Il existe un algorithme due à l'U. Maurer qui génère des preuves aléatoires (contrairement à des nombres premiers statistiquement probables) qui sont presque uniformément répartis sur l'ensemble de tous les nombres premiers d'une taille spéciale. J'ai une implémentation de python qui est assez efficace à: http://s13.zetaboards.com/crypto/topic/7234475/1/