Génération de paramètres Diffie-Hellman (générateur)

Question

J'essaie d'implémenter un échange de clé diffie-hellman. Disons que j'ai trouvé un grand nombre premier p - comment puis-je trouver un générateur g? Restreint par la bibliothèque multiprécision que je dois utiliser, quelques opérations de base (+, *, -, /, pow, modExp, modMult, mod, gcd, isPrime, genRandomPrime, genRandomBits, et quelques autres) sont disponibles.

Ne serait-il travailler pour trouver un premier sûr q, de sorte que chaque numéro n pour lequel gcd(n,q) == 1 devrait être un générateur, non?

Answer 1

Vous avez déjà reçu l'avertissement rituel de ne pas rouler votre propre crypto si vous vous souciez de votre sécurité, alors voici comment trouver un générateur de sécurité q prime. Un nombre g dans la plage fermée [2, q - 2] est un générateur si et seulement si g^((q-1)/2)! = 1 mod q, que vous devez calculer avec l'algorithme standard pour l'exponentiation modulaire. Choisissez des valeurs aléatoires de g jusqu'à ce que l'on passe le test.

Answer 2

Vous avez essentiellement répondu à votre question. Juste le test gcd(n,q)==1 n'est pas nécessaire puisque q est premier. Cela signifie que tout nombre n, de sorte que n < q n'a pas le facteur commun avec q et gcd(n,q) sera toujours sortie 1.

Vous pouvez vérifier si q = 1 + 2 p est nombre premier. Si oui, alors ord (Zq) = q-1 = (2p + 1) -1 = 2p. Depuis ord (x) | ord (Zq) pour chaque x dans Zq ord (x) = 2 ou ord (x) = p ou ord (x) = 2p. Il suffit donc de vérifier si votre élément choisi au hasard x de {2, ..., q-1} est de l'ordre 2. Si non alors il est de commande p ou 2p et vous pouvez l'utiliser comme générateur.

Answer 3

En règle générale, ne posez pas de questions aux programmeurs sur la cryptographie. La cryptographie est subtile et, par conséquent, difficile d'une manière invisible qui conduit facilement à l'auto-tromperie sur sa propre compétence. Demandez plutôt aux cryptographes (dont beaucoup sont aussi des programmeurs). Stack Exchange a un tableau de cryptographie, où cette question a déjà été répondue.

https://crypto.stackexchange.com/questions/29926/what-diffie-hellman-parameters-should-i-use

Je pourrais ergoter avec les conseils là-bas, mais il est fondamentalement sain. À moins que vous ne vouliez vraiment apprendre les mathématiques pertinentes, je m'en remettrais aux autorités; ils sont cités dans la réponse ci-dessus.

En ce qui concerne la question mathématique que vous posez, voici une toute petite introduction. Le groupe multiplicatif modulo a prime p a la taille p-1. (Voir Fermat's Little Theorem.) Le order of any element doit diviser p-1. Le cas le plus favorable est où p-1 = 2q, où q est également premier.