Journal Question existentielle

Posté par  .
Étiquettes : aucune
0
15
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  . É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  . Évalué à 5.

      A mon avis, ca part en boucle infinie
    • [^] # Re: Question existentielle

      Posté par  . É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  . É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  . É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  . É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  . É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  (site web personnel) . É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  . É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  . É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  (site web personnel, Mastodon) . É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  . É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  . É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  (site web personnel) . É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  . É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  . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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.