Giáo trình An toàn và bảo mật thông tin
Mục lục
MỤC LỤC
LỜI NÓI ĐẦU.................................................................................................................... 1
CHƯƠNG I: GIỚI THIỆU.................................................................................................. 2
1. An toàn bảo mật thông tin và mật mã học ................................................................. 2
2. Khái niệm hệ thống và tài sản của hệ thống.............................................................. 2
3. Các mối đe doạ đối với một hệ thống và các biện pháp ngăn chặn........................... 2
4. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin ................................... 3
5. Mật mã học (cryptology)............................................................................................ 4
6. Khái niệm hệ mã mật (CryptoSystem)....................................................................... 4
7. Mô hình truyền tin cơ bản của mật mã học và luật Kirchoff ....................................... 5
8. Sơ lược về lịch sử mật mã học ................................................................................. 6
9. Phân loại các thuật toán mật mã học ........................................................................ 8
10. Một số ứng dụng của mật mã học........................................................................... 8
CHƯƠNG II: CƠ SỞ TOÁN HỌC................................................................................... 10
1. Lý thuyết thông tin................................................................................................... 10
1.1. Entropy............................................................................................................. 10
1.2. Tốc độ của ngôn ngữ. (Rate of Language)....................................................... 11
1.3. Tính an toàn của hệ thống mã hoá................................................................... 11
1.4. Kỹ thuật lộn xộn và rườm rà. (Confusion and Diffusion) ................................... 12
2. Lý thuyết độ phức tạp.............................................................................................. 13
2.1. Độ an toàn tính toán......................................................................................... 14
2.2. Độ an toàn không điều kiện.............................................................................. 14
3.3. Hệ mật tích....................................................................................................... 16
3. Lý thuyết toán học................................................................................................... 17
3.1. Modulo số học.................................................................................................. 17
3.2. Số nguyên tố. ................................................................................................... 17
3.3. Ước số chung lớn nhất..................................................................................... 17
3.4. Vành ZN (vành đồng dư module N)................................................................... 18
3.5. Phần tử nghịch đảo.......................................................................................... 18
3.6. Hàm phi Ơle..................................................................................................... 19
3.7. Thặng dư bậc hai ............................................................................................. 19
3.8. Thuật toán lũy thừa nhanh................................................................................ 20
3.9. Thuật toán Ơclit mở rộng ................................................................................. 21
3.10. Phương trình đồng dư bậc nhất 1 ẩn.............................................................. 21
3.11. Định lý phần dư Trung Hoa. ........................................................................... 22
4. Các thuật toán kiểm tra số nguyên tố...................................................................... 23
4.1. Một số ký hiệu toán học.................................................................................... 23
4.2. Thuật toán Soloway-Strassen........................................................................... 25
4.3. Thuật toán Rabin-Miller .................................................................................... 25
4.4. Thuật toán Lehmann. ....................................................................................... 26
CHƯƠNG III: CÁC HỆ MÃ KHÓA BÍ MẬT...................................................................... 27
1. Các hệ mã cổ điển .................................................................................................. 27
1.1. Hệ mã hoá thay thế (substitution cipher) .......................................................... 27
1.2. Hệ mã Caesar .................................................................................................. 27
i
Mục lục
1.3. Hệ mã Affine..................................................................................................... 28
1.4. Hệ mã Vigenere ............................................................................................... 29
1.5. Hệ mã Hill......................................................................................................... 29
1.6. Hệ mã đổi chỗ (transposition cipher) ................................................................ 31
2. Các hệ mã khối ....................................................................................................... 33
2.1. Mật mã khối...................................................................................................... 33
2.2. Chuẩn mã hoá dữ liệu DES (Data Encryption Standard) .................................. 34
2.3. Các yếu điểm của DES .................................................................................... 48
2.4. Các cơ chế, hình thức sử dụng của mã hóa khối (Mode of Operation)............. 50
CHƯƠNG IV: CÁC HỆ MÃ MẬT KHÓA CÔNG KHAI..................................................... 55
1. Khái niệm hệ mã mật khóa công khai...................................................................... 55
2. Nguyên tắc cấu tạo của các hệ mã mật khóa công khai.......................................... 56
3. Một số hệ mã khóa công khai.................................................................................. 56
3.1. Hệ mã knapsack............................................................................................... 56
3.2. Hệ mã RSA ...................................................................................................... 57
3.3. Hệ mã El Gammal ............................................................................................ 60
CHƯƠNG V: CHỮ KÝ ĐIỆN TỬ VÀ HÀM BĂM ............................................................. 62
1. Chữ ký điện tử ........................................................................................................ 62
1.1. Khái niệm về chữ ký điện tử............................................................................. 62
1.2. Hệ chữ ký RSA................................................................................................. 63
1.3. Hệ chữ ký ElGammal ....................................................................................... 64
1.4. Chuẩn chữ ký điện tử (Digital Signature Standard)........................................... 67
2. Hàm Băm (Hash Function)...................................................................................... 69
2.1. Khái niệm ......................................................................................................... 69
2.2. Đặc tính của hàm Băm..................................................................................... 70
2.3. Birthday attack.................................................................................................. 71
2.4. Một số hàm Băm nổi tiếng................................................................................ 72
2.5. Một số ứng dụng của hàm Băm........................................................................ 78
CHƯƠNG VI: QUẢN LÝ KHÓA ...................................................................................... 80
1. Quản lý khoá trong các mạng truyền tin .................................................................. 80
2. Một số hệ phân phối khoá ....................................................................................... 80
2.1. Sơ đồ phân phối khoá Blom ............................................................................. 80
2.2. Hệ phân phối khoá Kerberos............................................................................ 82
2.3. Hệ phân phối khoá Diffe-Hellman..................................................................... 83
3. Trao đổi khoá và thoả thuận khoá ........................................................................... 84
3.1. Giao thức trao đổi khoá Diffie-Hellman............................................................. 84
3.2. Giao thức trao đổi khoá Diffie-Hellman có chứng chỉ xác nhận ........................ 85
3.3. Giao thức trao đổi khoá Matsumoto-Takashima-Imai ....................................... 86
3.4. Giao thức Girault trao đổi khoá không chứng chỉ.............................................. 87
CHƯƠNG VII: GIAO THỨC MẬT MÃ ............................................................................. 89
1. Giao thức ................................................................................................................ 89
2. Mục đích của các giao thức..................................................................................... 89
3. Các bên tham gia vào giao thức (the players in protocol)........................................ 90
4. Các dạng giao thức................................................................................................. 91
ii
Mục lục
4.1. Giao thức có trọng tài....................................................................................... 91
4.2. Giao thức có người phân xử ............................................................................ 92
4.3. Giao thức tự phân xử ....................................................................................... 93
5. Các dạng tấn công đối với giao thức....................................................................... 93
TÀI LIỆU THAM KHẢO ................................................................................................... 95
iii
Lời nói đầu
LỜI NÓI ĐẦU
Từ trước công nguyên con người đã phải quan tâm tới việc làm thế nào để đảm
bảo an toàn bí mật cho các tài liệu, văn bản quan trọng, đặc biệt là trong lĩnh vực quân
sự, ngoại giao. Ngày nay với sự xuất hiện của máy tính, các tài liệu văn bản giấy tờ và
các thông tin quan trọng đều được số hóa và xử lý trên máy tính, được truyền đi trong
một môi trường mà mặc định là không an toàn. Do đó yêu cầu về việc có một cơ chế, giải
pháp để bảo vệ sự an toàn và bí mật của các thông tin nhạy cảm, quan trọng ngày càng
trở nên cấp thiết. Mật mã học chính là ngành khoa học đảm bảo cho mục đích này. Khó
có thể thấy một ứng dụng Tin học có ích nào lại không sử dụng các thuật toán mã hóa
thông tin. Tài liệu này dựa trên những kinh nghiệm và nghiên cứu mà tác giả đã đúc rút,
thu thập trong quá trình giảng dạy môn học An toàn và Bảo mật Thông tin tại khoa Công
nghệ Thông tin, Đại học Hàng hải Việt nam. Với bảy chương được chia thành các chủ đề
khác nhau từ cơ sở toán học của mật mã học cho tới các hệ mã, các giao thức mật mã,
hy vọng sẽ cung cấp cho các em sinh viên, các bạn độc giả một tài liệu bổ ích. Mặc dù đã
rất cố gắng song vẫn không tránh khỏi một số thiếu sót, hy vọng sẽ được các bạn bè
đồng nghiệp, các em sinh viên, các bạn độc giả góp ý chân thành để tôi có thể hoàn thiện
hơn nữa tài liệu này.
Xin gửi lời cảm ơn chân thành tới các bạn bè đồng nghiệp và Ban chủ nhiệm khoa
Công nghệ Thông tin đã tạo điều kiện giúp đỡ để tài liệu này có thể hoàn thành.
Hải phòng, tháng 10 năm 2006
Tác giả
Nguyễn Hữu Tuân
1
Chương I: Giới thiệu
CHƯƠNG I: GIỚI THIỆU
1. An toàn bảo mật thông tin và mật mã học
Trải qua nhiều thế kỷ hàng loạt các giao thức (protocol) và các cơ chế (mechanism)
đã được tạo ra để đáp ứng nhu cầu an toàn bảo mật thông tin khi mà nó được truyền tải
trên các phương tiện vật lý (giấy, sách, báo …). Thường thì các mục tiêu của an toàn bảo
mật thông tin không thể đạt được nếu chỉ đơn thuần dựa vào các thuật toán toán học và
các giao thức, mà để đạt được điều này đòi hỏi cần có các kỹ thuật mang tính thủ tục và
sự tôn trọng các điều luật. Chẳng hạn sự bí mật của các bức thư tay là do sự phân phát
các lá thư đã có đóng dấu bởi một dịch vụ thư tín đã được chấp nhận. Tính an toàn về
mặt vật lý của các lá thư là hạn chế (nó có thể bị xem trộm) nên để đảm bảo sự bí mật
của bức thư pháp luật đã đưa ra qui định: việc xem thư mà không được sự đồng ý của
chủ nhân hoặc những người có thẩm quyền là phạm pháp và sẽ bị trừng phạt. Đôi khi
mục đích của an toàn bảo mật thông tin lại đạt được nhờ chính phương tiện vật lý mang
chúng, chẳng hạn như tiền giấy đòi hỏi phải được in bằng loại mực và giấy tốt để không
bị làm giả.
Về mặt ý tưởng việc lưu giữ thông tin là không có nhiều thay đổi đáng kể qua thời
gian. Ngày xưa thông tin thường được lưu và vận chuyển trên giấy tờ, trong khi giờ đây
chúng được lưu dưới dạng số hóa và được vận chuyển bằng các hệ thống viễn thông
hoặc các hệ thống không dây. Tuy nhiên sự thay đổi đáng kể đến ở đây chính là khả
năng sao chép và thay đổi thông tin. Người ta có thể tạo ra hàng ngàn mẩu tin giống nhau
và không thể phân biệt được nó với bản gốc. Với các tài liệu lưu trữ và vận chuyển trên
giấy điều này khó khăn hơn nhiều. Và điều cần thiết đối với một xã hội mà thông tin hầu
hết được lưu trữ và vận chuyển trên các phương tiện điện tử chính là các phương tiện
đảm bảo an toàn bảo mật thông tin độc lập với các phương tiện lưu trữ và vận chuyển vật
lý của nó. Phương tiện đó chính là mật mã học, một ngành khoa học có lịch sử lâu đời
dựa trên nền tảng các thuật toán toán học, số học, xác suất và các môn khoa học khác.
2. Khái niệm hệ thống và tài sản của hệ thống
Khái niệm hệ thống: Hệ thống là một tập hợp các máy tính gồm các thành phần
phấn cứng, phần mềm và dữ liệu làm việc được tích luỹ qua thời gian.
Tài sản của hệ thống bao gồm:
•
•
•
•
•
•
Phần cứng
Phần mềm
Dữ liệu
Các truyền thông giữa các máy tính của hệ thống
Môi trường làm việc
Con người
3. Các mối đe doạ đối với một hệ thống và các biện pháp ngăn chặn
Có 3 hình thức chủ yếu đe dọa đối với hệ thống:
2
Chương I: Giới thiệu
•
•
Phá hoại: kẻ thù phá hỏng thiết bị phần cứng hoặc phần mềm hoạt động trên hệ
thống.
Sửa đổi: Tài sản của hệ thống bị sửa đổi trái phép. Điều này thường làm cho hệ
thống không làm đúng chức năng của nó. Chẳng hạn như thay đổi mật khẩu,
quyền người dùng trong hệ thống làm họ không thể truy cập vào hệ thống để
làm việc.
•
Can thiệp: Tài sản bị truy cập bởi những người không có thẩm quyền. Các
truyền thông thực hiện trên hệ thống bị ngăn chặn, sửa đổi.
Các đe dọa đối với một hệ thống thông tin có thể đến từ nhiều nguồn và được thực
hiện bởi các đối tượng khác nhau. Chúng ta có thể chia thành 3 loại đối tượng như sau:
các đối tượng từ ngay bên trong hệ thống (insider), đây là những người có quyền truy cập
hợp pháp đối với hệ thống, những đối tượng bên ngoài hệ thống (hacker, cracker),
thường các đối tượng này tấn công qua những đường kết nối với hệ thống như Internet
chẳng hạn, và thứ ba là các phần mềm (chẳng hạn như spyware, adware …) chạy trên hệ
thống.
Các biện pháp ngăn chặn:
Thường có 3 biện pháp ngăn chặn:
•
•
•
Điều khiển thông qua phần mềm: dựa vào các cơ chế an toàn bảo mật của hệ
thống nền (hệ điều hành), các thuật toán mật mã học
Điều khiển thông qua phần cứng: các cơ chế bảo mật, các thuật toán mật mã
học được cứng hóa để sử dụng
Điều khiển thông qua các chính sách của tổ chức: ban hành các qui định của tổ
chức nhằm đảm bảo tính an toàn bảo mật của hệ thống.
Trong môn học này chúng ta tập trung xem xét các thuật toán mật mã học như là
một phương tiện cơ bản, chủ yếu để đảm bảo an toàn cho hệ thống.
4. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin
Ba mục tiêu của an toàn bảo mật thông tin:
−
Tính bí mật: Tài sản của hệ thống chỉ được truy cập bởi những người có thẩm
quyền. Các loại truy cập gồm có: đọc (reading), xem (viewing), in ấn (printing), sử dụng
chương trình, hoặc hiểu biết về sự tồn tại của một đối tượng trong tổ chức.Tính bí mật có
thể được bảo vệ nhờ việc kiểm soát truy cập (theo nhiều kiểu khác nhau) hoặc nhờ các
thuật toán mã hóa dữ liệu. Kiếm soát truy cập chỉ có thể được thực hiện với các hệ thống
phần cứng vật lý. Còn đối với các dữ liệu công cộng thì thường phương pháp hiệu quả là
các phương pháp của mật mã học.
−
Tính toàn vẹn dữ liệu: tài sản của hệ thống chỉ được thay đổi bởi những người
có thẩm quyền.
−
Tính sẵn dùng: tài sản luôn sẵn sàng được sử dụng bởi những người có thẩm
quyền.
Hai nguyên tắc của an toàn bảo mật thông tin:
3
Chương I: Giới thiệu
−
Việc thẩm định về bảo mật phải là khó và cần tính tới tất cả các tình huống,
khả năng tấn công có thể được thực hiện.
−
Tài sản được bảo vệ cho tới khi hết gía trị sử dụng hoặc hết ý nghĩa bí mật.
5. Mật mã học (cryptology)
Mật mã học bao gồm hai lĩnh vực: mã hóa (cryptography) và thám mã
(cryptanalysis-codebreaking) trong đó:
−
Mã hóa: nghiên cứu các thuật toán và phương thức để đảm bảo tính bí mật và
xác thực của thông tin (thường là dưới dạng các văn bản lưu trữ trên máy tính). Các sản
phẩm của lĩnh vực này là các hệ mã mật, các hàm băm, các hệ chữ ký điện tử, các cơ
chế phân phối, quản lý khóa và các giao thức mật mã.
−
Thám mã: Nghiên cứu các phương pháp phá mã hoặc tạo mã giả. Sản phẩm
của lĩnh vực này là các phương pháp thám mã, các phương pháp giả mạo chữ ký, các
phương pháp tấn công các hàm băm và các giao thức mật mã.
Trong giới hạn của môn học này chúng ta chủ yếu tập trung vào tìm hiểu các vấn đề
mã hóa với các hệ mã mật, các hàm băm, các hệ chữ ký điện tử, các giao thức mật mã.
Mã hóa (cryptography) là một ngành khoa học của các phương pháp truyền tin bảo
mật. Trong tiếng Hy Lạp, “Crypto” (krypte) có nghĩa là che dấu hay đảo lộn, còn “Graphy”
(grafik) có nghĩa là từ. [3]
Người ta quan niệm rằng: những từ, những ký tự của bản văn bản gốc có thể hiểu
được sẽ cấu thành nên bản rõ (P-Plaintext), thường thì đây là các đoạn văn bản trong
một ngôn ngữ nào đó; còn những từ, những ký tự ở dạng bí mật không thể hiểu được thì
được gọi là bản mã (C-Ciphertext).
Có 2 phương thức mã hoá cơ bản: thay thế và hoán vị:
−
Phương thức mã hoá thay thế là phương thức mã hoá mà từng ký tự gốc hay
một nhóm ký tự gốc của bản rõ được thay thế bởi các từ, các ký hiệu khác hay kết hợp
với nhau cho phù hợp với một phương thức nhất định và khoá.
−
Phương thức mã hoá hoán vị là phương thức mã hoá mà các từ mã của bản
rõ được sắp xếp lại theo một phương thức nhất định.
Các hệ mã mật thường sử dụng kết hợp cả hai kỹ thuật này.
6. Khái niệm hệ mã mật (CryptoSystem)
Một hệ mã mật là bộ 5 (P, C, K, E, D) thoả mãn các điều kiện sau:
1)
2)
3)
4)
P là không gian bản rõ: là tập hữu hạn các bản rõ có thể có.
C là không gian bản mã: là tập hữu hạn các bản mã có thể có.
K là kkhông gian khoá: là tập hữu hạn các khoá có thể có.
Đối với mỗi k ∈ K, có một quy tắc mã hoá ek ∈ E và một quy tắc giải mã
tương ứng dk ∈ D. Với mỗi ek: P →C và dk: C →P là những hàm mà dk(ek(x)) = x cho mọi
bản rõ x ∈ P. Hàm giải mã dk chính là ánh xạ ngược của hàm mã hóa ek [5]
4
Chương I: Giới thiệu
Thường thì không gian các bản rõ và không gian các bản mã là các văn bản được
tạo thành từ một bộ chữ cái A nào đó. Đó có thể là bộ chữ cái tiếng Anh, bộ mã ASCII,
bộ mã Unicode hoặc đơn giản nhất là các bit 0 và 1.
Tính chất 4 là tính chất quan trọng nhất của mã hoá. Nội dung của nó nói rằng nếu
mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng hàm dk thì kết quả nhận
được phải là bản rõ ban đầu x. Rõ ràng trong trường hợp này, hàm ek(x) phải là một đơn
ánh, nếu không thì ta sẽ không giải mã được. Vì nếu tồn tại x1 và x2 sao cho y = ek(x1) =
ek(x2) thì khi nhận được bản mã y ta không biết nó được mã từ x1 hay x2.
Trong một hệ mật bất kỳ ta luôn có |C| ≥ |P| vì mỗi quy tắc mã hoá là một đơn ánh.
Khi |C| = |P| thì mỗi hàm mã hoá là một hoán vị.
7. Mô hình truyền tin cơ bản của mật mã học và luật Kirchoff
Mô hình truyền tin thông thường: Trong mô hình truyền tin thông thường thông tin
được truyền (vận chuyển) từ người gửi đến người nhận được thực hiện nhờ một kênh vật
lý (chẳng hạn như việc gửi thư) được coi là an toàn.
Mô hình truyền tin cơ bản của mật mã học:
K1
K2
Insecured
Channel
Encrypt
Decrypt
Sender
Receiver
X
Y
Y
X
Enemy
Hình 1.1: Mô hình cơ bản của truyền tin bảo mật
Đây là mô hình cơ bản của truyền tin bảo mật. Khác với truyền tin thông thường, có
các yếu tố mới được thêm vào như khái niệm kẻ địch (E-Enemy), các khoá mã hoá và
giải mã K để đảm bảo tính bảo mật của thông tin cần truyền đi.
Trong mô hình này người gửi S (Sender) muốn gửi một thông điệp X (Message – là
một bản rõ) tới người nhận R (Receiver) qua một kênh truyền không an toàn (Insecured
Channel), kẻ địch E (Enemy) có thể nghe trộm, hay sửa đổi thông tin X. Vì vậy, S sử dụng
phép biến đổi, tức mã hoá (E-Encryption) lên thông tin X ở dạng đọc được (Plaintext) để
tạo ra một đoạn văn bản được mã hoá Y (C-Ciphertext) không thể hiểu được theo một
quy luật thông thường sử dụng một thông tin bí mật được gọi là khoá K1 (Key), khoá K1
chính là thông số điều khiển cho phép biến đổi từ bản rõ X sang bản mã Y (chỉ các bên
tham gia truyền tin S và R mới có thể biết khóa này). Giải mã (D-Decryption) là quá trình
ngược lại cho phép người nhận thu được thông tin X ban đầu từ đoạn mã hoá Y sử dụng
khóa giải mã K2 (chú ý là khóa giải mã và khóa mã hóa có thể khác nhau hoặc là một tùy
thuộc vào hệ mã sử dụng).
Các phép biến đổi được sử dụng trong mô hình truyền tin trên thuộc về một hệ mã
mật (Cryptosytem) nào đó.
5
Chương I: Giới thiệu
Quá trình mã hóa và giải mã yêu cầu các quá trình biến đổi dữ liệu từ dạng nguyên
thuỷ thành in put cho việc mã hóa và chuyển output của quá trình giải mã thành bản rõ.
Các quá trình này là các quá trình biến đổi không khóa và được gọi là các quá trình
encode và decode.
Theo luật Kirchoff (1835 - 1903) (một nguyên tắc cơ bản trong mã hoá) thì: toàn bộ
cơ chế mã/giải mã trừ khoá là không bí mật đối với kẻ địch [5]. Rõ ràng khi đối phương
không biết được hệ mã mật đang sử dụng thuật toán mã hóa gì thì việc thám mã sẽ rất
khó khăn. Nhưng chúng ta không thể tin vào độ an toàn của hệ mã mật chỉ dựa vào một
giả thiết không chắc chắn là đối phương không biết thuật toán đang sử dụng. Vì vậy, khi
trình bày một hệ mật bất kỳ, chúng ta đều giả thiết hệ mật đó được trình bày dưới luật
Kirchoff.
Ý nghĩa của luật Kirchoff: sự an toàn của các hệ mã mật không phải dựa vào sự
phức tạp của thuật toán mã hóa sử dụng.
8. Sơ lược về lịch sử mật mã học
Mật mã học là một ngành khoa học có một lịch sử khoảng 4000 năm. Các cổ vật
của ngành khảo cổ học thu được đã cho thấy điều này. Những người Ai cập cổ đại đã sử
dụng các chữ tượng hình như là một dạng mã hóa đơn giản nhất trên các bia mộ của họ.
Các tài liệu viết tay khác cũng cho thấy các phương pháp mã hóa đơn giản đầu tiên mà
loài người đã sử dụng là của người Ba Tư cổ và người Do Thái cổ.
Tuy vậy có thể chia lịch sử mật mã học thành hai thời kỳ như sau:
Thời kỳ tiền khoa học: Từ trước công nguyên cho tới năm 1949. Trong giai đoạn
này mật mã học được coi là một nghệ thuật nhiều hơn là một môn khoa học mặc dù đã
được ứng dụng trong thực tế.
Lịch sử của mật mã học được đánh dấu vào năm 1949 khi Claude Shannon đưa ra
lý thuyết thông tin. Sau thời kỳ này một loạt các nghiên cứu quan trọng của nghành mật
mã học đã được thực hiện chẳng hạn như các nghiên cứu về mã khối, sự ra đời của các
hệ mã mật khóa công khai và chữ ký điện tử.
Qua nhiều thế kỷ phát triển của mật mã học chủ yếu được phục vụ cho các mục
đích quân sự (gián điệp, ngoại giao, chiến tranh…). Một ví dụ điển hình là 2000 năm
trước đây hoàng đế La mã Julius Caesar đã từng sử dụng một thuật toán thay thế đơn
giản mà ngày nay được mang tên ông trong cuộc chiến tranh Gallic.
Tác phẩm “A manuscript on Deciphering Cryptography Messages” của Abu al-Kindi
được viết vào thế kỷ thứ 9 được tìm thấy tại Istabul vào năm 1987 đã cho thấy những nhà
khoa học Ả rập là những người đầu tiên đã phát triển các phương pháp thám mã dựa vào
phân tích tần số xuất hiện của các ký tự đối với các hệ mã thay thế đơn âm (một phương
pháp được sử dụng rộng rãi trong thời kỳ Trung cổ do đơn giản và khá hiệu quả).
Ở châu Âu thời kỳ Trung cổ là một khoảng thời gian u ám và tăm tối của lịch sử nên
không có nhiều phát triển mạnh về văn hóa nói chung và mật mã học nói riêng. Một vài
sự kiện được ghi lại bởi các vị linh mục nhưng chỉ có Roger Bacon là người thực sự đã
viết về mật mã học trong tác phẩm “Secret Work of Art and the Nullity of Magic” vào giữa
những năm 1200. Vào thời Trung cổ một trong những cái tên nổi tiếng nhất là Chaucer,
người đã đưa ra các công trình nghiên cứu nghiêm túc đầu tiên về mật mã học trong các
6
Chương I: Giới thiệu
tác phẩm của mình chẳng hạn như “Treatise on the Astrolabe”. Trong thời kỳ Trung cổ ở
phương Tây cuốn sách của Blaise De Vegenere (người phát minh ra thuật toán mã hóa
thay thế đa âm tiết) được xem như là một tổng kết các kiến thức về mật mã học cho tới
thời điểm bấy giờ, bao gồm cả thuật toán thay thế đa âm tiết và một vài sơ đồ khóa tự
động.
Blaise De Vegenere cũng là tác giả của hệ mã mang tên ông, hệ mã này đã từng
được xem là an toàn tuyệt đối và được sử dụng trong một thời gian dài tuy nhiên Charles
Babbages đã thực hiện thám mã thành công vào năm 1854 nhưng điều này được giữ bí
mật. Một thuật toán thám mã được phát hiện độc lập bởi một nhà khoa học người Nga có
tên là Friedrich Kasiski. Tuy vậy do việc thiếu các thiết bị cải tiến nên các biến thể của
thuật toán mã hóa này vẫn còn được sử dụng trong những năm đầu của thế kỷ 20 mà
tiêu biểu nhất là việc thám mã thành công máy điện tín Zimmermann của quân Đức (một
trong các sự kiện tiêu biểu của mật mã học) trong thế chiến thứ nhất và kết quả là sự
tham gia của Mỹ vào cuộc chiến.
Với sự xuất hiện của các hệ thống máy tính cá nhân và mạng máy tính các thông tin
văn bản ngày càng được lưu trữ và xử lý nhiều hơn trên các máy tính do đó nảy sinh yêu
cầu về an toàn bảo mật đối với các thông tin được lưu trữ, xử lý và truyền giữa các máy
tính.
Vào đầu những năm 1970 là sự phát triển của các thuật toán mã hóa khối đầu tiên:
Lucipher và DES. DES sau đó đã có một sự phát triển ứng dụng rực rỡ cho tới đầu
những năm 90.
Vào cuối những năm 1970 chứng kiến sự phát triển của các thuật toán mã hóa
khóa công khai sau khi Whitfield Diffie và Martin Hellman công bố bài báo làm nền tảng
cho sự ra đời của các hệ mã khóa công khai và các hệ chữ ký điện tử.
Do nhược điểm của các hệ mã mật khóa công khai là chậm nên các hệ mã khối vẫn
tiếp tục được phát triển với các hệ mã khối mới ra đời để thay thế cho DES vào cuối thế
kỷ 20.
Gần đây nhất là các sự kiện liên quan tới các hàm băm MD5 (một hàm băm thuộc
họ MD do Ron Rivest phát triển) và SHA1. Một nhóm các nhà khoa học người Trung
Quốc (Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu) đã phát triển các phương pháp cho
phép phát hiện ra các đụng độ của các hàm băm được sử dụng rộng rãi nhất trong số các
hàm băm này. Đây là một sự kiện lớn đối với ngành mật mã học do sự ứng dụng rộng rãi
và có thể xem là còn quan trọng hơn bản thân các hệ mã mật của các hàm băm. Do sự
kiện này các hãng viết phần mềm lớn (như Microsoft) và các nhà mật mã học đã khuyến
cáo các lập trình viên sử dụng các hàm băm mạnh hơn (như SHA-256, SHA-512) trong
các ứng dụng.
Bruce Schneier (một trong những nhà mật mã học hàng đầu, tác giả của hệ mã
Blowfish) đã từng nói rằng các hình thức tấn công đối với các hệ mã mật nói riêng và tấn
công đối với các hệ thống máy tính nói chung sẽ ngày càng trở nên hoàn thiện hơn
“Attacks always get better; they never get worse.” và lịch sử phát triển của mật mã học
chính là lịch sử phát triển của các hình thức tấn công đối với các hệ mã mật đang được
sử dụng.
7
Chương I: Giới thiệu
9. Phân loại các thuật toán mật mã học
Có nhiều cách khác nhau để chúng ta có thể phân loại các thuật toán mật mã học
sẽ được học trong chương trình. Ở đây chúng ta sẽ phân loại các thuật toán mật mã học
dựa vào hai loại tiêu chí.
Tiêu chí thứ nhất là dựa vào các dịch vụ an toàn bảo mật mà các thuật toán cung
cấp, dựa vào số lượng khóa sử dụng (0, 1, 2) chúng ta có các thuật toán mã hóa sau:
1. Các thuật toán mã hóa khóa bí mật tương ứng với các hệ mã mật khóa bí mật
hay khóa đối xứng SKC (Symmetric Key Cryptosytems), do vai trò của người nhận và
người gửi là như nhau, cả hai đều có thể mã hóa và giải mã thông điệp, như Caesar,
DES, AES … Khóa sử dụng cho các thuật toán này là 1 khóa cho cả việc mã hóa và giải
mã.
2. Các thuật toán mã hóa khóa công khai tương ứng với các hệ mã khóa công
khai PKC (Public Key Cryptosystems). Đôi khi các hệ mã này còn được gọi là các hệ mã
khóa bất đối xứng (Asymmetric Key Cryptosytems). Khóa sử dụng cho các thuật toán này
là 2 khóa, một cho việc mã hóa và một cho việc giải mã, khóa mã hóa được công khai
hóa.
3. Các thuật toán tạo chữ ký điện tử (Digital Signature Algorithms). Các thuật
toán tạo chữ ký điện tử tạo thành các hệ chữ ký điện tử. Thông thường mỗi hệ chữ ký
điện tử có cùng cơ sở lý thuyết với một hệ mã mật khóa công khai nhưng với cách áp
dụng khác nhau. Trong chương trình học chúng ta sẽ học một số hệ chữ ký điện tử phổ
biến là RSA, ElGammma…
4. Các hàm băm (Hash functions). Các hàm băm là các thuật toán mã hóa không
khóa hoặc có khóa và thường được sử dụng trong các hệ chữ ký điện tử hoặc các hệ mã
khóa công khai.
Tiêu chí thứ hai phân loại các thuật toán mã hóa dựa trên cách thức xử lý input của
thuật toán (tức là bản rõ), dựa trên tiêu chí này chúng ta có hai loại thuật toán mã hóa
sau:
1. Các thuật toán mã hóa khối (chẳng hạn như DES, AES …) xử lý bản rõ dưới
các đơn vị cơ bản là các khối có kích thước giống nhau.
2. Các thuật toán mã hóa dòng (RC4 …) coi bản rõ là một luồng bit, byte liên tục.
10. Một số ứng dụng của mật mã học
Ngày nay khó có thể tìm thấy các ứng dụng trên máy tính lại không sử dụng tới các
thuật toán và các giao thức mật mã học. Từ các ứng dụng cho các máy tính cá nhân
(Desktop Applications) cho tới các chương trình hệ thống như các hệ điều hành
(Operating Systems) hoặc các ứng dụng mạng như Yahoo Messenger hoặc các hệ cơ sở
dữ liệu đều có sử dụng các thuật toán mã hóa mật khẩu người dùng bằng một hệ mã
hoặc một hàm băm nào đó. Đặc biệt với sự phát triển mạnh mẽ của thương mại điện tử
các mô hình chữ ký điện tử ngày càng đóng vai trò tích cực cho một môi trường an toàn
cho người dùng. Tuy vậy chúng ta vẫn có thể chia các lĩnh vực ứng dụng của mật mã học
thành các lĩnh vực nhỏ như sau:
8
Chương I: Giới thiệu
−
Bảo mật (Confidentiality): che dấu nội dung của các thông điệp được trao đổi
trong một phiên truyền thông hoặc giao dịch hoặc các thông điệp trên một hệ thống máy
tính (các file, các dữ liệu trong một cơ sở dữ liệu …).
−
Xác thực hóa (Authentication): đảm bảo nguồn gốc của một thông điệp, người
dùng.
−
Toàn vẹn (Integrity): đảm bảo chỉ có các tổ chức đã được xác thực hóa mới có
thể thay đổi các tài sản của hệ thống cũng như các thông tin trên đường truyền.
Dịch vụ không thể chối từ (Non-Repudiation): Các bên đã được xác thực
không thể phủ nhận việc tham gia vào một giao dịch hợp lệ.
Ngoài ra còn các dịch vụ quan trọng khác chẳng hạn như chữ ký điện tử, dịch
−
−
vụ chứng thực danh tính (Identification) cho phép thay thế hình thức xác thực hóa người
dùng dựa trên các mật khẩu bằng các kỹ thuật mạnh hơn hoặc dịch vụ thương mại điện
tử cho phép tiến hành các giao dịch an toàn trên các kênh truyền thông không an toàn
như Internet.
9
Chương II: Cơ sở toán học
CHƯƠNG II: CƠ SỞ TOÁN HỌC
Để hiểu được những thuật toán sử dụng trong các hệ mã mật, trong các hệ chữ ký
điện tử cũng như các giao thức mật mã, chúng ta phải có những kiến thức nền tảng cơ
bản về toán học, lý thuyết thông tin … được sử dụng trong mật mã học. Chương này trình
bày những khái niệm cơ bản về lý thuyết thông tin như Entropy, tốc độ của ngôn ngữ
(Rate of Language), độ phức tạp của thuật toán, độ an toàn của thuật toán, và một số
kiến thức toán học: đồng dư số học (modulo), số nguyên tố, định lý phần dư trung hoa,
định lý Fermat . . . và các thuật toán kiểm tra số nguyên tố. Những vấn đề chính sẽ được
trình bày trong chương này gồm :
• Lý thuyết thông tin
• Lý thuyết độ phức tạp
• Lý thuyết số học.
1. Lý thuyết thông tin
Những khái niệm mở đầu của lý thuyết thông tin được đưa ra lần đầu tiên vào năm
1948 bởi Claude Elmwood Shannon (một nhà khoa học được coi là cha để của lý thuyết
thông tin). Trong phần này chúng ta chỉ đề cập tới một số chủ đề quan trọng của lý thuyết
thông tin.
1.1. Entropy
Lý thuyết thông tin định nghĩa khối lượng thông tin trong một thông báo là số bít nhỏ
nhất cần thiết để mã hoá tất cả những nghĩa có thể của thông báo đó.
Ví dụ, trường ngay_thang trong một cơ sở dữ liệu chứa không quá 3 bít thông tin,
bởi vì thông tin ngày có thể mã hoá với 3 bít dữ liệu:
000 = Sunday
001 = Monday
010 = Tuesday
011 = Wednesday
100 = Thursday
101 = Friday
110 = Saturday
111 is unused
Nếu thông tin này được biểu diễn bởi chuỗi ký tự ASCII tương ứng, nó sẽ chiếm
nhiều không gian nhớ hơn, nhưng cũng không chứa nhiều thông tin hơn. Tương tự như
trường gioi_tinh của một cơ sở dữ liệu chỉ chứa 1 bít thông tin, nó có thể lưu trữ như một
trong hai xâu ký tự ASCII : Nam, Nữ.
Khối lượng thông tin trong một thông báo M đo bởi Entropy của thông báo đó, ký
hiệu là H(M). Entropy của thông báo gioi_tinh là 1 bít, ký hiệu H(gioi_tinh) = 1, Entropy
của thông báo số ngày trong tuần là nhỏ hơn 3bits.
10
Chương II: Cơ sở toán học
Trong trường hợp tổng quát, Entropy của một thông báo là log2n, với n là số khả
năng có thể (ý nghĩa) của thông báo.
H(M) = log2n
1.2. Tốc độ của ngôn ngữ. (Rate of Language)
Đối với một ngôn ngữ, tốc độ thực tế (actual rate) của ngôn ngữ là:
r = H(M)/N
trong trường hợp này N là độ dài của thông báo và M là một thông điệp có độ dài N.
Tốc độ của tiếng Anh bình thường là 0.28 do đó mỗi chữ cái tiếng Anh có 1.3 bit nghĩa.
Tốc độ tuyệt đối (absolute rate) của một ngôn ngữ là số bits lớn nhất cần thiết để
mã hóa các ký tự của ngôn ngữ đó. Nếu có L ký tự trong một ngôn ngữ, thì tốc độ tuyệt
đối là :
R = log2L
Đây là số Entropy lớn nhất của mỗi ký tự đơn lẻ. Đối với tiếng Anh gồm 26 chữ cái,
tốc độ tuyệt đối là log226 = 4.7bits/chữ cái. Sẽ không có điều gì là ngạc nhiên đối với tất
cả mọi người rằng thực tế tốc độ của tiếng Anh nhỏ hơn nhiều so với tốc độ tuyệt đối, và
chúng ta vẫn thấy rằng đối với một thông báo bằng tiếng Anh có thể loại bỏ một số chữ
cái nhưng người đọc vẫn có thể hiểu được. Hiện tượng này được gọi là độ dư thừa của
ngôn ngữ (Redundancy) tự nhiên.
Không chỉ đối với tiếng Anh mà với hầu hết các ngôn ngữ tự nhiên, do cấu trúc của
ngôn ngữ, do việc sử dụng ngôn ngữ dẫn tới có một số chữ cái được sử dụng với tần
suất không đồng đều hoặc chỉ có thể xuất hiện với một cấu trúc nào đó làm cho chúng ta
vẫn có thể đoán được nghĩa của các thông báo nếu loại bỏ các chữ cái này.
Độ dư thừa (Redundancy) của một ngôn ngữ ký hiệu là D và D = R – r. Đối với
tiếng Anh:
D = 1 - .28 = .72 letters/letter
D = 4.7 – 1.3 = 3.4 bits/letter
Như vậy mỗi chữ cái có 1.3 bit nghĩa và 3.4 bit dư thừa (xấp xỉ 72%).
1.3. Tính an toàn của hệ thống mã hoá
Shannon định nghĩa rất rõ ràng, tỉ mỉ các mô hình toán học để đánh giá độ an toàn
của các hệ mã mật sử dụng. Mục đích của người thám mã là phát hiện ra khoá sử dụng
của hệ mã (K-Key), bản rõ (P-PlainText), hoặc cả hai. Hơn nữa họ có thể hài lòng với
một vài thông tin có khả năng về bản rõ P chẳng hạn như đó là âm thanh dạng số, hoặc
là một văn bản tiếng Đức, hoặc là một bảng tính dữ liệu, v. v . . .
Trong hầu hết các lần thám mã, người thám mã thường cố gắng thu thập một số
thông tin có khả năng về bản rõ P trước khi bắt đầu. Họ có thể biết ngôn ngữ đã được sử
dụng để mã hoá. Ngôn ngữ này chắc chắn có sự dư thừa kết hợp với chính ngôn ngữ đó.
11
Chương II: Cơ sở toán học
Nếu nó là một thông báo gửi tới Bob, nó có thể bắt đầu với "Dear Bob". Đoạn văn bản
"Dear Bob" sẽ là một khả năng có thể hơn là một chuỗi không mang ý nghĩa gì chẳng hạn
"tm*h&rf". Mục đích của việc thám mã là sửa những tập hợp khả năng có thể có của bản
mã (C-CipherText) với mỗi khả năng có thể của bản rõ.
Shannon phát triển lý thuyết cho rằng, hệ thống mã hoá chỉ an toàn tuyệt đối nếu
nếu số khoá có thể sử dụng ít nhất phải bằng số thông báo có thể. Hiểu theo một nghĩa
khác, khoá tối thiểu của hệ mã phải dài bằng thông báo của hệ mã đó.
Ngoại trừ các hệ mã an toàn tuyệt đối, các bản mã thường chứa một số thông tin
đúng với bản rõ, điều này là không thể tránh được. Một thuật toán mật mã tốt giữ cho
thông tin bị tiết lộ ở mức nhỏ nhất và một người thám mã giỏi sẽ khai thác tốt những
thông tin này để phát hiện ra bản rõ.
Người thám mã sử dụng sự dư thừa tự nhiên của ngôn ngữ để làm giảm số khả
năng có thể có của bản rõ. Nhiều thông tin dư thừa của ngôn ngữ, sẽ dễ dàng hơn cho
quá trình thám mã. Chính vì lý do này mà nhiều mô hình mã hóa sử dụng thuật toán nén
bản rõ để giảm kích thước văn bản trước khi mã hoá chúng. Vì quá trình nén làm giảm sự
dư thừa của thông báo. Entropy của một hệ mã mật là kích thước của không gian khoá
(Keyspace).
H(K) = log2(number of keys )
Shannon cũng đưa ra một khái niệm gọi là Unicity Distance (ký hiệu là U) để đánh
giá độ an toàn của một hệ mã mật. Đối với một hệ mã mật U của nó là:
U = H(K)/D
Đây là số nhỏ nhất các bản mã cần thiết để có thể tiến hành thám mã theo cách thử
tất cả các khóa có thể (brute-force attack) thành công. Chẳng hạn đối với hệ mã thay thế
đơn âm (như Caesar) trên bảng chữ cái tiếng Anh ta sẽ có:
H(K)= log226! = 87. D = 3.4 suy ra U = 25.5.
Điều này có nghĩa là nếu chúng ta có khoảng 25 chữ cái bản mã chúng ta chỉ có thể
thử để khớp với một bản rõ.
Khái niệm Unicity Distance là một khái niệm mang tính xác suất nó cho chúng ta
biết số lượng ít nhất các bản mã cần có để có thể xác định duy nhất 1 bản mã chứ không
phải là số bản mã đủ để tiến hành thám mã (chắc chắn thành công). Nếu chúng ta có số
bản mã ít hơn số U thì không thể nói là dự đoán (phép thử) của chúng ta là đúng. Dựa
vào công thức này chúng ta thấy nếu như độ dư thừa của ngôn ngữ càng gần 0 thì càng
khó thám mã mặc dù đó có thể là một hệ mã rất đơn giản. Cũng dựa vào công thức này
suy ra để tăng tính an toàn của hệ mã có thể tăng không gian khóa của nó.
1.4. Kỹ thuật lộn xộn và rườm rà (Confusion and Diffusion)
Theo Shannon, có hai kỹ thuật cơ bản để che dấu sự dư thừa thông tin trong thông
báo gốc, đó là: sự lộn xộn và sự rườm rà.
Kỹ thuật lộn xộn (Confusion): che dấu mối quan hệ giữa bản rõ và bản gốc. Kỹ
thuật này làm thất bại các cố gắng nghiên cứu bản mã để tìm kiếm thông tin dư thừa và
thống kê mẫu. Phương pháp dễ nhất để thực hiện điều này là thông qua kỹ thuật thay
12
Chương II: Cơ sở toán học
thế. Một hệ mã hoá thay thế đơn giản, chẳng hạn hệ mã dịch vòng Caesar, dựa trên nền
tảng của sự thay thế các chữ cái của bản rõ, nghĩa là chữ cái này được thay thế bằng
chữ cái khác
Kỹ thuật rườm rà (Diffusion): làm mất đi sự dư thừa của bản rõ bằng cách tăng
sự phụ bản mã vào bản rõ (và khóa). Công việc tìm kiếm sự dư thừa của người thám mã
sẽ rất mất thời gian và phức tạp. Cách đơn giản nhất tạo ra sự rườm rà là thông qua việc
đổi chỗ (hay còn gọi là kỹ thuật hoán vị).
Thông thường các hệ mã hiện đại thường kết hợp cả hai kỹ thuật thay thế và hoán
vị để tạo ra các thuật toán mã hóa có độ an toàn cao hơn.
2. Lý thuyết độ phức tạp
Lý thuyết độ phức tạp cung cấp một phương pháp để phân tích độ phức tạp tính
toán của thuật toán và các kỹ thuật mã hoá khác nhau. Nó so sánh các thuật toán mã
hoá, kỹ thuật và phát hiện ra độ an toàn của các thuật toán đó. Lý thuyết thông tin đã cho
chúng ta biết rằng một thuật toán mã hoá có thể bị bại lộ. Còn lý thuyết độ phức tạp cho
biết khả năng bị thám mã của một hệ mã mật.
Độ phức tạp thời gian của thuật toán là một hàm của kích thước dữ liệu input của
thuật toán đó. Thuật toán có độ phức tạp thời gian f(n) đối với mọi n và kích thước input
n, nghĩa là số bước thực hiện của thuật toán lớn hơn f(n) bước.
Độ phức tạp thời gian thuật toán phụ thuộc vào mô hình của các thuật toán, số các
bước nhỏ hơn nếu các hoạt động được tập trung trong một bước (chẳng hạn như các
vòng lặp, các lời gọi hàm …).
Các lớp của thuật toán, với độ phức tạp thời gian là một hàm mũ đối với kích thước
input được coi là "không có khả năng thực hiện". Các thuật toán có độ phức tạp giống
nhau được phân loại vào trong các lớp tương đương. Ví dụ tất cả các thuật toán có độ
phức tạp là n3 được phân vào trong lớp n3 và ký hiệu bởi O(n3). Có hai lớp tổng quát sẽ
được là lớp P (Polynomial) và lớp NP (NonPolynomial).
Các thuật toán thuộc lớp P có độ phức tạp là hàm đa thức của kích thước input.
Nếu mỗi bước tiếp theo của thuật toán là duy nhất thì thuật toán gọi là đơn định. Tất cả
thuật toán thuộc lớp P đơn định có thời gian giới hạn là P_time, điều này cho biết chúng
sẽ thực hiện trong thời gian đa thức, tương đương với độ phức tạp đa thức của kích
thước input.
Thuật toán mà ở bước tiếp theo việc tính toán phải lựa chọn giải pháp từ những
giới hạn giá trị của hoạt động gọi là không đơn định. Lý thuyết độ phức tạp sử dụng các
máy đặc biệt mô tả đặc điểm bằng cách đưa ra kết luận bởi các chuẩn. Máy Turing là
một máy đặc biệt, máy hoạt động trong thời gian rời rạc, tại một thời điểm nó nằm trong
khoảng trạng thái đầy đủ số của tất cả các trạng thái có thể là hữu hạn. Chúng ta có thể
định nghĩa hàm độ phức tạp thời gian kết hợp với máy Turing A.
fA(n) = max{m/A kết thúc sau m bước với đầu vào w = n3 }
Ở đây chúng ta giả sử rằng A là trạng thái kết thúc đối với tất cả các đầu vào, vấn
đề sẽ trở nên khó khăn hơn nếu các trạng thái không nằm trong P . Máy Turing không
đơn định hoạt động với thuật toán NP. Máy Turing không đơn định có thể có một vài trạng
13
Chương II: Cơ sở toán học
thái chính xác. S(w) là trạng thái đo sự thành công ngắn nhất của thuật toán, (Nghĩa là sự
tính toán dẫn đến trạng thái cuối cùng)
Hàm số độ phức tạp thời gian của máy Turing không đơn định A được định nghĩa :
fA(n)=max{1,m/s(w) có m bước đối với w/w=n}
ở mỗi bước máy Turing không đơn định bố trí nhiều bản sao của chính nó như có
một vài giải pháp và tính toán độc lập với mọi lời giải.
Các thuật toán thuộc lớp NP là không đơn định và có thể tính toán trên máy Turing
không đơn định trong thời gian P.
Tuy nhiên không phải thuật toán mã hóa càng có độ phức tạp lớn thì hệ mã mật sử
dụng thuật toán đó sẽ càng an toàn theo như phát biểu của luật Kierchoff.
Vậy có thể đánh giá độ an toàn của một hệ mã mật như thế nào? Vấn đề này đã
được Claude Shannon trả lời với các khái niệm về độ an toàn của các hệ mã mật trong
một bài báo có tiêu đề “Lý thuyết thông tin của các hệ thống bảo mật” (1949).
2.1. Độ an toàn tính toán
Định nghĩa:
Một hệ mật được gọi là an toàn về mặt tính toán nếu có một thuật toán tốt nhất để
phá nó thì cần ít nhất N phép toán, với N là một số rất lớn nào đó. [10]
Tuy nhiên trong thực tế, không có một hệ mật nào chứng tỏ là an toàn theo định
nghĩa trên. Vì vậy, trên thực tế, người ta gọi hệ mật là “an toàn tính toán” nếu có một
thuật toán để phá nó nhưng đòi hỏi thời gian lớn đến mức không chấp nhận được (thuật
toán có độ phức tạp hàm mũ hoặc thuộc lớp các bài toán có độ phức tạp NP).
Một cách tiếp cận khác về độ “an toàn tính toán” là quy nó về một bài toán đã được
nghiên cứu kỹ và được coi là khó. Ví dụ như bài toán “phân tích ra thừa số nguyên tố của
một số n cho trước” được coi là bài toán khó với n lớn, vì vậy ta có thể coi một hệ mật
dựa trên bài toán “phân tích ra thừa số nguyên tố” là an toàn (tất nhiên đây chỉ là độ an
toàn dựa vào chứng minh một bài toán khác chứ không phải chứng minh hoàn chỉnh về
độ an toàn của hệ mật).
2.2. Độ an toàn không điều kiện
Định nghĩa 1:
Một hệ mật được coi là an toàn không điều kiện khi nó không thể bị phá ngay cả với
khả năng tính toán không hạn chế. [10]
Rõ ràng là “độ an toàn không điều kiện” không thể nghiên cứu theo quan điểm độ
phức tạp tính toán vì thời gian tính toán là không hạn chế. Vì vậy, ở đây lý thuyết xác suất
sẽ được đề cập để nghiên cứu về “an toàn không điều kiện”.
Định nghĩa 2:
Giả sử biến X và Y là các biến ngẫu nhiên. Ký hiệu xác suất để X nhận giá trị x là
p(x) và để Y nhận giá trị y là p(y). Xác suất đồng thời p(x, y) là xác suất để đồng thời X
nhận giá trị x và Y nhận giá trị y. Xác suất có điều kiện p(x/y) là xác suất để X nhận giá trị
14
Chương II: Cơ sở toán học
x với điều kiện Y nhận giá trị y. Các biến X và Y được gọi là độc lập nếu p(x, y) = p(x)p(y)
với mọi giá trị có thể có của X và Y.
Định lý Bayes:
Nếu p(y) ≠ 0 thì ta có:
p(x) p(y / x)
p(x / y) =
p(y)
Hệ quả:
X, Y là biến độc lập khi và chỉ khi p(x/y) = p(x) với mọi x, y. [5]
Ở đây, ta giả thiết rằng một khoá cụ thể chỉ được dùng cho một bản mã. Ký hiệu
xác suất tiên nghiệm để bản rõ xuất hiện là pp(x). Cũng giả thiết rằng khoá K được chọn
theo một phân bố xác suất nào đó (thông thường khoá K được chọn ngẫu nhiên nên các
khoá sẽ đồng khả năng). Ký hiệu xác suất khoá K được chọn là pk(K).
Giả thiết rằng khoá K và bản rõ x là các biến độc lập. Hai phân bố xác suất trên P
và K sẽ tạo ra một phân bố xác suất trên C . Ký hiệu C(K) là tập các bản mã có thể nếu
K là khoá.
∈
C (K) = { eK(x): x P }
∈
Khi đó với mỗi y C, ta có:
pC (y) =
pK (K).pp (dK (y))
∑
K ,y∈C(K )
Và xác suất có điều kiện pC(y/x) là xác suất để y là bản mã với điều kiện bản rõ là x
được tính theo công thức sau:
pC (y / x) =
p (K)
K
∑
K ,x=dK ( y)
Bây giờ ta có thể tính xác suất có điều kiện pP(x/y) là xác suất để x là bản rõ khi
bản mã là y theo định lý Bayes:
pP (x)
pK (K)
∑
pP (x)pC (y / x)
pC (y)
K,x=dK ( y)
pP (x / y) =
=
pK (K)pP (dK (y))
∑
K ,y∈C(K )
Lúc này, ta có thể định nghĩa khái niệm về độ mật hoàn thiện. Nói một cách không
hình thức, độ mật hoàn thiện nghĩa là đối phương với bản mã trong tay cũng không thể
thu nhận được thông tin gì về bản rõ. Tuy nhiên ta sẽ nêu định nghĩa chính xác về độ mật
hoàn thiện như sau:
Định nghĩa:
∈
∈
Một hệ mật hoàn thiện nếu pP(x/y) = pP(x) với mọi x P và mọi y C. Tức là xác
suất hậu nghiệm để thu được bản rõ là x với điều kiện đã thu được bản mã là y đồng nhất
với xác suất tiên nghiệm để bản rõ là x. [5]
15
Chương II: Cơ sở toán học
Hay nói cách khác, độ mật hoàn thiện cũng tương đương với pC(y/x)= pC(y)).
Định lý Shannon:
Giả sử (P, C, K, E, D) là một hệ mật, khi đó hệ mật đạt được độ mật hoàn thiện khi
và chỉ khi |K| ≥ |C|. Trong trường hợp |K| = |C| = |P|, hệ mật đạt độ mật hoàn thiện khi và
∈
chỉ khi mỗi khoá K được dùng với xác suất bằng nhau, bằng 1/|K| và với mỗi x P, mỗi
∈
y C có một khoá K duy nhất sao cho eK(x) = y. [5]
Như vậy ta thấy để đạt độ hoàn thiện đòi hỏi khoá phải rất dài, do vậy rất khó khăn
trong việc chuyển giao khoá giữa hai bên truyền tin. Vì vậy trong thực tế, chúng ta không
thể có an toàn không điều kiện mà chúng ta chỉ cần an toàn thực tế, tức là phụ thuộc vào
thông tin và thời gian cần bảo mật bằng cách sử dụng các hệ mật khác nhau với độ bảo
mật khác nhau.
3.3. Hệ mật tích
Một ý tưởng khác được Shannon đưa ra là ý tưởng tạo ra các hệ mật mới dựa trên
các hệ mật cũ bằng cách tạo tích của chúng. Đây là một ý tưởng quan trọng trong việc
thiết kế các hệ mật hiện đại ngày nay.
Để đơn giản, ở đây chúng ta chỉ xét các hệ mật trong đó C = P, các hệ mật loại này
gọi là tự đồng cấu. Giả sử S1 = (P, C, K1, E1, D1) và S2 = (P, C, K2, E2, D2) là các hệ
mật tự đồng cấu có cùng không gian bản rõ và bản mã. Khi đó hệ mật tích được định
×
nghĩa là hệ mật S = (P, C, K1 K2 ,E ,D). Khoá của hệ mật tích K = (K1, K2) trong đó K1
∈
∈
K1, K2 K2. Các hàm mã hoá và giải mã được xác định như sau:
e
(K ,K ) (x) = eK (eK (x))
1
2
2
1
d
(K ,K ) (x) = dK (eK (x))
1
2
1
2
Nếu chúng ta lấy tích của S với chính nó, ta có hệ mật (S×S) (ký hiệu S2). Nếu lấy
tích n lần thì kết quả là Sn. Ta gọi Sn là một hệ mật lặp. Nếu S2 = S thì ta gọi hệ mật là
luỹ đẳng. Nếu S là luỹ đẳng thì không nên lấy tích lặp vì độ bảo mật không tăng lên mà
không gian khoá lại lớn hơn. Đương nhiên nếu S không luỹ đẳng thì ta có thể lặp lại S
nhiều lần để tăng độ bảo mật. Ở đây nảy sinh một vấn đề là làm thế nào để có một hệ
mật không luỹ đẳng?
Ta biết rằng nếu S1 và S2 là luỹ đẳng và giao hoán thì S1×S2 cũng luỹ đẳng, đơn
giản vì:
(S1×S2)×(S1×S2) = S1×(S2×S1)×S2
= S1×(S1×S2)×S2
= (S1×S1)×(S2×S2)
= (S1×S2)
Vậy nếu muốn (S1×S2) không luỹ đẳng thì cần phải có S1 và S2 không giao hoán.
Điều này có thể dễ dàng thực hiện bằng cách lấy tích của một hệ mật theo kiểu thay thế
và một hệ mật theo kiểu hoán vị. Đây là kỹ thuật được dùng để thiết kế các hệ mã hiện
đại như mã DES.
16
Chương II: Cơ sở toán học
3. Lý thuyết toán học
3.1. Modulo số học
Về cơ bản a ≡ b(mod n) nếu a = b+kn trong đó k là một số nguyên. Nếu a và b
dương và a nhỏ hơn n, chúng ta có thể gọi a là phần dư của b khi chia cho n. Nói chung a
và b đều là phần dư khi chia cho n. Người ta còn gọ b là thặng dư của a theo modulo n,
và a là đồng dư của b theo modulo n.
Modulo số học cũng giống như số học bình thường, bao gồm các phép giao hoán,
kết hợp và phân phối. Mặt khác giảm mỗi giá trị trung gian trong suốt quá trình tính toán.
(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a- b) mod n = ((a mod n) - (b mod n)) mod n
(a×b) mod n = ((a mod n) × (b mod n)) mod n
(a×(b + c)) mod n = (((a × b) mod n) + ((a × c) mod n)) mod n
Các phép tính trong các hệ mã mật hầu hết đều thực hiện đối với một modulo N nào
đó.
3.2. Số nguyên tố
Số nguyên tố là một số lớn hơn 1, nhưng chỉ chia hết cho 1 và chính nó, ngoài ra
không còn số nào nó có thể chia hết nữa. Số 2 là một số nguyên tố đầu tiên và là số
nguyên tố chẵn duy nhất. Do vậy 7, 17, 53, 73, 2521, 2365347734339 cũng là số nguyên
tố. Số lượng số nguyên tố là vô tận. Hệ mật mã thường sử dụng số nguyên tố lớn cỡ 512
bits và thậm chí lớn hơn như vậy.
3.3. Ước số chung lớn nhất
Hai số a và n được gọi là hai số nguyên tố cùng nhau nếu chúng không có thừa số
chung nào khác 1, hay nói một cách khác, nếu ước số chung lớn nhất của a và n là bằng
1. Chúng ta có thể viết như sau :
GCD(a,n)=1, (GCD-Greatest Common Divisor)
Số 15 và 28 là hai số nguyên tố cùng nhau, nhưng 15 và 27 thì không phải là hai số
nguyên tố cùng nhau do có ước số chung là 1 và 3, dễ dàng thấy 13 và 500 cũng là một
cặp số nguyên tố cùng nhau. Một số nguyên tố sẽ là nguyên tố cùng nhau với tất cả các
số nguyên khác trừ các bội số của nó.
Một cách dễ nhất để tính toán ra ước số chung lớn nhất của hai số là nhờ vào thuật
toán Euclid. Knuth mô tả thuật toán và một vài mô hình của thuật toán đã được sửa đổi.
Dưới đây là đoạn mã nguồn trong ngôn ngữ C:
/* Thuật toán tìm ước số chung lớn nhất của x và y, giả sử x,y>0 */
int gcd(int x, int y)
{
int g;
if(x<0)
17
Tải về để xem bản đầy đủ
98 trang
18940
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình An toàn và bảo mật thông tin", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_an_toan_va_bao_mat_thong_tin.pdf
