rsabin.py

from sage.all import *
import string

p = 123722643358410276082662590855480232574295213977
q = 164184701914508585475304431352949988726937945291
n = p * q
t = (p-1)*(q-1)
e = 31415926535897932384
rt = Integers(t)

#flag = open('flag').read().strip()
#assert len(flag) == 50
#m = int(flag.encode('hex'), 16)
#print gcd(t/16,e)
x = inverse_mod(e/16,t/16)
#print rt(x*e)
c = 19103602508342401901122269279664114182748999577286972038123073823905007006697188423804611222902
lower = int('hitcon{'.encode('hex') + '20'*43, 16)
upper = int('hitcon{'.encode('hex') + '7f'*43, 16)

squares = [mod(pow(c,x,n),n)]
sqrts = []


for i in range(4):
    for square in squares:
        try:
            #print ("square",square,hex(int(square)))
            s1 = mod(square,p)
            s2 = mod(square,q)
            ss1 = s1.sqrt()
            ss2 = s2.sqrt()
            #print(ss1,ss2)
            #print(int(ss1), int(ss2))
            (int(ss1),int(ss2))
            for s1m in [-1,1]:  
                for s2m in [-1,1]:
                    x = crt(int(mod(mod(ss1,n)*s1m,n)), int(mod(mod(ss2,n)*s2m,n)), p, q)
                    sqrts += [mod(x,n)]
        except ValueError:
            continue
    #print(sqrts)
    #print ""
    squares = sqrts
    #squares = list(set(squares))
    sqrts = []

for s in squares:
    s = int(s)
    low = (lower-s)/n
    high = (upper-s)/n
    diff = (high - low) / 0x100
    print(diff)
    s += low*n
    while s % 0x100 != 0x7d:
        s += n
    for i in range(diff):
        x = '%x' % (s,)
        h = ('0' * (len(x) % 2)) + x
        hh = h.decode('hex')
        if all(c in string.printable for c in hh):
            print(hh)
        s += 0x100*n