Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale Calcul matricielTopics traitant de calcul matriciel [tout]Lister tous les topics de mathématiques
Niveau terminale
Partager :

Chiffrement de Hill

Posté par
vmorgane 13-07-14 à 09:42

Bonjour, j'ai un dm a rendre et je bloque sur quelques questions :
Première partie

On se donne pour clé la matrice (8  6)
                                (5  4)
1. Déterminer deux de deux lettres, distincs, et dont le chiffrement par la méthode de Hill donnera le même message.
Là j'ai trouvé B=(0)     et C=(0)     sont tous les deux codés par ( 4)
                 (18)         (5)                                  (20)
  
Par contre je ne sais pas du tout comment l'expliquer, j'y suis allée à taton et il me faudrait une méthode pour le démontrer.

2. Une telle matrice est-elle une clé acceptable?
J'ai dit que non parce que le message codé, lorsqu'il est décodé, peut l'être par deux mots différents et il est impossible de savoir lequel

Deuxième partie

On utilise la clé A= (a   b) où a, b,c et d sont des entiers tels que delta=ad-bc soit un entier non nul premier
                     (c   d)
avec 26.

1. Soit M la matrice (d  -b). Calculer le produit MA
                     (-c  a)

J'ai trouvé : MA=(delta      0)
                 (0      delta)

2. Déduire de la question précédente l'existence d'une matrice B à coefficients entiers telle que le produit BA soit égal à la matrice sI2 où s est un entier tel que s congru a 1 modulo 26.

Là je ne sais pas du tout.
Si vous pouviez m'aider s'il vous plait

Posté par
carpediemre : Chiffrement de Hill 13-07-14 à 10:27

salut

la question 1/ n'est pas bien claire .... et sa réponse ....

mais la partie 2 te donne aussi une raison pour laquelle la matrice de la partie 1 ne convient pas ....

Posté par
carpediemre : Chiffrement de Hill 13-07-14 à 10:28

tu as donc MA = DI où D = ad - bc = s ....

Posté par
vmorganere : Chiffrement de Hill 13-07-14 à 10:43

Je pensais a poser
BA=s*I2 d'où B*(A/s)=I2

Mais en remplacant je tombe sur

B* (a/s    b/s) = (1  0)
   (c/s    d/s)   (0  1)

Si je continue je retombe sur un système mais qui me parait impossible a résoudre

Posté par
athrunre : Chiffrement de Hill 13-07-14 à 10:51

Bonjour,

pour la 2) : tu as MA=\delta I_2. Donc on y est presque en soi, c'est juste qu'on a pas \delta\equiv1\pmod{26}.

Je te rappelle que \delta\wedge26=1, donc ...

Posté par
carpediemre : Chiffrement de Hill 13-07-14 à 10:53

mais B = M et s = ad - bc !!! tout simplement ...


peux-tu m'éclaircir sur ce que tu as fait à la question 1/ ... je ne comprends pas !!!

Citation :
Déterminer deux de deux lettres, distincs, et dont le chiffrement par la méthode de Hill donnera le même message.
Là j'ai trouvé B=(0)     et C=(0)     sont tous les deux codés par ( 4)
                 (18)         (5)                                  (20)
  

Posté par
athrunre : Chiffrement de Hill 13-07-14 à 11:01

carpediem : \delta\not\equiv1\pmod{26} donc s=\delta ne convient pas.

Ensuite je suppose que la question est en réalité "déterminer deux mots distincts de deux lettres tels que leur chiffrement par la méthode de Hill donnera le même message.

Ici on a bien   \begin{pmatrix}8&6\\ 5&4 \end{pmatrix}\begin{pmatrix}0\\18\end{pmatrix}=\begin{pmatrix}8&6\\ 5&4 \end{pmatrix}\begin{pmatrix}0\\5\end{pmatrix}=\begin{pmatrix}4\\20\end{pmatrix}   (modulo 26).

Posté par
carpediemre : Chiffrement de Hill 13-07-14 à 11:12

merci beaucoup athrun ...

pour la partie 2 :: si on dit que ad - bc est un entier non nul premier avec 26 donc s = ad - bc convient ...

c'est justement ce qu'on n'a pas avec la première matrice

Posté par
vmorganere : Chiffrement de Hill 13-07-14 à 11:18

Donc j'ai posé b=(d   -b)
                 (-c   a)

Puis =1

ensuuite j'en ai déduis des entiers possibles a,b,c et d (je ne sais pas si c'est très mathématiques..)
a=7 ; b=3 ; c=9 ; d=4
donc a*d-b*c=1 et B=(4  -3)
                    (-9  7)

Pour la question 1/
J'ai cherché deux mots par exemple B=(a)    et C=(c)
                                     (b)         (d)

tel que A*B congru a A*C.
Le problème c'est que je pense avoir la bonne méthode mais je n'aboutis a rien. J'ai donc ensuite cherché en essayant des combinaisons et je tombe toujours sur des paires de mots sur genre B=(0)  et C=(0)
                                                                                  (k)       (k+13)

Posté par
flightre : Chiffrement de Hill 13-07-14 à 11:52

salut

un exo du meme type à deja été posé :

Chiffrement de Hill

Posté par
athrunre : Chiffrement de Hill 13-07-14 à 11:55

@carpediem : ah oui, si on choisit ad-bc tel que ça soit congru à 1 ça marche tout seul (je pensais qu'ils étaient déjà fixés et vérifiaient simplement (ad-bc)\wedge26=1).

@vmorgane : je ne suis pas sûr que tu ais besoin d'expliciter a,b,c,d. Tu supposes juste que a,b,c et d sont des entiers tels que (ad-bc)\wedge 26=1 et ad-bc\equiv1\pmod{26}, alors la matrice B=\begin{pmatrix}d&-b\\-c&a\end{pmatrix} convient avec s=\delta=ad-bc.

Si tu as juste la propriété \delta\wedge26=1, alors l'identité de Bézout fournit \lambda et \mu tels que \lambda\delta+26\mu=1 et donc B=\lambda\begin{pmatrix}d&-b\\-c&a\end{pmatrix} avec s=\lambda\delta convient.

Pour la question 1), il ne t'est pas demandé de trouver toutes les paires de mots distincts qui ont le même chiffré. Pour te simplifier la vie, tu peux alors chercher une paire de mots distincts sous la forme \begin{pmatrix}0\\ \alpha\end{pmatrix} et \begin{pmatrix}0\\ \beta\end{pmatrix}. On obtient alors après calcul le système suivant :

6(\alpha-\beta)\equiv0\pmod{26}
4(\alpha-\beta)\equiv0\pmod{26}

Cela montre en particulier que 13 divise \alpha-\beta. Puis toutes les paires \left\{\begin{pmatrix}0\\ \beta+13\end{pmatrix},\begin{pmatrix}0\\ \beta\end{pmatrix}\right\} conviennent.

Posté par
vmorganere : Chiffrement de Hill 13-07-14 à 12:17

Merci, je crois avoir compris pour le même si l'utilisation de l'identité de Bézout me laisse dans le flou.. le fait de prouver que n'est pas nul et sachant que a, b,c et d sont des entiers ne suffit-il pas a prouver l'existence de cette matrice B constituée d'entiers ?

Pour la question 1 ensuite j'ai compris le raisonnement mais je ne vois pas comment vous arrivez a passer du fait que 13 divise - à la forme des paires qui conviennent. Est-ce-qu'il serait possible de m'expliquer s'il-vous-plait

Posté par
athrunre : Chiffrement de Hill 14-07-14 à 18:34

Dans l'exercice, il est simplement dit que \mathrm{pgcd}(\delta,26)=1. Dès lors, si \delta est fixé (ie si a,b,c,d le sont), on a juste \delta\wedge26=1 et pas forcément \delta\equiv1\pmod{26}. Donc prendre B=M et s=\delta ne fonctionne pas à cause du fait que \delta n'est pas forcément égal à 1 modulo 26.

Je récapitule : si \delta\equiv1\pmod{26} on prend B=M et s=\delta. Sinon (ie si \delta\not\equiv1\pmod{26}), on s'en sort grâce au théorème de Bézout : comme \mathrm{pgcd}(\delta,26)=1, il existe (\lambda,\mu)\in\mathbb{Z}^2 tels que \lambda\delta+26\mu=1. Cela donne donc que \lambda\delta\equiv1\pmod{26}. Donc on prend s=\lambda\delta. Comme on a déjà MA=\delta I_2, on a (\lambda M)A=(\lambda\delta)I_2, on prend B=\lambda M.

Pour le 1), prenons deux mots de la forme \begin{pmatrix}0\\ \alpha\end{pmatrix} et \begin{pmatrix}0\\ \beta\end{pmatrix}. Alors on a \begin{pmatrix}8&6\\ 5&4 \end{pmatrix}\begin{pmatrix}0\\ \alpha\end{pmatrix}=\begin{pmatrix}8&6\\ 5&4 \end{pmatrix}\begin{pmatrix}0\\ \beta\end{pmatrix} si et seulement si :

\left\{\begin{array}{cc} \\ 6\cdot(\alpha-\beta)&\equiv0\pmod{26}\ (1)\\ \\ 4\cdot(\alpha-\beta)&\equiv0\pmod{26}\ (2). \\ \end{array} \\ \right.

On a  (1)\ \Leftrightarrow\ (2)\ \Leftrightarrow\ 13\ |\ \alpha-\beta. En effet si 13 divise \alpha-\beta alors on a clairement (1) et (2), et pour l'autre sens, par exemple pour (1) ; comme 26 divise 6(\alpha-\beta), alors 13 divise 6(\alpha-\beta). Comme 13 est premier avec 6, alors 13 divise \alpha-\beta par le théorème de Gauss. Dès lors :

13\ |\ \alpha-\beta\ \Leftrightarrow\ \exists k\in\mathbb{Z},\ \alpha=\beta+13k.

Modulo 26, si k est pair, on obtient \alpha=\beta, ce qui n'est pas ce qu'on veut. Du coup, pour avoir \alpha\not\equiv\beta \pmod{26}, et le même chiffré de Hill pour les deux mots de la forme \begin{pmatrix}0\\ \alpha\end{pmatrix} et \begin{pmatrix}0\\ \beta\end{pmatrix}, il faut et il suffit que |\alpha-\beta|\equiv13\pmod{26}. D'où par exemple les paires de mot que j'ai données dans mon précédent message. C'est plus clair ?


Rechercher
Menu
Espace membre
Changer d'île

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 1675 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 !