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écial en cryptographie?

Est-ce que quelqu’un a une explication simple et courte? (Je sais qu’il y a beaucoup d’amorces et qu’Applied Cryptography est la Bible, mais comme je l’ai dit: je ne cherche pas à implémenter mon propre algorithme cryptographique et ce que j’ai trouvé a fait exploser mon cerveau. 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 élémentaire et générale: la cryptographie concerne la théorie des nombres et tous les nombres entiers (sauf 0 et 1) sont constitués de nombres premiers. Vous devez donc traiter beaucoup de nombres premiers en théorie des nombres.

    Plus précisément, certains algorithmes cryptographiques importants, tels que RSA, dépendent de manière critique du fait que la factorisation en nombres premiers des grands nombres prend du temps. Fondamentalement, vous avez une “clé publique” composée d’un produit de deux grands nombres premiers utilisés pour chiffrer un message, et d’une “clé secrète” constituée des 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 crypter des messages, mais vous seul connaissez les facteurs premiers et pouvez décrypter les messages. Tout le monde devrait prendre en compte le nombre, ce qui prend trop de temps pour être pratique, étant donné l’état actuel de la théorie des nombres.

    Simple? 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 sortingviale, et ce fait est la source de nombreux algorithmes cryptographiques. Voir les fonctions à sens unique pour plus d’informations.

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

    Voici un exemple très simple et commun.

    L’ algorithme de chiffrement RSA, couramment utilisé dans les sites Web de commerce sécurisé, repose sur le fait qu’il est facile de multiplier et multiplier deux nombres premiers (très grands), alors qu’il est extrêmement difficile de faire le contraire. très grand nombre, étant donné qu’il n’a que deux facteurs premiers, et les trouver.

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

    Il existe de bonnes ressources pour accélérer la cryptographie. En voici un:

    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 est possible de dériver la clé privée de la clé publique en recourant à la formule. Mais seul le produit des grands nombres premiers est public, et la prise en compte du nombre de cette taille dans les nombres premiers est si difficile que même les supercalculateurs les plus puissants du monde ne peuvent briser une clé publique ordinaire.

    Le livre de Bruce Schneier, Applied Cryptography, en est un autre. Je recommande fortement ce livre; c’est amusant à lire.

    Ce ne sont pas tellement 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 l’affacturage est si important est que les mathématiciens et les informaticiens ne savent pas comment factoriser un nombre sans simplement essayer toutes les combinaisons possibles. C’est-à-dire, essayez d’abord de diviser par 2, puis par 3, puis par 4 et ainsi de suite. Si vous essayez de prendre en compte 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 prendre en compte les types de nombres premiers utilisés en cryptographie.

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

    Pour être un peu plus concret sur la manière dont RSA utilise les propriétés des nombres premiers, l’algorithme RSA dépend essentiellement 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 totalisante d’Euler de N.

    D’où viennent les primes? Pour calculer efficacement la fonction de totalisateur d’Euler, 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.

    Plus abstraitement, de nombreux protocoles cryptographiques utilisent différentes fonctions de trappe , fonctions faciles à calculer mais difficiles à inverser. La théorie des nombres est une source riche de telles fonctions de trappe (telles que la multiplication de grands nombres premiers), et les nombres premiers sont absolument centraux à la théorie des nombres.

    Je suggère le livre Un voyage mathématique en code . Le livre a un sens de la terre, ce qui est surprenant, car il s’agit de cryptographie. Le livre résume le parcours de Sarah Flannery, de l’apprentissage des puzzles en tant qu’enfant à la création de l’algorithme Cayley-Purser (CP) à l’âge de 16 ans. Il fournit une explication incroyablement détaillée des fonctions à sens unique, de la théorie des nombres et des nombres premiers. 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 en utilisant des masortingces. Il é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 chiffrement, 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 d’environ 30 minutes, lien vers la transcription) traite des problèmes de cryptographie et explique pourquoi les nombres premiers sont importants.

    Je ne suis pas un mathématicien ou un crypticien, alors voici une observation extérieure en termes simples (pas d’équations de fantaisie, désolé).

    Ce fil de discussion est rempli d’explications sur la façon dont les nombres premiers sont utilisés en cryptographie, il est difficile de trouver quelqu’un expliquant de manière simple POURQUOI les nombres premiers sont utilisés … parce que tout le monde considère ces connaissances comme acquises.

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

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

    Le plus grand taux préférentiel connu (au mois de février 2015) est de 2 à la puissance de 257 885 161 – 1, soit 17 425 170 chiffres.

    Cela signifie qu’il n’y a aucun intérêt à garder une liste de tous les nombres premiers connus et beaucoup moins de toutes leurs sums possibles. Il est plus facile de prendre un numéro et de vérifier s’il s’agit d’un nombre premier.

    Calculer les grands nombres premiers en soi est une tâche monumentale, donc calculer en inverse deux nombres premiers qui ont été multipliés les uns avec les autres. Les cryptographes et les mathématiciens diraient que c’est assez difficile … aujourd’hui.

    Les algorithmes cryptographiques reposent généralement sur leur sécurité pour avoir un “problème difficile”. La plupart des algorithmes modernes semblent utiliser la factorisation de très grands nombres comme un problème difficile – si vous multipliez deux grands nombres ensemble, le calcul de leurs facteurs est “difficile” (c’est-à-dire long). Si ces deux nombres sont des nombres premiers, alors il n’y a qu’une seule réponse, ce qui rend la tâche encore plus difficile et garantit également que lorsque vous trouvez la réponse, c’est la bonne, pas une autre réponse qui donne le même résultat.

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

    Supposons que vous ayez un très grand nombre entier 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.

    En passant, il existe un article publié sur l’algorithme qui peut “résoudre” ce problème de factorisation en temps acceptable en utilisant un ordinateur quantique. Les nouveaux algorithmes de cryptographie ne peuvent donc plus compter sur cette “difficulté” de la factorisation en nombre lorsque l’ordinateur quantique arrive en ville 🙂

    Parce que les algorithmes de factorisation s’accélèrent considérablement avec chaque facteur trouvé. Rendre les deux clés privées primordiales garantit que le premier facteur trouvé sera également le dernier. Idéalement, les deux clés privées auront également une valeur presque égale, car seule la force des clés les plus faibles est importante.

    Les nombres premiers sont principalement utilisés en cryptographie, car ils consumnt beaucoup de temps 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