Rating:

# Complicated Function

[Video](https://www.youtube.com/live/9IUsP3CBwZc?si=qW7hPpInPMRE6ovD&t=911)

Experiments show that `D = f(p)-p` is a fixed value.
we can perform prime factorization by solving the equation `x*(x+D)=N`.

```py
from Crypto.Util.number import *

x = var('x')
D = 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503042044 + 2**1023
N = 36517404305297844159564250986998364545749151568667732337564141796428285198409567155495468780386611544242689580089026301007867731616501462571857014948329304677585682534513311931280592743677919741211277066420279973665839898693462080087384474270473468411814863104608060945012301810206919347219744349831947632420533489933798065496290612931089442978868423837068735855183319271953531607892676482508704408482509645764820088854762889436761417245871075875762331247987854763068633058894469255779600684845456979405817748289218533715177711802661303055514957438072072036882111277967476497338901040854808789173453802590826788192053
c = 10955441460830702971387335888341162305090757526159743008807609823673521696863955454033040842132899414049783504960968117620860408142538216669369693386110678382112863315608217382774969191050306778748875856817288367369848881561750362221050586276876239956129985854245190619132772579774800480316624847309710595491090120189333272498817039509311650265968036568364234815921263181086438290844976279974023236010641698308664245573159698211860696725554580817928576304048869309097043078452170158082597167199813821750238244173483019805092246803337196768846732908994751887507198151471659940647272634351206676375579258509003076141110
p = solve(x*(x+D) == N, x)[0].rhs()
q = p+D
e = 65537
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
print(long_to_bytes(int(pow(c, d, N))))
```

Original writeup (https://github.com/x-vespiary/writeup/blob/master/2023/11-tsg/crypto-complicated-function.md).