Pourquoi les nombres premiers sont-ils importants en cryptographie?

Une chose qui me frappe toujours en tant que non-cryptographe: pourquoi est-il si important d'utiliser des nombres premiers? Qu'est-ce qui les rend si spéciaux en cryptographie?

Quelqu'un at-il une courte explication simple ? (Je suis conscient qu'il existe de nombreuses amorces et que la cryptographie appliquée est la Bible, mais comme dit: je ne cherche pas à implémenter mon propre algorithme cryptographique, et ce que j'ai trouvé vient de faire exploser mon cerveau - pas de 10 pages de formules mathématiques S'il vous plaît :))

Merci pour toutes les réponses. J'ai accepté celui qui a rendu le concept le plus clair pour moi.

Explication la plus basique et générale: la cryptographie est une question de théorie des nombres , et tous les nombres entiers (sauf 0 et 1) sont constitués de nombres premiers, vous traitez donc beaucoup les nombres premiers dans la théorie des nombres.

Plus spécifiquement, certains algorithmes cryptographiques importants tels que RSA dépendent de manière critique du fait que la factorisation des nombres premiers de grands nombres prend beaucoup de temps. Fondamentalement, vous avez une "clé publique" constituée d'un produit de deux grands nombres premiers utilisés pour chiffrer un message, et d'une "clé secrète" constituée de ces deux nombres premiers utilisés pour déchiffrer le message. Vous pouvez rendre la clé publique publique, et tout le monde peut l'utiliser pour chiffrer les messages qui vous sont adressés, mais vous seul connaissez les facteurs premiers et pouvez déchiffrer les messages. Tout le monde devrait factoriser le nombre, ce qui prend trop de temps pour être pratique, étant donné l'état actuel de l'art de la théorie des nombres.

Facile? Ouaip.

Si vous multipliez deux grands nombres premiers, vous obtenez un grand nombre non premier avec seulement deux (grands) facteurs premiers.

La factorisation de ce nombre est une opération non triviale, et ce fait est la source de nombreux algorithmes cryptographiques. Voir les fonctions unidirectionnelles pour plus d'informations.

Addendum: Juste un peu plus d'explications. Le produit des deux nombres premiers peut être utilisé comme clé publique, tandis que les nombres premiers eux-mêmes peuvent être utilisés comme clé privée. Toute opération effectuée sur des données qui ne peut être annulée qu'en connaissant l'un des deux facteurs ne sera pas facile à déchiffrer.

Voici un exemple très simple et courant.

L' algorithme de cryptage RSA, couramment utilisé dans les sites Web de commerce sécurisé, est basé sur le fait qu'il est facile de prendre deux (très grands) nombres premiers et de les multiplier, alors qu'il est extrêmement difficile de faire le contraire - c'est-à-dire: prendre un très grand nombre, étant donné qu'il n'a que deux facteurs premiers, et les trouver.

Ce ne sont pas tant les nombres premiers eux-mêmes qui sont importants, mais les algorithmes qui fonctionnent avec les nombres premiers. En particulier, trouver les facteurs d'un nombre (n'importe quel nombre).

Comme vous le savez, tout nombre a au moins deux facteurs. Les nombres premiers ont la propriété unique en ce sens qu'ils ont exactement deux facteurs: 1 et eux-mêmes.

La raison pour laquelle la factorisation est si importante est que les mathématiciens et les informaticiens ne savent pas comment factoriser un nombre sans simplement essayer toutes les combinaisons possibles. Autrement dit, essayez d'abord de diviser par 2, puis par 3, puis par 4, et ainsi de suite. Si vous essayez de factoriser un nombre premier - en particulier un très grand nombre - vous devrez essayer (essentiellement) tous les nombres possibles entre 2 et ce grand nombre premier. Même sur les ordinateurs les plus rapides, il faudra des années (voire des siècles) pour factoriser les types de nombres premiers utilisés en cryptographie.

C'est le fait que nous ne savons pas comment factoriser efficacement un grand nombre qui donne aux algorithmes cryptographiques leur force. Si, un jour, quelqu'un trouve comment le faire, tous les algorithmes cryptographiques que nous utilisons actuellement deviendront obsolètes. Cela reste un domaine de recherche ouvert.

Parce que personne ne connaît un algorithme rapide pour factoriser un entier en ses facteurs premiers. Pourtant, il est très facile de vérifier si un ensemble de facteurs premiers se multiplie en un certain entier.

Il existe de bonnes ressources pour accélérer la crypto. En voici une:

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

De cette page:

Dans le système de cryptographie à clé publique le plus couramment utilisé, inventé par Ron Rivest, Adi Shamir et Len Adleman en 1977, les clés publiques et privées sont dérivées d'une paire de grands nombres premiers selon une formule mathématique relativement simple. En théorie, il pourrait être possible de dériver la clé privée de la clé publique en travaillant la formule à l'envers. Mais seul le produit des grands nombres premiers est public, et la factorisation de nombres de cette taille en nombres premiers est si difficile que même les supercalculateurs les plus puissants du monde ne peuvent pas casser une clé publique ordinaire.

Le livre Applied Cryptography de Bruce Schneier en est un autre. Je recommande vivement ce livre; c'est amusant de lire.

Pour être un peu plus concret sur la façon dont RSA utilise les propriétés des nombres premiers, l'algorithme RSA dépend de manière critique du théorème d'Euler , qui stipule que pour les nombres premiers "a" et "N", a ^ e est congru à 1 modulo N, où e est la fonction totiente d'Euler de N.

D'où viennent les nombres premiers? Pour calculer efficacement la fonction totiente d'Euler de N, il faut connaître la factorisation première 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 connaître p et q, le calcul de e est très difficile.

De manière plus abstraite, de nombreux protocoles cryptographiques utilisent diverses fonctions de trappe , des fonctions faciles à calculer mais difficiles à inverser. La théorie des nombres est une riche source de ces fonctions de trappe (comme la multiplication de grands nombres premiers), et les nombres premiers sont absolument essentiels à la théorie des nombres.

Je suggérerais le livre A Mathematical Journey In Code . Le livre a une belle sensation terre-à-terre, ce qui est surprenant, car il s'agit de cryptographie. Le livre résume le parcours de Sarah Flannery, de l'apprentissage d'énigmes dans l'enfance à la création de l'algorithme Cayley-Purser (CP) à l'âge de 16 ans. Il donne une explication incroyablement détaillée des fonctions à sens unique, de la théorie des nombres et des nombres premiers et de leur relation cryptographie.

Ce qui rend ce livre encore plus spécifique à votre question, c'est que Sarah a essayé d'implémenter un nouvel algorithme à clé publique utilisant des matrices. C'était beaucoup plus rapide que d'utiliser des nombres premiers, mais un trou de boucle a été trouvé qui pourrait l'exploiter. Il s'avère que son algorithme était mieux utilisé comme mécanisme de cryptage privé. Le livre est un excellent témoignage de l'utilisation des nombres premiers pour le cryptage, car il a résisté à l'épreuve du temps et aux défis des individus très intelligents.

Une ressource de plus pour vous. Sécurité maintenant! l'épisode 30 (podcast ~ 30 minutes, le lien vers la transcription) parle des problèmes de cryptographie et explique pourquoi les nombres premiers sont importants.

Je ne suis ni mathématicien ni crypticien, alors voici une observation extérieure en termes simples (pas d'équations fantaisistes, désolé).

Ce fil entier est rempli avec des explications sur COMBIEN les nombres premiers sont utilisés en cryptographie, il est difficile de trouver quelqu'un dans ce fil qui explique de manière simple Pourquoi les nombres premiers sont utilisés ... plus probablement parce que tout le monde prend pour acquis que la connaissance.

Seul le fait de regarder le problème de l'extérieur peut générer une réaction comme; mais s'ils utilisent les sommes de deux nombres premiers, pourquoi ne pas créer une liste de toutes les sommes possibles que deux nombres premiers peuvent générer?

Sur ce site, il y a une liste de 455 042 511 nombres premiers, où les nombres premiers les plus élevés sont 9 987 500 000 ( 10 chiffres).

Le plus grand nombre premier connu (en février 2015) est de 2 à la puissance de 257 885 161 - 1, soit 17 425 170 chiffres.

Cela signifie qu'il est inutile de garder une liste de tous les nombres premiers connus et encore moins de toutes leurs sommes possibles. Il est plus facile de prendre un nombre et de vérifier s'il s'agit d'un nombre premier.

Calculer de gros nombres premiers en soi est une tâche monumentale, donc le calcul inverse de deux nombres premiers qui ont été multipliés l'un avec l'autre, les cryptographes et les mathématiciens diraient que c'est déjà assez difficile ... aujourd'hui.

Les algorithmes cryptographiques reposent généralement pour leur sécurité sur un "problème difficile". La plupart des algorithmes modernes semblent utiliser la factorisation de très grands nombres comme leur problème difficile - si vous multipliez deux grands nombres ensemble, calculer leurs facteurs est «difficile» (c'est-à-dire prend du temps). Si ces deux nombres sont des nombres premiers, il n'y a qu'une seule réponse, ce qui rend les choses encore plus difficiles et garantit également que lorsque vous trouvez la réponse, c'est la bonne, pas une autre réponse qui donne simplement le même résultat.

Je pense que ce qui est important en cryptographie, ce ne sont pas les nombres premiers en soi, mais c'est la difficulté du problème de la factorisation des nombres premiers

Supposons que vous ayez un entier très très grand qui est connu pour être le produit de deux nombres premiers m et n, il n'est pas facile de trouver ce que sont m et n. Un algorithme tel que RSA dépend de ce fait.

À propos, il existe un article publié sur l'algorithme qui peut «résoudre» ce problème de factorisation des nombres premiers en un temps acceptable en utilisant un ordinateur quantique. Ainsi, les nouveaux algorithmes de cryptographie peuvent ne plus s'appuyer sur cette "difficulté" de la factorisation première lorsque l'ordinateur quantique arrive en ville :)

Parce que les algorithmes de factorisation accélèrent considérablement avec chaque facteur trouvé. Rendre les deux clés privées prime garantit que le premier facteur trouvé sera également le dernier. Idéalement, les deux clés privées auront également une valeur presque égale puisque seule la force de la clé la plus faible compte.

Les nombres premiers sont principalement utilisés en cryptographie car cela prend un temps considérable pour déterminer si un nombre donné est un nombre premier ou non. Pour le hacker, si un algorithme prend beaucoup de temps pour casser le code, il devient inutile pour eux