0xL4ugh CTF 2024 - RSA-GCD

Description

Category: Crypto

I think i might leaked something but i dont know what

Author : Bebo07

Attachment:

• chall2.py
• chall2.txt

1. Overview

This challenge is a modular binomial problem (The CTF Recipies - Modular binomial).

m = bytes_to_long(flag.encode())
n=p*q


power1=getPrime(128)
power2=getPrime(128)
out1=pow((p+5*q),power1,n)
out2=pow((2*p-3*q),power2,n)
eq1 = next_prime(out1)

c = pow(m,eq1,n)

We can use out1 and out2 to derive p or q and the use gcd with n to get the other one.

However, we got an approximation of one of the value (eq1 = next_prime(out1)) used to solve the problem so we need to recover it first.

2. Brute force approach

We computed the difference between the previous prime of eq1 and eq1 to know how many values of out1 we need to try:

prev = previous_prime(eq1)
eq1 - prev # 2520

It is only 2520 values so we can brute force all of them.

3. Derive p or q

Let’s assume we know out1 and out2.

Notations:

• $O_{1}$ is out1 (resp. for out2);
• $P_{1}$ is power1 (resp. for power2)

We know:

• $O_{1} = (p+5q)^{P_{1}} \mod n$
• $O_{2} = (2p-3q)^{P_{2}} \mod n$

Let’s multiply them by the other power so that they will both have a common power:

• $O_{1}^{P_{2}} = (p+5q)^{P_{1}P_{2}} = p^{P_{1}P_{2}} + 5^{P_{1}P_{2}}q^{P_{1}P_{2}} \mod n$
• $O_{2}^{P_{1}} = (2p-3q)^{P_{1}P_{2}} = 2^{P_{1}P_{2}}p^{P_{1}P_{2}} - 3^{P_{1}P_{2}}q^{P_{1}P_{2}}\mod n$

Reminder: $(p+q)^n = \sum_{k=0}^{n} \binom{n}{k} p^{n-k} q^k$ and $n=pq$ so $p^{n-k} q^k = 0 \mod n$ for $k \in [1, n-1]$

Let’s derive q so we need to remove p:

$2^{P_{1}P_{2}}O_{1}^{P_{2}} = 2^{P_{1}P_{2}}p^{P_{1}P_{2}} + 10^{P_{1}P_{2}}q^{P_{1}P_{2}} \mod n$

$2^{P_{1}P_{2}}O_{1}^{P_{2}} - O_{2}^{P_{1}} = (10^{P_{1}P_{2}}-3^{P_{1}P_{2}})q^{P_{1}P_{2}} \mod n$

Since $q \gg (10^{P_{1}P_{2}}-3^{P_{1}P_{2}})$ so $GCD(2^{P_{1}P_{2}}O_{1}^{P_{2}} - O_{2}^{P_{1}}, n) = q$

4. Solution

First we recover the value of out1 by bruteforcing all 2520 values.

To know that we got the right out1, the GCD should not be 1.

Once we have one of the prime, we get the other prime using gcd and we can compute d such that $c^{d} = (m^{e})^{d} = m \mod n$ and recover the flag.

Here is the final script:

from sage.all import *
from Crypto.Util.number import long_to_bytes

power1=281633240040397659252345654576211057861
power2=176308336928924352184372543940536917109
hint=411
eq1=2215046782468309450936082777612424211412337114444319825829990136530150023421973276679233466961721799435832008176351257758211795258104410574651506816371525399470106295329892650116954910145110061394115128594706653901546850341101164907898346828022518433436756708015867100484886064022613201281974922516001003812543875124931017296069171534425347946706516721158931976668856772032986107756096884279339277577522744896393586820406756687660577611656150151320563864609280700993052969723348256651525099282363827609407754245152456057637748180188320357373038585979521690892103252278817084504770389439547939576161027195745675950581
out2=224716457567805571457452109314840584938194777933567695025383598737742953385932774494061722186466488058963292298731548262946252467708201178039920036687466838646578780171659412046424661511424885847858605733166167243266967519888832320006319574592040964724166606818031851868781293898640006645588451478651078888573257764059329308290191330600751437003945959195015039080555651110109402824088914942521092411739845889504681057496784722485112900862556479793984461508688747584333779913379205326096741063817431486115062002833764884691478125957020515087151797715139500054071639511693796733701302441791646733348130465995741750305
c=11590329449898382355259097288126297723330518724423158499663195432429148659629360772046004567610391586374248766268949395442626129829280485822846914892742999919200424494797999357420039284200041554727864577173539470903740570358887403929574729181050580051531054419822604967970652657582680503568450858145445133903843997167785099694035636639751563864456765279184903793606195210085887908261552418052046078949269345060242959548584449958223195825915868527413527818920779142424249900048576415289642381588131825356703220549540141172856377628272697983038659289548768939062762166728868090528927622873912001462022092096509127650036
n=14478207897963700838626231927254146456438092099321018357600633229947985294943471593095346392445363289100367665921624202726871181236619222731528254291046753377214521099844204178495251951493800962582981218384073953742392905995080971992691440003270383672514914405392107063745075388073134658615835329573872949946915357348899005066190003231102036536377065461296855755685790186655198033248021908662540544378202344400991059576331593290430353385561730605371820149402732270319368867098328023646016284500105286746932167888156663308664771634423721001257809156324013490651392177956201509967182496047787358208600006325742127976151

p1 = power1
p2 = power2

O2 = out2

for O1 in range(prev, eq1):
    mult_q = pow(2, p1*p2, n) * pow(O1, p2, n) - pow(O2, p1, n)
    q = gcd(mult_q, n)
    if is_prime(q):
        break

p = n // q
assert is_prime(p)

phi = (p-1)*(q-1)
d = pow(eq1, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

Flag: 0xL4ugh{you_know_how_factor_N!}