ACTIVITE : cryptographie BTS et TS spé maths 2016
Activité
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Chacune des 26 lettres de l'alphabet est associée à un entier compris entre 0 et 25
CODAGE:
1 . Par exemple pour A on considère x = 0 et pour Z on considère x = 25.
2. On commence, pour coder une lettre de l'alphabet, par considérer l'entier x compris entre 0 et 25
qui lui correspond.
3. Ensuite on choisit une clé constituée de deux entiers naturels p et q , en général premiers entre eux,
compris entre 0 et 25.
Nous prendrons ici par défaut dans l'activité p = 9 et q = 2
4. On cherche alors le reste x ' de la division euclidienne de px + q par 26
x ' est donc caractérisé par p x + q ≡ x ' [ 26 ] avec 0 ≤ x ' ≤ 25
c-à-d x ' ≡ p x + q [ 26 ] avec 0 ≤ x ' ≤ 25
Ensuite on regarde dans le tableau quelle lettre correspond à cet entier x '.
Par exemple: Soit V à coder.
Cela correspond à x = 21 dans le tableau.
p x + q = 9 × 21 + 2 = 191
Le reste de la division de 191 par 26 est 9 car 191 = 7 × 26 + 9 avec 0 ≤ 9 ≤ 25
x ' = 9
Cela correspond dans les tableau à la lettre J
Donc: V est codée en J
ASPECT RECIPROQUE : Décodage:
On dispose d'une lettre qu'il faut décoder.
Il y a pour cette lettre un entier x ' compris entre 0 et 25 que l'on peut voir avec le tableau.
Notre objectif est d'abord d'extraire x de la congruence x ' ≡ p x + q [ 26 ] avec 0 ≤ x ' ≤ 25
L'idée est de multiplier les deux membres de cette congruence par un entier relatif u
tel que up soit égale à 1 à un multiple de 26 près.
Dans cette nouvelle congruence on pourra alors remplacer upx par x car tous
les multiples de 26 sont intégrés au modulo 26.
( En pratique on cherche deux entiers relatifs u et v tels que u p + v q = 1 )
Nous avons convenu de prendre p = 9 et q = 2.
On a : x ' ≡ 9 x + 2 [ 26 ] avec 0 ≤ x ' ≤ 25 et avec 0 ≤ x ≤ 25
Comme 3 × 9 = 27 = 1 + 26 on prend u = 3
Ainsi : 3 x ' ≡ 3 × 9 x + 3 × 2 [ 26 ]
c-à-d 3 x ' ≡ 27 x + 6 [ 26 ] ( Dans 27 x il y a 26x à intégrer au modulo 26 )
c-à-d 3 x ' − 6 ≡ x [ 26 ]
c-à-d x ≡ 3 x ' − 6 + 26 [ 26 ] avec 0 ≤ x ≤ 25
( on peut ajouter 26 autant de fois que l'on veut en raison du modulo 26 )
On obtient: x ≡ 3 x ' + 20 [ 26 ] avec 0 ≤ x ≤ 25 à imposer
Par exemple: Décodons R
La lettre correspond à x ' = 17
3 x ' + 20 = 3 × 17 + 20 = 71
71 = 2 × 26 + 19 avec 0 ≤ 19 ≤ 25
Donc x ≡ 19 [ 26 ] avec 0 ≤ 19 ≤ 25
On considère x = 19
La lettre correspondante est T
Donc la lettre codée R était en fait la lettre T
REMARQUE: Il apparaît que pour la clé p = 9 et q = 2,
et x et x ' des entiers naturels compris entre 0 et 25 , on a :
x ' ≡ 9 x + 2 [ 26 ] ⇔ x ≡ 3 x ' + 20 [ 26 ]
La congruence de gauche permet le codage. Celle de droite permet le décodage.
---------------------------------------------------------------------------------------------------------------