Bonjour,
En supposant que dans un cas particulier on calcule le CRC32 pour des
buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet
pour ces buffers est-il une fonction bijective ?
Merci pour la r=E9ponse ! Je cherche une explication math=E9matique de
pr=E9f=E9rence...
Je précise la question... peut-on obtenir une valeur donnée du CRC32 avec 2 valeurs d'entrées différentes définies sur 4 octets ?
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
-- shen --8323328-412637536-1128955861=:17448--
Xavier Roche
shen wrote:
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits) Pour CRC32, j'en doute, et il suffit de trouver une collision pour le prouver mathématiquement.
shen wrote:
Une fonction de hachage ne peut pas être bijective ou bien on appelle
cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits)
Pour CRC32, j'en doute, et il suffit de trouver une collision pour le
prouver mathématiquement.
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits) Pour CRC32, j'en doute, et il suffit de trouver une collision pour le prouver mathématiquement.
Adrien Huvier
Xavier Roche wrote in news:die0eh$s17$:
shen wrote:
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits) Pour CRC32, j'en doute, et il suffit de trouver une collision pour le prouver mathématiquement.
Le CRC32 d'une valeur 32 bits ne serait-il pas toujours la valeur elle- même ? C'est le reste de la division d'un polynôme de degré 31 (dont les coefficients sont les différents bits de la valeur en question) par un polynôme fixé de degré 32, et si mes souvenirs sont corrects, le quotient sera nul et le reste sera le polynôme à diviser (+constante éventuellement).
-- Adrien
Xavier Roche <xroche@free.fr.NOSPAM.invalid> wrote in
news:die0eh$s17$1@news.httrack.net:
shen wrote:
Une fonction de hachage ne peut pas être bijective ou bien on
appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32
bits) Pour CRC32, j'en doute, et il suffit de trouver une
collision pour le prouver mathématiquement.
Le CRC32 d'une valeur 32 bits ne serait-il pas toujours la valeur elle-
même ? C'est le reste de la division d'un polynôme de degré 31 (dont
les coefficients sont les différents bits de la valeur en question) par
un polynôme fixé de degré 32, et si mes souvenirs sont corrects, le
quotient sera nul et le reste sera le polynôme à diviser (+constante
éventuellement).
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits) Pour CRC32, j'en doute, et il suffit de trouver une collision pour le prouver mathématiquement.
Le CRC32 d'une valeur 32 bits ne serait-il pas toujours la valeur elle- même ? C'est le reste de la division d'un polynôme de degré 31 (dont les coefficients sont les différents bits de la valeur en question) par un polynôme fixé de degré 32, et si mes souvenirs sont corrects, le quotient sera nul et le reste sera le polynôme à diviser (+constante éventuellement).
-- Adrien
Clément
shen wrote:
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits) Pour CRC32, j'en doute, et il suffit de trouver une collision pour le prouver mathématiquement.
Bonjour,
comme par exemple :
"UPDATE payroll SET wage = 10.75 WHERE empno = 11" et "UPDATE payroll SET wage = 1075 WHERE empno = 18; -- pN#j,"
qui ont tous les deux 0x954f8133 comme CRC. (source : http://www.networksecurityarchive.org/html/Security-Basics/2004-10/msg00189.html)
Ainsi, CRC32 n'est pas bijective.
Clément.
shen wrote:
Une fonction de hachage ne peut pas être bijective ou bien on appelle
cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits)
Pour CRC32, j'en doute, et il suffit de trouver une collision pour le
prouver mathématiquement.
Bonjour,
comme par exemple :
"UPDATE payroll SET wage = 10.75 WHERE empno = 11"
et
"UPDATE payroll SET wage = 1075 WHERE empno = 18; -- pN#j,"
qui ont tous les deux 0x954f8133 comme CRC. (source :
http://www.networksecurityarchive.org/html/Security-Basics/2004-10/msg00189.html)
Une fonction de hachage ne peut pas être bijective ou bien on appelle cela plus communément une fonction de compression.
Si, elle peut l'être, sur un ensemble de même cardinal (ici, 32 bits) Pour CRC32, j'en doute, et il suffit de trouver une collision pour le prouver mathématiquement.
Bonjour,
comme par exemple :
"UPDATE payroll SET wage = 10.75 WHERE empno = 11" et "UPDATE payroll SET wage = 1075 WHERE empno = 18; -- pN#j,"
qui ont tous les deux 0x954f8133 comme CRC. (source : http://www.networksecurityarchive.org/html/Security-Basics/2004-10/msg00189.html)
Ainsi, CRC32 n'est pas bijective.
Clément.
Xavier Roche
Clément wrote:
comme par exemple :
Non. On vous parle d'un ensemble de départ de 32 bits.
Clément wrote:
comme par exemple :
Non. On vous parle d'un ensemble de départ de 32 bits.
Non. On vous parle d'un ensemble de départ de 32 bits.
Sylvain
wrote on 10/10/2005 15:29:
Bonjour, En supposant que dans un cas particulier on calcule le CRC32 pour des buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet pour ces buffers est-il une fonction bijective ?
une visite sur wikipedia confirme ma première intuition: de quel CRC32 parle-t-on ?, le fait qu'ils produisent une empreinte (checksum) de 32 bits est acquis, mais la façon de le calculer est loin d'être unique.
Merci pour la réponse ! Je cherche une explication mathématique de préférence...
à défaut, et une fois votre réduction polynomiale (ou autre) définie, une petite boucle de 0 à -1 en stockant l'apparition d'un checksum donné sous un bit ne demande que 512 Méga de mémoire, juste de quoi occuper le CPU cette nuit.
Sylvain.
bp_site@tiscali.fr wrote on 10/10/2005 15:29:
Bonjour,
En supposant que dans un cas particulier on calcule le CRC32 pour des
buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet
pour ces buffers est-il une fonction bijective ?
une visite sur wikipedia confirme ma première intuition: de quel CRC32
parle-t-on ?, le fait qu'ils produisent une empreinte (checksum) de 32
bits est acquis, mais la façon de le calculer est loin d'être unique.
Merci pour la réponse ! Je cherche une explication mathématique de
préférence...
à défaut, et une fois votre réduction polynomiale (ou autre) définie,
une petite boucle de 0 à -1 en stockant l'apparition d'un checksum donné
sous un bit ne demande que 512 Méga de mémoire, juste de quoi occuper le
CPU cette nuit.
Bonjour, En supposant que dans un cas particulier on calcule le CRC32 pour des buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet pour ces buffers est-il une fonction bijective ?
une visite sur wikipedia confirme ma première intuition: de quel CRC32 parle-t-on ?, le fait qu'ils produisent une empreinte (checksum) de 32 bits est acquis, mais la façon de le calculer est loin d'être unique.
Merci pour la réponse ! Je cherche une explication mathématique de préférence...
à défaut, et une fois votre réduction polynomiale (ou autre) définie, une petite boucle de 0 à -1 en stockant l'apparition d'un checksum donné sous un bit ne demande que 512 Méga de mémoire, juste de quoi occuper le CPU cette nuit.
Sylvain.
pornin
According to :
En supposant que dans un cas particulier on calcule le CRC32 pour des buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet pour ces buffers est-il une fonction bijective ?
Un CRC32 est fondé sur l'utilisation d'un polynôme P de degré 32 dans F_2[X]. L'état est un polynôme modulo P. Le traitement de chaque bloc de 32 bits est un XOR bit à bit, i.e. une addition dans F_2[X], suivie de 32 multiplications par X modulo P. La sortie du CRC32 est l'état final (j'ignore ici les pre- et post-conditionings, qui ne changent pas le concept).
Si P est un polynôme premier (pas de diviseur strict de degré supérieur ou égal à 1), alors X est inversible modulo P et donc les 32 multiplications par X modulo P sont réversibles ; il s'en suit que ça fait bien une bijection.
Il s'avère qu'il est courant que le polynôme en question soit premier ; en général on en prend un qui, en plus, est primitif (i.e., non seulement tous les polynômes modulo P sauf 0 sont inversibles, mais en plus X est générateur du groupe des inversibles). C'est le cas du polynôme utilisé dans le CRC32 évoqué dans la RFC 1952 (format de compression GZIP).
De toutes façons, le CRC32 est linéaire, donc il suffit de reconstruire la matrice (calculer le CRC32 de 2^0, 2^1, 2^2... 2^31), et de vérifier qu'elle est inversible avec un banal pivot de Gauss.
--Thomas Pornin
According to <bp_site@tiscali.fr>:
En supposant que dans un cas particulier on calcule le CRC32 pour des
buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet
pour ces buffers est-il une fonction bijective ?
Un CRC32 est fondé sur l'utilisation d'un polynôme P de degré 32 dans
F_2[X]. L'état est un polynôme modulo P. Le traitement de chaque bloc de
32 bits est un XOR bit à bit, i.e. une addition dans F_2[X], suivie de
32 multiplications par X modulo P. La sortie du CRC32 est l'état final
(j'ignore ici les pre- et post-conditionings, qui ne changent pas le
concept).
Si P est un polynôme premier (pas de diviseur strict de degré
supérieur ou égal à 1), alors X est inversible modulo P et donc les 32
multiplications par X modulo P sont réversibles ; il s'en suit que ça
fait bien une bijection.
Il s'avère qu'il est courant que le polynôme en question soit premier ;
en général on en prend un qui, en plus, est primitif (i.e., non seulement
tous les polynômes modulo P sauf 0 sont inversibles, mais en plus X est
générateur du groupe des inversibles). C'est le cas du polynôme utilisé
dans le CRC32 évoqué dans la RFC 1952 (format de compression GZIP).
De toutes façons, le CRC32 est linéaire, donc il suffit de reconstruire
la matrice (calculer le CRC32 de 2^0, 2^1, 2^2... 2^31), et de vérifier
qu'elle est inversible avec un banal pivot de Gauss.
En supposant que dans un cas particulier on calcule le CRC32 pour des buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet pour ces buffers est-il une fonction bijective ?
Un CRC32 est fondé sur l'utilisation d'un polynôme P de degré 32 dans F_2[X]. L'état est un polynôme modulo P. Le traitement de chaque bloc de 32 bits est un XOR bit à bit, i.e. une addition dans F_2[X], suivie de 32 multiplications par X modulo P. La sortie du CRC32 est l'état final (j'ignore ici les pre- et post-conditionings, qui ne changent pas le concept).
Si P est un polynôme premier (pas de diviseur strict de degré supérieur ou égal à 1), alors X est inversible modulo P et donc les 32 multiplications par X modulo P sont réversibles ; il s'en suit que ça fait bien une bijection.
Il s'avère qu'il est courant que le polynôme en question soit premier ; en général on en prend un qui, en plus, est primitif (i.e., non seulement tous les polynômes modulo P sauf 0 sont inversibles, mais en plus X est générateur du groupe des inversibles). C'est le cas du polynôme utilisé dans le CRC32 évoqué dans la RFC 1952 (format de compression GZIP).
De toutes façons, le CRC32 est linéaire, donc il suffit de reconstruire la matrice (calculer le CRC32 de 2^0, 2^1, 2^2... 2^31), et de vérifier qu'elle est inversible avec un banal pivot de Gauss.
--Thomas Pornin
teno
wrote:
Bonjour, En supposant que dans un cas particulier on calcule le CRC32 pour des buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet pour ces buffers est-il une fonction bijective ?
Merci pour la réponse ! Je cherche une explication mathématique de préférence...
Bernard
En un peu plus lourd...
Par definition, CRC( u(x) ) = ( x^32*u(x) ) mod p(x) ou p(x) est de degre 32.
Si 2 polynomes u et v ont meme CRC, alors ( x^32*( u(x)-v(x) ) = 0 mod p(x). Ce qui revient a x^32 * ( u(x)-v(x) ) = a(x)*p(x) dans F_2[x].
Comme les degres de u(x) et v(x) sont <= 31 (32 bits), celui de a est aussi <1.
Si on continue, u(x)-v(x) = ( a(x)*p(x) )/x^32 . Comme x^32 est forcement relativement premier avec p(x), il doit diviser a(x) => impossibilité a cause des degres.
bp_site@tiscali.fr wrote:
Bonjour,
En supposant que dans un cas particulier on calcule le CRC32 pour des
buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet
pour ces buffers est-il une fonction bijective ?
Merci pour la réponse ! Je cherche une explication mathématique de
préférence...
Bernard
En un peu plus lourd...
Par definition, CRC( u(x) ) = ( x^32*u(x) ) mod p(x) ou p(x) est de
degre 32.
Si 2 polynomes u et v ont meme CRC, alors ( x^32*( u(x)-v(x) ) = 0 mod
p(x). Ce qui revient a x^32 * ( u(x)-v(x) ) = a(x)*p(x) dans F_2[x].
Comme les degres de u(x) et v(x) sont <= 31 (32 bits), celui de a est
aussi <1.
Si on continue, u(x)-v(x) = ( a(x)*p(x) )/x^32 . Comme x^32 est
forcement relativement premier avec p(x), il doit diviser a(x) =>
impossibilité a cause des degres.
Bonjour, En supposant que dans un cas particulier on calcule le CRC32 pour des buffers de longueur 4 octets, la fonction calculant le CRC32-Ethernet pour ces buffers est-il une fonction bijective ?
Merci pour la réponse ! Je cherche une explication mathématique de préférence...
Bernard
En un peu plus lourd...
Par definition, CRC( u(x) ) = ( x^32*u(x) ) mod p(x) ou p(x) est de degre 32.
Si 2 polynomes u et v ont meme CRC, alors ( x^32*( u(x)-v(x) ) = 0 mod p(x). Ce qui revient a x^32 * ( u(x)-v(x) ) = a(x)*p(x) dans F_2[x].
Comme les degres de u(x) et v(x) sont <= 31 (32 bits), celui de a est aussi <1.
Si on continue, u(x)-v(x) = ( a(x)*p(x) )/x^32 . Comme x^32 est forcement relativement premier avec p(x), il doit diviser a(x) => impossibilité a cause des degres.
