Shamir's Secret Sharing

17

Biorąc pod uwagę n(liczbę graczy), t(wartość progową) i s(sekret), ngeneruj sekrety generowane przez algorytm Shamir's Secret Sharing .

Algorytm

Na potrzeby tego wyzwania obliczenia zostaną wykonane w GF (251) (skończone pole wielkości 251, znane również jako liczby całkowite mod 251 ). Zazwyczaj pole jest wybierane w taki sposób, że jego wielkość jest liczbą pierwszą znacznie większą niż n. Aby uprościć wyzwanie, wielkość pola będzie stała. 251został wybrany, ponieważ jest największą liczbą pierwszą reprezentowaną przez 8-bitową liczbę całkowitą bez znaku.

  1. Generuj t-1losowe liczby całkowite z zakresu (włącznie) [0, 250]. Oznacz je do 1 za pomocą t-1 .
  2. Skonstruować t-1algebraicznej p użyciu sjako wartość stałą i liczb całkowitych z etapu 1, tak jak współczynniki uprawnień x: f (x) = y + x * a 1 + x 2 * a 2 + ... + X t- 1 * a t-1 .
  3. Wyjście (f(z) mod 251)dla każdego zz zakresu (włącznie) [1, n].

Wdrożenie referencyjne

#!/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)

Weryfikacja

Do weryfikacji wyników można użyć następującego fragmentu stosu:

Pokaż fragment kodu

Zasady

  • sbędzie nieujemną liczbę całkowitą, mniejszą 251i ni tbędzie całkowite dodatnie mniej niż 251i więcej niż 1. Ponadto masz gwarancję, że dane wejściowe są prawidłowe (znaczenie t <= n).
  • Dane wejściowe i wyjściowe mogą mieć dowolny rozsądny, jednoznaczny i spójny format.
  • Próbki liczb losowych należy próbkować z równomiernego rozkładu - każda możliwa wartość powinna mieć jednakowe prawdopodobieństwo wyboru.
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
źródło
1
Czy musimy produkować z i f(z) ? Jeśli wydrukuję tablicę f(z)s po kolei, zwynika to z indeksu. [[1, 5], [2, 2], [3, 9], [4, 14]]nie zawiera więcej informacji niż [5, 2, 9, 14].
orlp
1
Wyzwanie dla wykonania odwrotności .
FryAmTheEggman
@orlp Fair point.
Mego
Jakieś przypadki testowe?
Leaky Nun
4
@LeakyNun Ponieważ to pytanie jest oznaczone losowo , uważam, że fragment weryfikacyjny jest o wiele bardziej wartościowy niż przypadki testowe, które będą różne dla każdego uruchomienia.
FryAmTheEggman

Odpowiedzi:

13

Galaretka , 15 bajtów

251©xX€⁵0¦ḅЀ%®

Oczekuje , że t , n i s jako argumenty wiersza polecenia. Wypróbuj online!

Jak to działa

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
źródło
3
Zastąpienie ostatniej liczby całkowitej jest takie eleganckie :)
Lynn
8

Mathematica, 59 56 bajtów

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

Przyjmuje trzy argumenty w kolejności t , n i s . Konstruuje tablicę 2d z n rzędami i t -1 kolumnami. Każdy wektor wiersza j , ponumerowany od 1 do n , zawiera moce od j do j t -1 . Następnie tworzony jest wektor losowych współczynników całkowitych z zakresu od 0 do 250 z wartościami t -1. To jest mnożone przez macierz z macierzą 2d, a następnie s jest dodawane elementarnie i pobierane moduł 251, aby uzyskać wartość wielomianu w każdym z n punktów.

mile
źródło
1
Właśnie miałem opublikować 79-bajtową odpowiedź, fajna sztuczka Sum!
LegionMammal978
1
Mam inne podejście, ale obecnie jest o dwa bajty dłużej. Może masz pomysł, jak to skrócić:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Martin Ender
3

Pyth, 24 bajty

J+EmOK251tEm%s.e*b^dkJKS

Wypróbuj online!

Kolejność wprowadzania: n s toddzielone przez podawanie liniowe.

Leaky Nun
źródło
arrrrrgh, ninja'd bo poszedłem po ciasteczko
Maltysen
3

JavaScript, 181 bajtów

(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 _;}

Nie golfowany:

(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 _;
}

Nie wiem, jak poprawnie to sprawdzić, ale wiem, że JS miał problem z mapowaniem nowej tablicy, ponieważ najwyraźniej .mappomija niezdefiniowane wartości. Jeśli ktoś widzi jakieś sposoby poprawy lub wady, nie wahaj się dać mi znać.

charredgrass
źródło
123 bajty:(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
Nie używasz n, co wydaje się złe. Wydaje się, że twój kod również indeksuje w oparciu o 1. [...Array()]jest nieco krótszy niż fiil(). Ponadto ostatnie dwa wiersze można zmniejszyć doreturn _.map(f);
Neil
3

C #, 138 134 bajtów

(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, gdzie są dane wejściowe, inta dane wyjściowe to IEnumerable<double>. Możesz wypróbować mój kod na .NetFiddle .

Nie jestem w 100% pewien co do poprawności mojego algorytmu, proszę o komentarz, jeśli coś źle zrozumiem.

4 bajty zapisane za pomocą sztuczki @ raggy .

aloisdg przenosi się do codidact.com
źródło
3

MATL , 20 19 bajtów

251tliq3$Yrihi:ZQw\

Kolejność wejście jest t, s, n.

Wypróbuj online!

Wyjaśnienie

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
źródło
2

Julia, 48 bajtów

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

Wypróbuj online!

Dennis
źródło
1

JavaScript (ES6), 116 bajtów

(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))

Chciałbym pomyśleć, że to jeden z rzadkich przypadków, w których reducebije map.

Neil
źródło
1

Python 3 z NumPy , 103 bajty

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

Mogę szczerze powiedzieć, że nigdy nie spodziewałem się używać NumPy do golfa kodowego ...

Anonimowa funkcja, która pobiera dane wejściowe za pomocą argumentu i zwraca listę.

Jak to działa

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

Wypróbuj na Ideone

TheBikingViking
źródło
1

J , 32 30 bajtów

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

Pobiera listę z wartościami n , t oraz s .

Zaoszczędzono 2 bajty, używając idei replace at index 0 z rozwiązania @ Dennis .

Wyjaśnienie

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
mile
źródło
0

Java 8, 224 bajty:

(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;};

Wyrażenie lambda Java 8. Zwraca tablicę liczb całkowitych oddzielonych przecinkami i działa idealnie, dopóki wartości w tablicy wyjściowej nie przekroczą zakresu typu danych Java longlub 64-bitowej liczby całkowitej ze znakiem, na podstawie którego -200dane wyjściowe są wysyłane do tablicy.

Wypróbuj online! (Ideone)

R. Kap
źródło