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é sémantique, ou encore inconditionnelle
• la sécurité calculatoire

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.

Ce document provient de « Preuve de s%C3%A9curit%C3%A9 ».