handicraft.py

from sage.all import *
import base64

def factor(n,b):
    M=1
    print 'start'
    a = 2
    i=0
    for q in primes(b):
        i+=1
        if i % 1000 == 0: print 'Progress:', q, b
        base = 1
        while base*q <= n:
            base *= q
        a = pow(a, base, n)
        g = gcd(a-1,n)
        if g != 1 and g != n:
            return g
    assert 0

n=0xABE9BB887BAB05AF46F2E8C4893A59EF5687395361417A5DEA3090361C0C377843E891E4BF41D2C662707C67B41275C3B6346B696992E8E6334F8F8B4AB5ECCFD224586CD1949E250BB5874BC0F735621660708FE1346DD8DD139565D69BD9C50AB117A90DC85A0610A50BCACEC76C7AD9C86492F5B5FD70433184EAB6E46EF51195405BCC14AE89D9268B4918E50C69D897DBE8E508EB8EF3C7674FC49A437DF48235F7D52035183AFAE0631221B391E6085DD71020B755F68AB5171E2F924CF11D2ACF99D553636CF213EF4953FEEFF8BB1B8E3B7235B5E75B22D23A01ED1A41A65BB8E1593C4D75C3024D0965D5BA2B0267EC84DA5F4E0000000000000001
e=0x10001

p = factor(n, 2**22)
# p = 139457081371053313087662621808811891689477698775602541222732432884929677435971504758581219546068100871560676389156360422970589688848020499752936702307974617390996217688749392344211044595211963580524376876607487048719085184308509979502505202804812382023512342185380439620200563119485952705668730322944000000001

assert n%p==0
q=n/p
d=inverse_mod(e,(p-1)*(q-1))
assert p*q==n

c = base64.b64decode('''eER0JNIcZYx/t+7lnRvv8s8zyMw8dYspZlne0MQUatQNcnDL/wnHtkAoNdCalQkpcbnZeAz4qeMX
5GBmsO+BXyAKDueMA4uy3fw2k/dqFSsZFiB7I9M0oEkqUja52IMpkGDJ2eXGj9WHe4mqkniIayS4
2o4p9b0Qlz754qqRgkuaKzPWkZPKynULAtFXF39zm6dPI/jUA2BEo5WBoPzsCzwRmdr6QmJXTsau
5BAQC5qdIkmCNq7+NLY1fjOmSEF/W+mdQvcwYPbe2zezroCiLiPNZnoABfmPbWAcASVU6M0YxvnX
sh2YjkyLFf4cJSgroM3Aw4fVz3PPSsAQyCFKBA==''')

from Crypto.PublicKey import RSA
key = RSA.construct((long(n), long(e), long(d), long(p), long(p)))
for s in range(18,23):
    msg = c
    for _ in range(s):
        msg = key.decrypt(msg)
    print repr(msg)