In [30]:
import math
In [31]:
modulus=0x978602aeb02e56eb99f3c970541277966299e3df1b4964aa4adc9aa05901d599bf6009234926d8ee0b93a4faca9d89e2a8d522add442c67cd3bc4fd26669c87f
e=publicExponent=0x10001
d=privateExponent=0x296e7b4d48df62e509339fe1171bf597295eeaf01685fb009577bcd01b8664e139bdb62bafa4b7228ffb00142d141cdf5a90b28983cb1b5f6fd133f9bd21a01
p=prime1=0xc56630cf17e5363315ee3f71f09ae7326ccc3c1f7e01b1ef4962019f0c8dafe7
q=prime2=0xc481639f89b5322b50a6feeaf308e4b22f766d7eeea534dc0257f72fe818efa9
d_p=exponent1=0x88f118e14269800d36a49e9d13d6d29737c503dcb114c9f4ffca9ee750d52677
d_q=exponent2=0xae6b56bd1623521ba66404231183d452e0d4128eb74ec6a37e250c50668833b9
q_inv=coefficient=0x32ed63b1399504db987b3d7c2265b088d6c4c44905afad05e217ce181b7060db
In [32]:
assert p>q # as generated by OpenSSL. SSH 1.x is other way round: p<q
assert math.gcd(p,q)==1 # coprime to each other
assert modulus==prime1*prime2 # AKA N
totient=(prime1-1)*(prime2-1)
assert privateExponent==pow(e,-1,totient) # AKA d
assert exponent1==divmod(d,p-1)[1] and exponent1==pow(e,-1,p-1) # AKA d_p
assert exponent2==divmod(d,q-1)[1] and exponent2==pow(e,-1,q-1) # AKA d_q
assert coefficient==pow(q,-1,p) # AKA q_inv
In [33]:
# our message to be encrypted:
m=12345678901234567890123456789012345678901234567890123456789012345678901234567890
assert m<modulus and m>q and m>p
In [34]:
c=pow(m,e,modulus) # encrypted
c
Out[34]:
5473971933008973694019038418251374589826018649241185765775698303356454424650122337982685489929109976255457564898918059277830850469588170541739113383290278
In [35]:
assert m==pow(c,d,modulus) # usual decryption, as in RSA introductory textbooks
In [36]:
math.log(d,2), math.log(d_p,2), math.log(d_q,2)
Out[36]:
(505.37265854845595, 255.09741892193816, 255.44641581321525)
In [37]:
# as in SSH 1.x
# AKA CRT representation of $m$
p2=pow(c,d_p,p)
q2=pow(c,d_q,q)
p2,q2
Out[37]:
(24185172713156141797474942366269203108138752835852090086310023367401253255244,
 79972676092133531377071881477514018824095664254876941148957882772150740179384)
In [38]:
assert p2==divmod(m,p)[1]
assert q2==divmod(m,q)[1]
In [39]:
# Algorithm from SSH 1.x
#k=divmod(q_inv*(q2-p2),q)[1] # if p<q
k=divmod(q_inv*(p2-q2),p)[1] # if p>q
decrypted=p2+p*k
assert m==decrypted
In [40]:
def invmod(x,p):
    return pow(x,-1,p)
In [41]:
# stolen and reworked from https://shainer.github.io/crypto/math/2017/10/22/chinese-remainder-theorem.html
def ChineseRemainderGauss(n, a):
    N=math.prod(n)
    result = 0

    for i in range(len(n)):
        ai = a[i]
        ni = n[i]
        bi = N // ni

        result += ai * bi * invmod(bi, ni)

    return result % N
In [42]:
assert m==ChineseRemainderGauss([p,q],[p2,q2])
In [43]:
def ChineseRemainderGaussForTwo(n, a):
    N=math.prod(n)
    b0 = N // n[0]
    b1 = N // n[1]
    
    result = a[0] * b0 * invmod(b0, n[0]) + a[1] * b1 * invmod(b1, n[1])

    return result % N
In [44]:
assert m==ChineseRemainderGaussForTwo([p,q],[p2,q2])