Clés de contrôle, cryptographie et codes correcteurs
L'essentiel du cours (1 notion)
Clés de contrôle et congruences
Définition : Une clé de contrôle est un symbole ajouté à un code pour vérifier son intégrité à l'aide d'une division euclidienne ou d'une congruence.
Méthode : 1. Pondérer les chiffres du code. 2. Calculer le reste $r$ du total modulo $n$. 3. Déduire la clé $k$ (selon la règle : $k = n - r$ ou $k \equiv -S \pmod n$).
Exemple : Pour la clé du RIB : $K = 97 - (N \pmod{97})$, où $N$ est le numéro à 21 chiffres.
Un code-barres à $8$ chiffres $c_1 c_2 c_3 c_4 c_5 c_6 c_7 k$ utilise un chiffre de contrôle $k \in \{0, 1, \dots, 9\}$.
Pour calculer la clé $k$, on détermine d'abord la somme pondérée des sept premiers chiffres :
$$S = 3c_1 + c_2 + 3c_3 + c_4 + 3c_5 + c_6 + 3c_7$$La clé de contrôle $k$ est le plus petit entier naturel tel que la somme $S + k$ soit divisible par $10$.
Un produit possède les sept premiers chiffres suivants : $4, 0, 1, 2, 3, 4, 5$.
Déterminer la valeur de la clé de contrôle $k$.
Un système de chiffrement affine transforme un nombre $x$ compris entre $0$ et $25$ en un nombre $y$ compris entre $0$ et $25$ selon la congruence $y \equiv a x + b \pmod{26}$, où $a$ et $b$ sont deux entiers compris entre $0$ et $25$ vérifiant $\operatorname{PGCD}(a, 26) = 1$.
On sait que la clé de décalage est $b = 3$ et que la valeur claire $x = 11$ est chiffrée en $y = 8$.
- En traduisant la situation par une congruence, déterminer le reste de $11 a$ modulo $26$.
- Déterminer l'inverse modulaire de $11$ modulo $26$, c'est-à-dire l'entier $u$ compris entre $0$ et $25$ vérifiant $11 u \equiv 1 \pmod{26}$.
- En déduire la valeur du coefficient $a$.
Saisir la valeur de $a$.
Le code européen des articles à treize chiffres (EAN-13) est constitué d'une suite de treize chiffres $a_1 a_2 \dots a_{13}$.
Pour être valide, ce code doit vérifier la condition suivante : la somme obtenue en multipliant chaque chiffre de rang impair par $1$ et chaque chiffre de rang pair par $3$ doit être un multiple de $10$.
Un lecteur optique a scanné un code-barres dont le sixième chiffre est illisible, représenté par la lettre $x$ :
9 7 8 2 0 $x$ 1 4 5 2 3 1 5
Déterminer la valeur du chiffre manquant $x$.
Saisir la valeur de $x$.
Pour chiffrer un texte, on associe à chaque lettre de l'alphabet un entier compris entre $0$ et $25$ selon son rang habituel (A $= 0$, B $= 1$, ..., Z $= 25$).
Le message clair est découpé en blocs de deux lettres représentés par un vecteur colonne $X = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$. Ce bloc est chiffré sous la forme d'un vecteur $Y = \begin{pmatrix} y_1 \\ y_2 \end{pmatrix}$ défini par la relation :
$$Y \equiv A X \pmod{26} \quad \text{où} \quad A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$Les coefficients $a, b, c, d$ sont des entiers compris entre $0$ et $25$. De plus, la matrice $A$ vérifie $\text{PGCD}(ad - bc, 26) = 1$.
On observe que le bloc de lettres claires BE est chiffré en XE, et que le bloc CD est chiffré en VZ.
Saisir la valeur du coefficient $a$.
Un protocole de chiffrement associe à deux nombres premiers $p = 11$ et $q = 17$ un exposant de chiffrement $e = 27$.
Pour déchiffrer un message, l'exposant de déchiffrement est le plus petit entier $d > 0$ vérifiant la congruence $27d \equiv 1 \pmod{160}$.
Cette relation se traduit par l'existence d'un entier positif $k$ vérifiant l'égalité $27d - 160k = 1$.
Par une justification arithmétique complète, prouver l'existence de cet exposant $d$, puis déterminer la valeur de l'entier pivot $k$ associé au plus petit exposant de déchiffrement $d > 0$.
Saisir la valeur de $k$.
Dans un protocole de chiffrement RSA, la clé publique d'un destinataire est représentée par le couple $(n, e) = (77, 13)$. Un message secret $M$, représenté par un entier naturel strictement inférieur à $77$, a été chiffré sous la forme du nombre $C = 57$.
Par une justification arithmétique rigoureuse s'appuyant sur les propriétés des congruences et de l'inverse modulaire, déterminer la valeur exacte du message clair $M$.
Saisir la valeur du message clair $M$.
On s'intéresse à la transmission binaire de messages comportant $11$ bits d'information. Pour corriger d'éventuelles erreurs de transmission, chaque message de $11$ bits est associé à un mot de code binaire de $n$ bits (avec $n > 11$).
Pour qu'un tel code permette de corriger toute erreur portant sur au plus un bit, les ensembles de mots situés à une distance de Hamming au plus égale à $1$ de chaque mot de code doivent être deux à deux disjoints.
Déterminer la valeur minimale de l'entier $n$ pour laquelle l'existence d'un tel code correcteur est théoriquement possible.
Longueur minimale n :