Introduction
Prérequis :
Congruences
Résolution d'équations diophantiennes
Durée : 90 minutes
Niveau : difficile
Objectifs :
Il s'agit d'illustrer l'emploi de quelques notions et résultats d'arithmétique en cryptographie, science qui s'occupe de chiffrer et déchiffrer des messages à l'aide d'une clé.
Nous allons travailler sur une méthode à clés cachées, c'est-à-dire que les clés ne sont connues que des personnes qui codent et décodent le message.
On assimile les lettres A, B, C, ..., Z aux nombres 0, 1, 2, ..., 25 et on code ces nombres entiers
par
,
est appelée la fonction de codage, en définissant
comme le reste de la division euclidienne de
par
, où
est un entier donné.
est la clé du codage.
Prenons par exemple
.
1) Coder le mot SECRET.
On affecte à chaque lettre de l'alphabet un nombre entier entre
et
, suivant l'ordre alphabétique.
Lettre | A | B | C | ... | Z |
Nombre |
|
|
| ... |
|
La fonction de codage
est définie par : 
avec 
.
Pour coder la lettre R, assimilée au nombre
: 
donc 
soit 
avec 
et finalement 
donc le lettre R est codée par G.
1) On affecte à chaque lettre de l'alphabet un nombre entier entre
et
, suivant l'ordre alphabétique.
Lettre | A | B | C |
| Z |
Nombre |
|
|
|
|
|
La fonction de codage
est définie par : avec 
.
Pour coder la lettre C par exemple, on calcule
: 
avec 
, donc
; la lettre C est donc codée par la lettre portant le numéro 17, c'est-à-dire R.
Pour coder le lettre R, assimilée au nombre 17 : donc et 
donc avec d'où finalement
. La lettre R est codée par G.
Lettre | A | B | C | ... | Z |
Nombre |
|
|
|
|
|
|
|
|
|
|
|
On remarque que ce codage consiste à décaler les lettres de l'alphabet de 15 rangs dans le sens de A vers Z.
Le mot SECRET se code HTRGTI.
2) Décoder le mot TJRAXST.
2) Pour décoder on décale les lettres de l'alphabet de 15 rangs dans le sens de Z vers A. Le mot TJRAXST se décode EUCLIDE.
Avec les notations de la partie A, on utilise la fonction de codage définie par : 
, avec . Les clés de ce codage sont
et
.
1) a. Coder le mot HUIT.
b. Montrer que si
alors
. En déduire que deux lettres distinctes ne peuvent pas être codées par la même lettre.
b. Utiliser les propriétés sur les congruences pour montrer que si
alors
divise
.
b. Montrer que si
alors 
. Remarquer que
et
sont premiers entre eux.
b.
divise
. Penser à des encadrements de
et
qui n'ont pas encore été utilisés.
1) a. La lettre H est assimilée au nombre 7. 
avec 
d'où
c'est-à-dire que la lettre H se code par L.
On a ainsi que le mot HUIT se code en LYCH.
1) b.
,
,
et
sont des entiers,
est un entier supérieur ou égal à
.
1/ si 
alors 
.
2/ alors 
.
1) b.
Si
alors 
.
Si
alors 
d'après la propriété 1 sur les congruences avec 
.
Si
alors 
.
Si
alors 
est divisible par
.
Si
alors 
est divisible par
.
et
sont premiers entre eux donc d'après le théorème de Gauss,
divise
. Or 
et 
donc 
.
On en déduit que 
. Le seul multiple de
compris entre
et
est
. On a donc que si
alors
, c'est-à-dire
.
Nous devons ensuite prouver que deux lettres distinctes assimilées aux nombres
et
ne peuvent pas être codées par la même lettre, c'est-à-dire : si
alors
. Cette propriété est la contraposée de la proposition : si
alors
démontrée ci-dessus. Nous savons que si une proposition est vraie, sa contraposée est vraie aussi, donc ici deux lettres distinctes ne peuvent pas être codées par la même lettre. Le codage est donc un bon codage.
1) b. Nous avons utilisé que les nombres
et
sont premiers entre eux. Cette condition est importante. Prenons la fonction de codage
définie par 
, avec 
.
et
ne sont pas premiers entre eux. Un calcul rapide montre que
, c'est-à-dire que H et U se codent toutes les deux en Y. Cette fonction de codage ne peut donc pas être utilisée.
2) Pour pouvoir décoder un message, nous allons définir une fonction de décodage.
a. Déterminer un entier
tel que 
.
b. En déduire l'expression d'une fonction de décodage
telle que : si
alors
.
c. Déchiffrer le mot NMFAYH.
a. 
« il existe
entier tel que
».
b. Soit
le nombre codé en
. 
.
Utiliser les propriétés sur les congruences pour isoler
.
a. Pour trouver une solution particulière de l'équation
, écrire l'algorithme d'Euclide pour la recherche du
de
et
.
b. 
et 
donc 
.
Utiliser ensuite que .
2) a. 
«
est divisible par
».
« il existe 
tel que
».
Il suffit donc de trouver un entier
tel que
.
On reconnaît une identité de Bézout car
et
sont premiers entre eux, on sait donc que cette équation a des solutions entières. Pour trouver une solution particulière nous allons écrire l'algorithme d'Euclide pour la recherche du
de
et
, puis « remonter » cet algorithme pour arriver à une solution particulière.
Le dernier reste
est le
de
et
.
Partons de (
) :
.
De (
) l'on tire
que l'on reporte dans (
) : 
.
De (
) l'on tire
que l'on reporte dans (
) : 
, soit 
. Une solution particulière de l'équation
est donc
et
.
Nous prendrons
(remarque :
peut prendre une infinité de valeurs, toutes celles solutions de l'équation
).
b. Il s'agit maintenant de décoder une lettre correspondant au nombre
avec 
. On cherche donc
tel que : et
soit .
donc .
Utilisons
et .
On a 
et , donc d'après la propriété 2 sur les congruences 
, soit encore 
d'où 
(encore la propriété 2 avec et 
).
Donc si
alors
avec 
où
et 
.
c. Pour décoder la lettre N assimilée au nombre
on calcule
.
soit 
d'où 
et 
donc
.
N est donc la lettre codée B. Le mot NMFAYH se décode BEZOUT.
