i
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG
VÕ TÁ HOÀNG
NGHIÊN CỨU XÂY DỰNG
THUẬT TOÁN TẤN CÔNG HỆ MẬT RSA
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Thái Nguyên – 2020
ii
LỜI CAM ĐOAN
Học viên xin cam đoan luận văn này là công trình nghiên cứu thực sự của
bản thân, dưới sự hướng dẫn khoa học của TS. Hồ Văn Canh.
Các số liệu, kết quả trong luận văn là trung thực và chưa từng được công
bố dưới bất cứ hình thức nào. Tất cả các nội dung tham khảo, kế thừa của các tác
giả khác đều được trích dẫn đầy đủ.
Em xin chịu trách nhiệm về nghiên cứu của mình.
Người cam đoan
Võ Tá Hoàng
iii
LỜI CẢM ƠN
Học viên trân trọng cảm ơn sự quan tâm, tạo điều kiện và động viên của
Lãnh đạo Trường Đại học Thái Nguyên, các thầy cô Khoa Đào tạo sau đại học,
các khoa đào tạo và các quý phòng ban Học viện trong suốt thời gian qua.
Học viên xin bày tỏ sự biết ơn sâu sắc tới TS. Hồ Văn Canhđã nhiệt tình định
hướng, bồi dưỡng, hướng dẫn học viên thực hiện các nội dung khoa học trong
suốt quá trình nghiên cứu, thực hiện luận văn.
Xin chân thành cảm ơn sự động viên, giúp đỡ to lớn từ phía Cơ quan đơn
vị, đồng nghiệp và gia đình đã hỗ trợ học viên trong suốt quá trình triển khai các
nội dung nghiên cứu.
Mặc dù học viên đã rất cố gắng, tuy nhiên, luận văn không tránh khỏi những
thiếu sót. Học viên kính mong nhận được sự đóng góp từ phía Cơ sở đào tạo, quý
thầy cô, các nhà khoa học để tiếp tục hoàn thiện và tạo cơ sở cho những nghiên
cứu tiếp theo.
Xin trân trọng cảm ơn!
Hà Nội, tháng năm 2020
Học viên
Võ Tá Hoàng
iv
MỤC LỤC
LỜI CAM ĐOAN................................................................................................... i
LỜI CẢM ƠN ...................................................................................................... iii
MỤC LỤC ............................................................................................................ iv
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ............................................... vii
DANH MỤC HÌNH VẼ, BẢNG BIỂU ............................................................. viii
MỞ ĐẦU ............................................................................................................... 1
CHƯƠNG 1: TÌM HIỂU VỀ HỆ MẬT RSA ....................................................... 4
1.1 Hệ mật mã hóa RSA ........................................................................................ 4
1.1.1 Mô tả hệ mật RSA .................................................................................... 4
1.1.2 Thực thi hệ mật RSA ................................................................................ 6
1.1.3 Vấn đề an toàn của hệ mật RSA............................................................... 6
1.2 Tính an toàn của hệ mật mã RSA.................................................................... 7
1.2.1 An toàn vô điều kiện ................................................................................ 7
1.2.2 An toàn được chứng minh ........................................................................ 7
1.2.3 An toàn tính toán ...................................................................................... 7
1.3 Các kiểu thám mã ............................................................................................ 8
1.3.1 Bài toán thám mã chỉ biết bản mã ............................................................ 9
1.3.2 Bài toán thám mã khi các cặp rõ/ mã đã biết ........................................... 9
1.3.3 Bài toán thám mã với bản rõ lựa chọn ..................................................... 9
1.3.4 Bài toán thám mã với bản mã lựa chọn .................................................... 9
1.4 Tấn công hệ mật RSA lợi dụng những lỗ hổng của chúng ............................. 9
1.4.1 Biết (n) tìm được p, q ........................................................................... 10
1.4.2 Biết số mũ bí mật của RSA .................................................................... 10
1.4.3 Giao thức công chứng ............................................................................ 12
1.4.4 Giao thức module n chung ..................................................................... 14
1.4.5 Giao thức số mũ công khai nhỏ.............................................................. 20
1.4.6 Giao thức số mũ bí mật nhỏ ................................................................... 21
v
1.4.7 Trường hợp các tham số p-1 và q-1 có các ước nguyên tố nhỏ ............. 24
Kết luận Chương 1 .............................................................................................. 26
CHƯƠNG 2: NGHIÊN CỨU MỘT SỐ THUẬT TOÁN TẤN CÔNG HỆ MẬT
RSA ..................................................................................................................... 27
2.1 Kiểm tra tính nguyên tố của một số .............................................................. 27
2.1.1 Đặt bài toán ............................................................................................ 27
2.1.2 Các thuật toán kiểm tra tính nguyên tố theo xác suất ............................ 28
2.1.2.1 Thuật toán Fermat ............................................................................... 29
2.1.2.2 Thuật toán Solovay-Strassen ............................................................... 29
2.1.2.3 Thuật toán Miller-Rabin ...................................................................... 30
2.1.2.4 So sánh thuật toán Fermat, Solovay-Strassen và Miller - Rabin ........ 31
2.1.2.5 Kiểm tra tính nguyên tố của số nguyên tố Mersenne.......................... 32
2.1.2.6 Một số thuật toán kiểm tra tính nguyên tố khác .................................. 32
2.2 Các thuật toán phân tích thừa số ................................................................... 34
2.2.1 Thuật toán tìm nhân tử lớn nhất thứ nhất ............................................... 34
2.2.2 Thuật toán phân tích thứ hai ................................................................... 37
2.2.3 Thuật toán phân tích thứ ba .................................................................... 38
Kết luận Chương 2 .............................................................................................. 42
CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN TẤN CÔNG RSA KHÔNG CẦN
PHÂN TÍCH NHÂN TỬ..................................................................................... 43
3.1 Mở đầu........................................................................................................... 43
3.2 Cơ sở toán học của thuật toán ....................................................................... 44
3.2.1 Một số mệnh đề ...................................................................................... 44
3.2.2 Xác định hàm ф(n) ................................................................................. 45
3.3 Đề xuất thuật toán ......................................................................................... 46
3.3.1 Lưu đồ giải thuật .................................................................................... 46
3.3.2 Xây dựng chương trình .......................................................................... 47
3.3.3 Một số ví dụ............................................................................................ 51
Kết luận Chương 3 .............................................................................................. 53
vi
KẾT LUẬN ......................................................................................................... 54
DANH MỤC TÀI LIỆU THAM KHẢO ............................................................ 55
PHỤ LỤC ............................................................................................................ 57
Phụ lục Mã nguồn Chương trình ......................................................................... 57
Phụ lục Thư viện tính toán số lớn ....................................................................... 71
1 Biểu diễn số lớn ................................................................................................ 72
2 Các phép toán với số lớn .................................................................................. 73
vii
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Ký hiệu,
Ý nghĩa
viết tắt
RSA
Rivest - Shamir - Adlemal
Hệ mật mã RSA
RCT
Chinese Remainder Theorem Định lý đồng dư Trung Hoa
GCD
Greatest Common Divisor
Ước chung lớn nhất
GF (P)
Trường số thực
GF (2)
Trường nhị phân
K
Tập hợp khóa mã
E
Thuật toán mã hóa
D
Thuật toán giải mã
P
Tập hợp các bản rõ
C
Tập hợp các bản mã
n
Hàm Phi_Ơle
p, q
Cặp số nguyên tố p và q
n
Số nguyên dương bất kỳ
x
Văn bản rõ thuộc P
y
Bản mã thuộc C
k'
Thành phần khóa công khai
k ''
Thành phần khóa bí mật
s
Số nguyên tố Mersenne
r
Số nguyên lẻ
viii
DANH MỤC HÌNH VẼ, BẢNG BIỂU
Hình 3.1: Lưu đồ thuật toán ................................................................................ 47
Hình 3.2: Giao diện chính của chương trình ...................................................... 48
Hình 3.3: Kiểm tra tính chẵn của số cần phân tích ............................................ 49
Hình 3.4: Kiểm tra tính nguyên tố của số cần phân tích .................................... 49
Hình 3.5: Chức năng phân tích ........................................................................... 50
Hình 3.6: Chức năng dừng trong quá trình phân tích ........................................ 50
Hình 3.7: Chức năng hiển thị kết quả ................................................................. 51
1
MỞ ĐẦU
1. Đặt vấn đề
Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len
Adleman, công bố lần đầu vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ,
được sử dụng trong lĩnh vựcbảo mật và cung cấp cơ chế xác thực của dữ liệu
số [3],[17]. Ngày nay, RSA đã được phát triển và ứng dụng rộng rãi trong tất
cả các lĩnh vực đời sống, kinh tế xã hội, an ninh quốc phòng, đặc biệt là trong
thương mại điện tử. Theo [4],[6] RSA được sử dụng nhiều nhất để trao đổi khóa
bí mật và xác thực đối với hệ mật mã đối xứng; sử dụng trên web servers và
trên các browsers nhằm đảm bảo an ninh đường truyền, đặc biệt RSA được coi
là hạt nhân của hệ thống thanh toán điện tử... Bởi vậy, nghiên cứu phân tích hệ
mật RSA luôn thu hút sự quan tâm của nhiều quốc gia, tổ chức, các tập đoàn,
công ty và các nhà khoa học đầu tư nghiên cứu [7],[9].
Ở nước ta hiện nay, hầu hết các cơ quan, tổ chức hoạt động trong lĩnh
vực bảo mật và các trung tâm nghiên cứu, trường đại học khối kỹ thuật đều có
những kết quả nghiên cứu, phân tích hệ số an toàn đối với các tham số hệ mật,
từ đó chỉ rõ những mối nguy hiểm tiềm ẩn cần cải thiện hệ mật RSA khi sử
dụng [5],[10]. Vấn đề thám mã đối với hệ mật RSA hiện nay đang được các
nhà nghiên cứu tập trung khai thác dựa trên các sơ hở của RSA như: tấn công
vào số mũ công khai hoặc số mũ bí mật thấp, tấn công vào các tham số nguyên
tố p, q bé hoặc cách xa nhau lớn, hoặc họ tập trung vào việc phân tích nhân tử
số n (modul của RSA). Trường hợp đối với số lớn, từ n 1024 trở lên thì các
phương pháp hiện tại không phát huy được hiệu quả hoặc chạy chậm và không
cho quả như mong muốn [3]. Mặt khác về mặt toán học đã chứng minh hiệu
quả của việc tấn công hệ mật RSA phụ thuộc vào cách thu hẹp khoảng cách dò
tìm số nguyên tố p đối với hệ mật RSA. Do vậy cần có những nghiên cứu tấn
công RSA mới mà không cần phân tích nhân tử [4].
2
Xuất phát từ thực tế đó, luận văn “Nghiên cứu xây dựng thuật toán tấn
công hệ mật RSA” mang tính cấp thiết, thực sự có ý nghĩa khoa học và thực
tiễn.
2. Đối tượng và phạm vi nghiên cứu
- Nghiên cứu về các phương pháp tấn công hệ mật RSA hiện nay và đề
xuất một phương pháp tấn công RSA mới.
- Sử dụng ngôn ngữ lập trình C để xây dựng chương trình phần mềm
được đề xuất.
3. Hướng nghiên cứu của luận văn
Nghiên cứu tổng quan về vấn đề an toàn hệ mật RSA, các phương pháp
tấn công RSA phổ biến hiện nay. Từ đó đi sâu nghiên cứu đề xuất một phương
pháp tấn công RSA mới, không dựa trên bài toán phân tích nhân tử. Nghiên
cứu xây dựng phần mềm giải pháp và thực nghiệm, đánh giá.
4. Những nội dung nghiên cứu chính
Chương 1: Tổng quan về hệ mật RSA
Nghiên cứu mô tả, thực thi hệ mật RSA, vấn đề an toàn và các kiểu,
phương pháp tấn công hệ mật RSA phổ biến.
Chương 2: Nghiên cứu một số thuật toán tấn công RSA
Tập trung nghiên cứu, phân tích một số thuật toán tấn công RSA phổ
biến sử dụng chung phương pháp phân tích nhân tử. Nội dung chính của chương
trình bày kết quả nghiên cứu các thuật toán kiểm tra số nguyên tố và thuật toán
phân tích số nguyên thành tích các thừa số nguyên tố.
Chương 3: Nghiên cứu đề xuất thuật toán tấn công RSA
Dựa trên cơ sở lý thuyết toán học, nội dung Chương 3 nghiên cứu, tìm
hiểu và xây dựng chương trình thuật toán tấn công hệ mật RSA không cần phân
tích nhân tử. Việc tính toán, phân tích số nguyên n để xác định các số nguyên
tố p, q được thực hiện thông qua tính toán hàm n . Đồng thời đã phân tích,
tính toán thực nghiệm để đưa ra một số kết luận.
3
5. Phương pháp nghiên cứu
- Nghiên cứu các bài báo khoa học, công trình nghiên cứu trong nước và
quốc tế.
- Nghiên cứu, phân tích các phương pháp tấn công RSA hiện nay. Từ đó
xây dựng thuật toán tấn công RSA mới.
- Xây dựng phần mềm ứng dụng và đánh giá.
6. Ý nghĩa khoa học của luận văn
Nghiên cứu vấn đề tấn công hệ mật RSA có ý nghĩa và vai trò to lớn
trong việc vệ an ninh thông tin. Đây là vấn đề đang được quan tâm, thu hút
nhiều quốc gia, tổ chức, cá nhân đầu tư nghiên cứu. Học viên đã nghiên cứu
tìm hiểu và xây dựng phần mềm giải pháp tấn công RSA, không cần phân tích
nhân tử. Do vậy, luận văn có tính khoa học và ứng dụng thực tiễn.
4
CHƯƠNG 1: TỔNG QUAN VỀ HỆ MẬT RSA
1.1 Hệ mật mã hóa RSA
Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir và Len
Adleman và được Scientific American công bố lần đầu tiên vào năm 1977 [17].
Hệ mật RSA được sử dụng để bảo mật và đảm bảo tính xác thực của dữ
liệu số. Hiện nay RSA được sử dụng trong hệ thống thương mại điện tử, các
dịch vụ Web Server và Web Browser. RSA còn được sử dụng để đảm bảo tính
xác thực vào bảo mật của Email, đảm bảo an toàn cho các phiên truy cập từ xa
và là bộ phận quan trọng của hệ thống thanh toán thẻ tín dụng. Như vậy ta có
thể thấy rằng RSA thường được sử dụng trong các ứng dụng cần đảm bảo sự
an toàn và bảo mật dữ liệu số cao.
1.1.1 Mô tả hệ mật RSA
Định nghĩa hệ mật RSA
Hệ mật RSA bao gồm bộ P, C, K , D, E . Trong đó [1]:
1. P là tập các bản rõ.
2. C là tập các bản ký tự mã.
3. K là tập các khóa k , mỗi khóa k gồm hai phần: k ' là khóa công khai
dành cho việc lập mã, còn k '' là khóa bí mật dành cho việc giải mã.
4. Với mỗi bản rõ x P , thuật toán lập mã E cho ta ký tự mã tương ứng
y E k', x C
5. Với mỗi ký tự mã y thuật toán giải mã D cho ta lại ký tự bản rõ x :
D k '' , y D k '' , E k ' , x x
Hệ mật RSA sử dụng các tính toán trong Z n trong đó n là tích của hai số
nguyên tố lớn phân biệt nhau p, q và n p 1q 1 . Mô tả hình thức của hệ
mật như sau:
Cho n p.q trong đó p, q là các số nguyên tố lớn phân biệt nhau sao cho
độ dài của hai số này là gần nhau nhất có thể được.
5
Đặt: P C Z n và định nghĩa k n, p, q, a, b : ab 1mod n
- Mã hóa: ek x x b mod n
- Giải mã:
d k y y a mod n
Trong đó x P , y C
Các giá trị n, b công khai còn các giá trị p, q, a được giữ bí mật.
Ta sẽ kiểm xem các phép mã hóa và giải mã có phải là các phép toán
nghịch đảo của nhau hay không?
Vì ab 1mod n nên ta có ab t. n 1 với một số nguyên bất kỳ t 1 .
Giả sử có x Z n khi đó ta sẽ xét hai trường hợp.
a.Trường hợp x, n 1 x n mod n 1. Khi đó ta có:
y a mod n xb mod n x t . n 1 mod n x n mod n x mod n 1t.xmod n xmod n
a
t
b. Trường hợp ( x, n) d 1 d p hoặc d q
Giả sử d p , khi đó x hp với 0 h q và h, n 1
Suy ra: y a mod n x b mod n h ab mod n p ab mod n mod n . Do h, n 1 nên
a
h ab mod n h . Bên cạnh đó ta lại có:
p ab mod n p ab mod pq p ab mod q p. p n mod q p. p p . q
p. p p
mod q p . Vậy
q
y a mod n hp mod n hp x
Ví dụ:
Giả sử Bob chọn
p 101 và q 113 . Khi đó
n pq 11413 và
n p 1q 1 100 .112 11200 .
Vì 11200 26.52.7 nên có thể dùng một số nguyên b khóa công khai có giá
trị không chia hết cho 2,5,7 . Anh ta kiểm tra điều kiện gcd n, b 1 bằng thuật
toán Euclidean.
Giả sử Bob chọn b 3533, khi đó theo thuật toán Euclidean mở rộng ta
có:
6
b1 6597 mod11200
Do vậy số mũ mật (khóa bí mật) để giải mã của Bob sẽ là a 6597 . Bob
sẽ công bố n 11413 và b 3533.
Giả sử Alice muốn gửi bản rõ 9726 đến Bob. Cô ta sẽ tính:
97263533 mod11413 5761
Rồi gửi bản mã 5761 trên kênh truyền. Khi Bob nhận được bản mã 5761
, anh ta sẽ sử dụng khóa bí mật để tính: 57616597 mod11413 9726
1.1.2 Thực thi hệ mật RSA
Để thiết lập hệ thống, Bob sẽ tuân theo các bước sau:
1. Bob tạo ra hai số nguyên lớn p và q sao cho độ dài của hai
số gần bằng nhau nhất có thể được.
2. Bob tính n p.q và n p 1q 1
3. Bob chọn một số ngẫu nhiên b 0 b n sao cho:
gcdb, n 1
4. Bob tính a b 1 mod n bằng cách sử dụng thuật toán
Euclidean.
5. Bob công bốHình
n và 1.1:
b trong
mộtthidanh
bạ và
dùng chúng làn
Thực
hệ mật
RSA
khóa
công
1.1.3
Vấn
đề khai.
an toàn của hệ mật RSA
Hệ mật RSA chỉ được an toàn khi giữ bí mật khóa giải mã a và thừa số
nguyên tố p, q (hay giữ bí mật n ).
Trường hợp biết được p, q thì Marvin dễ dàng tính được n p 1q 1
. Khi đó Marvin sẽ sử dụng thuật toán Euclidean mở rộng để tính a .
Khi biết a thì toàn bộ hệ thống sẽ bị phá vỡ ngay lập tức. Vì khi biết a ,
toàn bộ khóa K đều được biết và Marvin sẽ giải mã được và sẽ đọc được nội
dung của bản rõ, Ngoài ra Marvin có thể lập mã trên văn bản khác là cực kỳ
7
nguy hiểm. Nhất là những thông tin liên quan đến an ninh quốc gia, quân đội,
ngân hàng.
1.2 Tính an toàn của hệ mật mã RSA
Tính an toàn của một hệ thống mật mã phụ thuộc vào độ khó của bài toán
thám mã khi sử dụng hệ mật đó. Người ta đã đề xuất một số cách hiểu cho khai
niệm an toàn của hệ thống mật mã, để trên cơ sở các ccách hiểu đó nghiên cứu
tính an toàn của nhiều hệ mật khác nhau, sau đây là một vài cách hiểu thông
dụng nhất:
1.2.1 An toàn vô điều kiện
Giả thiết người thám mã có được thông tin về bản mã. Theo quan niệm
lý thuyết thông tin, nếu những hiểu biết về bản mã không thu hẹp được độ bất
định về bản rõ đối với người thám mã, thì hệ mật mã là an toàn vô điều kiện,
hay theo thuật ngữ của C.Shannon, hệ mật là bí mật hoàn toàn. Như vậy, hệ là
an toàn vô điều kiện, nếu độ bất định về bản rõ sau khi người thám mã có được
cả thông tin (về bản mã) bằng độ bất định về bản rõ trước đó. Tính an toàn vô
điều kiện thường được sử dụng cho các hệ mật mã khó đối xứng.
1.2.2 An toàn được chứng minh
Một hệ thống mật mã được xem là có độ an toàn được chứng minh nếu
ta có thể chứng minh được bài toán thám mã đối với hệ thống đó “khó tương
đương” với một bài toán khó đã biết, thí dụ bài toán phân tích một số nguyên
thành tích các thừa số nguyên tố, bài toán tìm lôgarit theo một modul nguyên
tố,…(“khó tương đương” có nghĩa là nếu bài toán này giải được thì bài toán kia
cũng giải được cùng một độ phức tạp như nhau).
1.2.3 An toàn tính toán
Hệ mật mã được xem là an toàn về mặt tính toán, nếu mọi phương pháp
thám mã đã biết đều đòi hỏi một nguồn năng lực tính toán vượt quá mọi khả
năng (kể cả phương tiện thiết bị máy móc) tính toán của một kẻ thám mã. An
8
toàn theo nghĩa này, nói theo ngôn ngữ của lý thuyết về độ phức tạp tính toán
là bao hàm cả khái niệm an toàn theo nghĩa “được chứng minh” nói trên.
Tính an toàn theo nghĩa được chứng minh hay tính toán được sử dụng
nhiều trong công việc nghiên cứu các hệ thống mật mã hiện đại, đặc biệt là các
hệ thống mật mã khóa công khai. Các bài toán đó đều có hạt nhân là tính an
toàn của các hệ mật mã, góp phần giải quyết các vấn đề an toàn thông tin kể
trên.
1.3 Các kiểu thám mã
Mật mã được sử dụng trước hết là để đảm bảo tính bí mật cho các thông
tin được trao đổi trên các kênh truyền thông công cộng. Do đó bài toán quan
trọng nhất của thám mã cũng chính là bài toán phá bỏ tính bí mật đó, tức là: với
những bản mã có thể dễ dàng thu được trên các kênh truyền thông công cộng,
người thám mã phải tìm ra được nội dung thông tin che dấu bên trong bản mã
[8],[17],[18].
Giả thiết chung: Ta luôn coi đối phương biết hệ mã đang dùng. Giả thiết
này được gọi là nguyên lý KoreKhoff. Dĩ nhiên nếu đối phương không biết hệ
mật được dùng thì nhiệm vụ của anh ta sẽ khó khăn hơn nhiều. Tuy nhiên, ta
không muốn độ mật của một hệ thống dựa trên một giả thiết không chắc chắn:
đối phương không biết hệ mật đang sử dụng. Vì vậy, mục tiêu trong việc thiết
kế một hệ mật là phải đạt được độ mật của giả thiết KoreKhoff.
Việc thám mã có thể quy về việc tìm được bản rõ hoặc phát hiện khóa
giải mã, khi biết trước hệ mật mã sử dụng. Ngoài việc biết hệ mật mã, người
thám mã cần có thông tin về bản rõ và một số phát hiện khác. Tuỳ theo thông
tin đó là gì mà ta phân các bài toán thám mã thành 4 loại [2]:
- Bài toán thám mã chỉ biết bản mã: Đây là bài toán phổ biến nhất
- Bài toán thám mã khi biết cặp rõ/mã.
- Bài toán thám mã khi có bản rõ được chọn.
- Bài toán thám mã khi có bản mã được chọn.
9
1.3.1 Bài toán thám mã chỉ biết bản mã
Đây là bài toán phổ biến nhất. Người thám mã chỉ biết các bản mã
c1 ek m1 ,.., ek mi mà không biết bản rõ tương ứng với những bản mã đó cũng
như khóa giải mã. Anh ta cố gắng tìm khóa giải mã, nếu không cần tìm các bản
rõ m1m2 ..mi .
1.3.2 Bài toán thám mã khi các cặp rõ/mã đã biết
Người thám mã biết các bản mã c1c2 ..ci
Như trên, nhưng cũng biết các bản rõ tương ứng m1m2 ..mi . Anh ta cố gắng
tìm khóa giải mã a , nếu không thì cố gắng phỏng đoán bản rõ mi 1 từ bản mã
mới ci1 ek mi1 đã được mã hóa cùng với khóa b .
1.3.3 Bài toán thám mã với bản rõ lựa chọn
Người thám mã được quyền truy nhập tạm thời cơ chế mã hóa, nên có
thể chọn các bản rõ m1m2 ..mi và có được các bản mã tương ứng c1 ek m1 ,
c2 ek m2 ,.., ci ek mi ,
từ đó anh ta sẽ phỏng đoán khóa giải mã a và có thể
tìm được bản rõ mi 1 từ một vài bản mã mới ci1 ek mi1 cũng được mã hóa bởi
khóa lập mã b .
1.3.4 Bài toán thám mã với bản mã lựa chọn
Người thám mã được quyền truy cập tạm thời vào cơ chế giải mã, nên từ
các bản mã c1c2 ..ci anh ta nhận được các bản rõ tương ứng m1m2 ..mi . Từ đó anh
ta phỏng đoán khóa giải mã a và có thể tìm được bản rõ mi 1 từ một vài bản mã
mới ci1 ek mi1 cũng được mã hóa bởi cùng khóa lập mã b .
Trong mỗi trường hợp đối tượng cần phải xác định chính là khóa đã sử
dụng: Rõ ràng bốn mức tấn công (thám mã) trên đã được liệt kê theo độ tăng
dần của sức mạnh tấn công và cách tấn công các bản mã được lựa chọn là thích
hợp đối với hệ mật mã hóa công khai.
1.4 Tấn công hệ mật RSA lợi dụng những lỗ hổng của chúng
10
Tính bảo mật của RSA chủ yếu dựa vào việc giữ bí mật số mũ giải mã a
và các thừa số p, q của n . Tuy nhiên, điều kiện an toàn trên của hệ mật chỉ là
điều kiện chung. Trong thực tế khi thiết kế một giao thức hay một kênh bí mật
có sử dụng hệ mật RSA vẫn tồn tại nhiều sơ hở, những sơ hở đó đã được thám
mã lợi dụng nhằm phá huỷ giao thức, kênh bí mật, phá vỡ tính an toàn của hệ
mật. Trong phần này, sẽ giới thiệu một số sơ hở người thám mã có thể lợi dụng
vào đó để phá vỡ hệ mật RSA [5, 8, 13].
1.4.1 Biết (n) tìm được p, q
Người ta có thể xác định được p, q và ngược lại. Biết được p, q người ta
có thể dễ dàng tính được n .
Nếu biết được n ta có thể tìm được p, q bằng cách giải hệ phương trình:
p.q n
p.q n
( p 1)( q 1) (n)
p q n 1 ( n)
Do đó p, q là nghiệm của phương trình bậc 2:
x 2 n n 1x n 0
Bởi vậy nếu người thám mã biết được n anh ta có thể phân tích được
n và phá được hệ mật.
Ngược lại cho trước p, q rõ ràng việc tính n được thực hiện dễ dàng:
n p 1q 1
1.4.2 Biết số mũ bí mật của RSA
Nếu như biết số mũ giải mã a thì coi như đã làm xong việc thám mã, vì
vậy việc tìm kiếm p, q là không còn ý nghĩa đối với Marvin (người thám mã)
nữa. Tuy nhiên điều này còn có một ý nghĩa quan trọng hơn đó là nếu đối
phương biết a thì ta không chỉ phải thay đổi số mũ giải mã mà còn phải chọn
modul n khác. Vì khi Marvin biết được d, anh ta cũng có thể tính được p, q . Do
đó Marvin sẽ biết cách tìm một khóa bí mật bất kỳ, néu hệ thống vẫn giữ nguyên
modul n p.q .
11
Bây giờ chúng ta sẽ chứng minh rằng: nếu biết số mũ giải a sẽ tìm được
các thừa số p, q của n .
Thật vậy:
Do a.b 1mod n nên a.b 1 e. n k
Do n là một số chẵn nên ta có thể viết k dưới dạng.
k 2t.r với r là số lẻ và t 1 .
Theo định lý ơle: với a : a, n 1 a thì a n 1 . Do đó ta có:
g Z n 1 mod n (do k là bội của n và do đó g 2 là căn bậc hai của 1
k
theo module n .
Theo định lý phần dư Trung Hoa, 1 có 4 căn bậc hai module n p.q . Hai
căn bậc 2 là 1 , hai căn bậc hai là xx 1mod p; x 1mod q, 1 x p . Sử dụng
một trong hai căn bậc hai không tầm thường này sẽ tìm được p, q trong thời
gian đa thức bằng cách tính gcdx 1, n
x 2 1 mod n x 1x 1 1 mod n x 1x 1 : n
(1)
Đặt x 1, n d1 và x 1, n d 2
Vì n p.q và x 1,0 x n nên:
x 1 0 và
0 x 1 n
x 1 0 và
0 x 1 n
Suy ra d1 hoặc d 2 phải khác 1 và do n p.q nên một trong hai giá trị d1 , d 2
chính là p hoặc q .
Ví dụ: Giả sử n 403 13.31 . Bốn căn bậc hai của 1 theo modul 403 là:
1,92,311,402 .
Căn
bậc
hai
92
nhận
được
bằng
cách
giải
hệ
x 1mod13, x 1mod31theo định lý phần dư China. Nếu tìm được nghiệm
không tầm thường này, thì nghiệm không tầm thường kia phải là 403-92=311.
Đó là nghiệm của hệ x 1mod13 và x 1mod31.
12
Giả sử x là căn bậc hai không tầm thường của 1 module n . Khi đó ta có:
n x 1x 1
Nhưng n không là ước của một nhân tử nào ở vế phải. Điều đó kéo theo
gcdx 1, n p hoặc q (và tương tự gcdx 1, p hoặc q ). Tất nhiên có thể tính
ước chung lớn nhất bằng thuật toán Euclidean mà không cần phải phân tích nhâ
tử n. Bởi vậy hiểu biết về căn bậc hai không tầm thường 1 module n sẽ làm cho
việc phân tích n chỉ cần thực hiện trong thời gian đa thức. Yếu tố quan trọng
này là cơ sở của nhiều kết quả trong mật mã.
Trong ví dụ trên, gcd93,403 31 và gcd312 ,403 13
Sau đây là thuật toán phân tích thừa số khi đã biết số mũ giải mã a .
1. Cho w ngẫu nhiên sao cho 1 w n 1
2. Tính x gcdw, n
3. If 1 x n then quit (thanh công: x p hoặc x q )
4. Tính a Ab
5. Viết ab 1 2 s r , với r là số lẻ
6. Tính v wr modn
7. If v 1modn then quit (không thành công)
8. While v 1modn do
9. v0 v
10. v v 2 modn
11. If v0 1mod n then quit (không thành công)
Else
Tính x gcdv0 1, n
(thành công: x p hoặc x q )
Thuật toán có xác suất thành công tối thiểu là 1 2 .
1.4.3 Giao thức công chứng
- Xem thêm -