Berbagi Rahasia Shamir

17

Mengingat n(jumlah pemain), t(nilai ambang), dan s(rahasia), menampilkan nrahasia yang dihasilkan oleh algoritma Berbagi Rahasia Shamir .

Algoritma

Untuk keperluan tantangan ini, perhitungan akan dilakukan dalam GF (251) (bidang ukuran terbatas 251, atau dikenal sebagai bilangan bulat mod 251 ). Biasanya, bidang akan dipilih sedemikian rupa sehingga ukurannya adalah yang utama jauh lebih besar daripada n. Untuk menyederhanakan tantangan, ukuran bidang akan konstan. 251telah dipilih karena ini merupakan prime terbesar yang dapat diwakili oleh integer 8-bit unsigned.

  1. Hasilkan t-1bilangan bulat acak dalam rentang (inklusif) [0, 250]. Label ini sebuah 1 melalui sebuah t-1 .
  2. Bangun t-1derajat polinomial menggunakan ssebagai nilai konstan dan bilangan bulat acak dari langkah 1 sebagai koefisien dari kekuatan x: f (x) = s + x * a 1 + x 2 * a 2 + ... + x t- 1 * a t-1 .
  3. Output (f(z) mod 251)untuk masing-masing zdalam kisaran (inklusif) [1, n].

Implementasi Referensi

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

Verifikasi

Cuplikan Stack berikut dapat digunakan untuk memverifikasi output:

Tampilkan cuplikan kode

Aturan

  • sakan menjadi bilangan bulat non-negatif kurang dari 251, dan ndan takan menjadi bilangan bulat positif kurang dari 251dan lebih besar dari 1. Selanjutnya, Anda dijamin bahwa inputnya valid (artinya t <= n).
  • Input dan output dapat dalam format yang masuk akal, tidak ambigu, dan konsisten.
  • Nomor acak harus diambil sampelnya dari distribusi yang seragam - setiap nilai yang mungkin harus memiliki probabilitas yang sama untuk dipilih.
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
sumber
1
Apakah kita harus output z dan f(z) ? Jika saya mencetak array f(z)s secara berurutan, ztersirat oleh indeks. [[1, 5], [2, 2], [3, 9], [4, 14]]tidak mengandung informasi lebih dari [5, 2, 9, 14].
orlp
1
Tantangan untuk melakukan kebalikannya .
FryAmTheEggman
@ Atau titik adil.
Mego
Adakah testcases?
Leaky Nun
4
@ LeakyNun Karena pertanyaan ini ditandai acak , saya pikir potongan verifikasi jauh lebih berharga daripada kasus uji yang akan bervariasi untuk setiap proses.
FryAmTheEggman

Jawaban:

13

Jelly , 15 byte

251©xX€⁵0¦ḅЀ%®

Mengharapkan t , n , dan s sebagai argumen command-line. Cobalah online!

Bagaimana itu bekerja

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
sumber
3
Mengganti bilangan bulat terakhir sangat elegan :)
Lynn
8

Mathematica, 59 56 byte

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

Membawa tiga argumen dalam urutan t , n , dan s . Membangun 2d-array dengan n baris dan t -1 kolom. Setiap vektor baris j , nomor dari 1 sampai n , mengandung kekuatan j melalui j t -1 . Kemudian vektor koefisien bilangan bulat acak dalam kisaran 0 hingga 250 dibuat dengan nilai t -1. Itu dikalikan matriks dengan array 2d, dan kemudian s ditambahkan elemen-bijaksana dan diambil modul 251 untuk mendapatkan nilai polinomial pada setiap n poin.

mil
sumber
1
Baru saja memposting jawaban 79 byte, trik yang menyenangkan Sum!
LegionMammal978
1
Saya punya pendekatan yang berbeda, tetapi saat ini dua byte lebih lama. Mungkin Anda punya ide bagaimana mempersingkatnya:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Martin Ender
3

Pyth, 24 byte

J+EmOK251tEm%s.e*b^dkJKS

Cobalah online!

Pesanan input: n s tdipisahkan oleh linefeed.

Biarawati Bocor
sumber
arrrrrgh, ninja'd karena aku pergi untuk mendapatkan kue
Maltysen
3

JavaScript, 181 byte

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

Tidak Disatukan:

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

Saya tidak tahu bagaimana cara memeriksanya dengan benar, tetapi saya tahu bahwa itu sulit untuk mendapatkan JS untuk memetakan di array baru karena tampaknya .mapmelewatkan nilai yang tidak ditentukan. Jika ada yang melihat cara untuk meningkatkan, atau kekurangan, jangan ragu untuk memberi tahu saya.

charredgrass
sumber
123 byte:(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
Anda tidak menggunakan n, yang tampaknya salah. Kode Anda juga tampaknya mengasumsikan pengindeksan berbasis 1. [...Array()]sedikit lebih pendek dari fiil(). Juga, dua baris terakhir dapat dikurangi menjadireturn _.map(f);
Neil
3

C #, 138 134 byte

(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 di mana input berada intdan output adalah IEnumerable<double>. Anda dapat mencoba kode saya di .NetFiddle .

Saya tidak 100% yakin tentang validitas algoritma saya, mohon komentar jika saya salah mengerti sesuatu.

4 byte disimpan dengan trik @ raggy .

aloisdg kata Reinstate Monica
sumber
3

MATL , 20 19 byte

251tliq3$Yrihi:ZQw\

Agar input t, s, n.

Cobalah online!

Penjelasan

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

Julia, 48 byte

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

Cobalah online!

Dennis
sumber
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))

Saya ingin berpikir ini adalah salah satu kasus yang jarang terjadi di mana reduceketukan map.

Neil
sumber
1

Python 3 dengan NumPy , 103 byte

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

Jujur saya bisa mengatakan bahwa saya tidak pernah diharapkan untuk menggunakan NumPy untuk kode golf ...

Fungsi anonim yang mengambil input melalui argumen dan mengembalikan daftar.

Bagaimana itu bekerja

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

Cobalah di Ideone

TheBikingViking
sumber
1

J , 32 30 byte

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

Mengambil daftar dengan nilai n , t , dan s .

Disimpan 2 byte dengan menggunakan ganti pada indeks 0 ide dari solusi @ Dennis .

Penjelasan

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
mil
sumber
0

Java 8, 224 byte:

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

Ekspresi Java 8 lambda. Output array integer yang dipisahkan koma, dan bekerja dengan sempurna sampai nilai-nilai dalam array output mencapai di luar kisaran Java long, atau 64-bit integer yang ditandatangani, tipe data, yang -200menjadi output ke dalam array.

Cobalah secara Online! (Ideone)

R. Kap
sumber