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:
Haskellimport 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: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.Haskellchr 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.Pour le chiffrement, on pourra utiliser foldl et reverse.
- 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:
{-# 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:
{-# 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