Shamir Secret Sharing - P not prime I was wondering what will happen if I use the Shamir Secret Sharing scheme with $P$ not being a prime, let's say it is $255$. An adversary which holds $k'$ shares ($k'&lt;$ threshold $k$  ) can attack the scheme and find the secret $S$? If he can attack the scheme, how the attack works?
There are two problems that arise when you attempt to use a composite $P$:

The first is that the attacker can gain some information about the shared secret; he can't reconstruct the entire secret, however the goal of Shamir Secret Sharing is that the attacker obtains no information.  For a simple case, consider a threshold $k=2$ case where the attacker has the single share $(3, 0)$.  That is, the attacker knows that the polynomial is a linear equation $ax + s$, with $s$ being the shared secret, and with $3a + s = 0 \bmod 255$.  What the attacker can immediately deduce is that, whatever the shared secret is, it must be a multiple of 3 (because $3a + s$ is a multiple of $3$); this happens because $3$ is a divisor of $255$.

The second issue is that the legitimate reconstructors, with $k$ different shares, cannot necessarily uniquely reconstruct the secret.  For an example, consider that case $k=2$ and we have the two shares $(1, 0)$ and $(4, 0)$.  In this case, we know we have a linear equation with $1a + s = 0 \bmod 255$ and $4a + s = 0 \bmod 255$.

Unfortunately, there are 3 possible equations that fit this criteria:

$$0 x + 0 $$

$$85 x + 170$$

$$170 x + 85$$

It is easy to see that plugging in 0, 4 into each of these equations yields the values implied by the shares.

Hence, while we know that the secret is one of $\{0, 85, 170\}$, we have no idea which one it is.