Factoring N by associated prime factors

2023-09-19

–

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 = }")

Python

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)
        
        print(long_to_bytes(flag).decode())
        break

Python

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:
            continue
        q = p**2 + 1
        assert q % 2 == 0
        if isPrime(q // 2):
            break

    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 = }")

Python

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)

print(long_to_bytes(c).decode())

Python

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.