# 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'<$ threshold $k$ ) can attack the scheme and find the secret $S$? If he can attack the scheme, how the attack works?

• Shamir secret sharing is only possible when operating in a finite field. So, for moduli that are not a power of a prime ($p^k$), the calculations won't work. – mikeazo Jul 7 '17 at 14:16
• Also, if you do use a power of a prime $p^k$ with $k>1$, you don't do the computation modulo $p^k$, instead, you need to use an extension field; addition and multiplication work differently than just computing things $\bmod p^k$ – poncho Jul 7 '17 at 14:41

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.