Shamirs geheimes Teilen

17

Ausgehend von n(der Anzahl der Spieler), t(dem Schwellenwert) und s(dem Geheimnis) werden die nGeheimnisse ausgegeben, die durch Shamirs Secret-Sharing-Algorithmus generiert wurden .

Der Algorithmus

Für die Zwecke dieser Herausforderung werden die Berechnungen in GF (251) (dem endlichen Feld der Größe 251, auch bekannt als Ganzzahlen mod 251 ) durchgeführt. Normalerweise würde das Feld so gewählt, dass seine Größe eine Primzahl ist, die viel größer ist als n. Um die Herausforderung zu vereinfachen, ist die Feldgröße konstant. 251wurde gewählt, weil es die größte durch eine 8-Bit-Ganzzahl ohne Vorzeichen darstellbare Primzahl ist.

  1. Generieren Sie t-1zufällige Ganzzahlen im Bereich (einschließlich) [0, 250]. Beschriften Sie diese ein 1 durch einen t-1 .
  2. Konstruiere ein t-1Polynom des Grades mit sdem konstanten Wert und den Zufallszahlen aus Schritt 1 als Koeffizienten der Potenzen von x: f (x) = s + x * a 1 + x 2 * a 2 + ... + x t- 1 * a t-1 .
  3. Ausgabe (f(z) mod 251)jeweils zim (inklusive) Bereich [1, n].

Referenzimplementierung

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

Nachprüfung

Das folgende Stack-Snippet kann zum Überprüfen von Ausgaben verwendet werden:

Code-Snippet anzeigen

Regeln

  • swird weniger eine nicht negative ganze Zahl ist als 251und nund twird positive ganze Zahlen kleiner als 251und größer als 1. Darüber hinaus ist gewährleistet, dass die Eingaben gültig sind (Bedeutung t <= n).
  • Die Ein- und Ausgabe kann in jedem vernünftigen, eindeutigen und konsistenten Format erfolgen.
  • Zufallszahlen sind aus einer Gleichverteilung abzutasten - jeder mögliche Wert sollte die gleiche Wahrscheinlichkeit haben, gewählt zu werden.
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
quelle
1
Müssen wir ausgeben z und f(z) ? Wenn ich ein Array von f(z)s in der richtigen Reihenfolge zdrucke , wird dies durch den Index impliziert. [[1, 5], [2, 2], [3, 9], [4, 14]]enthält nicht mehr Informationen als [5, 2, 9, 14].
Orlp
1
Herausforderung für das Umkehren .
FryAmTheEggman
@orlp Fairer Punkt.
Mego
Irgendwelche Testfälle?
Undichte Nonne
4
@LeakyNun Da diese Frage als zufällig markiert ist, ist das Überprüfungs-Snippet meiner Meinung nach viel wertvoller als Testfälle, die bei jedem Durchlauf variieren.
FryAmTheEggman

Antworten:

13

Gelee , 15 Bytes

251©xX€⁵0¦ḅЀ%®

Erwartet t , n und s als Befehlszeilenargumente. Probieren Sie es online!

Wie es funktioniert

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
quelle
3
Das Ersetzen der letzten Ganzzahl ist so elegant :)
Lynn
8

Mathematica, 59 56 Bytes

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

Nimmt drei Argumente in der Reihenfolge t , n und s auf . Konstruiert ein 2d-Array mit n Zeilen und t -1 Spalten. Jeder von 1 bis n nummerierte Zeilenvektor j enthält die Potenzen von j bis j t & supmin; ¹ . Dann wird ein Vektor von zufälligen ganzzahligen Koeffizienten im Bereich von 0 bis 250 mit t & supmin; ¹ Werten erzeugt. Dies wird mit dem 2d-Array matrixmultipliziert und dann wird s elementweise addiert und das Modul 251 genommen, um den Wert des Polynoms an jedem der n Punkte zu erhalten.

Meilen
quelle
1
Wollte gerade eine 79-Byte-Antwort posten, netter Trick mit Sum!
LegionMammal978
1
Ich habe einen anderen Ansatz, aber es ist derzeit zwei Bytes länger. Vielleicht haben Sie eine Idee, wie Sie es verkürzen können:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Martin Ender
3

Pyth, 24 Bytes

J+EmOK251tEm%s.e*b^dkJKS

Probieren Sie es online!

Eingabereihenfolge: n s tdurch Zeilenvorschub getrennt.

Undichte Nonne
quelle
arrrrrgh, ninja'd weil ich ging, um einen Keks zu bekommen
Maltysen
3

JavaScript, 181 Bytes

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

Ungolfed:

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

Ich weiß nicht, wie man es richtig überprüft, aber ich weiß, dass es ein Problem war, JS dazu zu bringen, ein neues Array zuzuordnen, da anscheinend .mapundefinierte Werte übersprungen werden. Wenn jemand Verbesserungsmöglichkeiten oder Mängel sieht, zögern Sie nicht, mich zu informieren.

verkohltes Gras
quelle
123 Bytes:(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
Sie verwenden nicht n, was falsch zu sein scheint. Ihr Code scheint auch eine 1-basierte Indizierung vorauszusetzen. [...Array()]ist etwas kürzer als fiil(). Außerdem können die letzten beiden Zeilen aufreturn _.map(f);
Neil
3

C #, 138 134 Bytes

(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, wo Eingänge intund Ausgang sind, ist ein IEnumerable<double>. Sie können meinen Code auf .NetFiddle ausprobieren .

Ich bin mir über die Gültigkeit meines Algorithmus nicht 100% sicher. Bitte kommentieren Sie, wenn ich etwas falsch verstanden habe.

4 Bytes mit @ raggys Trick gespeichert .

aloisdg sagt Reinstate Monica
quelle
3

MATL , 20 bis 19 Bytes

251tliq3$Yrihi:ZQw\

Eingabereihenfolge ist t, s, n.

Probieren Sie es online!

Erläuterung

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
quelle
2

Julia, 48 Bytes

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

Probieren Sie es online!

Dennis
quelle
1

JavaScript (ES6), 116 Byte

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

Ich würde gerne denken, dass dies einer der seltenen Fälle ist, in denen reduceBeats auftreten map.

Neil
quelle
1

Python 3 mit NumPy , 103 Bytes

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

Ich kann ehrlich sagen, dass ich nie damit gerechnet hätte, NumPy für Code Golf zu verwenden ...

Eine anonyme Funktion, die Eingaben über Argumente entgegennimmt und eine Liste zurückgibt.

Wie es funktioniert

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

Probieren Sie es auf Ideone

TheBikingViking
quelle
1

J , 32-30 Bytes

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

Nimmt eine Liste mit den Werten n , t und s auf .

Durch Verwendung der Idee " Ersetzen bei Index 0" aus der @ Dennis- Lösung wurden 2 Byte eingespart .

Erläuterung

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
Meilen
quelle
0

Java 8, 224 Bytes:

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

Ein Java-8-Lambda-Ausdruck. Gibt ein durch Kommas getrenntes ganzzahliges Array aus und funktioniert einwandfrei, bis die Werte im Ausgabearray außerhalb des Bereichs des Java liegenlong Datentyps 64-Bit Integer mit Vorzeichen) überschreiten, der -200in das Array ausgegeben wird.

Probieren Sie es online! (Ideone)

R. Kap
quelle