Etude d'un chiffrement affine et de son décodage


  • B

    Bonsoir à tous, et merci d'avance à ceux qui m'aideront pour ce dm:
    On considère la méthode de chiffrement ( = de codage ) suivante : tout d'abord, à chaque lettre de l'alphabet on associe sa position dans l'alphabet, en commençant par 0 pour la lettre A (puis B -> 1 , C ->2 , D-> 3 etc...). Puis une lettre associée au nombre x est codée par la lettre associée au nombre f(x) ≡ ax+b [ 26] ( = reste de la division euclidienne de ax+b par 26 ; en effet toutes les lettres sont ici codées par des nombres compris entre 0 et 25) avec a et b à préciser.

    1. Si l'on choisit a = 3 et b = 5, quel est le codage du mot CIPHER (mot anglais signifiant cryptage ) ? Que constate-t-on si l'on prend a = 2 au lieu de a = 3 ?
    2. a) Vérifier que f(x) = f(x') équivaut à a(x-x') ≡ 0 [ 26 ] puis que si 0 ≤ x ≤ 25 alors -25 ≤ x-x' ≤ 25.
      b) A quelle condition sur a peut-on dire que, pour tous x et x' , a ( x-x' ) ≡ 0 [26] équivaut à x= x' ? ( c'est à cette condition que l'on pourra dire que le chiffrement est valable, c'est-à-dire que l'on n'est pas confronté au problème observé au 1) avec a = 2 ; pour justifier la réponse, on pourra utiliser le théorème de Gauss...)
      c) En déduire le nombre de chiffrements affines valables possibles en faisant varier a et b entre 0 et 25 ( remarque : b n'intervient pas dans les 2 questions précédentes, donc on n'a pas de " restriction " sur b comme on en a trouvée sur a...).

    PS : L’exercice n'est pas terminé je mettrai la suite après avoir fait ces questions là.

    Mes réponses pour le moment:

    1. J'ai trouvé comme code LDBARE pour a = 3 , et JVLTNN pour a = 2.. On constate un cryptage différent
      2)a) f(x) = ax +b , f(x') = ax'+b
      f(x) = f(x') = 0 soit encore (ax+b) - (ax+b) = a (x-x') = 0
      ax+b ≡ ax'+b [26] , ce qui conduit à a(x-x') ≡ 0 [26]
      

  • N
    Modérateurs

    Bonjour Breezy94,

    Pour la question 2 a) c'est f(x) =f(x')

    Pour la question b) il faut analyser les cas a premier ou non avec 26.


  • B

    Comment vérifier que si 0 ≤ x ≤ 25 et 0 ≤ x' ≤ 25 alors -25 ≤ x-x' ≤ 25 ?


  • N
    Modérateurs

    Si 0 ≤ x' ≤ 25
    quel encadrement pour -x ?


  • B

    0≤ - x '≤ -25
    Jai ensuite additioné
    0 ≤ x ≤ 25
    -25 ≤ -x' ≤ 0
    Ce qui donne -25 ≤ x-x' ≤ 25
    Es ce correct ?


  • B

    Pour la 2)b je n'y arrive vraiment pas..


  • N
    Modérateurs

    2 a) Correct,
    2 b) analyse les cas de a premier ou non avec 26.


  • B

    si 26 est premier avec a, il divise x-x' on aura donc x-x' ≡ 0 [26] et comme les x sont entre 0 et 25, x = x' donc on pourra décoder, et si a n'est pas premier avec 26 x n'est pas égale à x' donc on ne pourra pas décoder..
    C'est correct ?


  • N
    Modérateurs

    Rapide comme démonstration mais c'est la réponse attendue.


  • B

    D'accord, je cherche la 2)c..


  • N
    Modérateurs

    Tu cherches les valeurs de a tel qu'il soit premier avec 26.


  • B

    je trouve 11 a premier avec 26
    Le nombre de chiffrement valable est de 286 ?


  • B

    En attendant votre réponse.. Voici la suite l'exo :
    On considère la phrase cryptée suivante : IXBTPY UXTO KXUUTJ SHNHUNTJ TM NXRRTUNTE KFTU OH UXPSTOOT HUUTT

    Pour la décoder, il faut déja déterminer les nombres a et b intervenant dans le chiffrement affine x -> f(x) ≡ ax+b [26] et un outil possible est l'étude de la fréquence des lettres.
    3) Dans un texte normal en Français, la lettre la plus fréquente est E. Quelle est la lettre la plus fréquente dans la phrase codée précédente? (On a donc la correspondance E -> ? soit numériquement 4 -> f(4) ≡ ? ce qui donne une 1ere relation, à compléter ..a + b ≡ ... [26] ; mais pour déterminer les deux inconnues a et b il faut une 2eme relation qui donnera un système) Quelle est la 2eme lettre fréquente dans la phrase codée ? (On admet qu'on en déduit la relation suivante 13a + b ≡ 20 [26] )
    4) Ecrice le système de congruences obtenu en combinant les deux relations précédentes ; en déduire qu'on obtient 9a ≡ 1 [26 ] puis proposer une valeur de a (On dit que 9 est l'inverse de a mod 26). En déduire ensuite la valeur de b puis la formule de décodage si l'on prend x -> y ≡ ax+b [26] pour le codage, pour le décodage on a y -> x ≡ ....... [ 26 ] ( Formule à compléter avec les a et b trouvés)
    5) Décoder alors la phrase ci dessus

    Mes réponses pour le moment :
    3) 4 -> f(4) ≡ 19 On a 4 a + b≡ 19 [26]
    La 2eme lettre la plus fréquente est U
    4) y-> x ≡ 3x+7 [26] ( a = 3 et par déduction b = 7 )
    5) Je n'arrive pas à décoder la phrase mais j'ai quand trouvé par stratégie qu'elle veut dire JOYEUX NOEL BONNES VACANCES ET COMMENCEZ BIEN LA NOUVELLE ANNEE


  • N
    Modérateurs

    Pour le décodage il faut trouver a' l'inverse de a puis le reste de la division euclidienne par 26 de a' (26-b)
    et compléter la relation : y -> x ≡ ....... [ 26 ]


  • B

    9 pour a et 15 pour b ?


  • B

    9 pour a et 15 pour b ?


  • B

    Y -> x ≡ 9y +15 ?


  • N
    Modérateurs

    C'est correct.


  • B

    Pour le 2)c j'ai trouvé 12 a donc le nombre de chiffrement valable est de 312? (12x 26 )


  • N
    Modérateurs

    11 ou 12 ?


Se connecter pour répondre