No Key: a simple library for Shamir’s no-key protocol

Shamir’s no-key protocol is a way to encrypt a communication using finite exponentiation. It is similar to Diffie-Hellman in that it depends on the difficulty of solving the discrete logarithm problem, but unlike DH, where both parties agree on a previously unkown datum, the no-key protocol is used to share information (party A transmit some data to party B).

The algorithm is as follows. Assume A wants to transmit message m (which is an integer number) to B. Both parties have previuosly agreed on a prime number p, which can be public.

1. A chooses a random number 0<=q1<p such that q1 and (p-1) are relatively prime, and computes
   m1 = pow(m,q1) mod (p), where pow(a,b) is the exponentiation a to the power b.
   Then A sends m1 to B.
2. B chooses a random number 0<=q2<p such that q1 and (p-1) are relatively prime and computes
   m2 = pow(q1,q2) mod (p)
   and sends m2 back to A.
3. A computes q1*, the inverse of q1 modulo (p-1) (not modulo p) and sends m3 = pow(m2,q1*) mod (p) to B.
4. B comptues q2*, the inverse of q2 modulo (p-1) and m4 = pow(m3,q2*) mod (p).
   This last m4 is equal to m and B has the initial message