Pourquoi nombre premier utilisé dans l'échange de clés Diffie-Hellman

Question

Je l'ai cherché mais je n'ai pas trouvé ma réponse. Dans l'algorithme d'échange de clés Diffie-Hellman opération utilisée comme

2^8 mod (%) Prime Nombre

Ma requête est quelle est la raison en utilisant le numéro premier lieu d'utiliser un autre numéro? Si possible, donnez-moi un exemple de la vie réelle ou donnez-moi un exemple lucide avec des explications.

Answer 1

Les nombres premiers ne se décomposent pas en facteurs plus petits, ce qui rend le code ou le hachage beaucoup plus difficile que l'utilisation, disons 12, qui se décompose avec/2 ou/3 ou/4 ou/6. Le nombre premier 7 est inférieur à 12, mais n'a que le facteur 7, il y a donc moins de vecteurs d'attaque. C'est une simplification excessive drastique, mais j'espère aider un peu.

Voici un exemple précis:

2^x mod 12

Cela a seulement 2 valeurs possibles, pour tout x supérieur à 1: 4 ou 8. Comme il est utilisé pour générer la clé partagée dans un de la même manière, vous vous retrouvez avec les mêmes deux possibilités. En d'autres termes, une fois que vous savez que la base et le mod sont 2 et 12 (que tout ordinateur qui écoute sur la conversation pourrait capter), vous savez automatiquement que la clé de chiffrement secrète partagée peut être l'une des deux possibilités. Il suffit de deux opérations simples pour déterminer lequel déchiffre le message. Maintenant, regardons un mod premier:

2^x mod 13

Cela a 12 possibilités différentes, pour x> 1. Il a également 12 différentes clés partagées possibles qui peuvent être générées. Il faut donc 6 fois plus de puissance de calcul pour déchiffrer un message basé sur ce module prime que pour l'exemple du mod 12.

2^x mod 14 a 4 possibilités.

2^x mod 15 a 4

2^x mod 16 effondrements complètement dans une possibilité après x = 3 (qui est la raison pour laquelle le choix d'une base qui correspond aux exigences de DH est important)

2^x mod 17 a ... vous l'avez deviné, 16 possibilités! Les nombres premiers ne sont-ils pas frais? :)

Ainsi, oui, la factorabilité du nombre de module a tout à voir avec la capacité de craquage du message crypté.