Shamir Secret Sharing

Un portefeuille est une application ou un appareil permettant de recevoir et d’envoyer des bitcoins. Anna veut une sauvegarde qui résiste à la perte de certains documents. Elle choisit trois sur cinq : cinq parts distinctes sont créées, et trois parts valides quelconques du même ensemble permettent de retrouver le secret. Elle peut en perdre deux, mais pas trois. Le nombre requis est le seuil ; en général, k parmi n signifie qu’il faut k des n parts créées et que l’on peut en perdre n−k. Mais le seuil ne reconnaît pas le consentement d’Anna. Si quelqu’un obtient trois parts, ou si leurs détenteurs s’entendent, ils retrouvent le même secret. Un seuil plus bas facilite la restauration, mais réduit aussi le groupe capable de l’effectuer sans Anna. [1] [6]

Anna gagne peu à placer les cinq fichiers dans un seul compte cloud. La perte ou la compromission du compte les touche tous simultanément. Une sauvegarde demande une répartition réfléchie, des indications sur la méthode et ses paramètres, ainsi qu’un essai de restauration sur un appareil de confiance. Si les héritiers doivent aussi pouvoir suivre ce plan, ils doivent savoir quoi chercher et comment le manipuler sans danger. Une nouvelle répartition aléatoire du même secret S produit un nouvel ensemble ; on ne mélange pas les anciennes et les nouvelles parts. Pourtant, un ancien ensemble suffisant permet toujours de retrouver S. Redistribuer les parts ne révoque donc pas une sauvegarde utilisable déjà divulguée et ne change pas le secret. [1] [4]

Lors d’une restauration ordinaire, le secret entier se retrouve sur un seul appareil. Si celui-ci est compromis, un attaquant peut le récupérer à cet instant. Si le secret est une Private Key, une valeur numérique secrète permettant de créer une signature numérique qui autorise une dépense, son détenteur peut ensuite signer sans réunir de nouvelles parts. Multisig exige au contraire plusieurs signatures selon les conditions de la dépense concernée. La signature à seuil existe aussi : un protocole MPC supplémentaire, un calcul commun sécurisé entre plusieurs participants, permet aux parts de contribuer à une signature sans reconstituer la clé entière. NIST distingue ces situations. Une part de Shamir ne met pas, à elle seule, en place ce protocole de signature. [3] [5] [6]

Deux programmes portant le nom Shamir ne savent pas nécessairement lire leurs parts respectives. Les opérations mathématiques, le codage des valeurs, les identifiants et l’appartenance à un même ensemble doivent correspondre. SLIP-39 est une norme concrète fondée sur cette méthode : elle ajoute une liste de mots, des métadonnées ou informations complémentaires, des groupes, du chiffrement et des contrôles d’erreurs. Le principe général n’est donc pas une invitation à découper soi-même une Seed Phrase existante. Avant de confier un portefeuille à cette sauvegarde, il faut connaître le format pris en charge et vérifier que la procédure prévue permet réellement sa restauration. [2]

Avec trois sur cinq, les conséquences de la perte de deux parts sont claires. Une part endommagée ou falsifiée peut en revanche conduire le calcul de base à un autre secret, au lieu de signaler un nombre insuffisant. La méthode seule ne garantit ni l’origine des parts ni l’honnêteté de leur créateur. La détection et la correction d’erreurs, ainsi que verifiable secret sharing, qui permet de vérifier que le partage est correct, sont des couches supplémentaires avec leurs propres hypothèses. SLIP-39 ajoute par exemple une somme de contrôle et une empreinte de vérification appelée digest. Cela ne signifie pas que toutes les applications de Shamir Secret Sharing ont les mêmes contrôles, ni qu’une somme correcte prouve une origine fiable. [2] [5]

Dans le schéma idéal, moins de k parts complètes ne donnent aucune information nouvelle sur S à un attaquant, même avec une puissance de calcul illimitée. Une part n’est donc pas un tiers visible des mots d’origine. Cette propriété suppose un bon aléa : les nombres utilisés pour le partage sont choisis indépendamment et avec la même probabilité. Des nombres prévisibles, leur réutilisation ou une fuite de données depuis la mémoire de l’appareil changent la situation. Les données de contrôle supplémentaires, comme le digest de SLIP-39, doivent également être examinées séparément. Et un mot de passe initial faible reste devinable par d’autres moyens, même après le partage de sa sauvegarde. [1] [2]

Prenons le petit secret S=5 et la règle f(x)=5+3*x mod 17. mod 17 signifie garder le reste de la division par 17. Trois parts sont les couples (1,8), (2,11), (3,14) : le premier nombre indique une position, le second la valeur calculée. Les deux premiers donnent l’accroissement 3 et le secret initial 8−3=5. Chacune des trois paires possibles de points retrouve ce même cinq. Le seul point (1,8) est pourtant compatible avec tout S de 0 à 16 si l’on choisit a=8−S mod 17 comme accroissement. Ces petits nombres illustrent le principe ; ils ne constituent pas une sauvegarde pour un vrai portefeuille. [1]

La règle générale est f(x)=S+a1*x+…+a(k−1)*x^(k−1). Cette expression est un polynôme ; S est le secret et les autres coefficients sont des éléments indépendants, tirés uniformément au hasard dans un corps fini, un cadre aux règles précises d’addition et de multiplication. Une part est (x,f(x)), avec chaque x distinct et non nul : x=0 révélerait directement S. À partir de k points, l’interpolation de Lagrange calcule f(0), le secret. Deux copies du même point n’ajoutent aucune information. Dans le corps premier GF(p), la division ordinaire est remplacée par une multiplication par l’inverse modulaire, dont le produit avec le diviseur vaut 1. GF(256) emploie aussi une arithmétique différente des simples restes modulo 256 ; les confondre serait une erreur. [1]