VI. Tấn công bằng số module chung

1. Cơ sở lý thuyết

Trong mật mã RSA, nếu một thông điệp m được mã hóa đồng thời với một số n dùng chung và hai số riêng biệt e1, e2 thỏa mãn điều kiện GCD(e1, e2) = 1, thì có thể áp dụng hình thức tấn công Common module attack để tìm ra thông điệp gốc khi biết các bản mã.

Bài toán này được phát biểu như sau: Ta có các dữ liệu đã biết:

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

Khi đó, ta có thể phân tích để tìm ra thông điệp qua các yếu tố đã biết. Vì GCD(e1, e2) = 1, nên có thể tìm được hai số nguyên s1 và s2 sao cho e1 * s1 + e2 * s2 = 1. Ta có:

c1 = m^{e1} (mod n)
c2 = m^{e2} (mod n)

Bằng cách sử dụng phương trình e1 * s1 + e2 * s2 = 1, ta tìm được:

c1^{s1} * c2^{s2} = m (mod n)

Như vậy, ta sẽ xác định được thông điệp m.

2. Thử thách 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 có số n chung và hai e nguyên tố cùng nhau. Chúng ta sẽ tìm hai số s1 và s2 thỏa mãn e1 * s1 + e2 * s2 = 1 và từ đó tìm ra thông điệp m.

VII. Tấn công chỉ số khóa công khai nhỏ

1. Ví dụ với e = 3

1.1. Cơ sở lý thuyết

Khi số e được chọn nhỏ với e = 3, tức là:

c = m^{3} (mod n)

Điều này nghĩa là tồn tại số k sao cho c = k * n + m^{3}. Ta có thể thử từng giá trị của k để tìm m.

Điều này có thể thực hiện bằng cách sử dụng hàm math.pow trong module math hoặc hàm gmpy2.iroot cho số lớn, nhằm kiểm tra số lập phương

import gmpy2

x = gmpy2.mpz(64)
cube_root, exact = gmpy2.iroot(x, 3)

1.2. Thử thách CTF

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

n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L

e: 0x3

c: 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

Sử dụng ý tưởng trên ta có thể thử từng giá trị của k để kiểm tra số lập phương và tìm ra m.

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

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

Định lý nêu rằng: Cho a1,a2,...,an ∈ Z, m1,m2,...,mn ∈ Z+ với mọi cặp (mi,mj) nguyên tố cùng nhau, tồn tại nghiệm duy nhất x cho hệ phương trình module sau:

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ an (mod mn)

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

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

2.3. Thử thách CTF

Challenge cung cấp các số n và bản mã:

(n1, c1)
(n2, c2)
(n3, c3)

Chúng ta có thể sử dụng định lý thặng dư Trung Hoa để giải quyết.

VIII. Tấn công của Wiener

1. Cơ sở lý thuyết

Wiener’s attack nhắm vào RSA với q < p < 2q, và số d nhỏ hơn 1/3 N^{1/4}. Kỹ thuật này phù hợp khi số e rất nhỏ hoặc rất lớn.

2. Thử thách CTF

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

c, n, e

Sử dụng chương trình trong Github, chúng ta có thể tìm ra 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
  source: viblo