Chiffrement de Hill en Haskell

Pour éviter que vous ne sombriez dans l'ennui d'ici janvier, voici un petit travail à effectuer pour la fin de la semaine 2 de l'année 2014.

Il s'agit de fabriquer un petit outil cryptant des chaînes de caractères en utilisant le chiffrement de Hill. Renseignez-vous sur cette méthode mise au point dans les années 1920.

Nous travaillerons sur les 95 caractères affichables du code ascii 7 bits.

Vous pourrez utiliser le fichier ci-dessous comme squelette de départ.

Vous devrez par exemple obtenir :

Haskell
*Matrix> codeHill "Rendez-vous 02:34 pm Pont de Remagen avec les microfilms" cleHill
"+=rQmQEoM{hqL/0#Ksy-j1kA?Nh7}<6XJigQ{?P6D^Kv=Y5};{ Td[zXp"

avec comme clé [[12 , 22 , 1] , [2 , 24 , 1] , [12 , 7 , 3]].

Cela doit marcher dans les deux sens :

Haskell
*Matrix> ???? "+=rQmQEoM{hqL/0#Ksy-j1kA?Nh7}<6XJigQ{?P6D^Kv=Y5};{ Td[zXp" ???? 
"Rendez-vous 02:34 pm Pont de Remagen avec les microfilms "

Mystérieux n'est-ce pas ? Cela donne un peu de piquant à la chose. Bonne enquête...

Haskell
--
--                       Anneau des classes modulo un entier
--
 
data Classe = Integer :% Integer 
 
 
representant :: Classe   -> Integer
representant    (a :% n) =  a
 
modulo :: Classe   -> Integer
modulo    (a :% n) =  n
 
 
 
-- cas d'égalité
instance Eq Classe where
  (a:%n) == (b:%m) = (mod a n == mod b m) && (n == m)
 
-- affichage sous la forme a%n
instance Show Classe where
  show (a:%n) = (show (mod a n)) ++ "%" ++ (show n)
 
-- opérateur infixe : a%n = a modulo n
infixr 9 %%  
(%%) :: Integer -> Integer -> Classe
(%%) a n =  (mod a n) :% n
 
 
-- somme induite
plusMod :: Integer -> Classe -> Classe  -> Classe
plusMod    n (a :% p)  (b :% m) = if (n == p) && (n == m) then
                               (a + b) %% n
                             else 
                               error "Classes incompatibles" 
   
-- produit induit
mulMod :: Integer -> Classe -> Classe  -> Classe
mulMod  n  (a :% p)  (b :% m) = if (n == p) && (n == m)  then
                               (a * b) %% n
                             else
                               error "Classes incompatibles" 
                               
                               
-- euclide étendu
euclide :: Integer -> Integer -> (Integer,Integer,Integer)
euclide a b = euc 1 0 a 0 a b 
  where
    euc u v r u' v' r' 
      |r' == 0 = (u,v,r)
      |otherwise = euc u' v' r' (u - q * u') (v - q * v') (r - q * r') where q = quot r r'
 
-- inverse modulaire
invMod :: Classe -> Classe
invMod a = 
  let (u,v,r) = euclide (representant a) (modulo a) in
  if r == 1 then (u %% (modulo a))
  else error "Classe non inversible"
 
--
--         Z / 95Z
--
 
 
 
data Z95 = Z95 Classe deriving (Eq)
 
z95 n = Z95 (n :% 95)
    
 
instance Num Z95 where
  (+) (Z95 a) (Z95 b) = ????
  (*) (Z95 a) (Z95 b) = ????
  fromInteger n = ????
  negate (Z95 x) = ????
  
                                                        
instance Fractional Z95 where
  (/) c1 c2 = ????
 
 
-- Chiffrement de Hill 
 
 
-- Un exemple de clé sous forme d'une liste de listes d'entiers
cleHill :: [[Integer]]
cleHill =  [[12 , 22 , 1] , [2 , 24 , 1] , [12 , 7 , 3]]
 
-- La clé comme matrice à coefficients dans Z/95Z
matHill :: [[Integer]] -> Matrice Z95
matHill   cle = ?????
 
-- Inverse de la clé comme matrice à coefficients dans Z/95Z
dematHill :: [[Integer]] -> Matrice Z95
dematHill cle = ?????
 
-- Inverse de la clé sous forme d'une double liste d'entiers
invCle :: [[Integer]] -> [[Integer]]
invCle cle = ?????
 
{- Exemple d'utilisation :
*Matrix> matHill cleHill
 |    12%95    22%95     1%95  | 
 |     2%95    24%95     1%95  | 
 |    12%95     7%95     3%95  | 
  
*Matrix> dematHill cleHill
 |    75%95    62%95    81%95  | 
 |    42%95    73%95    25%95  | 
 |    77%95    25%95    93%95  | 
  
*Matrix> invCle cleHill
[[75,62,81],[42,73,25],[77,25,93]]
-}
 
-- Code ascii translaté dans [|0,94|]
ordHill :: Char -> Integer
ordHill c = ?????
 
-- Caractère correspondant au code ascii translaté
chrHill :: Integer -> Char
chrHill n = ?????
 
-- Liste des codes translatés correspondant à une chaîne donnée
codeMessage :: String -> [Integer]
codeMessage m = ????
 
-- Chaîne correspondant à une liste de codes translatés
decodeMessage :: [Integer] -> String
decodeMessage liste = ????
 
-- On découpe une liste en liste de listes de listes de longueur n
-- parPaquets 3 [1..10]
-- [[[1,2,3]],[[4,5,6]],[[7,8,9]],[[10,0,0]]]
parPaquets :: Int -> [Integer] -> [[[Integer]]]
parPaquets n liste 
     ?????
 
-- liste de listes extraite d'une matrice
listeMat :: Matrice t -> [[t]]
listeMat (Mat m) = ????
 
-- Le message crypté à partir d'un message clair et d'une clé sous forme de liste de listes d'entiers
codeHill :: String -> [[Integer]] -> String
codeHill m cle = 
   ?????

courtesy of webmatter.de