Preuve de sécurité

Preuve de sécurité

L'objectif de la cryptographie est de construire des systèmes de chiffrement sûrs. Cela étant, il convient de définir rigoureusement ce critère de sûreté.

Essentiellement, on dispose de deux notions :

La première notion est introduite par Claude Shannon, dans son célèbre article Communication theory of secrecy systems paru en 1949. Actuellement, seul le système du masque jetable est prouvé inconditionnellement sûr. Shannon lui-même l'a démontré dans l'article cité ci-dessus. Cette notion formalise l'idée que, si l'on ne dispose que du seul message chiffré, il est impossible de déduire la moindre information sur le message en clair.

La seconde notion est moins forte, elle suppose que si l'on ne dispose que d'une capacité de calcul limité, on ne pourra pas déduire le message.

Distinctions entre cryptographie symétrique et asymétrique

Il faut maintenant distinguer la cryptographie symétrique de la cryptographie asymétrique.

Dans le domaine symétrique, seule la sécurité sémantique peut être prouvée, ce qui est un problème très important du domaine. En effet, hormis cette sécurité, la seule chose que l'on arrive à prouver sur des systèmes symétriques est leur résistance à des techniques de cryptanalyse connues, comme par exemple la cryptanalyse différentielle ou bien linéaire. On ne sait pas prouver la résistance à des attaques encore inconnues.

Dans le domaine asymétrique, le problème se pose différemment et c'est d'ailleurs dans ce dernier que l'on retrouve le plus la notion de preuve de sécurité. Les systèmes asymétriques reposent sur des problèmes calculatoires de la théorie des nombres ou de l'algèbre discrète. Par exemple, un algorithme comme ElGamal repose sur le problème du logarithme discret. Le schéma général d'une preuve de sécurité est alors de prouver que casser le système se réduit, par un nombre d'opérations polynômiales (en certaines quantités dépendant du système), à un autre problème supposé difficile. On se retrouve donc, moyennant un surcoût considéré comme négligeable, à résoudre un problème (supposé) difficile.

La théorie de la complexité

Mais que doit-on appeler difficile ? Une réponse à cette question est apportée par la théorie de la complexité à laquelle on emprunte entre autres le concept de réduction entre problèmes. Cette théorie cherche à classifier les problèmes en fonction du temps de calcul nécessaire pour les résoudre, et définit des classes de « difficulté ». En l'occurrence, la classe qui nous intéresse est celle dite non déterministe polynômiale (NP). Ce sont les problèmes dont une solution, donnée, est « facile » à vérifier (se vérifie en temps polynômial), mais risque en revanche d'être difficile (potentiellement en temps non polynômial) à trouver.

L'appartenance d'un problème à la classe NP ne signifie pas que celui-ci n'est pas résoluble en temps polynomial. En effet, tous les problèmes de P sont dans NP, et le fait de savoir si au contraire il existe des problèmes de NP qui ne sont pas dans P est une des grandes questions ouvertes en mathématiques.

En pratique

Les problèmes utilisés par la cryptographie sont tous dans NP : il est « facile » de coder un message, ou de décoder un message quand on en possède la clé. En revanche, en l'état actuel des connaissances, toutes les méthodes existantes pour casser ces codes sont exponentielles en la taille de la clé. C'est la disproportion pratique entre le temps de codage ou décodage avec clé d'une part, et de cassage d'autre part, qui rend les méthodes utiles.

Il n'y a pour l'instant pas d'objection théorique à l'existence d'algorithmes polynomiaux de cassage des codes utilisés actuellement, mais juste le constat pratique que ces problèmes résistent aux efforts soutenus de la communauté depuis suffisamment longtemps. Notons par ailleurs que les ordinateurs quantiques, si on arrive à en construire de « taille » (nombre de qbits) suffisante, permettraient de casser des systèmes comme RSA.

Enfin, il est important de préciser que les preuves de sécurité sont à prendre avec précaution. Par exemple, un système que l'on doit à Ajtai et Dwork, accompagné d'une preuve de sécurité théorique supposant un certain problème difficile, s'est retrouvé cassé en pratique par Phong Nguyen et Jacques Stern.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Preuve de sécurité de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Preuve de securite — Preuve de sécurité L objectif de la cryptographie est de construire des systèmes de chiffrement sûrs. Cela étant, il convient de définir rigoureusement ce critère de sûreté. Essentiellement, on dispose de deux notions : la sécurité… …   Wikipédia en Français

  • Securite des donnees — Sécurité des données En sécurité des systèmes d information, la sécurité des données est la branche qui s intéresse principalement aux données, en complément des aspects de traitement de l information. Sommaire 1 Rappel sur les données… …   Wikipédia en Français

  • Sécurité des données informatiques — Sécurité des données En sécurité des systèmes d information, la sécurité des données est la branche qui s intéresse principalement aux données, en complément des aspects de traitement de l information. Sommaire 1 Rappel sur les données… …   Wikipédia en Français

  • Securite par l'obscurite — Sécurité par l obscurité Le principe de la sécurité par l obscurité repose sur la non divulgation d information relative à la structure, au fonctionnement et à l implémentation de l objet ou du procédé considéré, pour en assurer la sécurité. Cela …   Wikipédia en Français

  • Securite inconditionnelle — Sécurité inconditionnelle En cryptologie, la sécurité inconditionnelle est un critère de sécurité important dans le cadre des algorithmes de chiffrement. Cette sécurité est intimement liée à la théorie de l information et la notion d entropie,… …   Wikipédia en Français

  • Securite semantique — Sécurité sémantique En cryptologie, la sécurité sémantique est un critère de sécurité important dans le cadre des algorithmes de chiffrement. Elle fut introduite en 1982 par Shafi Goldwasser et Silvio Micali dans une optique de cryptographie… …   Wikipédia en Français

  • Sécurité des données — En sécurité des systèmes d information, la sécurité des données est la branche qui s intéresse principalement aux données, en complément des aspects de traitement de l information. Sommaire 1 Rappel sur les données informatiques 2 Bref historique …   Wikipédia en Français

  • Sécurité matérielle des cartes à puce — La sécurité matérielle des cartes à puce et des autres microcontrôleurs est l un des éléments clefs de la sécurité des informations sensibles qu ils manipulent. La littérature scientifique a produit un grand nombre de publications visant à… …   Wikipédia en Français

  • Sécurité par l'obscurité — Le principe de la sécurité par l obscurité (de l anglais : « security through/by obscurity ») repose sur la non divulgation d information relative à la structure, au fonctionnement et à l implémentation de l objet ou du procédé… …   Wikipédia en Français

  • Sécurité inconditionnelle — En cryptologie, la sécurité inconditionnelle est un critère de sécurité important dans le cadre des algorithmes de chiffrement. Cette sécurité est intimement liée à la théorie de l information et la notion d entropie, elle a été définie dans le… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”