Rating:
## Ferman
### Challenge
> Modern cryptographic algorithms are the theoretical foundations and the core technologies of information security. Should we emphasize more?
>
> `nc 07.cr.yp.toc.tf 22010`
```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi talented participants, welcome to the FERMAN cryptography task! +
+ Solve the given equations and decrypt the encrypted flag! Enjoy! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Parameters generation is a bit time consuming, so please be patient :P
| Options:
| [P]rint encrypted flag
| [R]eveal the parameters
| [Q]uit
P
| encrypt(flag) = 6489656589950752810044571176882070993656025408411955877914111875896024399252967804237101085443293019406006339555779534657926807551928549712558667515175079267695028070934727514846970003337126120540450206565849474378607706030211234939933160392491902242074123763448231072583065175864490510115483208842110529309232348180718641618424365058379284549574700049803925884878710773408472100779358561980206902500388524570616750475958017638946408491011264747032498524679282489181606124604218147
R
e = 65537
isPrime(p) = True
isPrime(q) = True
n = p * q
(p - 127)**2 + (q - 184)**2 = 13809252727788824044233595548226590341967726502046327883413398709726819135921363848617960542444505497356040393690402758557636039683075007984614264314802550433942617885990971202110511768121760826488944622697964930982921462840320850014092598270493079542993367042001339267321218767132063176291998391714014192946596879176425904447127657664796094937171819714510504836456988487840790317576922986001688147359646287894578550322731904860694734616037751755921771706899493873123836562784063321
m = bytes_to_long(flag)
c = pow(m, e, n)
```
### Solution
On each connection, we are given a flag encrypted using RSA, with additional information in the form
$$
(p - a)^2 + (q - b)^2 = w
$$
On every connection, the integers $a,b,w$ are different, although $a,b$ are usually small ($a,b < 2000$ ).
**Lyutoon** and **Ratman** noticed that factoring $z$, it was always a seventh power $w = z^t$, which means we can write the equation as:
$$
x^2 + y^2 = z^7
$$
We can factor the left hand side by writing:
$$
x^2 + y^2 = (x + iy)(x - iy)
$$
and now we realise that by factoring $z^7$ as a Gaussian integer in $\mathbb{Z}[i]$:
$$
z = \prod_i (a_i + i b_i)
$$
we can obtain $x,y$, as $(x + i y)$ will be a divisor of $z \in \mathbb{Z}[i]$, and from this solve for $p,q$ to grab the flag.
Connecting again, we get:
```python
a = 2265
b = 902
w = 24007015341450638047707811509679207068051724063799752621201994109462561550079479155110637624506028551099549192036601169213196430196182069103932872524092047760624845002308713558682251660517182097667675473038586407097498167776645896369165963981698265040400341878755056463554861788991872633206414266159558715922583613630387512303492920597052611976890648632123534922756985895479931541478630417251021677032459939450624439421018438357005854556082128718286537575550378203702362524442461229
flag_enc = 10564879569008106132040759805988959471544940722100428235462653367215001622634768902220485764070394703676633460036566842009467954832811287152142597331508344786167188766356935684044757086902094847810694941751879500776345600036096556068243767090470376672110936445246103465175956767665996275085293250901512809704594905257754009538501795362031873203086994610168776981264025121998840163864902563628991590207637487738286741829585819040077197755226202284847
```
Obtaining the factors of $z \in \mathbb{Z}[i]$ we find:
```python
a = 2265
b = 902
z = w^(1/7)
K = ZZ[i]
gaussian_factors = factor(K(z))
# gaussian_factors (-I) * (-1236649975237776943493190425869173*I - 3575914522629734831030006136433790) * (-5*I - 4) * (4*I + 5) * (-1236649975237776943493190425869173*I + 3575914522629734831030006136433790)
```
We now know that $(x + iy)$ is some divisor of $z$, and knowing that $p,q$ are prime, we can find these easily
```python
z_test = (-1236649975237776943493190425869173*I - 3575914522629734831030006136433790)*(4*I + 5)
w_test = z_test**7
x_test = abs(w_test.imag())
y_test = abs(w_test.imag())
p = x_test + a
q = y_test + b
assert is_prime(p)
assert is_prime(q)
assert (p - a)**2 + (q - b)**2 == w
```
Finally, with `p,q` we can solve for the flag
```python
from Crypto.Util.number import *
p = 3515251100858858796435724523870761115321577101490666287216209907489403476079222276536571942496157069855565014771125798502774268554017196492328530962886884456876064742139864478104832820555776577341055529681241338289453827370647829795170813667
q = 3413213301181339793171422358348736699126965473930685311400429872075816456893055375667482794611435574843396575239764759040242158681190020317082329009191911152126267671754529169503180596722173728126136891139303943035843711591741985591269095977
phi = (p-1)*(q-1)
d = pow(0x10001, -1, phi)
print(long_to_bytes(pow(flag_enc,d,p*q)))
b'CCTF{Congrats_Y0u_5OLv3d_x**2+y**2=z**7}'
```
##### Flag
`CCTF{Congrats_Y0u_5OLv3d_x**2+y**2=z**7}`
