Partage de secret de Shamir : mathématiques polynomiales

Le partage de secret de Shamir (1979) encode le secret comme l’ordonnée à l’origine (f(0)) d’un polynôme aléatoire de degré (k-1) sur un corps fini. N’importe quels k points déterminent de manière unique le polynôme (interpolation de Lagrange) ; moins de k points ne révèlent rien.

Pour partager le secret S avec un seuil k entre n parties : choisissez un nombre premier p > S et n. Choisissez des coefficients aléatoires a_1, ..., a_{k-1}. Définissez f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). La partie i reçoit la part (i, f(i)).

Secret S=7, p=17, k=2 (polynôme linéaire). Choisissez a_1=3. f(x)=7+3x mod 17. Parts : (1,10), (2,13), (3,16). Deux points quelconques déterminent la droite. f(0)=7. Un seul point : une infinité de droites possibles, et aucune information sur S.

Étant donné k points (x_1,y_1),...,(x_k,y_k), reconstruisez f(0) à l’aide de Lagrange : S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Tous les calculs sont modulaires. Aucun calcul en virgule flottante : la reconstruction est exacte dans le corps fini.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

Pour k-1 parts, il existe exactement un polynôme de degré k-1 passant par ces k-1 points pour chaque valeur secrète possible S. Ainsi, en connaissant k-1 parts, chaque valeur de S dans [0, p-1] est équiprobable : aucune information n'est révélée.

p doit être supérieur au secret et à n. Un choix courant est p = 2^127-1 (nombre premier de Mersenne) pour les secrets de 128 bits. Cela garantit que toutes les parts tiennent sur 128 bits et que les calculs sont efficaces. Vous pouvez aussi utiliser p=2^521-1 pour les secrets de 512 bits.

Le SSS de base ne garantit pas l'intégrité des parts : un détenteur malveillant peut soumettre une fausse part, ce qui entraîne une reconstruction incorrecte du secret. Le VSS de Feldman (partage de secret vérifiable) publie des engagements g^{a_i} mod p, ce qui permet de vérifier les parts sans révéler le polynôme.

Les parts peuvent être renouvelées périodiquement : générez un nouveau polynôme avec le même secret S, redistribuez de nouvelles parts, puis les anciennes parts deviennent invalides. Un attaquant qui compromet un détenteur après le renouvellement obtient une ancienne part inutilisable. Cette technique est utilisée dans les systèmes de gestion de clés à longue durée de vie.

ssss (ligne de commande Linux), python-secret-sharing, hashicorp/vault utilise le SSS pour son mécanisme de scellement, et le portefeuille matériel Trezor utilise le SSS pour sauvegarder la graine du portefeuille (SLIP-39). Tous fonctionnent sur de grands corps finis premiers.

Le SSS nécessite un distributeur de confiance pour générer et distribuer les parts (le distributeur connaît le secret). En l'absence de distributeur, il faut utiliser le DKG (génération distribuée de clés). La reconstruction révèle le secret à toute personne détenant k parts — ce problème est éliminé par le MPC et les signatures à seuil.

Dans le partage de secret de Shamir (3,5), quel est le nombre minimal de parts nécessaires pour reconstruire le secret ?

Le SSS de Shamir code les secrets comme des ordonnées à l'origine de polynômes. L'interpolation de Lagrange récupère le secret à partir de k parts. Il offre une sécurité parfaite au sens de la théorie de l'information avec moins de k parts. Ensuite : le partage de secret visuel et additif.