Rating:

We are given

```
n=26706945871223798806946567625795745310647399659910598613997438170254676906320884787067291531568519581570486505530743159364695624192713907899891271681764762953336380737131975766376099738961455030059224153288449157216742686968813567875985953638444306291312518875724353663737051438038036035099564144122022281552250120947444532179363543166124147017052863439430843377077740483023785112229296507447979037935294981520399432954250262200308445567157808086777018246204173836071669692996120543482828072165197963284007401424318760488753193259221799398791420356909875006600265454926001793243794296606402995498420890137289762372317
e=65537
c=23019210926096019439662080022606555682160756482834075327688353681886906610735890281790270131457122119250965229008288515731486979333114095719712091659318484794730767674622587987581809466359299442767153506617978770320841352703398756153820807425217273950725518164059399873031742670470133617642452981854757791219145490367164586994610571438029547154710468508564665436778777102606301409620497016801946989455522437287686118571821432746989660390518300438262592025889870066232387034421405728002475182042809287138843339136122128603871664518171161801772950796600043855925127506164323670825747150515557156102573381266827793503914
2d+phi(n)=37732317402097892656548210368059150520715311244186827321460515339110825509994606476441219328574059681654107935415953369600005791889525955066919184173730927777542439132137456187316767857542892181069605145389028008447003177489965519989581906591202747002126347010093645064766054828212106925552838747800759084251589866089273026254966234164176466563186438248776961541146620434009503689100128122320997739428424975306256417865610162074912031638292878093662017512614000114412433772628503843778614582386663028723327141014781803346402661832265806675785945746391801332346416280561063520342062390151626459813123281193179325458386
```

Let $s = 2d + \phi(n)$. Then $\phi(n) = s - 2d$. Since $ed = 1 \pmod {\phi(n)}$, there is natural $k$, such that
$$
ed = k \phi(n) + 1
$$
$$
ed = k(s - 2d) + 1
$$
$$
ed + 2kd = ks + 1
$$
$$
d = (ks+1)/(e+2k)
$$

This expression depends on choice of $k$ only. So if we could bound the range of search, we could find the value of $d$ quickly.
Indeed, since $d < phi(n)$,
$$
ed = k \phi(n) + 1 \Rightarrow k = (ed - 1)/\phi(n) < e \cdot \frac d {\phi(n)} < e
$$
$e$ is small, so we can brute force whole search space:
```python
candidates = {(k*s+1)//(e+2*k) for k in range(1, e) if (k*s+1)%(e+2*k) == 0}
for d in candidates:
dec = pow(c, d, n).to_bytes(n.bit_length()//8, 'big')
if b'easyctf' in dec:
print(dec.strip(b'\0'))
```
```
b'easyctf{1n1n77n9x2db57dqbk}'
```