README.md

Euclidean RSA

Challenge Description

Bob apparently likes squares, but what does it have to do with encryption?

Challenge Writeup

We first look at the code.

#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
from secret import flag, magic

while True:
	try:
		key = RSA.generate(2048)
		a,b,c,d = magic(key)
		break
	except:
		pass
assert a**2 + b**2 == key.n
assert c**2 + d**2 == key.n
for _ in [a,b,c,d]:
	print(_)
cipher = pow(bytes_to_long(flag), key.e, key.n)
print(cipher)

This seems to be standard RSA encryption. Since no value of $e$ has been passed to RSA.generate explicitly, it will take the default value of $e = 65537$. We are also given four numbers $a, b, c, d$ such that $a^2 + b^2 = c^2 + d^2 = n$, where $n$ is the public modulus.
If we can factorise $n$, we'd be done. We can decrypt the RSA encrypted ciphertext by the standard decryption method. We can, in fact, factor a semiprime when we are given its representation as the sum of two squares in two different ways as in the challenge. We can use Euler's Factorisation Method for the same.

We start by noting that

$$ \begin{align*} &a^2 + b^2 = c^2 + d^2\\ \implies &a^2 - c^2 = d^2 - b^2\\ \implies &(a-c)(a+c) = (d-b)(d+b)\\ \implies &kl(a+c) = km(d+b) \quad \text{where }k=gcd(a-c,d-b), (a-c)=kl, (d-b)=km\\ \implies &\frac{a+c}{d+b} = \frac{m}{l}\\ \implies &(a+c) = mh \text{ and } (d+b) = lh \quad \text{where }h=gcd(a+c, d+b) \end{align*} $$

Now we let $q = (k^2 + h^2)(l^2 + m^2)$ and see that it ends up simplifying to $q = 4n$. If we assume (an assumption that turns out to be correct in this challenge) that $k$ and $h$ are both even, then we must have: $$n = ((k/2)^2 + (h/2)^2)(l^2 + m^2)$$ Thus, we have successfuly factorised n!

The following script then gives us the flag:

from math import gcd
from Crypto.Util.number import *

a = 139488614271687589953884690592970545345100917058745264617112217132329766542251923634602298183777415221556922931467521901793230800271771036880075840122128322419937786441619850848876309600263298041438727684373621920233326334840988865922273325440799379584418142760239470239003470212399313033715405566836809419407
b = 68334789534409058399709747444525414762334123566273125910569662060699644186162637240997793681284151882169786866201685085241431171760907057806355318216602175990235605823755224694383202043476486594392938995563562039702918509120988489287149220217082428193897933957628562633459049042920472531693730366503272507672
c = 124011822519139836919119491309637022805378274989854408578991029026928119002489232335977596528581855016599610031796540079373031282148998625318658034408770283112750172223328012238338715644743140990997114236125750813379366262418292349962679006556523851370694404238101553966330965676189731474108393418372330606063
d = 93529593432394381438671783119087013080855868893236377597950059020717371498802208966524066540234253992421963224344343067174201693672350438201011499762718490958025617655722916641293034417795512315497126128726644064013248230211347407788186320320456853993252621916838570027019607155835349111757703654306736031792
ct = 2819638499688340337879314536945338371611392232636746056275506290935131270682791584873534866138393305591899169164183372576878693678187335219904407119253951099126339949954303448641761723704171837075206394491403411400326176280981393624784437102905397888236098861970020785226848615566768625581096019917060387964269283048823007992992874533775547300443032304973521568046956516203101626941042560505073773998143068621715480774707735064134961852206070850277695448391038882766344567740211926618750074636868149063283746597347807257171871016202588384726430246523650462866812935130465049824665395626882280287488078029119879891722

k = gcd(a-c, d-b)
l = (a-c)//k
m = (d-b)//k

h = gcd((a+c), (d+b))

assert k % 2 == 0
assert h % 2 == 0

p = (k//2)**2 + (h//2)**2
q = l**2 + m**2

n = a**2 + b**2
assert p*q == n

e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
pt = pow(ct, d, n)
print(long_to_bytes(pt).decode())

We obtain the flag:
ENO{Gauss_t0ld_u5_th3r3_1s_mor3_th4n_on3_d1men5i0n}

---

^{Author: Nilabha}