La base des algorithmes de cryptographie

[Cet article est une partie de la future version du Petit Livre du Hacker]

Il y a plusieurs méthodes pour crypter des messages et c’est cette diversité qui en fait la richesse et qui peut être une source d’ennuis, car il faut choisir le bon algorithme selon la tâche à accomplir. Il faut tenir compte de la vitesse d’exécution, des attaques que nous désirons contrer et de la complexité de chaque solution. Par exemple, si le but est de décoder un visionnement vidéo en temps réel et que le décryptage prend une journée pour une vidéo d’une heure, c’est loin d’être du temps réel. C’est pourquoi il y a toujours des compromis à faire.

Chaque algorithme s’appelle un algorithme de cryptographie et il détaille la méthode pour crypter et décrypter ainsi que la gestion des clés (symétrique ou non, quelle grandeur, etc.). Tous les algorithmes ont un point en commun et c’est qu’ils utilisent l’opération XOR (un « ou » exclusif). Je vais vous expliquer ce qu’est cette opération, mais tout d’abord, en tant qu’humain, l’opération la plus simple à utiliser pourrait être l’addition ainsi que sa contrepartie, la soustraction. Alors si je vous donne comme message « 12345 » et que je vous dis de le crypter avec le texte « 69184 », vous devrez additionner non pas les deux nombres ensemble, mais uniquement les chiffres un à un et s’ils dépassent 10, en soustraire 10. Donc 1+6=7; 2+9=11=1; 3+1=4; 4+8=12=2; 5+4=9 ce qui donne « 71429 ». Puis pour décrypter vous faite l’inverse : 7-6=1;1-9=-8=2; 4-1=3; 2-8=-6=4; 9-4=5 et cela revient au « 12345 » du début.

Maintenant, pour un ordinateur qui utilise des bits (valeur 0 ou 1), une opération très simple est le XOR. Un simple OR (un « ou ») est de dire que si l’un des deux bits à comparer est un 1, alors la réponse est 1 (voir le tableau en bas de l’article). Le problème est que trois des quatre possibilités donnent 1 et une seule des quatre donne 0. C’est un problème étant donné que si nous avons comme résultat un 1 et comme texte de cryptage un 1, le message initial pourrait être 0 ou 1, mais nous voulons une seule valeur. Le XOR (« ou » exclusif) stipule que si les deux bits comparés sont différents, alors la réponse est 1; sinon elle est 0 (voir le tableau en bas de l’article). Avec cette opération, il y a deux possibilités sur quatre pour chaque résultat et cela nous donne une seule réponse possible. Il est donc possible de cacher un message en faisant un XOR entre le message à crypter et le texte de cryptage.

Voici un exemple. Prenons le message « 11010 » et cryptons-le (faisons un XOR) avec le texte « 01111 » : 1 XOR 0 = 1; 1 XOR 1 = 0; 0 XOR 1 = 1; 1 XOR 1 = 0; 0 XOR 1 = 1. Le tout « 10101 ». Comme dit précédemment, cette opération est très rapide pour une machine, mais il y a aussi une autre propriété importante et c’est que contrairement à l’addition dont son inverse est la soustraction; pour le XOR, son inverse est encore XOR. Donc en prenant le message crypté et en faisant un XOR avec, nous obtenons le message initial : « 10101 » XOR « 01111 » = « 11010 ».

or_xor