Télécharger - Mon cours de maths

CHIFFREMENT AFFINE.
Afin de coder un message, on peut utiliser un chiffrement affine.
On choisit une clé de codage (a ; b) où a et b sont des entiers.
Pour coder une lettre :
1) A cette lettre on associe un nombre entier naturel x en utilisant le tableau ci-dessous :
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
2) On calcule ax + b et on note y l entier compris entre 0 et 25 tel que ax + b  y[26].
3) A y on associe une lettre en utilisant le tableau.
I.
Cas où a = 11 et b = 8.
Coder la lettre M.
II.
Choisir la bonne clé.
On se pose la question suivante : Tous les couples d entiers (a ; b) peuvent-ils être utilisés comme clé de
codage ? Si non, à quelle condition un tel couple convient-il ?
1.
Réduisons le nombre de clés possibles.
a.
Supposons que (a ; b) et (a ; b ) soient deux clés telles que a  a [26] et b  b [26]. Que
peut-on dire des codes obtenus avec ces deux clés ?
b.
Que se passe-t-il si on choisit a = 0 ?
On va donc étudier les clés (a ; b) telles que 1
a
25 et 0
b
25.
c.
En théorie, de combien de codages dispose-t-on ?
2.
Toutes les clés conviennent-elles ?
On choisit la clé (4 ; 3). Coder le mot AN. Que peut-on dire ?
3.
Choisir une bonne clé.
Pour être utilisable, un chiffrement doit coder deux lettres différentes par deux lettres différentes.
Soient x, x' deux entiers compris entre 0 et 25 et y et y’ leurs codes respectifs avec la clé (a ; b).
a.
Montrer que si y = y , alors 26 divise a(x x ).
Théorème de Gauss : Soient a, b et c trois entiers. Si a divise bc et si a est premier avec b, alors a
divise c.
b.
En déduire que si a est premier avec 26 et si y = y , alors x = x .
c.
Donner une condition suffisante pour que le chiffrement soit utilisable. Est-ce une condition
nécessaire ?
d.
Supposons que a et 26 ne soient pas premiers entre eux. On a alors 26 = dk où d est le PGCD
de a et 26. Montrer que la lettre A et la lettre correspondant à k sont deux lettres différentes codées
de la même façon.
e.
De combien de clés utilisables dispose-t-on ? Que penser de la sûreté d un tel chiffrement ?
CHIFFREMENT AFFINE.
CORRECTION
A B C D E
0 1 2 3 4
I.
II.
F
5
G H
6 7
I
8
Cas où a = 11 et b = 8.
M
12 11 12 + 8 = 140
J K L M N O P Q R S T U V W X Y Z
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
10 mod 26
K
Choisir la bonne clé.
1.
a.
Les codes seront les mêmes.
b.
Si a = 0, toutes les lettres sont codées par la même lettre.
On va donc étudier les clés (a ; b) telles que 1
a
25 et 0
b
25.
c.
25 26 = 650 codages possibles.
2.
Toutes les clés conviennent-elles ?
A 0 4 0+3=3 D
N 13 4 13+3=55 3 (26) D
Les deux lettres A et N sont codées par la même lettre D. Pb pour décoder.
3.
Choisir une bonne clé.
Pour être utilisable, un chiffrement doit coder deux lettres différentes par deux lettres différentes.
Soient x, x' deux entiers compris entre 0 et 25 et y et y’ leurs codes respectifs avec la clé (a ; b).
a.
On a ax + b  y(26) et ax + b  y (26).
Si y = y , ax + b  ax + b (26) c'est-à-dire ax  ax (26) c'est-à-dire a(x x )  0 (26) et donc
26 divise a(x x ).
Théorème de Gauss : Soient a, b et c trois entiers. Si a divise bc et si a est premier avec b, alors a
divise c.
b.
Si a est premier avec 26, comme 26 divise a(x x ), d après le th de Gauss, 26 divise x x .
Or x et x sont compris entre 0 et 25 donc x x est compris entre 25 et 25.
Le seul multiple de 26 compris entre 25 et 25 est 0 donc x x = 0, c'est-à-dire x = x .
c.
Si a est premier avec 26, deux lettres codées par la même lettre sont identiques ; ce qui
signifie que deux lettres différentes sont codées par deux lettres différentes.
Le chiffrement est OK.
Une condition suffisante pour que le chiffrement soit utilisable est que a soit premier avec 26.
Ce n est à priori pas une condition nécessaire.
d.
Supposons que a et 26 ne soient pas premiers entre eux. On a alors 26 = dk où d est le PGCD
de a et 26 et a = da avec a et k premiers entre eux.
De plus, 1 k 13 car d
2 donc la lettre correspondant à k n est pas la lettre A.
On a ak + b = da k + b = 26 a + b  b (26)
et a 0 + b  b(26)
donc la lettre A (correspondant à 0) et la lettre correspondant à k sont codées de la même
façon (par la lettre correspondant à b).
e.
26 25 = 650 clés au max.
Il y a 12 nombres entre 1 et 25 premiers avec 26. Pour chacun, on peut choisir 26 valeurs de b.
Il y a donc 12 26 = 312 clés dont on est sûr qu elles sont utilisables. C est facile à décoder
avec un ordi (on teste toutes les clés et on cherche les messages qui ont un sens).
Remarque : la condition est nécessaire. Il n y a que 312 clés utilisables.
En effet :
Soit a un nb non premier avec 26 : a = da et 26 = db avec a et b premiers entre eux.
et 1 b’ 13 car d
2.
On a ab = da b = 26 a  0 (26)
donc la lettre A (correspondant à 0) et la lettre correspondant à b sont codées de la même façon.

Download Report