ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LÊ CÔNG TUẤN ANH
CÁC PHƯƠNG PHÁP TẤN CÔNG CHỮ KÝ SỐ:
RSA,ELGAMAL,DSS
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2016
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LÊ CÔNG TUẤN ANH
CÁC PHƯƠNG PHÁP TẤN CÔNG CHỮ KÝ SỐ:
RSA,ELGAMAL,DSS
Ngành: Công nghệ Thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS TRỊNH NHẬT TIẾN
Hà Nội – 2016
1
LỜI CẢM ƠN
Tôi xin được gửi lời cảm ơn sâu sắc tới PGS.TS Trịnh Nhật Tiến, Trường
Đại học Công nghệ – Đại học Quốc gia Hà Nội, người thầy đã dành nhiều thời
gian tận tình chỉ bảo, hướng dẫn, giúp đỡ tôi trong suốt quá trình tìm hiểu và
nghiên cứu.Thầy cũng là người đ nh hướng và đưa ra nhiều góp ý quý báu trong
suốt quá trình tôi th c hiện luận v n.
Tôi xin chân thành cảm ơn các thầy, cô ở khoa Công nghệ thông tin – Trường
Đại học Công nghệ – ĐHQGHN đã cung cấp cho tôi những kiến thức và tạo cho tôi
những điều kiện thuận lợi trong suốt quá trình tôi học tập tại trường.
Tôi xin cảm ơn gia đình, người thân và bạn bè luôn động viên và tạo mọi điều
kiện tốt nhất cho tôi.
Tôi xin chân thành cảm ơn!
Hà Nội, tháng 10 năm 2016
Họ và tên
Lê Công Tuấn Anh
2
LỜI CAM ĐOAN
Tôi xin cam đoan đây là đề tài do tôi nghiên cứu, th c hiện dưới s hướng dẫn
của PGS.TS Trịnh Nhật Tiến.
Trong toàn bộ nội dung nghiên cứu của luận v n, các vấn đề được trình bày đều
là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các
nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp.
Hà Nội, tháng 10 năm 2016
Họ và tên
Lê Công Tuấn Anh
3
MỤC LỤC
LỜI CẢM ƠN ………………………………………………………………………………………………….. 1
LỜI CAM ĐOAN
……………………………………………………………………………………………… 2
MỤC LỤC
……………………………………………………………………………………………………….. 3
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ………………………………………………. 5
DANH MỤC CÁC BẢNG …………………………………………………………………………………. 6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
………………………………………………………………… 7
MỞ ĐẦU
…………………………………………………………………………………………………………. 8
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN …………………………………………………………. 9
1.1. Một số khái niệm trong số học
……………………………………………………………………. 9
1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất
……………………………………………… 9
1.1.2. Quan hệ đồng dư ………………………………………………………………………………… 9
1.1.3. Số nguyên tố
…………………………………………………………………………………….. 10
1.2. Một số khái niệm trong đại số
…………………………………………………………………… 12
1.2.1. Cấu trúc nhóm …………………………………………………………………………………. 12
1.2.2. Nhóm Cyclic ……………………………………………………………………………………. 13
1.2.3. Nhóm Zn
* ………………………………………………………………………………………… 13
1.3. Độ phức tạp của thuật toán ………………………………………………………………………. 15
1.3.1. Khái niệm độ phức tạp của thuật toán …………………………………………………… 15
1.3.2. Phân lớp bài toán theo độ phức tạp ………………………………………………………. 16
1.3.3. Hàm một phía và hàm cửa sập một phía ……………………………………………….. 17
1.4. Các bài toán quan trọng trong mật mã
………………………………………………………… 18
1.4.1. Bài toán kiểm tra số nguyên tố lớn ………………………………………………………. 18
1.4.2. Bài toán phân tích thành thừa số nguyên tố
……………………………………………. 22
1.4.3. Bài toán tính logarit rời rạc theo modulo ………………………………………………. 28
Kết luận chương 1 ………………………………………………………………………………………… 34
Chương 2. CÁC PHƯƠNG PHÁP TẤN CÔNG CHỮ KÝ SỐ ……………………………….. 35
2.1. Tổng quan về chữ ký số …………………………………………………………………………… 35
2.1.1. Khái niệm chữ ký số
………………………………………………………………………….. 35
2.1.2. Phân loại “chữ ký số” ………………………………………………………………………… 36
2.2. Chữ ký RSA ………………………………………………………………………………………….. 37
2.2.1. Sơ đồ chữ ký ……………………………………………………………………………………. 37
2.2.2. Tấn công dạng 1: Tìm cách xác đ nh khóa bí mật …………………………………… 38
2.2.3. Tấn công dạng 2: Giả mạo chữ ký (không tính tr c tiếp khóa bí mật) ………… 42
4
2.3. Chữ ký Elgamal
……………………………………………………………………………………… 42
2.3.1. Sơ đồ chữ ký ……………………………………………………………………………………. 42
2.3.2. Tấn công dạng 1: Tìm cách xác đ nh khóa bí mật …………………………………… 44
2.3.3. Tấn công dạng 2: Giả mạo chữ ký (không tính tr c tiếp khóa bí mật) ………… 45
2.4. Chữ ký DSS
…………………………………………………………………………………………… 47
2.4.1. Sơ đồ chữ ký ……………………………………………………………………………………. 47
2.4.2. Chú ý
………………………………………………………………………………………………. 48
2.5. Ứng dụng chữ ký số tại Việt Nam
……………………………………………………………… 49
Kết luận chương 2 ………………………………………………………………………………………… 50
Chương 3. XÂY DỰNG THƯ VIỆN TÍNH TOÁN SỐ LỚN …………………………………. 51
3.1. Biểu diễn số lớn
……………………………………………………………………………………… 51
3.2. Các phép toán trong số lớn……………………………………………………………………….. 51
3.2.1. So sánh hai số lớn
……………………………………………………………………………… 51
3.2.2. Cộng hai số dương lớn
……………………………………………………………………….. 52
3.2.3. Trừ hai số dương lớn …………………………………………………………………………. 53
3.2.4. Nhân hai số lớn…………………………………………………………………………………. 53
3.2.5. Phép chia hai số lớn dương
…………………………………………………………………. 54
3.2.6. Lũy thừa ………………………………………………………………………………………….. 56
3.2.7. Ước chung lớn nhất …………………………………………………………………………… 56
3.2.8. Phép nhân theo modulo p …………………………………………………………………… 57
3.2.9. Tìm phần tử ngh ch đảo theo modulo p…………………………………………………. 57
3.2.10. Phép cộng có dấu
…………………………………………………………………………….. 58
3.2.11. Phép trừ có dấu
……………………………………………………………………………….. 59
3.2.12. Phép nhân có dấu
…………………………………………………………………………….. 59
Kết luận chương 3 ………………………………………………………………………………………… 59
Chương 4. THỬ NGHIỆM CHƯƠNG TRÌNH TẤN CÔNG
………………………………….. 60
4.1
. Chương trình th c nghiệm
……………………………………………………………………….. 60
4.2
. Dữ liệu th c nghiệm
……………………………………………………………………………….. 61
4.3
. Tấn công thử nghiệm
………………………………………………………………………………. 64
4.4. Nhận xét và thảo luận ……………………………………………………………………………… 68
Kết luận chương 4 ………………………………………………………………………………………… 68
KẾT LUẬN ……………………………………………………………………………………………………. 69
TÀI LIỆU THAM KHẢO…………………………………………………………………………………. 70
5
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
STT
Từ viết tắt
Ý nghĩa
1
BCNN
Bội chung nhỏ nhất
2
CA
Certificate Authority
3
DSS
Digital Signature Standard
4
NIST
National Institute of Standards and Technology
5
PT
Độ phức tạp
6
RSA
Ron Rivest, Adi Shamir, Len Adleman
7
Sigk
Thao tác ký số
8
UCLN
Ước chung lớn nhất
9
USA
United States of America
10
Verk
Thao tác kiểm tra chữ ký
6
DANH MỤC CÁC BẢNG
Bảng 1.1: Bảng 10 số nguyên tố lớn nhất………………………………………………………..10
Bảng 1.2: Bảng 10 số nguyên tố sinh đôi lớn nhất……………………………………………11
Bảng 1.3: Thời gian chạy của các lớp thuật toán khác nhau………………………………16
Bảng 4.1: Thông tin về chương trình th c nghiệm……………………………………………60
Bảng 4.2: Bảng mô tả tập dữ liệu th c nghiệm…………………………………………………62
7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 4.1: Chương trình th c nghiệm………………………………………………………………60
Hình 4.2: Phần mềm tạo chữ ký số RSA…………………………………………………………61
Hình 4.3: Phần mềm mã hóa dữ liệu……………………………………………………………….62
Hình 4.4: Thư mục chứa khóa công khai…………………………………………………………63
Hình 4.5: Tệp dữ liệu khóa công khai……………………………………………………………..63
Hình 4.6: Giao diện của chương trình tấn công………………………………………………..64
Hình 4.7: Tấn công bằng thuật toán Pollard…………………………………………………….64
Hình 4.8: Kết quả tấn công bằng thuật toán Pollard…………………………………………65
Hình 4.9: Tấn công bằng thuật toán P-1………………………………………………………….65
Hình 4.10: Kết quả tấn công bằng thuật toán P-1…………………………………………….66
Hình 4.11: Tấn công bằng thuật toán Williams……………………………………………….66
Hình 4.12: Kết quả tấn công bằng thuật toán Williams…………………………………….67
Hình 4.13: Tấn công bằng thuật toán Fermat…………………………………………………..67
Hình 4.14: Kết quả tấn công bằng thuật toán Fermat……………………………………….68
8
MỞ ĐẦU
Ngày nay, chữ ký số được sử dụng trong rất nhiều lĩnh v c, ví dụ: trong kinh tế
với các cuộc trao đổi hợp đồng giữa các đối tác kinh doanh; trong xã hội là các cuộc
bỏ phiếu kín khi tiến hành bầu cử từ xa; hay trong các cuộc thi có phạm vi rộng lớn.
Một vài chữ ký số đã được xây d ng và phát triển là: RSA,ELGAMAL,DSS.
Mặc dù bản thân chúng vẫn còn tồn tại nhiều hạn chế như là về kích thước chữ ký, khả
n ng chống giả mạo chưa cao, tuy nhiên, những khả n ng mà nó đem lại cho chúng ta
là rất hữu ích.
Khi áp dụng chữ ký số, vấn đề an ninh luôn được chúng ta quan tâm hàng đầu.
Một chữ ký số chỉ th c s được áp dụng trong th c tế nếu như nó được chứng minh là
không thể hoặc rất khó giả mạo. Mục tiêu của những kẻ tấn công các sơ đồ chữ ký
chính là việc giả mạo chữ ký, điều này có nghĩa là kẻ tấn công sẽ sinh ra được chữ ký
của người ký lên thông điệp, mà chữ ký này sẽ được chấp nhận bởi người xác nhận.
Trong th c tế, các hành vi tấn công vào chữ ký số hết sức đa dạng. Đây cũng chính là
vấn đề được nghiên cứu trong luận v n này.
Nội dung của luận v n gồm các chương:
Chương 1. Trình bày một số khái niệm cơ bản
Chương 2. Tìm hiểu các phương pháp tấn công chữ ký số
Chương 3. Xây d ng thư viện tính toán số lớn
Chương 4. Thử nghiệm chương trình tấn công
9
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN
1.1. Một số khái niệm trong số học
1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất
1/. Khái niệm [1]
Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, thì
ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a, và a là bội của b.
Ví dụ: Cho a = 6, b = 2, ta có 6 = 2*3, ký hiệu 2\6. Ở đây 2 là ước của 6 và 6 là bội của
2.
2/. Ước chung lớn nhất, bội chung nhỏ nhất [1]
Số nguyên d được gọi là ước chung của các số nguyên a1,a2,…,an, nếu nó là ước
của tất cả các số đó.
Số nguyên m được gọi là bội chung của các số nguyên a1,a2,…,an, nếu nó là bội
của tất cả các số đó.
Một ước chung d >0 của các số nguyên a1,a2,…,an trong đó mọi ước chung của
a1,a2,…,an đều là ước của d,thì d gọi là ước chung lớn nhất (UCLN) của a1,a2,…,an. Ký
hiệu d = gcd(a1,a2,…,an) hay d = UCLN(a1,a2,…,an).
Một bội chung m >0 của các số nguyên a1,a2,…,an, trong đó mọi bội chung của
a1,a2,…,an đều là bội của m, thì m gọi là bội chung nhỏ nhất (BCNN) của a1,a2,…, an.
Ký hiệu m = lcm(a1,a2,…,an) hay m = BCNN(a1,a2,…,an).
Ví dụ: Cho a =12, b =15 thì: gcd(12,15) = 3 và lcm(12,15) = 60.
1.1.2. Quan hệ đồng dư
1/. Khái niệm [1]
Cho các số nguyên a, b, m (m >0). Ta nói rằng a và b “đồng dư” với nhau theo
modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư.
Ký hiệu: a ≡ b (mod m)
Ví dụ: 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, được cùng số dư là 2.
Nhận xét:
Các mệnh đề sau đây là tương đương:
a). a ≡ b(mod m)
b). m\(a – b)
c). Tồn tại số nguyên t sao cho a = b + mt
10
2/. Các tính chất [1]
a). Quan hệ “đồng dư” là quan hệ tương đương trong Z:
Với mọi số nguyên dương m ta có:
a ≡ a (mod m) với mọi aZ; (tính chất phản xạ).
a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng).
a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu).
b). Tổng hay hiệu các “đồng dư”:
(a+b) (mod n) [(a mod n) + (b mod n)] (mod n)
(a- b) (mod n) [(a mod n) – (b mod n)] (mod n)
c). Tích các “đồng dư”:
(a*b) (mod n) [(a mod n) * (b mod n)] (mod n)
1.1.3. Số nguyên tố
1/. Khái niệm: Số nguyên tố là số t nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 17,…, 1299827,… là các số nguyên tố.
Số 2 là số nguyên tố chẵn duy nhất và đồng thời là số nguyên tố nhỏ nhất.
Người ta đã chứng minh rằng số lượng các số nguyên tố là vô hạn. Số nguyên tố có vai
trò vô cùng quan trọng trong lý thuyết mật mã. Các nhà khoa học đang ngày đêm tìm
kiếm các số nguyên tố lớn để ứng dụng vào trong mật mã.
Bảng 10 số nguyên tố lớn nhất được tìm ra cho tới thời điểm này (tháng 10/2016):
Bảng 1.1 Bảng 10 số nguyên tố lớn nhất [13]
Rank
Prime
Digits
Who When
Reference
1
274207281 -1 22338618 G14 2016 Mersenne 49??
2
257885161 -1 17425170 G13 2013 Mersenne 48??
3
243112609 -1 12978189 G10 2008 Mersenne 47??
4
242643801 -1 12837064 G12 2009 Mersenne 46??
5
237156667 -1 11185272 G11 2008 Mersenne 45??
6
232582657 -1 9808358 G9
2006 Mersenne 44??
7
230402457 -1 9152052 G9
2005 Mersenne 43??
8
225964951 -1 7816230 G8
2005 Mersenne 42??
9
224036583 -1 7235733 G7
2004 Mersenne 41??
10
220996011 -1 6320430 G6
2003 Mersenne 40??
11
Bảng 10 số nguyên tố sinh đôi lớn nhất được tìm thấy (tháng 10/2016):
Bảng 1.2 Bảng 10 số nguyên tố sinh đôi lớn nhất [13]
Rank
Prime
Digits
Who
When
Reference
1
2996863034895·21290000+1 388342 L2035 2016
Twin (p+2)
2
2996863034895·21290000-1 388342 L2035 2016
Twin (p)
3
3756801695685·2666669+1 200700 L1921 2011
Twin (p+2)
4
3756801695685·2666669-1 200700 L1921 2011
Twin (p)
5
65516468355·2333333+1
100355 L923
2009
Twin (p+2)
6
65516468355·2333333-1
100355 L923
2009
Twin (p)
7
70965694293·2200006+1
60219
L95
2016
Twin (p+2)
8
70965694293·2200006-1
60219
L95
2016
Twin (p)
9
66444866235·2200003+1
60218
L95
2016
Twin (p+2)
10
66444866235·2200003-1
60218
L95
2016
Twin (p)
Trong mật mã, người ta thường sử dụng các số nguyên tố có vài tr m chữ số trở lên.
Hai số m và n được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của
chúng bằng 1. Ký hiệu: gcd (m, n) = 1.
Ví dụ: 9 và 14 là hai số nguyên tố cùng nhau. [6]
2/. Các định lý về số nguyên tố
a). Định lý về số nguyên dương >1
Mọi số nguyên dương n >1 đều có thể biểu diễn được duy nhất dưới dạng:
1
2
k
n
n
n
1
2
k
.
…
=P P
P
n
, trong đó: k,ni (i =1,2,..,k) là các số t nhiên, Pi là các số nguyên tố,
từng đôi một khác nhau. [1]
b). Định lý Mersenne [1]
Cho p = 2k – 1, nếu p là số nguyên tố, thì k phải là số nguyên tố.
c). Định lý Fermat và số nguyên tố Fermat [6]
– Đ nh lý: Nếu p là số nguyên tố, a là số nguyên thì
(mod )
p
a
a
p
.
Một cách phát biểu khác của định lý như sau: Nếu p là số nguyên tố và a là số nguyên
tố cùng nhau với p thì: ap-1 1 (mod p).
Ví dụ: 47 4 (mod 7); 47-1 1 (mod 7).
– Số nguyên tố Fermat: là một số nguyên dương có dạng:
1
22
n
n
F
12
Rất nhiều số Fermat là số nguyên tố, cho nên có một thời gian người ta cho rằng tất cả
các số có dạng đó đều là số nguyên tố.
Với n là số không âm, các số Fermat đầu tiên bao gồm:
F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65.537
F5 = 232 + 1 = 4.294.967.297
F6 = 264 + 1 = 18.446.744.073.709.551.617
F7 = 2128 + 1 = 340.282.366.920.938.463.463.374.607.431.768.211.457
d). Hàm Euler [1]
Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên tố cùng
nhau với n được ký hiệu (n) và gọi là hàm Euler.
Nhận xét: Nếu p là số nguyên tố, thì (p) = p-1.
Ví dụ: Tập các số nguyên không âm nhỏ hơn 7 là Z7 ={0, 1, 2, 3, 4, 5, 6}.
Do 7 là số nguyên tố, nên tập các số nguyên dương nhỏ hơn 7 và nguyên tố cùng nhau
với 7 là Z7
* ={1, 2, 3, 4, 5, 6}. Khi đó /Z/=(p) = p-1= 7-1= 6.
Định lý: Nếu n là tích của hai số nguyên tố n=p.q, thì (n) =(p).(q) = (p-1).(q-1).
1.2. Một số khái niệm trong đại số
1.2.1. Cấu trúc nhóm [1]
1/. Khái niệm: Nhóm là một bộ (G, *), trong đó G , * là phép toán hai ngôi trên G
thoả mãn ba tính chất sau:
+ Phép toán có tính kết hợp: (x*y)*z = x*(y*z) với mọi x, y, z G.
+ Có phần tử trung lập eG: x*e = e*x = x với mọi x G.
+ Với mọi xG, có phần tử ngh ch đảo x’ G: x*x’ = x’*x = e.
Cấp của nhóm G được hiểu là số phần tử của nhóm, ký hiệu: G .
Cấp của nhóm có thể là nếu G có vô hạn phần tử.
Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán.
Tính chất:
Nếu a*b = a*c thì b = c.
Nếu a*c = b*c thì a = b.
Ví dụ: Tập hợp các số nguyên Z cùng với phép cộng (+) thông thường là nhóm giao
hoán, có phần tử đơn v là số 0. Gọi là nhóm cộng các số nguyên.
13
Tập Q* các số hữu tỷ khác 0 (hay tập R* các số th c khác 0), cùng với phép
nhân (*) thông thường là nhóm giao hoán. Gọi là nhóm nhân các số hữu tỷ (số th c)
khác 0.
Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán.
2/. Nhóm con của nhóm (G,*)
Nhóm con của G là tập S G, S , và thỏa mãn các tính chất sau:
+ Phần tử trung lập e của G nằm trong S.
+ S khép kín đối với phép tính (*) trong G, tức là x*y S với mọi x,y S.
+ S khép kín đối với phép lấy ngh ch đảo trong G, tức x-1 S với mọi xS.
1.2.2. Nhóm Cyclic [1]
1/. Khái niệm: Nhóm (G,*) được gọi là nhóm Cyclic nếu nó được sinh ra bởi một
trong các phần tử của nó. Tức là có phần tử gG mà với mỗi aG, đều tồn tại số nN
để gn = g*g*…*g = a. (g*g*…*g là g*g với n lần). Khi đó g được gọi là phần tử sinh
hay phần tử nguyên thuỷ của nhóm G.
2/. Cấp của nhóm Cyclic: Cho (G,*) là nhóm Cyclic với phần tử sinh g và phần tử
trung lập e. Nếu tồn tại số t nhiên nhỏ nhất n mà gn = e, thì G sẽ chỉ gồm có n phần tử
khác nhau: e, g, g2, g3,…,gn-1. Khi đó, G được gọi là nhóm Cyclic hữu hạn cấp n. Nếu
không tồn tại số t nhiên n để gn = e, thì G có cấp .
Ví dụ: (Z +, +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1, e = 0. Đó là
nhóm Cyclic vô hạn, vì không tồn tại số t nhiên n để gn = e.
3/. Cấp của một phần tử trong Nhóm Cyclic: Phần tử G gọi là có cấp d, nếu d là
số nguyên dương nhỏ nhất sao cho d = e, trong đó e là phần tử trung lập của G. Như
vậy, phần tử có cấp 1, nếu = e.
1.2.3. Nhóm Zn
*
1/. Tập thặng dư thu gọn theo modulo [1]
* Kí hiệu:
Zn = 0, 1, 2,…, n-1 là tập các số nguyên không âm < n.
Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1 và phần tử
trung lập là e = 0.
(Zn,+) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n.
* Kí hiệu:
14
Zn
* = xZn, x là nguyên tố cùng nhau với n. Tức là x phải 0.
Zn
*
được gọi là tập thặng dư thu gọn theo mod n, có số phần tử là (n).
Zn
* với phép nhân mod n lập thành một nhóm nhân, phần tử trung lập e = 1.
Tổng quát (Zn
* , phép nhân mod n ) không phải là nhóm Cyclic.
Nhóm nhân Zn
* là Cyclic chỉ khi n có dạng: 2, 4, pk, hay 2pk với p là số nguyên tố lẻ
và k ≥ 1. Còn nếu n là số nguyên tố thì Zn
* là nhóm Cyclic.
2/. Phần tử nghịch đảo đối với phép nhân [1]
a). Định nghĩa: Cho aZn, nếu tồn tại bZn sao cho a.b 1(mod n), ta nói b là phần tử
nghịch đảo của a trong Zn và ký hiệu a-1. Một phần tử có phần tử ngh ch đảo, gọi là
khả ngh ch.
b). Định lý: UCLN(a, n) = 1 Phần tử aZn có phần tử ngh ch đảo.
c). Thuật toán Euclid tìm phần tử nghịch đảo
Input: aZn, n
Output: Phần tử ngh ch đảo của a.
Procedure Ngh ch đảo(a,n)
Begin
g0:=n; g1:=a;
u0:=1; u1:=0;
v0:=0; v1:=1;
i:=1;
while (gi 0) do
begin
y := gi-1 div gi;
gi+1 := gi+1 - y.gi;
ui+1 := ui+1 - y.ui;
vi+1 := vi+1 - y.vi;
i := i+1;
end;
t := vi+1; if (t > 0) then a-1 := t else a-1:= t+n;
End.
3/. Khái niệm logarit rời rạc [1]
Cho p là số nguyên tố, g là phần tử nguyên thuỷ Z*
p và Z*
p
15
“Logarit rời rạc” chính là việc giải phương trình x = logg
β (mod p) với ẩn x.
Hay phải tìm số x duy nhất sao cho: gx (mod p).
4/. Thặng dư bậc hai [5]
a). Định nghĩa: Phần tử aZ*
n được gọi là thặng dư bậc 2 theo modulo n nếu xZ*
n:
x2 a mod n. Gọi QN là tập các thặng dư bậc 2 và QN là tập các thặng dư không bậc 2.
b). Định lý (về số lượng thặng dư bậc 2):
– Với p là số nguyên tố, α là phần tử sinh Z*
p, khi đó a = αi mod p là thặng dư bậc 2
khi và chỉ khi i chẵn. Số lượng thặng dư bậc 2 được tính bằng công thức:
1
.
2
p
p
p
Q
Q
– Với n = p.q trong đó p,q là các số nguyên tố. Khi đó, a QN khi và chỉ khi a Qp
và a Qq .
Vậy số lượng thặng dư bậc 2 là:
1 (
1).(
1)
4
N
p
q
Q
số lượng thặng dư không bậc 2 là:
3 (
1).(
1).
4
N
p
q
Q
1.3. Độ phức tạp của thuật toán
1.3.1. Khái niệm độ phức tạp của thuật toán [1]
1/. Chi phí của thuật toán
Chi phí phải trả cho một quá trình tính toán gồm chi phí về thời gian và chi phí về
bộ nhớ. Gọi A là một thuật toán, e là dữ liệu vào của bài toán đã được mã hoá bằng
cách nào đó. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất đ nh.
Ta ký hiệu: tA (e) là giá thời gian và lA(e) là giá bộ nhớ.
2/. Độ phức tạp về bộ nhớ
LA(n) = max{lA (e), với |e| n}, n là “kích thước” đầu vào của thuật toán.
3/. Độ phức tạp về thời gian
TA(n) = max{t A (e), với |e| n}
4/. Độ phức tạp tiệm cận
Độ phức tạp PT(n) được gọi là tiệm cận tới hàm f(n), ký hiệu O(f(n)) nếu (n0,c)
mà PT(n) c.f(n), n n0.
5/. Độ phức tạp đa thức
16
Độ phức tạp PT(n) được gọi đa thức, nếu nó tiệm cận tới đa thức p(n).
6/. Thuật toán đa thức
Thuật toán được gọi là đa thức, nếu độ phức tạp về thời gian (trong trường hợp
xấu nhất) của nó là đa thức.
Nói cách khác:
+ Thuật toán thời gian đa thức là thuật toán có độ phức tạp thời gian O(nt ), trong
đó t là hằng số.
+ Thuật toán thời gian hàm mũ là thuật toán có độ phức tạp thời gian O(tf(n) ), trong
đó t là hằng số và f(n) là đa thức của n.
Bảng 1.3 Thời gian chạy của các lớp thuật toán khác nhau
Độ phức tạp
Số phép tính (n=106) Thời gian(106 phép tính/s)
O(1)
1
1 micro giây
O(n)
106
1 giây
O(n2)
1012
11,6 ngày
O(n3)
1018
32 000 n m
O(2n)
10301030
10301006 tuổi của vũ trụ
* Chú ý
– Có người cho rằng, ngày nay máy tính có tốc độ rất cao cho nên không cần phải
quan tâm nhiều tới thuật toán nhanh, tôi xin dẫn một ví dụ đã được kiểm chứng.
– Bài toán xử lý n đối tượng, có ba thuật toán với 3 mức phức tạp khác nhau sẽ ch u 3
hậu quả như sau: Sau 1 giờ:
Thuật toán A có độ phức tạp O(n): xử lý được 3,6 triệu đối tượng.
Thuật toán B có độ phức tạp O(n log n): xử lý được 0,2 triệu đối tượng.
Thuật toán C có độ phức tạp O(2n): xử lý được 21 đối tượng.
1.3.2. Phân lớp bài toán theo độ phức tạp [1]
1/. Khái niệm “dẫn về được”
Bài toán B được gọi là “dẫn về được” bài toán A một cách đa thức, ký hiệu: B
A, nếu có thuật toán đơn đ nh đa thức để giải bài toán A, thì cũng có thuật toán đơn
đ nh đa thức để giải bài toán B.
Nghĩa là: Bài toán A “khó hơn” bài toán B, hay B “dễ” hơn A, bài toán B được
diễn đạt bằng ngôn ngữ của bài toán A, hay có thể hiểu B là trường hợp riêng của A.
17
Vậy nếu giải được bài toán A thì cũng sẽ giải được bài toán B. Quan hệ có tính chất
bắc cầu: Nếu C B và B A thì C A.
2/. Khái niệm “khó tương đương”
Bài toán A gọi là “khó tương đương” bài toán B, ký hiệu A ~ B, nếu: A B và B A.
3/. Lớp bài toán P, NP
Ký hiệu:
P là lớp bài toán giải được bằng thuật toán đơn đ nh, đa thức.
NP là lớp bài toán giải được bằng thuật toán không đơn đ nh, đa thức.
Theo đ nh nghĩa ta có P NP. Hiện nay người ta chưa biết được P ≠ NP ?
4/. Lớp bài toán NP- Hard
Bài toán A được gọi là NP – Hard (NP- khó) nếu L NP đều là L A.
Lớp bài toán NP – Hard bao gồm tất cả những bài toán NP – Hard.
Bài toán NP – Hard có thể nằm trong hoặc ngoài lớp NP.
5/. Lớp bài toán NP – Complete
Bài toán A được gọi là NP – Complete (NP- đầy đủ) nếu A là NP – Hard và A NP.
Bài toán NP – Complete là bài toán NP – Hard nằm trong lớp NP.
Lớp bài toán NP – Complete bao gồm tất cả những bài toán NP – Complete.
Lớp NP – Complete là có th c, vì Cook và Karp đã chỉ ra bài toán đầu tiên thuộc lớp
này, đó là bài toán “thỏa được” (Satisfy ability).
1.3.3. Hàm một phía và hàm cửa sập một phía [1]
1/. Hàm một phía
Hàm f(x) được gọi là hàm một phía nếu tính “xuôi” y = f(x) thì “dễ”, nhưng tính
“ngược” x = f -1(y) thì lại rất “khó”.
Ví dụ: Hàm f(x) = gx (mod p), với p là số nguyên tố lớn, g là phần tử nguyên thuỷ mod
p là hàm một phía.
2/. Hàm cửa sập một phía
Hàm f(x) được gọi là hàm cửa sập một phía nếu tính “xuôi” y = f(x) thì “dễ”,
nhưng tính “ngược” x = f -1 (y) thì lại rất “khó”. Tuy nhiên, lại có cửa sập z sao cho
việc tính x = f -1(y) là “dễ”.
Ví dụ: Hàm f(x) = xa (mod n) (với n là tích của hai số nguyên tố lớn n = p*q) là hàm
một phía. Nếu chỉ biết a và n thì việc tính x = f -1(y) là rất “khó”, nhưng nếu biết cửa
sập p và q, thì việc tính được f -1(y) là khá “dễ”.
18
1.4. Các bài toán quan trọng trong mật mã
Trong phần này, chúng ta sẽ tìm hiểu ba bài toán có vai trò c c kỳ quan trọng
trong lý thuyết mật mã, đó là các bài toán: kiểm tra tính nguyên tố của một số nguyên;
phân tích một số nguyên thành tích của các thừa số nguyên tố; tính logarit rời rạc của
một số theo modulo nguyên tố. Ở đây ta mặc đ nh rằng các số nguyên là rất lớn.
1.4.1. Bài toán kiểm tra số nguyên tố lớn
Cho n là số nguyên dương bất kỳ. Làm thế nào để kiểm tra được n có phải là số
nguyên tố hay không ? Bài toán được đặt ra từ những buổi đầu của số học và trải qua
hơn 2000 n m đến nay vẫn là một bài toán chưa có được những cách giải dễ dàng.
N m 1975, Pratt đã chứng minh nó thuộc lớp NP và thuộc lớp co-NPNP, đây là bài
toán “khó”. Bằng những phương pháp đơn giản như sàng Eratosthenes, từ rất sớm
người ta đã xây d ng được bảng các số nguyên tố đầu tiên, rồi tiếp tục bằng nhiều
phương pháp khác tìm thêm được nhiều số nguyên tố lớn hơn.
Tuy nhiên, chỉ đến giai đoạn hiện nay của lý thuyết mật mã hiện đại thì nhu cầu
sử dụng các số nguyên tố và thử tính nguyên tố của các số mới trở thành một nhu cầu
to lớn và phổ biến, đòi hỏi nhiều phương pháp mới có hiệu quả hơn. Trong mục này
chúng ta sẽ lược qua vài tính chất của số nguyên tố và một vài phương pháp thử tính
nguyên tố của một số nguyên bất kỳ. [4]
1/. Một số ký hiệu toán học [3]
a). Ký hiệu Lagrăng
Ký hiệu L(a,p) được đ nh nghĩa với a là một số nguyên và p là một số nguyên tố lớn
hơn 2. Nó nhận ba giá tr 0, 1, -1:
L(a,p) = 0 nếu a chia hết cho p
L(a,p) = 1 nếu aQN (a là thặng dư bậc 2 modulo p)
L(a,p) = -1 nếu aQN (a không là thặng dư bậc 2 modulo p)
Một phương pháp dễ dàng để tính toán ra L(a,p) là: L(a,p) = a(p-1)/2 mod p
b). Ký hiệu Jacobi
Ký hiệu Jacobi được viết là J(a,n), nó là s khái quát hóa của ký hiệu Lagr ng, nó đ nh
nghĩa cho bất kỳ cặp số nguyên a và n nào. Ký hiệu Jacobi là một chức n ng trên tập
hợp số thặng dư thấp của ước số n và có thể tính toán theo công thức sau:
Nếu n là số nguyên tố, thì J(a,n) = 1 nếu a là thặng dư bậc hai modulo n.
Nếu n là số nguyên tố, thì J(a,n) = -1 nếu a không là thặng dư bậc hai modulo n.
19
Nếu n không phải là số nguyên tố thì Jacobi (a,n) sẽ được tính theo công thức
sau: J(a,n) = J(h,p1) × J(h,p2) ×…× J(h,pm) với p1, p2,…,pm là các thừa số lớn
nhất của n.
Thuật toán này tính ra số Jacobi tuần hoàn theo công thức sau:
(1) J(1,k) = 1
(2) J(a×b,k) = J(a,k) × J(b,k)
(3) J(2,k) = 1 nếu (k2 – 1)/8 là chia hết và J(2,k) = -1 trong các trường hợp khác.
(4) J(b,a) = J((b mod a), a)
(5) Nếu gcd(a,b)=1:
J(a,b) × J(b,a) = 1 nếu (a-1).(b-1)/4 là chia hết.
J(a,b) × J(b,a) = -1 nếu (a-1).(b-1)/4 là còn dư.
Trên th c tế có thể tính được ký hiệu Jacobi một cách thuận lợi hơn nếu d a vào một
trong các tính chất sau, giả sử m và n là các số nguyên lẻ, a,b Z:
J(a*b, n) = J(a,n) * J(b,n) do đó J(a2, n) = 1
J(a, m*n) = J(a,m) * J(a,n)
Nếu a b (mod n) thì J(a,n) = J(b,n)
J(1,n) = 1
J(-1,n) = (-1)(n-1)/2
J(m,n) = J(n,m) * (-1)(m-1)*(n-1)/4
2/. Một số thuật toán kiểm tra tính nguyên tố
a). Thuật toán Soloway-Strassen [3]
Thuật toán này sử dụng hàm Jacobi.
Thuật toán kiểm tra số p là số nguyên tố:
1. Chọn ngẫu nhiên một số a nhỏ hơn p.
2. Nếu ước số chung lớn nhất gcd(a, p) ≠ 1 thì p là hợp số.
3. Tính j = a(p-1)/2 mod p.
4. Tính số Jacobi J(a,p).
5. Nếu j ≠ J(a,p), thì p không phải là số nguyên tố.
6. Nếu j = J(a,p) thì ta nói p có thể là số nguyên tố với chắc chắn 50%.
Lặp lại các bước này n lần, mỗi lần với một giá tr ngẫu nhiên khác nhau của a. Phần
dư của hợp số với n phép thử là không quá 2n.
Độ phức tạp của thuật toán là O(log2
p).
20
b). Thuật toán Miller-Rabin [6]
Thuật toán này được phát triển bởi Rabin, d a trên một phần ý tưởng của Miller. Th c
tế những phiên bản của thuật toán đã được giới thiệu tại NIST.
Input: Số t nhiên lẻ n
Output: Nguyên tố hoặc hợp số
1. Phân tích n – 1 = 2s.m, trong đó s ≥ 1 và m là số t nhiên lẻ
2. Chọn ngẫu nhiên số t nhiên a {2,…,n-1}
3. Đặt b = am mod n
4. Nếu b 1 mod n thì đây là số nguyên tố. Kết thúc.
5. Cho k chạy từ 0 đến s-1:
5.1 Nếu b -1 mod n thì đây là số nguyên tố. Kết thúc.
5.2 Thay b:= b2 mod n
6. Kết luận đây là hợp số. Kết thúc.
Xác suất sai lầm của thuật toán này là ≤ 1
4 . Độ phức tạp của thuật toán là O(log2
n).
c). Thuật toán Lehmann [3]
Một phương pháp đơn giản hơn kiểm tra số nguyên tố được phát triển độc lập bởi
Lehmann.
Sau đây là thuật toán với số bước lặp là 100:
1. Chọn ngẫu nhiên một số n để kiểm tra.
2. Chắc chắn rằng n không chia hết cho các số nguyên tố nhỏ như 2,3,5,7, và 11
3. Chọn ngẫu nhiên 100 số a1, a2, a3,… a100 giữa 1 và n-1
4. Tính ai
(n-1)/2 (mod n) cho tất cả ai = a1. . . a100. Dừng lại nếu bạn tìm thấy ai sao
cho phép kiểm tra là sai.
5. Nếu ai
(n-1)/2 = 1 (mod n) với mọi i thì n có thể là hợp số.
Nếu ai
(n-1)/2 ≠ 1 hoặc -1 (mod n) với i bất kỳ, thì n là hợp số.
Nếu ai
(n-1)/2 = 1 hoặc -1 (mod n) với mọi i ≠ 1, thì n là số nguyên tố.
d). Thuật toán AKS (Agrawal-Kayal-Saxene) [6]
Tháng 8 n m 2002, ba tác giả Manindra Agrawal, Neeraj Kayal và Nitin Saxena (Viện
công nghệ Kanpur Ấn Độ) đã công bố thuật toán kiểm tra tính nguyên tố với độ phức
tạp thời gian đa thức.
Thuật toán xuất phát từ ý tưởng sau: một số nguyên n (n>2) là số nguyên tố khi và chỉ
21
khi: (x-a)n (xn-a)(mod n) (*) đúng với mọi số nguyên a là số nguyên tố cùng nhau
với n (hoặc chỉ cần đúng với số giá tr của a, đặc biệt khi a = 1).
Với đ nh lý trên, thời gian tính của thuật toán sẽ là một hàm mũ. Tiến hành rút gọn hai
vế của đẳng thức trên theo modulo xr – 1. Sau đó lại rút gọn các hệ số của kết quả thu
được theo modulo n. Ta được biểu thức sau:
(x-a)n (xn-a)(mod xr-1,n) (**)
Hay ta có:
(x-a)n – (xn-a) = nf + (xr-1)g (***)
Biểu thức (**) có thể xảy ra trong một số trường hợp p là hợp số, nhưng người ta đã
chứng minh được rằng không hợp số p nào thoả mãn (**) với mọi a nằm trong vùng
1 1
Output: Nguyên tố hoặc hợp số
if (n có dạng ab; a,b N, b >1) output n là hợp số. Kết thúc.
r = 2;
while (r < n) {
if (UCLN(n,r) >1) output n là hợp số. Kết thúc.
if (r là số nguyên tố) {
Tìm số q – là ước nguyên tố lớn nhất của r-1;
if ((q ≥ 4
r log2
n) và (
1
r
q
n
≠ 1 (mod r))) break;
}
r:= r + 1; if (r ≥ n) output n là số nguyên tố. Kết thúc.
22
}
if ((n-1) ≤ 2
r log2
n) {
for a = (r+1) to (n-1)
if (UCLN(a,n) >1) output n là hợp số. Kết thúc.
}
for a = 1 to 2
r log2
n
if ((x-a)n
xn – a(mod xr – 1)) output n là hợp số. Kết thúc.
output n là số nguyên tố.
Thuật toán này đã được một số nhà toán học kiểm nghiệm, đánh giá cao và xem
là thuật toán tốt, có thể dùng cho việc kiểm thử tính nguyên tố của các số nguyên.
Trong th c tiễn xây d ng các giải pháp mật mã, nhu cầu tìm kiếm các số nguyên tố rất
lớn. Để tìm được số như vậy, người ta chọn ngẫu nhiên một số n rất lớn, dùng một
thuật toán xác suất, chẳng hạn như thuật toán Miller-Rabin. Nếu thuật toán cho kết quả
“n là số nguyên tố” với một xác suất sai nào đó, thì dùng tiếp một thuật toán tất đ nh
(chẳng hạn thuật toán Agrawal-Kayal-Saxena) để đảm bảo chắc chắn 100% rằng số n
là nguyên tố. Thuật toán Agrawal-Kayal-Saxena được chứng minh là có độ phức tạp
thời gian đa thức cỡ O((log n)12) khi thử trên số n; và nếu số nguyên tố được thử có
dạng Sophie Germain, tức dạng 2p+1, thì độ phức tạp thời gian chỉ còn O((log n)6). [4]
1.4.2. Bài toán phân tích thành thừa số nguyên tố
Bài toán phân tích một số nguyên thành thừa số nguyên tố cũng được xem là
bài toán “khó”, thường được sử dụng trong lý thuyết mật mã. Đồng thời, đây cũng là
một bài toán quan trọng trong việc tấn công hệ mật RSA. Như chúng ta đã biết thì độ
an toàn của hệ mật RSA chủ yếu phụ thuộc vào độ “khó” của bài toán phân tích số
nguyên lớn modulo n thành tích của hai số nguyên tố p và q. Nếu chúng ta th c hiện
được công việc này trong thời gian “đủ nhanh” thì việc phá được hệ mật này là hoàn
toàn có thể. Có nhiều thuật toán để làm việc này, tuy nhiên trong luận v n này tôi chỉ
trình bày một số thuật toán thường được sử dụng nhất.
1/. Thuật toán sàng Eratosthenes [2]
Thuật toán phân tích số nguyên N được mô tả như sau:
(1) p = 1
(2) p = p+1
(3) Tính r = N mod p
23
Nếu r > 0 thì quay về bước (2).
Ngược lại, p là ước của N. Dừng chương trình.
Đây là thuật toán có tính phổ thông và mặc dù như chúng ta đã biết là thuật toán rất
“tồi” vì thời gian tính của nó là O(
n ) nhưng nếu N có ước nhỏ thì việc áp dụng thuật
toán này lại rất hiệu quả.
2/. Thuật toán sàng đồng dư [2]
Thuật toán được mô tả như sau:
(1) Lấy ngẫu nhiên hai số a và b, với a,b Zn
*
(2) Kiểm tra gcd((a-b) mod n,n) > 1 hoặc gcd((a+b) mod n,n) > 1
– Nếu đúng thì gcd((a-b) mod n,n) > 1 hoặc gcd((a+b) mod n,n) > 1 là ước của
n. Dừng chương trình.
– Ngược lại thì quay về (1)
Bây giờ, chúng ta hãy tạm dừng để phân tích thuật toán dưới góc độ xác suất như sau:
Cho p là ước nguyên tố nhỏ nhất của n, thế thì “cần có tối thiểu bao nhiêu cặp a,b
được xét đến để xác suất có ít nhất một cặp trong số đó thỏa mãn ((a ± b) mod p)≡ 0 ≥
0.5 ? ”. Bài toán trên còn được gọi là bài toán “trùng ngày sinh” và số m tối thiểu cần
tìm trong bài toán sẽ là m ≈ c.p, với c là một hằng số tính được nào đó. Thuật toán có
thể thành công với xác suất > 0.5, sau không quá m bước.
Bằng cách duyệt dần thì thời gian của thuật toán không khác gì thời gian của phép
sàng. Tác giả J.M.Pollard đã sử dụng một phương pháp còn gọi là “phương pháp δ”.
Chỉ cần thông qua
m bước có thể duyệt được m cặp khác nhau như đã nêu trên trong
thuật toán.
3/. Thuật toán Pollard [2]
Thuật toán hiệu quả trong việc tìm các ước nhỏ là thuật toán d a vào phương pháp δ
và được gọi là thuật toán Pollard. Thời gian tính của thuật toán này chỉ còn là O(
p ).
Với p là ước nguyên tố nhỏ nhất của n. Trong trường hợp tồi nhất (p≈
n ) thì thời gian
tính của thuật toán cũng chỉ là 4 n .
Phương pháp δ của Pollard:
Tìm hai phần tử đồng dư modulo p (a ≡ ± b mod p) nhưng không đồng dư modulo n.
Lúc này p sẽ là ước của gcd(n, (a ± b) mod n).
Có thể mô tả thuật toán như sau:
