Accueil | Outils
Arithmétique
Cryptographie

## 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.

Partie A : le chiffrement de César

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.

Aide méthodologique

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 .

Aide détaillée

Pour coder la lettre R, assimilée au nombre : donc soit avec et finalement donc le lettre R est codée par G.

Solution détaillée

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.

Solution simple

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.

Partie B : un exemple de codage par transformation affine

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.

Aide méthodologique

b. Utiliser les propriétés sur les congruences pour montrer que si alors divise .

Aide simple

b. Montrer que si alors . Remarquer que et sont premiers entre eux.

Orientation

b. divise . Penser à des encadrements de et qui n'ont pas encore été utilisés.

Solution détaillée

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.

Propriété
Propriétés sur les congruences :

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.

Remarque

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.

Aide méthodologique

a. « il existe entier tel que ».

b. Soit le nombre codé en . .

Utiliser les propriétés sur les congruences pour isoler .

Aide détaillée

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 .

Solution détaillée

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.

Précédent Suivant