# ISITDTU CTF 2023 - babyRSA

Lời nói đầu: đây là một giải CTF chất lượng vì mình thấy đề mảng crypto rất hay, tuy vậy mình vẫn chỉ giải được 1 bài crypto trong suốt thời gian cuộc thi diễn ra :sweat_smile:. Mong trong tương lai mình sẽ tìm ra cách giải của các bài còn lại ahihi.

Ok bây giờ sẽ đến phần WU của bài babyRSA.

# babyRSA

Đề bài cho ta file sau:

from Crypto.Util.number import bytes_to_long
from FLAG import flag

p1 = 401327687854144602104262478345650053155149834850813791388612732559616436344229998525081674131271
p2 = 500233813775302774885494989064149819654733094475237733501199023993441312997760959607567274704359
p3 = 969568679903672924738597736880903133415133378800072135853678043226600595571519034043189730269981
e1 = 398119
e2 = 283609
e3 = 272383

c = bytes_to_long(flag)
c = pow(c, e1, p1)
c = pow(c, e2, p2)
c = pow(c, e3, p3)

print(f"{c = }")
# c = 104229015434394780017196823454597012062804737684103834919430099907512793339407667578022877402970

Đề bài này có ý tưởng khá giống với bài [Broken RSA](https://cryptohack.org/) trên Cryptohack nhưng khác biệt là được thực hiện nhiều lần, với N lần lượt là p1, p2, p3 (đều là số nguyên tố) nên phi1, phi2, phi3 lần lượt là p1-1, p2-1, p3-1. Nhưng vì GCD(e1,phi1), GCD(e2,phi2) và GCD(e3,phi3) đều khác 1, nên ta sẽ có rất nhiều plaintext ứng với một ciphertext.

Chi tiết hơn thì như cách giải thích như sau:
* n là số nguyên tố
* phi(n) và e không có ước chung bằng 1 => nhiều plaintext khác nhau từ 1 ciphertext
* Ta tìm tất cả các $x$ thoả (bằng hàm roots_of_unity()):
$$(m⋅x)^e ≡ c \ (mod \ n)$$$$x^e ≡ 1 \ (mod \ n)$$

Nhưng việc tìm ra được c1 và c2 khá là dễ vì chỉ có một c2 làm thoả điều kiện xét `pow(c1,e2,p2) == c2` (theo mình tìm được), và từ đó tính c1 và tương tự tìm ra plaintext bắt đầu bằng "ISITDTU".

Trong hàm roots_of_unity() thì số rounds (số lượng cần tìm các số $x$ thoả như ở trên) mình sẽ lấy bằng số $e$ của từng $n$ để có tỉ lệ tìm được $flag$ cao nhất có thể.

Đây là code giải:

from Crypto.Util.number import long_to_bytes
import Crypto.Util.number as cun
from tqdm import tqdm

p1 = 401327687854144602104262478345650053155149834850813791388612732559616436344229998525081674131271
p2 = 500233813775302774885494989064149819654733094475237733501199023993441312997760959607567274704359
p3 = 969568679903672924738597736880903133415133378800072135853678043226600595571519034043189730269981
e1 = 398119
e2 = 283609
e3 = 272383

def roots_of_unity(e, phi, n, rounds=2000):
    # Divide common factors of `phi` and `e` until they're coprime.
    phi_coprime = phi
    while cun.GCD(phi_coprime, e) != 1:
        phi_coprime //= cun.GCD(phi_coprime, e)

    # Don't know how many roots of unity there are, so just try and collect a bunch
    roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))

    assert all(pow(root, e, n) == 1 for root in roots)
    return roots, phi_coprime

c = 104229015434394780017196823454597012062804737684103834919430099907512793339407667578022877402970
phi3 = p3-1
phi2 = p2-1
phi1 = p1-1

roots3, phi_coprime3 = roots_of_unity(e3, phi3, p3,e3)
print('root3 ok')
roots2, phi_coprime2 = roots_of_unity(e2, phi2, p2,e2)
print('root2 ok')
roots1, phi_coprime1 = roots_of_unity(e1, phi1, p1,e1)
print('root1 ok')

d3 = pow(e3, -1, phi_coprime3)
d2 = pow(e2, -1, phi_coprime2)
d1 = pow(e1, -1, phi_coprime1)
c2 = pow(c, d3, p3)
assert pow(c2,e3,p3) == c

c2 = [((c2 * root) % p3) for root in roots3 if pow(((c2 * root) % p3), e3, p3) == c]

for c2_test in tqdm(c2):
    c1_test = pow(c2_test, d2, p2)
    if pow(c1_test,e2,p2) == c2_test:
        print(c2_test)
        c1_list = [(c1_test * root) % p2 for root in roots2]

for c1 in tqdm(c1_list):
    m_test = pow(c1, d1, p1)
    if pow(m_test,e1,p1) == c1:
        for root in roots1:
            m = (m_test * root) % p1 
            if b'ISITDTU' in long_to_bytes(m):
                print(long_to_bytes(m))
                exit()
# flag: ISITDTU{s0_m4ny_m0dul4r_r00t5}

# welcome

Sử dụng Cipher Identifier ta có được kết quả là ASCII85 Encoding cipher:

Sau đó ta tiếp tục decrypt thì sẽ có được flag:
Flag: ISITDTU{wellcOme_t0_ISitdtu_ctf}