Trong các thử thách về mật mã học (Cryptography) tại các cuộc thi CTF, dạng bài tập sử dụng cùng một modulo $n$ với các số mũ công khai $e$ khác nhau là một kịch bản kinh điển. Đây là lỗ hổng bảo mật được gọi là RSA Common Modulus Attack. Dưới đây là phân tích chi tiết về kỹ thuật này thông qua bài toán thực tế.

Phân tích mã nguồn bài toán

Giả sử chúng ta có một kịch bản thực thi RSA như sau:

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import os

def create_params():
    prime_p = getPrime(1024)
    prime_q = getPrime(1024)
    modulus_n = prime_p * prime_q
    exponent = getPrime(32)
    return modulus_n, exponent

def check_format(cipher_int):
    # Kiểm tra định dạng bản rõ sau khi giải mã
    return long_to_bytes(cipher_int).startswith(b"rose")

def encrypt_process(message_bytes):
    n, e1 = create_params()
    # Mã hóa lần 1
    c1 = pow(message_bytes, e1, n)
    
    # Tìm kiếm một số mũ e2 khác để đảm bảo tính chất bài toán
    e2 = getPrime(32)
    c2 = pow(message_bytes, e2, n)
    
    print(f"n = {hex(n)}")
    print(f"e1 = {hex(e1)}")
    print(f"c1 = {hex(c1)}")
    print(f"e2 = {hex(e2)}")
    print(f"c2 = {hex(c2)}")

# Bản tin bao gồm flag và 64 byte ngẫu nhiên
secret_msg = bytes_to_long(flag + os.urandom(64))
encrypt_process(secret_msg)

Đặc điểm quan trọng ở đây là biến secret_msg không thay đổi trong cả hai lần mã hóa, và giá trị modulo n được giữ nguyên. Chúng ta có hệ phương trình sau:

• $c_1 \equiv m^{e_1} \pmod n$
• $c_2 \equiv m^{e_2} \pmod n$

Nguyên lý tấn công Common Modulus

Nếu $\gcd(e_1, e_2) = 1$, theo định lý Bezout, luôn tồn tại hai số nguyên $r$ và $s$ sao cho:

$e_1 \cdot r + e_2 \cdot s = 1$

Khi đó, ta có thể khôi phục bản rõ $m$ bằng cách tính:

$(c_1^r \cdot c_2^s) \equiv (m^{e_1})^r \cdot (m^{e_2})^s \equiv m^{e_1 r + e_2 s} \equiv m^1 \pmod n$

Lưu ý rằng trong thực tế, một trong hai giá trị $r$ hoặc $s$ sẽ là số âm. Do đó, ta cần tính nghịch đảo modulo để xử lý lũy thừa âm trong trường số nguyên modulo $n$.

Triển khai mã khai thác

Sử dụng thư viện gmpy2 để xử lý các số nguyên lớn và thuật toán Euclid mở rộng để tìm các hệ số $r, s$.

import gmpy2
from Crypto.Util.number import long_to_bytes

def extended_gcd(a, b):
    if a == 0:
        return 0, 1, b
    x1, y1, gcd = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return x, y, gcd

def solve_common_modulus(n, e1, c1, e2, c2):
    # Tìm r, s sao cho e1*r + e2*s = gcd(e1, e2)
    r, s, g = extended_gcd(e1, e2)
    
    if g != 1:
        raise ValueError("GCD của e1 và e2 phải bằng 1")

    # Xử lý lũy thừa âm
    if r < 0:
        c1 = gmpy2.invert(c1, n)
        r = -r
    if s < 0:
        c2 = gmpy2.invert(c2, n)
        s = -s
        
    # Tính m = (c1^r * c2^s) mod n
    part1 = gmpy2.powmod(c1, r, n)
    part2 = gmpy2.powmod(c2, s, n)
    m = (part1 * part2) % n
    return m

# Dữ liệu thu được từ log
n_val = 0xa1d4d3...
e1_val = 0xf4c1158f
c1_val = 0x2f6546...
e2_val = 0xf493f7d1
c2_val = 0xd32dfa...

result_m = solve_common_modulus(n_val, e1_val, c1_val, e2_val, c2_val)
full_payload = long_to_bytes(result_m)

# Loại bỏ 64 byte ngẫu nhiên ở cuối để lấy flag
print(full_payload[:-64].decode())

Kỹ thuật này cho thấy việc tái sử dụng modulo $n$ trong RSA là cực kỳ nguy hiểm nếu các số mũ công khai không được quản lý chặt chẽ, cho phép kẻ tấn công khôi phục hoàn toàn nội dung mà không cần phân tích thừa số nguyên tố của $n$.