Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Exercice chiffrement affine ( maths expertes)

Posté par
Matibo
22-12-20 à 14:51

Bonjour!
Désolée de déranger pendant les fêtes, mais j'aurai besoin d'aide pour mon DM de maths expertes.
L'énoncé:
Le chiffrement affine est une méthode de cryptage des messages basée sur le principe suivant :
Chaque lettre est associé à un nombre : A=0, B=1 ... Z=25. On considère ensuite un couple d'entiers (a;b) qui constitue la clé de chiffrement.
Cela signifie que , à chaque entier x allant de 0 à 25, on lui attribue comme image le reste de la division de f ( x) par 26 où f(x)  est la fonction affine définie par f(x)=ax+b
Par exemple, avec la clé (5;1), B sera codé par G car f(1)=6.
1) Coder les lettres A et J avec la clef (3;2)
2) Quel est l'inconvénient de la clé (13;5)
3) On utilise la clé (13;5)
    a) Coder le mot PGCD
    b)Justifier l'existence d'un couple (u;v) tels que 21u+26v=1 et déterminer un tel couple
    c) EN déduire l'inverse de 21 modulo 26 ( c'est a dire l'entier x' tel que 21x' est congru à 1 modulo 26, et dont on admettra l'unicité)
    d) Décoder la lettre D

(Je vous transmets mes réponses dans le prochain message)

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 15:01

1)  codage lettre A : 3 x 0 + 2 congru à 2 (26)   lettre codée : C
      codage  lettre J  : 3 x 9 + 2 congru à 3 (26)   lettre codée  D

2) Je n'arrive pas à justifier l'inconvénient, mais j'ai compris qu'il n'y aura que deux lettres codées ( en regardant sur un tableur)

3)a)  clé  (21;11)
P : 21 x 15 + 11 congru à 14 (26)   lettre codée: O
G: 21x6+11 congru à 7 (26)   lettre codée H
C:  21 x 2+11 congru à 1 (26)   lettre codée B
D 21x3+11 congru à 22 (26)  lettre codée X

b) D'après le théorème de Bézout, il existe deux entiers u et v tel que 21u + 26v = 1 si et seulement si PGCD(21;26) = 1
26 = 21 x 1+ 5
21 = 5 x 4 + 1[
Grace à l'algorithme d'euclide, je trouve le couple d'entiers ( 5;-4)

c ) je n'ai pas vu en cours comment trouver l'inverse


Merci d'avance pour votre aide

Posté par
mathafou Moderateur
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 15:30

Bonjour,

2) Je n'arrive pas à justifier l'inconvénient, mais j'ai compris qu'il n'y aura que deux lettres codées ( en regardant sur un tableur)

comment décoder ?

3) On utilise la clé (13;5)
3)a) clé (21;11)

je suppose que dans le premier message (13;5) était une faute de frappe

PGCD --> OHBX
erreur de calcul dans le codage du D :
V =
W =
X =
Y =
Z = 25
et donc 22 c'est ?

b) OK (détailler le lien entre l'algorithme et le résultat obtenu)

c) la définition de l'inverse est
un nombre u tel que 21u ≡ 1 [26]
quel lien peux tu faire avec 21u + 26 v = 1 ?

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 16:05

Bonjourmathafou,

2) De ce que j'ai compris , pour décoder il faut utiliser l'inverse de a ( 26) ou quelque chose comme ça... ce n'est pas très clair

3) Oui pardon faute de frappe! et c'est la lettre W et pas X.

b) que voulez-vous dire dans "détaillez le lien "
c) et bien j'imagine que cela veut dire que 26v est congru à 0  (26) ce qui est logique...  AH ! et bien si je fais 5 x 21 = 105 et 4 x 21 = 104, Je vois bien que l'inverse de 21 ( 26) est 105

Posté par
mathafou Moderateur
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 17:24

2)
tout simplement si plusieurs lettres du message clair ont le même code, il est impossible de décoder.
si A, C, E, etc sont tous codés F comment décoderait on ce "F" ??
il serait impossible de savoir si cela représente un A, un C, un E etc

3b)
21 = 5 x 4 + 1 OK
et ensuite ? comment cela te permet d'affirmer que 5x21 - 4 x26 = 1 ?
d'où précisément sortent ce "5" et ce "-4" ?

3c)
21u + 26v = 1 veut dire que 21u ≡ 1 [26]
et donc que le u que tu as trouvé dans la question d'avant est l'inverse de 21 modulo 26
c'est tout :
21 x 5 ≡ 1 [26]
5 est l'inverse de 21

et de façon générale c'est comme ça qu'on trouve l'inverse ; grâce à l'algorithme d'Euclide et la relation de Bézout (le "au + bv = PGCD")

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 18:47

2) D'accord, en gros je montre que plusieurs lettres sont codées par la même  lettre.

3) b) Oui je fais la méthode vue en cours, je fais l'algorithme puis je le "remonte" pour trouver les deux solutions.

3c Oh d'accord c'est 5 et non 105. Il suffit de l'expliquer comme nous l'avons fait plus haut ou il faut approfondir?

d) Et pour décoder j'utilise l'inverse de 21 c'est ça?

Merci beaucoup pour votre aide!

Posté par
mathafou Moderateur
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 19:27

3b) OK. tu n'avais pas écrit explicitement ici cette remontée.
3c) il suffit de bien comprendre que au + bv = d veut dire au ≡ d [b]

3d) oui, mais pas que ...
décoder ça veut dire trouver la transformation inverse

codage : y = ax + b [mod 26]
décodage : x = a'y + b' [mod 26]

il faut trouver a' et b'
a' sera l'inverse de a modulo 26, oui. (mais vois tu pourquoi ?)
mais il faut aussi calculer b' !

c'est comme résoudre une équation
d'habitude résoudre Y connu = ax + b , x inconnu, on divise par a
sauf que là avec des congruences "diviser" ça n'existe pas ! on multiplie par l'inverse
sinon la méthode est la même pour mettre l'inconnue d'un côté et les constantes ("connues") de l'autre.

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 22-12-20 à 20:00

D'accord  je vais essayer de le faire je vous envoie mes résultats demain!

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 23-12-20 à 09:12

3 d) Donc  b est le reste de la division euclidienne de  a' ( 26-b) par 26?
     et quand j'ai retrouvé cela  j'utilise la formule  y=a'y+b'
Par contre je ne saurais expliquer pourquoi nous utilisons les inverses...

Posté par
mathafou Moderateur
re : Exercice chiffrement affine ( maths expertes) 23-12-20 à 10:58

on veut "résoudre" y = ax+b (modulo 26)
dans laquelle y est connu (la lettre codée) et x inconnu (la lettre du message en clair)
on fait comme pour n'importe quelle équation :
on met ce qui est inconnu (le terme en x) d'un côté et ce qui est connu de l'autre (b et y)
ax = y - b (modulo 26) (on a en fait retranché b aux deux membres)

là "normalement" (dans R) on diviserait par a

mais diviser c'est multiplier par l'inverse a', vu que a' * a = 1 modulo 26
comparer avec (1/a)*a = 1 dans les réels, c'est pareil

et on obtiendra bien
x = a' * y - a' * b modulo 26

26-b mouais ... pour calculer une congruence on ajoute ou retranche autant de fois 26 qu'on en a besoin.

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 03-01-21 à 18:15

Bonjour, désolée de répondre si tard mais je n'avais pas vu votre réponse.  Je n'ai toujours pas compris comment décoder la lettre D. ..

Posté par
mathafou Moderateur
re : Exercice chiffrement affine ( maths expertes) 03-01-21 à 18:36

la lettre D ou n'importe quelle autre c'est pareil

si pour coder la lettre de rang x, on calcule y = ax+b [26]
pour décoder la lettre de rang y (c'est à dire retrouver le "clair" x connaissant le message en code y)
on calcule d'abord l'inverse a' de a
à partir de y = ax+b [26] (règle de codage)
en multipliant par a' (qui est premier avec 26, donc aucun problème)
cela donne a'y = a'ax + a'b [26]
c'est à dire puisque aa' = 1 [26]
x = a'y -a'b [26] (règle de décodage)

la question est directement l'application numérique de ça avec les valeurs
a = 21 et b = 11
a' = 5 (question d'avant)
et y = 3 (rang de la lettre D à décoder)

tous les calculs se faisant modulo 256
sans qu'il soit prévisible à priori combien de fois il faudra ajouter ou retrancher 26 pour obtenir entre 0 et 25
ça se fait sur les valeurs numériques quand on les calcule.

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 03-01-21 à 19:12

D'accord merci beaucoup pour votre aide! Mais pourquoi y a t il un signe moins qui apparait à la dernière étape ?

Posté par
mathafou Moderateur
re : Exercice chiffrement affine ( maths expertes) 03-01-21 à 19:17

A = B +C
A - C = B
B = A - C
manipulations de collège sur des égalités
que ce soit des congruences ne change rien à la chose.

Posté par
Matibo
re : Exercice chiffrement affine ( maths expertes) 03-01-21 à 19:21

ah pardon excusez moi. Bonne soirée!



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !