Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).
Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).
Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).
Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).
Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).
Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).
Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Phil l'ancienLe problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Quelques remarques:
- si le "condensat" est une "checksum", un code à redondance
cyclique (CRC), *OU* est une valeur courte (moins de disons
50 bits) calculée par une méthode publique, il offre une
protection quasi nulle contre les attaques délibérées
consistant à changer le fichier, puisqu'il est facile de
changer un fichier sans changer le condensat.
- même absence de protection si le condensat (quelque soit sa
nature et sa taille) est calculé par une méthode publique et
transmis sans protection particulière avec le fichier, car
il est facile de changer le fichier et le condensat.
- bref pour avoir une protection, il faut un condensat calculé
selon une méthode cryptographiquement saine, et transmis dans
des conditions où son intégrité est assurée (par exemple, par
téléphone, ou mieux signé par un algorithme à clé publique).
Ceci étant posé, quand une information est transmise, elle
l'est souvent sous forme de fichier, comprenant un nombre
entier d'octets de 8 bits (parfois: multiple supérieur mais
rentrant dans ce cas assez général), et à peu près tout le
monde est d'accord pour calculer le hash, par exemple SHA-1,
d'un tel fichier, SANS en connaitre le format.
Mon conseil serait donc de
- si il y a plusieurs fichiers, les rassembler en une archive
(zip, tar, tar.bz2..)
- calculer un condensat SHA-1 du fichier / de l'archive
(ou RipeMD-160, SHA-256, SHA-512, pour ceux qui ne veulent
pas entrer dans une discussion de spécialistes sur la
sécurité de SHA-1 dans les attaques de type seconde préimage)
- signer le consensat avec la clé privée de l'émetteur
- transmettre (protégé par une encapsulation adéquate) le
fichier / archive et la signature
Note: une bonne utilisation de PGP/GPG combine au moins les 3
dernières étapes de manière transparente.
Bien sur le destinataire doit vérifier la signature avec la
clé publique de l'émetteur avant d'utiliser le ficher / ouvrir
l'archive.
Phil l'ancien
Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Quelques remarques:
- si le "condensat" est une "checksum", un code à redondance
cyclique (CRC), *OU* est une valeur courte (moins de disons
50 bits) calculée par une méthode publique, il offre une
protection quasi nulle contre les attaques délibérées
consistant à changer le fichier, puisqu'il est facile de
changer un fichier sans changer le condensat.
- même absence de protection si le condensat (quelque soit sa
nature et sa taille) est calculé par une méthode publique et
transmis sans protection particulière avec le fichier, car
il est facile de changer le fichier et le condensat.
- bref pour avoir une protection, il faut un condensat calculé
selon une méthode cryptographiquement saine, et transmis dans
des conditions où son intégrité est assurée (par exemple, par
téléphone, ou mieux signé par un algorithme à clé publique).
Ceci étant posé, quand une information est transmise, elle
l'est souvent sous forme de fichier, comprenant un nombre
entier d'octets de 8 bits (parfois: multiple supérieur mais
rentrant dans ce cas assez général), et à peu près tout le
monde est d'accord pour calculer le hash, par exemple SHA-1,
d'un tel fichier, SANS en connaitre le format.
Mon conseil serait donc de
- si il y a plusieurs fichiers, les rassembler en une archive
(zip, tar, tar.bz2..)
- calculer un condensat SHA-1 du fichier / de l'archive
(ou RipeMD-160, SHA-256, SHA-512, pour ceux qui ne veulent
pas entrer dans une discussion de spécialistes sur la
sécurité de SHA-1 dans les attaques de type seconde préimage)
- signer le consensat avec la clé privée de l'émetteur
- transmettre (protégé par une encapsulation adéquate) le
fichier / archive et la signature
Note: une bonne utilisation de PGP/GPG combine au moins les 3
dernières étapes de manière transparente.
Bien sur le destinataire doit vérifier la signature avec la
clé publique de l'émetteur avant d'utiliser le ficher / ouvrir
l'archive.
Phil l'ancienLe problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).
Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".
Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?
Quelques remarques:
- si le "condensat" est une "checksum", un code à redondance
cyclique (CRC), *OU* est une valeur courte (moins de disons
50 bits) calculée par une méthode publique, il offre une
protection quasi nulle contre les attaques délibérées
consistant à changer le fichier, puisqu'il est facile de
changer un fichier sans changer le condensat.
- même absence de protection si le condensat (quelque soit sa
nature et sa taille) est calculé par une méthode publique et
transmis sans protection particulière avec le fichier, car
il est facile de changer le fichier et le condensat.
- bref pour avoir une protection, il faut un condensat calculé
selon une méthode cryptographiquement saine, et transmis dans
des conditions où son intégrité est assurée (par exemple, par
téléphone, ou mieux signé par un algorithme à clé publique).
Ceci étant posé, quand une information est transmise, elle
l'est souvent sous forme de fichier, comprenant un nombre
entier d'octets de 8 bits (parfois: multiple supérieur mais
rentrant dans ce cas assez général), et à peu près tout le
monde est d'accord pour calculer le hash, par exemple SHA-1,
d'un tel fichier, SANS en connaitre le format.
Mon conseil serait donc de
- si il y a plusieurs fichiers, les rassembler en une archive
(zip, tar, tar.bz2..)
- calculer un condensat SHA-1 du fichier / de l'archive
(ou RipeMD-160, SHA-256, SHA-512, pour ceux qui ne veulent
pas entrer dans une discussion de spécialistes sur la
sécurité de SHA-1 dans les attaques de type seconde préimage)
- signer le consensat avec la clé privée de l'émetteur
- transmettre (protégé par une encapsulation adéquate) le
fichier / archive et la signature
Note: une bonne utilisation de PGP/GPG combine au moins les 3
dernières étapes de manière transparente.
Bien sur le destinataire doit vérifier la signature avec la
clé publique de l'émetteur avant d'utiliser le ficher / ouvrir
l'archive.
Je reformule pour être plus clair.
Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
Chaque destinataire a donc une liste de nombres
supposée être identique à la liste de référence
(la mienne).
Chaque destinataire a son système d'information
propre, que je ne connais pas, et sa propre implémentation.
Je ne sais pas si c'est un fichier ou une base de données, etc.
Chaque destinataire, et moi-même, avons des systèmes
d'information : on est capables de compter, d'additionner,
etc.
Je cherche un algo de type checksum ou autre
qui permette à chaque destinataire de s'assurer
que sa liste est bien identique à la mienne, avec
une fiabilité connue.
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.
Exemples d'algos possibles :
Je transmet à tous les destinataires
la longueur de la liste et la somme de tous les nombres.
(ex : 1000 nombres, somme 12345654321)
Chaque destinataire regarde la longueur de sa liste et
additionne de son côté. Si il trouve la même longueur
de liste et la même somme, il en déduit que sa liste
est correcte.
ou
On compte le nombres de '1', le nombre
de '2', etc. dans la liste de nombres
exprimés en base 10.
Connaissez-vous un algo efficace de ce type ?
(j'ai besoin d'un algo documenté en termes
de sa fiabilité, c'est à dire de la probabilité
qu'il laisse passer une ou des erreurs).
Je reformule pour être plus clair.
Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
Chaque destinataire a donc une liste de nombres
supposée être identique à la liste de référence
(la mienne).
Chaque destinataire a son système d'information
propre, que je ne connais pas, et sa propre implémentation.
Je ne sais pas si c'est un fichier ou une base de données, etc.
Chaque destinataire, et moi-même, avons des systèmes
d'information : on est capables de compter, d'additionner,
etc.
Je cherche un algo de type checksum ou autre
qui permette à chaque destinataire de s'assurer
que sa liste est bien identique à la mienne, avec
une fiabilité connue.
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.
Exemples d'algos possibles :
Je transmet à tous les destinataires
la longueur de la liste et la somme de tous les nombres.
(ex : 1000 nombres, somme 12345654321)
Chaque destinataire regarde la longueur de sa liste et
additionne de son côté. Si il trouve la même longueur
de liste et la même somme, il en déduit que sa liste
est correcte.
ou
On compte le nombres de '1', le nombre
de '2', etc. dans la liste de nombres
exprimés en base 10.
Connaissez-vous un algo efficace de ce type ?
(j'ai besoin d'un algo documenté en termes
de sa fiabilité, c'est à dire de la probabilité
qu'il laisse passer une ou des erreurs).
Je reformule pour être plus clair.
Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
Chaque destinataire a donc une liste de nombres
supposée être identique à la liste de référence
(la mienne).
Chaque destinataire a son système d'information
propre, que je ne connais pas, et sa propre implémentation.
Je ne sais pas si c'est un fichier ou une base de données, etc.
Chaque destinataire, et moi-même, avons des systèmes
d'information : on est capables de compter, d'additionner,
etc.
Je cherche un algo de type checksum ou autre
qui permette à chaque destinataire de s'assurer
que sa liste est bien identique à la mienne, avec
une fiabilité connue.
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.
Exemples d'algos possibles :
Je transmet à tous les destinataires
la longueur de la liste et la somme de tous les nombres.
(ex : 1000 nombres, somme 12345654321)
Chaque destinataire regarde la longueur de sa liste et
additionne de son côté. Si il trouve la même longueur
de liste et la même somme, il en déduit que sa liste
est correcte.
ou
On compte le nombres de '1', le nombre
de '2', etc. dans la liste de nombres
exprimés en base 10.
Connaissez-vous un algo efficace de ce type ?
(j'ai besoin d'un algo documenté en termes
de sa fiabilité, c'est à dire de la probabilité
qu'il laisse passer une ou des erreurs).
Phil l'ancien
Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
...
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.
Ce n'est pas l'acception courante de 'intégrité' dans ce
forum de cryptographie, qui s'intéresse aux adversaires qui
modifient sciemment les données; d'où mon précédent message.
Exemples d'algos possibles :
...
Une point qui a son importance: l'ordre des entiers est-il
significatif ? Dans les techniques citées en exemple, la
permutation d'éléments de la liste n'est pas détectée.
C'est peut-être une faiblesse non voulue.
...
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
En théorie, la même technique ne fonctionne pas avec un CRC,
car on ne peut exclure que le canal de transmission ait une
forte propension à ne faire que des erreurs qui n'altèrent
par ce CRC (exemple classique: si le canal de transmission
corrige ses erreurs avec le même polynôme).
Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
/...
; et l'on calcule
la valeur de contrôle v des entiers aj de la liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
François Grieu
Phil l'ancien
Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
...
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.
Ce n'est pas l'acception courante de 'intégrité' dans ce
forum de cryptographie, qui s'intéresse aux adversaires qui
modifient sciemment les données; d'où mon précédent message.
Exemples d'algos possibles :
...
Une point qui a son importance: l'ordre des entiers est-il
significatif ? Dans les techniques citées en exemple, la
permutation d'éléments de la liste n'est pas détectée.
C'est peut-être une faiblesse non voulue.
...
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
En théorie, la même technique ne fonctionne pas avec un CRC,
car on ne peut exclure que le canal de transmission ait une
forte propension à ne faire que des erreurs qui n'altèrent
par ce CRC (exemple classique: si le canal de transmission
corrige ses erreurs avec le même polynôme).
Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
/...
; et l'on calcule
la valeur de contrôle v des entiers aj de la liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
François Grieu
Phil l'ancien
Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
...
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.
Ce n'est pas l'acception courante de 'intégrité' dans ce
forum de cryptographie, qui s'intéresse aux adversaires qui
modifient sciemment les données; d'où mon précédent message.
Exemples d'algos possibles :
...
Une point qui a son importance: l'ordre des entiers est-il
significatif ? Dans les techniques citées en exemple, la
permutation d'éléments de la liste n'est pas détectée.
C'est peut-être une faiblesse non voulue.
...
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
En théorie, la même technique ne fonctionne pas avec un CRC,
car on ne peut exclure que le canal de transmission ait une
forte propension à ne faire que des erreurs qui n'altèrent
par ce CRC (exemple classique: si le canal de transmission
corrige ses erreurs avec le même polynôme).
Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
/...
; et l'on calcule
la valeur de contrôle v des entiers aj de la liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
François Grieu
Dans mon application, l'ordre n'est pas significatif.
(l'utilisation est de vérifier la non appartenance
d'un nombre à la liste)
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.
Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.
Il faut un autre contrôle que celui de la transmission
Un contrôle autant que possible "orthogonal", si on peut dire.
Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.
Les nombres de mon application sont inférieurs à 2^40-1.
Si je vous comprend bien, on pourrait faire deux
contrôles par SHA-1 :
- un contrôle de transmission, dans l'ordre big-endian
- un contrôle de prise en compte, dans l'ordre little-endian
(ou l'inverse) c'est bien ça ?
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
A partir de là, je suis perdu... pourtant je suis un
ingénieur, purée ! bon, ok, pas de polytechnique ;-)
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Dans mon application, l'ordre n'est pas significatif.
(l'utilisation est de vérifier la non appartenance
d'un nombre à la liste)
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.
Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.
Il faut un autre contrôle que celui de la transmission
Un contrôle autant que possible "orthogonal", si on peut dire.
Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.
Les nombres de mon application sont inférieurs à 2^40-1.
Si je vous comprend bien, on pourrait faire deux
contrôles par SHA-1 :
- un contrôle de transmission, dans l'ordre big-endian
- un contrôle de prise en compte, dans l'ordre little-endian
(ou l'inverse) c'est bien ça ?
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
A partir de là, je suis perdu... pourtant je suis un
ingénieur, purée ! bon, ok, pas de polytechnique ;-)
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Dans mon application, l'ordre n'est pas significatif.
(l'utilisation est de vérifier la non appartenance
d'un nombre à la liste)
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.
Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.
Il faut un autre contrôle que celui de la transmission
Un contrôle autant que possible "orthogonal", si on peut dire.
Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.
Les nombres de mon application sont inférieurs à 2^40-1.
Si je vous comprend bien, on pourrait faire deux
contrôles par SHA-1 :
- un contrôle de transmission, dans l'ordre big-endian
- un contrôle de prise en compte, dans l'ordre little-endian
(ou l'inverse) c'est bien ça ?
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
A partir de là, je suis perdu... pourtant je suis un
ingénieur, purée ! bon, ok, pas de polytechnique ;-)
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Phil l'ancienDans mon application, l'ordre n'est pas significatif.
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.
Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.
Ca ressemble à la question de la mise à jour de la
"liste noire" dans les les terminaux de paiement.
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
Bon je reformule: mon but est de construire une somme de contrôle
qui ne manipule les nombres qu'avec des opérateurs présents
dans la pluspart des plateformes, ce qui exclu en particulier
l'opérateur XOR par exemple, qui est très difficile à implementer
dans mon tableur habituel; et donc exclu SHA-1.
Mais je veux pouvoir donner un argument rigoureux que la
somme de contrôle résiste aux erreur non intentionelles.
Ma démarche, standard en crypto académique, est de construire une
famille de sommes de contrôles, et de démontrer que face à un
adversaire qui ingore quelle membre de la famille j'ai choisi,
la probabiltié qu'une altération (y compris intentionelle) soit
non détectée, est inférieure à un seuil.
Je dis que si j'ai une telle famille, il suffit que j'en prenne
un membre particulier au hasard, et/donc sans rapport avec le genre
d'erreur accidentelle que je vais rencontrer en pratique, pour être
"certain" de ma capacité de détection d'erreur: les erreurs non
intentionelles n'ont "aucne raison" de m'être plus défavorables que
des erreurs intentionelles.
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Phil l'ancien
Dans mon application, l'ordre n'est pas significatif.
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.
Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.
Ca ressemble à la question de la mise à jour de la
"liste noire" dans les les terminaux de paiement.
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
Bon je reformule: mon but est de construire une somme de contrôle
qui ne manipule les nombres qu'avec des opérateurs présents
dans la pluspart des plateformes, ce qui exclu en particulier
l'opérateur XOR par exemple, qui est très difficile à implementer
dans mon tableur habituel; et donc exclu SHA-1.
Mais je veux pouvoir donner un argument rigoureux que la
somme de contrôle résiste aux erreur non intentionelles.
Ma démarche, standard en crypto académique, est de construire une
famille de sommes de contrôles, et de démontrer que face à un
adversaire qui ingore quelle membre de la famille j'ai choisi,
la probabiltié qu'une altération (y compris intentionelle) soit
non détectée, est inférieure à un seuil.
Je dis que si j'ai une telle famille, il suffit que j'en prenne
un membre particulier au hasard, et/donc sans rapport avec le genre
d'erreur accidentelle que je vais rencontrer en pratique, pour être
"certain" de ma capacité de détection d'erreur: les erreurs non
intentionelles n'ont "aucne raison" de m'être plus défavorables que
des erreurs intentionelles.
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Phil l'ancienDans mon application, l'ordre n'est pas significatif.
Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.
Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.
Ca ressemble à la question de la mise à jour de la
"liste noire" dans les les terminaux de paiement.
Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../
Bon je reformule: mon but est de construire une somme de contrôle
qui ne manipule les nombres qu'avec des opérateurs présents
dans la pluspart des plateformes, ce qui exclu en particulier
l'opérateur XOR par exemple, qui est très difficile à implementer
dans mon tableur habituel; et donc exclu SHA-1.
Mais je veux pouvoir donner un argument rigoureux que la
somme de contrôle résiste aux erreur non intentionelles.
Ma démarche, standard en crypto académique, est de construire une
famille de sommes de contrôles, et de démontrer que face à un
adversaire qui ingore quelle membre de la famille j'ai choisi,
la probabiltié qu'une altération (y compris intentionelle) soit
non détectée, est inférieure à un seuil.
Je dis que si j'ai une telle famille, il suffit que j'en prenne
un membre particulier au hasard, et/donc sans rapport avec le genre
d'erreur accidentelle que je vais rencontrer en pratique, pour être
"certain" de ma capacité de détection d'erreur: les erreurs non
intentionelles n'ont "aucne raison" de m'être plus défavorables que
des erreurs intentionelles.
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
On sait déjà par ailleurs vérifier l'absence d'erreur
dans la transmission des mises à jour, et là je
cherche le moyen de vérifier l'absence d'erreur
après prise en compte (prise en compte cumulative
de plusieurs transmissions).
Francois Grieul'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
L'algorithme me convient plutôt bien.
Dans votre exemple, n est très proche de
la borne supérieure des entiers aj.
Est-ce une nécessité ?
Pouvez-vous m'indiquer comment on détermine la probabilité
(le risque) qu'une erreur accidentelle ne soit pas détectée ?
on choisi comme paramètres deux nombres premiers
distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée;
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Ca m'intéresse aussi, ainsi on supprime la
nécessité de trier la liste.
On sait déjà par ailleurs vérifier l'absence d'erreur
dans la transmission des mises à jour, et là je
cherche le moyen de vérifier l'absence d'erreur
après prise en compte (prise en compte cumulative
de plusieurs transmissions).
Francois Grieu
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
L'algorithme me convient plutôt bien.
Dans votre exemple, n est très proche de
la borne supérieure des entiers aj.
Est-ce une nécessité ?
Pouvez-vous m'indiquer comment on détermine la probabilité
(le risque) qu'une erreur accidentelle ne soit pas détectée ?
on choisi comme paramètres deux nombres premiers
distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée;
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Ca m'intéresse aussi, ainsi on supprime la
nécessité de trier la liste.
On sait déjà par ailleurs vérifier l'absence d'erreur
dans la transmission des mises à jour, et là je
cherche le moyen de vérifier l'absence d'erreur
après prise en compte (prise en compte cumulative
de plusieurs transmissions).
Francois Grieul'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.
L'algorithme me convient plutôt bien.
Dans votre exemple, n est très proche de
la borne supérieure des entiers aj.
Est-ce une nécessité ?
Pouvez-vous m'indiquer comment on détermine la probabilité
(le risque) qu'une erreur accidentelle ne soit pas détectée ?
on choisi comme paramètres deux nombres premiers
distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée;
Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n
Ca m'intéresse aussi, ainsi on supprime la
nécessité de trier la liste.
En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.
En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.
En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.