Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Chiffrement – Bac S Pondichéry 2018 (spé)

Exercice 4 (5 points)

Candidats ayant suivi l'enseignement de spécialité

À toute lettre de l'alphabet on associe un nombre entier xx compris entre 0 et 25 comme indiqué dans le tableau ci-dessous :

Lettre A B C D E F G H I J K L M
xx 0 1 2 3 4 5 6 7 8 9 10 11 12
Lettre N O P Q R S T U V W X Y Z
xx 1314151617181920212223 24 25

Le « chiffre de RABIN » est un dispositif de cryptage asymétrique inventé en 1979 par l'informaticien Michael Rabin.

Alice veut communiquer de manière sécurisée en utilisant ce cryptosystème. Elle choisit deux nombres premiers distincts pp et qq. Ce couple de nombres est sa clé privée qu'elle garde secrète.

Elle calcule ensuite n=p×qn = p \times q et elle choisit un nombre entier naturel BB tel que 0Bn10 \leqslant B \leqslant n - 1.

Si Bob veut envoyer un message secret à Alice, il le code lettre par lettre.

Le codage d'une lettre représentée par le nombre entier xx est le nombre yy tel que :

yx(x+B)[n] avec 0yn.y \equiv x(x + B)\:\: [n] \:\text{ avec }\: 0 \leqslant y \leqslant n.

Dans tout l'exercice on prend p=3,q=11p = 3,\: q = 11 donc n=p×q=33n = p \times q = 33 et B=13B = 13.

Partie A : Cryptage

Bob veut envoyer le mot « NO » à Alice.

  1. Montrer que Bob code la lettre « N » avec le nombre 8.

  2. Déterminer le nombre qui code la lettre « O ».

Partie B : Décryptage

Alice a reçu un message crypté qui commence par le nombre 3.

Pour décoder ce premier nombre, elle doit déterminer le nombre entier xx tel que :

x(x+13)3[33] avec 0x<26.x(x + 13) \equiv 3 \:\: [33]\: \text{ avec }\: 0 \leqslant x < 26.

  1. Montrer que x(x+13)3[33]x(x + 13) \equiv 3\:\: [33] équivaut à (x+23)24[33].(x + 23)^2 \equiv 4\:\: [33].

    1. Montrer que si (x+23)24[33](x + 23)^2 \equiv 4\:\: [33] alors le système d'équations

      {(x+23)24[3](x+23)24[11]\left\{\begin{array}{l c l} (x + 23)^2 &\equiv &4 \:\: [3]\\ (x + 23)^2 &\equiv &4 \:\: [11] \end{array}\right.

      est vérifié.

    2. Réciproquement, montrer que si

      {(x+23)24[3](x+23)24[11]\left\{\begin{array}{l c l} (x + 23)^2 &\equiv &4\:\: [3]\\ (x + 23)^2 &\equiv &4 \:\: [11] \end{array}\right.

      alors (x+23)24[33].(x + 23)^2 \equiv 4\:\: [33].

    3. En déduire que :

      x(x+13)3[33]x(x + 13) \equiv 3\:\: [33] \Leftrightarrow {(x+23)21[3](x+23)24[11] \left\{\begin{array}{l c l} (x + 23)^2 &\equiv&1 \:\: [3]\\ (x + 23)^2 &\equiv& 4 \:\: [11] \end{array}\right.

    1. Déterminer les nombres entiers naturels aa tels que 0a<30 \leqslant a < 3 et a21[3]a^2 \equiv 1 \:\: [3].

    2. Déterminer les nombres entiers naturels bb tels que 0b<110 \leqslant b < 11 et b24[11]b^2 \equiv 4\:\: [11].

    1. En déduire que x(x+13)3[33]x(x + 13) \equiv 3 \quad[33] équivaut aux quatre systèmes suivants :

      {x2[3]x8[11]\left\{\begin{array}{l c l} x &\equiv&2\quad [3]\\ x&\equiv &8\quad[11] \end{array}\right.
      ou
      {x0[3]x1[11]\left\{\begin{array}{l c l} x &\equiv& 0\quad[3]\\ x &\equiv& 1 \quad[11] \end{array}\right.
      ou
      {x2[3]x1[11]\left\{\begin{array}{l c l} x &\equiv& 2\quad[3]\\ x &\equiv&1 \quad[11] \end{array}\right.
      ou
      {x0[3]x8[11]\left\{\begin{array}{l c l} x &\equiv& 0\quad [3]\\ x &\equiv& 8 \quad [11] \end{array}\right.

    2. On admet que chacun de ces systèmes admet une unique solution entière xx telle que 0x<330 \leqslant x < 33.

      Déterminer, sans justification, chacune de ces solutions.

  2. Compléter l'algorithme ci-dessous pour qu'il affiche les quatre solutions trouvées dans la question précédente.

    algorithme décodage Rabin

  3. Alice peut-elle connaître la première lettre du message envoyé par Bob ?

    Le « chiffre de RABIN » est-il utilisable pour décoder un message lettre par lettre ?