Factoring with Gaussian Integer

Gaussian Integer is represented as $a + bi$. Simply can think as complex number with integer coefficients.

Gaussian integer – Wikipedia

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or [1]

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)

Python

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())

Python

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)

Python

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()

Python

The solver took a lot of time but finally, I could solve it 🙂