Partage secret de Shamir

17

Étant donné n(le nombre de joueurs), t(la valeur seuil) et s(le secret), sortez les nsecrets générés par l'algorithme de partage de secrets de Shamir .

L'algorithme

Aux fins de ce défi, les calculs seront effectués en GF (251) (le champ fini de taille 251, autrement connu comme les entiers mod 251 ). Normalement, le champ serait choisi de telle sorte que sa taille soit un nombre premier bien supérieur à n. Pour simplifier le défi, la taille du champ sera constante. 251a été choisi car il s'agit du plus grand nombre premier représentable par un entier non signé 8 bits.

  1. Générez t-1des entiers aléatoires dans la plage (inclusive) [0, 250]. Marquez ces un 1 par un t-1 .
  2. Construire un t-1polynôme de th degré en utilisant scomme valeur constante et les entiers aléatoires de l'étape 1 comme coefficients des puissances de x: f (x) = s + x * a 1 + x 2 * a 2 + ... + x t- 1 * un t-1 .
  3. Sortie (f(z) mod 251)pour chacun zdans la plage (incluse) [1, n].

Implémentation de référence

#!/usr/bin/env python
from __future__ import print_function
import random
import sys

# Shamir's Secret Sharing algorithm
# Input is taken on the command line, in the format "python shamir.py n t s"

n, t, s = [int(x) for x in sys.argv[1:4]]
if t > n:
    print("Error: t must be less than or equal to n")
    exit()
if n not in range(2, 251):
    print("Error: n must be a positive integer less than 251")
    exit()
if t not in range(2, 251):
    print("Error: t must be a positive integer less than 251")
    exit()
if s not in range(251):
    print("Error: s must be a non-negative integer less than 251")
    exit()
p = 251
a = [random.randrange(0, 251) for x in range(t-1)]

def f(x):
    return s + sum(c*x**(i+1) for i,c in enumerate(a))

# Outputting the polynomial is for explanatory purposes only, and should not be included
#  in the output for the challenge
print("f(x) = {0} + {1}".format(s, ' + '.join('{0}*x^{1}'.format(c, i+1) for i,c in enumerate(a))))
for z in range(1, n+1):
    print(f(z) % p)

Vérification

L'extrait de pile suivant peut être utilisé pour vérifier les sorties:

Afficher l'extrait de code

Règles

  • ssera un entier non négatif inférieur à 251, et net tsera un entier positif inférieur 251et supérieur à 1. De plus, vous êtes assuré que les entrées sont valides (ce qui signifie t <= n).
  • L'entrée et la sortie peuvent être dans n'importe quel format raisonnable, sans ambiguïté et cohérent.
  • Les nombres aléatoires doivent être échantillonnés à partir d'une distribution uniforme - chaque valeur possible devrait avoir une probabilité égale d'être choisie.
code-golf number-theory random cryptography polynomials code-golf number code-golf math number sequence code-golf quine code-generation code-golf arithmetic set-theory code-golf sequence code-golf code-golf string math fastest-code optimization code-golf code-golf internet stack-exchange-api code-golf array-manipulation code-golf string internet string code-challenge internet test-battery code-golf math pi code-golf arithmetic primes code-golf array-manipulation code-golf string code-golf string palindrome code-golf sequence number-theory fastest-algorithm code-golf math number base-conversion code-golf number-theory sorting subsequence search code-golf permutations code-challenge popularity-contest code-generation Mego
la source
1
Doit-on sortir z et f(z) ? Si j'imprime un tableau de f(z)s dans l'ordre, zest impliqué par index. [[1, 5], [2, 2], [3, 9], [4, 14]]ne contient pas plus d'informations que [5, 2, 9, 14].
orlp
1
Défi pour faire l'inverse .
FryAmTheEggman
@orlp Fair point.
Mego
Des tests?
Leaky Nun
4
@LeakyNun Étant donné que cette question est étiquetée au hasard , je pense que l'extrait de vérification est beaucoup plus précieux que les cas de test qui varieront pour chaque exécution.
FryAmTheEggman

Réponses:

13

Gelée , 15 octets

251©xX€⁵0¦ḅЀ%®

Attend t , n et s comme arguments de ligne de commande. Essayez-le en ligne!

Comment ça fonctionne

251©xX€⁵0¦ḅЀ%®  Main link. Left argument: t. Right argument: n Third argument: s

251©             Yield 251 and copy it to the register.
    x            Repeat [251] t times.
     X€          Random choice each; pseudo-randomly choose t integers from
                 [1, ..., 251]. Since 251 = 0 (mod 251), this is equivalent to
                 choosing them from [0, ..., 250].
       ⁵0¦       Replace the last generated integer (index 0) with s (⁵).
          ḅЀ    Interpret the resulting array as a base-k number, for each k in
                 [1, ..., n], and convert to integer.
              ®  Yield 251 from the register.
             %   Take the generated integers modulo 251.
Dennis
la source
3
Remplacer le dernier entier est si élégant :)
Lynn
8

Mathematica, 59 56 octets

Mod[Power~Array~{#2,#-1}.RandomInteger[250,#-1]+#3,251]&

Prend trois arguments dans l'ordre t , n et s . Construit un tableau 2D avec n lignes et t -1 colonnes. Chaque vecteur ligne j , numéroté de 1 à n , contient les puissances de j à j t -1 . Ensuite, un vecteur de coefficients entiers aléatoires compris entre 0 et 250 est créé avec des valeurs t -1. Cela est multiplié par matrice avec le tableau 2d, puis s est ajouté par élément et pris le module 251 pour obtenir la valeur du polynôme en chacun des n points.

miles
la source
1
Était sur le point de publier une réponse de 79 octets, bonne astuce avec Sum!
LegionMammal978
1
J'ai une approche différente, mais c'est actuellement deux octets de plus. Vous avez peut-être une idée de comment le raccourcir:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Martin Ender
3

Pyth, 24 octets

J+EmOK251tEm%s.e*b^dkJKS

Essayez-le en ligne!

Ordre d'entrée: n s tséparé par un saut de ligne.

Leaky Nun
la source
arrrrrgh, ninja'd cuz je suis allé chercher un cookie
Maltysen
3

JavaScript, 181 octets

(n,t,s)=>{r=Array(t-1).fill(0).map($=>{return Math.random()*251});f=(x=>{p = 0;r.map((k,c)=>p+=k*Math.pow(x, c));return s+p});_=Array(t-1).fill(0);_.map((l,i)=>_[i]=f(i));return _;}

Non golfé:

(n, t, s) => {
    r = Array(t - 1).fill(0).map($ =>{return Math.random() * 251});
    f = (x => {
        p = 0;
        r.map((k, c) => p += k * Math.pow(x, c));
        return s + p
    });
    _ = Array(t - 1).fill(0);
    _.map((l, i) => _[i] = f(i));
    return _;
}

Je ne sais pas comment le vérifier correctement, mais je sais que c'était difficile de faire en sorte que JS mappe sur un nouveau tableau car il .mapsaute apparemment des valeurs non définies. Si quelqu'un voit des moyens de s'améliorer ou des défauts, n'hésitez pas à me le faire savoir.

charredgrass
la source
123 octets:(n,t,s,A=f=>Array(t-1).fill(0).map(f),r=A($=>Math.random()*251))=> A((l,i,_,p=0)=>(r.map((k,c)=>p+=k*Math.pow(i,c)),s+p))
Dendrobium
Vous n'utilisez pas n, ce qui semble faux. Votre code semble également supposer une indexation basée sur 1. [...Array()]est légèrement plus courte que fiil(). De plus, les deux dernières lignes peuvent être réduites àreturn _.map(f);
Neil
3

C #, 138 134 octets

(n,t,s)=>new int[n+1].Select((_,x)=>(s+new int[t-1].Select(k=>new Random(e).Next(251)).Select((c,i)=>c*Math.Pow(x+1,i+1)).Sum())%251);

C # lambda où les entrées sont intet la sortie est un IEnumerable<double>. Vous pouvez essayer mon code sur .NetFiddle .

Je ne suis pas sûr à 100% de la validité de mon algorithme, veuillez commenter si j'ai mal compris quelque chose.

4 octets enregistrés avec le truc de @ raggy .

aloisdg passe à codidact.com
la source
3

MATL , 20 19 octets

251tliq3$Yrihi:ZQw\

Commande d' entrée est t, s, n.

Essayez-le en ligne!

Explication

251t    % Push 251 twice
l       % Push 1
iq      % Take input t. Subtract 1
3$Yr    % Generate t-1 random integers in [1 2 ... 251]
ih      % Take input s. Concatenate with the random integers
i:      % Take input n. Generate range [1 2 ... n]
ZQ      % Evvaluate polynomial at those values
w       % Swap to move copy og 251 to the top of the stack
\       % Modulo. Implicitly display
Luis Mendo
la source
2

Julia, 48 octets

f(n,t,s)=(1:n).^(0:t-1)'*[s;rand(0:250,t-1)]%251

Essayez-le en ligne!

Dennis
la source
1

JavaScript (ES6), 116 octets

(n,t,s)=>[...Array(n)].map((_,i)=>++i&&t.reduce((r,a)=>r*i+a)%251,t=[...Array(t)].map(_=>--t?Math.random()*251|0:s))

J'aimerais penser que c'est l'un des rares cas où les reducebattements map.

Neil
la source
1

Python 3 avec NumPy , 103 octets

from numpy import*
lambda n,t,s:[poly1d(append(random.randint(0,251,t-1),s))(i+1)%251for i in range(n)]

Je peux honnêtement dire que je ne m'attendais pas à utiliser NumPy pour le golf de code ...

Une fonction anonyme qui prend une entrée via un argument et renvoie une liste.

Comment ça fonctionne

from numpy import*         Import everything in the NumPy library
lambda n,t,s...            Function with input number of players n, threshold value t and
                           secret s
random.randint(0,251,t-1)  Generate a NumPy array R of t-1 random integers in [0,250]
append(...,s)              Append s to R
poly1d(...)                Generate a polynomial p of order t-1 with coefficients R and
                           constant term s
...for i in range(n)       For all integers i in [0,n-1]...
...(i+1)                   ...evaluate p(i+1), so for all integers in [1,n]...
...%251                    ...and take modulo 251
...:[...]                  return as list

Essayez-le sur Ideone

TheBikingViking
la source
1

J , 32 30 octets

251|(1+i.@{.)p.~{:0}251?@#~1&{

Prend une liste avec les valeurs n , t et s .

Enregistrement de 2 octets en utilisant l' idée de remplacement à l'index 0 de la solution de @ Dennis .

Explication

251|(1+i.@{.)p.~{:0}251?@#~1&{  Input: [n t s]
                           1&{  Select at index 1 (t)
                    251  #~     Create that many copies of 251
                       ?@       Generate that many random integers in [0, 251)
                {:              Get the tail of the input (s)
                  0}            Replace the value at index 0 of the random integer list
                                with s to make a coefficient list of the polynomial
          {.                    Get the head of the input (n)
       i.@                      Make the range [0, n-1]
     1+                         Add 1 to each to get [1, n]
             p.~                Evaluate the polynomial at each value [1, n]
251|                            Take each value mod 251 and return
miles
la source
0

Java 8, 224 octets:

(n,t,s)->{int[]W=new int[t-1];for(int i=0;i<t-1;i++){W[i]=new java.util.Random().nextInt(251);};long[]O=new long[n];for(int i=1;i<=n;i++){long T=0;for(int h=1;h<t;h++){T+=W[h-1]*Math.pow(i,h);}O[i-1]=((T+s)%251);}return O;};

Une expression lambda Java 8. Génère un tableau d'entiers séparés par des virgules et fonctionne parfaitement jusqu'à ce que les valeurs du tableau de sortie dépassent la plage du longtype de données Java ou entier signé 64 bits, sur lequel -200est sorti dans le tableau.

Essayez-le en ligne! (Ideone)

R. Kap
la source