Introduction to Cryptography with Coding Theory, 3rd Edition

B.10 Examples for Chapter 17

Example 38

Suppose we have a (5, 8) Shamir secret sharing scheme. Everything is mod the prime $p=987541\text{.}$ Five of the shares are

$$(9853\text{,}853)\text{,}(4421\text{,}4387)\text{,}(6543\text{,}1234)\text{,}(93293\text{,}78428)\text{,}(12398\text{,}7563)\text{.}$$

Find the secret.

SOLUTION

One way: First, find the Lagrange interpolating polynomial through the five points:

> interp([9853,4421,6543,93293,12398],
[853,4387,1234,78428,7563],x)

$$\begin{array}{c}-{\displaystyle \frac{\text{49590037201346405337547}}{\text{133788641510994876594882226797600000}}}{\text{X}}^{\text{4}}\\ +{\displaystyle \frac{\text{353130857169192557779073307}}{\text{8919242767399658439658815119840000}}}{\text{X}}^{\text{3}}\\ -{\displaystyle \frac{\text{8829628978321139771076837361481}}{\text{19112663072999268084983175256800000}}}{\text{X}}^{\text{2}}\\ +{\displaystyle \frac{\text{9749049230474450716950803519811081}}{\text{44596213836998292198294075599200000}}}\text{X}\\ +{\displaystyle \frac{\text{204484326154044983230114592433944282591}}{\text{22298106918499146099147037799600000 ...}}}\end{array}$$