Bonjour,
J'espère que vous passez un bon dimanche!
J'ai un DM de maths expertes et je voudrais avoir de l'aide pour la dernière partie.
Voici l'énoncé de DM:
Le chiffrement affine est une méthode de cryptographie basée sur un chiffrement par substitution mono-alphabétique, c'est-à-dire que la lettre d'origine n'est remplacée que par une unique autre lettre. On choisit a ∈ N∗ et b ∈ N. Le couple (a; b) est appelé la clef du chiffrement. Chaque lettre du texte à chiffrer est d'abord remplacée par son équivalent numérique m, puis chiffrée par le calcul du reste de la division euclidienne par 26 de l'expression affine am + b, soit l'entier p tel que : p ≡ am + b [26].
Et voici l'énoncé de l'exercice qui me pose problème
Partie D
Dans cette partie, on considère une chiffrement affine simple de clef (a; b) avec a ∈ N∗ et b ∈ N.
1) On suppose que a et 26 sont premiers entre eux.
Démontrez que pour tous entiers m et m′ : am + b ≡ am′ + b [26] si, et seulement si m ≡ m′ [26].
2) Dans quel cas, le chiffrement et le déchiffrement sont ils impossibles ? Justifiez.
3) Déterminez le nombre de chiffrements affines possibles. Justifiez.
4) En déduire une méthode pour « casser » une clef simple de chiffrement affine
Pour le 1) ça me semble tellement logique alors que je ne vois pas comment faire. Je suis arrivé à démontrer dans un sens mais pas dans l'autre et je ne suis pas sûr si j'ai juste.
Si
Réciproquement
( avec )
Et c'est là que je me bloque. L'idée c'était de me débarrasser de pour pouvoir diviser par a mais je pense que c'est une mauviase idée.
Je sais que comme et 26 sont premiers entre eux cela veut dire que et
qu'il existe et tels que mais je ne sais pas comment m'en servir.
Pour le 2) j'ai dis que le chiffrement et le déchiffrement sont impossibles quand a et 26 ne sont pas premiers entre eux mais je n'arrive pas à le justifier.
3) On sait que a et 26 sont premiers entre eux. Or, il existe 12 nombres premiers et inférieurs à 26 donc a peut prendre 12 valeurs différentes et b peut prendre les valeurs allant de 0 à 26. Autrement dit, on a 12*26=312 dhiffrements affines possibles.
4) On en déduit qu'il suffit de tester les 312 clefs possibles pour déchiffrer u n message codé.
Je vous remercie d'avance pour votre aide,