Threshold 2-of-2 RSA signatures

rsa_sign.py

#!/usr/bin/python

from fractions import gcd
import random

def lcm(a,b):
    return (a*b)//gcd(a,b)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    assert g == 1
    return x % m

def crt2(m, x):

    assert len(m) == 2
    assert len(x) == 2

    m1 = modinv(m[1], m[0])
    m2 = modinv(m[0], m[1])

    n = m[0] * m[1]

    temp1 = m1 * x[0] * m[1] + m2 * x[1] * m[0]

    return temp1 % n

# shared e
e = 65537

# RSA key 1
p1 = 94720082028609563655580284090785242407068485000929010279452358389753751518503
q1 = 110783740849639752444347104201076988843661811436796730150114684375971413208211
phi1 = lcm(p1 - 1, q1 - 1)
n1 = p1*q1
d1 = modinv(e, phi1)

assert((e*d1) % phi1 == 1)

# RSA key 2
p2 = 112817608130405937172301950368463102929192946325450845558448316612016086936659
q2 = 98412103241088769678416698472457363406876279121454272667443230754583686041243
phi2 = lcm(p2 - 1, q2 - 1)
n2 = p2*q2
d2 = modinv(e, phi2)
assert((e*d1) % phi1 == 1)

# RSA key 2
p2 = 112817608130405937172301950368463102929192946325450845558448316612016086936659
q2 = 98412103241088769678416698472457363406876279121454272667443230754583686041243
phi2 = lcm(p2 - 1, q2 - 1)
n2 = p2*q2
d2 = modinv(e, phi2)

assert((e*d2) % phi2 == 1)

# Choose random message H(m) in Z_{n1*n2}
m = random.randint(1, n1*n2)

# s1 = H(m)^d1 mod n1
s1 = pow(m % n1, d1, n1)
assert pow(s1, e, n1) == m % n1

# s2 = H(m)^d2 mod n2
s2 = pow(m % n2, d2, n2)
assert pow(s2, e, n2) == m % n2

# Combine s1,s2
s = crt2([n1,n2], [s1,s2])

r = pow(s, e, n1*n2)

# Print original message and recovered message
print("m=",m)
print("r=",r)
assert(m == r)