Introduction :

Dans un contexte où les échanges d'information dématérialisées se développent, il est indispensable de pouvoir bénéficier de systèmes sécurisés pour protéger les données a caractère personnel ou confidentiel. Il est donc, nécessaire d'avoir accès à des outils permettant une meilleure protection contre les intrusions arbitraires de la confidentialité des données. Le chiffrement est souvent le seul moyen efficace pour répondre à ces exigences. La cryptographie est l'ensemble des processus de verrouillage visant à protéger l'accès à certaines données afin de les rendre incompréhensible aux personnes non autorisées. Les technologies cryptographiques sont ainsi reconnues comme étant des outils essentiels de sécurité des données et de la confiance dans les communications et le commerce électroniques. Le chiffre de Hill que nous allons étudier afin de l'implémenter pour sécuriser les données a été publié par Lester S. Hill en 1929. C'est un chiffre polygraphique, c'est-à-dire qu'on ne (dé) chiffre pas les lettres les unes après les autres, mais par paquets. Nous étudierons la version bigraphique, c'est-à-dire que nous grouperons les lettres deux par deux, mais on peut imaginer des paquets plus grands. C'est une méthode de chiffrement qui utilise des matrices carrées. Cet algorithme est, plus au moins, performant pour une petite entreprise qui veux se doter d'un moyen software sécurisant ses données et qui n'est pas cher.

Notion sur les Matrices

En mathématiques, les matrices servent à interpréter en termes calculatoires et donc opérationnels les résultats théoriques de l'algèbre linéaire et même de l'algèbre bilinéaire. Toutes les disciplines étudiant des phénomènes linéaires utilisent les matrices. Quant aux phénomènes non linéaires, on en donne souvent des approximations linéaires comme c'est le cas en optique géométrique avec les approximations de Gauss.

Matrice

Méthodes d'inversion

Avant de décrire les méthodes usuelles d'inversion, notons qu'en pratique, il n'est pas nécessaire de calculer l'inverse d'une matrice pour résoudre un système d'équations linéaires. Il est toutefois nécessaire que la matrice considérée soit inversible. Des méthodes de décomposition comme la décomposition LU sont beaucoup plus rapide que l'inversion.

Méthode des cofacteurs

L'inverse d'une matrice A s'écrit sous une forme très simple à l'aide de la matrice complémentaire t comA Où detA est le déterminant de A, comA est la comatrice de A et t A est la matrice transposée de A. Cette écriture permet un calcul aisé de l'inverse d'une matrice de petite dimension. Pour des matrices de plus grandes dimensions, cette méthode essentiellement récursive devient inefficace.

Inversion des matrices 2 x 2

L'équation des cofacteurs ci-dessus permet de calculer l'inverse des matrices de dimensions 2x2 :

det A = ad-bc ≠ 0

Chiffre de Hill

Lester Hill, mathématicien cryptographe (1891-1961) publie en 1929 dans la revue American Mathematical Monthly un article intitulé Cryptography in an algebraic alphabet, où il détaille un nouveau type d'algorithme de chiffrement. Son idée n'est plus de coder lettres par lettres, mais de coder simultanément des groupes de m lettres! Bien sûr, plus m est grand, plus les analyses statistiques deviennent difficiles!. Le chiffre de Hill est une méthode de chiffrement qui utilise des matrices carrées. On désigne par 2-chiffre de Hill, le chiffre obtenu en codant les lettres par blocs de deux, par 3chiffre de Hill celui obtenu en codant les lettres par blocs de trois, et ainsi de suite.

Chiffrement

Dans une première phase, chaque lettre du texte à chiffrer est remplacée par une valeur numérique, celle de son rang dans l'alphabet, c'est-à-dire, nous remplaçons chaque lettre par son ordre dans l'alphabet : A devient 1, B devient 2,..., Z devient 26. On groupe les nombres ainsi obtenus par m (prenons par exemple m=2 La valeur 0 est attribuée à la lettre Z afin de travailler modulo 26. Cependant, d'autres auteurs posent "A"=0, "B"=1, ..., "Z"=25. Les deux conventions se défendent. L'essentiel est que les protagonistes se mettent d'accord avant d'échanger des messages. On pourrait même imaginer de prendre un alphabet désordonné, par exemple "A"=15, "B"=6, etc., ce qui constituerait un surchiffrement.

Exemples de chiffrement

1) On souhaite coder le message "je vous aime" en prenant comme clef de cryptage la matrice P 1 = . Après avoir remplacé les lettres par leur rang dans l'alphabet (a=1, b=2, etc.), elle obtiendra: Elle fera de même avec les 3 e et 4 e lettres, 5 e et 6 e , etc. Elle obtiendra finalement: 2) Soit la matriceP 2 = , si on veut crypter le message "Rendez-vous ce soir", on obtient le cryptogramme : "UDZBI WLOSR VSSAY STAIE AM"

Déchiffrement :

Pour déchiffrer, le principe est le même que pour le chiffrement: on prend les lettres deux par deux, puis on les multiplie par une matrice.

Cette matrice doit être l'inverse de matrice de chiffrement (modulo 26). Ordinairement l'inverse de la matrice est:

Mais que cela signifie-t-il dans le contexte Z 26 ? Reprenons notre exemple.

Exemple de déchiffrement

Pour déchiffrer le message qu'on a envoyé par la clef P 1 doit calculer :

Comme pgdc(43,26)=1, (43) -1 existe dans Z 26 et (43) -1 égale 23. Le récepteur a donc maintenant la matrice de déchiffrement:

Il prend donc la matrice pour déchiffrer le message "FGXGE DSPGV". Après avoir remplacé les lettres par leur rang dans l'alphabet (A=1, B=2, etc.), il obtiendra: Il fera de même avec les 3 e et 4 e lettres, 5 e et 6 e , etc. Il obtiendra finalement: Les images cryptées ont la même taille que l'image claire.

Lettres chiffrées F G X G E D S P G V Rangs chiffrés (C k )6

Attaque à texte clair connu : chiffrement de Hill

Lorsque l'on cherche à déterminer la clé de chiffrement d'un adversaire, on peut se situer à plusieurs niveaux d'information. On peut n'avoir à sa disposition que le message chiffré. Parfois, et cela apporte beaucoup d'informations, on dispose à la fois du message chiffré et de sa traduction en clair, ou au moins une partie de celle-ci. Cela n'est pas si saugrenu : bien des messages protocolaires (et dans l'armée, les protocoles...) comportent le même début ou la même fin, et c'est ainsi par exemple que Türing a procédé pour la machine Enigma. C'est ce que l'on appelle l'attaque à texte clair connu!

Voyons un exemple à partir du chiffrement de Hill (cette méthode s'applique à tout algorithme fonctionnant à partir de combinaisons linéaires). On suppose qu'on a le texte codé suivant : COR ZZETMDW...., qui correspond au début de MON GENERAL... Un espion dans les bases ennemies nous a permis de savoir que nos adversaires utilisent le chiffre de Hill, avec une longueur de clé égale à 2. On note A la matrice 2×2 de chiffrement à coefficients dans Z|26Z. La première paire CO s'obtient en appliquant la matrice A à partir de la paire MO, la seconde paire RZ s'obtient en appliquant la matrice A à partir de la paire NG. On obtient l'équation matricielle:

Conclusion

On peut classer les algorithmes cryptographiques en deux grandes familles. Certains opèrent sur le message en clairs par groupes de bits (blocs). Et d'autres opèrent sur le message en clair un bit à la fois (continue).

Les algorithmes de bloc sont souvent coûteux en termes de temps de calcul, et ne permettent que malaisément le chiffrage d'information de type synchrone (parole, images animées, …). Le chiffre de Hill fait partie de cette catégorie d'algorithme en bloc.

Pour rendre le chiffre de Hill plus difficile à casser, on peut penser aux améliorations suivantes:



Transposer les lettres avant de les chiffrer.



Modifier les nombres associés aux lettres. Par exemple, au lieu de dire "A"=1, "B"=2, etc., on pourrait dire "A"=12, "B"=5, etc. Cela revient en fait à surchiffrer le chiffre de Hill avec un alphabet désordonné.



Agrandir la taille de la matrice de chiffrement. On peut utiliser des matrices 3x3, 4x4, 5x5, etc. La seule limitation est d'ordre pratique: plus les matrices sont grandes, plus le temps de calcul est élevé, et plus le risque d'erreur augmente.