Pourquoi les nombres premiers sont importants en cryptographie ?

Question

Une chose qui me frappe toujours comme un non-cryptographe: Pourquoi est-il si important d'utiliser des nombres premiers? Ce qui les rend si spécial dans la cryptographie?

Quelqu'un aurait-il une simple brève explication? (Je suis conscient qu'il existe de nombreuses amorces et que Cryptographie Appliquée est la Bible, mais comme a dit: je ne cherche pas à mettre en œuvre mon propre algorithme de chiffrement, et le truc que j'ai trouvé juste fait mon cerveau exploser - n ° 10 pages de formules mathématiques s'il vous plaît :))

Merci pour toutes les réponses. J'ai accepté celle qui a fait de la notion même plus clair pour moi.

Answer 1

Plus fondamentaux et généraux explication: la cryptographie est tout au sujet de la théorie des nombres, et tous les nombres entiers (sauf 0 et 1) sont constitués de nombres premiers, de sorte que vous traitez avec des nombres premiers pour beaucoup dans la théorie des nombres.

Plus précisément, certains de nos principaux algorithmes cryptographiques tels que RSA dépendent de manière critique le fait que la factorisation des grands nombres prend beaucoup de temps. Fondamentalement, vous avez une "clé publique" consistant en un produit de deux grands nombres premiers utilisée pour chiffrer un message, et une "clé secrète", composé de l'amorce utilisée pour décrypter le message. Vous pouvez faire la clé publique du public, et tout le monde peut l'utiliser pour crypter des messages pour vous, mais vous êtes seul à connaître les facteurs premiers et peut déchiffrer les messages. Tout le monde aurait à facteur du nombre, qui prend trop de temps pour être pratiques, compte tenu de l'état actuel de l'art de la théorie des nombres.

Answer 2

Simple? Yup.

Si vous multiplier deux grands nombres premiers, vous avez un énorme non-nombre premier avec seulement deux (grandes) facteurs premiers.

L'affacturage que le nombre est un non-trivial de l'opération, et de ce fait est la source de beaucoup d'algorithmes de Chiffrement. Voir d'une manière fonctions pour plus d'informations.

Addendum: Juste un peu plus d'explication. Le produit de deux nombres premiers peut être utilisé comme une clé publique, tandis que les nombres premiers eux-mêmes comme une clé privée. Toute opération effectuée à des données qui ne peuvent être annulées par la connaissance de l'un des deux facteurs non négligeables pour les décrypter.

Answer 3

Voici un exemple très simple et commun.

L' algorithme de chiffrement RSA qui est couramment utilisé dans les sites web de commerce sécurisé, est basée sur le fait que c’est facile à prendre deux nombres premiers (très grands) et de se multiplier, alors qu’il est extrêmement difficile de faire le contraire - ce qui signifie : prendre un très grand nombre , étant donné qu’elle a seulement deux facteurs premiers et les trouver.

Answer 4

Car personne ne sait un algorithme rapide pour factoriser un nombre entier dans ses facteurs premiers. Pourtant, il est très facile de vérifier si un ensemble de facteurs premiers se multiplie pour un certain entier.

Answer 5

Il y a quelques bonnes ressources pour la rampe sur la crypto. En voici un:

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

À partir de cette page:

Dans les plus couramment utilisés à clé publique système de cryptographie, inventé par Ron Rivest, Adi Shamir et Len Adleman en En 1977, à la fois le public et le privé les touches sont dérivées à partir d'une paire de grands nombres premiers, selon un relativement simple mathématique de la formule. En théorie, il pourrait être possible de dériver la clé privée à partir de la clé publique par le travail la formule à l'envers. Mais seulement la produit de grands nombres premiers est public, de l'affacturage, les numéros de taille en nombres premiers est tellement fort que même le plus puissant des supercalculateurs dans le monde cant pause ordinaire la clé publique.

Bruce Schneier livre de Cryptographie Appliquée en est une autre. Je recommande fortement ce livre; c'est le plaisir de la lecture.