Un tutoriel sur le cryptage RSA.

Objectif.

Le but de ce tutoriel est de manipuler les concepts liés à l'encryptage/décryptage par clés publique et privée, RSA. L'intérêt de la manipulation est de faire passer la non-symétrie du processus: autrement dit, tout le monde peut encrypter (par la clé publique), mais seule une personne pourra décrypter (possédant la clé privée)..

Introduction.

  1. Le principe de la cryptographie consiste à définir une transformation des symboles d'un langage (les lettres ou les mots par exemple) qui soit difficilement inversible, de telle sorte que retrouver le mot original à partir du mot codé devienne une opération difficile à effectuer.
  2. Il existe deux grandes familles d'algorithmes de cryptographie : les algorithmes symétriques (à clé secrète) et les algorithmes asymétriques (à clé publique). En cryptographie asymétrique (ou à clé publique), il existe une fonction dite à sens unique, pour transformer un message en message codé.
  3. Il faut que cette fonction soit simple à appliquer à un quelconque message, mais qu'il soit difficile de retrouver le message original à partir du message codé. La cryptographie à clé publique permet de coder un message secret et aussi d'authentifier l'émetteur d'un message, par le protocole symmétrique.
  4. Pour une explication plus aprofondie du procédé de cryptologie par l'algorithme RSA, se référer à l'article interstices.

Travail proposé.

  1. Manipuler l'interface: cryptage de données..

    Scénario: Deux élèves sont "Alice" et "Bob" et vont se succéder à tour de rôle sur devant l'interface.
    1. Alice est chargée de générer les clés publique et privée en suivant les différentes étapes:
      1. Génération de deux entiers premiers P et Q;
      2. Calcul de N = P x Q;
      3. Génération de E tel que E soit premier avec (P - 1) x (Q - 1);
      4. Calcul de D tel qu'il existe un relatif entier M, tel que E × D + M × (P - 1) x (Q - 1) = 1
      Ainsi, (N,E) est la clé publique et D est la clé privée.
      Bien entendu nous n'avons pas à faire le calcul nous même . . juste à utiliser l'interface qui l'a programmé.
      Alice divulgue la clé publique et garde précieusement la clé privée.
    2. Bob reçoit alors la clé publique d'Alice.
      Il écrit son message secret, puis le traduit en chiffres, donc un nombre X, pour qu'il puisse se faire encrypter à l'aide d'un calcul arythmétique, qui ne peut porter que sur des nombres et non une chaine de caratères.
      Il encrypte ensuite le résultat grâce à la clé publique de la manière suivante: il élève le message chiffré X à la puissance E, et prend le reste de la division du nombre qu'il a obtenu par N que lui a également fourni Alice.
      Il envoie alors le message encrypté Y à Alice.
    3. Alice reçoit le message encrypté Y.
      Elle le décrypte alors grâce à sa clé privée de la manière suivante: elle élève le nombre reçu de Bob à la puissance D, puis prend le reste de sa division par N.
      Elle obtient alors une suite de chiffres Z qu'elle traduit en lettres et aboutit au message secret de Bob: c'est à dire que Z = X !
    essayer ce scénario par binôme de deux, pour bien vous familiariser avec l'interface.
    Puis refaire le scénario sans l'interface, mais sur papier, en essayant de se faire deviner un nombre X.
  2. Utiliser les clés pour s'authentifier..

    Scénario: "Alice" va maintenant prouver à "Bob" qu'elle est Alice.
    1. Puis il encrypte avec la clé publique d'Alice un nombre secret (tiré au hasard) et l'envoie à Alice.
    2. Alice le décrypte avec sa clé privée (elle seule peut le faire, car elle seule à la clé privée) et annonce à Bob le nombre secret.
    3. Bob sait alors que ce ne peut être que Alice, la voilà authentifiée.
    Jouer ce scénario sans l'interface, mais sur papier.
    Proposer ensuite à Bob d'aller sur l'interface et de se calculer lui aussi des clés publiques et privées et rejouer le scénario de façon à ce que personne ne puisse jamais connaître le nombre secret.
  3. Traiter à la main, un exemple numérique:.

    Un professeur envoie ses notes au secrétariat de l'école par mail. La clef publique du professeur est (55,3); celle du secrétariat est (33,3).
    Vérifier, à l'aide des formules, que la clef privé du professeur (supposée connue de lui seul) est 27; et que celle du secrétariat est 7. Pour cela, reprise de la formule E x D + M x (P - 1) x (Q - 1) = 1, ce qui fait pour le professeur 3 x 27 - 2 x (5 - 1) x (11 - 1) = 1, et pour le secrétariat 3 x 7 - 1 x (3 - 1) x (11 - 1) = 1.
    • On voit bien que avec de si petit nombres un espion peut facilement essayer toutes les clés privées jusqu'à trouver la bonne !!!
    • Oui mais si clé est un mombre de plusieurs milliards de milliards (donc de 9 + 9 = une 20taine de chiffres) . . alors:
      • On pourra tout de même facilement faire les calculs de cryptage et de décrytage avec un ordinateur, en quelques dizaines d'opérations.
      • Mais le programme qui devra essayer lees milliards de milliards de clé privées avant de trouver la bonne . . même en faisant un milliard d'opérations par secondes en aura pour un milliard de secondes . c'est à dire . .
      • A vous: calculer combien cela fait en années . .
    Pour assurer la confidentialité de ses messages, le professeur chiffre les notes avec la clef RSA du secrétariat. Quel message chiffre correspond à la note 12 ? (convertit en nombre: 12594; regrouper en tranche de chiffres strictement plus petit que n=33: 12 5 9 4; élever chaque nombre à la puissance e=3 et en prendre le reste par la division par la division par n=33: 12 26 3 31. Mais si déjà converti en nombre: ce sera 12)
    Pour assurer l'authenticité des messages contenant les notes, le professeur signe ses messages pour le secrétariat aprés les avoir chiffrés. Le secrétariat reçoit le message 23. Quelle est la note correspondante ? (élever 23 à la puissance 7, prenez le reste de sa division avec 33)
  4. Utiliser les fonctions dans votre propre programme..

    • Utiliser les fonctions de la proglet pour programmer une interface pour Bob qui demande un message au clavier et renvoie le message encrypté. Vous mettrez les clés publiques dans le code à partir d'un jeu de clé déjà calculé. ce sont des clés publiques . . le code a pas besoin d'être caché.
    • Utiliser les fonctions de la proglet pour programmer une interface pour Alice qui demande le message crypté au clavier et renvoie le message encrypté. Vous mettrez les clés publiques et privées dans le code (qui devra donc rester secret, lui !).
    • Rejouer un des deux scénarios en utilisant les deux bouts de programme.
    • Comment faire pour le code d'Alice ne risque pas d'être piraté . . pour y lire la clé privée ?
  5. Coder vous même les fonctions de cryptage et de décryptage.

    Ecrire la formule du cryptage de Bob et celle du décyptage d'Alice.
    Reprendre alors les deux codes précédents en remplaçant les routines encrypt() et decrypt() par vos propres routines:
    • Pour passer du message à sa valeur en chiffres on utilise: BigInteger X = new BigInteger(message.getBytes());
    • Pour passer du message en chiffres à sa valeur en chaine de caractères on utilise: String message = new String(X.totByteArray());
    • Pour calculer Y = X ^ E modulo N on utilise: modPow [mettre un lien vers la doc]
    Vous avez donc tous les ingrédients.