Modular arithmetic and sharing secrets

We want to get two people to be able to together compute a secret, but unable to do it on their own. Let's first define a boring prime sieve.

def is_prime(p):
    """
    Basic sieve.
    """
    for i in range(2, p - 1):
        if p % i == 0:
            return i
    return True

We also need a way to invert numbers in $\Z_m$ and we do so by a boring linear search.

def inv(a, m):
    """Find multiplicative
    inverse of a in Z_m.

    That is, c such that
    a * c == 1 (mod m).
    """
    for c in range(m):
        if (a * c) % m == 1:
            return c

The mechanism

Suppose we have some secret that we can represent as an integer $b$. We also fix a prime $p>b$ and we pick at random an integer between $0$ and $p$. We define a linear function $f$ by $$f(x)=ax+b \pmod p$$

Now suppose we get two pairs $(i, f(i))$ and $(j, f(j))$. We can then find the coefficients of $f$ and the constant term is the secret!

def solve(i, f_i, j, f_j):
    """Solve system of two
    linear equations in Z_p
    hence obtaining secret b.
    """
    a = inv(i - j, p) * (f(i) - f(j))
    b = f_i - a * i
    return b % p

We test it as follows

from random import randint

b = 1111 # Secret
p = 10007 # Prime
a = randint(0, p)
f = lambda x: (a * x + b) % p

solve(5, f(5), 7, f(7)) == b # True!

27 December, 2018