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