Compartilhamento Secreto de Shamir

17

Dado n(o número de jogadores), t(o valor limite) e s(o segredo), são apresentados os nsegredos gerados pelo algoritmo de Compartilhamento Secreto de Shamir .

O Algoritmo

Para os propósitos deste desafio, os cálculos serão feitos em GF (251) (o campo finito de tamanho 251, também conhecido como número inteiro mod 251 ). Normalmente, o campo seria escolhido de tal forma que seu tamanho seja um primo muito maior que n. Para simplificar o desafio, o tamanho do campo será constante. 251foi escolhido porque é o maior número primo representável por um número inteiro não assinado de 8 bits.

  1. Gere t-1números inteiros aleatórios no intervalo (inclusive) [0, 250]. Rotular essas um 1 por meio de um t-1 .
  2. Construa um t-1polinômio de th grau usando scomo valor constante e os números inteiros aleatórios da etapa 1 como os coeficientes das potências de x: f (x) = s + x * a 1 + x 2 * a 2 + ... + x t- 1 * a t-1 .
  3. Saída (f(z) mod 251)para cada um zna faixa (inclusive) [1, n].

Implementação de referência

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

Verificação

O seguinte snippet de pilha pode ser usado para verificar as saídas:

Mostrar snippet de código

Regras

  • sserá um número inteiro não negativo menor que 251e ne tnúmeros inteiros positivos menores que 251e maiores que 1. Além disso, você tem a garantia de que as entradas são válidas (significado t <= n).
  • A entrada e a saída podem estar em qualquer formato razoável, inequívoco e consistente.
  • Números aleatórios devem ser amostrados a partir de uma distribuição uniforme - cada valor possível deve ter igual probabilidade de ser escolhido.
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
fonte
11
Temos que produzir z e f(z) ? Se eu imprimir uma matriz de f(z)s em ordem, zestá implícito no índice. [[1, 5], [2, 2], [3, 9], [4, 14]]não contém mais informações que [5, 2, 9, 14].
Ou orp
11
Desafio para fazer o inverso .
FryAmTheEggman
@orlp Fair point.
Mego
Algum caso de teste?
Leaky Nun
4
@LeakyNun Como essa pergunta é marcada aleatoriamente , acho que o snippet de verificação é muito mais valioso do que os casos de teste que variam a cada execução.
FryAmTheEggman

Respostas:

13

Gelatina , 15 bytes

251©xX€⁵0¦ḅЀ%®

Espera t , n , e s como argumentos de linha de comando. Experimente online!

Como funciona

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
fonte
3
Substituindo o último inteiro é tão elegante :)
Lynn
8

Mathematica, 59 56 bytes

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

Leva três argumentos na ordem t , n , e s . Constrói um array 2D com n linhas et -1 colunas. Cada vetor de linha j , numerado de 1 a n , contém os poderes de j a j t -1 . Então, um vetor de coeficientes inteiros aleatórios no intervalo de 0 a 250 é criado com os valores t -1. Isso é multiplicado por matriz com a matriz 2d e, em seguida, s é adicionado elemento a elemento e é obtido o módulo 251 para obter o valor do polinômio em cada um dos n pontos.

milhas
fonte
11
Estava prestes a postar uma resposta de 79 bytes, um belo truque Sum!
LegionMammal978
11
Eu tenho uma abordagem diferente, mas atualmente é dois bytes mais. Talvez você tem uma idéia de como reduzi-lo:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Martin Ender
3

Pitão, 24 bytes

J+EmOK251tEm%s.e*b^dkJKS

Experimente online!

Ordem de entrada: n s tseparados por avanço de linha.

Freira Furada
fonte
Arrrrrgh, ninja'd porque eu fui pegar um cookie
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 _;
}

Eu não sei como checá-lo corretamente, mas sei que foi um problema fazer JS mapear em uma nova matriz, pois aparentemente .mapignora valores indefinidos. Se alguém vê alguma maneira de melhorar, ou falhas, não hesite em me avisar.

charredgrass
fonte
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 07/07
Você não está usando n, o que parece errado. Seu código também parece estar assumindo uma indexação baseada em 1. [...Array()]é um pouco menor que fiil(). Além disso, as duas últimas linhas podem ser reduzidas parareturn _.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 onde estão as entradas inte a saída é um IEnumerable<double>. Você pode tentar meu código no .NetFiddle .

Não tenho 100% de certeza sobre a validade do meu algoritmo. Por favor, comente se entendi algo errado.

4 bytes salvos com o truque de @ raggy .

aloisdg diz Restabelecer Monica
fonte
3

MATL , 20 19 bytes

251tliq3$Yrihi:ZQw\

Ordem de entrada é t, s, n.

Experimente online!

Explicação

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

Julia, 48 bytes

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

Experimente online!

Dennis
fonte
1

JavaScript (ES6), 116 bytes

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

Eu gostaria de pensar que este é um dos raros casos em que reducebate map.

Neil
fonte
1

Python 3 com 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)]

Posso dizer honestamente que nunca esperei usar o NumPy para código de golfe ...

Uma função anônima que recebe entrada por meio de argumento e retorna uma lista.

Como funciona

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

Experimente no Ideone

TheBikingViking
fonte
1

J , 32 30 bytes

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

Faz uma lista com os valores n , t e s .

Economizou 2 bytes usando a idéia de substituição no índice 0 da solução de @ Dennis .

Explicação

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
milhas
fonte
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;};

Uma expressão lambda do Java 8. Produz uma matriz inteira separada por vírgula e funciona perfeitamente até que os valores na matriz de saída cheguem além do intervalo do longtipo de dados inteiro assinado em Java ou de 64 bits, no qual -200é gerado na matriz.

Experimente Online! (Ideona)

R. Kap
fonte