|
|
|||
| Les systèmes à clé publique :
«Ars ipsi secreta magistro» Les cryptages reposaient d'abord sur des clés symétriques, mais un problème et un risque se sont posés lorsqu'il a fallu transmettre la clé au destinataire, puisque sa communication ne pouvait se faire que de façon claire. C'est l'inconvénient que ne présentent pas les clés publiques : Une clé sert à crypter, une autre à décrypter, et il n'y a pas de communication de clés secrètes entre les interlocuteurs.
Le premier système à clé publique : l'algorithme Diffie-Hellman : Le premier système à clé publique est celui de Diffie-Hellman, inventé en 1975. C'était la première méthode pratique pour établir une clé secrète entre deux individus sans crainte, dans un lieu de discussion non sécurisé. Sa sécurité repose sur la difficulté de calculer des logarithmes discrets par rapport à la facilité de calculer les exponentielles. Principe de l'algorithme :Soient 2 personnes A et B désirant communiquer sans utiliser une clef secrète. Ils se mettent d'accord sur un canal qui n'est pas forcément sécurisé, sur deux grands entiers premiers entre eux, n et g, tels que n > g > 1. Pour que l'échange de clefs soit sécurisé, il faut que n ait une taille de l'ordre de 512 ou 1024 bits. A choisit un grand nombre entier aléatoire x. A calcule X=gx mod n et l'envoie à B. B choisit un grand nombre entier aléatoire y. B calcule Y=gy mod n et l'envoie à A. Ensuite, chacun de leur coté :
On constate alors que k = k' = gxy mod n et donc que A et B sont parvenus à établir une clef secrète commune qui sera ensuite utilisée par un algorithme symétrique (comme le DES part exemple). La clef publique correspond aux valeurs X et Y échangées par les deux protagonistes. La clef privée correspond aux valeurs x et y conservées par les deux protagonistes. Information : Ci dessus comme dans le reste de cette page, "mod" représente l'opérateur arithmétique modulo. Ainsi (x mod y)=z si et seulement si x congrue à z modulo y. Il faut rajoutter que z est toujours choisi le plus petit possible.
Analyse à travers un exemple : le RSA Le RSA, nom venant des initiales de ses trois inventeurs, repose sur un principe très simple dont la sécurité n'a jamais été démontré, c'est une simple constatation algorithmique: il est beaucoup plus aisé de calculer un produit de nombres que de calculer la décomposition en facteurs premiers. Cette assertion prend toute sa force lorsqu'on parle de grands nombres comportant plusieurs centaines de chiffres...
Voilà la technique rapidement expliquée, d'après une traduction de l'anglais d'un des membres du groupe :
Comment fonctionne le RSA ? ============= Nous commençons par choisir deux grands nombres premiers p et q. Calculons n = p*q. Nous cherchons ensuite e, un nombre entier aléatoire qui est premier avec (p-1)*(q-1). Le couple (n, e) consitue la clé publique. En utilisant l'algorithme d'Euclide, on calcule d, tel que e*d = 1 mod ((p-1)*(q-1)). Le couple (n, d) consitue la clé privée. Aussi bien le texte décrypté m que le texte crypté c doivent être des entiers positifs. Puis, avant de crypter le message m, nous nous assurons que 0 <= m < n. Si m est plus grand que le modulo n, le résultat c ne sera pas lié à m de façon unique. Nous savons grâce au théorème d'Euler que pour tous les entiers m, m^(e*d) = m (mod n). Ainsi, avec 0 <= m < n et (m^(e*d) mod n) = m. Pour crypter le message m, nous réalisons l'algorithme suivant : Ek(m) = (m^e mod n) = c avec Ek( ) pour l'algorithme de cryptage. Pour décrypter c avec la clé privée d, nous réalisons l'algorithme suivant : Dk(c) = (c^d mod n) = (m^(e*d) mod n) = (m^1 mod n) = m avec Dk( ) pour l'algorithme de décryptage. La paire (e, n) constitue la clé publique du cryptosystème RSA. Tout le monde peut utiliser cette paire (e, n) pour crypter un message. Par exemple, Alice peut diffuser sa clé publique(e, n) sur Internet. Quand Bob voudra envoyer un message secret à Alice, il cherche la clé publique d'Alice (e, n) sur Internet et crypte son message avec la clé publique d'Alice : c = (m*e mod n). p, q et d constituent la clé privée d'Alice. Seule Alice connait p, q, et d. Un tiers, Carole, ne peut pas comprendre ce que Bob a écrit à Alice car Carole n'a pas la clé privée. Quand Alice reçoit le message de Bob, elle le décrypte en utilisant sa clé privée d, n en effectuant (cd mod n) = m. Si l'on ne connait pas d, on ne peut pas décrypter le message crypté c et connaitre le message m. Pour connaitre d, on doit connaitre (p-1)*(q-1) pour trouver d à partir de l'équation : e*d = (1 mod (p-1)*(q-1)). Or, pour avoir (p-1)*(q-1), on doit en premier lieu être capable de factoriser le grand nombre n en p et q, tous deux premiers. A partir du moment où tous les nombres sont de très grands nombres (100 chiffres au moins), nous pouvons dire qu'il est impossible en pratique qu'un tiers obtienne d, et puisse donc décrypter le message crypté.
Exemple :
Les variables étant données, p = 29, q = 31, e = 13, m = 123;
==>Nous calculons : n = p * q = 899 (p-1)*(q-1) = 840 d = 517 car e*d = 13*517 = 8*(p-1)*(q-1) + 1 Pour crypter, c = (123^13 mod 899) = 402 Et pour décrypter, m = (402^517 mod 899) = 123
Sécurité :
Le cryptage RSA se fait bien évidemment par bloc de caractère dans le cas d'un message, empêchant ainsi toute attaque par étude de la fréquence d'apparition des lettres. Le RSA effectue aussi une authentification de l'expéditeur, ce que ne permet pas la cryptographie à clé privée : En encodant un message annexe avec sa clé secrète, on l'authentifie. Le destinataire l'encode avec la clé publique de l'expéditeur pour pouvoir lire la signature correctement. En effet, le RSA fonctionne que l'on encode avec e et décode avec d, ou inversement : M^ed = M [n] Une fois l'entier e ou d choisi pour constituer la clé publique, il faut s'y tenir pour des raisons de sécurité évidentes.
L'exponentiation rapide
Nous avons réalisé deux programmes sur Ti-83 Plus, permettant de trouver une forme simplifiée de A^B [N]. Si même notre calculatrice (6Mhz) de lycée est capable de réaliser ce calcul pour un nombre A à 6 chiffres en 3 secondes, vous pouvez vous douter que le codage et le décodage d'un court message (quelques caractères) peut-être relativement rapide grâce aux ordinateurs les plus récents (plus de 3 Ghz pour le grand public). En outre, le cryptage RSA sur un ordinateur se faisant uniquement pour la clé privée générée aléatoirement, il n'est pas vraiment comparable à celui qu'aurait réalisé la calculatrice en cryptant tout en RSA. Nous n'avons donc pas juger important d'évaluer le temps de calcul nécessaire au cryptage d'un petit document (2 Ko par exemple) : un ordinateur grand-public actuel a une puissance suffisante pour que ce temps reste de l'ordre de la dizaine de secondes au maximum pour un petit document et pour un cryptage RSA 4096 bits.
Voici une méthode extraite de Pour la Science de Janvier 2000, revue et corrigée par nos soins, car elle présentait quelques oublis dans leur magazine :
Le programme est accessible aux possesseurs de Ti-83 : algo (le plus rapide).
Et voici une méthode, dont l'idée de fonctionnement en base 2 nous a été donnée par M. Meunier :
Le programme est accessible aux possesseurs de Ti-83 : algo (le premier que nous ayons fait). Pour transférer les programmes sur calculatrice Ti, il faut utiliser un logiciel comme celui disponible à cette adresse : NB : L'idée d'un programme de cryptage/décryptage RSA sur Ti-83 a cependant été abandonnée : En effet, la calculatrice ne peut retenir en mémoire que des nombres composés de 13 chiffres au maximum (10^12). C'est insuffisant pour un cryptage RSA. L'élévation au carré nous aurait obligés à utiliser des blocs de 3 caractères, chaque caractère étant représenté par 2 chiffres, et ne voulant pas dépasser 13 chiffres, nous nous serions limiter à des blocs de 6 chiffres. Remarque : Les deux programmes reposent sur le même principe (calculer le reste en réduisant l'exposant petit à petit), seul le mode d'action diffère légèrement : l'un convertit l'exposant en base 2 pour calculer facilement les élévations à la puissance modulo n, alors que l'autre réduit l'exposant en le divisant par 2 s'il est pair, ou en lui soustrayant 1 avant de le diviser par 2 s'il est impair. Ceci permet de réduire rapidement l'exposant en scindant le résultat en deux nombres que l'on multipliera à la fin. La différence de vitesse notée lors de nos tests peut être expliquée par le fait que l'algorithme le plus rapide ne convertit pas l'exposant en base 2, ceci permet certainement un gain de temps quasiment négligeable à l'échelle de nos calculs, mais qui peut représenter un gain certain à l'échelle de calculs utilisant de très grands nombres (plus de 100 chiffres).
Les défauts du RSA
Le RSA présente quelques défauts. Premièrement, sa sécurité n'a jamais été démontrée mathématiquement. L'idée que le noyau mathématique du RSA est inviolable est une conclusion expérimentale tirée de l'échec des tentatives connues de décryptage sans la clef secrète depuis sa création en 1977. Mais il est possible que l'on puisse casser le RSA à l'aide d'algorithmes spécifiques de factorisation, voire d'ordinateurs quantiques, et il n'est même pas sûr que casser le RSA revienne à factoriser n = pq, peut-être est-il possible de déchiffrer un message, c'est-à-dire d'obtenir d, sans passer par p et q. Deuxièmement, si une organisation avait réussi à casser des clés de plus de 512 bits RSA, elle le garderait certainement pour son pays et l'information ne circulerait pas forcément dans le monde. Donc la confiance qu'on lui accorde ne doit pas être une confiance aveugle. Nombreux sont les systèmes de cryptage réputés infaillibles qui ont été cassés par la suite. Troisièmement, les conseils pour ne laisser transparaître aucune faille de sécurité dans le RSA se font de plus en plus nombreux avec les années (principalement pour le choix de p, q et e).
N'oublions pas que le 22 Août 1999, un clé RSA de 512 bits a été cassée : un entier n de 155 chiffres décimaux a été factorisé. Citons enfin le cas du "RSA for paranoids" (paranoïaques) proposé par A. Shamir (un des inventeurs du RSA) en 1995, qui était censé rassurer les utilisateurs du RSA classique qui craignaient des failles de sécurité. "RSA for paranoids" permettait d'allonger la clé sans trop augmenter les coûts de codage. Résultat : 3 ans plus tard, ce prétendu renforcement du RSA est cassé. Ainsi, un des inventeurs du RSA, croyant renforcer son système pour rassurer les paranoïaques, a, au contraire, augmenté leurs craintes.
|
|||
|
