Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 26-02-2009 16:58:51
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
chiffrement affine
Bonjour,
voila je débute dans la crypto et j'ai des difficultés.
Dans un chiffrement affine f(x)= ax+b
On sais que K et chiffrée par D, et N est chiffrée par O.
On me demande:
1) quelles informations sur a et b peut on en déduire:
(moi je me dit que K étant la 17 ème lettrre de l'alphabet, D la 4ème, N la 14ème, et O la 15 ème
f(17)=a17+b=4
f(14)=a14+b=15
)
2.calculer la clé de chiffrement utilisée.
(faut il faire un système?dans ce cas je n'y arrive pas :/ )
3.en déduire la clé de déchiffrement
4.trouver toutes les solutions mod 26 a l'équation 6a=14
merci de bien vouloir m'aider et m'éclairer
:)
Hors ligne
#2 26-02-2009 18:02:01
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Bonsi=oir,
Et bienvenue sur BibMath..
Rassure-toi ou inquiète-toi, j'ignorais l'existence du chiffrement affine jusqu'à ton ton post.
J'ai donc fait une recherche.
Ton présupposé est bon à ceci près que
- D c'est la 4e lettre mais avec un index de 3 (de 0 pour A à 3 pour D ça fait bien 4)
- f(x) = ax+b mais modulo 26
Donc tes équations deviennent :
f(16) = 16a + b = 3 (mod 26=
f(13) = 13a + b = 14
La résolution du système donne 3a = -11 ce qui me gène un peu.
Je fais la supposition que 16a + b = 29 qui modulo 26 donne bien 3.
J'ai alors 3a = 15, soit a = 5 et b... ne colle pas !
Je poursuis mes investigations
@+
Hors ligne
#3 26-02-2009 18:34:51
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
D'accord merci de te pencher sur mon problème :)
oui j'avais oublier de cité le modulo 26.
et justement je trouve le système assez complexe :/ sachant quand plus on doit trouver a et b entier.
Moi je reste avec mes livres emprunté a la bibliothèque en essayant de trouver une éventuel astuce.
merci encore :)
Hors ligne
#4 26-02-2009 19:37:23
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Donc,
Je reprends...
1. Contrairement à ce que tu as dit sur le forum îlemaths, à lettre A ne correspond pas pas le rang 1 parce qu'on travaille modulo 26...
2. K est la la 17e lettre de l'alphabet mais la 11e, de rang 10, N est bien la 14e de rang 13 donc...
3. On a donc :
f(10) = 3 et f(13)=14
soit
[tex]\begin{cases}10a + b &= 13 \;(mod 26)\\13a + b &= 14 \;(mod 26) \end{cases}[/tex]
Soit 13a+b=40 et 3a = 27 d'où a = 9
90 + b = 13 (mod 26) on a 91 = 13 (mod 26) d'où b = 1
Vérification pour 10a + b
10 x 9 + 1 = 91 = 13 mod 26
Donc la clé est (9 ; 1)
@+
Hors ligne
#6 26-02-2009 20:05:51
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
SAlut,
Bin oui...
x modulo 26, c'est le reste de x dans la division par 26. Dans cette division, il y a 26 restes possibles de 0 à 25 et non de 1 à 26 : le reste de 26k (k étant un entier naturel quelconque) dans la division par 26 est 0.
On note [tex]26k\equiv0\;[26][/tex]
@+
Dernière modification par yoshi (26-02-2009 20:06:56)
Hors ligne
#8 27-02-2009 09:08:13
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Salut,
On va faire un peu moins "Dédé la bricole".
En procédant ainsi
(13a + b)-(10a+b) = 14-13
j'obtiens
3a = -1 [26]
Je vais donc chercher k, entier naturel, tel que
1+26k = 0 [3]
soit k = 1 --> 1 + 26 * 1 = 27
3a = 27 et a = 9
D'où b : 10*9 + b = 13
b = -77+ 26k pour 0<=b <= 25
soit k = 3 : b = -77 + 78 = 1
Ou
b = 14 - 13 * 9 = - 103
Et je cherche k pour que
b = -103+26k et 0 <= b <= 25
soit k = 4 et b = -103 + 26 * 4 = 1.
On retrouve la clé (9 ; 1)
Je vais pouvoir écrire ça en Python. Mais y a-t-il quelqu'un qui sache résoudre autrement :
[tex]\begin{cases}10a + b &= 13 \;(mod 26)\\13a + b &= 14 \;(mod 26) \end{cases}[/tex] ?
Ca me semble être du Bezout, mais jr ne vois pas trop comment rapprocher ces deux lignes en une seule du genre ux + vy = 1....
@+
Hors ligne
#9 27-02-2009 20:57:06
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
salut
j'ai deux question sur ce que tu as écrit
comment tu trouves -1 dans
(13a + b)-(10a+b) = 14-13
j'obtiens
3a = -1 [26]
?
et pourquoi à tu mit un mod 3 dans
1+26k = 0 [3]
??
après je comprend la logique c'est comme en cours.
merci d'avoir bien prit le temps de détaillé, je pense avoir prochainement d'autre exercice qui me poseront problème je ferai un nouveau topic dans ce cas la.
a+
Dernière modification par shengao (27-02-2009 21:00:00)
Hors ligne
#10 27-02-2009 21:02:02
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Re,
C'est pourtant simple : faute de frappe, c'est 1 pas -1, bien sûr... !!! :-)
D'ailleurs sur la ligne suivante, j'ai bien écrit 1+26k et non -1+26k
Dans la zone programmation, je présente mes petits programmes (provisoires, en attendant mieux) écrits en python de codage/décodage affine...
@+
Hors ligne
#12 27-02-2009 21:12:31
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Ren
J'avais pas vu :
et pourquoi à tu mit un mod 3 dans
1+26k = 0 [3]
??
Là encore c'est tout bête, il faut que 1+26k soit un multiple entier de 3 et cela n'arrive que si 1+26*k = 0 [3] autrement dit si le reste de 1+26k dans la division par 3 est nul...
+
Hors ligne
#17 28-02-2009 11:57:18
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
Bon alors on a commit un erreur dès le début...
Le systeme est dans l'énoncé
f(k)=D
f(N)=O
et on a fait f(10) = 13 et f(13)=14 or D =3 donc j'ai refait avec le bon système
f(10)=3
f(13)=14
donc
(13a + b)-(10a+b) = 14-3
on obtient
3a = 11 [26]
on cherche k pour que
1+26k = 0 [3]
soit k = 2 --> 11 + 26 * 2 = 63
3a = 63 et a = 21
Et là je me rend compte que je ne comprend pas la logique pour le b... (:suicide:) :'(
Hors ligne
#18 28-02-2009 12:01:26
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
(:mega boulet:)
b = 14 - 13 * 21 = - 259
on cherche k pour que
b = -259+26k et 0 <= b <= 25
soit k = 10 et b = -259 + 26 * 10 = 1.
clé (21,1)
est ce que j'ai compris?
bon maintenant j'attaque la clé de déchiffrement, je sent que je vais là aussi m'amuser. :P
Dernière modification par shengao (28-02-2009 12:04:39)
Hors ligne
#19 28-02-2009 12:21:09
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Salut,
dsl si je parai inculte mais je n'ai pas encore de solide base en arithmétique et en crypto.
Perso, je sais trop bien que ce qui paraît évident à celui qui sait, ne l'est pas pour celui qui cherche sans trouver.
Là c'est un cas classique de cécité caractérisée : on ne voit pas ce qu'on a de simple sous le nez, on échafaude des explications fumeuses et très compliquées... ;-)
Ca arrive à tout le monde...
(21,1) clé exacte si c'est bien K (comme je l'ai supposé) et non k... Attention !
@+
Hors ligne
#20 28-02-2009 12:58:56
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
oui dsl pour le K,
là je cherche pour le déchiffrement, je suis sur une bonne vois, je sais que l'inverse de a (ici 21) est 5,
je fais un pause et je reprend l'exercice en m'instruisant sur comment trouver b.
bonne après midi
Hors ligne
#21 28-02-2009 14:44:39
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
C'est bon j'ai enfin fini cet exercice, je trouve en clée de déchiffrement (5,-5) clé vérifier puisque j'ai traduit un message codé.
Cependant l'avant dernière question est
trouver toutes les solution mod 26 de l'équation 6a=14.
je trouve bizarre qu'il me demande ça.. qu'est ce qu'il veule me faire comprendre? Je vois pas le lien entre l'exercice et la question..
la dernier question est:
tous les couples de lettre décryptées tels que K-->D et N -->O peuvent -ils convenir pour décrypter un cryptogramme affine?
(j'ai repondu qu'il faut que dans ax+b a doit être premier avec 26 et b doit être <= 25
Dernière modification par shengao (28-02-2009 14:48:57)
Hors ligne
#22 28-02-2009 20:28:03
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : chiffrement affine
Bonsoir,
Moi, ce que je ne vois pas c'est pourquoi il pose la question à ce stade...
Une solution simple de 6a = 14 [26] est a = 11.
En effet 6 * 11 = 66 et 66 = 26 * 2 + 14 = 14 [26]
Toutes les solutions donc données par a = 11 + 26k (avec k entier naturel quelconque) : {11,37,63,89,115...}
Elles diffèrent toutes de 26...
Oui, et alors ? Poser la question au début aurait aiguillé sur la recherche de a et b... Mais là... ??!!
@+
Hors ligne
#23 28-02-2009 21:04:57
- shengao
- Membre
- Inscription : 26-02-2009
- Messages : 16
Re : chiffrement affine
franchement je suis épaté avec ta logique modulaire. Je comprend facilement, mais trouver les solutions c'est une autre histoire:/.
j'ai une bonne nouvelle j'ai fini tous les exercices de chiffrement affine donc je t'embêterais plus avec sa.
Une unique dernière question un peu hors sujet au topic... dans le cas d'un chiffrement par substitution simple, pourquoi on peut dire que ce chiffrement est a clé secrète? pour un chiffrement affine oui je comprend que c'est a clé secrète mais par substitution là je vois pas...
Hors ligne
Pages : 1