PicoCTFPicoCTF2026
ClusterRSA
Writeups Reverse Engineering PicoCTF Binary Instrumentation 1 & 2
Overview
A message has been encrypted using RSA, but this time something feels... more crowded than usual. Can you decrypt it?
n = 8749002899132047699790752490331099938058737706735201354674975134719667510377522805717156720453193651
e = 65537
ct = 3834152707673200098217711830451812292969443248147329830146346725533249396845301509591469898509446306Solving
karena di soal RSA ini kita tidak diberi sebuah prime makan kita perlu memfaktorisasikan n untuk mencari prime
❯ yafu "factor(874900289913204769979075249033109993805873770673520135467497513471966751037
7522805717156720453193651)"
SIQS elapsed time = 59.4226 seconds.
Total factoring time = 81.1144 seconds
***factors found***
P25 = 9671406556917033398439721
P25 = 9671406556917033398314601
P25 = 9671406556917033397931773
P25 = 9671406556917033398454847
ans = 1 menggunakan yafu dapat ditemukan 4 bilangan prima dari faktorisasi n tadi, normalnya RSA hanya memiliki 2 bilangan prima, sehingga ini tidak bisa di solve dengan cara biasa, kita perlu membuat solver:
from Crypto.Util.number import *
n = 8749002899132047699790752490331099938058737706735201354674975134719667510377522805717>
e = 65537
ct = 383415270767320009821771183045181229296944324814732983014634672553324939684530150959>
p1 = 9671406556917033397931773
p2 = 9671406556917033398314601
p3 = 9671406556917033398439721
p4 = 9671406556917033398454847
phi = (p1-1)*(p2-1)*(p3-1)*(p4-1)
d = inverse(e, phi)
m = pow(ct, d, n)
print(long_to_bytes(m))setelah menjalankan script tersebut, kita akan dapat menemukan flagnya
❯ python3 rsa.py
b'picoCTF{mul71_rsa_1580d395}'