Chiffre de Hill
Ce calculateur utilise le chiffre de Hill pour coder/décoder un bloc de texte
Suivant la définition de wikipedia, en cryptographie classique, le chiffre de Hill est un code de substitution polygraphique basé sur l’algèbre linéaire. Inventé par Lester S. Hill en 1929, c’était le premier code polygraphique pour lequel on pouvait l’appliquer (bien que rarement) pour travailler sur plus de trois symboles à la fois. L’explication du code en-dessous du calculateur nécessite quelques connaissances élémentaires concernant les matrices.
Chiffre de Hill
Comment fonctionne-t-il
Tout d’abord, les symboles de l’alphabet utilisé (l’alphabet a un ensemble de symboles, par exemple l’alphabet du calculateur ci-dessus inclus l’espace, la virgule et le point) sont encodés par des chiffres, par exemple, le numéro de l’ordre des symboles dans l’ensemble. Ensuite, nous choisissons une matrice de taille n x n qui sera la clef du code. Le texte est divisé en blocs de taille n et chaque bloc forme un vecteur de taille n. Chaque vecteur est multiplié par la matrice clef de n x n. Le résultat, un vecteur de taille n est le bloc de texte codé. L’arithmétique modulaire est utilisée, ce sont toutes les opérations (addition, soustraction et multiplication) qui sont réalisées dans l’ensemble des entiers, où le module est m – la longueur de l’alphabet. Ceci nous permet de forcer le résultat à appartenir au même alphabet.
First, symbols of used alphabet (alphabet as set of symbols, for example, alphabet in the above calculator includes space, comma and dot symbols) are encoded with digits, for example, symbol's order number in the set. Then we choose matrix of n x n size, which will be cipher's key. Text is divided into blocks of size n, and each block forms a vector of size n. Each vector is multiplied by key matrix of n x n. The result, vector of size n is block of encrypted text. Modular arithmetic is used, that is all operations (addition, subtraction, and multiplication) are done in the ring of integers, where modulus is m - the length of the alphabet. This allows us to force results to belong to the same alphabet.
La clef est la matrice, cependant, il est plus pratique d’utiliser une phrase clef, qui est transformée en une représentation chiffrée puis dans une matrice. Evidemment, pour créer une matrice clef de n x n, la longueur de la phrase doit être le carré d’un entier, soit 4, 9, 16, etc..
Des restrictions supplémentaires sont imposées à la clef dans le besoin de décrypter le texte codé :)
Et pour que cela ait lieu, nous avons besoin d’avoir un inverse modulaire de la matrice clef dans - l’ensemble des entiers modulo m.
En effet, si le vecteur source B est multiplié par la matrice A pour obtenir le vecteur C, alors pour restaurer le vecteur B à partir du C (décrypter le texte), il faut le multiplier par l’inverse modulaire de la matrice.
C’est pourquoi il y a les restrictions suivantes :
Le déterminant de la matrice ne doit pas être égal à zéro, et le déterminant de la matrice doit avoir un inverse multiplicatif modulaire.
Ceci est imposé par la formule
.
où les opérations de divisions sont substituées par des opérations de multiplications par inverse multiplicatif modulaire.
Afin d’avoir un inverse multiplicatif modulaire, le déterminant et le modulo (longueur de l’alphabet) doivent être des entiers premier entre eux, se référer à Inverse modulaire. Pour accroître la probabilité que cela soit le cas, l’alphabet est augmenté afin que sa longueur soit un nombre premier. C’est pourquoi l’alphabet du calculateur ci-dessus est augmenté avec l’espace, la virgule et le point pour atteindre 29 symboles, 29 est un nombre premier.
Toutes les phrases clefs ne peuvent pas être une clef, cependant il y en a bien assez.
commentaires