ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHÊ
Nguyễn Thị Phương Liên
NGIỈIÊN CỨU NHỮNG PHƯƠNG PHÁP
TẤN CÔNG GIAO THỨC YÉU s ử DỤNG
HỆ MẬT MÃ KHOÁ CÔNG KHAI
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã sổ: 1.01.10
LUẬN VĂN THẠC sĩ
NGƯỜI HƯỚNG DẢN KHOA HỌC:
TS. NGUYỄN NGỌC CƯƠNG
Hà Nội - 2003
*■ : : :
V'U?/J31
Trang 2
2.2.5 Giao thức modal chung và các phương pháp tẩn công 25
2.2.6 Giao thức số mũ công khai nhỏ

.
31
2.2.7 Giao thức sổ m ũ bí mật n h o.

33
2.2.8 Giao thức entropy thấp

.
36
2.2.9 Giao thức khoủ đổi xứng 38

3.3.4 Phép trừ 50
3.3.5 Phép nhân
.

.

50
3.3.6 Phép chia
5 ì
3.3.7 Luỹ thừa
.

52
3.3.8 Ước số chung lớn nhất 53
3.3.9 Phép tỉnh nhân theo moduỉ p 54
3.3.10 Phép tính luỹ thừa theo moduỉ p

54
3.3.1 Ị Tìm phần tử nghịch đảo theo moduì p 55
3.3. ỉ 2 Phép cộng có dấu 56
3.3.13 Phép trừ có dấu

.
57
3.3. ì 4 Phép nhân có dấu
.
57

máy tính trở nên phổ biến, các dịch vụ thư tín điện tử, thương mại điện tử,
giao dịch tiền tệ., trên mạng phát triển, và những cơ sở dữ liệu khổng lồ chứa
các thông tin riêng tư được ỉưu giữ trong nhừng chiếc máv tính kết nối mạng
thì việc sử dụng mật mã để đảm bảo an toàn mạng, báo mật và xác thực dữ
liệu đã được phổ biến rộng rãi trong xã hội,
Từ cuối những năm 70, các nhà lập mã đà phát triển các hệ mật mã có
độ mật được bảo đảm bằng độ phức tạp tính toán. Những thuật toán mật mã
này yêu cầu khả năng tính toán phức tạp khi tấn công và được thiết kế để
chống lại sự tấn công của các đối thủ có thời gian giới hạn. Ý tưởng cơ bản ià
xây dựng những hệ thống sao cho biết phần khoá lập mã và thuật toán lập mã
vẫn rất khó tìm được cách giải mã và thường là khó tìm được phần khoá giải
mã. Phần khoá lập mã và phần khoá giải mà khác nhau, trong đó phần khoá
lập mã là công khai, phần khoá giải mã là bí mật. Và hệ thống này được gọi là
hệ mật mã khoá công khai, ví dụ như hệ mật mã RSA, Rabin, ElGamal,
Khi một thuật toán mật mã được sử dụng để bảo mật hay xác thực dữ
liệu, nó sẽ nằm trong khuôn khố một giao thức xác định, thích hợp để xử lý
dừ liệu. Chính vì vậy, từ khi hệ mật mã khoố công khai ra đời đã có rất nhiều
giao thức được thiết kế đế nâne cao độ tin cậy và xác thực. Mục đích của giao
Trang 5
thức là đàm bao thuật toán mật mà sê thực sự cung cấp sự báo mật hay xác
thực mà hệ thống yêu cầu.
Có nhiều giao thức đứng vừng và được đánh giá tôt sau một khoáng
thời gian dài sử dụng như giao thức X.509, Kerberos Tuy nhiên cũng có
nhiều giao thức nhanh chóng bộc lộ nhược điếm và bị tấn công mặc dù thuật
toán mật mã sử dụng trone, đó được đánh giá là tốt. Vì vậy việc đánh giá độ
an toàn cúa giao thức là rất quan trọng. Độ an loàn của giao thức không chỉ
phụ thuộc vào thuật toán mật mã mà còn phụ thuộc vào việc thiết kể giao thức
và cho đến nay đã có một số chuyên ngành ra đời đê nghiên cứu về độ an toàn
của giao thức chẳng hạn Logic BAN, chứng minh tri thức không V.V
về mặt thực tiễn, chúng ta cũng biết rằng trong nhiều mạng máy tính

CÔNG KHAI RSA có MODUL CHUNG
Phụ lục là các chương trình mô phỏng phương pháp tấn công giao thức
sứ dụng hệ mật mã khoá công khai RSA có modul chunR.
Cuối cùng, tôi xin chân thành cảm ơn thầy giáo hướng dẫn TS. Nguyễn
Ngọc Cương, người đã trực tiếp hướng dẫn tôi viết luận văn thạc sĩ này. Tôi
cũng xin chân thành cảm ơn tất cả các thầv cô trong khoa Công nghệ thông
tin, Viện Công nghệ thông tin đã trang bị cho tôi nhùng kiến thức cơ bản đế
tôi có thế hoàn thành được luận văn. Xin chân thành cảm ơn các bạn bè, đồng
nghiệp, những người đã có rất nhiều ý kiến đóng góp, giúp đờ tôi trong quá
trình làm luận văn. Và tôi xin bày to lòng biết ơn đến nhừng naười thân trong
gia đình đã luôn dành cho tôi sự quan tâm và động viên.
Trang 7
CHƯƠNG 1 - HỆ MẬT MẢ KHOÁ CỒNG KHAI
Trong mô hình mật mã cổ điển, người gửi và người nhận cùng chọn
một khoá K bí mật, sau đó dùng K đê tạo thuật toán lập mã eK và thuật toán
giái mã clK. Các hệ mật thuộc loại này còn được gọi là các hệ mật khoá bí mật
vì việc đế lộ eK sẽ làm cho hệ thong mất an toàn. Nhược điêm cùa hệ mật này
là nó yêu cầu phải có thông tin trước về khoá K giữa người gửi và người nhận
qua một kênh an toàn trước khi gửi một bản mã bất kỳ.
Chính vì vậy, náy sinh V tướng xây dựng một hệ mật mã sao cho biết
dược phần công khai của khoá K và thuật toán lập mã ÜK vẫn rất khó giải mã,
và ihường là khó tìm được phần khoá giải mã K dù thuật toán giải mã có thể
dược biết.
Từ cuối những năm 70, các nhà lập mã đà phát triển các hệ mật mã có
độ mật được bảo đảm bàng độ phức tạp tính toán. Nhừna, thuật toán mật mã
này yêu cầu khả năng tính toán phức tạp khi tấn công và được thiết kế để
chống lại sự tấn công của các đối thú có thời gian giới hạn. Trong các hệ mật
mã này, phần khoá lập mã và phần khoá giải mã khác nhau, trong đó phần
khoá lập mã, thuật toán lập mã, thuật toán giải mã là công khai còn phần khoá
giải mã là bí mật. Và hệ thống này được gọi là hệ mật mã khoá công khai.

thường được sir dụng trong các ứne. dụng cần sự bảo đám an toàn và bảo mật
dữ liệu số.
1.1.1 Mô tả hệ mật RSA
Trước tiên, ta hãy nhắc lại định nghĩa hệ mật.
Một hệ mật là một bộ 5 (p, c - K £, $) thoả màn các điều kiện sau:
1 . plà một tập hữu hạn các bàn rõ có thể.
2 . c\ằ tập hữu hạn các bản mã có thể.
3. .^(không gian khoá) là tập hữu hạn các khoá có thể.
4. Đối với mồi K e J(cò một quy tắc mà eK: p~> ỚVà một quy tắc giải
mà tương ứng dK e 'ĩò. Mồi eK: p c và dK: c -> p\à những hàm mà
dis(eK(x)) = X với mọi bản rõ X G p.
1.1. HỆ MẬ T MÃ RSA
Tra nụ 10
Hệ mật mà RSA[5] sừ dụng các tính toán t r o n g z,„ trong đó n là tích
của hai số nguyên tố phân biệt p, q và (ị)(n) = (p-1 )(q-l ). Mô tả hình thức của
hệ mật này như sau:
Cho n = p.q trong đó p và q là các số nguyên tố khác nhau.
Đặt p= c= zn và định nghĩa J(= {(n,p,q,a,b): ab = l(modệ(n))}
Với K = (n,p,q,a,b) ta xác định:
eK(x) = xb mod n
và dK(y) = y*1 modn
trong đó (x, y e z„).
Các giá trị n, b công khai còn các giá trị p, q, a giữ bí mật.
Ta hãy kiếm tra xem các phép mã 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 = l(mod<Ị)(n)) nên ta có ab = t.ệ(n) + 1 với một số nguyên t > 1
nào đó. Giả sử X € zn ;
a. Trường hợp (x,n) =1 —> x^'1’ mod n = 1.
Khi đó ta có: ya modn = (xb)a mod n = xlệ(n)+l mod n
= ((xộ<n) mod n)' ).x mod n

Bởi vậy, số
1
Ĩ
1
Ũ bí mật đề giải mã cùa Bob là a — 6597.
Bob sẽ công bổ n = 11413 và b = 3533 trong một danh bạ khoá công
khai.
Bây giờ, giả sử Alice muốn gửi bản rõ X = 9726 tới Bob. Cô ta sẽ tính:
9 7 2 6 3533 mod 11413 = 5761
rồi gửi bản mã 5761 trên kênh.
Khi Bob nhận được bản mã 5761, anh ta sứ dụng số IĨ1Ũ bí mật a đê tính
ra x:
57616597mod 11413 = 9726.
1.1.3 Đô an toàn của hê RSA
• •
Độ an toàn cúa hệ RSA được dựa trên eiá thiết là hàm mã Ck(x) = xb
mod n là hàm một chiều. Bởi vậy thám mã sẽ khôna, có khả năng về mặt tính
toán để giải mã được một bản mã. Cửa sập cho phép Bob giải mã được chính
là thông tin về phép phân tích thừa sổ n (n=p.q). Vì Bob biết phân tích này,
anh ta có thế tính ệ(n) = (p-l).(q-l) và rồi tính số mũ giải mã a bằng cách sử
dụng thuật toán Euclide mở rộng.
Trang 13
Cách tấn công dề thấy nhất đối với hệ mật này là thám mã cô găng
phân tích n ra các thừa số nguyên tố. Nếu thực hiện được phép phân tích này
thì có thể dễ dàng tính được ệ(n) = (p-1 ).(q-l) rồi tính số mủ a từ b đúng như
Bob làm.
Vì thế để hệ RSA được coi là an toàn thì nhất thiết n = p.q phái là một
số du lớn để việc phân tích nó sẽ không có kha năng về mặt tính toán. Các
thuật toán phân tích hiện thời có khả nâng phân tích các số tới 130 chữ số
thập phân. Vì vậy đế đảm báo an toàn nên chọn các số p và q có khoảng 100

y
2
) = y2(yiay' mod p
Hệ mật Elgamaỉ là một hệ mật không tất định vì bàn mã phụ thuộc vào
cả bán mã X lẫn giá trị ngầu nhién k do Alice chọn. Bởi vậy, sẽ có nhiều bản
mà được mã từ cùng bản rõ.
Dề thử lại rằng dK(y I, y2) - x- số ngầu nhiên k do người lập mã tự chọn
và không cần thông báo dưới bất kỳ dạng nào cho người nhận, tuy nhiên nó là
cần thiết và cần được giữ kín để bảo mật dối với ncười thám mã.
Trang 15
1.2.2 Thực thi hệ Elgamal
Bản rõ X được che dấu bàng cách nhân X với |3k đế tạo ra y2. Giá trị yi =
«k cùng được gừi đi như một phần cua ban mà. Bob là người biết số mù bí
mật a có thể tính được ị3k từ otk. Sau đó anh ta sẽ
tính ra X bàng cách nhân y2
với p'k đế thu được X.
Ví dụ:
Cho p = 2579, a = 2, a = 765. Khi đó:
p = 2765 mod 2579 = 949.
Bây giờ giả sứ Alice muốn gửi thông báo X = 1299 tới Bob. Giả sử số
ngầu nhiên k mà cô chọn là k = 853. Sau đó cô ta tính:
y, = 2853 mod 2579 = 435
và y2 = 1299 X 949853 mod 2579 = 2396.
Khi Bob thu được bán mã y = (435,2396), anh ta tính:
X = 2396 X (435765)*1 mod 2579 = 1299
Đó chính là bản rõ mà Alice đã mã hoá.
1.2.3 Độ an toàn của hệ Elgamal
Hệ mật Elgamal được xây dựng trên bài toán logarit rời rạc. Lợi thế của
bài toán logarit rời rạc trong xây dựng hệ mật là khó tìm được các logarit rời
rạc, song bài toán ngược lấy luỹ thừa lại có thế tính toán hiệu quá theo thuật

5 = (x - ay). k' 1 mod(p-l )
r
Trang 18
CH ƯƠNG 2 - NGHIÊN cửu CÁC PHƯƠNG PHÁP TẤN CÔNG GIAO
THỨC YÉU
Khi một thuật toán mật mã được sứ dụng đê bao mật hay xác thực dữ
liệu, nó sè nằm trong khuôn khồ một giao thức xác định, thích hợp đê xứ ỉý
dừ liệu. Chính vì vậy, từ khi hệ mật mã khoá công khai ra đời đã có rất nhiều
giao thức được thiết kế đề nâng cao độ tin cậy và xác thực. Mục đích của giao
thức là đảm bảo thuật toán mật mã sẽ thực sự cung cấp sự bảo mật hay xác
thực mà hệ thống yêu cầu. Trong chương này chúng ta sè nghiên cứu một số
uiao thức không đạt được những mục đích như vậy mà nguyên nhân không
phái là do sử dụng thuật toán mã hoá yếu mà vì nhìrng thiếu sót trong việc
thiết kể giao thức. Những chỉ dẫn đế phát triển các giao thức tốt cũng được rút
ra từ việc phân tích những sai sót này.
Trước khi đi vào nội dung chính, chúng ta hãy xem xét các kiểu tấn
công mật mã cơ bán.
2.1 CÁC KIẺƯ TẤN CÔNG THÁM MẢ
Phẩn này sẽ Irình bày một vài kiểu thám mã. Giả thiết chung ở đây là
luôn coi đổi phương biết hệ mật đang dùne. Giả thiết nàv được gọi là nguyên
lý Kerekhoff[5]. 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.Tuy nhiên ta khôno, muốn độ mật của
một hệ mật lại dựa trên một giả thiết không chắc chắn là đối phương không
Trang 19
biết hệ mật được sử dụng. Do đó, mục tiêu trong việc thiết kế một hệ mật là
phải đạt được độ mật dưới giả thiết Kerekhoff.
Việc thám mà có thê quy về việc tìm được ban rõ hoặc phát hiện khoá
mã, khi biết trước hệ mật mã được dùng. Ngoài việc biết hệ mật mã, người
thám mà còn cần có thông tin khác đê tim ban rõ và phát hiện khoá. Tuỳ theo
thông tin dó là gì mà ta phân các bài toán thám mà thành các loại: chỉ biết bản

hợp đối với hệ mật mã khoá công khai.
2.1.4 Tấn công ban mã lụa chọn
2.2 NGHIÊN CỨU CÁC PHƯƠNG PHÁP TẤN CÔNG GIAO THỨC YÉU
2.2.1 Một số sơ suất dẫn đến tấn công hệ RSA
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. Ta thử xét một vài trường hợp xâm phạm tới các
yếu tố bí mật đó.
a. Biết ệ(n) tìm được p và (Ị
Biết ộ(n) thì có thể tính p, q theo hệ phương trình:
p.q = n
p.q = n
p + q = n + 1 - ộ(n)
Do đó p và q là nghiệm của phương trình bậc hai:
X2 - (n- <j)(n) + 1 )x + n = 0
'I’rang 2 1
Bới vậy nếu thám mã biết được ộ(n), anh ta có thế phân tích được n và
phá được hệ mật.
b. Biết số mũ giai mã tì
Nếu biết số mũ giải mã a thì coi như đã làm xong việc thám mã, nên
việc tìm được p, q cùng không còn ý nghĩa đối với việc thám mã nữa. Tuy
nhiên, điều này có một ý nghĩa quan trọng hơn đó là nếu đối phương biết a thì
khônç chỉ phải thay số mù giải mã khác mà còn phái chọn modul n khác, vì
khi đó đối phương cùng có thề biết p, q, do dó biết cách tìm khoá giải mã a
bất kỳ, nếu khoá lập mã vẫn giữ modul n, n^p.q.
Ta sè chứng minh rằng biết số 1Ĩ1Ũ giải mã a sẽ tim được các thừa sổ p,
q của n.
Do a.b = 1 mod <Ị)(n) nên a.b - 1 = l.ộ(n) = k.
Do ộ(n) là một số chẵn nên ta có thể viết k dưới dạne k = 2l.r (với r là
số lé) và t > 1.
Theo định lý ơle: với Va mà (a,n)=l thì aíp,nl modn = 1, do đó, ta có:

Khi a bị lộ thì Oscar dễ dàng giả mạo chừ ký.
1 rang 23
b. Ngirờì sử dụng (ỉùng một số k ngẫu nhiên đế ký hai thông báo khác nhau
Nếu người sử dụng dùng cùng một số k đê ký hai thông báo khác nhau
sẽ tạo thuận lợi cho Oscar tính a. Trước hết, ta có:
Yi = Ĩ2 - Y = a k modp
Giả sử (y,ỗ|) là chừ ký trên X| và (y,Õ2) là chừ ký trên x2. Khi đó ta có:
ồ| = (X| - ay)k‘' mod (p-1)
ỏ2 = (X2 - ay)k'' mod (p-1)
Từ đây suy ra phương trình:
X| - x2 = k(ô| - ỗ2) mod (p-l)
h a y (ô ) - ô ? )k = (X | - x 2) m o d ( p - 1 )
Phương trình này có nghiệm vì k đã được dùng để thiết lập nên nó.
Việc giải phương trình này đã được biết. Ký hiệu d = (ô| - 62, p-1). Phương
trình này có d nghiệm k|, kt|.
Trong d giá trị có thê này, Oscar có thể xác định được một giá trị đúng
duy nhất qua việc kiểm tra điều kiện Y = a k modp.
2.2.4 Giao thức công chứng
Giao thức công chứng là giao thức được thiết kế cho phép một văn bản
sau khi A ký, người khác có the xác thực được rằng văn bản này thực sự được
ký bởi A (nó giống như việc công chứng viên ký chừ ký của mình lên bản
công chứng nên người ta gọi nó là giao thức công chửng).
Trang 24
Đề thiết lập giao thức công chúng, A phai chọn các tham số RSA: các
số nguyên tố p, q và các số ỈĨ1Ũ mã hoá e và giải mã d thoả mãn: e.d=l mocỉ
<Ị)(n), tronR đó n = p.q. Các giá trị n, e là công khai, còn p, q và d được A giữ
bí mật.
Đè ký một văn bán M, A sứ dụng số mũ bí mật d đê tính chừ ký: s =
vr' mod n. Bất cứ ai cũng có thế sứ dụng nhừng thông tin công khai của A đế
kiém thử xem s có thực sự là chừ ký của A trên M hay không bằng cách tính

Tình huống dẫn đến việc sử dụng RSA có sổ modul chung xảy ra như
sau: khi trong hệ thống có k người đăng ký sử dụng RSA, để việc quán lý -
phân phối khoá được đơn giản, trung tâm sẽ sinh ra 2 sổ nguyên tổ p, q; tính
sô modul n = p.q; sinh ra các cặp khoá mã hoá/giải mã {ej, dị} sau đó cấp cho
người đăng ký thứ i trong hệ thống khoá bí mật dj tương ứng, cùng các thông
tin công khai bao gồm số modul n và một danh sách đầy đủ khoá công khai
{ei} (i=l k).
Bât kỳ người nào có thông tin công khai này đều có thể mã hoá văn bản
M đê g ử i cho người đăng ký thứ i bằng cách sư đụne thuật toán mã hoá RSA
với khoá mã eL: Y - Me> mod n rồi gửi Y Hoặc người dăng ký thứ i có thể ký