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}