Crypto solutions ASIS CTF finals

gracias.py

from sage.all import continued_fraction, Integer, inverse_mod

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c=(1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

def wiener(e, n):
    q0 = 1
    M = 1333337
    C = pow(M, e, n)
    for x in continued_fraction(Integer(e) / Integer(n)).convergents():
        q1 = int(x.denominator())
        # see Andrej Dujella. "A variant of Wiener’s attack on RSA"
        for r in range(10):
            for s in range(10):
                d = r*q1 + s*q0
                if pow(C, d, n) == M:
                    return d
        q0 = q1

n, e, a, g = pubkey
c1, c2 = c

d = wiener(e, n)
# d = 100556095937036905102538523179832446199526507742826168666218687736467897968451
k = pow(c1, d, n)
K = pow(g, k, a)
print '{:x}'.format(c2 * inverse_mod(K, a) % a).decode('hex')

handicraft.py

from sage.all import *
import base64

def factor(n,b):
    ''' p-1 factorization '''
    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)

hashcoll.txt

Just use "\o" and "\o/".....

interested_messages.sage

N = 198215811254578914143528679853394516943487191887133602719421229002835939155691362962056570747961133502365266191144307866755524824103871505056373013932585133835543321312227889313102212621888049039915064642604244253420464918662950537321433526102958541961921321562189585754292234269540520254519467706456342129214007611726103951423784590140561773123755857400629545080504437281815096797288082474978240553370503
enc = 90202671282140726938772231828532543465876394733342802972061264758729938518019431881534956868790097577690987026821010559147302121811579117273065376510961140002317015599909541782531328674281365144484724526798519803467240235138261486140279631210452738702091365452358994702604159240518573590663651781917664308109701267670633780136142501057454596418073159035730758145508658399991034098716891323263302795445575

## Find p.... Some guessing was needed here
# N=int(N)
# r=int(N^(1/3))
# p = r - 10000000
# up = r + 10000000
# while p < up:
    # if p % 1000000 == 0:
        # print p
    # if N%p == 0:
        # print 'p=',p
        # break
    # p += 1
# exit()

p = 583059350840498322495293827270996268277814817261340572149557041850334201169979322271355385635285998430821171194131461175804739753635743
q = 583059350840498322495293827270996268277814817261340572149557041850334201169979322271355385635285998430821171194131461175804739754635847
assert int(N)==int(p**2*q)

# Via GP/PARI: sqrt(enc + O(p^2)), sqrt(enc + O(q))
xp=144700724729106173481484195473900653740758779669983364485006587553456283802794245634995698477664928450548053686605705908119365419253227 + 468842531140345950122338162355890054828538173945384356724810331374305725217353127260194532581841836123218197498830229767032097160445681*583059350840498322495293827270996268277814817261340572149557041850334201169979322271355385635285998430821171194131461175804739753635743
xq=262892979042870799510054131669978888598382275897989723851511797254128556052624429073055178104422772883380630683634294164180017168498378

assert int(pow(xp,2,p**2))==int(enc%p**2)
assert int(pow(xq,2,q))==int(enc%q)
res = set()

for x1 in (xp,p**2-xp):
    for x2 in (xq,q-xq):
        assert int(pow(x1,2,p**2))==int(enc%p**2)
        assert int(pow(x2,2,q))==int(enc%q)
        x=crt([x1,x2], [p**2,q])
        assert int(pow(x,2,N)) == int(enc)
        assert int(pow(N-x,2,N)) == int(enc)
        res.add(int(x))
        res.add(int(N-x))

from oracle import revno
for x in res:
    a,b = revno(x)
    if 'ASIS' in a:
        print a.strip()

marijuana.py

# We find (via meet in the middle) a number g' with ~6 bits such that
# pk * g' has few bits set.
#
# Then (A*pk + B) * g' = A*pk*g' + B*g', which has low hamming weight, so we can
# distinguish this case from the -(A*pk + B) case.
import itertools
from collections import defaultdict

(n, p, h, pk) = 289, 994646472819573284310764496293641680200912301594695434880927953786318994025066751066111, 6, 843235888465494832763255804166953659073735483996382764878385572219936486704848907391083

nums = map(int,open('FLAG.enc').readlines())

def ham(x):
    return bin(x).count('1')

def decrypt(g):
    res = ''
    for i in range(len(nums)):
        x = nums[i]
        bit = int(ham(x * g % p) > 120)
        res += str(bit)
    return '{:x}'.format(int(res, 2)).decode('hex')

def enum(h, n):
    for indexes in itertools.combinations(range(n), h):
        yield sum(1 << i for i in indexes)

res = defaultdict(list)
for g1 in itertools.islice(enum(3, n), 10000):
    x = g1 * pk % p
    hash = x & 0xffff
    res[hash].append(g1)

for g2 in enum(3, n):
    x = -g2 * pk % p
    hash = x & 0xffff
    for g1 in res.get(hash, []):
        g = (g1 + g2) % p
        if ham(g * pk % p) < 20:
            flag = decrypt(g)
            if 'ASIS{' in flag:
                print flag
                exit()