L'existence de fonctions à sens unique? Voici un problème mathématique d'un million de dollars!

Pouvez-vous le résoudre?

Introduction:

L'existence de fonctions à sens unique est l'un des problèmes les plus importants de la théorie informatique. Si vous ne savez pas ce qu'est une fonction à sens unique ou pourquoi son existence est si importante, ne craignez rien. Nous explorerons ensemble des fonctions à sens unique en commençant par les concepts fondamentaux, puis en nous efforçant de comprendre certaines des fonctions avancées et en essayant de répondre à la question figurant dans le titre. Mais pour comprendre les fonctions à sens unique et leurs applications, vous devez posséder des connaissances de base sur les ensembles et les mathématiques, ce que je suppose que vous possédez. Pour le dire simplement, pour l’instant, une fonction unidirectionnelle est une fonction qui est facile à calculer dans un sens mais difficile à inverser, difficile en ce sens qu’il n’existe aucune méthode efficace pour les résoudre. Laissons la deuxième partie du titre pour plus tard.

Concepts de base:

Commençons au tout début. Il y a plus d'un siècle, George Cantor, un mathématicien allemand, a présenté les concepts d'ensembles et a dérivé tous les théorèmes mathématiques d'un seul schéma d'axiomes, le postulat de Cantor, qui stipule que, pour chaque formule à ensembles théoriques A (x), elle suppose de définir ceux et seulement ceux x satisfaisant A. Cet axiome a rencontré beaucoup de contradictions, mais d'autres mathématiciens ont pragmatiquement remplacé le postulat de Cantor par une collection de ses cas restreints, limitant les types de propriétés autorisées A. En 1904, Zermelo remarqua qu'un autre axiome est nécessaire pour dériver toutes les mathématiques connues, l’axiome du choix, qui stipule que chaque fonction f a un inverse g tel que f (g (x)) = x pour x dans la gamme de f. Il a été accepté à contrecoeur et des preuves qui en dépendent sont isolées à ce jour. De plus, il a acheté des paradoxes. Laisse-moi décomposer ça pour toi.

· La plage de f est connue et ne dépend d'aucune autre information.

· Si nous avons x, nous pouvons facilement calculer f (x)

· Si y est dans la gamme de f, il est difficile de trouver x tel que f (x) = y.

Ceci constitue la base de ce que l’on appelle une fonction à sens unique.

Problème P versus NP:

Maintenant que vous savez de manière informelle ce que sont les fonctions unidirectionnelles et ses bases, nous devons comprendre le problème célèbre et le plus discuté de P versus NP. En termes simples, P représente des problèmes faciles à résoudre pour les ordinateurs et NP représente des problèmes qui ne sont pas faciles à résoudre pour les ordinateurs mais faciles à vérifier pour eux. Par exemple, un homme veut emballer 100 pastèques dans des boîtes. Chaque boîte peut contenir 20 kilogrammes sans se rompre. L’homme doit savoir si 10 boîtes suffiront pour emballer les 100 pastèques.

Cela peut sembler facile, mais ce n’est pas facile. Il vous faudrait passer par toutes les combinaisons possibles. Mais vérifier la réponse finale est cependant facile. La question reste ouverte. Les problèmes de P et les problèmes de NP sont-ils les mêmes types de problèmes? Ou, y a-t-il des problèmes qui peuvent être facilement vérifiés mais pas facilement résolus? En termes mathématiques, si P = NP, alors tous les problèmes du monde réel seraient assez faciles à résoudre. Et si vous pouviez le prouver, vous obtiendrez un million de dollars. Oui, tu l'as bien lu. Maintenant, voici la déclaration d'un million de dollars, L'existence de fonctions à sens unique si prouvé vrai, impliquerait P ≠ NP. Cela voudrait dire qu’aucun moyen général rapide de résoudre les problèmes de NP ne peut exister, peu importe la difficulté que nous avons à chercher. Il ya beaucoup plus dans le problème P contre NP, mais c’est tout pour le moment. Notre objectif est simplement de vous donner une idée de la relation entre les fonctions à sens unique et le problème P / NP. (Ouais! Si vous pouvez résoudre ce problème, vous avez droit à un million de dollars pour résoudre l'un des problèmes du Prix du Millénaire!)

Tentatives de résolution du problème:

Maintenant que vous avez bien compris l’énoncé du problème, examinons quelques-unes des tentatives précédentes pour résoudre ce problème relatif aux fonctions à sens unique. Encore une fois, vous devez avoir des connaissances de base en algèbre, ensembles et polynômes. Mais avant de plonger dans ces tentatives, il faut comprendre un concept mineur mais utile, à savoir la complexité temporelle.

Il existe un certain nombre de solutions à un problème donné. Par exemple, si je discute du même problème avec 10 amis différents, chacun d'entre eux apportera 10 solutions différentes à ce problème et je choisirai bien sûr la meilleure solution. Même est le cas avec des algorithmes. Un ordinateur prend un certain temps pour résoudre un problème en utilisant un algorithme donné. Nous voulons que nos machines résolvent le problème le plus rapidement possible en utilisant un algorithme efficace. Un algorithme efficace est un algorithme qui prend un minimum de temps pour résoudre un problème. Ainsi, la complexité temporelle d'un algorithme signifie le temps total requis par le programme pour s'exécuter jusqu'à son achèvement. Il est noté O et il s’appelle généralement Big O.

Premier essai:

Définissons une fonction f: {0: 1} n à {0,1} * soit (t1, t2). Ce serait une fonction à sens unique si et seulement si elle peut être calculée en temps t1 et pour tous les algorithmes A exécutés en temps t2 et pour tout x € {0,1}, A (f (x)) x. Mais , cette définition est assez problématique car la seconde exigence est trop forte car pour chaque fonction f et pour chaque x ∈ {0,1} n, nous pouvons construire un algorithme qui produira toujours x et donc A (f (x)) = x Il n’ya donc pas de fonction qui réponde à cette définition, c’est une tentative qui a échoué mais qui nous donne un indice sur l’existence possible d’une fonction.

Deuxième essai:

Essayons de faire une déclaration probabiliste - nous allons permettre à A d’inverser f sur une très petite fraction des points.Une fonction f: {0,1} n → {0,1} * est (t1, t2, ε) serait être une fonction à sens unique si et seulement si elle peut être calculée dans le temps t1 et pour tous les algorithmes A exécutés dans le temps t2, Prx∈ {0,1} n, c (A) [A (f (x)) = x ] <ε.

Cette définition est également problématique, car elle est trop facile à satisfaire: par exemple, prenons f ≡ 0, il est décidément facile à calculer. Aussi, étant donné un x aléatoire, il n’ya aucun moyen de deviner une pré-image de f (x) puisque chaque point est une pré-image de 0 = f (x). Donc, cette fonction satisfait à la définition, mais elle ne semble capturer aucune notion de dureté de calcul. C'est encore une tentative ratée.

Troisième tentative:

Une fonction f: {0,1} n → {0,1} * est une fonction unidirectionnelle si elle peut être calculée à l'aide d'un algorithme «efficace» (c.-à-d. En polynôme temporel dans la longueur en entrée) pour tous les algorithmes polynomiaux A ,

p (n) = Pr x {0,1}, c (A) [f (A (f (x))) = f (x)] est une fonction négligeable. Le passage à la formulation asymptotique a introduit un nouveau problème: si f (x) est beaucoup plus court que x, alors A n’aura pas le temps de travailler sur f (x) (son entrée et il doit être exécuté dans le temps polynomial jusqu’à sa longueur). une fois encore, il est trop facile de satisfaire à la définition.

Toutes ces tentatives ont quelque chose en commun: toutes ces fonctions ne se comportent comme des fonctions à sens unique que si les valeurs données sont de taille raisonnable. Si nous augmentons les valeurs, disons de manière exponentielle, ces algorithmes échoueraient. Nous pouvons donc comprendre que peut-être des fonctions à sens unique existent.

Cryptographie à clé publique:

Courtoisie d'image: TutorialsPoint

Maintenant que vous avez une compréhension de base des fonctions à sens unique et de leur fonctionnement, il est temps que nous en apprenions sur certaines fonctions à sens unique du monde réel qui sont conjecturées mais non prouvées. Cependant, ils sont largement utilisés dans le commerce et l'industrie. L'une des principales applications d'une fonction à sens unique supposée est la cryptographie à clé publique. Nous discuterons de la cryptographie en détail pour bien comprendre les fonctions à sens unique et leur fonctionnement dans le monde réel. En outre, cela vous donnerait des indices permettant de faire la preuve de l’existence de fonctions à sens unique.

Qu'est-ce que la cryptographie? En termes simples, la cryptographie est le processus de conversion d'informations ordinaires en données abstraites ou non reconnaissables, et inversement. Son objectif principal est de stocker et de transmettre des données en toute sécurité, de sorte que seules les personnes auxquelles elles sont destinées puissent accéder.

Prenons un exemple de deux personnes nommées Alice et Bob. Bob veut envoyer une lettre d’amour à sa petite amie Alice mais il ne veut pas que le facteur ou qui que ce soit le lise, à l’exception d’Alice. Donc, ce que fait Bob, il écrit la lettre sous une forme cryptée, ce qui signifie qu'il crypte les informations à l'aide d'un ensemble d'instructions secrètes appelé clé. Le contenu de la lettre ne peut être déchiffré qu'avec la clé spéciale utilisée pour le chiffrement. Bob écrit donc la lettre sous forme cryptée, puis la poste à Alice. Maintenant, le problème, c’est qu’il doit en quelque sorte partager sa clé secrète avec Alice afin qu’elle puisse déchiffrer facilement la lettre. D'une manière ou d'une autre, nous supposons que Bob a partagé la clé avec Alice sans que personne ne le sache et qu'elle peut maintenant déchiffrer facilement la lettre.

Nous avons "supposé" que Bob avait en quelque sorte partagé la clé avec Alice, mais comment? La façon dont les clés peuvent être transmises de manière sécurisée de l’expéditeur au destinataire est un problème majeur qui a déconcerté les informaticiens pendant un certain temps. Cependant, Diffie et Helman en 1976 ont proposé l’idée de systèmes de cryptographie à clé publique, un système de chiffrement dans lequel la clé utilisée pour chiffrer est différente de la clé utilisée pour déchiffrer (mot de fantaisie pour déchiffrer). Plusieurs fonctions unidirectionnelles ont été trouvées et sont utilisées dans la cryptographie à clé publique.

Un exemple standard décrivant la cryptographie à clé publique

Revenons à notre exemple précédent d’Alice et de Bob et modifions notre histoire pour comprendre l’idée générale de la cryptographie à clé publique. Bob place sa clé de chiffrement dans un répertoire public où tout le monde, y compris le facteur, peut la voir. Et Bob a une clé de déchiffrement différente de la clé publique que lui seul sait. Si Alice souhaite envoyer une lettre d'amour à Bob, elle vérifie la clé publique de l'annuaire public dans le répertoire public, chiffre le message à l'aide de EB (M) = C, où M est le message et C le texte, et EB la clé publique. envoie le texte chiffré C à Bob. Si le facteur tente d'intercepter, il ne pourra pas le déchiffrer. Remarquez, même Alice ne peut pas déchiffrer le message. Si vous pensez que si elle inverse le processus de cryptage, alors elle peut le déchiffrer, alors vous vous trompez. Rappelez-vous des fonctions à sens unique? Oui, elle peut chiffrer, mais elle ne peut pas déchiffrer car seul Bob détient les informations secrètes permettant de déchiffrer la clé. Ainsi, vous pouvez constater que Bob et Alice n’ont pas besoin de communication préalable pour l’échange de clés. Ils n'ont pas besoin de partager une clé secrète. Seul Bob peut déchiffrer les messages chiffrés avec sa clé de chiffrement publique et inversement. La clé secrète dont disposait Bob pour le déchiffrement est appelée une information de trappe ou une fonction de trappe, une fonction qui détient la clé pour déchiffrer les informations. Ces fonctions de trappe sont les fonctions à sens unique conjecturées. Plusieurs fonctions unidirectionnelles hypothétiques sont utilisées dans la cryptographie à clé publique, mais nous aborderons la plus importante, l'algorithme RSA.

RSA:

Source de l'image: ResearchGate

RSA signifie Rivest, Shamir, Adelman. Ils étaient les inventeurs des systèmes cryptographiques à clé publique. Un peu de calculs complexes nous attendent, mais ne craignez rien si vous ne comprenez rien. Nous avons fourni des liens de référence à la fin pour que vous puissiez les explorer davantage. Dans l’algorithme RSA, nous avons une clé publique, supposons (a, b) et une clé privée d. Pour chiffrer un message M (créer le texte chiffré c), le message est levé à ath et pour déchiffrer un texte chiffré C (revenir au message M), le texte chiffré est levé avec le pouvoir modulo n:

C ≡ E (M) Ma (mod b), crypter le message

M ≡ D (C) Cd (mod n), déchiffrer le message

Ceci est une description générale de l'algorithme RSA. Mais comment générer une clé RSA utilisable pour le cryptage et le décryptage? Voici les étapes pour générer une clé RSA.

· Calcule p comme un produit de deux très grands nombres premiers aléatoires a et b. Bien que p fasse partie d'une clé publique, les facteurs de p, a et b sont gardés secrets.

P = a * b

· Choisissez une clé de déchiffrement d comme un grand entier aléatoire relativement premier pour

(a - 1) * (b - 1). Leur plus grand commun diviseur doit être 1. Les inventeurs du cryptage RSA ont suggéré que tout nombre premier supérieur à max (a, b) suffirait pour la clé de déchiffrement d, mais il est important que d soit choisi dans un ensemble suffisamment grand pour qu'il ne puisse pas. être trouvé par recherche directe.

Gcd (d, (a - 1) * (b - 1) = 1

· Le chiffrement (clé publique) est calculé à l'inverse multiplicatif de d modulo

(a - 1) * (b - 1)

e * d ≡ 1 (mod (a - 1) * (p - 1))

Il est très important de noter que si p = ab et a, b sont des nombres premiers, la fonction totale d’Euler ⱷ (p) = (a - 1) * (b - 1). ⱷ (p) est le nombre de nombres plus petits que p et co-premiers avec p. Il n'y a pas d'algorithme efficace pour factoriser les grands entiers et si les facteurs a et b de p ne sont pas connus, il n'y a pas non plus de moyen efficace de calculer (n). La sécurité de la RSA réside dans cette propriété.

Conclusion:

Nous avons commencé avec la définition informelle des fonctions à sens unique, puis avons défini l'énoncé du problème en question. Nous avons discuté de certaines des tentatives précédentes pour résoudre ce problème et de la raison pour laquelle elles ont fini par être des échecs. Après cela, nous avons vu quelques-unes des fonctions unidirectionnelles conjecturées (c'est-à-dire supposées sans information complète) et comment elles sont mises en pratique dans l'industrie. En fin de compte, il est toujours mystérieux de pouvoir calculer des fonctions à sens unique en temps polynomial. C'est un mystère qui est encore abordé par les informaticiens à ce jour. C'est un mystère qui semble impossible à résoudre. Mais qui sait? Peut-être qu’après la lecture de cet article, il vous faut quelque chose dans votre esprit et c’est vous qui pourrez résoudre ce problème et gagner un million de dollars! En fin de compte, nous ne pouvons pas nier que le mystère qui entoure les fonctions unidirectionnelles persiste et que l’ensemble du tableau attend d’être découvert.

Voulez-vous plonger dans cette recherche? Visitez cette page Web P vs NP qui contient une compilation de toutes les ressources et documents de recherche liés à ce sujet pour commencer, une véritable bible pour ceux qui veulent se concentrer sur la résolution de ce problème.

Pour en savoir plus sur l’algorithme RSA, consultez ce lien, Algorithme RSA en cryptographie.

Références:

  1. Fonction à sens unique. (11 juin 2018). Récupérée de https://en.wikipedia.org/wiki/One-way_function
  2. Fonction à sens unique. (Dakota du Nord.). Extrait le 14 juin 2018 à l'adresse http://mathworld.wolfram.com/One-WayFunction.html.
  3. Bühler, P., Schlaich, P. et Sinner, D. (2018). PDF-Grundlagen. PDF Bibliothek Der Mediengestaltung, 2–11. doi: 10.1007 / 978–3–662–54615–4_1
  4. Tutoriels Point. (2018, janvier 08). Cryptage à clé publique. Extrait le 15 juin 2018 à l'adresse https://www.tutorialspoint.com/cryptography/public_key_encryption.htm.
  5. L., & A., L. (17 août 2003). Le conte des fonctions à sens unique. Extrait le 20 juin 2018 à l'adresse https://arxiv.org/abs/cs/0012023.
  6. Qu'est-ce que la cryptographie à clé publique? (Dakota du Nord.). Extrait de https://www.globalsign.com/en/ssl-information-center/what-is-public-key-cryptography/

(Cet article a été rédigé par Zeeshan Mushtaq, rédacteur technique de Research Nest)

Appliquez et partagez si vous avez aimé celui-ci, et suivez «Le nid de la recherche» pour un contenu plus perspicace.

Intéressé à collaborer avec The Research Nest dans certaines initiatives de recherche en ligne révolutionnaires? Envoyez un courrier électronique à l'adresse suivante: the.research.nest@gmail.com.