Journal Question existentielle

Posté par N-Mi le 15 décembre 2003 à 13:04.

Étiquettes : aucune

déc.

2003

Tiens je me posais une question l'autre jour, dans la même lignée que l'énigme de la poule et de l'oeuf.

Est-il possible qu'un fichier contienne son propre checksum?

# Re: Question existentielle

Posté par wismerhill le 15 décembre 2003 à 13:21. Évalué à 7.
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 le 15 décembre 2003 à 13:29. Évalué à 5.
  
  A mon avis, ca part en boucle infinie
  - [^] # Re: Question existentielle
    
    Posté par wismerhill le 15 décembre 2003 à 16:11. Évalué à 2.
    
    C'est une des deux solutions que j'ai donné.
- [^] # Re: Question existentielle
  
  Posté par cumulus le 15 décembre 2003 à 13:45. É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 le 15 décembre 2003 à 13:50. É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 décembre 2003 à 16:00. É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 décembre 2003 à 15:41. É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 le 15 décembre 2003 à 16:13. É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 le 15 décembre 2003 à 16:53. É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...
      - [^] # Re: Question existentielle
        
        Posté par wismerhill le 15 décembre 2003 à 17:07. É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
        
        Posté par Nap le 15 décembre 2003 à 17:18. Évalué à 2.
        
        bah là tu sous-entends qu'il y a une définition précise du terme "checksum", que je ne vois que vaguement :)
# Re: Question existentielle

Posté par kolter (site web personnel, Mastodon) le 15 décembre 2003 à 13:22. Évalué à 4.

par définition, ça me parait improbable, pas volontairement et sur n'importe quel fichier en tous cas !!!!
# Re: Question existentielle

Posté par Clem Yeats le 15 décembre 2003 à 13:23. Évalué à 6.

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 décembre 2003 à 14:44. É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
    
    Posté par Clem Yeats le 15 décembre 2003 à 16:02. Évalué à 0.
    
    ok je sors... :)
  - [^] # Re: Question existentielle
    
    Posté par N-Mi le 15 décembre 2003 à 18:38. Évalué à 1.
    
    En effet, c'est là où je voulais en venir (d'où la référence à la poule et l'oeuf dans l'énoncé).
  - [^] # Re: Question existentielle
    
    Posté par Axioplase ıɥs∀ (site web personnel) le 16 décembre 2003 à 00:33. É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

Posté par Émilien Kia le 15 décembre 2003 à 13:46. Évalué à 3.

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 ?
Un jour libre ?
- [^] # Re: Question existentielle
  
  Posté par free2.org le 15 décembre 2003 à 13:57. É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 le 15 décembre 2003 à 14:23. É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

Posté par Émilien Kia le 15 décembre 2003 à 13:58. Évalué à 3.

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.
Un jour libre ?
- [^] # Re: Question existentielle
  
  Posté par Émilien Kia le 15 décembre 2003 à 14:04. É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.
  Un jour libre ?
# Re: Question existentielle

Posté par Jean-Christophe Berthon le 15 décembre 2003 à 14:03. Évalué à 3.

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

Posté par inz le 15 décembre 2003 à 14:37. Évalué à 7.

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 décembre 2003 à 14:44. É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

Posté par Romuald Delavergne le 15 décembre 2003 à 15:18. Évalué à 1.

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´ ̄)-» le 15 décembre 2003 à 16:07. Évalué à 1.
  
  ben non c'est toujours le meme fichier ;)
# Re: Question existentielle

Posté par newbix le 15 décembre 2003 à 15:34. Évalué à 1.

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 kd le 15 décembre 2003 à 16:47. É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

Posté par Hervé Rilos le 15 décembre 2003 à 16:16. Évalué à 2.

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 décembre 2003 à 16:37. É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 décembre 2003 à 17:15. É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

Posté par jigso le 15 décembre 2003 à 16:24. Évalué à 2.

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 le 15 décembre 2003 à 16:32. É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
    
    Posté par jigso le 15 décembre 2003 à 19:14. Évalué à 1.
    
    Bravo, et Monsieur Wismerhill repart avec un panier garni, et sous vos applaudissements !
    
    et hop -1 ... euh zut ... c'était une porte spatio-temporelle. Ah celle là c'est la bonne ---> []
# Re: Question existentielle

Posté par KiKouN le 15 décembre 2003 à 17:20. Évalué à 2.

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).
- [^] # Re: Question existentielle
  
  Posté par N-Mi le 15 décembre 2003 à 18:47. É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 le 16 décembre 2003 à 10:10. É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.
# Le plus simple.

Posté par pasPierre pasTramo le 15 décembre 2003 à 17:40. Évalué à 1.

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

Posté par grafit le 15 décembre 2003 à 18:20. Évalué à 2.

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 ;)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.