Tags: coppersmith fermat rsa
Rating: 5.0
# Old School (crypto, 14 solved, 740p)
In the task we get 3 parts [part1](part1.txt), [part2](part2.txt), [part3](part3.txt).
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:
```python
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:
```python
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.
```python
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.
```python
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:
```python
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:
```python
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!!!!}`
