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

. 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 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\cdot x{)}^e\equiv c(modn)$$
  $$x^e\equiv 1(modn)$$

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}