Association Ergodis/Tirage au sort

Le problème

Les statuts de l’association Ergodis stipulent que :

« Après épuisement de l’ordre du jour, on procède au renouvellement du Collège. Ensuite l’AG élit les nouveaux secrétaire et trésorier parmi les membres du Collège. […] Un tirage au sort désigne le représentant légal de l’année parmi les membres restants du Collège. »

Chaque année, se pose donc la question de comment réaliser le tirage au sort du ou de la représentant(e) légal(e) parmi les membres du Collège (autres que le trésorier ou la trésorière et le ou la secrétaire), ce d’autant plus que les assemblées générales ont lieu sur IRC. Faut-il faire confiance à une personne pour réaliser le tirage au sort ? Si oui, comment vérifier que tout cela a bien été sincère et sans trucage ?

La solution

Pour répondre à ce problème, une solution simple peut consister en un tirage pseudoaléatoire à partir de mots clefs utilisant des fonctions de hachage cryptographiques. L’algorithme est le suivant :

chaque personne présente sur le chat IRC donne un mot (par exemple zoulou, trompette ou macaque) ;
on concatène tous les mots, dans l’ordre dans lequel ils ont été donnés, pour obtenir la clef d’initialisation (ici : zoulou trompette macaque) ;
pour chaque membre du Collège solidaire éligible, on calcule le hash de la chaîne de caractère [clef] + [nom], par exemple (si les membres sont Alice, Bob et Charlie) : zoulou trompette macaqueAlice, zoulou trompette macaque Bob et zoulou trompette macaque Charlie. La fonction de hachage est une moulinette mathématique qui, à partir de la chaîne de caractère, donne un nombre^[1] ;
le membre pour lequel ce procédé a donné le nombre le plus petit est élu.

Pour mettre en œuvre cet algorithme, on peut utiliser le script Python suivant (à copier-coller dans un interpréteur Python, ou dans un fichier texte puis exécuter, après avoir mis la bonne clef et la bonne liste de participants) :

#!/usr/bin/python3

"""
Script de tirage au sort d’une personne parmi les membres du collège EGD.

Entrée :
 * Une clef d’initialisation quelconque pour simuler du hasard. En
   pratique, des mots quelconques donnés par les participants.
 * Une liste de pseudonymes de personnes participant au tirage au
   sort.

Sortie :
 * Un nom tiré de façon pseudoaléatoire, avec un aléa reproductible.

Traitement :
 * Pour chaque pseudo de personne participant au tirage, la chaîne du nom
   est concaténée avec la clef.
 * La chaîne concaténée ainsi obtenue est passée dans une fonction de
   hachage (en l’occurrence, sha512), ie une fonction générant une
   empreinte irréversible et imprévisible.
 * Les noms sont ordonnés en fonction du hash ainsi généré.
 * Le premier (dans l’ordre croissant des hash) est retenu.
"""

clef = "Pinage tartiflette hydroprêtre nauséabond Elections"
participants = [
    "Caracole",
    "Galex-13",
    "Mimoza",
    "Gildev",
]

def calcule_hash(nom):
    import hashlib
    return hashlib.sha512((clef + nom).encode("utf8")).hexdigest()

participants.sort(key=calcule_hash)

print(participants[0])

Éléments d’attention

Le résultat du tirage au sort n’est pas sensible à l’ordre dans lequel sont mentionnés les participants. Par contre, il est sensible à la casse, aux espaces, ou encore aux absents. Bien évidemment, le moindre changement dans la clef (l’ordre des mots, la présence d’espaces entre les mots, etc.).

Il faut donc s’entendre à l’avance sur quelques détails pour éviter toute contestation du résultat. On utilisera les conventions suivantes :

une personne est désignée (ou se désigne…) volontaire pour « présider » le tirage au sort ;
la personne qui préside demande aux participants de donner un mot. Pendant 60 secondes, les membres peuvent donner un ou deux mots^[2]. Il faut qu’au moins deux membres aient donné un mot pour que le résultat soit valide. Le président ou la présidente ne donne pas de mots ;
les mots sont repris tels quels, en respectant la casse et l’accentuation. S’il y a une faute d’orthographe, ce n’est pas grave. De même si le mot qui est donné est un nom propre ou n’est pas français. Seuls les 42 lettres et graphèmes du français (capitales et bas de casse) et le tiret (tiret ASCII, figurant sous le chiffre 8 en BÉPO) sont acceptés ;
les mots sont repris dans l’ordre dans lequel ils apparaissent sur le serveur. En cas de contestation sérieuse, on recommence le choix des mots ;
les mots formant la clef sont séparés par une espace exactement ;
chaque candidat(e) est désigné(e) par son pseudo IRC. Si le membre n’a pas de pseudo IRC et est connecté par Discord, alors on utilise son pseudo Discord.

Le résultat du tirage ne dépend pas de la personne exécutant le script. Il est donc recommandé que le président ou la présidente de séance reprenne le code ci-dessus, remplisse la clef et les pseudos conformément aux règles qui précèdent, et partage le code source ainsi modifié (par exemple en le partageant sur un privatebin). Toute personne qui exécuterait ce code obtiendrait le même résultat.

Exemple concret de mise en pratique

L’exemple suivant est factice et inventé.

Supposons par exemple que les membres du collège autres que trésorier et secrétaire soient (pseudos IRC) : Flavien, Chouhartem, Arathor, Mimoza et SardemFF7. On pourrait avoir :

22:13:04 <GilDev>	Je peux m’occuper du tirage au sort si vous voulez ! On utilise l’algo qui est donné sur le wiki <https://bepo.fr/wiki/Association_Ergodis/Tirage_au_sort>
22:13:25 <Chouhartem>	Pour
22:13:35 <GilDev>	Pour
22:14:05 <Bepo>	<Morph> Pour
22:14:15 <Arathor>	hum en fait on va faire un tir groupé
22:15:30 <GilDev>	OK, dont les participants sont Flavien, Chouhartem, Arathor, Mimoza et SardemFF7. Ça ferait : participants = ["Flavien", "Chouhartem", "Arathor", "Mimoza", "SardemFF7"]
22:15:48 <GilDev>	À mon top, tout le monde donne un mot ou deux, pendant les 60 prochaines secondes, ok ?
22:15:57 <GilDev>	TOP !
22:15:59 <Arathor>	zèbre
22:16:03 <Bepo>	<Morph> hippie
22:16:04 <SardemFF7>	Poulet
22:16:08 <Bepo>	<Morph> Youpiiie
22:16:23 <Zluglu>	clavier
22:16:32 <Chouhartem>	Arathor
22:16:39 <Milton>	amphithéâtre
22:16:54 <Chouhartem>	manger
22:16:55 <Flavien>	épinard
22:17:01 <GilDev>	stop stop, c’est fini !
22:17:23 <GilDev>	cela donne donc clef = "zèbre hippie Poulet Youpiiie clavier Arathor amphithéâtre manger épinard"
22:17:29 <GilDev>	avec trois i à Youpiiie
22:17:54 <GilDev>	je copie donc le script complet à l’adresse suivante, vous pouvez vérifier : <https://paste.chapril.org/?9105780c3b777166#2cnR1h9zYYfmSQzqYFLoVvajY1tdcCktgdw9QiSxW4dM>
22:18:07 <GilDev>	et l’heureuse élue est donc : SardemFF7
22:18:13 <GilDev>	tout le monde peut bien sûr vérifier le résultat !

Limites

Le choix des mots influe, de façon déterministe, sur le résultat. La personne qui donne le dernier mot pourrait donc en théorie, en choisissant bien celui-ci, influencer le résultat du tirage. Cependant, dans le cas où les membres donnent les mots à la suite en seulement quelques dizaines de secondes, la mise en œuvre pratique d’une fraude serait fastidieuse d’un point de vue pratique, et le jeu n’en vaudrait certainement pas la chandelle.

Cet algorithme est par exemple celui qui est utilisé pour tirer au sort l’attribution des chambres à l’internat de l’ÉNS Ulm, depuis des années. Il a, dans ce contexte^[3], largement démontré sa robustesse, alors même que l’enjeu est beaucoup plus important (le résultat du tirage détermine qui aura une chambre ou non).

Notes

↑ Souvent représenté en hexadécimal, c’est-à-dire qu’on l’écrit avec des nombres et les lettres de a à f, par exemple : 9875ef8c766b93f qui donne l’impression d’être aléatoire : il est impossible de savoir quel nombre sortira avant d’avoir fait le calcul complet, ce qui prend un certain temps.
↑ Pas plus, pour éviter le flood.
↑ L’enjeu est bien plus important, mais la fraude est aussi plus difficile à mettre en œuvre car les mots sont donnés à l’oral, en présentiel, et que les participants ne peuvent donc pas être en parallèle sur leur ordinateur occupés à faire tourner un script optimisant le choix du mot.

[1] Souvent représenté en hexadécimal, c’est-à-dire qu’on l’écrit avec des nombres et les lettres de a à f, par exemple : 9875ef8c766b93f qui donne l’impression d’être aléatoire : il est impossible de savoir quel nombre sortira avant d’avoir fait le calcul complet, ce qui prend un certain temps.

[2] Pas plus, pour éviter le flood.

[3] L’enjeu est bien plus important, mais la fraude est aussi plus difficile à mettre en œuvre car les mots sont donnés à l’oral, en présentiel, et que les participants ne peuvent donc pas être en parallèle sur leur ordinateur occupés à faire tourner un script optimisant le choix du mot.

[1]

[2]

[3]