CHƯƠNG III. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG RSA
3.6. Một số tấn công bằng nhân tử hóa số N với số N lớn
Khi cácsơ hở của hệ mật RSA được “bịt kín” thì người ta thường sử dụng một số tính toán sau đây đểnhân tửhóa sốN.
3.6.1. Tìm nhân tử lớn nhất thứ nhất ≤ N
Định lý 7 Fermat: Giả sử n là một số nguyên dương lẻ có dạng n = p.q.
Trong đóp≤q và p, q là các số nguyên tố. Khi đó biểu thức n có thể được viết dưới dạng: n = t2 – s2 (t, s là các số nguyên dương). Các số nguyên t, s, p và q có mối quan hệ: t =
2 q p+
và s = 2
p q−
Phương pháp này được xây dựng dựa trên định lý Fermat, cụthể:
1. Đặt x = 2. N + 1, y = 1, r = N 2 - n.
2. If r ≤0 go to (4) 3. r = r–y,
y = y+2 goto (2)
4. If r =0 then thuật toán dừng Khi đó chúng ta sẽcó:
n =
+ −
−
2 2 2
y x y
x {Đây chính là hai nhân tửcủa n(p,q)}
và 2 y x−
là phân sốcó giá trịlớn nhất ≤ N 5. r = r + x
x = x+2 goto (3)
Thuật toán này đơn giản nhưng sửdụng nhiều vòng lặp 3.6.2. Phân tích thứ hai
Như chúng ta đã phân tích,đ ộan toàn của hệmật RSA phụthuộc vào độkhó của phép phân tích n thành các thừa số nguyên tốp, q. Nếu trong hai số nguyên tố p, q; sốnày nhỏ hơn sốkia rất nhiều thì khả năng phân tích được n là rất cao. Vì thế khi thiết kế, các chuyên gia khuyến cáo nên chọn giá trị p, q sao cho p < n< q và độdài của p xấp xỉbằng một nửa độdài của n. Khí đó xác suất p nằm trong khoảng (23 n+1, n) là rất cao.
Bài toán đặt ra là cho n là số nguyên dương lẻ, d≥23 n+1. Tìm nhân tử lẻ nhỏnhất f sao cho d < f≤ n. Thuật toán được thực hiện như sau:
(1) Đặt r = n mod d {trong đó d = 3 n +1}
r’ = n mod (d- 2)
q = 4 ;
2
−
− d
n d
n
s = n ;
(2) If d> s thuật toán kết thúc với kết quảkhông tìmđược nhân tử;
(3) Đặt d = d +2, x = r r = 2r– r’, r’ = x (4) If r < 0, set r = r + d
q = q + 1, goto (6) (5) If r < d, set r = r–d
q = q - 1, goto (5)
Thuật toán kết thúc, ta sẽ thu được f = d Else goto (2)
Ta thấy rằng thuật toán sẽ quét tất cả các giá trị lẻ nằm trong khoảng ( n
n 1, 23 + )
3.6.3. Phân tích thứ ba
Ta lấy r sốnguyên: m1, m2, . ., mrthỏa mãn gcd(mi, mj) = 1 ∀i, j∈{ }1,r
Trước tiên ta lập ma trận S[i, j] với 1≤i≤r,0≤ j≤mi−1thỏa mãn:
Thuật toán tiến hành như sau:
Set x = n và ki= (-x) mod mi. For 1 ≤ i ≤ r If S[i,j] = 1
For 1 ≤ i ≤ r goto (4)
Set x = x + 1, ki= (ki-1) mod mi
For 1 ≤ i ≤ r goto (2) Set y = x2−n or x2−n
If y2= x2–b then (x - y) là một nhân tửcần tìm của n và thuật toán kết thúc Else goto (3).
Trong đó:
- x là sốnguyên bé nhất mà lơn hơn hoặc bằng x.
- x là sốnguyên lớn nhất mà nhỏ hơn hoặc bằng x.
3.6.4. Thuật toán Pollard (p-1)
Giảsửta cần phân tích N = pq. Nếu nhưp–1 có phân tích chuẩn:
vớiαklà các sốnguyên không âm, còn pklà các sốnguyên tốnhỏ.
Khi đó, nếu chọn B là một giới hạn nào đó. Để ý thấy rằng, hiện tại, ta chỉ biết được p-1 có thể phân tích được thành tích của các số nguyên tố bé chứkhông biết các thừa sốnguyên tố đó là bao nhiêu. Nhưng vìđó là các s ốnguyên tốbé, nên có thểchọn một giới hạn không lớn B.
Pollarl mô tảthuật toán p -1như sau:
Thuật toán p -1 của Pollard:
Input N và B Begin
1. a = 2
2. For j = 2 to B Do a = ajmod N 3. d = gcd(a-1, N) 4. If 1 < d < N then
d là một thừa sốnguyên tốcủa N /* thành công*/
Else
Không tìmđược thừa sốnguyên tốcủa N /*thất bại*/
End.
Thuật toán có đầu vào là Nvà B, trong đó, N là lẻcần được phân tích nguên tố, còn B là một giới hạn.
Giảsửrằng, p là một ước nguyên tốcủa N, còn q là sốnguyên tốbất kỳthỏa mãn q≤ B và q|(p-1).
Người ta chỉra rằng, tồn tại trường hợp như sau xảy ra:
(p–1) | B!
Trởlại thuật toán, sau khi kết thúc vòng lặpở bước 2, ta có:
a 2B!( mod N) Vì N = p×q nên ta cũng có:
a 2B!( mod p)
Theo định lý Fermat: 2p-1 1 (mod p)
mà (p-1) | B! a 1 (mod p)
p | (a -1)
lại có: p | N p | d = gcd(a–1, N)
Sốnguyên d là một ước không tầm thường của N (ngoại trừ trường hợp a = 1 trong bước 3). Việc tìmđược một ước nguyên tố của N sẽ cho phép ta tìm được nốt ước nguyên tốcòn lại, và do đó phân tích được thừa sốnguyên tốcủa N.
Ta đưa ra một ví dụ minh họa phương pháp phân tích nguyên tố modul N như vừa nêu trên.
Giảsửrằng N = 15770708441. Ta áp dụng thuật toán trên với B = 180 sau bước 2, ta tìmđược a = 11620221425. Và trong bước 3 ta tính được d = 135979.
Đây chính là một ước nguyên tố của N:
N = 15770708441 = 135979 × 115979 Nhận xét:
Trong trường hợp này, ta phân tích thành công vì p–1 = 135978 là tích của các sốnguyên tốnhỏ:
p–1 = 135978 = 2 ×3 ×131 × 173
Vì thế, nếu chọn B≥ 173 sẽ xảy ra trường hợp 135978 | B! như đã nói ởtrên (đó là (p–1) | B!).
Do đó, nếu hệmật RSA sửdụng modul N có thừa sốnguyên tốp mà p -1 chỉ có các thừa sốnguyên tốnhỏthì kẻthù có thểphá vỡ được hệthống bằng việc phân tích modul Ntheo phương pháp p – 1 như trên.
Tới đây, ta có thể khuyến cáo người dùng khi thực thi hệ mã hóa RSA, khi sinh các sốnguyên tốp và qđểtạo ra modul N, tuyệt đối, không nên sửdụng các số nguyên tốmà hiệu của nó với 1 (p -1 hay q -1) có phân tích nguyên tốlà các thừa số nguyên tốnhỏ.