Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/python
def exgcd(a,b):
u, v, s, t = 1, 0, 0, 1
while b !=0:
q, r = divmod(a,b)
a, b = b, r
u, s = s, u - q*s
v, t = t, v - q*t
return (u, v, a)
def mod_inverse(a,b):
x,y,z = exgcd(a,b)
assert(z==1)
return x
n = 104176920808444707134363566789644103637046138703732812593856489450966164422700871083271001476798525601830292237723021138499045286505397665962198734248957208942814238767855960753797521549548788530151996440657784060736603682776712677518537991291065233449586393186516770855075158900503486179189610821817031409223
e1 = 3
m1 = 80026450605919212347157319516655228661982088106956311148514121800139890113377161068043879513015347037232410178041918490832353137735848626795271143817272105057902549455690557715462777567966903851646207028020678373050285949287173514737755698953051536123368646144531895984034141177000138932645546381541544731963
e2 = 0x7478
m2 = 24789836942239403722795930341732835678691656750347230627416434227665247940527361150396455511246644544283832637661545664078814615114240744561273489461844843182114793772702713013603371781739673411384862756987736726406966123858749513205304608394157412210509128405578588422322912351914650629099969071449156118527
a,b,g = exgcd(e1, e2)
print a,b,g
print a * e1 + b * e2
print mod_inverse(m2, n)
r = (pow(m1, a) * mod_inverse(m2, n)) % n
print hex(r).decode('hex')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment