PureBasic

Bonjour,

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 "=========================================="

Salut Julien,
intéressant d'autant que je ne connaissais pas cette méthode et j'avoue que je n'ai pas tout compris...
Le test a réussi avec le debugger sur Win11 pro x64 et avec PB6.30.
Par contre le Input() à la fin sans la console fait planter. Il faut le commenter ou le retirer.

Merci, corrigé

PureBasic

Implémentation de Shamir Secret Sharing

Implémentation de Shamir Secret Sharing

Re: Implémentation de Shamir Secret Sharing

Re: Implémentation de Shamir Secret Sharing