-2
$\begingroup$

I am trying to get secret S and I have 3 values (2,2)(6,3)(4,9) and know that modulo is 13.

I tried using Lagrange basis polynomial and got 8 but I am not sure if that is right and also I cannot find way to derive the equation of the line in form of ax+by= c mod 13.

$\endgroup$
2
  • 1
    $\begingroup$ 8 is correct... $\endgroup$
    – poncho
    Oct 27 '15 at 19:25
  • $\begingroup$ I cannot find way to derive the equation of the line in form of ax+by= c mod 13. $\endgroup$
    – n0unc3
    Oct 29 '15 at 12:53
0
$\begingroup$

You should choose two points. (for example (2,2) and (6,3)). Then you can compute the Lagrange interpolation polynomial as below:

$f(x)=2.(\dfrac{x-6}{2-6})+3.(\dfrac{x-2}{6-2})=-(\dfrac{2x-12}{4})+(\dfrac{3x-6}{4})$

$\ \ \ \ \ \ \ \ =(\dfrac{x+6}{4})=(\dfrac{x}{4})+(\dfrac{6}{4})\ mod(13)=10x+60\ mod(13)=10x+8$

Because $4^{-1}=10 \ mod(13)$.

$\endgroup$
1
  • 1
    $\begingroup$ Latex has \mod \bmod and \pmod{}. Also \cdot instead of *. $\endgroup$
    – kelalaka
    Nov 14 '20 at 19:16
0
$\begingroup$

The form of equation you expect is not usually applied to Shamir's Sharing Scheme. Instead the equation is usually represented as polynomial: $$f\left(x\right)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}\,\! \mod p,$$ where $k$ is number of pieces needed to restore the secret; $a_i$ are random coefficients (modulo p) and $p$ is 13 (in your case).

According to this your "equation of the line" (after recovering it with Lagrange interpolation polynomial) should look like: $$f\left(x\right)=10x+8\mod 13.$$ As you can see $a_0$ coefficient here is $8$ so that your guess is right (since $a_0$ is the secret itself).

$\endgroup$
2
  • $\begingroup$ n0unc3 did say it saw a (2,3) system; that means that 2 shares were sufficient to recover the secret. Hence, it's not at all surprising that one of the shares are superfluous... $\endgroup$
    – poncho
    Nov 12 '15 at 19:08
  • $\begingroup$ @poncho, that's right, thank you. I have removed needless caveat. $\endgroup$
    – Toparvion
    Nov 13 '15 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.