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:
Choose a prime $p \gt \text{max}(m,w)$, where $p$ is public, and set $m_0 = m \in \mathbb{Z}/p\mathbb{Z}$.
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$.
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.
I chose prime $p=101$ to work in $\mathbb{Z}_p^*$.
I chose 2 random integers $c_1=11$ and $c_2=6$, and set $c_0=m=7$.
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}$$
What the answer is NOT
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.
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. :-)
