ECB et CBC en Haskell

Voici un petit travail pour les INFO1 qui devra être rendu sous forme d'un fichier hs et transmis via courriel à votre responsable de TD avant le vendredi 13 à 17h59.

Nous ne chercherons pas
à être très efficaces : nous nous contenterons d'une approche naïve utilisant
les caractères ASCII.

  • Commencez par écrire une fonction qui convertit un entier en base 10 en
    une liste de sept bits en base 2. Par exemple:
    Haskell
    *CryptoSys> toBin 97
    [1,1,0,0,0,0,1]
    *CryptoSys> toBin 15
    [0,0,0,1,1,1,1]
    *CryptoSys> toBin 1
    [0,0,0,0,0,0,1]
      
  • Créez une fonction réciproque qui convertit une chaîne de 7 bits en un
    entier en base 10:
    Haskell
    *CryptoSys> toDec [0,0,0,1,1,0,1]
    13
    *CryptoSys> toDec [1,1,1,1,1,1,1]
    127
      
  • Nous utiliserons un codage adapté à nos besoins. Les codes ASCII
    sont accessibles via les
    fonctions chr et ord de la bibliothèque Data.Char.

    On prendra comme alias C pour cette bibliothèque:

    Haskell
    import qualified Data.Char as C

    Par exemple:

    Haskell
    *CryptoSys> map C.chr [0..127]
    "\NUL\SOH\STX\ETX\EOT\ENQ\ACK\a\b\t\n\v\f\r\SO\SI\DLE\DC1\DC2\DC3\DC4\NAK\SYN\ETB\CAN\EM\SUB\ESC\FS
    \GS\RS\US !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvw
    xyz{|}~\DEL"

    Au-delà, c'est moins drôle:

    Haskell
    *CryptoSys> map C.chr [128 .. 140]
    "\128\129\130\131\132\133\134\135\136\137\138\139\140"

    Mais on peut avoir une sortie correspondant à l'UTF8 via la fonction
    putStrLn qui a une signature un peu étrange:

    Haskell
    *CryptoSys> :t putStrLn
    putStrLn :: String -> IO ()

    et qui n'est pas trop explicable à notre niveau. Disons que IO est ce qui
    correspond aux entrées/sorties en Haskell.

    Mais il faut passer une option au compilateur. Or nous utilisons
    GHCi... Heureusement, il existe un moyen pour passer une option à GHC via le
    fichier d'extension hs. Il faut mettre en en-tête du fichier:

    Haskell
    {-# LANGUAGE OverloadedStrings #-}

    Alors, par exemple:

    Haskell
    *CryptoSys> C.ord 'à'
    224
    *CryptoSys> C.chr 224
    '\224'
    *CryptoSys> putStrLn [C.chr 224]
    à

    Pour faciliter notre tâche, nous allons « remapper » nos
    caractères accentués et écraser les touches d'actions correspondant aux 32
    premiers codes ASCII. C'est évidemment maladroit dans la vraie vie mais cela nous permet ici de nous limiter à 7 bits pour faciliter notre tâche.

    Haskell
    chr 0  = 'à'
    chr 1  = 'â'
    chr 2  = 'é'
    chr 3  = 'è'
    chr 4  = 'ê'
    chr 5  = 'ë'
    chr 6  = 'î'
    chr 7  = 'ï'
    chr 8  = 'ô'
     
    ...
     
    ord  'à' = 0
    ord  'â' = 1
    ord  'é' = 2
    ord  'è' = 3
    ord  'ê' = 4
    ord  'ë' = 5
    ord  'î' = 6
    ord  'ï' = 7
    ord  'ô' = 8 
     
    ...

    Maintenant:

    Haskell
    *CryptoSys> ord 'à'
    0
    *CryptoSys> chr 0
    '\224'
    *CryptoSys> putStrLn [chr 0]
    à

    ce qui va faciliter notre travail : on se limitera à 7 bits mais avec les
    caractères qui nous intéressent.

  • Créez une fonction stringToBin qui convertit une chaîne de
    caractère en la liste des chaînes de 7 bits des caractères
    qui la composent. Par exemple:
    Haskell
    *CryptoSys> stringToBin "Aïe"
    [[1,0,0,0,0,0,1],[0,0,0,0,1,1,1],[1,1,0,0,1,0,1]]
      
  • Il faut maintenant s'occuper des permutations.

    Une permutation sera tout simplement une fonction de signature Int -> Int

    Haskell
    *CryptoSys> per 4
    2
    *CryptoSys> per 8
    *** Exception: Non_defini

    On définira ensuite une fonction permBits qui prend en argument une liste
    et renvoie la liste permutée:

    Haskell
    *CryptoSys> permBits per ['a'..'g']
    "cadbfeg"

    avec per désignant la permutation introduite dans l'exercice \vref{exo::ecb}.

  • Il ne reste plus qu'à créer une fonction ecb qui va crypter un
    message selon le cryptosystème ECB:
    Haskell
    *CryptoSys> ecb per "maman"
    ";);)>"
      

    On utilisera les fonctions précédentes et l'incontournable map.

    Comment déchiffrer ";);)>" connaissant la clé?

  • Un peu plus sportif: le CBC...

    On commencera par créer une fonction xor:

    Haskell
    *CryptoSys> xor 1 1
    0
    *CryptoSys> xor 1 0
    1

    On s'occupera ensuite de la fonction de déchiffrement qui est un peu plus simple
    à écrire. On utilisera à bon escient les fonctions zipWith, map et
    init.

    Haskell
    *CryptoSys> putStrLn (cbc_decrypt iper [1,0,1,0,1,0,1] "Papa")9!
    *CryptoSys> putStrLn (cbc_decrypt iper [1,0,1,0,1,0,1] "Père")
    MU_!

    Pour le chiffrement, on pourra utiliser foldl et reverse.

    Haskell
    *CryptoSys> putStrLn (cbc_crypt per [1,0,1,0,1,0,1] "Maman")
    PIù=e
    *CryptoSys> putStrLn (cbc_crypt per [1,0,1,0,1,0,1] "Mâ9!")
    Papa
  • Comment expliquer le phénomène suivant:
    Haskell
    *CryptoSys> putStrLn $ (cbc_crypt per [1,0,1,0,1,0,1] "aaaaaaaaaaaaaaaaaaaaaaaa")
    JÇzUJÇzUJÇzUJÇzUJÇzUJÇzU
      

Et voici le squelette du fichier que vous rendrez:

Haskell
{-# LANGUAGE OverloadedStrings #-}
 
module CryptoSys where
 
import qualified Data.Char as C
 
 
 
 
toBin :: Int -> [Int]
...
 
toDec :: [Int] -> Int 
...
 
stringToBin :: String -> [[Int]]
...
 
per :: Int -> Int
...
 
iper :: Int -> Int
...
 
permBits :: (Int -> Int) -> [a] -> [a]
...
               
ecb :: (Int -> Int) -> String -> String
...
  
xor :: Int -> Int -> Int
...
  
cbc_crypt :: (Int -> Int) -> [Int] -> String -> String
...
 
cbc_decrypt :: (Int -> Int) -> [Int] -> String -> String
...
 
 
chr 0  = 'à'
chr 1  = 'â'
chr 2  = 'é'
chr 3  = 'è'
chr 4  = 'ê'
chr 5  = 'ë'
chr 6  = 'î'
chr 7  = 'ï'
chr 8  = 'ô'
chr 9  = 'ö'
chr 10 = 'ù'
chr 11 = 'û'
chr 12 = 'ü'
chr 13 = 'ç'
chr 14 = 'æ'
chr 15 = 'œ'
chr 16 = 'À'
chr 17 = 'Â'
chr 18 = 'É'
chr 19 = 'È'
chr 20 = 'Ê'
chr 21 = 'Ë'
chr 22 = 'Î'
chr 23 = 'Ï'
chr 24 = 'Ô'
chr 25 = 'Ö'
chr 26 = 'Ù'
chr 27 = 'Û'
chr 28 = 'Ü'
chr 29 = 'Ç'
chr 30 = 'Æ'
chr 31 = 'Œ'
chr 127 = '€'
chr x = C.chr x
 
 
 
ord  'à' = 0
ord  'â' = 1
ord  'é' = 2
ord  'è' = 3
ord  'ê' = 4
ord  'ë' = 5
ord  'î' = 6
ord  'ï' = 7
ord  'ô' = 8 
ord  'ö' = 9 
ord  'ù' = 10
ord  'û' = 11
ord  'ü' = 12 
ord  'ç' = 13
ord  'æ' = 14
ord  'œ' = 15
ord  'À' = 16
ord  'Â' = 17
ord  'É' = 18
ord  'È' = 19
ord  'Ê' = 20
ord  'Ë' = 21
ord  'Î' = 22
ord  'Ï' = 23
ord  'Ô' = 24
ord  'Ö' = 25
ord  'Ù' = 26
ord  'Û' = 27
ord  'Ü' = 28
ord  'Ç' = 29
ord  'Æ' = 30
ord  'Œ' = 31
ord  '€' = 127
ord x = C.ord x

Et voici une proposition de solution:

Haskell
{-# LANGUAGE OverloadedStrings #-}
 
module CryptoSys where
 
import qualified Data.Char as C
 
septBits :: [Int] -> [Int]
septBits xs 
  |length xs == 7 = xs
  |otherwise = septBits (0:xs)
 
 
toBin :: Int -> [Int]
toBin x =
  let conv n 
        | n < 2 =  [n]
        | otherwise =  (conv (div n 2)) ++ [mod n 2] 
  in septBits (conv x)
 
 
toDec :: [Int] -> Int 
toDec [] = 0
toDec b = (last b) + 2 * ( toDec (init b))
 
stringToBin :: String -> [[Int]]
stringToBin s = reverse 
                (foldl (\ acc d -> (toBin (ord d)) : acc) [] s)
 
per :: Int -> Int
per 1 = 3
per 2 = 1
per 3 = 4
per 4 = 2
per 5 = 6
per 6 = 5
per 7 = 7
per _ = error "Non_defini"
 
 
iper :: Int -> Int
iper 3 = 1
iper 1 = 2
iper 4 = 3
iper 2 = 4
iper 6 = 5
iper 5 = 6
iper 7 = 7
iper _ = error "Non_defini"
 
 
permBits :: (Int -> Int) -> [a] -> [a]
permBits k p = [ p !! ((k i) - 1) |  i <- [1 .. t]]
  where t = length p
        
               
 
ecb :: (Int -> Int) -> String -> String
ecb k s =
  let ds = stringToBin s in
  let ps = map (permBits k) ds in
  map (\b -> chr (toDec b)) ps 
  
xor :: Int -> Int -> Int
xor x y = mod (x+y) 2
  
cbc_crypt :: (Int -> Int) -> [Int] -> String -> String
cbc_crypt k vi s = 
  let ds = stringToBin s in
  let ps = foldl 
           (\acc b ->  (permBits k (zipWith xor b (head acc))) : acc) [vi] ds in
  reverse (map (\b -> chr (toDec b)) (init ps)) 
  
 
cbc_decrypt :: (Int -> Int) -> [Int] -> String -> String
cbc_decrypt k vi s = 
  let ds = stringToBin s in
  let l1 = map (permBits k) ds in
  let l2 = vi : (init ds) in
  let ps = zipWith (zipWith xor) l1 l2 in
  map (\b -> chr (toDec b)) ps

courtesy of webmatter.de