En passant sur un forum d'amateurs d'Histoire, je suis passé sur un topic parlant de la cryptographie lors de la seconde guerre mondiale (Enigma, Turing/Rejewski, toussa).
Je me suis emballé et j'ai rapidement rédigé une réponse de mémoire, exposant mes connaissances d'amateur sur la cryptographie moderne. La réponse est rapidement devenue assez conséquente, et je me demande si elle ne pourrait pas servir de base à un article de vulgarisation plus complet.
Je m'auto-cite :
Alan Turing est un personnage très intéressant et on le considère comme un des pères fondateurs des théories de l'Intelligence Artificielle et de la science de l'informatique fondamentale en général.
En particulier, il a démontré qu'il existait des problèmes pour lesquels aucun algorithme ne trouverait jamais de solution (ce sont des problèmes indécidables).
Il existe aussi des problèmes pour lesquels la durée d'exécution de l'algorithme évolue exponentiellement avec le nombre d'informations. Ces problèmes sont au coeur de la cryptographie moderne. Ainsi, si un programme met 2 secondes à casser une clé 8 bits (généralement en essayant toutes les clés possibles, les algorithmes de cryptage étant a priori mathématiquement conçus pour ne pas permettre d'autre méthode), il mettra 4 secondes à casser une clé 9 bits, 8 secondes à casser une clé 10 bits... A 16 bits, on en est déjà à 8 minutes, à 24 bits à 36 heures... A 128 bits, il faudrait un milliard de milliards de milliards d'années de calculs pour "casser" le cryptage !
On sent bien que l'augmentation de puissance des ordinateurs n'est pas une solution suffisante au décryptage... D'ailleurs ils est très facile d'augmenter la taille des clés.
Une propriété très importante de ces algorithmes est que même en en connaissant parfaitement les rouages, il est impossible de décrypter des messages sans disposer de la clé de décryptage.
Le problème, c'est que personne n'a réussi à démontrer mathématiquement que ce type de problèmes exponentiels existait ! Ou plutôt, on connaît des problèmes qu'on ne sait résoudre que de cette manière, mais personne n'a réussi à démontrer qu'il n'existerait pas une méthode susceptible de résoudre ces problèmes sans augmentation exponentielle des temps de calcul. Trouver de tels algorithmes est le travail de la majorité des chercheurs en intelligence artificielle aujourd'hui (ces algorithmes ont d'ailleurs des applications ailleurs qu'en cryptographie).
De plus, face à un message crypté, il existe des méthodes basées sur les statistiques susceptibles d'aider au décryptage des messages. Cacher les messages cryptés dans des documents anodins (données musicales, images...) permet de renforcer encore la protection.
D'autre part, même en supposant qu'on ait le moyen d'avoir des algorithmes de cryptage totalement incassables, la gestion des clés de cryptage et de décryptage est également quelque chose de très complexe. Actuellement, la plupart des méthodes de cryptage utilisent un système de "double clés", publique et privée. La clé publique permet de cryptage de message, et la clé privée en permet de décryptage. La clé publique est générée à partir de la clé privée, et il est normalement impossible de retrouver la clé privée à partir de la clé publique (en fait le problème est le même que pour le décryptage lui même, voir paragraphe ci dessus).
De cette façon, la clé publique peut être envoyée à tout le monde sans problème, et vous serez le seul à pouvoir lire les messages codés avec la clé publique.
Ce système de paire de clés permet également la "signature numérique" des messages : à partir du contenu du message et de la clé privée, on génère une "signature". Avec la clé publique, on peut vérifier que la signature n'a pu être réalisée qu'à partir de la clé privée. Ainsi, on est sûr que le message provient bien du possesseur de la clé privée associée à la clé publique dont on dispose.
Il existe même des systèmes permettant de se prémunir contre les fausses clés (si je publie une clé publique en me faisant passer pour quelqu'un d'autre, je pourrais facilement signer des messages à son nom).
Je sollicite l'avis des mou^W linuxéfèriens avisés, pour corriger les grosses coquilles (et en même temps parfaire mes connaissances sur le sujet). N'oubliez pas que je destine ce texte plutôt à un article de vulgarisation, mais à titre personnel je suis ouvert aux détails techniques.
Pour info, les informations sur la complexité des algorithmes, et notamment l'absence de démonstration P=NP provient de plus ou moins vagues souvenirs d'un DEA d'IA, et la partie concernant les clé, de l'installation et configuration d'Enigmail (oui, j'ai pas été chercher bien loin).
Et si ça intéresse quelqu'un, je mets la partie entre "blockquote" sous licence FDL. Là.
P.S. Ah tiens, le correcteur orthographique de LinuxFR me rappelle qu'on dit "chiffrage" et non pas "cryptage". Je pourrais le corriger, mais ça serait long, et ça permettra de le rappeler.
# et wikipedia alors ?
Posté par fabien . Évalué à 7.
http://fr.wikipedia.org/wiki/Cryptographie(...)
[^] # Re: et wikipedia alors ?
Posté par Mes Zigues . Évalué à 3.
À la question Je me demande si elle ne pourrait pas servir de base à un article de vulgarisation plus complet ? c'est la seule réponse valable.
C'est même à proposer à toutes vos connaissances qui se targuent de fare la vulgarisation.
# Chiffrage, cryptage, cassage, vocabulairage
Posté par jojo2002 . Évalué à 2.
Vulgarisation oui mais en respectant les termes :
chiffrement = ce que tu entends par crypter
déchiffrement = ce que tu entends parfois par décrypter çàd effectuer une opération légitime (en disposant de la clé) avec de récupérer le clair à partir du chiffré.
décryptage/cryptanalyse = la même manip que précédemment mais non légitime. Il existe tout un tas d'attaque pour trouver le clair sans connaître la clé donc la plus bourrine est effectivement la force brute.
# Houla, IA n'est pas algo !
Posté par Sylvain Sauvage . Évalué à 2.
Trouver des problèmes et/ou des algorithmes P=NP, (ça revient à peu près au même en algo, car ce que l'on veut prouver, c'est que P=NP ou P!=NP), c'est le boulot des algorithmiciens, des chercheurs en algorithmique.
Les chercheurs en IA, ils font de l'IA : ils cherchent des modèles et des techniques pour que la machine « montre » de l'« intelligence », qu'elle « raisonne », qu'elle aide.
(Notez tous les guillemets. Ces guillemets s'épaississent depuis les années 60-70 où l'on imaginait pouvoir dire ce qu'est l'intelligence et donc en « créer »...)
En IA, les problèmes NP (NP-complets ou NP-difficiles) peuvent être gênants, alors on utilise d'autres techniques pour les contourner (p.ex. quelques heuristiques qui permettent de réduire le problème ou d'approcher une solution). Mais ceux qui cherchent à démontrer que P=NP ou P!=NP, ce sont les algorithmiciens.
(Notez que si un chercheur en IA tombe sur un problème NP et démontre qu'il est P, il sera content quand même, mais ce n'est pas son but principal.)
[^] # Re: Houla, IA n'est pas algo !
Posté par Anonyme . Évalué à 1.
J'aime bien ton euphémisme.
En fait c'est un certain groupe de chercheurs s'est persudé qu'ils réussiraient à faire de l'intelligence (sans guillemets) à partir de leur base de recherche.
Ils on appelé leur discipline (eux-mêmes) Intelligence artificielle.
Notons que leurs traveux de recherche ont aboutis à des résultats très intéressant, et utilisés dans l'informatique de nos jour.
Mais leur principale découverte, c'est qu'ils ne pourraient jamais faire de l'intelligence, de la vraie !.
Du coups, maintenant il y des gens qui étudient l'intelligence artificitielle, alors que maintenant c'est bien connu, l'intelligence artificielle ne fait rien d'intelligent.
comme quoi, il ne faut jamais le laisser de côté le 'AMHA'.
[^] # Re: Houla, IA n'est pas algo !
Posté par Yusei (Mastodon) . Évalué à 3.
C'est un scoop ça, non ? C'est dans quel papier au juste que quelqu'un a montré qu'une machine de Turing ne pourrait jamais répondre à nos critères d'intelligence ?
[^] # Re: Houla, IA n'est pas algo !
Posté par Anonyme . Évalué à 3.
=> sous entendu, dans le cadre de leur base de recherche, et par extension, ils ne pourraient pas eux-même, dans cet axe de recherche, trouver un moyen de faire de l'intelligence artificielle.
Pour l'instant, le seul espoir de pourvoir réaliser un jour une intelligence artificielle se voit en sciences cognitives (en résumé bref, c'est l'étude de l'acquisition des connaissance et donc des processus de raisonnement, l'objectif étant de les formaliser - imaginez un systeme formel modélisant l'intelligence, moi ca me laisse reveur).
Ceci n'a rien a voir avec les automates et automates auto régulés. C'est de ca qu'était parti le groupe de recherche en "Intelligence Artificielle", et ils se sont royalement planté, - mis a part évidement, leur résultat, qui sont, en eux-même intéressant.
[^] # Re: Houla, IA n'est pas algo !
Posté par Sylvain Sauvage . Évalué à 2.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.