Factoring N by associated prime factors



Factoring N is very very important problem for RSA crypto system. If we could factor N, the crypto system will be cracked and can be easily decrypted. So it is safe to say that the difficulties of RSA encryption systems depend on factorization.

In some CTF challenges such as sus - [ImagianryCTF 2023] and cry - [Wacon 2023], they calculate N with some related factors. so we could factor N into three factors. Let’s see the challenges.

Sus – [ImaginaryCTF 2023]

from Crypto.Util.number import getPrime, isPrime, bytes_to_long

def sus(sz, d):
	while True:
		p = getPrime(sz)
		pp = sum([p**i for i in range(d)])
		if isPrime(pp):
		return p, pp

p, q = sus(512, 3)
r = getPrime(512 * 3)
n = p * q * r
e = 65537
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

The code is very simple. The only information is $N = p \times (p^2 + p + 1) \times r$. Honestly, I didn’t get any clues to solve this challenge while the CTF was running, so I saw the write-ups on the discord. Let’s see the basic ideas.

Let me explain in a little bit more detail for people who don’t understand (I was also hard understand it when I saw it lol).

Let’s think about the $GF(p^k)$ (and the operation of the group is multiplication). The cardinality of this field is $p^k$, and except zero, every elements have inverse element. So the cardinality of invertible group is $p^k – 1$. And by the Lagrange theorm, the subgroup of invertible group’s cardinality must be divisors of $p^k – 1$. So for any element, the value of $a^{(p^k – 1)}$ will be 1.

Hence, when we calculate $a^n$ when $n = p \times q \times r$, the order of $a^n$ will be $p-1$ usually. And if the order is $p-1$, the element must be expressed as $u + 0x + 0x^2$ in GF field.

from output import *
n = 1125214074953003550338693571791155006090796212726975350140792193817691133917160305053542782925680862373280169090301712046464465620409850385467397784321453675396878680853302837289474127359729865584385059201707775238870232263306676727868754652536541637937452062469058451096996211856806586253080405693761350527787379604466148473842686716964601958192702845072731564672276539223958840687948377362736246683236421110649264777630992389514349446404208015326249112846962181797559349629761850980006919766121844428696162839329082145670839314341690501211334703611464066066160436143122967781441535203415038656670887399283874866947000313980542931425158634358276922283935422468847585940180566157146439137197351555650475378438394062212134921921469936079889107953354092227029819250669352732749370070996858744765757449980454966317942024199049138183043402199967786003097786359894608611331234652313102498596516590920508269648305903583314189707679
e = 65537
c = 27126515219921985451218320201366564737456358918573497792847882486241545924393718080635287342203823068993908455514036540227753141033250259348250042460824265354495259080135197893797181975792914836927018186710682244471711855070708553557141164725366015684184788037988219652565179002870519189669615988416860357430127767472945833762628172190228773085208896682176968903038031026206396635685564975604545616032008575709303331751883115339943537730056794403071865003610653521994963115230275035006559472462643936356750299150351321395319301955415098283861947785178475071537482868994223452727527403307442567556712365701010481560424826125138571692894677625407372483041209738234171713326474989489802947311918341152810838321622423351767716922856007838074781678539986694993211304216853828611394630793531337147512240710591162375077547224679647786450310708451590432452046103209161611561606066902404405369379357958777252744114825323084960942810
from Crypto.Util.number import *
R = PolynomialRing(Zmod(n), "x")

while True:
    Q = R.quo(R.random_element(3))
    res = gcd(int(list(Q.random_element() ^ n)[1]), n)
    if res > 1:
        p = res
        q = p^2 + p + 1
        r = n // (p*q)
        assert p * q * r == n
        phi = (p-1)*(q-1)*(r-1)
        d = inverse(e, phi)
        flag = pow(c, d, n)

Now here is the implementation by organizers.

After I first encountered this way of thinking, I thought it was really new. Let’s look at another problem using this.

Cry – [Wacon 2023]

This challenge is similar with sus. The whole encryption pass through the encryption 3 times, but we can convert this challenge to a simple challenge which make us to factor N.

from Crypto.Util.number import bytes_to_long, getStrongPrime, isPrime

SIZE = 512
e = 65537

with open("flag.txt", "rb") as f:
    m = bytes_to_long(f.read())

def encrypt(m):
    while True:
        p = getStrongPrime(SIZE)
        if p % 4 != 3:
        q = p**2 + 1
        assert q % 2 == 0
        if isPrime(q // 2):

    r = getStrongPrime(SIZE * 3)
    n = p * q * r
    c = pow(m, e, n)
    return n, c

if __name__ == "__main__":
    n0, c0 = encrypt(m)
    n1, c1 = encrypt(c0)
    n2, c  = encrypt(c1)
    assert m < n0 and c0 < n1 and c1 < n2

    print(f"{n0 = }")
    print(f"{n1 = }")
    print(f"{n2 = }")
    print(f"{c = }")

So now, how can we factor N which is $N = p \times (p^2 + 1) \times r$ where $p \equiv 3 \pmod{4}$? As similar to sus, we can think about the $p^4 – 1$. Let’s think similar with sus. To make the $p^2 + 1$ useful, we can make $GF(p^4)$ and calculate the $\alpha^n$ so that the order of $\alpha^n$ be $p^2 – 1$.

But if the order is $p^2 – 1$, we cannot make some coefficients to zero. So we need to think $p^2$ in a bundle. If we make the Galois Field with polynomial $x^4 + a x^2 + b$, every element of order $p^2 – 1$ can be expressed as $c x^2 + d$.

Let’s see the code of soon-haari the god of cryptography XD

import random
from Crypto.Util.number import *

exec(open("output", "r").read())

for n in [n0, n1, n2][::-1]:
    P.<x> = PolynomialRing(Zmod(n))

    while True:
        poly = x^4 + random.randrange(0, n) * x^2 + random.randrange(0, n)
        y = P.quotient(poly).gen()

        p = gcd(n // 2, ZZ(list((y + 1)^n)[1]))
        if p > 1: break

    q = (p^2 + 1) // 2
    r = n // (2 * p * q)
    assert p * q * r * 2 == n

    phi = (p - 1) * (q - 1) * (r - 1)
    d = pow(65537, -1, phi)
    c = pow(c, d, n)


There are few different solutions on the internet, but I couldn’t understand other solutions. If we think about the conditions in challenge again, the $p \equiv 3 \pmod{4}$ condition isn’t used in this solution. So I want to know why there is this condition, and also want to understand this sol from sahuang.

I want anyone help me understand it 🙁
Thanks for reading my post.

“Factoring N by associated prime factors” 에 하나의 답글

  1. 민순 아바타

    sahuang님의 풀이는 quotient를 $x^2(x + a)^2 + 1$로 설정한 풀이입니다.

    order을 계산한 방식은 다르지만, 근본적인 원리는 동일합니다.

    $(x + a)^2(x + b)^2 + c$를 quotient로 사용한다면, $b = 0, c = 1$을 대입하면, sahuang님의 $x^2(x + a)^2 + 1$와도 대응시킬 수 있고,

    $b = -a$인 경우에는$(x^2 – a^2)^2 + c = x^4 + (-2a^2)x^2 + (a^4 + c)$가 되어, 제 $x^4 + ax^2 + b$꼴의 quotient와도 대응시킬 수 있어 동일한 원리인 것으로 보입니다.

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다