C.9 Examples for Chapter 17 – Introduction to Cryptography with Coding Theory, 3rd Edition

C.9 Examples for Chapter 17

Example 38

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

(9853, 853), (4421, 4387), (6543, 1234), (93293, 78428), (12398, 7563).

Find the secret.

SOLUTION

The function interppoly(x,f,m) calculates the interpolating polynomial that passes through the points (xj, fj). The arithmetic is done mod m.

In order to use this function, we need to make a vector that contains the x values, and another vector that contains the share values. This can be done using the following two commands:

>> x=[9853 4421 6543 93293 12398];

>> s=[853 4387 1234 78428 7563];

Now we calculate the coefficients for the interpolating polynomial.

>> y=interppoly(x,s,987541)

y =
    678987   14728   1651   574413   456741

The first value corresponds to the constant term in the interpolating polynomial and is the secret value. Therefore, 678987 is the secret.