Ce code est une implémentation open-source en PureBasic du Shamir Secret Sharing Scheme, un procédé cryptographique qui permet de diviser un secret en plusieurs parts, de telle sorte que toute combinaison d’au moins T parts puisse reconstituer le secret original, tandis qu’un nombre inférieur à T parts ne fournit aucune information exploitable.
L’algorithme fonctionne ici sur le corps fini GF(257), ce qui permet de traiter correctement chaque octet (0-255) et rend le système compatible avec tout type de chaîne de caractères.
Principe de fonctionnement (résumé)
Le secret est utilisé comme premier coefficient d’un polynôme aléatoire de degré (T−1).
Chaque part correspond à l’évaluation de ce polynôme sur un point x différent.
La reconstitution utilise l’interpolation de Lagrange en x=0 pour retrouver le secret.
Avec moins de T parts, la reconstruction est mathématiquement impossible.
Ce mécanisme est utilisé dans de nombreux domaines :
sécurité des clés, portefeuilles matériels, sauvegardes cryptées, systèmes d’accès multi-personnes, etc.
Fonctions principales disponibles
1. Shamir_CreateShares(secret$, nombreÀGénérer, seuil, List parts()) → Bool
Génère la liste des parts.
Chaque part contient :
x → indice unique de la part
values → chaîne hexadécimale représentant les fragments du secret
2. Shamir_ReconstructSecret(List parts()) → String
Reconstruit le secret initial à partir de n’importe quel ensemble de parts satisfaisant le seuil.
Utilitaires inclus
PrintShares() pour afficher les parts générées
Code entièrement converti en anglais au niveau des noms de fonctions / paramètres
Commentaires et structure propre, prêt à intégrer dans un projet PureBasic
Licence
Ce code est fourni en Open-Source, licence de type MIT.
Vous pouvez l’utiliser, l’adapter et le redistribuer librement.
Code : Tout sélectionner
; ============================================================================
; Shamir Secret Sharing - Implementation PureBasic - By Julien www.emjysoft.com
; Niveau pédagogique / démonstration (NON industriel)
; ============================================================================
#PREMIER = 257
Structure Part
x.i
valeurs.s ; Chaine hexadecimale des valeurs y (3 hex par valeur)
EndStructure
; ============================================================================
; Retourne toujours un modulo positif
; ============================================================================
Procedure.i ModuloPositif(a.i, m.i)
Protected resultat.i = a % m
If resultat < 0
resultat = resultat + m
EndIf
ProcedureReturn resultat
EndProcedure
; ============================================================================
; Inverse modulaire via Euclide etendu (itératif, robuste)
; Retourne 0 si pas d'inverse (gcd != 1)
; ============================================================================
Procedure.i InverseModulaire(a.i, m.i)
Protected a0.i = ModuloPositif(a, m)
Protected m0.i = m
Protected x0.i = 1
Protected x1.i = 0
Protected q.i, t.i, tmp.i
; Cas trivial
If m0 = 1
ProcedureReturn 0
EndIf
While m0 <> 0
q = a0 / m0
t = a0 % m0
a0 = m0
m0 = t
tmp = x1
x1 = x0 - q * x1
x0 = tmp
Wend
; a0 contient le gcd
If a0 <> 1
ProcedureReturn 0 ; pas d'inverse
EndIf
ProcedureReturn ModuloPositif(x0, m) ; x0 peut être négatif -> normaliser
EndProcedure
; ============================================================================
; Evalue un polynome en x modulo 'premier'
; coefficients() : coefficients(0) = a0, ...
; ============================================================================
Procedure.i EvaluePolynome(x.i, Array coefficients.i(1), premier.i)
Protected resultat.i = 0
Protected i.i
Protected terme.i
Protected puissance.i = 1
Protected limite.i = ArraySize(coefficients())
For i = 0 To limite
terme = ModuloPositif(coefficients(i) * puissance, premier)
resultat = ModuloPositif(resultat + terme, premier)
puissance = ModuloPositif(puissance * x, premier)
Next
ProcedureReturn resultat
EndProcedure
; ============================================================================
; Multiplication modulaire (sécurisée)
; ============================================================================
Procedure.i MultiplicationModulaire(a.i, b.i, m.i)
Protected resultat.q = (a * b) % m
If resultat < 0
resultat = resultat + m
EndIf
ProcedureReturn resultat
EndProcedure
; ============================================================================
; Interpolation de Lagrange : retourne P(0) modulo premier
; points_x(), points_y() : tableaux d'entiers (indices 0..n-1)
; ============================================================================
Procedure.i InterpolationLagrange(Array points_x.i(1), Array points_y.i(1), premier.i)
Protected resultat.i = 0
Protected i.i, j.i
Protected numerateur.i, denominateur.i
Protected terme.i, inv.i
Protected taille.i = ArraySize(points_x())
For i = 0 To taille
numerateur = 1
denominateur = 1
For j = 0 To taille
If i <> j
; pour x=0 : (0 - x_j) / (x_i - x_j)
numerateur = ModuloPositif(numerateur * ModuloPositif(0 - points_x(j), premier), premier)
denominateur = ModuloPositif(denominateur * ModuloPositif(points_x(i) - points_x(j), premier), premier)
EndIf
Next
inv = InverseModulaire(denominateur, premier)
If inv = 0
; pas d'inverse -> erreur (deux x identiques ou gcd != 1)
ProcedureReturn 0
EndIf
terme = ModuloPositif(points_y(i) * numerateur, premier)
terme = ModuloPositif(terme * inv, premier)
resultat = ModuloPositif(resultat + terme, premier)
Next
ProcedureReturn resultat
EndProcedure
; ============================================================================
; Generation des parts (stocke chaque y sur 3 hex chars pour éviter troncation)
; ============================================================================
Procedure.i Shamir_CreeClesPartagees(secret.s, nombre_de_cles_a_generer.i, nombre_de_cles_necessaires_pour_reconstitution.i, List parts.Part())
Protected i.i, j.i, x.i, y.i
Protected octet_secret.i
Protected Dim coefficients.i(nombre_de_cles_necessaires_pour_reconstitution - 1)
Protected taille_secret.i = Len(secret)
Protected valeurHex.s
If nombre_de_cles_necessaires_pour_reconstitution > nombre_de_cles_a_generer
Debug "Erreur : Le seuil ne peut pas etre superieur au nombre de cles a generer"
ProcedureReturn #False
EndIf
If nombre_de_cles_necessaires_pour_reconstitution < 2
Debug "Erreur : Le seuil doit etre au minimum de 2"
ProcedureReturn #False
EndIf
If taille_secret = 0
Debug "Erreur : Le secret ne peut pas etre vide"
ProcedureReturn #False
EndIf
ClearList(parts())
For x = 1 To nombre_de_cles_a_generer
AddElement(parts())
parts()\x = x
parts()\valeurs = ""
Next
RandomSeed(ElapsedMilliseconds())
For i = 1 To taille_secret
octet_secret = Asc(Mid(secret, i, 1))
coefficients(0) = octet_secret
For j = 1 To nombre_de_cles_necessaires_pour_reconstitution - 1
coefficients(j) = Random(#PREMIER - 1)
Next
ResetList(parts())
While NextElement(parts())
x = parts()\x
y = EvaluePolynome(x, coefficients(), #PREMIER)
; convertir y en 3 hex (padding à gauche) : 0 -> "000", 255 -> "0FF", 256 -> "100"
valeurHex = Hex(y)
While Len(valeurHex) < 3
valeurHex = "0" + valeurHex
Wend
parts()\valeurs + valeurHex
Wend
Next
ProcedureReturn #True
EndProcedure
; ============================================================================
; Reconstruction : on lit 3 hex par octet
; ============================================================================
Procedure.s Shamir_ReconstruitSecret(List parts.Part())
Protected secret_reconstitue.s = ""
Protected i.i, j.i
Protected nombre_octets.i
Protected nombre_parts.i = ListSize(parts())
Protected octet_secret.i
Protected valeur_hex.s
Protected Dim parts_x.i(nombre_parts - 1)
Protected Dim parts_y.i(nombre_parts - 1)
If nombre_parts < 2
Debug "Erreur : Au moins 2 cles sont necessaires pour reconstituer le secret"
ProcedureReturn ""
EndIf
ResetList(parts())
If FirstElement(parts())
nombre_octets = Len(parts()\valeurs) / 3
EndIf
For i = 1 To nombre_octets
j = 0
ResetList(parts())
While NextElement(parts())
parts_x(j) = parts()\x
valeur_hex = Mid(parts()\valeurs, (i - 1) * 3 + 1, 3)
parts_y(j) = Val("$" + valeur_hex)
j + 1
Wend
octet_secret = InterpolationLagrange(parts_x(), parts_y(), #PREMIER)
secret_reconstitue + Chr(octet_secret)
Next
ProcedureReturn secret_reconstitue
EndProcedure
; ============================================================================
; Affichage des parts
; ============================================================================
Procedure AfficherParts(List parts.Part())
Protected compteur.i = 1
Debug "=== Parts generees ==="
ResetList(parts())
While NextElement(parts())
Debug "Part " + Str(compteur) + " (x=" + Str(parts()\x) + ") : " + parts()\valeurs
compteur + 1
Wend
Debug ""
EndProcedure
; ============================================================================
; Programme principal (exemple)
; ============================================================================
Define secret.s = "Mon super secret"
Define nombre_de_cles_a_generer.i = 10
Define nombre_de_cles_necessaires_pour_reconstitution.i = 3
Define compteur.i
Define secret_reconstitue.s
NewList parts.Part()
NewList parts_pour_reconstitution.Part()
Debug "=========================================="
Debug "Test de Shamir Secret Sharing (corrigé)"
Debug "=========================================="
Debug ""
Debug "Secret original : " + secret
Debug "Nombre de cles a generer : " + Str(nombre_de_cles_a_generer)
Debug "Seuil de reconstitution : " + Str(nombre_de_cles_necessaires_pour_reconstitution)
Debug ""
If Shamir_CreeClesPartagees(secret, nombre_de_cles_a_generer, nombre_de_cles_necessaires_pour_reconstitution, parts())
Debug "✓ Generation des cles reussie !"
Debug ""
AfficherParts(parts())
; Test 1 : parts 1,3,7
ClearList(parts_pour_reconstitution())
ResetList(parts())
compteur = 1
While NextElement(parts())
If compteur = 1 Or compteur = 3 Or compteur = 7
AddElement(parts_pour_reconstitution())
parts_pour_reconstitution()\x = parts()\x
parts_pour_reconstitution()\valeurs = parts()\valeurs
EndIf
compteur + 1
Wend
Debug "=== Test 1 : Reconstitution avec 3 parts (1, 3, 7) ==="
secret_reconstitue = Shamir_ReconstruitSecret(parts_pour_reconstitution())
Debug "Secret reconstitue : " + secret_reconstitue
If secret = secret_reconstitue
Debug "✓ Test 1 reussi ! Les secrets correspondent."
Else
Debug "✗ Test 1 echoue. Les secrets ne correspondent pas."
EndIf
Debug ""
; Test 2 : parts 2,5,9
ClearList(parts_pour_reconstitution())
ResetList(parts())
compteur = 1
While NextElement(parts())
If compteur = 2 Or compteur = 5 Or compteur = 9
AddElement(parts_pour_reconstitution())
parts_pour_reconstitution()\x = parts()\x
parts_pour_reconstitution()\valeurs = parts()\valeurs
EndIf
compteur + 1
Wend
Debug "=== Test 2 : Reconstitution avec 3 autres parts (2, 5, 9) ==="
secret_reconstitue = Shamir_ReconstruitSecret(parts_pour_reconstitution())
Debug "Secret reconstitue : " + secret_reconstitue
If secret = secret_reconstitue
Debug "✓ Test 2 reussi ! Les secrets correspondent."
Else
Debug "✗ Test 2 echoue. Les secrets ne correspondent pas."
EndIf
Else
Debug "✗ Erreur lors de la generation des cles"
EndIf
Debug ""
Debug "=========================================="
