Ask Your Question
0

how to use the secret perfect shamir in Sage?

asked 2012-05-20 08:11:00 -0500

anonymous user

Anonymous

updated 2015-01-13 15:06:07 -0500

FrédéricC gravatar image

Good Morning. I need to resorve this problem. I have three fragments that I make with shamir's secret perfect and now I need to find the polinomy, but I don`t know if there is a method which I can to solve the polinomy and have the secret with Sage.

For exemple I have this polinomy 56 + 10x + 5x^2 mod 101. I know that the secret is 56 and three fragments [25, 98], [47, 57], [19, 31], (56 +1025+525^2)mod 101 = 98

How I can to find the polinomy with these fragments? I can't use Lagrange because it is arithmetic modular.

Thank you.

edit retag flag offensive close merge delete

Comments

This sounds like homework. Can you give us a reference to "shamir's secret perfect"? It sounds like a key-sharing or encryption scheme, perhaps one not implemented in Sage. Certainly we should have the infrastructure to deal with any polynomial stuff over Z_n, though.

kcrisman gravatar imagekcrisman ( 2012-05-21 03:23:11 -0500 )edit

1 answer

Sort by » oldest newest most voted
1

answered 2012-06-29 01:35:10 -0500

Sigurd Meldgaard gravatar image

You seem to be refering to Shamir Secret Sharing a secret-sharing scheme invented by Shamir: paper here

Described nicely here: http://en.wikipedia.org/wiki/Shamir%2...

The following Sage code works fine to reconstruct the polynomial from the shares:

F = FiniteField(101) # Construct finite field
P = F['x'] # Polynomial ring

# How to use P:
original_polynomial = P("56 + 10x + 5x^2")
# Convert the shares to elements of F (otherwise lagrange_polynomial will fail)
shares = [(F(x), F(y)) for x,y in [(25, 98), (47, 57), (19, 31)]]
# Now lagrange_polynomial works fine
reconstructed_polynomial = P.lagrange_polynomial(shares)

print "Correct reconstruction!" if reconstructed_polynomial == original_polynomial else "Something wrong!"
print "p(x) =", reconstructed_polynomial
print "Secret = p(0) =", reconstructed_polynomial(0)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-05-20 08:11:00 -0500

Seen: 453 times

Last updated: Jun 29 '12