Tout le monde (qui s'int=E9resse =E0 la cryptographie) connait le
chiffrement de Hill qui utilise des matrices (l'alg=E8bre lin=E9aire de
mani=E8re g=E9n=E9rale) pour chiffrer des blocs de donn=E9es (des
caract=E8res par ex.)
(voir http://www.apprendre-en-ligne.net/crypto/menu/index.html pour
ceux qui ne connaissent pas le chiffre de hill)
Pour fonctionner, il est n=E9cessaire d'obtenir une matrice inversible
modulo 26 (ou 256 si l'espace des caract=E8res =E0 coder est sur 8 bits).
D'o=F9 ma premi=E8re question : existe-t-il un algorithme relativement
performant pour g=E9n=E9rer une telle matrice (de mani=E8re
pseudo-al=E9atoire bien s=FBr) ? un algo plus performant que de choisir
des co=E9ficients al=E9atoirement puis de tester si le d=E9terminant est
inversible modulo 26 (ou 256) et si ce n'est pas le cas, refaire un
tirage (ou incr=E9menter les co=E9f les uns apr=E8s les autres)...
Ma deuxi=E8me question est un peu diff=E9rente : si j'ai une matrice non
inversible, et que je code un message avec le chiffre de Hill et cette
matrice, est-ce que j'obtiens un hachage cryptographique ? C'est =E0
dire que l'op=E9ration inverse n'est pas possible, puisque la matrice
inverse n'existe pas... Bien entendu, cela ne comprime pas le message
(donc peu utile comme algorithme de signature) mais cela "pourrait"
servir pour g=E9rer des mots de passe. Bien s=FBr, pour =E9viter une
attaque par force brute, il faudrait g=E9n=E9rer une matrice de taille
cons=E9quente afin que le nombre de clefs (le nombre de combinaisons
possibles pour les co=E9ficients) soit suffisament grand.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
pornin
According to Arnaud W. :
Pour fonctionner, il est nécessaire d'obtenir une matrice inversible modulo 26 (ou 256 si l'espace des caractères à coder est sur 8 bits). D'où ma première question : existe-t-il un algorithme relativement performant pour générer une telle matrice (de manière pseudo-aléatoire bien sûr) ? un algo plus performant que de choisir des coéficients aléatoirement puis de tester si le déterminant est inversible modulo 26 (ou 256) et si ce n'est pas le cas, refaire un tirage (ou incrémenter les coéf les uns après les autres)...
La probabilité d'obtenir une matrice inversible avec des coefficients aléatoires est assez haute (pas loin de 50% à chaque essai, qu'on le fasse modulo 26 ou modulo 256), donc cette méthode de sélection _est_ performante... Le point le plus lent est la vérification de l'inversibilité de la matrice, ce qui se fait en O(n³) pour une matrice n*n, ce qui n'est pas la mer à boire.
Ceci étant, il faut bien voir que cette méthode de chiffrement n'est pas "sûre" : la combinaison est complètement linéaire. Dans le cas d'une matrice 2*2, il suffit de connaître deux paquets clairs (donc quatre caractères d'entrée) et les chiffrés correspondants pour reconstruire la matrice, avec un banal pivot de Gauss. La linéarité transporte également très bien les propriétés linéaires du texte clair, donc ça ouvre la porte à toutes les attaques sur texte chiffré si l'information connue de l'attaquant sur le texte clair est du type "c'est un texte en français" ou encore "ce sont des octets mais leur huitième bit vaut 0 (texte ASCII)". Plus généralement, si on groupe les caractères par blocs de n, on utilise une matrice n*n, on a donc n² coefficients et la sécurité passe par la fenêtre dès qu'on essaye de chiffrer plus de n² caractères. En bref, on ferait mieux d'utiliser un One-Time Pad, qui fournit le même niveau de sécurité mais est beaucoup plus simple à implémenter et à utiliser...
Ma deuxième question est un peu différente : si j'ai une matrice non inversible, et que je code un message avec le chiffre de Hill et cette matrice, est-ce que j'obtiens un hachage cryptographique ?
De fait non, puisque ça reste linéaire et donc n'offre pas du tout les garanties de sécurité qu'on attend d'une fonction de hachage.
Par ailleurs, une fonction de hachage est censée avoir une sortie de taille fixe mais accepter des entrées de taille arbitraire. Autrement dit, fournir (par exemple) 256 bits de sortie, et pas un de plus, même si je fais rentrer 200 giga-octets de données.
--Thomas Pornin
According to Arnaud W. <ab6y5keot0gpy3h@jetable.net>:
Pour fonctionner, il est nécessaire d'obtenir une matrice inversible
modulo 26 (ou 256 si l'espace des caractères à coder est sur 8 bits).
D'où ma première question : existe-t-il un algorithme relativement
performant pour générer une telle matrice (de manière pseudo-aléatoire
bien sûr) ? un algo plus performant que de choisir des coéficients
aléatoirement puis de tester si le déterminant est inversible
modulo 26 (ou 256) et si ce n'est pas le cas, refaire un tirage (ou
incrémenter les coéf les uns après les autres)...
La probabilité d'obtenir une matrice inversible avec des coefficients
aléatoires est assez haute (pas loin de 50% à chaque essai, qu'on
le fasse modulo 26 ou modulo 256), donc cette méthode de sélection
_est_ performante... Le point le plus lent est la vérification de
l'inversibilité de la matrice, ce qui se fait en O(n³) pour une matrice
n*n, ce qui n'est pas la mer à boire.
Ceci étant, il faut bien voir que cette méthode de chiffrement n'est pas
"sûre" : la combinaison est complètement linéaire. Dans le cas d'une
matrice 2*2, il suffit de connaître deux paquets clairs (donc quatre
caractères d'entrée) et les chiffrés correspondants pour reconstruire la
matrice, avec un banal pivot de Gauss. La linéarité transporte également
très bien les propriétés linéaires du texte clair, donc ça ouvre la
porte à toutes les attaques sur texte chiffré si l'information connue de
l'attaquant sur le texte clair est du type "c'est un texte en français"
ou encore "ce sont des octets mais leur huitième bit vaut 0 (texte
ASCII)". Plus généralement, si on groupe les caractères par blocs de n,
on utilise une matrice n*n, on a donc n² coefficients et la sécurité
passe par la fenêtre dès qu'on essaye de chiffrer plus de n² caractères.
En bref, on ferait mieux d'utiliser un One-Time Pad, qui fournit le
même niveau de sécurité mais est beaucoup plus simple à implémenter et
à utiliser...
Ma deuxième question est un peu différente : si j'ai une matrice non
inversible, et que je code un message avec le chiffre de Hill et cette
matrice, est-ce que j'obtiens un hachage cryptographique ?
De fait non, puisque ça reste linéaire et donc n'offre pas du tout les
garanties de sécurité qu'on attend d'une fonction de hachage.
Par ailleurs, une fonction de hachage est censée avoir une sortie de
taille fixe mais accepter des entrées de taille arbitraire. Autrement
dit, fournir (par exemple) 256 bits de sortie, et pas un de plus, même
si je fais rentrer 200 giga-octets de données.
Pour fonctionner, il est nécessaire d'obtenir une matrice inversible modulo 26 (ou 256 si l'espace des caractères à coder est sur 8 bits). D'où ma première question : existe-t-il un algorithme relativement performant pour générer une telle matrice (de manière pseudo-aléatoire bien sûr) ? un algo plus performant que de choisir des coéficients aléatoirement puis de tester si le déterminant est inversible modulo 26 (ou 256) et si ce n'est pas le cas, refaire un tirage (ou incrémenter les coéf les uns après les autres)...
La probabilité d'obtenir une matrice inversible avec des coefficients aléatoires est assez haute (pas loin de 50% à chaque essai, qu'on le fasse modulo 26 ou modulo 256), donc cette méthode de sélection _est_ performante... Le point le plus lent est la vérification de l'inversibilité de la matrice, ce qui se fait en O(n³) pour une matrice n*n, ce qui n'est pas la mer à boire.
Ceci étant, il faut bien voir que cette méthode de chiffrement n'est pas "sûre" : la combinaison est complètement linéaire. Dans le cas d'une matrice 2*2, il suffit de connaître deux paquets clairs (donc quatre caractères d'entrée) et les chiffrés correspondants pour reconstruire la matrice, avec un banal pivot de Gauss. La linéarité transporte également très bien les propriétés linéaires du texte clair, donc ça ouvre la porte à toutes les attaques sur texte chiffré si l'information connue de l'attaquant sur le texte clair est du type "c'est un texte en français" ou encore "ce sont des octets mais leur huitième bit vaut 0 (texte ASCII)". Plus généralement, si on groupe les caractères par blocs de n, on utilise une matrice n*n, on a donc n² coefficients et la sécurité passe par la fenêtre dès qu'on essaye de chiffrer plus de n² caractères. En bref, on ferait mieux d'utiliser un One-Time Pad, qui fournit le même niveau de sécurité mais est beaucoup plus simple à implémenter et à utiliser...
Ma deuxième question est un peu différente : si j'ai une matrice non inversible, et que je code un message avec le chiffre de Hill et cette matrice, est-ce que j'obtiens un hachage cryptographique ?
De fait non, puisque ça reste linéaire et donc n'offre pas du tout les garanties de sécurité qu'on attend d'une fonction de hachage.
Par ailleurs, une fonction de hachage est censée avoir une sortie de taille fixe mais accepter des entrées de taille arbitraire. Autrement dit, fournir (par exemple) 256 bits de sortie, et pas un de plus, même si je fais rentrer 200 giga-octets de données.
--Thomas Pornin
Arnaud W.
1) Merci pour la réponse sur la génération de matrice inversible. La méthode naive est donc suffisament performante. 2) Concernant la sécurité du chiffrement de Hill, j'avais bien conscience que ce n'est pas le graal (et même loin de là), j'implémente des algorithmes historiques dans un petit soft (en Java) sans prétention. 3) Concernant la non inversibilité, j'aimerais e surtout savoir, si je donne un message chiffré (avec des informations sur la langue utilisée et la valeur de la clef-matrice par ex) avec une matrice non inversible (suffisament grande), s'il y a une méthode pour retrouver le texte clair plus performante que d'essayer toutes les valeurs possibles pour le texte clair (ce qui est, à priori, un problème complexe si la taille de la clef et le texte clair sont grands).
Je pars de l'idée que si la matrice est non inversible, on ne peut trouver les solutions du système d'équations linéraires formés à partir du texte chiffré et de la clef (fournie), n'est ce pas ? D'ailleurs, peut être existe-t-il une technique de construction de la matrice non inversible pour la rendre plus "résistante" ?
Arnaud W.
http://awr.free.fr
1) Merci pour la réponse sur la génération de matrice inversible. La
méthode naive est donc suffisament performante.
2) Concernant la sécurité du chiffrement de Hill, j'avais bien
conscience que ce n'est pas le graal (et même loin de là),
j'implémente des algorithmes historiques dans un petit soft (en Java)
sans prétention.
3) Concernant la non inversibilité, j'aimerais e surtout savoir, si je
donne un message chiffré (avec des informations sur la langue
utilisée et la valeur de la clef-matrice par ex) avec une matrice non
inversible (suffisament grande), s'il y a une méthode pour retrouver
le texte clair plus performante que d'essayer toutes les valeurs
possibles pour le texte clair (ce qui est, à priori, un problème
complexe si la taille de la clef et le texte clair sont grands).
Je pars de l'idée que si la matrice est non inversible, on ne peut
trouver les solutions du système d'équations linéraires formés à
partir du texte chiffré et de la clef (fournie), n'est ce pas ?
D'ailleurs, peut être existe-t-il une technique de construction de la
matrice non inversible pour la rendre plus "résistante" ?
1) Merci pour la réponse sur la génération de matrice inversible. La méthode naive est donc suffisament performante. 2) Concernant la sécurité du chiffrement de Hill, j'avais bien conscience que ce n'est pas le graal (et même loin de là), j'implémente des algorithmes historiques dans un petit soft (en Java) sans prétention. 3) Concernant la non inversibilité, j'aimerais e surtout savoir, si je donne un message chiffré (avec des informations sur la langue utilisée et la valeur de la clef-matrice par ex) avec une matrice non inversible (suffisament grande), s'il y a une méthode pour retrouver le texte clair plus performante que d'essayer toutes les valeurs possibles pour le texte clair (ce qui est, à priori, un problème complexe si la taille de la clef et le texte clair sont grands).
Je pars de l'idée que si la matrice est non inversible, on ne peut trouver les solutions du système d'équations linéraires formés à partir du texte chiffré et de la clef (fournie), n'est ce pas ? D'ailleurs, peut être existe-t-il une technique de construction de la matrice non inversible pour la rendre plus "résistante" ?
Arnaud W.
http://awr.free.fr
pornin
According to Arnaud W. :
Je pars de l'idée que si la matrice est non inversible, on ne peut trouver les solutions du système d'équations linéraires formés à partir du texte chiffré et de la clef (fournie), n'est ce pas ?
Si, on peut trouver les solutions. Le problème est justement dans ce "les". Quand la matrice est inversible, la solution est unique. Quand elle n'est pas inversible, la solution n'est pas unique : l'espace des solutions est un sous-espace affine dont le degré dépend du rang de la matrice. Par pivot de Gauss (i.e. résolution "à la main"), on peut arriver à extraire une base de ce sous-espace, qui permet d'énumérer toutes les solutions de façon optimale.
Ce n'est pas de la sécurité : ça veut juste dire qu'avec une matrice non inversible, plusieurs messages clairs donnent le même chiffré. L'opération de déchiffrement est alors impossible dans toute sa généralité, qu'on connaisse la matrice ou pas : de l'information a été simplement détruite. C'est la même chose que de dire "on va chiffrer en effaçant un caractère sur trois" (la matrice rajoute une transposition jusque vers un sous-espace vectoriel mais tout cela est linéaire et rapidement accessible à l'attaquant aussi).
Tout cela reste distinct d'une fonction de hachage, car dans une fonction de hachage, la taille de la sortie doit être fixe, indépendamment de celle de l'entrée.
--Thomas Pornin
According to Arnaud W. <ab6y5keot0gpy3h@jetable.net>:
Je pars de l'idée que si la matrice est non inversible, on ne peut
trouver les solutions du système d'équations linéraires formés à
partir du texte chiffré et de la clef (fournie), n'est ce pas ?
Si, on peut trouver les solutions. Le problème est justement dans ce
"les". Quand la matrice est inversible, la solution est unique. Quand
elle n'est pas inversible, la solution n'est pas unique : l'espace des
solutions est un sous-espace affine dont le degré dépend du rang de la
matrice. Par pivot de Gauss (i.e. résolution "à la main"), on peut
arriver à extraire une base de ce sous-espace, qui permet d'énumérer
toutes les solutions de façon optimale.
Ce n'est pas de la sécurité : ça veut juste dire qu'avec une matrice
non inversible, plusieurs messages clairs donnent le même chiffré.
L'opération de déchiffrement est alors impossible dans toute sa
généralité, qu'on connaisse la matrice ou pas : de l'information a été
simplement détruite. C'est la même chose que de dire "on va chiffrer
en effaçant un caractère sur trois" (la matrice rajoute une transposition
jusque vers un sous-espace vectoriel mais tout cela est linéaire et
rapidement accessible à l'attaquant aussi).
Tout cela reste distinct d'une fonction de hachage, car dans
une fonction de hachage, la taille de la sortie doit être fixe,
indépendamment de celle de l'entrée.
Je pars de l'idée que si la matrice est non inversible, on ne peut trouver les solutions du système d'équations linéraires formés à partir du texte chiffré et de la clef (fournie), n'est ce pas ?
Si, on peut trouver les solutions. Le problème est justement dans ce "les". Quand la matrice est inversible, la solution est unique. Quand elle n'est pas inversible, la solution n'est pas unique : l'espace des solutions est un sous-espace affine dont le degré dépend du rang de la matrice. Par pivot de Gauss (i.e. résolution "à la main"), on peut arriver à extraire une base de ce sous-espace, qui permet d'énumérer toutes les solutions de façon optimale.
Ce n'est pas de la sécurité : ça veut juste dire qu'avec une matrice non inversible, plusieurs messages clairs donnent le même chiffré. L'opération de déchiffrement est alors impossible dans toute sa généralité, qu'on connaisse la matrice ou pas : de l'information a été simplement détruite. C'est la même chose que de dire "on va chiffrer en effaçant un caractère sur trois" (la matrice rajoute une transposition jusque vers un sous-espace vectoriel mais tout cela est linéaire et rapidement accessible à l'attaquant aussi).
Tout cela reste distinct d'une fonction de hachage, car dans une fonction de hachage, la taille de la sortie doit être fixe, indépendamment de celle de l'entrée.
