Cours Stage - Le transcodage

Exercice - Le cryptage d'informations

L'énoncé

Le but de cet exercice est d'utiliser le changement de base pour crypter une série de chiffre. Supposons qu'un agent secret veuille envoyer une série de chiffres à un correspondant de telle manière qu'il soit le seul à comprendre le sens du message. Inventons un moyen de cryptage qui consiste à exprimer la série de chiffre dans une autre base. Ainsi, seuls ceux qui connaissent la base de cryptage peuvent décoder (ou coder) le message.

Le but de cet exercice est de voir différentes manières de crypter une suite de chiffres par changement de base, ainsi que les inconvénients des différentes manières.


Question 1

Prenons la liste de chiffres suivante : 15789

La première approche de codage serait de considérer la suite de chiffres comme un nombre à part entière. Ainsi, il suffit de l'exprimer dans une autre base pour le crypter.

Exprimer le nombre 15789 en base 5. 

On remarque que $15789=15625+125+25+2\times 5 +4\times 1=1\times 5^6+0\times 5^5+0\times 5^4+1\times 5^3+1\times 5^2+2\times 5^1+4\times 5^0$

Ainsi, en base 5, 15789 devient 1001124.

Pour passer de la base décimale à la basse 5, le but est de décomposer le nombre en somme de puissances de 5, en faisant attention à bien prendre à chaque fois la plus grande puissance de cinq.

 


On rappelle que :

$5^0=1$

$5^1=5$

$5^2=25$

$5^3=125$

$5^4=625$

$5^5=3125$

$5^6=15625$

$5^7=78125$

Question 2

Maintenant, pour se rendre compte de la faiblesse du cryptage, crypter 15789 en base 7.

Que remarque-t-on lorsque l'on écrit un nombre dans une base quelconque ? (Décimale, binaire, base 5 ou 7 dans le cas de cet exercice.)

En quoi cela pose-t-il problème dans le cas de la cryptographie ?

On a :

$15789=14406+1372+7+4=6\times 7^4+4\times 7^3+0\times 7^2+1\times 7^1+4\times 7^0$

Ainsi, en base 7, 15789 s'écrit 64014.

On remarque que peut importe la base choisie, les chiffres composant le nombre sont toujours strictement inférieurs au numéro de la base. Ainsi, en base 10 (décimale), les chiffres sont 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. En base 2 (binaire), les chiffres sont 0, 1. En base 5, les chiffres utilisés sont 0, 1, 2, 3, 4 et en base 7, il n'y a que 0, 1, 2, 3, 4, 5, 6.

Ainsi, si quelqu'un intercepte le message, en examinant les chiffres présents et les chiffres manquants, il est capable de déterminer dans quelle base le nombre est écrit. Il sera donc en mesure de le décoder.

De la même manière que pour la question précédente, on donne :

$7^0=1$

$7^1=7$

$7^2=49$

$7^3=343$

$7^4=2401$

$7^5=16807$

 

Question 3

Supposons maintenant que l'on crypte chiffre par chiffre, et non pas comme un nombre à part entière.

Prenons la suite de chiffres 7236489531567.

Crypter la liste en base 2. Quel problème pose cette nouvelle technique de cryptage ? Peut-on y remédier ?

Cryptons 7 2 3 6 4 8 9 5 3 1 5 6 7 en base 2 :

7 --> 111

2 --> 10

3 --> 11

6 --> 110

4 --> 10

8 --> 1000

9 --> 1001

5 --> 101

3 --> 11

1 --> 1

5 --> 101

6 --> 110

7 --> 111

Ainsi, en accolant tout, on obtient 11110111101010001001101111101110111

Cependant, on réalise que le décodage est impossible car le correspondant ne sait pas où sectionner.

Il serai donc possible de séparer chaque chiffre par des espaces ou en les écrivant chacun sur 4 bits, mais dans ce cas on retombe sur le problème du codage précédent : un inconnu pourrait décoder trop simplement le message.

Question 4

On peut maintenant suggérer que le message lui même contienne des informations nécessaires au décodage. Ainsi, en plus du message à transmettre, l'espion intercale des chiffres nécessaires au décodage et connus uniquement par son correspondant.

Supposons par exemple que le premier chiffre de la liste corresponde à la base de codage, et que le dernier corresponde au sectionnement de code :

Par exemple, si le correspondant reçoit 73255421463, le message à comprendre est le suivant : 

7 325542146 3

7 signifie que la base de codage est la base 7.

3 signifie que pour comprendre le message, il faut le sectionner tous les 3 chiffres : le message devient 325 542 146.

Ainsi, pour décrypter le message, il faut repasser en base décimale : en faisant les calculs, on trouve 166 275 83.

 

Décrypter le code suivant :

20110100101010100011100014

Le message devient donc en réalité :

2    0110 1001 0101 0100 0111 0001    4

Ainsi, en décodant chaque chiffre de la base binaire vers la base décimale, on obtient : 6 9 5 4 7 1

Question 5

Cependant, on remarque qu'en base binaire, la technique de codage est assez explicite : les seuls chiffres différents de 1 et 0 sont le premier et le dernier, on s'aperçoit vite que le premier correspond au numéro de base, et il ne reste plus qu'a comprendre que le dernier chiffre correspond au séquençage. La technique de codage n'est donc toujours pas suffisante.

On pourrait donc supposer que le chiffre de séquençage (le dernier chiffre) soit nécessairement inférieur au numéro de la base. Ainsi, une personne ne connaissant pas la technique ne pourra pas différencier les chiffres du code du chiffre de séquençage. Par exemple, un chiffre écrit en base 7 est nécessairement plus petit que 7. Si le chiffre de séquençage est inférieur à 7, il se mêlera parmi les autres et un inconnu ne pourra pas comprendre qu'il correspond au séquençage.

Quel est le problème de limiter le séquençage par le chiffre de la base de codage ?

Si on prend la base binaire, le séquençage est nécessairement 1.

Ainsi, les seuls chiffres accessibles avec un séquençage de 1 en base binaire sont 1 et 0. Il est donc impossible de coder un nombre supérieur à 2. Le codage ne peut pas fonctionner. Cela s'applique aussi pour toutes les autres bases.