Factoring N by associated prime factors

by

in

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.

“Factoring N by associated prime factors”에 대한 125개의 응답

  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와도 대응시킬 수 있어 동일한 원리인 것으로 보입니다.

  2. sklep internetowy 아바타

    Wow, fantastic weblog format! How lengthy have you been running a blog for?

    you made blogging glance easy. The entire glance of your website is excellent, as smartly as the content!
    You can see similar here e-commerce

  3. mozggogo 아바타

    Beatus ille, qui procul negotiis — Блажен тот, кто вдали от дел.

  4. razumdodo 아바타

    Ab imo pectore — С полной откровенностью.

  5. psychologist-online 아바타

    Ad futuram memoriam — На долгую память.

  6. Psypsy 아바타

    Ars vitae — Искусство жизни

  7. psychologist-online 아바타

    Contra vim mortis non est medicamen in hortis — Против силы смерти в садах нет лекарств.

  8. Alter 아바타

    Concordet sermo cum vita — Пусть речь соответствует жизни.

  9. psychologist-online 아바타

    Aquila non captat muscas — Орёл не ловит мух

  10. psikholog-onlayn 아바타

    Aut non tentaris, aut perfice — Или не берись, или доводи до конца.

  11. Psixoterapevt 아바타

    Фрейд Зигмунд и популярные статьи по психологии.

  12. filmb 아바타

    Dictum – factum

  13. onlinem 아바타

    Cogito ergo sum

  14. onlinee 아바타

    100 лет тому вперед смотреть фильм онлайн. 100 лет тому вперед смотреть онлайн бесплатно.

  15. smotrety 아바타

    100 лет тому вперед 2024 смотреть онлайн. Кошмаров смотреть онлайн.

  16. geinoutime.com 아바타

    geinoutime.com
    “이건…” Li Chaowen이 어색하게 말했다. “Baiyun Temple은 그들을 무시했습니다.”

  17. geinoutime.com 아바타

    geinoutime.com
    이것은 진나라와 한나라 시대에 내려온 전통으로, 부르면 수많은 사람들이 응답한다.

  18. geinoutime.com 아바타

    geinoutime.com
    Hongzhi 황제는 얼굴에 분개 한 표정을 지었고 이제야 Jiaozhi가 구덩이, tiankeng임을 깨달았습니다.

  19. k8 カジノ 아바타

    k8 カジノ ビンゴ
    素晴らしい記事です。思わず共有したくなりました。

  20. geinoutime.com 아바타

    geinoutime.com
    사실 Fang Jifan은 말하는 것 외에도 상대방이 말하고 싶은 것을 알고있었습니다.

  21. k8 カジノ 아바타

    k8 Jackpot
    興味深い視点と深い洞察を提供してくれてありがとうございます。

  22. geinoutime.com 아바타

    geinoutime.com
    Hongzhi 황제는 미소를지었습니다. “나는 … 이런 의도가 있습니다.”

  23. k8 カジノ 아바타

    k8 カジノ kyc 時間
    このブログはいつも私の期待を超える情報を提供してくれます。本当にありがとう。

  24. k8 カジノ 아바타

    モンスターハンター(V2.2)
    このブログは私の思考を広げるのに役立ちます。いつもありがとうございます。

  25. k8 カジノ 아바타

    k8 カジノ エアドロップ
    この記事から多くを学びました。引き続きフォローします。

  26. k8 カジノ 아바타

    闇の花(特殊大賞燈)
    実用性が高く、読んでよかったです。素晴らしい記事です!

  27. k8 カジノ 아바타

    k8 カジノ 誕生日ボーナス
    いつも興味深いトピックを提供してくれてありがとう。

  28. geinoutime.com 아바타

    geinoutime.com
    Zhu Houzhao는 “그러나 그들은 참수하지 않았습니다. “라고 정직하게 말했습니다.

  29. geinoutime.com 아바타

    geinoutime.com
    그러나 몸을 굽히자 갑자기 몸이 흔들렸다.

  30. 슬롯 아바타

    geinoutime.com
    “예.” 승무원은 황급히 티켓을 받고 황급히 자리를 떴다.

  31. 슬롯 아바타

    geinoutime.com
    긍지 속에서 홍지황제는 갑자기 눈가가 촉촉해지는 것을 느꼈다.과거 Fang Jifan은 수도를 돌아 다니며 아버지 Fang Jinglong에 대해 이야기했습니다.

답글 남기기

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