Problem

I am trying to implement Shamir's Secret Sharing algorithm, but sometimes it works and sometimes it doesn't, making me think I'm misunderstanding something subtle about the algorithm as it's written.

Verbatim from Richard Mollin's "Codes: The Guide to Secrecy from Ancient to Modern Times" the algorithm is described this way:

Shamir's Threshold Scheme

Trent distributes shares of $m$ to $w \in \mathbb{N}$ participants of whom any $t \le w$ of them will be able to recover $m$.

Trent's Actions:

1. Choose a prime $p \gt \text{max}(m,w)$, where $p$ is public, and set $m_0 = m \in \mathbb{Z}/p\mathbb{Z}$.

2. Select $t-1$ random integers $c_j$ for $j = 1, 2, \ldots, t-1$ and set $$p(x) \equiv m + \sum_{j=1}^{t-1}c_{j}x^{j} \equiv \sum_{j=0}^{t-1}c_{j}x^{j} \;(\text{mod}\,p),$$ where $c_0=m$.

3. Compute $p(x_k)\equiv m_k \;(\text{mod}\,p)$ for distinct integers $x_k \le p-1$ and securely distribute the share $(x_k,m_k)$ to participant $\mathcal{P}_k$ for $1 \le k \le w$.

Pooling Shares: Without loss of generality, suppose a group of $t$ participants $\mathcal{P}_k$ for $1 \le k \le t$ get together and plug their shares into the Lagrange interpolation formula: $$f(x) = \sum_{k=1}^{t}m_k \prod_{\begin{array}{c} 1 \le l \le t \\ l \ne k \end{array}} \frac{x-x_l}{x_k-x_l} = \sum_{k=1}^{t} m_k K_k(x),$$ where $$K_k(x) = \prod_{\begin{array}{c} 1 \le l \le t \\ l \ne k \end{array}} \frac{x-x_l}{x_k-x_l}.$$

In the analysis following, we will show that the next equation must hold: $$f(x_i) \equiv m_i \;(\text{mod}\,p),\text{ for } 1 \le i \le t$$ and from it the following crucial equation must hold: $$p(0) \equiv f(0) \equiv \sum_{k=1}^{t} m_k K_k(0) \equiv m \;(\text{mod}\,p)$$ so the shares have been pooled to retrieve the secret.

Implementation

In my implementation, say my message is $m=7$ and I want to distribute it among $w=6$ people so that any $t=3$ can recover it.

1. I chose prime $p=101$ to work in $\mathbb{Z}_p^*$.

2. I chose 2 random integers $c_1=11$ and $c_2=6$, and set $c_0=m=7$.

3. Since in step 2 I fixed the coefficients of the polynomial $p(x)$ (based on $m,t$ and $p$), I can compute and distribute the $w$ shares of the secret. Note that I never actually used $w$ anywhere yet and I could have reached this point if $w$ held any value between $t \le w \lt p$. I could compute and distribute anywhere between 3 and 100 shares of the secret. As long as I kept $m$, $t$, $p$, $c_1$, and $c_2$ I could continue computing new shares (up to a total of 100) for any additional co-conspirators that join me in the future. For simplicity here, I'll just compute $x\in\{1,2,3,4\}$

\begin{align} p(x) & \equiv c_0 x^0 + c_1 x^1 + c_2 x^2 & (\text{mod}\,p) \\ p(1) & \equiv 7 \cdot 1 + 11 \cdot 1 + 6 \cdot 1 \equiv 24 & (\text{mod}\,101) \\ p(2) & \equiv 7 \cdot 1 + 11 \cdot 2 + 6 \cdot 4 \equiv 53 & (\text{mod}\,101) \\ p(3) & \equiv 7 \cdot 1 + 11 \cdot 3 + 6 \cdot 9 \equiv 94 & (\text{mod}\,101) \\ p(4) & \equiv 7 \cdot 1 + 11 \cdot 4 + 6 \cdot 16 \equiv 46 & (\text{mod}\,101) \\ \end{align}

$$\begin{array}{l|l} k & (x_k,m_k) \rightarrow \mathcal{P}_k \\ \hline 1 & (1,24) \\ 2 & (2,53) \\ 3 & (3,94) \\ 4 & (4,46) \\ \end{array}$$

Now if participants 1, 2, and 3 get together, they compute (with apologies for the formatting; this was the most readable I could make it) $$\begin{array}{l} f(0) \equiv& &m_1 \cdot \frac{0-x_2}{x_1-x_2} \cdot \frac{0-x_3}{x_1-x_3} \\ &+ &m_2 \cdot \frac{0-x_1}{x_2-x_1} \cdot \frac{0-x_3}{x_2-x_3} \\ &+ &m_3 \cdot \frac{0-x_1}{x_3-x_1} \cdot \frac{0-x_2}{x_3-x_2} &(\text{mod}\,p) \\\\\\ f(0) \equiv& &24 \cdot \frac{-2}{1-2} \cdot \frac{-3}{1-3} \\ &+ &53 \cdot \frac{-1}{2-1} \cdot \frac{-3}{2-3} \\ &+ &94 \cdot \frac{-1}{3-1} \cdot \frac{-2}{3-2} &(\text{mod}\,101) \\\\\\ f(0) \equiv& &24 \cdot 1 \cdot 3 \\ &+ &53 \cdot -1 \cdot 3 \\ &+ &94 \cdot 1 \cdot 1 &(\text{mod}\,101) \\\\\\ f(0) \equiv& &7 &(\text{mod}\,101). \\\\\\ \end{array}$$

But if participants 1, 2, and 4 get together, they compute $$\begin{array}{l} f(0) \equiv& &m_1 \cdot \frac{0-x_2}{x_1-x_2} \cdot \frac{0-x_4}{x_1-x_4} \\ &+ &m_2 \cdot \frac{0-x_1}{x_2-x_1} \cdot \frac{0-x_4}{x_2-x_4} \\ &+ &m_4 \cdot \frac{0-x_1}{x_4-x_1} \cdot \frac{0-x_2}{x_4-x_2} &(\text{mod}\,p) \\\\\\ f(0) \equiv& &24 \cdot \frac{-2}{1-2} \cdot \frac{-4}{1-4} \\ &+ &53 \cdot \frac{-1}{2-1} \cdot \frac{-4}{2-4} \\ &+ &46 \cdot \frac{-1}{4-1} \cdot \frac{-2}{4-2} &(\text{mod}\,101) \\\\\\ f(0) \equiv& &24 \cdot 2 \cdot \frac{4}{3} \\ &+ &53 \cdot -1 \cdot 2 \\ &+ &46 \cdot \frac{-1}{3} \cdot -1 &(\text{mod}\,101) \\\\\\ f(0) \equiv& &74 \frac{1}{3} & (\text{mod}\,101). \\\\\\ \end{array}$$

1. From the example above, it might seem that the problem stems from the fact that for generating $m_1$, $m_2$, and $m_3$ in step 3 of the sharing portion, the value is already less than 101 so no modulation occurs, but for $m_4$ the value gets modulated. This isn't the answer because other combinations of participants (some or all of whose data required modulation) work and some don't.

2. Similarly, it might seem from above, that when participants 1, 2, and 3 get together to compute $f(0)$, the function produces 7 directly and no modulation is necessary. I see that in the first equation of the pooling portion, $f(x)$ is followed by $=$ instead of $\equiv$, but note that $p$ is public. There are many combinations of participants who can reconstruct the secret by modulating the value they compute for $f(0)$, who wouldn't be able to if they hadn't.

At this point I've tried so many combinations of values for all the variables and I keep ending up with whenever a set of participants get together to reconstruct the secret, they're only successful approximately 1/2 the time.

I've checked so many possible problem spots and I just can't figure out what I can't figure out so I figured I'd post here. I'm sure it's something subtle that will produce a Duh moment, but at this point I don't think I'm going to find it in a vacuum. I realize it's a lot to read (and type thankyouverymuch) ;-) but I appreciate anyone willing to help me understand. Thanks in advance for the help. :-)

-
It seems, like you used simple division. However, as you are working in $\mathbb{Z}_p^*$, division is multiplication with the modular inverse. – Maeher Sep 26 '12 at 5:31
As indicated by Maeher, you need to understand modular inverse; e.g. ${1\over3}\bmod{101}=34$ since $3\cdot34\equiv1\pmod{101}$. There must be another mistake but I fail to immediately spot it. – fgrieu Sep 26 '12 at 5:57
Spotted it! Check the derivation of ${74\cdot{1\over3}}\pmod{101}$ from the line above, it is wrong. You should get ${-80\cdot{1\over3}}\pmod{101}$. That is also ${(101-80)\cdot34}\pmod{101}$, giving the right value $7$. – fgrieu Sep 26 '12 at 10:45
@Travis, Welcome to our community. Hopefully you have found the comments here helpful to your problem. Given the comments, it seems that your question is not very constructive for the community here since it was due to a math error. Therefore, I'm going to close the question. Please do come back and visit often. This is a great place to learn. – mikeazo Sep 26 '12 at 16:25
Thanks guys. That was exactly the issue, but I'm so sleep deprived I wasn't able to see it. @mikeazo: I knew it had to be some simple math error which is why I posted it on math.SE first, but they didn't even attempt to answer it. They saw cryptogrophy everwhere and told me to post it here instead. – Travis Sep 26 '12 at 18:57