4
$\begingroup$

I originally posted this question in the math stackexchange, but I then thought that it might be more appropriate in this section. I am currently studying Shamir's secret sharing scheme, which uses Lagrange's interpolation formula to reconstruct a key $K$ from a certain number of shares. In Shamir's scheme, during key reconstruction, there is no need to reconstruct the entire polynomial $a(x)$ since we only need the value $a(0)$, the secret. Therefore, we can use a simplification in the formula by substituting $x=0$ in the original Lagrange formula, which then becomes this:

$$K = \sum_{j=1}^t (y_j \prod_{1 \leq k \leq t} \frac {x_k} {x_k - x_j}) \pmod p$$

where $y_j$ are the shares owned by the participants. If we now define

$$b_j = \prod_{1 \leq k \leq t} \frac {x_k} {x_k - x_j} \pmod p$$

we can then reconstruct the key $K$ with this formula:

$$K = \sum_{j=1}^t b_jy_j \pmod p$$

And during the calculation of $b_j$ is where I hit a wall: in the book that I am using to study this (Cryptography Theory and Practice, by Stinson and Paterson), there is an example of how to compute $b_j$. We are given the following values:

$x_1=1, x_2=2, x_3=3, x_4=4, x_5=5$

And we want to get the value of $b$ for $x_1$, $x_3$ and $x_5$. The book shows this example for $b_1$:

\begin{align} b_1 &= \frac{x_3 x_5}{(x_3 - x_1)(x_5-x_1)} & & \pmod{17} \\ &= 3 * 5 * (2)^{-1} * (4)^{-1} & & \pmod{17}\\ &= 3 * 5 * 9 * 13 & & \pmod{17} \\ &= 4 & & \pmod{17} \end{align}

How did we get from $(2)^{-1}$ and $(4)^{-1}$ to $9$ and $13$ respectively?

$\endgroup$
  • $\begingroup$ $2\cdot 9\bmod 17=18\bmod 17$ and $13\cdot 4\bmod 17=52\bmod 17=1$ as expected. $\endgroup$ – SEJPM Jun 9 at 12:03
6
$\begingroup$

All these calculations are done $\bmod{17}$.

$2^{-1}$ means here the number, $x$, that satisfies the equation $2x = 1 \pmod{17}$. (Note that this is the same definition that we use for the reals). When you're working $\bmod{17}$ (or any prime number, in fact), every number except 0 has an inverse.

To calculate inverses efficiently, you should use the extended Euclidean algorithm. But with a small number like 17, it might be worthwhile to just construct a multiplication table to get practice with modular arithmetic.

| improve this answer | |
$\endgroup$

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.