Cryptage / Décryptage

Cryptage / Décryptage : Programme de BTS

Cryptage / Décryptage

Aujourd'hui, on va apprendre à crypter puis décrypter une lettre grâce aux mathématiques. Nous avons donc :

  • L'équation de cryptage : 11x + 20
  • La première équation que nous devrons résoudre : 11U + 26V = 1
  • La seconde équation que nous devrons résoudre : f(y)=a'x + b'
  • La lettre à crypter : i
  • La lettre "i" correspond à : 8
L'équation de cryptage (ici, 11x + 20) est toujours sous forme : f(x)=ax+b

De plus, il faut absolument que le "a" de cette équation (ici en l'occurence, 11) soit premier avec 26. (Puisque l'on crypte une lettre de l'alphabet qui est composé de 26 lettres.) Et là, j'en vois venir quelques-uns ! C'est quoi des chiffres "premiers entre eux ?!"

26 = 13 * 2 = 2 * 13 = 1 * 26
11 = 1 * 11

Le seul facteur que ces deux nombres ont en commun est le 1 (1 * 26 pour le premier nombre et 1 * 11 pour le deuxième). Prenons 12 à la place de 11 par exemple :

26 = 13 * 2 = 2 * 13 = 1 * 26
12 = 6 * 2 = 4 * 3 = 3 * 4 = 2 * 6 = 1 * 12

Ici, les deux nombres ont le facteur 1 ainsi que le facteur 2 en commun. (2 * 13 pour le premier et 2 * 6 pour le deuxième). Ces nombres ne sont donc pas premiers entre eux.

Quelques petites astuces : généralement quand deux nombres se terminent par 5, il ne sont pas premiers entre eux (puisque 5 est leur plus grand facteur commun). Idem pour les nombres pairs ! Puisqu'ils ont forcément 2 en plus grand facteur commun :)

Étape 1 : Le Cryptage

Nous avons donc, comme exercice, le devoir de crypter la lettre "i" en utilisant l'équation donnée par l'énoncer : 11x + 20. Rien de plus facile, il y a juste à remplacer "x" par le chiffre correspondant à notre lettre "i". Ici en l'occurence : 8


		11 * 8 + 20 = 108
108 modulo 26 = 4
Pourquoi faire 108 modulo 26 ? Comme vous le savez, il y a 26 lettres dans l'alphabet (ce qui explique le choix du 26). Nous n'allons pas nous amuser à compter jusqu'à atteindre la "108eme" lettre de l'alphabet (en recommençant à A quand on arrive à Z). Pour gagner du temps on fait modulo 26, qui nous sort d'ailleurs "4". On sait donc que "i" est égal à 4 lorsqu'il est crypté. Et, 4 est égal à E. (A=0 ; B=1 ; C=2 ; D=3 ; E=4 ; etc...).
Attention, il est possible (en fonction de l'équation de départ et de la lettre choisie) que le modulo retourne un chiffre décimal. Exemple : 10,615

Dans ce cas là, retirez le chiffre AVANT la virgule : 10,615 => 0,615

et multipliez le chiffre que vous obtenez par 26 (le nombre de lettre de l'alphabet) : 0,615 * 26 = 16

et hop ! Vous n'avez plus qu'à regarder quelle lettre correspond à 16.

Revenons à notre exercice, nous savons donc que "i" devient "e" après avoir été crypté par l'équation "11x + 20". Le cryptage est donc terminé pour notre lettre "i" ! Plutôt facile non ? Passons au décryptage maintenant, on va s'marrer un peu.


Étape 2.1 : Le Décryptage : 11U + 26V = 1

Nous allons donc devoir, dans un premier temps, résoudre cette équation étrange : 11U + 26V = 1

Avant de résoudre cette équation, il faut la comprendre. Pourquoi 11U ? Pourquoi 26V ?

11U vient de l'équation de cryptage : 11x + 20

Si l'équation avait été 9x + 20 au lieu de 11x + 20, on chercherait à résoudre non pas l'équation :

"11U + 26V = 1"

mais plutôt celle-ci :

"9U + 26V = 1"

Revenons à l'exercice, 11U est donc tiré de 11x (c'est le même 11 !)

Ensuite on a 26V ! Une idée ? :) Ben oui, il s'agit du nombre de lettres de l'alphabet. Si vous voulez décrypter une lettre faisant partit d'un alphabet de 27 lettres, ça sera 27V :D

Nous cherchons donc U et V pour compléter cette équation. Pour le trouver il faudra compter combien de fois il y a le fameux "11" ( vous savez ? 11U, 11x) dans le célèbre "26" (nombres de lettres de l'alphabet) et indiquer le chiffre restant. Je le fais donc sous vos yeux :


		26 = 2 * 11 + 4
	
Il y a donc 2 fois le chiffre 11 (on arrive donc à 22) et il manque 4 à 22 pour arriver jusque 26 ! Je reprends :

		26 = 2 * 11 + 4
11 = 2 * 4 + 3
Une fois la première ligne faite, on va reprendre le chiffre dont on cherche la récurrence dans le 26 (ici, 11) et on va le mettre à la place du 26. On va ensuite prendre le reste de la première ligne (4), et on va chercher sa récurrence dans le "11" qui vient juste de remplacer le 26 :)

On va reproduire ce phénomène jusqu'à ce qu'on arrive à 1.

		26 = 2 * 11 + 4
11 = 2 * 4 + 3
4 = 1 * 3 + 1
Et voilà ! Une fois que le reste est arrivé à "1" (comme ci-dessus) On passe à l'étape suivante, rien de compliqué on fait tout à l'envers !

Étape 2.2 : Le tout à l'envers

26 = 2 * 11 + 4
11 = 2 * 4 + 3
4 = 1 * 3 + 1

Regardez bien ces trois lignes : la première a pour reste "4". La seconde a pour reste "3" et la dernière a pour reste "1". On va reprendre ces chiffre dans l'ordre décroissant et vous allez voir certaines similitudes avec ces trois lignes d'opération. Je vais remettre ces trois lignes à côté des lignes de l'étape suivante pour que vous puissiez bien voir :

4 = 26 - 2 * 11
3 = 11 - 2 * 4
1 = 4 - 1 * 3
26 = 2 * 11 + 4 | 4 = 26 - 2 * 11
11 = 2 * 4 + 3 | 3 = 11 - 2 * 4
4 = 1 * 3 + 1 | 1 = 4 - 1 * 3
Pour expliquer la dernière ligne par exemple (et c'est valable pour les deux lignes d'avant) : au lieu de dire combien de 3 il y a dans 4 et combien il reste ; on va dire "il me reste 1 lorsque je cherche combien de fois il y a de 3 dans 4"

Étape 2.3 : Développez et allez vous coucher

On va donc s'intéresser à la dernière ligne : 1 = 4 - 1 * 3

Et puisque, d'après la dernière étape, 3 = 11 - 2 * 4, nous allons développer comme cela :


		1 = 4 - 1 * 3
1 = 4 - 1 * (11 - 2 * 4)

À partir d'ici, ça va commencer à se compliquer... Nous allons devoir simplifier et, je le rappelle, nous recherchons le U et le V de la formule : 11U + 26V = 1. Nous souhaitons donc garder le "11" intact. On ne veut pas le transformer !

On a donc un "-2 * 4" qui va se transformer en "3 * 4". Nous allons faire -1 * -2 pour passer le "2" en positif :


		1 = 4 - 1 * 11 - 2 * 4
1 = 4 - 1 * 11 + 2 * 4

Et nous allons grouper le petit "4" qui est tout seul au début avec les autres de la fin. Au lieu d'avoir 4 + 2 * 4 nous aurons 3 * 4


		1 = 4 - 1 * 11 - 2 * 4
1 = 4 - 1 * 11 + 2 * 4
1 = - 1 * 11 + 3 * 4

Arrivé ici, on a bien avancé... mais ce n'est pas terminé ! On va maintenant remplacer le 4 de la fin par "26 - 2 * 11"


		1 = - 1 * 11 + 3 * 4
1 = - 1 * 11 + 3 * (26 - 2 * 11)

Je rappelle encore une fois que nous cherchons 11U + 26V = 1

On va donc grouper ce qui peut être groupé tout en gardant notre 11 et notre 26 intacts.

3 * -2 = -6

1 = - 1 * 11 + 3 * (26 - 2 * 11)
1 = - 1 * 11 + 3 * 26 - 6 * 11

Et - 1 * 11 + -6 * 11 = -7 * 11 ! donc je reprends : 1 = - 1 * 11 + 3 * (26 - 2 * 11)
1 = - 1 * 11 + 3 * 26 - 6 * 11
1 = 3 * 26 - 7 * 11

Et ainsi, nous obtenons enfin notre : 11U + 26V = 1

Vous ne me croyez pas ? => 11 * -7 + 26 * 3

11 * -7 = -77
26 * 3 = 78

-77 + 78 = 1


Étape 2.4 : f(y)=a'x + b'

Maintenant qu'on sait que 11U + 26V = 1 => 11 * -7 + 26 * 3 = 1

On va pouvoir s'attaquer à la résolution de la dernière équation : f(y)=a'x + b'

Tout d'abord, comprenons la.

f(y)=a'x + b'

Nous avons 3 variables là-dedans :

- a'
- x
- b'

- Pour trouver a' il faut faire : U modulo 26 (on sait que U = -7) donc : -7 modulo 26 = 19

- x est le numéro de la lettre cryptée que vous voulez décrypter : ici on veut décrypter "e", donc "4"

- Pour trouver b' : vous devez faire "(-a' * b) modulo 26" : "-a'" correspond à "a'" trouvé précédemment avec un "-" devant xD et b correspond au "b" de "ax + b" de votre équation de cryptage (tout au début !) : Notre équation était : 11x + 20 : donc b = 20 donc :

-19 * 20 = -380
-380 modulo 26 = 10

Nous obtenons donc : f(y)=19x + 10

Grâce à cette équation, nous allons voir si en décryptant le chiffre 4 (et donc la lettre E) nous obtenons bien 8 (donc la lettre i). Retenez votre souffle, si là, j'ai faux, ça veut dire que vous venez de lire 220 lignes pour rien.

19 * 4 + 10 = 86

Ici, même principe ! Quand vous obtenez un nombre trop grand pour l'alphabet, go faire un modulo 26 !

86 modulo 26 = 8

E est bien égal à I. j'ai transpiré avant de faire le calcul... Mais j'ai fini, le tuto à l'air de fonctionner... Amen !