crypto_old_school

Old School (crypto, 14 solved, 740p)

In the task we get 3 parts part1, part2, part3. It seems each one is RSA public key with encrypted data.

Part3

We're writing this in reverse order, because this is how we solved it. The last part was the simplest, because it was clear how primes were generated:

tmp.nbits()
1024
p = next_prime(1337*tmp + randint(2, 2**512))
q = next_prime(7331*tmp + randint(2, 2**512))
n = p * q

So we can see that high bits of both primes are the same, the difference is potentially at low 512 bits. This means that if we calculate isqrt(N) then the high bits should correspond to high bits of p and q.

We can approximate p or q use Coppersmith method to calculate the real value. The approximation of q we can get simply from isqrt of N, divided by the multiplier of p and then we can subtract 2**512 to get close to initial tmp value:

tmp = isqrt((N)/(1337*7331))
q_approx = 7331*tmp - 2**512

Now we can create a polynomial P(x) = x - q_approx mod N and the root x0 of this polynomial would be a value such that q_approx - x0 mod N == 0 which means q_approx - x0 must be a factor of N (we omit the obvious degenerated case where q_approx - x0 == 0). Since N has only two factors p and q, then it has to be one of them.

Using Coppersmith method we can find such roots, as long as they are relatively small. In our case we know that q_approx can't be very far from the real q and thus the root x0 has to be small.

N = 139713689065649193238602077859960857468098993135221000039102730899547298927683962573562384690733560045229965690142223836971463635696618075169874035306125645096696682021038045841133380609849851790395591047968701652975799368468556274243238594974251982826875184190103880810901174411829635180158201629467635591810569775155092318675639049754541256014635438864801255760305914815607547032463796789980267388517787537827413511219215383011915710116907720461035152786018808394261912036183662986050428253151429051345333273081222126466016921456969903177087878715836995228953335073770833282613911892360743789453583070756075529298371748549

c = 124685720137286087974637083454831701339966293804422893085596270389405855619404156520743766929373287868106538299589424038783043194334560243812640561592652200368376115611247891237635032352102375266455486004707355213472127905734695141272493858057378951812357840535403155691798886254882859468912066573675006464518263526982997249121158520551576258448776707985773899806354192979203812074933169737618274419084890323034162520302687449736028470908248699174457011959674081295825304524826030316907668167104468182549336009917924574890737992068942209504351840515837871695539713067102504739121645006079782283023187240752494388988784497294

hidden = 512
tmp = isqrt((N)/(1337*7331))
q_approx = 7331*tmp - 2**512
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x - q_approx
roots = f.small_roots(X=2**hidden, beta=0.5)
for delta in roots:
    print('delta', delta)
    print('q_approx - delta', q_approx-delta)
    q = q_approx-delta
    p = int(N)/int(q)
    d = inverse_mod(65537, (p-1)*(q-1))
    print("d", d)
    decrypted = hex(int(pow(c,d,N)))
    print('flag =', decrypted[2:-1].decode("hex"))

From this we get private key and can decrypt the flag: sch0Olllllllllllllllllllll!!!!}

Part2

In this part we didn't know exactly how the modulus was generated but if we look at hex representation we can see:

0x100000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a9d11f4b6f5b4331ac1d207a3c618adaea44ed000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000176a7f4d50f6d91d860184d79edff9b7eca7872ef07383cf2852f1e780f32fc1

This means few things:

1. There are most likely 2 numbers multiplied
2. Both numbers generated from some common root with mostly 0 bits
3. There is 0x1000001 multiplier involved, but we don't know exactly which number was multiplied by which part.
4. The random difference between numbers on low bits has to be small, about 128 bits.

We can again use Coppersmith method here, but since we don't know how the multiplier was split, we simply test all possiblities.

N = 32317007997554674385349615891817642773386605194812774888699399085196191794571384182422952167619837501795723538528931327159587983358628859504590723914892119478718126207089276060309706774425448653115310296039404328801754660372655218697443296169226536829110407154367147778475282279643613957212146771061477882859160052927335260673353787015976402719590523208336436450340211718238793469564080171762430651352930734689263596836122378167570929701725793689221407150157994038959493338968844604240687047300165564661354163479888199791831857521168174860532936751952480913605385678113510666108924260168617210436143153585499118186433
e = 65537
c = 3276317031877048034921689870842067102082984132116094274739382394942015587590724787158982350802646840240494972561882263073240227808400607161162982258260014527796718342988907758893432031368754237249396935435825620816173572853468606403492532489569016730369554744690415453811865812653908391295808987211722639212793730193965857595902086835233937795612266373947212176592539984179545181633416734531184100728289921617009799700655919616113513377725551467929505260502666912513988565860061157100733206213776142272254528206526835704772005607585391210115528195828817631620260680401489038612476650344781706860508085522520661975350
hidden = 256
tmp = isqrt((N)/(0x1000001))
for mult in [1, 97, 65281, 257, 172961, 24929, 16777217, 673]:
    q_approx = mult * tmp + 2**128
    F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
    f = x - q_approx
    roots = f.small_roots(X=2**hidden, beta=0.5)
    for delta in roots:
        q = q_approx-delta
        if is_prime(q):
            print(q)
            p = gcd(N,q)
            q = int(N)/int(p)
            print(p)
            phi = (p-1)*(q-1)
            d = inverse_mod(int(e), int(phi))
            print('d', d)
            decrypted = hex(int(pow(c,d,N)))
            print('flag =', decrypted[2:-1].decode("hex"))

From this we get _aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_

Part1

This part was for us the hardest, because nothing was known. The modulus looked normal and there was no indication what could we do.

Later we learned that primes were close and it could be factored using fermat, which we actually even have in crypto-commons:

from crypto_commons.generic import fermat_factors
n1 = 12263815858436391339801252716055343215721551207190585812808883921492616938019767754888047221243921529199781329682187336097470283133260860905444173937906698593993435816362355791049334301256672146334457160396157422171213155186704409015520723701624704179794619860512757194475928285433621469983215042163268337482613981138412642113164161985610041212644438310461087934752877418645890869616237437302541973412868157911349542527624597832254480191497600938121405413426358837072839977429474448232347107365820912432960433009928432513624193587173708951345864949412064817411473475077328080824358689398099979260395549956349458200199
p1, q1 = fermat_factors(n1)
print(p1,q1)

But we didn't realise that, and primefac or RsaTool didn't find the factorization. A desperate move from our side was to brute-force the flag. The idea was that part2 and part3 were not very imaginative: _aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_sch0Olllllllllllllllllllll!!!!} and the task name was Old School, so we guessed that probably the first part of the flag will be some kind of ooollllddd.

So:

n = 12263815858436391339801252716055343215721551207190585812808883921492616938019767754888047221243921529199781329682187336097470283133260860905444173937906698593993435816362355791049334301256672146334457160396157422171213155186704409015520723701624704179794619860512757194475928285433621469983215042163268337482613981138412642113164161985610041212644438310461087934752877418645890869616237437302541973412868157911349542527624597832254480191497600938121405413426358837072839977429474448232347107365820912432960433009928432513624193587173708951345864949412064817411473475077328080824358689398099979260395549956349458200199

c = 10768566524581730417282966534533772232170128646105592645274840624344800039953305762328123247486367933169410426551021676301441508080687130308882531249672782247453418751384028303096785698132140306753136583313099836328879191020815311025909775009768461235238724055399564994913948731120265357427622567179898229336239135361607806956357971819975387160453721508112358768552880424521729959498368682405606641964356553284372394601190105374421489502575623037672340535664494377154727704978673190317341737416683547852588813171964475428949505648909852833637140722157843587170747890226852432960545241872169453977768278393240010335066

msg = 'MeePwnCTF{'

for i in range(0, 32):
    for ii in range(0, 32):
        for j in range(0, 32):
            for k in range(0, 32):
                msg = 'MeePwnCTF{' + '0' * i + 'O' * ii + 'l' * j + 'd' * k
                if len(msg) > 32:
                    continue
                x = pow(int(msg.encode('hex'), 16), 65537, n)
                if x == c:
                    print '!!!!', msg
                    break

And to our amazement, it actually found the flag part: MeePwnCTF{0ldddddddddddddddddd

So finally the flag was MeePwnCTF{0ldddddddddddddddddd_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_sch0Olllllllllllllllllllll!!!!}