VI. Common module attack

1. Cơ sở lý thuyết

Giả thiết rằng một thông điệp $m$ được thực hiện mã hóa RSA đồng thời với số $n$ dùng chung, các số $e$ và $d$ riêng biệt. Trong trường hợp đó, nếu hai số $e_1$, $e_2$ thỏa mãn điều kiện nguyên tố cùng nhau, hay $GCD(e_1, e_2)=1$, thì chúng ta hoàn toàn có thể sử dụng hình thức tấn công Common module attack nhằm tìm ra thông điệp gốc khi biết bản mã.

Bài toán có thể phát biểu như sau: Dữ liệu đã biết bao gồm:

Số n dùng chung
c1, c2 là hai bản mã đã biết
e1, e2 đã biết và GCD(e1, e2)=1

Thật vậy, chúng ta cùng phân tích từng bước kẻ tấn công tìm ra thông điệp qua các yếu tố đã biết trên. Trước hết, lưu ý rằng nếu có $GCD(e_1, e_2)=1$, thì luôn có thể tìm được hai số nguyên $s_1$, $s_2$ sao cho $e_1\times s_1 + e_2\times s_2 = 1$ (Bạn đọc có thể xem lại mục $6$ phần $III$). Lại có:

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

Sử dụng $e_1\times s_1 + e_2\times s_2 = 1$ ta có:

$$c_1^{s_1}\times c_2^{s_2} = (m^{e_1})^{s_1}\times (m^{e_2})^{s_2} \pmod {n}\\ = m^{e_1\times {s_1}}\times m^{e_2\times {s_2}} \pmod {n}\\ = m^{e_1\times {s_1}+e_2\times {s_2}} \pmod {n}\\ = m \pmod {n}\\$$

Bởi vì $m<n$ nên cuối cùng ta nhận được:

$$c_1^{s_1}\times c_2^{s_2} \pmod {n} = m \pmod {n} = m$$

2. Challenge CTF

Một bài toán RSA cho biết các thành phần sau:

(n1, e1) = (6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249, 773)

(n2, e2) = (6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249, 839)

c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349

c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

Dễ dàng nhận thấy bài toán dùng chung số $n$, hai số $e_1$, $e_2$ nguyên tố cùng nhau, bởi vậy có thể tấn công bằng Common module attack. Ý tưởng lúc này là tìm ra hai số $s_1$, $s_2$ thỏa mãn $e_1\times s_1 + e_2\times s_2 = 1$ là có thể dễ dàng tìm ra thông điệp $m$. Xin dành cho bạn đọc viết tiếp chương trình giải mã.

VII. Small public key index attack

1. Ví dụ e = 3

1.1. Cở sở lý thuyết

Trong trường hợp số $e$ được chọn nhỏ với $e=3$, tức là có:

$$c = m^{3} \pmod {n}\\$$

Có nghĩa là tồn tại số $k$ sao cho $c = k\times n + m^3$, hay $m = \sqrt[3]{c - k\times n}$. Thực hiện thử từng trường hợp của số $k$, khi nhận được kết quả $\sqrt[3]{c - k\times n}$ là một số nguyên, tức là đã tìm ra $m$. Để tối ưu hóa, chúng ta sẽ thử các giá trị của $k$ theo cả hai phía bắt đầu từ số $0$ (cả trường hợp số nguyên dương và số nguyên âm), tức là chỉ cần $c - k\times n$ hoặc $c + k\times n$ là một lập phương đúng thì bài toán đã được giải quyết. Sử dụng ý tưởng này chúng ta cũng có thể giải quyết một số bài toán với số $e$ nhỏ bằng cách khai căn bậc $e$.

Chúng ta có thể sử dụng hàm math.pow trong module math để kiểm tra một số có phải số lập phương hay không:

import math

number = 8
cube_root = math.pow(number, 1/3)
print("Căn bậc ba của", number, "là:", cube_root)

Tuy nhiên hàm math.pow có nhiều hạn chế khi số cần kiểm tra quá lớn. Thay vào đó, chúng ta nên sử dụng hàm gmpy2.iroot trong module gmpy2 sẽ cho hiệu quả tốt hơn:

import gmpy2

x = gmpy2.mpz(64)  # Số nguyên 64
n = 3  # Bậc của căn
cube_root, exact = gmpy2.iroot(x, n)

if exact:
    print(f"Căn bậc {n} của {x} là {cube_root}")
else:
    print(f"{x} không có căn bậc {n} nguyên.")

1.2. Challenge CTF

Đề bài cung cấp các số:

n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
e: 0x3
c: 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

Sử dụng ý tưởng trên, dễ dàng vét cạn số $k$ với kiểm tra số lập phương bằng chương trình đơn giản như sau:

k = 0
while True:
    cube_root1, exact1 = gmpy2.iroot(c - k * n, 3)
    cube_root2, exact2 = gmpy2.iroot(c + k * n, 3)
    if exact1:
        print('m =', cube_root1)
        break
    if exact2:
        print('m =', cube_root2)
        break
    k = k + 1

Kết quả thu được số $m$:

2. Định lý thặng dư Trung Hoa - Chinese Remainder Theorem (CRT)

2.1. Định lý thặng dư Trung Hoa

Định lý thặng dư Trung Hoa phát biểu rằng: Cho $a_1, a_2, ..., a_n \in Z$, $m_1, m_2, ..., m_n \in Z^+$, trong đó mỗi cặp số $(m_i, m_j)$ bất kỳ nguyên tố cùng nhau, khi đó hệ phương trình module sau:

$$x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_1}\\ ...\\ x \equiv a_n \pmod {m_n}\\$$

Có nghiệm duy nhất theo module $M=m_1m_2...m_n$ là:

$$x = a_1M_1y_1 + a_2M_2y_2 + ... + a_nM_ny_n \pmod {M}$$

Trong đó $M_i = \frac{M}{m_i}$, $y_i \equiv (M_i)^{-1} \pmod {m_i}$ hay $y_iM_i \equiv 1 \pmod {m_i}$.

Chúng ta cũng có thể giản lược các giá trị $y_i$, viết lại công thức nghiệm trên thành:

$$x = a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + ... + a_nM_nM_n^{-1} \pmod {M}$$

Để giải được hệ phương trình module trên, theo công thức định lý thặng dự Trung Hoa thì chúng ta chỉ cần tính được các giá trị $M$, $M_i$ và $y_i$.

Ví dụ giải hệ phương trình module:

$$x \equiv 2 \pmod {3}\\ x \equiv 3 \pmod {5}\\ x \equiv 5 \pmod {7}\\$$

Tính được:

$$M=3.5.7=105\\ M_1 = 5.7=35, M_2=3.7=21,M_3=3.5=15\\ y_1 = (35)^{-1} \pmod {3} = (2)^{-1} \pmod {3} = 2\\ y_2 = (21)^{-1} \pmod {5} = (1)^{-1} \pmod {5} = 1\\ y_3 = (15)^{-1} \pmod {7} = (1)^{-1} \pmod {7} = 1\\$$

Từ đó $x=2.35.2+3.21.1+5.15.1\pmod {105}=68\pmod {105}$, tức là $x$ có dạng $x=105k+68$ ($k\in Z$).

2.2. Áp dụng vào giải mã RSA

Khi bài toán RSA đồng thời mã hóa thông điệp với nhiều cặp khóa, chúng ta có thể áp dụng ý tưởng định lý trên nhằm giải quyết hệ phương trình module như sau:

$$c_1 = m^e \pmod {n_1}\\ c_2 = m^e \pmod {n_2}\\ c_3 = m^e \pmod {n_3}$$

Coi $m^e$ là ẩn $x$ cần tìm, sử dụng công thức nghiệm trên ta có:

$$m^e = c_1M_1M_1^{-1} + c_2M_2M_2^{-1} + c_3M_3M_3^{-1} \pmod {M}$$

Với $M=n_1n_2n_3$, $M_i=\frac{M}{n_i}$

2.3. Challenge CTF

Challenge đưa ra các số $n$ và các bản mã $c$:

n1 = 129114230505356333697118994510021413915051088225570531043026917550451581564734952308651566723784981323900403426111056537185011193232603296112121643742691356399992969898010827710994350803494919151948423732426591598888439712920344266205641475348312727365971717305409127667391782677854219689063549759596429716629
c1 = 112820376318708309511883266356668393396816131447182791445506209031700236878469506355658352414748854472099361508824474365112325602319862842561436679067358900089331778617100580343694334226208753320435002324108477884950933641216044198203776075918323272795752182687450526442079367110656868374931125538339145721573
n2 = 109269702205029292120022054633721536134438763741801805368759852020529400112797868566931991813909053016228871499067304592740926931055426540840268677218282537450757063806695831503892336975370479004151114020279110611956433492281834217463178735931660370487895538198474855043942908224106013915984721193047940206159
c2 = 45651293556966072304818630107703140982560165499022836594523320391474750266281527820821435052904791681898782443840766880327957385288649094238886877657228597671521358830021677304123300882210216797719566693160533018601632768048713030788957904378243453859832229603157052843135978639276611231634399594108602071349
n3 = 130184984206907873325788608067133260010668825744109785989754700869397713689450907426005869455386099782561530247238688647088683853688926890638399087109982966623800264662846723141786785531512452737825132399495839974974884122270947543684537604890177662807013640102549749593966105133111628112742472630785570141963
c3 = 7145575537980676074780210417817024536632595547590648616669010213946256431795860784357127920679439181517662499063976244238924613193503273987203026894830988537974932336129245277788828190575305229420617551083516420170192425247732269483299819348769856966536443995217830327641185916042049253075074223777360483322

Với ba bộ số $(n, c)$ như trên chúng ta có thể nghĩ tới ý tưởng sử dụng công thức nghiệm trong định lý Thặng dư Trung Hoa nhằm giải quyết challenge.

Tính các giá trị $M, M_iM_i^{-1}$:

M = n1 * n2 * n3
M1xM_1_inv = n2 * n3 * gmpy2.invert(n2 * n3, n1)
M2xM_2_inv = n1 * n3 * gmpy2.invert(n1 * n3, n2)
M3xM_3_inv = n1 * n2 * gmpy2.invert(n1 * n2, n3)

Lưu giá trị $c_1M_1M_1^{-1} + c_2M_2M_2^{-1} + c_3M_3M_3^{-1}$ vào biến num:

num = c1 * M1xM_1_inv + c2 * M2xM_2_inv + c3 * M3xM_3_inv

Do giá trị $M=n_1n_2n_3$ rất lớn nhất có thể khẳng định x = m^e = num % M. Giá trị $x$ tìm được như sau:

Bước cuối cùng chỉ cần thử từng giá trị của $e$ để tìm ra thông điệp $m$.

e = 2
while True:
    m, exact = gmpy2.iroot(x, e)
    if exact:
        print('m =', m)
        print('flag =', long_to_bytes(m))
        break
    e = e + 1

Kết quả tìm được thông điệp rõ:

VIII. Wiener's attack

1. Cơ sở lý thuyết

Wiener's attack nhắm vào các bài toán RSA với $q<p<2q$, đồng thời số $d$ thỏa mãn $d<\frac{1}{3}N^{\frac{1}{4}}$. Kỹ thuật tấn công hoạt động hiệu quả khi số $e$ rất nhỏ hoặc rất lớn.

Trong trường hợp này, định nghĩa:

$$G = GCD(p-1, q-1)\\ \lambda(n) =lcm(p-1, q-1)=\frac{(p-1)(q-1)}{G}=\frac{\phi(n)}{G}$$

Khi đó ta có công thức:

$$ed \equiv 1 \pmod {\lambda(n)}$$

Về hàm tấn công giải mã $d$ chúng ta có thể tham khảo qua link:

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

2. Challenge CTF

Ví dụ challenge CTF đưa ra các giá trị như sau:

c: 1778673018511075140350698252891639557906407090250539057221806340768776705763113815373271713598206734943304136885307657644746166557801527614555955063613958550715606102502660768573300084767410478866161295739179626743292839204862654148472896949835346074323716667404949929701903737872090588147698250826373180618

n: 77531969503748326589677418948315140870584015245386763633241518845356850979564402923266696704186567270006361208862086254527576010412135230279553684940635956656649728134893874567619948675304052482720430367748612708917105846534082863042823913166120865362252479206576942147071396319459112580853771742537940112457

e: 56172436577459725698934391359139104915041430213184221292301658571726414059411889155782982024019814564512291421932489731563519296372873415080546379424619308859152360214209740169135159761234894923144971372974038021945201954600238994209605035703317119192844975463915465725406543097929017637859019950590916533609

Nhận thấy số $e$ được lựa chọn đủ lớn, chúng ta có thể sử dụng ý tưởng tấn công Wiener's attack. Vận dụng chương trình trong Github tham khảo chúng ta tìm được giá trị $d$:

Tài liệu tham khảo

• https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• https://www.amsi.org.au/teacher_modules/pdfs/Maths_delivers/Encryption5.pdf
• https://sites.math.washington.edu/~morrow/336_09/papers/Yevgeny.pdf
• https://people.math.harvard.edu/~cmwang/teaching/55/2-21.pdf
• https://iacr.org/archive/ches2008/51540128/51540128.pdf
• https://asecuritysite.com/cracking/rsa_ctf01?m0=Hello12&p0=64
• https://github.com/pablocelayes/rsa-wiener-attack