[Hacktoday Qual 2022] – Pushin P

Diberikan sebuah kodingan enkripsi rsa seperti berikut:

from Crypto.Util.number import *

def push_p(p):
    p += 0xD1CC
    if not p % 0x2:
        p += 0x1
    while not isPrime(p):
        p += 0x2
    return p


def get_factors(nbit):
    p = getPrime(nbit)
    q = push_p(pow(push_p(p), 0x2))
    return (p, q)


def get_modulus(f=()):
    n = 0x1
    for i in f:
        n *= i
    return int(n)


def get_msg(txt):
    with open(txt, “rb”) as f:
        m = f.read().strip()
        m = bytes_to_long(m)
        f.close()
        return m


def main():
    factors = get_factors(0x200)
    n = get_modulus(factors)
    m = get_msg(“flag.txt”)
    e = 0x10001
    c = pow(m, e, n)
    with open(“output.txt”, “w”) as f:
        f.write(f”{n = }\n”)
        f.write(f”{e = }\n”)
        f.write(f”{c = }\n”)
        f.close()


if __name__ == “__main__”:
    main()

Dapat dilihat bahwa p didapat dari getPrime sejumlah bit dan q didapat dari p yang diberlakukan fungsi bernama push_p. Push_p ini merupakan fungsi untuk menambahkan p sejumlah nilai, lalu menambahkan dengan 2 hingga hasilnya menjadi bilangan prima. q didapat dari push_p(p), hasilnya dikuadratkan lalu dilakukan push_p lagi.

N didapat dari p dikali q. Namun apabila dikira2, q yang secara tidak langsung merupakan hasil pengkuadratan dari p akan dikali dengan p, sehingga dapat disimpulkan gambaran kasarnya adalah n = p * p * p. Maka dari itu, kita bisa mengakar pangkat 3 nilai n untuk mendapatkan nilai kira-kira dari p.

Kami melakukan beberapa kali percobaan untuk mengetahui selisih hasil p asli (yang kami tentukan sendiri di local) dengan p kira-kira. Beberapa samplenya adalah berikut:

Dari percobaan tersebut kami selalu mendapatkan selisihnya di kisaran 35000 – 40000 (dimana p kira-kira yang lebih besar), jadi langkah kami selanjutnya adalah membruteforce kisaran tersebut untuk menguranginya dengan p kira-kira, menghitung q kira-kira, lalu memastikan apakah n yang diberi di soal sama dengan p kira-kira * q kira-kira.

Satu poin lagi, fungsi push_p(p) ini ternyata sedikit memakan waktu dalam menjalankannya, sehingga kami memutuskan untuk menggunakan gmpy2.next_prime() sebagai penggantinya karena prinsipnya yang sama dan waktunya jauh lebih cepat. Sehingga kodingannya kami buat sebagai berikut:

from Crypto.Util.number import *
import gmpy2

def push_p(p):
    p += 53708
    if not p % 0x2:#kalo p genap
        p += 0x1
    while not isPrime(p):
        p += 0x2
    return p


def get_factors(nbit):
    p = getPrime(nbit)
    print(‘pawals’, p)
    q = push_p(pow(push_p(p), 0x2))
    return (p, q)

def checker(proot, n):
    for i in range(35000, 40000):
        p = proot – i
        q = gmpy2.next_prime(pow(gmpy2.next_prime(p + 53708), 0x2) + 53708)
        print(i)
        if p * q == n:
            print(‘hasil’)
            return p, q


def main():
    # p, q = get_factors(512)
    # n = p*q
    # m = bytes_to_long(b’kodokgeming’)
    # e = 0x10001
    # c = pow(m, e, n)
    # print(n)
    n = 747711518232059926779344254390010243629733297684885700778285901048788955327920843242655544701523253975281756005172301849128740335820457086109874171295398385257710215241680151599266384225076936101016766742490821208993985818705524631574245931795321403786638801104999497599395163165661490373585721776857159039498982511558301239332130508072450257338598887946126052347854216636551259802575935316132527102322736187223651361495858981502790025584089304581999087255711313
    e = 65537
    c = 714407286479098015936046742974575388325418569576839823592060647609931179900601179657727921821368372533664586449734643984375810825936459250351538008350882640166304940090121664856105773254834913420639882528057899366389338857943940098563814637601855208170662422704348207380115388466365160553218057944017130365534705860894803131298989231366911350447414408206984947152822249184449420967406668189624970648445604404245613758378711152852057479686514802365361310462845715

    hasil, _ = gmpy2.iroot(n, 3)
    # print(‘pkira2’, hasil)
    # print(‘selisih’, hasil – p)

    pfind, qfind = checker(hasil, n)
    phi = (pfind – 1)* (qfind-1)
    d = inverse(e, phi)
    print(long_to_bytes(pow(c, d, n)))



if __name__ == “__main__”:
    main()

Output:

Flag = hacktoday{ppp_pppp_ppppp_78934345}

Leave a Reply

Your email address will not be published. Required fields are marked *