Another RSA Challenge • Gafna Blog

Another RSA Challenge#

RSA di gitu gituin challenge

DIberi 2 file yaitu file skrip python dan outputnya, isinya kek gini:

from Crypto.Util.number import *
from Crypto.Random import random
import os

BITS = 512
rand = random.randint(2,12)
primes = [getPrime(BITS) for _ in range(rand)]
e1 = 0x10001
n1 = phi = 1
for i in range(rand):
 n1 *= primes[i]
 phi *= primes[i]-1

p,q = getPrime(BITS), getPrime(BITS)
n2 = p*q
e2 = 3
phi2 = (p-1)*(q-1)
d2 = inverse(e2,phi2)

FLAG = b"Meta4Sec{REDACTED}"
while len(FLAG)*8 + 128 < (n1*n2).bit_length() :
 FLAG += os.urandom(16)
c = pow(bytes_to_long(FLAG), e1, n1*n2)

print("n1 = ", n1)
print("n2 = ", n2)
print("hehe1 = ", pow(d2,e2,n2))
print("hehe2 = ", pow(phi2,e2,n2))
print("leaked_phi = ", phi&((1<<(BITS*(rand-1)))-1))
print("ct = ", c)

python

alt text

Pertama, kita lihat dulu skrip generatornya. Intinya, skrip ini melakukan beberapa hal:

Bikin sebuah modulus n1 yang merupakan hasil perkalian dari rand (antara 2-12) bilangan prima 512-bit.
Bikin modulus RSA biasa, n2 = p\*q.
Flag-nya dienkripsi pake e1 = 0x10001 dengan modulus gabungan N = n1 - n2.
Kita dikasih beberapa leak atau bocoran: n1, n2, leaked_phi (beberapa bit terakhir dari phi(n1)), ct (ciphertext), dan dua nilai aneh hehe1 & hehe2.

Untuk dekripsi, kita butuh private key d1, yang artinya kita butuh phi(N). Karena n1 dan n2 koprima, maka phi(N) = phi(n1) \* phi(n2). Jadi, misi kita dibagi dua: cari phi(n1) dan cari phi(n2).

Langkah 1: Membongkar n2

Ini bagian yang bikin kita muter-muter. Leak yang kita punya untuk n2 adalah:

hehe1 = d2^3 mod n2
hehe2 = phi2^3 mod n2

Hubungan antara d2 dan phi2 adalah 3 _ d2 = k _ phi2 + 1 untuk suatu integer k. Karena d2 < phi2, nilai k ini pasti kecil, kemungkinannya cuma 1 atau

Kita bisa bikin dua polinomial yang punya akar yang sama, yaitu X = p+q-1.

Dari hehe2: kita tahu phi2^3 ≡ hehe2 (mod n2). Karena phi2 = n2 - X, ini bisa disederhanakan jadi X^3 + hehe2 ≡ 0 (mod n2). Jadilah polinomial pertama: P1(x) = x^3 + hehe2
Dari hehe1: kita tahu d2^3 ≡ hehe1 (mod n2). Setelah dijabarkan, ini bisa jadi polinomial kedua dalam X: P2(x) = (-2x+1)^3 - 27\*hehe1. (Kita pakai k=2 karena secara matematis ini yang paling valid).

Kita bisa pakai metode GCD Polinomial buat nemuin akarnya. Dengan sedikit manipulasi aljabar (mengeliminasi suku pangkat tertinggi), kita bisa dapet persamaan linear buat X. Dari situ, nilai X langsung ketemu.

Setelah X dapet, kita bisa:

Hitung s = X+1.
Faktorkan n2 dengan mencari akar dari y^2 - s\*y + n2 = 0.
Dapet p dan q, lalu hitung phi2 = (p-1)\*(q-1).

Langkah 2: Mencari phi(n1)

Kita punya leaked_phi, yaitu bit-bit terakhir dari phi(n1). Bit-bit awalnya hilang.

Cari rand: rand ini jumlah bilangan prima yang menyusun n1. Cara paling bener buat nebaknya adalah rand = round(n1.bit_length() / 512). Di kasus kita (setelah dapet data yang bener), rand jadi 11. 9.
Tebak Bit yang Hilang: Kita bisa aproksimasi nilai phi(n1) itu deket banget sama n1. Selisihnya, n1 - phi(n1), kira-kira sebesar rand dikali 2^(BITS\*(rand-1)). Dari sini, kita bisa tebak bit-bit awal phi(n1) yang hilang dengan rumus phi_H ≈ n1_H - rand. 10.
Brute-force: Karena ini cuma tebakan, kita tinggal looping di sekitar nilai tebakan itu. Kita coba beberapa nilai i di range(-250, 250), gabungkan dengan leaked_phi, dan coba dekripsi. Salah satunya pasti bener

Langkah 3: Dekripsi Final

Setelah phi1 (dari langkah 2) dan phi2 (dari langkah 1) ketemu

Hitung totient total: PHI_total = phi1 \* phi2.
Hitung private key: d1 = inverse(e1, PHI_total).
Dekripsi ciphertext: m = pow(ct, d1, n1 \* n2).
Ubah m jadi bytes: flag_bytes = long_to_bytes(m).

Berikut untuk skrip solper nya

#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import long_to_bytes, inverse
import math

n1 =  127985434146947451063248594741160909504281011987949286339684559944197121508645705649599593580816392974880171330761420563033968956370211879158549919014390342729154451049198161141684083236066497811023298891520708441351269439981216637053715595159079601509804596092109659829420042655852466551372546917361635326394811009845357620517978084635552707460844901185197019516328760711447771053552735843157996606770003574959357145002412295566321593309013586373301199992000059551237618206629731821240214715588712309719565247229086746832764733115498227943867470201474530854417348230192644708670671338528114635530213569715807817805576553600843353962895983652152952803721482583768477194499754970205018043669098256390061539071635613881645374271439769023375170450102406703864857609046216952959528858659167048974462636611399826329493800788877989735130918927343775037082749312344479851851897480720653015710024116138911273240928246226402537322843561690968797781978932813306169248423675007345283545067121136498628282575969268656187219717266331077610137492448898676731957142641016565504114974106449914409548492890962723028590361363140772946356245247537661582691341912744342405484804893851035580604811707299062438820093278415427468209274671086041444052628607258255078484626563022215886880027846538055273820998285846836448404612946447427209136909389850514284126613718453145817778735560354789110172401876959037319676585356167245628593462734376789302351325384673716759391335595198909838368026774946973264840093087071733882132005201143255120627333910863572257910651999338943158399771912892790523206864224333719807137158623987454991198450398788975032299932419512609077770625450038206424834762319788251383380210159352691544143
n2 =  94689972560993685335293323828554218730653801150611500909335968283537276179702747416383846512181737740786598668403758736863055980516297818532692013970772087301915046854906641949494189623309335598857633596293021017826970207458081868168758534123106188016624692649433920748148407960751398060860863674040147811387
hehe1 =  15569725899716908003809876446848778308038172145512977852892392878018746874732192633587188961231626012060032054927937477545766620152589181920410631578923754356832349858426366483949079006859871571271787583691980529404094187939763721760724539511519052369101915659217495672427375630825386451646732889365906347813
hehe2 =  5156240068018457687272037281769265479816085975461903960705418202920658447864962641915967647411608435886807441953894600871465259335624366991927407643200605402837684571204842075108416218716505773932220816028262075218204104020074895971240422779469583661403806983822810727278513078075085635825421831896494432184
leaked_phi =  71441146138303451723476975699526367265213715191138533669241232752796120745191092420195649373217251362748489472487268884890245036160075719592122306586573975862092846104992369022055052319608973966931912140757218089207511058275250441568780059700133930988844446614836314574509002758886623994493580961577924480322459605969788116843366238650647608837321505274150354064807518530282474631867111740592386333250964261865738231355701088553685211028494455225563004963379659646449366424736757274326908942390567087355132373763477624790994407055017246919996949350341786647793402316072288499652708451241189786567083635854182188655072241457505245707229896025065212770023029163602867283362663943417420813977688152231011786865662612118695208298659631047197754442094536144918447908510140333224150999873007313774685509000528186185617762410967394219944764594277239964325001049600844517811199423581423242734658718684362680759138883447654269741635580750617674286835382503596201953753640992189932059028158911063364506082026225062882610560890885791856670129280746912662838854363421387792597265649302210508845289715133937791017140947070612500527592927175110826158494851529644839375422479998420737949421333809302013947271563224242135189503415597018618296665460663924684516614889049028213500333419958262401387681561862150323144748692467084915703148615694495324105335746763459507706376951884892049948029527989134621422227806302554614158861667092547274163014770157675244715895042213714368939945274334381348077049228733181706699178756256116847417634092268206766075063042048
ct =  438931599736732791855400488003058483770853359695003054393283117194819465971098079488280722162796084850056548076432213063576391851362982160623209352111616113847731064035098795612903956551680487687146461825279135210977885552566517394718842000707432321246199250634082350847794163641746891232755415682659448934791632542406103477303448006139631132604761268504750892820115642891482372399876337582954792432744459011144792908450140994476125184491046868813030438369496228018814458189649804473903287919069379482120778230016682801383143198106248765617753215187276953613402217082817068199830665714189409609041739020531918622397699758139824639337524561098745075549180306602286879731634864110296135528799764608680762186190189355966783671023895337444618789165906494877397839980493695387505388739280213051182500353053921353008483717358632151577914939058507262047063053289025719524583521338087835985948987250794487970929703386545261613109739375037156915412495583055532146188339237480115898420679191316615332997372669591662860403587235259519490751520746705113555626729041125254273545284339678440484546020120242711543464183571861090377599003911578042219337482560399348027549778427917856513353735073850826423680348772446512593269761981470844379504307984168536875448537375408171334303937589568742447880200140887547189816667417956299557337501045286651927425406660692238982221942349905613356070431543763739608254189160497959285621565210106319708149277675308420400648525487449184441885154332883029622695618182870609055035445224422224513208364373298137287387634954289956978899361972551388228561879298981586900605737643240802205936341952772927176749986533046628773150353153861715442396472747147902572835886869764222909711789450684524626063596616616254055085278337398611742601061786784336329274365207290842076213013661640106331007454555883495379439995794361068354465357107226557397280524522644728919707287501025004272480678056516313090951669457205879829671106838102388654734802022683646243374284593813668929923127880102277683663

# Constants
BITS = 512
e1 = 0x10001
e2 = 3
k = 2


def solve_n2():
    print("[*] Recovering phi(n2) using Polynomial GCD method...")

    A_ = 3 * k**2
    B_ = -3 * k
    C_ = (1 + k**3 * hehe2 - 27 * hehe1) % n2

    L1 = (B_**2 - A_ * C_) % n2
    L2 = (B_ * C_ + A_**2 * hehe2) % n2

    try:
        inv_L1 = inverse(L1, n2)
        X = (-L2 * inv_L1) % n2
        print("[+] Found potential root X = p+q-1.")
    except Exception as e:
        print(f"[!] Could not solve for X. Error: {e}")
        return None

    s = X + 1
    delta_sq = s**2 - 4*n2

    if delta_sq < 0:
        print("[!] Error: s^2 - 4*n2 is negative. Cannot factor n2.")
        return None

    root, rem = gmpy2.isqrt_rem(delta_sq)
    if rem != 0:
        print("[!] Error: s^2 - 4*n2 is not a perfect square. Cannot factor n2.")
        return None

    p = (s + root) // 2
    q = (s - root) // 2

    if p * q != n2:
        print("[!] Error: Factoring failed. p*q does not equal n2.")
        return None

    print("[+] Successfully factored n2.")
    phi2 = (p-1)*(q-1)
    return phi2

def solve_n1(phi2):
    """Recovers phi(n1) and decrypts the flag."""
    if phi2 is None:
        return

    print("[*] Recovering phi(n1)...")
    rand = round(n1.bit_length() / BITS)
    L = BITS * (rand - 1)
    n1_H = n1 >> L

    phi_H_guess = n1_H - rand
    print(f"    - rand = {rand}. Leaked bits = {L}.")
    print(f"    - Searching for high bits of phi(n1) around: {phi_H_guess}")

    print("[*] Searching for the correct phi(n1) and decrypting...")
    N = n1 * n2
    for i in range(-250, 250):
        phi_H_candidate = phi_H_guess + i
        phi1_candidate = (phi_H_candidate << L) + leaked_phi

        if gmpy2.gcd(e1, phi1_candidate) != 1:
            continue

        try:
            PHI_total = phi1_candidate * phi2
            d1 = inverse(e1, PHI_total)
            m = pow(ct, d1, N)
            flag = long_to_bytes(m)

            if flag.startswith(b"Meta4Sec{"):
                print("\n[+] Success! Decrypted Flag Found: ✅")
                print(flag)
                return
        except (ValueError, ZeroDivisionError):
            continue

    print("\n[!] Failed to find the flag in the search range.")

if __name__ == '__main__':
    phi2 = solve_n2()
    solve_n1(phi2)

Flag: Meta4Sec{B1M1ll4H_G4_D1ON3SH0T_LLM}