BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2

HOÀNG THỊ CẨM NGUYÊN

NGHIÊN CỨU MỘT SÓ KĨ THUẬT
TẤN CÔNG HỆ MÃ CÔNG KHAI
VÀ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12

LUẬN VĂN THẠC sĩ TOÁN HỌC

Ngưòi hướng dẫn khoa học: TS. Trần Văn Dũng

Hà Nội, 2015


Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của thầy giáo TS. Trần
Văn Dũng. Sự giúp đỡ và hướng dẫn tận tình, nghiêm túc của thầy trong suốt quá trình thực hiện luận văn đã giúp
tôi trưởng thành hơn rất nhiều trong cách tiếp cận một vấn đề mới. Tôi xin bày tỏ lòng biết ơn, lòng kính trọng sâu
sắc nhất đối với thầy.
Tôi xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm Hà Nội 2, phòng sau đại học và các thầy cô
giáo trong nhà trường đã giúp đỡ tạo điều kiện thuận lợi cho tôi trong suốt quá trình thực tập.
Tôi xin chân thành cảm ơn gia đình, bạn bè đã luôn giúp đỡ động viên và tạo điều kiện thuận lợi để tôi hoàn
thành khóa học Thạc sĩ cũng như hoàn thành luận văn này.
Hà Nội, ngày 10 tháng 12 năm 2015
Tác giả

Hoàng Thị cẩm Nguyên


2.4

Bảo mật là nhu cầu đã xuất hiện từ rất lâu trong đời sống của con

người. Dưới nhu cầu cần thiết này “ Mật mã học” đã ra đòi và phát triển ngày
càng mạnh mẽ. Mật mã học là một lĩnh vực liên quan với các kĩ thuật ngôn ngữ
và toán học để đảm bảo an ninh an toàn thông tin. Mật mã học là một lĩnh vực
liên ngành, được tạo ra từ một số lĩnh vực khác. Các dạng cổ nhất của mật mã
há chủ yếu liên quan đến ngôn ngữ. gần đây thì tầm quan trọng đã thay đổi mật
mã hóa sử dụng và gắn liền nhiều hơn tói toán học cụ thể là toán rời rạc bao
gồm các vấn đề liên quan đến lý thuyết số, lý thuyết thông tin, độ phức tạp tính
toán, thống kê và tổ họp.
2.5

Mã hóa và thám mã là hai mặt của một vấn đề và luôn phát triển

song hành. Cùng với sự phát triển của mật mã, các phương pháp thám mã ngày
càng tinh vi hiệu quả và luôn là thách thức lớn đối với các nhà mật mã.
2.6

Mục tiêu của thám mã là tìm những điểm yếu hoặc không an toàn

trong phương thức mật mã hóa. Thám mã có thể được thực hiện bởi những kẻ
tấn công ác ý, nhằm làm hỏng hệ thống; hoặc bởi những ngưòi thiết kế ra hệ
thống (hoặc những người khác) với ý định đánh giá độ an toàn của hệ thống.
2.7

Cuối thế kỉ XX hệ mật mã khóa công khai được ra đời, nó được

coi như tiến triển làm thay đổi nền tảng cơ bản trong cách làm việc của hệ

2. Mục đích nghiên cứu
2.12

Tổng hợp lại các phương pháp thám mã các mật mã khóa công

khai, từ đó mong muốn người sử dụng sẽ tránh được các lỗi dẫn đến việc mất
an toàn của loại mật mã này.
3. Nhiệm vụ nghiên cứu
-

Nghiên cứu về lý thuyết mật mã.

-

Nghiên cứu các thuật toán mã hóa và thám mã.

-

Nghiên cứu một số phương pháp thám mã và ứng dụng.

4. Đối tuợng nghiên cứu
-

Các khái niệm cơ bản về mật mã.

-

Cơ sở toán học của mã hóa và thám mã.

5. Phuơng pháp nghiên cứu


2.17

Mật mã khóa công khai là một chuyên ngành mật mã học cho

phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các
khóa chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một
cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay
khóa bí mật).
2.18

Trong mật mã học khóa công khai, khóa cá nhân phải được giữ bí

mật trong khi khóa công khai được phổ biến công khai. Trong 2 khóa, một dùng
để mã hóa và khóa còn lại dùng để giải mã. Điều quan trọng đối với hệ thống là
không thể tìm ra khóa bí mật nếu chỉ biết khóa công khai.
1.1 Cơ sở lí thuyết của mật mã khóa công khai
1.1.1
2.19

Số hocModulo

Số học modulo là cơ sở cơ bản cho mật mã học nói chung và RSA nói

riêng. Định nghĩa 7: Cho số nguyên dương N. Chúng ta nói hai số nguyên a và
b đồng dư theo modun N nếu tồn tại số nguyên k sao cho a-b = kN. Chúng ta
miêu tả mối quan hệ này bởi kí hiệu sau :
2.20 a=b mod N
2.21



đó rất cần thiết cho các thuật toán mã công khai.
2.29

Đỉnh nghĩa 4: Cho a là một phần tử của ZN. Phần tử nghịch đảo của a

theo raodulo N là số nguyên X thỏa mãn:
2.30 ax = 1 mod N
2.31

phần tử nghịch đảo của a kí hiệu : a~l mod N.

2.32

Điều quan trọng cần lưu ý ở đây là ứf1 mod N tồn tại khi và chỉ khi

a và N nguyên tố cùng nhau, tức là ước chung lớn nhất của chúng bằng 1:
2.33 gcd(a,A0 = l.
2.34

Thật vậy, theo thuật toán Euclid mở rộng thì ta có (a, N)=l khi và

chỉ khi tồn tại các giá trị nguyên X, y sao cho: xa + yN = 1. Do đó ta có : ax = 1
mod N <=> ax-l = kN <=> ax-kN = 1 Nếu (a,N) ^ 1 thì sẽ không có nghiệm
nguyên X, k cho phương trình này, do đó không có nghịch đảo của a theo
moảN.
2.35

Một thủ tục rất quan trọng cho các thuật toán mã công khai về



Độ phức tạp của thuật toán là 0(m) = ơ(log(e)).

2.43

Định nghĩa 5: Cho số nguyên a và số nguyên N sao cho (a, N) = 1, bậc

của a theo modulo N, được kí hiệu oN (a), là số nguyên dương k nhỏ nhất sao
cho:
2.44 ak = 1 mod N
2.45

Đinh nghĩa 6: Cho số nguyên q và số nguyên n, ta nói q là đồng dư bậc 2

theo modulo n, nếu tồn tại số nguyên X sao cho:
2.46 X2 = q mod n
1.1.2

Định lí Fermat nhỏ
2.47 ap l mod /7 = 1

2.48

trong đó, p là số nguyên tố và a là số nguyên bất kỳ khác bội của p, tức là

gcd(ữ, p) = 1 , hay với mọi số nguyên tố p và số nguyên a không là bội của p, ta
luôn có
2.49 ap =a mod p



nhiên các số a.
1.1.3
2.56

Định lí phần dư Trung Hoa • Tính toán theo moduỉo số lớn:
Đe tính A mod M, với M khá lớn và A là biểu thức số học nào đó.

Trước hết ta cần tính tất cả dị = Amoáníị. Sau đó sử dụng công thức:
2.57 f k \
2.58 A = atct modM
2.59

Trong đó: M =M / m
2.60

2.61

C1 = Mi.(Ml 1 modmi) với \ < i < k

Vỉ du 2.'Tính 178 mod77 . Áp dụng định lý phần dư Trung Hoa, ta coi A =

1718,mj =7,m2 =11 . Khi đó M1 -11 ,M2 -7 và 11^mod7 = 4 1 mod7 = 2, suy ra Cj
—11.2 — 22 7 1 modi 1 = 8, suy ra c2 - 7.8 = 56 a} = 178 mod 7 = (17 mod7)8
mod 7 = 38 mod 7 = 2


2.62

a2 = 178 modl 1 = (17modl l)8 modl 1 = 68 modl 1 = 4 Vậy 178



2.77

x = an mod pn
2.74

M

i= 1

Pi

2>* 0

=
2.76

Bất kì nghiệm nguyên X nào khác của hệ phương trình đều thỏa mãn:
2.78

JC = JC0 modM

2.79

Ví dụ 3: Cho X = 2mod3, jc = 3mod5, JC = 9modll

2.80

Ta có: ^.5.11 = lmod3 =^> yv 1 = lmod3 =^> yỉ = 1
2.81 y2.3.11 = lmod5 =^> y2.3 = lmod5 =^> y2 =2

í,
0
(
,
1>
L 0 2.10
2.6
2.7
2.8
2.12
2.13
2.15
2.11
2.14
l Pl)
l Pr)
2.16 l Plj
2.85
2.86

Đinh lí Euler: Cho n là số nguyên dương, và a là số nguyên tố cùng nhau

với n, thì ta có:
2.87 aậ(n) =1 modn
2.88

Chứng minh: Gọi là các số nguyên dương

nhỏ hơn n và
2.89


Có phương pháp khác, mà ta sẽ xét ở đây, sử dụng các phép kiểm

tra tính nguyên tố thống kê dựa trên các tính chất:
• Mà mọi số nguyên tố phải thỏa mãn;
• Nhưng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn
tính chất đó.
2.94

Cụ thể là phép kiểm tra dựa trên định lý Ferma như sau: nếu số n

cần kiểm tra là số nguyên tố, thì nó sẽ thỏa mãn định lý Ferma đối với mọi số a
nhỏ hon nó an l mod« = 1 . Như vậy, lấy ngẫu nhiên số a và kiểm tra xem nó có
tính chất trên không. Nếu có thì n có thể là số nguyên tố, nếu cần độ tin cậy lớn
hon, thì ta kiểm tra liên tiếp nhiều lần như vậy với các số ngẫu nhiên a được
chọn. Sau mỗi lần qua được phép thử, xác suất để n là số nguyên tố lại tăng lên.
Chú ý rằng
• nếu ừ modn = 1, thì b2i modn = l2 modn = 1
• nếu ừ modn = n -1, thì b2i mod« = (n-1)2 modra = n2
-2n + lmodn = l
2.95

Kiểm tra số n có là số nguyên tố không, ta chỉ cần xét n là lẻ, khi

đó « — 1 là chẵn và biểu diễn nó dạng: n-ì = 2k.q
2.96

Khi đó để tính an 1 , ta tính aq, sau đó bình phương liên tiếp k lần.

Cụ thể thuật toán thể hiện ở phần sau.

31
31
31
10+ì
2.113 Và được viết ngắn gọn là [0; 2,1,10,3].
2.114 Đinh lí h Choe,N,t,d là số nguyên với gcd(e,N) = 1, gcd(t,d) =1 và
2.115 e t 1
~N~~d \.
2.118 Bài toán này có liên hệ mật thiết với các bài toán kiểm tra tính
nguyên tố của một số nguyên, nhưng với những gì mà ta biết đến nay, nó dường
như khó hơn nhiều so với bài toán kiểm tra tính nguyên tố.
1.2.2

Bài toán thặng dư bậc hai

2.119 Đinh nghĩa8: Ký hiệu Legendre được định nghĩa như sau:
2.120 Nếu p là số nguyên tố lẻ và a là một số tự nhiên thì kí hiệu là:
Legendre
• 0 nếu p chia hết cho a;
• 1 nếu a là thặng dư bậc hai theo mod p • —1 nếu a không là thặng dư bậc
2 theo mod p
2.121 Đinh nghĩa9: Ký hiệu Jacobi được định nghĩa như sau:

d p. Như vậy,

trong trường hợp này bài toán thặng dư bậc hai
2.127 có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên.
Mặt khác, nếu không biết cách phân tích n thành thừa số nguyên tố thì cho đến
nay, không có cách nào giải được bài toán thặng dư bậc hai trong thời gian đa
thức. Điều đó củng cố niềm tin rằng bài toán thặng dư bậc hai và bài toán phân
tích số nguyên tố là có độ khó tương đương nhau.
1.2.3

Bài toán úm căn bậc hai mod n

2.128 Cho một số nguyên lẻ n là họp số Blum và một số a e Qn, tức a là
một thặng dư bậc hai theo mod n. Hãy tìm một căn bậc hai của a theo mod n, tức
là tìm X sao cho X2 = a mod n.


2.129 Nếu phân tích được n thành thừa số nguyên tố n=pq, thì bằng cách
giải các phương trình X2 = a mod p và X2 = a mod q, rồi sau đó kết họp nghiệm
của chúng lại theo định lý số dư Trung Hoa ta sẽ được nghiệm của phương trình
X2 = a mod n. Người ta đã tìm được một số thuật toán tương đối đơn giản (giải

thuật trong thời gian đa thức) để giải phương trình X2 = a mod pvói p là số
nguyên tố. Như vậy, bài toán tìm căn bậc hai theo mod n có thể quy dẫn trong
thời gian đa thức về bài toán phân tích số nguyên. Ngược lại, nếu có thuật toán
A giải bài toán tìm căn bậc hai theo mod n thì cũng có thể xây dựng một thuật
toán giải bài toán phân tích số nguyên như sau: Chọn ngẫu nhiên một so X với
gcdịx, n)=l và tính a = X2 mod n. Dùng thuật toán A cho a để tìm một căn bậc
hai mod n của a. Gọi căn bậc hai tìm được là y. nếu y = ±x mod n thì phép thử
coi như thất bại, còn nếu ngược lại, thì gcd (x-y, n) chắc chắn là một ước số

-

Định lí phần dư Trung Hoa

-

Hàm ệ Euler

-

Kiểm tra tính nguyên tố

-

Phân số tiếp diễn
2.136 Trong mục các bài toán khó liên quan đến hệ mật mã khóa công

khai tôi đã trình bày các bài toán sau:
-

Bài toán phân tích số nguyên thành thừa số nguyên tố

-

Bài toán thặng dư bậc hai

-

Bài toán tìm căn bậc hai mod n


2.144 Ta xem xét hệ mật mã RSA là một bộ < N, M, c, K, E, D >ở đó:
2.145 N =pq - modun công khai, kết quả của hai số nguyên tố khác nhau
p, q M - tập các bản rõ. M =ZN
2.146 c tập các bản mã. c = ZN.
2.147 K- là một bộ < p, q, e, d >ở đó (d,ệ(N)) =1 và ed = 1 mod ệ(N)
2.148 Kr =<e, N > là khóa công
khai Kp =< p, q, d, N > là khóa bí
mật
2.149 E - hàm lập mã: E:M —>c, c = E(m\Kr) = me mod N D - hàm giải
mã: D:C —» M, m = E(cịKp) = cd mod N
2.150

e\ầd được gọi tương ứng là số mũ công khai và số mũ bí mật. số

mũ này thỏa mãn phương trình ed -1 = kệ(N), do đó nó được gọi là phương trình
khóa.


2.1.2

Khởi tao khóa RSA

2.151 Mỗi người sử dụng A tạo một cặp khóa công khai - riêng như sau:
1. Đưa ra hai số nguyên tố lớn p,q.
2. Tính N = pqvầ ệ(N) = (p-1 )(q -1).
3. Chọn e: (e,ệ(N)) = 1 và tính d = e~l mod Ộ(N). Để chọn được ethỏa mã
điều kiện đó thì ta chỉ cần chọn một số nguyên tố e ' > max {p, q}.
2.152

Chú ý: vai trò của evàdcó thể thay đổi cho nhau, tức là có thể lẩy

ậ(N) = (p -l)(q -1) = 16.40 = 640. Anh ấy chọn e = 33 có (33,640) = 1 . Sau đó
Bob tính d = e“1(mod^(A0) = 33“1mod640 = 97. Bob công bố « = 697 \àe = 33.
2.160 Alice muốn sử dụng khóa công khai của Bob để mã hóa thông điệp gửi
cho Bob:
-

Cho mẩu tin M = 207 ( thỏa mãn điều kiện 207 < 697)


-

Mã c = 207e mod n = 20733 mod 697 = 156

2.161 Alice gửi số 156 cho Bob. Từ số 156 là rất khó để cho bất kì ai xác định
được số 207.
2.162 Bob nhận được số 156 và tính M = 156d mod« = 15697 mod697 = 207.
2.163

• Cách sử dụng định lý phần dư Trung Hoa để giải mã cho nhanh

như sau:
2.164 Tính 15697 mod 17 = 397 modl7 = (38)12.3modl7 = (-l)12.3modl7 = 3
15697 mod 41 = 3397 mod41 = (334)24.33mod41 = (-4)24.3 3

2.165

mod 41 = 106.33mod41 = 2
2.166 Tính 411 modl7 = 7 1 modl7 = 5 suy ra q = 41.5 = 205
17 1 mod 41 = 29 suy ra c2 - 29.17 = 493
2.167 Vậy M = (493.2 + 205.3) mod697 = 207 .

2.172 Hiện tại tin rằng tất cả các bài toán trên đều tương đương với bài toán
phân tích một số ra thừa số.
-

Có các bước tiến chậm theo thời gian;

-

Hiện tại cho rằng RSA 1024 hoặc 2048 là an toàn.

2.173 Tấn công thời gian:
-

Được phát triển vào giữa năm 1990;

-

Paul Kocher chỉ ra rằng kẻ thám mã có thể xác định được khóa riêng nếu
theo dõi thời gian máy tính cần để giải mã các bản tin.

-

Tấn công thời gian không chỉ áp dụng cho RSA, mà cả với các hệ mã
công khai khác.

-

Tấn công thời gian giống như kẻ cưóp đoán số điện thoại bằng cách quan
sát một người nào đó trong bao lâu chuyển quay điện thoại từ số này sang
số khác.



• Không thể dùng để trao đổi mẩu tin bất kỳ.
• Tuy nhiên nó có thể thiết lập khóa chung.
• Chỉ có hai đối tác biết đến.
• Giá khóa phụ thuộc vào các đối tác (và các thông tin về khóa công khai
và khóa riêng của họ).
• Dựa trên phép toán lũy thừa trong trường hữu hạn (chẳng hạn, modulo
theo số nguyên tố) là bài toán dễ.
• Độ an toàn dựa trên độ khó của bài toán tính logarit rời rạc (giống bài
toán phân tích ra thừa số) là bài toán khó.
2.2.2
-

Khởi tạo Dỉffie - Hellman

Mọi người dùng thỏa thuận tham số chung:

• Số nguyên tố rất lớn p.
• a là căn nguyên thủy của mod q.
-

Mỗi người dùng ( A chẳng hạn) tạo khóa riêng của mình:

• Chọn một số X A làm khóa mật (số) của A: xA
2.186

Tính khóa phiên chung:

2.187 KAB = yBXA mod353 = 24897 = 160(Alice)
2.188 KAB = yAXa mod353 = 40233 =160(Bob).
2.3 Xác thưc mẩu tin
2.3.1

Xác thưc

mẩu tin Các khái
niệm
2.189 Xác thực mẩu tin (thông điệp) liên quan đến các khía cạnh sau, khi
truyền tin trên mạng:
-

Bảo vệ tính toàn vẹn của mẩu tin: bảo vệ mẩu tin không bị thay đổi hoặc
có các biện pháp phát hiện nếu mẩu tin bị thay đổi trên đường truyền.

-

Kiểm chứng danh tính và nguồn gốc: xem xét mẩu tin có đúng do người