Présentation
Comme tout informaticien sérieux, je suis allé voir ce bon film sur Alan Turing nommé : Imitation Game.
Si ce film vous a donné envie de comprendre les rudiments de la cryptographie au travers d’un exemple de chiffrement RSA en Java, cet article est pour vous !
Après une courte présentation d’Alan Turing, je vous présenterai tout d’abord un résumé du chiffrement RSA, avec un exemple basique de chiffrement / déchiffrement, puis une “attaque” tout aussi basique pour décrypter un message sans avoir la clé de déchiffrement.
Pendant la Seconde Guerre mondiale, les Allemands utilisaient une machine nommée Enigma qui permettait aux militaires de s’envoyer des messages codés, sur les positions des forces armées et sur les prochaines attaques. Il suffisait d’écrire un message sur cette sorte de grosse machine à écrire qu’est Enigma pour qu’il ressorte chiffré.
Le message chiffré était émis en morse par une radio, et un seul récepteur avec la même machine peut faire la manoeuvre inverse pour déchiffrer ce message. Chiffré, le message donne plus que 150 milliards de milliards de combinaisons : ça fait beaucoup de zéro !
Indécryptable? C’était sans compter le cerveau de génie de l’ingénieur Alan Turing dont Churchill aurait dit qu’il “a apporté la contribution individuelle la plus importante à la victoire des Alliés”. On peut dire de plus qu’Alan Turing est le “père” de l’informatique moderne.
Le nom Imitation Game vient du test de Turing :
Une machine converse avec des humains par l’intermédiaire d’un échange écrit, appelé de nos jours “chat”.
Si la machine imite suffisamment bien la conversation humaine, et que l’humain n’arrive pas à distinguer si c’est une machine ou un humain, alors la machine vient de réussir le test.
Une machine qui réussit le test avec beaucoup d’humains, serait dotée d’une sorte de “conscience” (ce qui est assez souvent contesté).
Exemple d’un chiffrement RSA en Java
L’algorithme est plutôt simple, il est basé sur les nombres premiers.
Je suis Paul, je suis dans un cours d’informatique, il y a un chat commun entre les élèves et le professeur. C’est le seul moyen de communication à notre disposition.
J’ai donc donné le code pour chiffrer des messages à certaines personnes, et le code pour déchiffrer des message à d’autres.
Je vais envoyer le message suivant à ceux qui ont le code de déchiffrement : “LE PROF EST BETE” sans que, bien sûr, le professeur ne puisse le lire.
Création des couples clé public / clé privée
// Je prends deux nombres premiers p et q au hasard 11 et 13
BigInteger nbPremier01 = BigInteger.valueOf(11);
BigInteger nbPremier02 = BigInteger.valueOf(13);
// Je calcule leur produit = 143
BigInteger produit = nbPremier01.multiply(nbPremier02);
// Je calcule f = (11-1)*(13-1) = 120
BigInteger f = nbPremier01.subtract(BigInteger.ONE).multiply(nbPremier02.subtract(BigInteger.ONE));
// Je choisis e, premier avec f : 7
BigInteger e = BigInteger.valueOf(7);
// Il faut de d*e modulo c soit égale à 1 => d = 103
BigInteger d = e.modInverse(f);
Nous avons donc ici deux couples :
- La clé de chiffrement, dit clé publique (e,n) : (7,143)
- La clé de déchiffrement, dit clé privée (d,n) : (103,143)
Transformation du message en ASCII
String message = "LE PROF EST BETE";
int length = message.length();
int messageEnAscii[] = new int[length];
// Transformation du message en tableau de caractères ASCII
char charMessage[] = message.toCharArray();
for (int i = 0; i < length; i++) {
messageEnAscii[i] = (int) charMessage[i];
// Ici la lettre en ASCII ne doit pas dépasser (length de 143) - 1 = 2 chiffres
}
Nous avons donc ici transformé chaque caractère par son numéro ASCII
76 69 32 80 82 79 70 32 69 83 84 32 66 69 84 69
Chiffrement du message grâce à la clé publique
// Chiffrement du message grâce au couple publique (7,143)
BigInteger e = BigInteger.valueOf(7);
BigInteger n = BigInteger.valueOf(143);
int messageCode[] = new int[length];
for (int i = 0; i < length; i++) {
BigInteger nb = BigInteger.valueOf(messageEnAscii[i]);
// ex: 76 puissances 7 modulo 143 = 54
messageCode[i] = nb.modPow(e, n).intValue();
}
Le message chiffré est le suivant :
54 108 98 141 69 40 60 98 108 8 72 98 66 108 72 108
Déchiffrement du message grâce a la clé privée
// Déchiffrement du message
BigInteger d = BigInteger.valueOf(103);
for (int i = 0; i < length; i++) {
BigInteger nb = BigInteger.valueOf(messageCode[i]);
// ex: 54 puissances 103 modulo 143 = 76
int decodedAscii = nb.modPow(d, n).intValue();
System.out.print((char) decodedAscii);
}
Résultat: LE PROF EST BETE
Après quelques ricanements dans la classe le prof se doute de quelque chose, récupère le message sur le chat puis insiste lourdement auprès d’un élève afin d’avoir la clé publique. Cet élève lui donne donc le couple (7,143)
Afin de pouvoir déchiffrer le message, le prof doit retrouver p et q, soit les deux nombres premiers du début : 11 et 13.
Le professeur n’ayant pas oublié ses cours de 4ième décompose immédiatement 143 en 11 * 13.
Une fois ces deux nombres trouvés, le professeur peut retourner à la première étape afin de trouver « d », puis de déchiffrer le message posté sur le chat.
Si notre Paul avait pris le soin de choisir un « n » plus grand, ça lui aurait évité d’avoir une heure de colle donnée par ce prof, qui finalement n’était pas si bête !
Dans le cas d’un « n » grand, la décomposition peut se faire de cette façon :
// La valeur que nous voulons factoriser
BigInteger n = new BigInteger("1487932939581322413763429");
LinkedList factors = new LinkedList();
BigInteger two = BigInteger.valueOf(2);
// Si n est paire
while (n.mod(two).equals(BigInteger.ZERO)) {
factors.add(two);
n = n.divide(two);
}
BigInteger currentValue = BigInteger.valueOf(3);
// On s'arrête a la racine carrée de n
while (currentValue.pow(2).compareTo(n) <= 0) {
// Si un facteur a été trouvé
if (n.mod(currentValue).equals(BigInteger.ZERO)) {
// La valeur courante est la facteur de n
factors.add(currentValue);
// On divise afin de diminuer les itérations
n = n.divide(currentValue);
} else {
// Afin d'avoir toujours un nombre impair
currentValue = currentValue.add(two);
}
}
factors.add(n);
// On trouve 21646157677 et 68738894069977
Sur un PC (pas très puissant), voici les temps pour factoriser les nombres suivants :
- L’opération de base
143 = 11 * 13 => 0s - Le produit des plus grands nombres premiers connus entre 1750 et entre 1867
6879317362553803649039 = 2147483647 * 3203431780337 => 3 min - Un grand nombre :
1487932939581322413763429 = 21646157677 * 68738894069977 => 50min - Le produit des plus grands nombres premiers connus entre 1867 et entre 1876
545035674241415089467649672839553856435004747689999 =
3203431780337 * 170141183460469231731687303715884105727 => Très long
Vous l’aurez compris l’intérêt est d’avoir un n très grand afin que sa décomposition en produits de facteurs premiers soit beaucoup plus difficile.
Aujourd’hui un n de :
- 256 bits (nombres de 78 chiffres) peut être décomposé, avec un ordinateur performant et un algorithme un peu plus évolué en quelques minutes.
- 2048 bits (617 chiffres) est une sécurité optimale pour au moins encore quelques années.
