Gaussian Integer is represented as $a + bi$. Simply can think as complex number with integer coefficients.
Surprisingly, we can use this Gaussian integer to factorize the numbers. Let’s see some challenges using Gaussian integer.
Euclidean RSA – [nullcon CTF]
#!/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)The code is simple enough, just generate the RSA key and make the variables $a, b, c, d$ which matches $a^2 + b^2 = c^2 + d^2 = n$.
There is various solutions for this challenge, but in this post, I would explain the solution which uses Gaussian Integer. So, how can we use gaussian integer in this equation?
We can assume that $ a + bi = rs$ and $a \,-\, bi = \bar{r}\bar{s}$, and also can assume that $ c + di = r\bar{s}$ and $c \,-\, di = \bar{r}s$. In addition, trivially n will be $r\bar{r}s\bar{s}$.
We can simplify these equations, like this
$$ ad = \frac{(rs + \bar{r}\bar{s})}{2} \times \frac{(r\bar{s}\, -\, \bar{r}s)}{2i} $$$$ bc = \frac{(rs \,- \,\bar{r}\bar{s})}{2i} \times \frac{(r\bar{s} + \bar{r}s)}{2}$$$$ ad \,-\,bc = \frac{(r\bar{r}\bar{s}^2 \,-\, r\bar{r}s^2)}{2i}$$
Because the $r\bar{r}$ is an integer, $ad \,-\, bc$ has factor $r\bar{r}$, and it is the factor of n also. So when we calculate GCD of $ad \,-\, bc$ and $n$, we can get one factor of n easily.
from Crypto.Util.number import *
from output import a, b, c, d, ct
'''
a = 139488614271687589953884690592970545345100917058745264617112217132329766542251923634602298183777415221556922931467521901793230800271771036880075840122128322419937786441619850848876309600263298041438727684373621920233326334840988865922273325440799379584418142760239470239003470212399313033715405566836809419407
b = 68334789534409058399709747444525414762334123566273125910569662060699644186162637240997793681284151882169786866201685085241431171760907057806355318216602175990235605823755224694383202043476486594392938995563562039702918509120988489287149220217082428193897933957628562633459049042920472531693730366503272507672
c = 124011822519139836919119491309637022805378274989854408578991029026928119002489232335977596528581855016599610031796540079373031282148998625318658034408770283112750172223328012238338715644743140990997114236125750813379366262418292349962679006556523851370694404238101553966330965676189731474108393418372330606063
d = 93529593432394381438671783119087013080855868893236377597950059020717371498802208966524066540234253992421963224344343067174201693672350438201011499762718490958025617655722916641293034417795512315497126128726644064013248230211347407788186320320456853993252621916838570027019607155835349111757703654306736031792
ct = 2819638499688340337879314536945338371611392232636746056275506290935131270682791584873534866138393305591899169164183372576878693678187335219904407119253951099126339949954303448641761723704171837075206394491403411400326176280981393624784437102905397888236098861970020785226848615566768625581096019917060387964269283048823007992992874533775547300443032304973521568046956516203101626941042560505073773998143068621715480774707735064134961852206070850277695448391038882766344567740211926618750074636868149063283746597347807257171871016202588384726430246523650462866812935130465049824665395626882280287488078029119879891722
'''
n = a**2 + b**2
assert n == c**2 + d**2
p = GCD(a*d - b*c, n)
q = n // p
phi = (p-1) * (q-1)
d = inverse(0x10001, phi)
flag = pow(ct, d, n)
print(long_to_bytes(flag).decode())And the flag tells us about the dimension lol
easy factoring – [Zer0pts 2023]
And let’s look about more SIMPLE gaussian integer. Maybe this challenge is further simple than upper one, but there was a sage skill issue for me XD
import os
import signal
from Crypto.Util.number import *
flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")
def main():
p = getPrime(128)
q = getPrime(128)
n = p * q
N = pow(p, 2) + pow(q, 2)
print("Let's factoring !")
print("N:", N)
p = int(input("p: "))
q = int(input("q: "))
if isPrime(p) and isPrime(q) and n == p * q:
print("yey!")
print("Here you are")
print(flag)
else:
print("omg")
def timeout(signum, frame):
print("Timed out...")
signal.alarm(0)
exit(0)
if __name__ == "__main__":
signal.signal(signal.SIGALRM, timeout)
signal.alarm(30)
main()
signal.alarm(0)Yeah we need to get $p$ and $q$ value with the only info of $p^2 + q^2$. Automatically, we can think about the $N = p^2 + q^2 = (p + qi)(p\, -\,qi)$ now lol.
This means we can factor N into two Gaussian Integer, and the sage computes divisors of N automatically 🤯
from pwn import *
# context.log_level = "debug"
while True:
REMOTE = 1
if REMOTE:
io = remote("crypto.2023.zer0pts.com", int(10333))
else:
io = process(["python3", "server.py"])
io.recvuntil(b"N: ")
N = int(io.recvline().strip().decode())
print(f"[*] N = {N}")
print("[*] Solving diophantine equation")
G = GaussianIntegers()
Gn = G(N)
for d in divisors(Gn):
p, q = abs(d.real()), abs(d.imag())
if is_prime(p) and is_prime(q) and d.norm() == N:
print("[*] Solved!!")
break
io.sendlineafter(b"p: ", str(p).encode())
io.sendlineafter(b"q: ", str(q).encode())
res = io.recvline().strip()
if res == b"omg":
print("[*] Failed..")
else:
io.recvline()
flag = io.recvline().strip().decode()
print(flag)
break
io.close()The solver took a lot of time but finally, I could solve it 🙂
답글 남기기