ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 29 Jun 2012 01:35:10 -0500how to use the secret perfect shamir in Sage?https://ask.sagemath.org/question/8986/how-to-use-the-secret-perfect-shamir-in-sage/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 + 10*x + 5*x^2 mod 101. I know that the secret is 56 and three fragments [25, 98], [47, 57], [19, 31], (56 +10*25+5*25^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.Sun, 20 May 2012 08:11:00 -0500https://ask.sagemath.org/question/8986/how-to-use-the-secret-perfect-shamir-in-sage/Comment by kcrisman for <p>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.</p>
<p>For exemple I have this polinomy 56 + 10<em>x + 5</em>x^2 mod 101. I know that the secret is 56 and three fragments [25, 98], [47, 57], [19, 31], (56 +10<em>25+5</em>25^2)mod 101 = 98</p>
<p>How I can to find the polinomy with these fragments?
I can't use Lagrange because it is arithmetic modular.</p>
<p>Thank you.</p>
https://ask.sagemath.org/question/8986/how-to-use-the-secret-perfect-shamir-in-sage/?comment=19759#post-id-19759This 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.Mon, 21 May 2012 03:23:11 -0500https://ask.sagemath.org/question/8986/how-to-use-the-secret-perfect-shamir-in-sage/?comment=19759#post-id-19759Answer by Sigurd Meldgaard for <p>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.</p>
<p>For exemple I have this polinomy 56 + 10<em>x + 5</em>x^2 mod 101. I know that the secret is 56 and three fragments [25, 98], [47, 57], [19, 31], (56 +10<em>25+5</em>25^2)mod 101 = 98</p>
<p>How I can to find the polinomy with these fragments?
I can't use Lagrange because it is arithmetic modular.</p>
<p>Thank you.</p>
https://ask.sagemath.org/question/8986/how-to-use-the-secret-perfect-shamir-in-sage/?answer=13777#post-id-13777You seem to be refering to Shamir Secret Sharing a secret-sharing scheme invented by Shamir: [paper here](http://scholar.google.com/scholar?q=related:fpLEeJoOcrAJ:scholar.google.com/&hl=en&as_sdt=0,5&as_vis=1)
Described nicely here: http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
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)
Fri, 29 Jun 2012 01:35:10 -0500https://ask.sagemath.org/question/8986/how-to-use-the-secret-perfect-shamir-in-sage/?answer=13777#post-id-13777