In [1]:
import math
In [2]:
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 [3]:
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 [4]:
# our message to be encrypted:
m=12345678901234567890123456789012345678901234567890123456789012345678901234567890
assert m<modulus and m>q and m>p
In [5]:
# ZZ is used to coerce <sage.rings.finite_rings.integer_mod.IntegerMod_int> type to <sage.rings.integer.Integer> type
c=ZZ(pow(m,e,modulus)) # encrypted
c
Out[5]:
5473971933008973694019038418251374589826018649241185765775698303356454424650122337982685489929109976255457564898918059277830850469588170541739113383290278
In [6]:
assert m==pow(c,d,modulus) # usual decryption, as in RSA introductory textbooks
In [7]:
math.log(d,2), math.log(d_p,2), math.log(d_q,2)
Out[7]:
(505.37265854845595, 255.09741892193816, 255.44641581321525)
In [8]:
# as in SSH 1.x
# AKA CRT representation of $m$
p2=ZZ(pow(c,d_p,p))
q2=ZZ(pow(c,d_q,q))
p2,q2
Out[8]:
(24185172713156141797474942366269203108138752835852090086310023367401253255244,
 79972676092133531377071881477514018824095664254876941148957882772150740179384)
In [9]:
assert p2==divmod(m,p)[1]
assert q2==divmod(m,q)[1]
In [10]:
decrypted=crt([p2,q2], [p,q])
assert m==decrypted