CHƯƠNG III. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG RSA
3.7. Một số phương pháp gài bẫy mới trong RSA
Marvin sẽthực hiện cặp sốnguyên tốp và q cóđộdài k bit. Thông tin bí mật được chọn là cặp hai số tự nhiên (a, b) cùng độ dài ks bit, với ks < k, được gọi là nhân, và lớn hơn:
( , ) = ln(1 − ) ÷ ln(1 − ) , ớ ≈ 1.
Đồng thời, Marvin chọn ngẫu nhiên một sốtựnhiên x sao cho ax và bx cóđộ dài k bit, tức là sốbit của x bằng cỡk–ks.
Sửdụng Luật Phân bốSốnguyên tố, có thểchỉrằng: Với ( , ) = ln(1 − ) ÷ ln(1 − ) ,
trongđó k là một số nguyên dương và là một số thực thỏa mãn 0 < < 1, trong khoảng ( , )các sốtựnhiên độdài k bit, xác suấtđểtồn tại ít nhất một sốnguyên tố là . Do a lớn hơn ( , ), với xấp xỉ 1, nên hầu như chắc chắn trong khoảng ( , )số tựnhiên liên tiếp tính từ ax tồn tại ít nhất một số nguyên tố có dạng p = ax + i, với i < ( , )< a.Điều này cũngđúng với b và tồn tại sốnguyên tố q = bx + j, với j < ( , )< b. Việc tìm i và j bằng cách duyệt từng giá trị khả thi trong thời gian chấp nhậnđược bởi giá trị ( , )là rất bé: với sốbit k = 2048 và xác suất
= 0.999, thì ( , )= 4900.
Nhưvậy, chương trìnhsinh được cặp hai sốnguyên tố:
= + 0 < < ( , )
= + 0 < < ( , )
và chương trình sửdụng chúngđểsinh khóa RSA. Alice nhậnđược khóa công khai (n, e) do chương trình gài bẫy sinh ra rồi thông báo khóa công khai này tới mọi người. Một khi Marvin lấy được khóa công khai này, thì anh ta có thể thực hiện việc phân tích n một cách hiệu quảnhưsau: Nhận xét rằng:
= + 0 < <
= + 0 < < ⟹ = ( + )( + ) > . Do i và j tươngứng nhỏhơn a và b nên: < < ( + 1) . Suy ra:
< < ( + 1) .
Vì nắm trong tay nhân bí mất (a, b) nên Marvin tínhđược:
= .
Sauđó, Marvin tìm sốtựnhiên i < a sao cho p = ax + i làước của n, và tính q = n/p. Khiđó, p và q là phân tích nguyên tốcủa n, tức là khóa RSAđã bịphá.
3.7.2. Phương pháp gài bẫy nhân độc lập (IS)
Ởphương pháp SP, nhân bao gồm hai sốnguyên a và b phảiđược chọnđồng thời, nên không thểáp dụng cho các sơ đồmà các sốnguyên tố được lấy từmột kho các sốnguyên tốcực lớn và có sẵn. Tuy nhiên, ởphương pháp IS, các sốnguyên tố được sử dụng để sinh khóa không nhất thiết phải được sinh cùng nhau mà chỉ cần được lấy từmột kho sốnguyên tốcực lớn có sẵn nàođó, mà phương pháp SP không áp dụngđược.
Ta chọn hằng số M, c cố định ( M có số bit t0 được giữ bí mật) và một số nguyên tốu ngẫu nhiên có sốbit t. Nhân ađược sinh ra phụthuộc u bởi công thức
= ( ). 2 + , (1.1)
trongđó
( ) = + ,
tương tự nhân b được sinh ra phụthuộc vào số nguyên tố v (có số bit t) bởi công thức
= ( ). 2 + .
Có thểlấy thiết lập các giá trịM, c, t lớn, để sinh được a và b cực lớn, đểkho số nguyên tốcó khối lượng lớn nhằm mục đích: ngẫu nhiên p, q từkho số nguyên tố, khảnăng các cặp (p, q) được lấy lặp lại là rất thấp.
Mong muốn của ta là tìm lạiđược a, b khi biết ab. Ta có
= ( ) ( )2 + [ ( ) + ( )]2 + . (1.2) Trong vếtrái của (1.2) ta có:
• Sốbit của uv nhỏhơn 2t+1.
• Vì sốbit của f(v) và f(u) nhỏhơn t0(là sốbit của M) nên sốbit của [ ( ) + ( )]2 nhỏ hơn 3t + t0 + 3 < 4t + 2 (vì t > t0). Do đó số bit của [ ( ) + ( )]2 nhỏhơn 4t + 2.
Dođóvếtrái của (1.2) ta có thểphân tách thành 3 phần riêng biệt:
( ) ( )2 + [ ( ) + ( )]2 + A, B, Cđược tính nhưsau:
⎩⎪
⎨
⎪⎧ = ( ℎé ℎ ê )
≔ 2
= ( ℎé ℎ ê )
= 2
Từ đóta có hệphương trình sau:
f(u)f(v) = A (1.3)
uf(v) + vf(u) = B (1.4)
uv = C (1.5)
Giải hệphương trình(1.3), (1.4), (1.5) ta được ( ) = ±√
( ) = ∓√ (1.6)
Đếnđây ta cần xácđịnh f(v) và f(u)để tìm lại được u, v. Từcách định nghĩa của hàm f thì giá trịcủa hàm f luôn thuộc khoảng , , và M được chọn là nhỏ nên hoàn toàn có thể duyệt tìm các giá trị trong khoảng từ đến M để tìm lại f(u), f(v). Cụthể, từ(1.6) ta chọn giá trị
= √
= √
rồi duyệt tìm i trong khoảng từ đến M sao cho i| . Từ đóta tínhđược
= ,
Và suy ra
= ( ).
Vì u, v là các sốnguyên tốnên chỉtồn tại duy nhất một cặp (u, v) thỏa mãn (1.5). Dođóquá trình duyệt tìm dừng lại khi ta tìmđược cặp u, v thỏa mãn (1.5).
Sau khiđã xácđịnhđược u, v thì ta sửdụng(1.1) đểtính lại nhân a, b tương ứng. Do tính duy nhất của cặp u, v tìmđược nên ta chỉ tìmđược duy nhất cặp nhân a, b.
Phần còn lại của bài toán là làm thếnào tìm lạiđược ab khi biết n = pq. Để làmđượcđiều này chúng ta tìmđiều kiện của i, j sao cho
= (1.7)
Từ(1.7) ta có
< < ( + 1) ⟺ − < (1.8) Ta có n =pq = (ax + i)(bx + j) nên từ(1.8) ta có
(aj + bi)x + ij < x2 (1.9)
Gọi sốbit của x là kx, sốbit của a và b cỡka= 2t + t0và sốbit của p và q cỡkp. Vì t và t0là các hằng sốbí mậtđược chọntrước nên ta hoàn toàn có thểchọn sao cho
= +
= − ớ à ℎằ ố ℎỏ
Khiđóta chọn i, j là các sốtựnhiên sao cho , ≤ − 1thì dễdàng chứng minh được (1.9) thỏa mãn. Đểcho việc chọn i và j chỉ phụ thuộc tương ứng vào a và b thì ta chọn i, j có sốbit cỡkx–(ka+1)–1 = kx–2t–t0- 2.
Từcách chọn i, j ta dễdàng suy ra rằng sốbit của i, j lớn hơn sốbit của a, b xấp xỉ3 . Dođói và j tươngứng lớn hơn a và b.