Modern cryptographic algorithms are the theoretical foundations and the core technologies of information security. Should we emphasize more?
This challenge only gives us a server to connect to with the following interactions:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ 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) = 48790321481981070334284834897002743904143367742567080121139875503627677163558938442363151365001170923856543352995009198916999044114034490190573783771904020525587752191210344256704686085230514048180152780013748635642271859330908866389413727451104623973255339543797167920503564005931662152602543251766255090842659435974220819895436577204154690210899973842334999175452720629152039181296261452873185143203984819655252786655755387428741502392505402920556814585424516239256655975181009
| Options:
| [P]rint encrypted flag
| [R]eveal the parameters
| [Q]uit
R
e = 65537
isPrime(p) = True
isPrime(q) = True
n = p * q
(p - 582)**2 + (q - 25)**2 = 14631667335665376436840829964208352592651640426073578145070933715959789971380009994599228441748977871671891122780871174585035107716073801876075537824911946177667748022294940252232874085867015283835699627140037360866815484198487657307973080528934669763321149163146222720745301051643570903526702386861550873974220860941488324946388489501970762170927237645397125403189863229303743865435714328534902839262771017996292025035300502112811380090440713136701311095838411721435477641677265625
m = bytes_to_long(flag)
c = pow(m, e, n)
| Options:
| [P]rint encrypted flag
| [R]eveal the parameters
| [Q]uit
Clearly the goal here is to solve for \(p,q\) and we are given a sum-of-two-squares expression. This can easily be solved by factoring in \(\mb Q[i]\), more specifically, note that we have
\[x^2+y^2=k\] \[(x+iy)(x-iy)=k\]
hence we simply pair up the factors of \(k\) as complex conjugates to determine possible values of \(p,q\), then check if they are prime. Do note that one needs to convert the ring back to \(\mb Z\) otherwise sage’s is_prime would attempt to factor in \(\mb Z[i]\) or \(\mb Q\).
Solution at solve.sage
Flag:
CCTF{Congrats_Y0u_5OLv3d_x**2+y**2=z**7}