Pourquoi sont premiers important en cryptographie?
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 a une simple courte 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 :))
Grâce pour toutes les réponses. J'ai accepté celle qui a fait de la notion même plus clair pour moi.
- Quelques observations: 1. Les gens en dessous de mentionner que "la factorisation des grands nombres prend beaucoup de temps". En fait, la même chose est vraie pour toute factorisation. Ce qui est important, c'est que tout entier != 0 a une unique factorisation comme produit de nombres premiers (dont 1 qui a de la décomposition de longueur 0).
- 2. Veuillez vérifier mon explication pourquoi les nombres premiers sont importants pour le hachage fonctions: stackoverflow.com/questions/1145217/... Elle est liée à la propriété des polynômes à coefficients appartenant à un domaine (qui n'est probablement pas une courte explication).
- Trop simple courte explication → Résoudre:
a * b = 91. Maintenant, à résoudre:13 * 7 = x. La deuxième équation est beaucoup plus rapide à résoudre (pour un humain ou un ordinateur).
Vous devez vous connecter pour publier un commentaire.
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 spécifiquement, quelques algorithmes cryptographiques tels que RSA dépendent de manière critique le fait que la factorisation en nombres premiers d'un grand nombre 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 ces deux nombres premiers 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.
Simple? Yup.
Si vous multiplier deux grands nombres premiers, vous avez un énorme non-nombre premier avec seulement deux (grandes) facteurs premiers.
D'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.
Voici un exemple simple et commun.
La L'algorithme de chiffrement RSA qui est couramment utilisé dans le commerce sécurisé de sites web, est basée sur le fait qu'il est facile de prendre les deux (très grand) de nombres premiers et de les multiplier, alors qu'il est extrêmement difficile de faire le contraire - sens: prendre un très grand nombre, compte tenu de laquelle il n'a que deux facteurs premiers, et de les trouver.
Parce que personne ne sait, un algorithme rapide pour factoriser un nombre entier en ses facteurs premiers. Pourtant, il est très facile de vérifier si un ensemble de facteurs premiers de se multiplier pour un certain entier.
Ce n'est pas tellement le premier des nombres eux-mêmes, qui sont importants, mais les algorithmes qui fonctionnent avec les nombres premiers. En particulier, trouver les facteurs d'un nombre (un nombre).
Comme vous le savez, n'importe quel nombre a au moins deux facteurs. Les nombres premiers ont la propriété unique en ce qu'ils ont exactement deux facteurs: 1 et eux-mêmes.
La raison d'affacturage est si important, c'est les mathématiciens et les informaticiens ne savent pas comment le facteur d'un nombre sans simplement en essayant toutes les combinaisons possibles. C'est, d'abord essayez de diviser par 2, puis par 3, puis par 4, et ainsi de suite. Si vous essayez de facteur d'un nombre premier, surtout un très grand--vous devrez essayer (essentiellement) chaque nombre entre 2 et que grand nombre premier. Même sur les ordinateurs les plus rapides, il va prendre des années (voire des siècles) de facteur les sortes de nombres premiers utilisés en cryptographie.
C'est le fait que nous ne savons pas comment efficacement facteur un grand nombre qui donne des algorithmes cryptographiques leur force. Si, un jour, quelqu'un a les chiffres de comment le faire, tous les algorithmes de chiffrement, nous utilisons actuellement deviendront obsolètes. Cela reste une zone ouverte de la recherche.
nn'est pas le premier &n = a * b. Sia > sqrt(n),bdoit être plus petite et vice-versa, d'autrea * b > nlui-même qui irait à l'encontre de notre demande initiale. Afin de vérifier, pour le premier, nous voulons seulement vérifier jusqu'à la racine.Il y a quelques bonnes ressources pour la rampe sur la crypto. En voici un:
À partir de cette page:
De Bruce Schneier livre Cryptographie Appliquée en est une autre. Je recommande fortement ce livre; c'est le plaisir de la lecture.
À être un peu plus concret sur la façon RSA utilise les propriétés des nombres premiers, de l'algorithme RSA dépend de façon critique sur Le Théorème d'Euler, qui stipule que, pour les premiers numéros de "a" et "N", un^e est congru à 1 modulo N, où e est l' Euler indicateur de fonction de N.
Où les nombres premiers viennent dans cette? Pour calculer l'indicateur d'Euler fonction de N efficacement nécessite de connaître la factorisation de N. Dans le cas de l'algorithme RSA, où N = pq pour certains nombres premiers "p" et "q", alors e = (p - 1)(q - 1) = N - p - q + 1. Mais, sans le savoir p et q, le calcul de e est très difficile.
De manière plus abstraite, de nombreux crypotgraphic l'utilisation de protocoles différents trappe fonctions, les fonctions qui sont faciles à calculer, mais difficile à inverser. La théorie des nombres est une riche source de cette trappe fonctions (telles que la multiplication de grands nombres premiers), et les nombres premiers sont absolument central de la théorie des nombres.
Je vous suggère le livre Mathématique Voyage Dans Le Code. Le livre a une belle descente à terre ressentir, ce qui est surprenant, puisqu'il s'agit de la cryptographie. Le livre résume Sarah Flannery voyage de l'apprentissage des énigmes comme un enfant à la création de la Cayley-Commissaire de bord (CP) de l'algorithme à l'âge de 16 ans. Il donne une merveilleuse explication détaillée des fonctions, théorie des nombres, et les nombres premiers et comment ils se rapportent à la cryptographie.
Ce qui rend ce livre encore plus spécifiques à votre question est que Sarah a essayé de mettre en œuvre un nouvel algorithme de clé publique à l'aide de la matrice de l'. Il était beaucoup plus rapide, puis à l'aide de nombres premiers, mais un trou de boucle a été constaté que pourrait l'exploiter. Il s'avère que son algorithme a été mieux utilisé à titre privé un mécanisme de chiffrement. Le livre est un grand testament à l'aide de nombres premiers pour le chiffrement comme il a résisté à l'épreuve du temps et les défis de très intelligent individus.
Un de plus de ressources pour vous. Sécurité Maintenant! épisode 30(~30 minutes de podcast, le lien est à la transcription) parle de cryptographie questions, et explique pourquoi les nombres premiers sont importantes.
Je ne suis pas un mathématicien ou cryptician, voici donc en dehors de l'observation en termes simples (pas de fantaisie, des équations, désolé).
Ce thread entier est rempli avec des explications sur COMMENT nombres premiers sont utilisés en cryptographie, il est difficile de trouver quelqu'un dans ce fil de discussion en expliquant de manière simple POURQUOI nombres premiers sont utilisés ... probablement parce que tout le monde considère que la connaissance de soi.
Regardant uniquement le problème de l'extérieur peut générer une réaction; mais s'ils utilisent les sommes de deux nombres premiers, pourquoi ne pas créer une liste de toutes les sommes de deux nombres premiers peut générer?
Sur ce site il y a une liste de 455,042,511 nombres premiers, où le plus grand nombres premiers est 9,987,500,000 (10 chiffres).
Le plus connu, le premier (en février 2015) est 2 à la puissance de 257,885,161 − 1 qui est 17,425,170 chiffres.
Cela signifie qu'il n'y a pas de point de tenir à jour une liste de tous les nombres premiers connus et beaucoup moins tout leur possible des sommes. Il est plus facile de prendre un numéro et de vérifier si c'est un nombre premier.
Calcul de grands nombres premiers en lui-même est une tâche monumentale, donc inverse le calcul de deux nombres premiers qui a été multiplié les uns avec les autres à la fois les cryptographes et les mathématiciens diraient est assez dur ... aujourd'hui.
Algorithmes cryptographiques généralement compter pour leur sécurité, pour avoir un "problème difficile". La plupart des algorithmes modernes semblent utiliser la prise en compte du très grand nombre comme leur problème difficile - si vous multiplier deux grands nombres, le calcul de leurs facteurs est "difficile" (c'est à dire de temps). Si ces deux nombres sont des nombres premiers, alors il n'y a qu'une seule réponse, ce qui rend encore plus difficile, et garantit également que, lorsque vous trouvez la réponse, c'est la bonne, pas une autre réponse qui arrive juste à donner le même résultat.
Je pense que ce qui est important dans la cryptographie ne sont pas des nombres premiers, mais il est le difficulté de le premier problème de la factorisation de
Supposons que vous avez très très grand nombre entier qui est connu pour être le produit de deux nombres premiers, m et n, il n'est pas facile à trouver, ce sont des m et n. Algorithme tel que RSA dépend de ce fait.
Par le façon, il ya un article publié sur un algorithme qui peut "résoudre" ce premier problème de la factorisation dans délai acceptable à l'aide de l'ordinateur quantique. Ainsi de nouveaux algorithmes de cryptographie peut pas s'appuyer sur cette "difficulté" de la factorisation en nombres premiers plus lorsque l'ordinateur quantique vient à la ville 🙂
Parce que les algorithmes de factorisation d'accélérer considérablement avec chaque facteur trouvés. Faisant à la fois les clés privées premier assure le premier facteur trouvé sera également la dernière. Idéalement, les deux clés privées seront également à peu près égaux en valeur depuis seulement la force de la faiblesse des questions clés.
Nombres premiers sont principalement utilisés en cryptographie, car il consomme beaucoup de temps pour déterminer si un nombre donné est premier nombre ou pas. Pour le hacker si l'algorithme prend beaucoup de temps pour briser le code, il devient inutile pour eux