Les journaux sont destinés à des informations qui ne sont pas suffisamment intéressantes
pour être validées en dépêche (sinon n'hésitez pas à proposer votre information en
dépêche), qui sont sans rapport avec Linux ou le libre, ou simplement pour donner votre
avis. Si vous désirez poser une question, merci d'utiliser Derniers journaux de NMi :
- [12/12@15:21] Benchmark PHP vs ASP vs ... ?
- [17/09@09:41] Fait scientifique
Journal : Question existentielle
Posté par N-Mi () le 15 décembre 2003Est-il possible qu'un fichier contienne son propre checksum?
> Lire le journal (40 commentaires, moyenne: 2,4).
Re: Question existentielle
Tout dépend de l'algorithme utilisé. Je n'en connais pas mais il doit être possible d'avoir des fichiers qui contiennent leur propre checksum.
On doit pouvoir y arriver à la limite:
Considérons un fichier, appelons-le f0, quelconque dont on calcule la signature. On concatène ensuite cette signature à la fin de f0 pour ainsi obtenir f1. On calcule ensuite la signature de f1 et on la concatène à la fin de f0 pour obtenir f2.
On continue récursivement: pour obtenir fn+1 on met la signature de fn à la fin de f0.
Deux solutions possibles:
- soit la suite diverge ou est périodique, ce qui veut dire qu'on a choisi un mauvais point de départ ou pire que ce n'est pas possible.
- soit il existe N tel que les signatures de fn pour n>=N sont toutes identiques.
C'est un procédé classique de résolution d'équation, en l'occurence l'équation était
signature(f)=signature(f+signature(f))
qu'on a transformé en
signature(fn+1)=signature(fn+signature(fn))
pour l'itérer.
-
[^]Re: Question existentielle
Posté par Fabien Jakimowicz (page perso, ) le 15/12/2003 à 12:29. (lien). Évalué à 5.A mon avis, ca part en boucle infinie
-
[^]Re: Question existentielle
Posté par wismerhill (page perso, ) le 15/12/2003 à 15:11. (lien). Évalué à 2.C'est une des deux solutions que j'ai donné.
-
-
[^]Re: Question existentielle
Posté par cumulus () le 15/12/2003 à 12:45. (lien). Évalué à 2.Une condition nécessaire pour que cela marche c'est que la fonction signature( ) soit surjective non ? Serait-ce le cas pour checksum( ) ?
Allez, un petit théorème applicable et on peut répondre à la question, mes souvenirs de maths sont un peu enfouis ..
-
[^]Re: Question existentielle
Posté par Cédric Foll (page perso, ) le 15/12/2003 à 12:50. (lien). Évalué à 1.Ca finira forcément par converger parce que {signature(fichier), fichier appartenant Univers} est fini (à moins qu'on l'on tombe sur un cycle ce qui est autement improbable à mon avis.)
Par contre on peut espérer que dans la pratique ça ne converge jamais (les algo de hash doivent avoir une proba de colision minimale).
La solution serait d'inventer un format de fichier pour gérer celà.
Par exemple un xml qui intègre un fichier et sa signature.-
[^]Re: Question existentielle
Posté par gawal () le 15/12/2003 à 15:00. (lien). Évalué à 2.Il ne me semble pas que tomber sur un cycle soit plus improbable que tomber sur un point fixe. Un point fixe est simplement un cycle de longeur 1. Si l'on considere que la fonction de hachage est pseudo-aleatoire, alors on a nettement plus de chances de tomber sur un cycle de longeur > 1 que sur un point fixe.
-
-
[^]Re: Question existentielle
Posté par Nap () le 15/12/2003 à 14:41. (lien). Évalué à 5.Tout dépend de l'algorithme utilisé
c'est clair
comme algo qui a un fichier donné associe un "checksum" je prends un algo qui extrait les 50 premiers caractères d'un fichier
vala, le checksum est bien contenu dans le fichier
aller je prends mon élan
<-------------------------------
et je
-------------------------------------->[]-
[^]Re: Question existentielle
Posté par wismerhill (page perso, ) le 15/12/2003 à 15:13. (lien). Évalué à 2.Mais tu sort des limites du problème, un algorithme de checksum doit obligatoirement prendre tout le fichier en compte.
-
[^]Re: Question existentielle
Posté par allcolor (Jabber id, page perso, ) le 15/12/2003 à 15:53. (lien). Évalué à 3.Ben non t'as pas besoin de "checksumer" la checksum... vu qu'elle sers à vérifier l'intégrité des données... donc dans l'exemple du haut, le format de fichier serait :
<checksum><data>
... à la verification si checksum ne correspond pas au checksum de la zone data... y a eu un problème... et voilà... on est content...--
All those moments will be lost in time, like tears in the rain.-
[^]Re: Question existentielle
Posté par wismerhill (page perso, ) le 15/12/2003 à 16:07. (lien). Évalué à 2.Bien sur, ta façon de faire fonctionne. Mais tu n'est pas dans le cadre de la question de ce journal.
La question est Est-il possible qu'un fichier contienne son propre checksum?, dans ton cas le fichier (qui n'est que la partie data) est distribué avec sa checksum (sous forme de la concaténation des deux).-
[^]Re: Question existentielle
-
-
-
-
Re: Question existentielle
par définition, ça me parait improbable, pas volontairement et sur n'importe quel fichier en tous cas !!!!
Re: Question existentielle
A priori on ne connait le checksum du fichier qu'une fois que celui-ci n'est plus edite. Or en inserant le checksum on modifie ce dernier....
Il faut donc inserer le checksum avant de le connaitre... ce qui me parait difficile.
Si l'on prend le probleme autrement. Le checksum represente le fichier, or si on l'insere dans ce fichier, il le denature.... et ne le represente donc plus.
A priori je dirais NON, NON et NON. Mais bien entendu, impossible n'est pas francais, et puisqu'il ne faut pas dire 'jam...', alors laissons nous penser que cela est probablement improbable.
Pour des soucis pratiques en revanche on peut parfaitement inclure le fichier et son checksum dans une unique archive. Le probleme survient lorsque l'on souhaite savoir si l'archive n'a pas ete corrompue... et ou l'on commence a introduire un nouveau checksum :))))
-
[^]Re: Question existentielle
Posté par #3588 () le 15/12/2003 à 13:44. (lien). Évalué à 2.Je pense qu'il sait très bien tout ça et que c'est pour ça que la question est intéressante... Il ne s'agit pas d'insérer le checksum dans le fichier, mais d'avoir un fichier contenant son propre checksum. C'est un jeu, du même style que les quines, pas une "situation normale".
-
[^]Re: Question existentielle
-
[^]Re: Question existentielle
-
[^]Re: Question existentielle
Posté par Axioplase Ashi (page perso, ) le 15/12/2003 à 23:33. (lien). Évalué à 1.ben...
J avais posté une news sur les quines il y a de cela quelques mois...
Et j ai jamais reussi à les faires... Si qq1 connait une methode (tant soit peu qu' il en existe une passe partout)
P!
-
Re: Question existentielle
Juste une chtite question : quand on insère un checksum dans un fichier, on fait bien le checksum de tout le fichier sauf l'emplacement du checksum ?
Qu'est-ce qui est petit, rond et vert, qui monte et qui descend ?
Yoda qui fait le con avec la force.
-
[^]Re: Question existentielle
Posté par free2.org (page perso, ) le 15/12/2003 à 12:57. (lien). Évalué à 2.bravo tu as gagné :)
encore faut-il une convention pour repérer où commence le checksum !
le plus simple est de commencer ou de finir le fichier par ce checksum
on peut s'inspirer des signatures gpg qui sont en fait des checksums SHA encryptés par une clé privée
-
[^]Re: Question existentielle
Posté par MagicNinja (page perso, ) le 15/12/2003 à 13:23. (lien). Évalué à 2.Oui, c'est comme ca par exemple qu'est calculé le checksum TCP : on sait où il est dans l'entête, on l'initialise à 0, on calcule, on stocke le résultat dans l'entête et on émet le paquet.
Re: Question existentielle
Ben, ca doit pouvoir se trouver. En effet, le checksum est la somme de tous les octets d'un fichier or cette somme est contenue dans une place qui est généralement supérieure à un octet (disons 4 ou 8 octets généralement).
Or quand on rajoute le checksum du fichier dans le fichier, le checksum ne double pas (heureusement car là on ne pourrait pas répondre) mais on rajoute la valeurs des-dits octets.
Si on considère un checksum sur 8 octets, on aura une différence d'au plus 8*256 soit 2048. On doit alors pouvoir imaginer un champ de meme taille que le checksum (4 ou 8 octets), initialisés à 0xFF...FF duquel on retranche la différence entre le checksum sans checksum et le checksum avec checksum mais en comptant toujours le champ de compensation à 0xFF...FF. Quand on retranche, je parle vie les octets, pas en mots.
Et au final, c'est bon.
Euh, je sais pas si je m'exprime bien mais ca marche.
Qu'est-ce qui est petit, rond et vert, qui monte et qui descend ?
Yoda qui fait le con avec la force.
-
[^]Re: Question existentielle
Posté par Emilien Kia (Jabber id, page perso, ) le 15/12/2003 à 13:04. (lien). Évalué à 5.Ptet un chtit exemple :).
Si on considère un fichier d'un certaine taille dont le checksum à plat est 725 0x02D5 (au pif) avec un checksum sur 2 octets et un champ de compensation de 2 octets à 0xFFFF.
Or 0x2D5 + 0x02 + 0xD5 = 0x03AC.
La différence est de 0x3AC-0x2D5 = 0xD7 (0x02+0xD5).
0xFF - 0xD7 = 0x28
On a juste à mettre le cham de compensation à 0xFF28 et le checksum à 0x03AC.
CQFD.--
Qu'est-ce qui est petit, rond et vert, qui monte et qui descend ?
Yoda qui fait le con avec la force.
Re: Question existentielle
Tu prends une solution façon gpg/pgp qui ajoute un entête (non compris dans le checksum) et qui indiquera le checksum du texte ensuite délimité.
La fonction que tu utiliserais alors ferait en sorte de vérifier le checksum et de le "supprimer"/"extraire le texte" par exemple, et donc tu aurais ton fichier tout propre, prêt à utiliser.
Sinon tu risques de faire une usine à gaz je pense...
Jean-Christophe
Re: Question existentielle
Ouais le problème réside dans la définition de l'algo utilisé dans le checksum.
Démonstration :
je check la parité binaire du fichier. S'il y a un nombre pair de 1, je rajoute 101 a la fin du fichier. Mon "checksum" est 101, il ne change pas la parité. Si j'ai un nombre impair de 1, je met 110 (pour changer, et on comprend l'interet du 0 entre les 1). Je ne change pas la parité non plus. Donc mon algo marche.
Je viens de démontrer l'existence d'un tel algo, héhé.
Bon apres, vous me direz que mon checksum, il prend que 2 valeurs possibles, bah c'est quand meme un checksum hein.
Donc un tel algo existe, je viens d'en exhiber un, j'ai répondu a ta question.
Bon plus sérieusement, le problème c'est la construction du checksum. Si l'on veut un checksum de qualité, il faut qu'il soit long, et plus il est long plus il a de chance d'etre de qualité (i.e. peu de collisions, et ecart important pour de faible variation).
Mais plus le checksum est long plus la complexité du problème est élevée.
Pour cela plusieurs solutions :
- utiliser un algo de type suite récursive (cf premier commentaire) qui converge. Il faut trouver une fonction potable, mais ça doit se trouver, c'est des maths.
- utiliser un algo magique qui fait que ca marcherait en une itération (faut pas rever)
- utiliser un algo statistique du genre construction progressive du checksum. Cela demanderait des propriétés assez contradictoires avec une maximisation de l'écart important pour de faibles variations.
- ou pour finir la solution que je préconiserais :
Utiliser successivement des algo de checksum utilisant une longueur de checksum de plus en plus petites (on concatène à chaque fois le checksum calculé), et on pourrai finir par exemple sur mon algo a 2 balles. A l'extreme limite, utiliser un checksum standard (md5) plus mon algo a la con. -> le checksum serait intégré au fichier, de qualité (md5) et vérifierait ta question. On connaitrait de plus la longueur du checksum, il suffit alors de couper la partie checksum du fichier :).
Des 4 solutions proposées, les 3 premières relèveraient plus de travaux mathématiques (je pense plus que c'est de ce coté que se penche ta question ;) ), alors que la derniere est plus une solution "technique".
Compenser la différence impliquée par le checksum n'est pas envisageable sur un checksum de taille conséquente (a moins que la fonction mathématique utilisée dans le checksum possède des propriétés particulières).
-
[^]Re: Question existentielle
Posté par inz () le 15/12/2003 à 13:44. (lien). Évalué à 1.Ah ouais j'oubliais.
L'intérêt du checksum c'est quand meme de vérifier l'intégrité du fichier. Autant pour les transferts de fichiers pourquoi pas, autant pour vérifier, au sens "non piraté", le fichier c'est un peu débile.
Bah ouais, si on falsifie le fichier, autant falsifier le checksum qui va avec :).
Mes deux cents.
Re: Question existentielle
A mon avis ce n'est pas possible et même si ça l'était, cela n'apporterait pas grand chose à la solution d'inclure un fichier et son checksum dans une archive.
Soit 'fichier' et 'checksum' une suite de caractères, 'f' la fonction checksum et '+' la fonction de concaténation, on veut:
f(Fichier+checksum)=checksum
=> f(Fichier+f(Fichier+checksum))=checksum
=> f(Fichier+f(Fichier+f(Fichier+checksum)))=checksum
=> f(Fichier+f(Fichier+f(Fichier+f(Fichier+checksum))))=checksum
=> ...
Ce qui implique qu'une infinité de fichiers tous différents et très liés aient le même checksum. Si cela devait être possible, il faudrait trouver une fonction 'checksum' très particulière.
-
[^]Re: Question existentielle
Posté par »-(¯`v´¯)-» (page perso, ) le 15/12/2003 à 15:07. (lien). Évalué à 1.ben non c'est toujours le meme fichier ;)
Re: Question existentielle
Dans le meme esprit que la parité, tu peut faire ca avec un XOR.
Tu fais un XOR de tous les bits du fichiers, et tu le rajoute a la fin. Ca te fais un fichier dans le XOR est nul (checksum)
-
[^]Re: Question existentielle
Posté par Khanh-Dang (page perso, ) le 15/12/2003 à 15:47. (lien). Évalué à 1.bin oui, XOR est bijective, tout comme l'application Identité, il n'y a que des points fixes (voir le premier post)
Par contre, au niveau de l'efficacité... ;-)
Re: Question existentielle
Quand on voit ce que certains arrivent à faire, je pense que ca doit être possible :
This
pangram
contains two
hundred nineteen
letters: five a's, one b,
two c's,four d's,thirty-one e's
eight f's, three g's, six h's,
fourteen i's, one j, one k,
two l's,two m's,twenty-six n's
seventeen o's, two p's, one q,
ten r's, twenty-nine s's,
twenty-four t's, six u's,
five v's, nine w's,
four x's,five y's,
and one
z.
-- Sallows, Lee
-
[^]Re: Question existentielle
Posté par ASpirit () le 15/12/2003 à 15:37. (lien). Évalué à 1.Ca me fait penser à la poésie : jouer avec les mots et montrer sa maîtrise de ceux-ci en s'imposant des exercices de style avec contraintes etc.
-
[^]Re: Question existentielle
Posté par David Douard () le 15/12/2003 à 16:15. (lien). Évalué à 1.Ca me fait penser à la poésie
Où à la littérature, tendance Oulipo (La disparition, par ex.)
A ce propos, le saviez-vous ? Dans la dernière édition de ce bouquin (je ne sais plus par qui) il y a une coquille : un e s'est glissé dans le texte.
Au fait, c'est Perec.
David
-
Re: Question existentielle
J' en ai un :
$ > foo
$ md5sum foo > foo
$ cat foo
d41d8cd98f00b204e9800998ecf8427e foo
on verifie :
$ md5sum foo > foo
$ cat foo
d41d8cd98f00b204e9800998ecf8427e foo
C'est bon ça n'a pas changé :-)
Amis lecteur, sauras-tu trouvé l'erreur...
-
[^]Re: Question existentielle
Posté par wismerhill (page perso, ) le 15/12/2003 à 15:32. (lien). Évalué à 3.Tu triche à ton deuxième
$ md5sum foo > foo
car, si je ne me trompe pas, avec le simple > le fichier est vidé avant de dommencer, donc on refait un checksum d'un fichier vide.-
[^]Re: Question existentielle
-
Re: Question existentielle
oui il le peut. fin c'est pas vraiment du ckecksum mais ca permet de vérifier l'intégrité des données.
certaines trames de réseau pas niveau utilse ce procéder (HDLC par exemple iso3309 et iso4335 rfc1662 (à vérifier)). cela s'appelle CRC (Cycle Redundancy Check).
KiKouN, Bucheron-Geek
-
[^]Re: Question existentielle
Posté par N-Mi () le 15/12/2003 à 17:47. (lien). Évalué à 2.Nan pour le HDLC y'a une tricherie : le checksum est calculé en prenant le paquet avec un checksum de 0.
Le checksum n'est donc pas checksumé.-
[^]Re: Question existentielle
Posté par KiKouN (Jabber id, ) le 16/12/2003 à 09:10. (lien). Évalué à 1.Bin en faites la norme ne précise pas la méthode pour le checksum.
bon me le but est de calculer le reste R de la divison (la_donnée*taille_du_checksum)/(par un nombre premier < taille_du_checksum) et tu envoie (la_donnée*taille_du_checksum) + taille_du_checksum-1-R
En réception,tu divise le tout par ton nombre premier et tu doit obtenir comme reste 0.
Bon aprés, ne me demander pas plus d'explication.--
KiKouN, Bucheron-Geek
-
Le plus simple.
Le plus simple c'est que tu fasse ton fichier , tu met ton checksum dedans et ensuite tu trouve l'algorithme qui donne ce checksum sur ce fichier.
Re: Question existentielle
Est-il possible qu'un fichier contienne son propre checksum?
Dans la série complètement théorique, et pas du tout pratique. Car il s'agit bien d'une question existantielle et non pas d'un cas pratique, je répondrais donc oui, bien sur!
écrit dans un fichier tous les checksum possible.
ce fichier contiendra son checksum.
Question existantielle résolue.
Maintenant pour le côté pratique... Si la question est:
H1 soit un fichier donné F1
H2 supposons que ses 32 premiers caractères représentent sa signature
Q1 est-il possible que l'outil md5sum retourne cette même signature ?
(simplement en modifiant les 32 premiers caractères, et pas le reste du fichier)
Q2 comment la trouver ?
...voir les reponses si dessus ;)
Cette page a été générée par Templeet en 0.2167s (dont 0.0554 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Faire un don !
Cette discussion est archivée, il n'est plus possible de laisser des commentaires.
Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.