Shut ! J’ai un secret en Python… 6


J’adore les chasses au trésor. Préparer les énigmes, suivre les participants, c’est bien plus marrant que de faire partie d’une des équipes. Je me suis toujours dit que si je devenais obscènement riche, j’achèterais 10 millions d’euros en pièces d’or et je les planquerais quelque part, puis je lancerais une chasse au trésor mondiale pour le fun. Des années de préparation, des années d’amusement !

Une des problématiques de la chasse au trésor, c’est de s’assurer que tout le monde a une chance. Il faut varier les épreuves: musique, littérature, observation, orientation, histoire, puzzle, exercice physique, etc. Et bien sûr il faut créer un système tolérant à l’échec, car le but c’est quand même que quelqu’un trouve le butin. La meilleure partie est après tout ce très court moment d’exultation où on ouvre le coffre, ou son équivalent.

Quand c’est une chasse au trésor pour mioches, c’est facile, il suffit de donner un temps d’avance à l’équipe qui réussi une épreuve en premier, de balancer un indice, de retirer une contrainte, etc. Au pire on saute juste une épreuve.

Dans une grosse chasse au trésor, il faut faire quelque chose de plus sérieux: on doit limiter son interaction au maximum avec les équipes pour leur donner une sensation d’aventure, et de challenge.

La solution à ce problème, c’est d’utiliser des indices divisibles:

  • prendre l’indice suivant;
  • le diviser en morceaux;
  • permettre de recoller les morceaux, et obtenir l’indice même quand on ne les a pas tous.

Ainsi, si on a 5 épreuves, on prend l’indice suivant, on le divise en 5, et on s’assure que réussir 3 épreuves suffisse à donner assez d’informations pour reconstituer l’indice suivant. Ca marche avec les cartes incomplètes, les textes à trou, les dessins superposables, etc.

En informatique il existe un moyen de faire cela avec le partage de clé secrète de Shamir. Et bien sûr, comme toujours, il y a une lib Python qui permet de s’en servir.

Malheureusement, comme beaucoup de libs scientifiques, elle est bien chiante à installer et elle ne respecte pas le PEP8:

D’abord il vous faut installer pycrypto, une dépendance:

pip install pycryto

Assurez-vous d’avoir les headers de Python (paquet python-dev sous Ubuntu), car c’est une extension en C que pip va compiler.

Ensuite, on doit cloner le repo à la main (si, si):

git clone https://code.google.com/p/python-secret-sharing/

Et copier le dossier nommé ‘ss’ (un truc aussi strict, c’est forcément les nazis j’vous dis) dans le dossier de votre application ou dans votre dossier de site-package. Si j’ai le temps je leur proposerais un petit setup.py.

Ensuite ça s’utilise très facilement:

>>> from ss.secret_sharing import secret_sharing
>>> secret = secret_sharing("1 - voler des caleçons. 2 - .... 3 - profit !", 20, 3)

Ceci va produire un secret divisible en 20 parts, donc il ne faut que 3 parts pour relire le secret de conquête du monde que j’ai planqué dans cette citation pleine de sagesse.

Je peux obtenir une part au hasard:

>>> secret.share_random() 
((16, 721654044499788854347597992565674L),
 (18,
  102214856329848326909206303519239813304695812929767500268700035275955811306374521388L))

Notez que c’est un simple tuple. On peut en faire des choses avec un simple tuple, comme le serialiser, le compresser, l’obfusquer, l’encoder, le sténographier…

Et si je veux retrouver le secret:

>>> from ss.secret_sharing_c import secret_sharing_c
>>> assembleur = secret_sharing_c()
>>> assembleur.add_share(secret.share_random())
>>> assembleur.add_share(secret.share_random())
>>> assembleur.add_share(secret.share_random())
>>> print assembleur.reconstruct()
1 - voler des caleçons. 2 - .... 3 - profit !

Attention: si on met moins ou plus de parts dans l’assembleur que prévu, il s’auto-poutre avec un salami en bêton bardé de ZeroDivisionError ou OverflowError.

Bref, comme d’habitude l’informatique peut être fun, fun, fun. Je me demande pourquoi on enseigne jamais ça en cours. C’est quand même plus marrant que de créer des fonctions de manipulation de graphes en Java comme on avait eu la bonne idée de nous faire faire.

6 thoughts on “Shut ! J’ai un secret en Python…

  • Recher

    Lui, là, il a codé du Shamir’s Secret en python :
    https://github.com/hbs/PySSSS

    J’ai rien testé, je ne sais pas si ça fonctionne. Mais ça m’a l’air d’avoir moins de dépendance et de difficultés d’installation que la lib dont tu nous parles.

    Le nom de son repository fait penser à quelqu’un en train de pisser, c’est déjà un premier bon point.

  • JeromeJ

    Ah ouais … j’imagine déjà plein d’applications !

    Vraiment juste dommage pour l’installation :/

  • Sam Post author

    @Recher: pas de doc. Arg.

    @Ouai je leur ai pondu et posté un setup.py et suggéré une mise en ligne sur pypi (avec didacticiel) mais pour le moment pas de réponse.

  • François

    Et les sources sans le numéro de version dans le nom, c’est pas cool pour les empaqueteurs. :(

  • Baronsed

    En bash : ssss-split et ssss-combine. SSSS pour Shamir’s secret sharing scheme (le libre et les acronymes ^^).

  • Poisson

    C’est dommage que ça bug si l’on ajoute plus de part que de nécessaire, rien dans l’algorithme de base ne force à en avoir pile le bon nombre..

Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.