Bài tập cơ sở lý thuyết mật mã năm 2024

Uploaded by

Tù Tội Toản

100% found this document useful (1 vote)

793 views

22 pages

mật mã học, cryptography

Copyright

© © All Rights Reserved

Available Formats

PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

100% found this document useful (1 vote)

793 views22 pages

Bài tập mật mã học

Uploaded by

Tù Tội Toản

mật mã học, cryptography

Jump to Page

You are on page 1of 22

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

1_classical_cryptosystem.pdf

1_mathematics of cryptography.pdf

00_cosotoanhoc_thuongk58.pdf

aes.pdf

aes_details.pdf

aesbyexample.pdf

crypto_chuong 1std.pdf

crypto_chuong 2std.pdf

crypto_chuong 3std.pdf

crypto_chuong 4std.pdf

crypto_chuong 5std.pdf

crypto_chuong 6std.pdf

fips-197.pdf

luythua.jpg

sha256-384-512.pdf

tailieu_ltmm.pdf

tailieu_ltmm_edit.pdf

[btl20171_98513]_nhom01_sha512.zip

baocao nhom 01.zip

btl nhom 01.zip

cac_thuat_ngu_trong_ltmm.pdf

chu ky so.zip

classical cryptosystem.zip

danh sách nhóm bài tập lớn môn lý thuyết mật mã.xlsx

gioithieuytuong.pdf

modern cryptosystem.zip

reportguide_cryptoproject2017.pdf

sha512.c

tai lieu di thi.pdf

testingmodel.pdf

thuat toan sha512.pdf

dethicuoiky_ltmm-20162.01x.pdf

ltmm_gk_20152.jpg

ltmm_gk_20171.pdf

ltmm_gk_20172.pdf

• 1. NGHỆ BƯU CHÍNH VIỄN THÔNG --------- ĐỖ XUÂN CHỢ BÀI GIẢNG MẬT MÃ HỌC CƠ SỞ Hà Nội, tháng 12 năm 2016
• 2. thế bùng nổ phát triển công nghệ và các ứng dụng của chúng ta trong cuộc sống hiện nay thì vấn đề an toàn và bảo mật hệ thống thông tin đang trở nên cấp thiết hơn bao giờ hết. Có rất nhiều phương pháp, kỹ thuật, cách thức để bảo vệ hệ thống công nghệ thông tin trước các cuộc tấn công. Mỗi phương pháp và kỹ thuật có ưu điểm và nhược điểm riêng. Một phương pháp cơ bản để đảm bảo an toàn cho thông tin hiện nay là ứng dụng các kỹ thuật mật mã để mã hóa thông tin. Hiện nay, các ứng dụng của mật mã học được triển khai và áp dụng ở hầu hết các lĩnh vực và công nghệ trong đời sống. Chính vì vậy, việc nghiên cứu và tìm hiểu về mật mã học cũng như các ứng dụng của mật mã trong thực tế là vấn đề rất cần quan tâm hiện nay. Môn học “Mật mã học cơ sở” là môn cơ sở chuyên ngành thuộc chương trình đào tạo đại học ngành An toàn thông tin của Học Viện Công Nghệ Bưu Chính Viễn Thông. Môn học cung cấp cho sinh viên các kiến thức cơ bản về mật mã học bao gồm: vai trò và tầm quan trọng của mật mã, khái niệm toán học trong mật mã; các thuật toán mã hóa thông dụng; các hàm băm; vấn đề quản lý và phân phối khóa; một số ứng dụng của mật mã trong thực tế. Bài giảng “Mật mã học cơ sở” được biên soạn trên cơ sở đề cương chi tiết môn học đã được duyệt và tổng hợp tài liệu từ nhiều nguồn nhằm cung cấp tài liệu phục vụ cho sinh viên nghiên cứu và học tập. Bài giảng được cấu trúc thành các chương như sau: Chương 1: Tổng quan về mật mã học. Chương này cung cấp các kiến thức cơ bản liên quan đến mật mã học bao gồm: khái niệm, các thuật ngữ, lịch sử phát triển và một số ứng dụng cơ bản. Bên cạnh đó, chương 1 còn trình bày về một số lý thuyết toán học được ứng dụng trong lĩnh vực mật mã như: lý thuyết số, lý thuyết thông tin, độ phức tạp của thuật toán… Chương 2: Mã hóa khóa đối xứng. Chương 2 cung cấp các kiến thức về hệ mật khóa đối xứng cũng như nguyên tắc mã hóa, giải mã của một số thuật toán mã hóa khóa đối xứng. Ngoài ra, chương 2 trình bày một số ưu và nhược điểm của các kỹ thuật mã hóa khóa đối xứng.
• 3. hóa khóa bất đối xứng. Chương 3 trình bày một số kiến thức liên quan đến kỹ thuật mã hóa khóa bất đối xứng bao gồm: khái niệm, nguyên tắc mã hóa, giải mã, ưu điểm và nhược điểm. Bên cạnh đó, chương 3 đề cập một số ứng dụng của mã hóa khóa bất đối xứng trong thực tế. Chương 4: Các hàm băm. Chương này cung cấp các kiến thức liên quan đến hàm băm bao gồm: định nghĩa, khái niệm, tính chất, vai trò của hàm băm. Ngoài ra, chương 4 còn trình bày về một số hàm băm phổ biến hiện nay cũng như nguyên tắc làm việc của một số hàm băm đó. Chương 5: Quản lý khóa. Chương này cung cấp các kiến thức liên quan đến vấn đề quản lý và phân phối khóa bao gồm: các khái niệm, phân loại, vai trò… Ngoài ra, chương 5 còn mô tả quy trình quản lý và phân phối khóa của một số giao thức phổ biến hiện nay.
• 4. mã học cơ sở 4 MỤC LỤC DANH MỤC CÁC BẢNG BIỂU VÀ HÌNH VẼ DANH MỤC CÁC TỪ VIẾT TẮT CHƯƠNG 1: TỔNG QUAN VỀ MẬT MÃ HỌC........................................................................ 11 1.1. CÁC THUẬT NGỮ VÀ CÁC KHÁI NIỆM CƠ BẢN..................................................11 1.2. LỊCH SỬ PHÁT TRIỂN.................................................................................................13 1.3. PHÂN LOẠI...................................................................................................................15 1.4. VAI TRÒ ........................................................................................................................17 1.5. MỘT SỐ ỨNG DỤNG CỦA MẬT MÃ HỌC...............................................................18 1.5.1. Kerberos ...................................................................................................................... 18 1.5.2. Krypto Knight ............................................................................................................. 19 1.5.3. PGP.............................................................................................................................. 19 1.5.4. Thẻ thông minh ........................................................................................................... 20 1.6. MỘT SỐ KHÁI NIỆM TOÁN HỌC TRONG MẬT MÃ..............................................21 1.6.1. Lý thuyết thông tin...................................................................................................... 21 1.6.2. Lý thuyết số................................................................................................................. 34 1.6.3. Độ phức tạp thuật toán ................................................................................................ 37 CHƯƠNG 2: MÃ HÓA KHÓA ĐỐI XỨNG............................................................................... 42 2.1. GIỚI THIỆU VỀ MÃ HÓA KHÓA ĐỐI XỨNG ..........................................................42 2.2. CÁC KỸ THUẬT MÃ HÓA ĐỐI XỨNG CỔ ĐIỂN....................................................43 2.2.1. Phương pháp thay thế.................................................................................................. 43 2.2.2. Phương pháp mã hóa hoán vị...................................................................................... 53 2.2.3. Phương pháp mã hóa XOR ......................................................................................... 53 2.2.4. Phương pháp sách hoặc khóa chạy.............................................................................. 54 2.3. CÁC KỸ THUẬT MÃ HÓA ĐỐI XỨNG HIỆN ĐẠI ..................................................54 2.3.1. Thuật toán mã hóa DES/3DES.................................................................................... 54 2.3.2. Thuật toán mã hóa AES .............................................................................................. 69 2.3.3. Thuật toán mã hóa A5/1.............................................................................................. 83 2.3.4. Thuật toán mã hóa RC4............................................................................................... 87 2.4. ƯU ĐIỂM VÀ NHƯỢC ĐIỂM CỦA MÃ HÓA ĐỐI XỨNG ......................................91
• 5. mã học cơ sở 5 CHƯƠNG 3: MÃ HÓA KHÓA BẤT ĐỐI XỨNG...................................................................... 94 3.1. GIỚI THIỆU VỀ MÃ HÓA BẤT ĐỐI XỨNG..............................................................94 3.1.1. Giới thiệu chung.......................................................................................................... 94 3.1.2. Một số thuật toán mã hóa bất đối xứng....................................................................... 96 3.2. THUẬT TOÁN MÃ HÓA RSA.....................................................................................97 3.3. ƯU ĐIỂM, NHƯỢC ĐIỂM CỦA MÃ HÓA BẤT ĐỐI XỨNG .................................100 3.4. ỨNG DỤNG CỦA MÃ HÓA BẤT ĐỐI XỨNG.........................................................102 CHƯƠNG 4: CÁC HÀM BĂM.................................................................................................. 104 4.1. GIỚI THIỆU VỀ HÀM BĂM ......................................................................................104 4.1.1. Định nghĩa................................................................................................................. 104 4.1.2. Phân loại.................................................................................................................... 105 4.1.3. Các tính chất cơ bản.................................................................................................. 104 4.1.4. Vai trò........................................................................................................................ 107 4.2. CÁC HÀM BĂM KHÔNG KHÓA..............................................................................108 4.2.1. MDC độ dài đơn............................................................................................................ 109 4.2.2. MDC độ dài kép: MDC-2 và MDC- 4.......................................................................... 110 4.3. CÁC HÀM BĂM CÓ KHÓA.......................................................................................112 4.4. MỘT SỐ HÀM BĂM THÔNG DỤNG .......................................................................113 4.4.1. Hàm băm họ MD - Message Digest (MD5).............................................................. 114 4.4.2. Hàm băm họ SHA - Secure Hash Algorithm (SHA-1)............................................. 117 CHƯƠNG 5: QUẢN LÝ KHÓA................................................................................................ 121 5.1. GIỚI THIỆU.................................................................................................................121 5.2. PHÂN PHỐI VÀ THỎA THUẬN KHÓA BÍ MẬT....................................................124 5.2.1. Các kỹ thuật phân phối và thỏa thuận khóa bí mật ................................................... 124 5.2.2. Một số giao thức phân phối và thỏa thuận khóa bí mật ............................................ 129 5.3. PHÂN PHỐI VÀ THỎA THUẬN KHÓA CÔNG KHAI ...........................................137 5.3.1. Các kỹ thuật phân phối và thỏa thuận khóa công khai.............................................. 137 5.3.2. Chứng chỉ xác thực khóa công khai X.509 ............................................................... 140 5.4. PHÂN PHỐI VÀ THỎA THUẬN KHÓA KẾT HỢP.................................................143 5.4.1. Giới thiệu chung........................................................................................................ 143
• 6. mã học cơ sở 6 5.4.2. Giao thức Diffie-Hellman ......................................................................................... 144 TÀI LIỆU THAM KHẢO........................................................................................................... 151
• 7. mã học cơ sở 7 DANH MỤC CÁC HÌNH VẼ Hình 1. 1. Mô hình mã hóa và giải mã đơn giản................................................................12 Hình 1. 2. Sơ đồ mã hóa của mã dòng................................................................................16 Hình 1. 3. Sơ đồ giải mã của mã dòng ...............................................................................16 Hình 2. 1: Mô hình mã hóa đối xứng .................................................................................42 Hình 2. 2. Mô hình Feistel..................................................................................................55 Hình 2. 3. Sơ đồ tổng quát quá trình mã hóa DES .............................................................57 Hình 2. 4. Mô hình vòng lặp DES ......................................................................................59 Hình 2. 5. Mô tả hàm f trong DES......................................................................................60 Hình 2. 6. Mô hình các bước tạo khóa của DES ................................................................65 Hình 2. 7. Sơ đồ mã hóa và giải mã Triple DES ................................................................69 Hình 2. 8. Sơ đồ SPN .........................................................................................................70 Hình 2. 9. Sơ đồ mã hóa giải mã AES ................................................................................74 Hình 2. 10. Phép biến đổi SubByte ....................................................................................76 Hình 2. 11. Phép biến đổi ShiftRows .................................................................................78 Hình 2. 12. Phép biến đổi MixColumn...............................................................................79 Hình 2. 13. Ví dụ về phép MixColumn..............................................................................80 Hình 2. 14. Biểu diễn sinh Nk khóa đầu tiên đối với khóa mã 128 bit...............................81 Hình 2. 15. Sơ đồ mã hóa giải mã A5/1 .............................................................................87 Hình 2. 16. Khởi tạo S và T................................................................................................88 Hình 2. 17. Quá trình hoán vị S..........................................................................................89 Hình 2. 18. Quá trình sinh số mã hóa thông điệp...............................................................90 Hình 3. 1. Mô hình mã hóa bất đối xứng............................................................................95 Hình 3. 2. Mô hình bảo mật..............................................................................................101 Hình 3. 3. Mô hình xác thực.............................................................................................101 Hình 3. 4. Mô hình chứng thực và không chối bỏ............................................................102 Hình 4. 1. Ví dụ tính chất hàm băm .................................................................................104 Hình 4. 2. Phân loại hàm băm ..........................................................................................105 Hình 4. 3. Sơ đồ kiểm tra toàn vẹn chỉ dùng MAC ..........................................................107 Hình 4. 4. Sơ đồ kiểm tra toàn vẹn dùng MDC và mã hóa ..............................................108 Hình 4. 5. Sơ đồ kiểm tra tính toàn vẹn dùng MDC và kênh an toàn ..............................108 Hình 4. 6. Các sơ đồ hàm băm MDC đơn ........................................................................109 Hình 4. 7. Sơ đồ thuật toán MDC-2..................................................................................111 Hình 4. 8. Sơ đồ thuật toán MDC-4..................................................................................112 Hình 4. 9. Sơ đồ hàm băm MAC.......................................................................................113 Hình 4. 10. Sơ đồ hàm băm MD5.....................................................................................115 Hình 4. 11. Sơ đồ cấu trúc hàm F.....................................................................................116
• 8. mã học cơ sở 8 Hình 4. 12. Cấu trúc biến đổi 1 vòng MD5......................................................................117 Hình 4. 13. Sơ đồ thuật toán băm SHA-1.........................................................................118 Hình 4. 14. Cấu trúc hàm F của thuật toán băm SHA-1...................................................119 Hình 5. 1. Sơ đồ trao đổi khóa trong một hệ thống 5 người.............................................124 Hình 5. 2. Phân phối khóa điểm – điểm ...........................................................................124 Hình 5. 3. Mô hình tạo và sử dụng khóa của hệ mã hóa khóa đối xứng..........................125 Hình 5. 4. Mô hình trao đổi khóa tập trung......................................................................126 Hình 5. 5. Mô hình trao đổi khóa đơn giản sử dụng KDC...............................................126 Hình 5. 6. Sơ đồ mô tả quá trình trao đổi khóa của giao thức Needham-Schroeder........130 Hình 5. 7. Hoạt động của Kerberos..................................................................................133 Hình 5. 8. Mô hình tạo và sử dụng khóa của hệ mã hóa khóa bất đối xứng ....................138 Hình 5. 9. Mô hình trao đổi khóa công khai thông qua sử dụng một máy chủ không trực tuyến và chứng chỉ............................................................................................................139 Hình 5. 10. Cơ chế xác thực một chiều ............................................................................142 Hình 5. 11. Cơ chế xác thực hai chiều..............................................................................142 Hình 5. 12. Cơ chế xác thực ba chiều...............................................................................143 Hình 5. 13. Quá trình thiết lập khóa phiên giữa hai thực thể ...........................................144 Hình 5. 14. Sơ đồ ví dụ về việc trao đổi khóa..................................................................145
• 9. mã học cơ sở 9 DANH MỤC CÁC BẢNG BIỂU Bảng 1. 1. Độ phức tạp để phân tích số nguyên ra thừa số nguyên tố ...............................40 Bảng 2. 1: Bảng thống kê kết quả tấn công vét cạn ...........................................................44 Bảng 2. 2: Ma trận mã hóa Palayfair..................................................................................46 Bảng 2. 3. Bảng thế A ........................................................................................................50 Bảng 2. 4. Bảng chân trị phép toán XOR...........................................................................53 Bảng 2. 5. Bảng hoán vị khởi tạo DES...............................................................................58 Bảng 2. 6. Bảng hoán vị kết thúc DES ...............................................................................58 Bảng 2. 7. Bảng Expand DES.............................................................................................60 Bảng 2. 8. Bảng S-box1 ......................................................................................................61 Bảng 2. 9. Bảng S-box2 ......................................................................................................61 Bảng 2. 10. Bảng S-box3 ....................................................................................................62 Bảng 2. 11. Bảng S-box4 ....................................................................................................62 Bảng 2. 12. Bảng S-box5 ....................................................................................................62 Bảng 2. 13. Bảng S-box6 ....................................................................................................63 Bảng 2. 14. Bảng S-box7....................................................................................................63 Bảng 2. 15. Bảng S-box8....................................................................................................63 Bảng 2. 16. Bảng P-box......................................................................................................64 Bảng 2. 17. Bảng nén khóa 64 xuống 56bit DES...............................................................65 Bảng 2. 18. Bảng nén khóa 56 bit xuống 48 bit DES.........................................................65 Bảng 2. 19. Ví dụ mã hóa DES ..........................................................................................66 Bảng 2. 20. Bảng S-box AES .............................................................................................75 Bảng 2. 21. Hộp thay thế ngược IS.....................................................................................77 Bảng 2. 22. Bảng kết quả của quá trình sinh khóa .............................................................83 Bảng 4. 1. Các hàm băm thông dụng................................................................................113 Bảng 4. 2. Bảng tính giá trị ROTL(t, s)............................................................................117 Bảng 5. 2. Quá trình trao đổi khóa giữa hai thực thể trong giao thức Shamir .................132 Bảng 5. 3. Bảng diễn giải giao thức Diffie-Hellman........................................................146
• 10. mã học cơ sở 10 DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt AES Advanced Encryption Standard Chuẩn mã hóa nâng cao CBC Cipher Block Chaining Chế độ mã móc xích CFB Ciphe Feedback Mode Chế độ mã phản hồi CRHF Collision resistant hash functions Hàm băm chống đụng độ DES Data Encryption Standard Chuẩn mã hóa dữ liệu ECB Electronic code book Chế độ bảng tra mã điện tử H Hash function Hàm băm KDC Key distribution center Trung tâm phân phối khóa KTC Key translation center Trung tâm dịch khóa MAC Message authentication codes Mã xác thực thông điệp MD Message Digest Tóm tắt thông điệp (có thể xem như một loại hàm băm) MDC Modification detection codes Mã phát hiện sửa đổi OWHF One-way hash functions Hàm băm một chiều PKC Public-key certificate Chứng chỉ khóa công khai SHA Secure Hash Algorithm Thuật toán băm an toàn SPN Substitution-Permutation Network Mạng thay thế hoán vị
• 11. mã học cơ sở Chương 1 11 CHƯƠNG 1: TỔNG QUAN VỀ MẬT MÃ HỌC Chương này cung cấp các kiến thức cơ bản liên quan đến mật mã học bao gồm: khái niệm, các thuật ngữ, lịch sử phát triển và một số ứng dụng cơ bản. Bên cạnh đó, chương 1 còn trình bày về một số lý thuyết toán học được ứng dụng trong lĩnh vực mật mã như: lý thuyết số, lý thuyết thông tin, độ phức tạp của thuật toán… 1.1. CÁC THUẬT NGỮ VÀ CÁC KHÁI NIỆM CƠ BẢN Một trong những khái niệm căn bản trong lĩnh vực mật mã là khái niệm mật mã học. Có nhiều định nghĩa khác nhau về mật mã học như: Mật mã học là kỹ thuật, nghệ thuật viết các ký tự bí mật (theo Webster's Revised Unabridged Dictionary). Hoặc mật mã học là việc mã hóa dữ liệu mà nó chỉ có thể được giải mã bởi một số người chỉ định (Free Online Dictionary of Computing)… Tuy nhiên, theo quan điểm của tác giả thì có thể hiểu một cách đơn giản về mật mã học như sau: Mật mã học là một ngành khoa học chuyên nghiên cứu, áp dụng các phương pháp, kỹ thuật, thuật toán nhằm che giấu, xử lý hoặc biến đổi thông tin thông thường thành dạng không đọc trực tiếp được là văn bản mã hóa. Để thực hiện được quy trình biến đổi từ thông tin thông thường thành văn bản mã hóa bao gồm nhiều công đoạn với nhiều thuật ngữ và các khái niệm liên quan. Dưới đây sẽ trình bày một số thuật ngữ và khái niệm cơ bản được sử dụng phổ biến nhất hiện nay. - Người gửi, người nhận Người gửi (sender): là người chịu trách nhiệm gửi thông điệp được mã hóa cho các bên liên quan. Người nhận (Receiver): là người có quyền hợp pháp nhận được thông điệp từ người gửi. - Thông điệp và Mã hóa Thông điệp (plaintext): hay còn gọi là bản rõ là một dạng văn bản có nội dung mà Người gửi muốn gửi tới Người nhận. Thông điệp thường được ký hiệu là M (message) hoặc P (plaintext). P hoặc M có thể là chuỗi bit, một file văn bản, tập tin ảnh bitmap, một dòng âm thanh hay ảnh số…
• 12. mã học cơ sở Chương 1 12 Mã hóa (encryption): quá trình cải trang một thông điệp, che giấu nội dung thật sự của thông điệp để nội dung của thông điệp không bị lộ. Bản mã (ciphertext): là kết quả của một thông điệp được mã hóa. Bản mã được ký hiệu là C (ciphertext). Giải mã (decryption): là quá trình chuyển đổi từ bản mã trở lại thông điệp ban đầu. Giả sử E là hàm mã hóa (encrypt), áp dụng trên P để tạo ra C, có biểu diễn toán học dạng: E(P) = C (1.1) Trong quy trình ngược lại, D là hàm giải mã (decrypt) áp dụng trên C để có P: D(C) = P (1.2) Để đảm bảo quá trình từ mã hóa đến giải mã là đúng, cần đảm bảo: D(E(P)) = P (1.3) - Thuật toán và khóa Bản rõ Bản mã Bản rõ ban đầu Mã hóaMã hóa Giải mãGiải mã KhóaKhóa KhóaKhóa Hình 1. 1. Mô hình mã hóa và giải mã đơn giản Hình 1.1. thể hiện một mô hình mã hóa và giải mã đơn giản. Từ mô hình này có thể thấy một số khái niệm cụ thể như sau : Thuật toán mã hóa (hay còn gọi là giải thuật mã hóa): là các phương pháp, mô hình toán học được ứng dụng trong quá trình mã hóa thông tin. Thuật toán giải mã (hay còn gọi là giải thuật giải mã): là kỹ thuật, thuật toán, mô hình toán học được ứng dụng trong quá trình giải mã thông tin. Khóa (key) : bản chất của Key là chìa. Tuy nhiên, thuật ngữ chìa không được sử dụng phổ biến mà thường sử dụng thuật ngữ Key là khóa. Chính vì vậy, trong bài giảng sẽ thống nhất sử dụng Key – khóa. Khóa là công cụ được ứng dụng trong quá trình mã hóa và giải mã. Khóa có thế là một phần tử trong một tập giá trị nào đó, phạm vi các giá trị
• 13. mã học cơ sở Chương 1 13 của khóa được gọi là không gian khóa. Khóa dùng để mã hóa và giải mã có thể giống hoặc khác nhau, tùy theo từng phương pháp, kỹ thuật mã hóa sử dụng. Các chương sau sẽ phân tích chi tiết hơn về vấn đề này. - Thám mã: là ngành khoa học khôi phục lại thông điệp mà không cần biết khóa. Thám mã thành công có thể thu được thông điệp hoặc khóa hoặc cả hai. Nó cũng có thể tìm thấy điểm yếu của hệ mật mà đã để lộ ra các kết quả trước đó. Thám mã có thể chia thành 4 loại chính:  Tấn công khi chỉ biết bản mã (ciphertext-only attack) ;  Tấn công đã biết thông điệp (known-plaintext attack):  Tấn công chọn thông điệp rõ (chosen plaintext attack) ;  Tấn công chọn thông điệp thích hợp (adaptive-chosen-ciphertext attack). - Độ an toàn thuật toán: Trong các nghiên cứu của Lars Knudsen đã trình bày chi tiết và cụ thể về độ an toàn của thuật toán mã hóa cũng như các tiêu chí đánh giá mức độ an toàn của một thuật toán. Dưới đây là một số tiêu chí cơ bản để đánh giá độ an toàn của một thuật toán mã hóa:  Chi phí yêu cầu cho việc phá mã lớn hơn so với việc mã hóa thì thuật toán đó tương đối an toàn;  Thời gian yêu cầu để phá mã dài hơn so với thời gian mà dữ liệu mã hóa cần giữ bí mật thì thuật toán đó là an toàn;  Tổng lượng dữ liệu mã hóa bằng 1 khóa ít hơn lượng dữ liệu đưa vào để phá mã thì nó được coi là an toàn. 1.2. LỊCH SỬ PHÁT TRIỂN Mật mã học là một ngành khoa học có lịch sử từ hàng nghìn năm nay. Trong phần lớn thời gian phát triển của mình, lịch sử mật mã học chính là lịch sử của những phương pháp mật mã học cổ điển. Vào đầu thế kỷ 20, sự xuất hiện của các cơ cấu cơ khí và điện cơ, chẳng hạn như máy Enigma, đã cung cấp những cơ chế phức tạp và hiệu quả hơn cho việc mật mã hóa. Bài giảng này sẽ trình bày một số cột mốc quan trọng trong lịch sử phát triển của mật mã học.
• 14. mã học cơ sở Chương 1 14 Mật mã học cổ điển: cách đây khoảng 4500 năm người Hy Lạp cổ đại đã sử dụng các kỹ thuật mật mã ví dụ như gậy mật mã. Cũng có những bằng chứng cho thấy người La Mã nắm được các kỹ thuật mật mã (mật mã Caesar và các biến thể). Thời trung cổ: Nguyên do xuất phát có thể là từ việc phân tích bản kinh Koran, do nhu cầu tôn giáo mà kỹ thuật phân tích tần suất đã được phát minh để phá vỡ các hệ thống mật mã đơn ký tự vào khoảng năm 1000. Đây chính là kỹ thuật phá mã cơ bản nhất được sử dụng, mãi cho tới tận thời điểm thế chiến thứ II. Về nguyên tắc, mọi kỹ thuật mật mã đều không chống lại được kỹ thuật mã này cho tới khi kỹ thuật mật mã dùng nhiều bảng chữ cái được Alberti sáng tạo (năm 1465). Mật mã học từ 1800 tới Thế chiến II: Tới thế kỷ 19, mật mã học mới được phát triển một cách có hệ thống. Trong thập niên 1840, Edgar Allan Poe đã xây dựng một số phương pháp có hệ thống để giải mật mã. Sau này ông có viết một đề tài về các phương pháp mã hóa và chúng trở thành những công cụ rất có lợi, được áp dụng vào việc giải mã của Đức trong Thế chiến II. Mật mã học trong Thế chiến II: Trong thế chiến II, các hệ thống mật mã cơ khí và cơ điện tử được sử dụng rộng rãi. Người Đức đã sử dụng rộng rãi một hệ thống máy rôto cơ điện tử, dưới nhiều hình thức khác nhau, có tên gọi là máy Enigma. Quân đội Đức cũng cho triển khai một số thử nghiệm cơ học sử dụng thuật toán mật mã dùng một lần (one-time pad). Bộ ngoại giao của Nhật cũng cục bộ xây dựng một hệ thống dựa trên nguyên lý của "bộ điện cơ chuyển mạch dịch bước" (được Mỹ gọi là Purple), và đồng thời cũng sử dụng một số máy tương tự để trang bị cho một số tòa đại sứ Nhật Bản. Các máy mật mã mà phe Đồng Minh sử dụng trong thế chiến II, bao gồm cả máy TypeX của Anh và máy SIGABA của Mỹ, đều là những thiết kế cơ điện dùng rôto trên tinh thần tương tự như máy Enigma, song có nhiều nâng cấp lớn. Mật mã học hiện đại: Năm 1949 Claude Shannon công bố bài: Lý thuyết về truyền thông trong các hệ thống bảo mật (Communication Theory of Secrecy Systems) trên tập san Bell System Technical Journal - Tập san kỹ thuật của hệ thống Bell - và một thời gian ngắn sau đó, trong cuốn Mathematical Theory of Communication - Lý thuyết toán học trong truyền thông - cùng với tác giả Warren Weaver. Ngày 17 tháng 3 năm 1975, IBM
• 15. mã học cơ sở Chương 1 15 (International Business Machines) đề xuất Tiêu chuẩn mật mã hóa dữ liệu DES (Data Encryption Standard). Vào năm 1976, Whitfield Diffie và Martin Hellman giới thiệu một phương pháp hoàn toàn mới về cách thức phân phối các khóa mật mã. Năm 2001, DES đã chính thức được thay thế bởi AES (Advanced Encryption Standard - Tiêu chuẩn mã hóa tiên tiến) khi NIST công bố phiên bản FIPS 197. 1.3. PHÂN LOẠI Có nhiều phương pháp và tiêu chí để phân loại các phương pháp mã hóa. Dưới đây sẽ trình bày một số phương pháp phổ biến dùng để phân loại mã hóa. Cách 1: Phân loại mã hóa theo đặc trưng của khoá: Mã hóa khóa đối xứng (Hay còn gọi là mã hóa khóa bí mật): là phương pháp mã hóa mà quá trình mã hóa và giải mã dùng chung một khóa. Khóa được dùng trong mã hóa đối xứng gọi là khóa bí mật. Các thuật toán mã hóa đối xứng thường gặp: DES, AES… Mã hóa khóa bất đối xứng (Hay còn gọi là mã hóa khóa công khai): là phương pháp mã hóa mà khóa sử dụng để mã hóa sẽ khác với khóa dùng để giải mã. Khóa dùng để mã hóa gọi là khóa công khai và khóa dùng để giải mã gọi là khóa bí mật. Tất cả mọi người đều có thể biết được khóa công khai (kể cả hacker), và có thể dùng khóa công khai để mã hóa thông tin. Nhưng chỉ có người nhận mới nắm giữ khóa bí mật, nên chỉ có người nhận mới có thể giải mã được thông tin. Cách 2: Phân loại mã hóa theo đặc trưng xử lý thông điệp Mã hóa dòng: là kiểu mã hóa mà từng bit (hoặc từng ký tự) của thông điệp được kết hợp với từng bit (hoặc từng ký tự) tương ứng của khóa để tạo thành bản mã. Đặc trưng cơ bản của mã dòng như sau: - Kích thước một đơn vị mã hóa là : k bit. - Thông điệp được chia thành các đơn vị mã hóa P→P0P1P2...Pn-1 - Một bộ sinh số ngẫu nhiên: Dùng khóa K ban đầu để sinh ra các số ngẫu nhiên có kích thước bằng kích thước của đơn vị mã hóa : StreamCipher(K) → S = S0S1S2...Sn-1
• 16. mã học cơ sở Chương 1 16 - Mỗi đơn vị mã hóa được XOR tương ứng với số ngẫu nhiên để cho ra bản mã. C0=P0  S0 , C1=P1  S1 ……., Cn-1=Pn-1  Sn-1 → C=C0C1C2…Cn-1; Giải thuậtGiải thuật Khóa (K) Bản rõ (Pi) Bản mã (Ci) Mã hóa dòng (Ki) Hình 1. 2. Sơ đồ mã hóa của mã dòng - Quá trình giải mã là một quá trình ngược lại, bản mã được XOR với bộ sinh số ngẫu nhiên cho ra thông điệp. P0=C0  S0 , P1=C1  S1 ……., Pn-1=Cn-1  Sn-1 → P=P0P1P2…Pn-1; Giải thuậtGiải thuật Khóa (K) Bản rõ (Pi) Bản mã (Ci) Giải mã dòng (Ki) Hình 1. 3. Sơ đồ giải mã của mã dòng Một số thuật toán mã hóa dòng phổ biến hiện nay: A5/1; RC4. Trong chương 2 của bài giảng sẽ trình bày chi tiết hơn về các thuật toán này. Mã hóa khối: là kiểu mã hóa mà dữ liệu được chia ra thành từng khối có kích thước cố định để mã hóa. Để xây dựng thuật toán mã hóa khối an toàn bằng cách sử dụng kết hợp các thao tác mã hóa tạo ra tính hỗn loạn và tính khuếch tán thông tin: - Tính hỗn loạn (diffusion) giúp phá vỡ mối quan hệ giữa thông điệp và bản mã, tạo ra mối quan hệ phức tạp và chặt chẽ giữa khóa và bản mã.
• 17. mã học cơ sở Chương 1 17 - Sự khuếch tán (confusion) giúp phá vỡ và phân tán các phần tử trong các mã xuất hiện trong thông điệp để không thể phát hiện ra các mẫu này trong bản mã. Các chế độ hoạt động của mã hóa khối: Trong mã hóa khối có 4 chế độ hoạt động cơ bản như sau: - Chế độ ECB (Electronic Codebook): cùng khối thông điệp đầu vào, khối bản mã giống nhau. Các khối bản mã hoàn toàn độc lập nhau. - Chế độ CBC (Cipher-Block Chaining): cùng khối thông điệp đầu vào, khối bản mã giống nhau với cùng khóa và phần nối đuôi. Khối mã cj phụ thuộc vào khối rõ xj và các khối rõ trước đó (x1-xj-1). - Chế độ CFB (Cipher Feedback): cùng khối thông điệp đầu vào, khối bản mã khác nhau. Khối mã cj phụ thuộc vào khối rõ xj và các khối rõ trước đó (x1-xj-1). - Chế độ OFB (Output Feedback): cùng khối thông điệp đầu vào, khối bản mã khác nhau. Luồng khóa độc lập với thông điệp. Các mô hình mã hóa khối: Về mô hình mã khối, các nhà mật mã chia làm 2 mô hình chính: mạng thay thế hoán vị (Substitution-Permutation Network - SPN) và Mô hình Feistel. Trong chương 2 của bài giảng sẽ trình bày chi tiết hơn về 2 mô hình này. 1.4. VAI TRÒ Mật mã học có vai trò rất lớn trong việc đảm bảo an toàn cho hệ thống thông tin cũng như các ứng dụng hiện nay. Việc ứng dụng mật mã học nhằm đảm bảo các tính chất: - Tính bí mật (confidentiality): thông tin chỉ được phép truy cập bởi những đối tượng hợp lệ, những đối tượng được cấp phép. - Tính toàn vẹn thông tin (integrity): đảm bảo thông tin không bị thay đổi trong quá trình truyền tin; hoặc nếu có thay đổi thì sẽ bị phát hiện. - Tính sẵn sàng (availability): đảm bảo thông tin phải luôn luôn sẵn sàng khi cần thiết. Điều đó có nghĩa rằng mật mã học cung cấp một cơ chế bảo mật tốt, có thể tránh được những rủi ro cả về phần cứng, phần mềm và tránh được các cuộc tấn công của tin tặc.
• 18. mã học cơ sở Chương 1 18 - Tính xác thực (authentication): đảm bảo các bên liên quan nhận biết và tin tưởng nhau trong một hệ truyền tin, đồng thời đảm bảo thông tin trao đổi là thông tin thật. - Tính chống chối bỏ (non-repudiation): đảm bảo rằng các bên liên quan không thể chối bỏ các hành động đã thực hiện trước đó. 1.5. MỘT SỐ ỨNG DỤNG CỦA MẬT MÃ HỌC Một số ứng dụng của mật mã phải kể đến như: Dịch vụ xác thực; Điều khiển truy nhập; Các công cụ cho đảm bảo an toàn cho truyền thông không dây; Các nền tảng bảo mật như PKI, PGP; Các giao thức bảo mật như SSL/TLS, SSH, SET, IPSec; Các hệ thống như VPN. Trong phần tiếp theo, bài giảng sẽ mô tả tổng quát một số ứng dụng cụ thể của mật mã đang được triển khai trong thực tế hiện nay. 1.5.1. Kerberos Kerberos là một giao thức xác thực cho các máy đáng tin cậy trong một mạng không tin cậy. Nó cũng đảm bảo tính toàn vẹn và tính bí mật cho thông tin truyền đi. Kerberos sử dụng mã hóa khóa đối xứng như DES, triple DES để đảm bảo an toàn thông tin. Tuy nhiên, Kerberos sẽ mất tác dụng nếu một người nào đó có được quyền truy cập vào máy chủ và sao chép tập tin chứa khóa. Một số nhận xét, đánh giá về ưu điểm và nhược điểm của giao thức Kerberos: Ưu điểm: Kerberos được đánh giá là giao thức xác thực an toàn nhờ các đặc điểm sau: - Khi sử dụng Kerberos, mật khẩu không bao giờ truyền dưới dạng rõ mà luôn được mã hóa. - Kerberos không yêu cầu người dùng lặp đi lặp lại thao tác nhập mật khẩu trước khi truy cập vào các dịch vụ điều đó hạn chế được nguy cơ tấn công ăn cắp dữ liệu. - Giao thức được mã hóa theo các chuẩn mã hóa cao cấp như Triple DES, RC4, AES nên rất an toàn. - Tất cả các trao đổi giữa các máy đều chứa timestamp nên vé bị đánh cắp không thể tái sử dụng, chống được tấn công dùng lại (replay attack). Hạn chế của Kerberos: Bên cạnh các ưu điểm kể trên, hệ thống Kerberos cũng tồn tại một số hạn chế nhất định:
• 19. mã học cơ sở Chương 1 19 - Độ bảo mật của hệ thống phụ thuộc vào sự an toàn của hệ thống KDC (Key Distribution Center). Nếu KDC bị tấn công thì toàn bộ các thành phần trong hệ thống cũng bị tê liệt. - Do tất cả các trao đổi đều gắn timestamp nên đòi hỏi các máy tính trong hệ thống phải đồng bộ về thời gian (không chênh lệch nhau quá 5 phút). Nếu không đảm bảo điều này, cơ chế xác thực dựa trên thời hạn sử dụng sẽ không hoạt động. - Với cơ chế đăng nhập một lần trên một máy tính, nếu máy tính đó rơi vào tay những kẻ tấn công ma ̣ng thì toàn bộ dữ liệu người dùng sẽ bị đánh cắp và gây nguy cơ cho toàn bộ hệ thống. 1.5.2. Krypto Knight KryptoKnight được phát triển bởi Phòng thí nghiệm nghiên cứu IBM Zurich và Yorktown. KryptoKnight cung cấp dịch vụ xác thực và phân phối khóa cho các ứng dụng và đối tượng giao tiếp trong môi trường mạng. Mục tiêu của KryptoKnight là cung cấp dịch vụ bảo mật mạng với tính bền và độ linh hoạt cao. Tính bền vững trong các thông điệp của KryptoKnight cho phép nó trở thành giao thức bảo mật truyền thông ở mọi tầng, có thể đảm bảo tính bí mật thông tin mà không cần sử dụng thêm bất kì giao thức nào khác. Mặt khác, KryptoKnight tránh việc sử dụng mã hóa hàng loạt, khiến cho kiến trúc của nó trở nên linh hoạt. KryptoKnight cung cấp các dịch vụ nhằm: - Hỗ trợ người sử dụng ủy thác danh tính của mình cho đối tượng khác. - Hỗ trợ các thực thể tham gia giao tiếp xác thực lẫn nhau bằng cách cung cấp ủy thác từ người sử dụng hợp pháp. - Cho phép các thực thể xác thực nguồn gốc và nội dung dữ liệu được trao đổi. Các dịch vụ mà Kryptoknight cung cấp bao gồm: Single Sign-On (SSO); Xác thực hai bên; Phân phối khóa; Xác thực nguồn gốc và nội dung dữ liệu. 1.5.3. PGP
• 20. mã học cơ sở Chương 1 20 PGP (Pretty Good Privacy): khi mới ra đời PGP là công cụ bảo mật file/email, sau đó được phát triển thành một chuẩn bảo mật và có nhiều bản cài đặt của PGP. Chức năng bảo mật PGP bao gồm: - Đảm bảo tính bí mật thông qua mã hóa - Xác thực thông qua chữ ký số Mô hình hoạt động của PGP được chia làm 3 mô hình chính như sau: - Mô hình Direct Trust: Là mô hình đơn giản nhất. Trong mô hình này, người dùng tin tưởng rằng khóa là hợp lệ vì họ biết nó đến từ đâu. - Mô hình Hierarchical Trust: Trong một hệ thống phân cấp, có một số các ‘root CA’ gọi là chứng chỉ gốc. Các root CA này có thể tự xác thực bản thân, hoặc có thể xác thực tới các chứng chỉ khác. - Mô hình A Web of Trust: Một mô hình web of trust bao gồm cả các mô hình an toàn khác. Do đó nó là một mô hình tin cậy phức tạp nhất. Chứng chỉ có thể được tin cậy trực tiếp, hoặc được tin cậy trong chuỗi (meta-introducers), hoặc bởi một số nhóm người giới thiệu (users). Trong thực tế, mô hình PGP được ứng dụng rất rộng với nhiều phiên bản khác nhau. Tuy nhiên, có thể khái quát ứng dụng của PGP như sau: email, chữ ký số, mật mã hóa ổ đĩa cứng máy tính xách tay, bảo mật tệp và thư mục, bảo mật các phiên trao đổi IM, mật mã hóa luồng chuyển tệp, bảo vệ các tệp và thư mục lưu trữ trên máy chủ mạng. 1.5.4. Thẻ thông minh Thẻ thông minh (Smart Card), thẻ gắn chip, hay thẻ tích hợp vi mạch (integrated circuit card -ICC) là loại thẻ bỏ túi thường có kích thước của thẻ tín dụng, bên trong chứa một mạch tích hợp có khả năng lưu trữ và xử lý thông tin. Nó có thể đóng vai trò như thẻ căn cước, thực hiện việc xác thực thông tin, lưu trữ dữ liệu hay dùng trong các ứng dụng thẻ. Thẻ thông minh được chia làm 2 loại chính như sau: - Thẻ thông minh có tiếp xúc: Loại thẻ thông minh có tiếp xúc có một diện tích tiếp xúc, bao gồm một số tiếp điểm mạ vàng, và có diện tích khoảng 1 cm vuông. Khi được
• 21. mã học cơ sở Chương 1 21 đưa vào máy đọc, con chip trên thẻ sẽ giao tiếp với các tiếp điểm điện tử và cho phép máy đọc thông tin từ chip và viết thông tin lên nó. - Thẻ thông minh không tiếp xúc: Đây là loại thẻ mà chip trên nó liên lạc với máy đọc thẻ thông qua công nghệ cảm ứng RFID (với tốc độ dữ liệu từ 106 đến 848 kbit/s). Một số chức năng và vai trò của thẻ thông minh trong vấn đề xác thực và bảo mật thông tin: - Cho phép thực hiện các giao dịch kinh doanh một cách hiệu quả theo một cách chuẩn mực, linh hoạt và an ninh mà trong đó con người ít phải can thiệp vào. - Giúp thực hiện việc kiểm tra và xác nhận chặt chẽ mà không phải dùng thêm các công cụ khác như mật khẩu…Chính vì thế, có thể thực hiện hệ thống dùng cho việc đăng nhập sử dụng máy tính, máy tính xách tay, dữ liệu bảo mật hoặc các môi trường kế hoạch sử dụng tài nguyên của công ty như SAP, v.v..với thẻ thông minh là phương tiện kiểm tra và xác nhận duy nhất. Ngoài ra, thẻ thông minh cung cấp một số tính năng có thể được sử dụng để cung cấp hoặc tăng cường bảo vệ quyền riêng tư trong hệ thống. Trong bài giảng chỉ liệt kê một số tính năng quan trọng của thẻ thông minh. Chi tiết về những tính năng này và làm thế nào thực hiện được các chức năng này, có thể tham khảo trong các tài liệu tham khảo khác. Một số tính năng cụ thể như sau: Chứng thực; An toàn dữ liệu lưu trữ; mã hóa; Bảo mật thiết bị; Thông tin liên lạc an toàn; Sinh trắc học; Chứng chỉ…. 1.6. MỘT SỐ KHÁI NIỆM TOÁN HỌC TRONG MẬT MÃ Có thể thấy rằng mật mã học là một lĩnh vực khoa học rộng lớn có liên quan rất nhiều ngành toán học như: Đại số tuyến tính, Lý thuyết thông tin, Lý thuyết độ phức tạp tính toán. Bởi vậy việc trình bày đầy đủ mọi khía cạnh của toàn học trong mật mã học trong khuôn khổ bài giảng là một điều khó có thể làm được. Chính vì lý do đó, bải giảng chỉ dừng ở mức mô tả ngắn gọn một số khái niệm toán học chủ yếu và thường được áp dụng để xây dựng các phương pháp mã hóa. Chi tiết hơn về cơ sở toán học của mật mã có thể tham khảo tại các tài liệu tham khảo trong bài giảng. 1.6.1. Lý thuyết thông tin
• 22. mã học cơ sở Chương 1 22 1.6.1.1. Độ an toàn của hệ mật Có 2 quan điểm cơ bản về độ an toàn của một hệ mật. 1. Độ an toàn tính toán: Độ đo này liên quan đến những nỗ lực tính toán cần thiết để phá một hệ mật. Một hệ mật là an toàn về mặt tính toán nếu một thuật toán tốt nhất để phá nó cần ít nhất N phép toán, N là số rất lớn nào đó. Vấn đề ở chỗ, không có một hệ mật thực tế đã biết nào có thể được chứng tỏ là an toàn theo định nghĩa này. Trên thực tế, gọi một hệ mật là "an toàn về mặt tính toán" nếu có một phương pháp tốt nhất phá hệ này nhưng yêu cầu thời gian lớn đến mức không chấp nhận được. Một quan điểm chứng minh về độ an toàn tính toán là quy độ an toàn của một hệ mật về một bài toán đã được nghiên cứu và bài toán này được coi là khó. Ví dụ, có thể chứng minh một khẳng định: “Một hệ mật đã cho là an toàn nếu không thể phân tích ra thừa số một số nguyên n cho trước". Các hệ mật loại này đôi khi gọi là “An toàn chứng minh được". Tuy nhiên cần phải hiểu rằng, quan điểm này chỉ cung cấp một chứng minh về độ an toàn có liên quan để một bài toán khác chứ không phải là một chứng minh hoàn chỉnh về độ an toàn. 2. Độ an toàn không điều kiện: Độ đo này liên quan đến độ an toàn của các hệ mật khi không có một hạn chế nào được đặt ra về khối lượng tính toán mà kẻ tấn công được phép thực hiện. Một hệ mật được gọi là an toàn không điều kiện nếu nó không thể bị phá trong trường hợp lý tưởng (với khả năng tính toán không hạn chế). Mặt khác độ an toàn không điều kiện của một hệ mật không thể được đánh giá theo quan điểm độ phức tạp tính toán vì thời gian tính toán cho phép không hạn chế. Ở đây lý thuyết xác suất là nền tảng thích hợp để nghiên cứu về độ an toàn không điều kiện. Định nghĩa 1.1: Giả sử 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 để 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ị x với điều kiện Y nhận giá trị y. Các biến ngẫu nhiê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ể x của X và y của Y.
• 23. mã học cơ sở Chương 1 23 Quan hệ giữa xác suất đồng thời và xác suất có điều kiện được biểu thị theo công thức: p(x,y)= p(x|y) p(y) (1.8) Đổi chỗ x và y có: p(x,y)= p(y|x) p(x) (1.9) Từ hai biểu thức trên có thể rút ra kết quả sau:(được gọi là định lý Bayes) Định lý 1.1: (Định lý Bayes) Nếu p(y) >0 thì: )( )()( yp x ypxp y x      (1.10) Hệ quả 1.1. x và y là các biến độc lập khi và chỉ khi: p(x|y)= p(x) , x,y. Giả sử rằng, một khoá cụ thể chỉ dùng cho một bản mã. Giả sử có một phân bố xác suất trên không gian thông điệp P. Ký hiệu xác suất tiên nghiệm để thông điệp xuất hiện là pP(x). Cũng giả sử rằng, khóa K được chọn (bởi Alice và Bob) theo một phân bố xác suất xác định nào đó. Thông thường khoá được chọn ngẫu nhiên, bởi vậy tất cả các khoá sẽ đồng khả năng, tuy nhiên đây không phải là điều bắt buộc. Ký hiệu xác suất để khóa K được chọn là pK(K). Cần nhớ rằng khóa được chọn trước khi Alice biết thông điệp. Bởi vậy có thể giả định rằng khoá K và thông điệp x là các sự kiệ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. Thật vậy, có thể dễ dàng tính được xác suất pP(y)với y là bản mã được gửi đi. Với một khoá K  K, xác định: C(K) ={eK(x): x P} (1.11) Ở đây C(K) biểu thị tập các bản mã có thể nếu K là khóa. Khi đó với mỗi yC , có: pC(y)=  )}(:{ KCyK pK(K) pP(dK(y)) (1.12)
• 24. mã học cơ sở Chương 1 24 Nhận thấy rằng, với bất kì yC và x P, có thể tính được xác suất có điều kiện pC(y|x). (Tức là xác suất để y là bản mã với điều kiện thông điệp là x): { : ( )} ( | ) ( ) K C K K x d y p y x p K    (1.13) Từ đó có thể tính được xác suất có điều kiện pP(x|y) (tức xác suất để x là thông điệp với điều kiện y là bản mã) bằng cách dùng định lý Bayes. Công thức thu được như sau: { : ( )} { : ( )} ( ) ( ) ( | ) ( ) ( ( )) K P K K x d y P K P K K y C K p x p K p y x p K p d y       (1.14) Các phép tính này có thể thực hiện được nếu biết được các phân bố xác suất. Sau đây sẽ trình bày một ví dụ đơn giản để minh hoạ việc tính toán các phân bố xác suất này. Ví dụ: Giả sử P={a,b} với pP(a)=1/4, pP(b)=3/4 Cho K ={K1, K2, K3} với pK(K1)=1/2, pK(K2)= pK(K3)=1/4 Giả sử C ={1,2,3,4} và các hàm mã được xác định là: 1 1 2 2 3 3 ( ) 1, ( ) 2, ( ) 2, ( ) 3, ( ) 3, ( ) 4K K K K K Ke a e b e a e b e a e b      . Hệ mật này được biểu thị bằng ma trận mã hóa sau: a b K1 1 2 K2 2 3 K3 2 4 Tính phân bố xác suất pC có: pC(1)=1/8 pC(2)=3/8+1/16=7/16 pC(3)=3/16+1/16=1/4 pC(4)=3/16
• 25. mã học cơ sở Chương 1 25 Bây giờ đã có thể các phân bố xác suất có điều kiện trên thông điệp với điều kiện đã biết bản mã. Từ đó có: pP(a|1)=1 pP(b|1)=0 pP(a|2)=1/7 pP(b|2)=6/7 pP(a|3)=1/4 pP(b|3)=3/4 pP(a|4)=0 pP(b|1)=1 Bây giờ đã có đủ điều kiện để xác định khái niệm về độ mật hoàn thiện. Một cách không hình thức, độ mật hoàn thiện có nghĩa là kẻ tấn công với bản mã trong tay không thể thu được thông tin gì về thông điệp. Ý tưởng này sẽ được làm chính xác bằng cách phát biểu nó theo các thuật ngữ của các phân bố xác suất định nghĩa ở trên. Định nghĩa 1.2. Một hệ mật có độ mật hoàn thiện nếu pP(x|y)= pP(x) với mọi x P, yC. Tức xác suất hậu nghiệm để thông điệp là x với điều kiện đã thu được bản mã y là đồng nhất với xác suất tiên nghiệm để thông điệp là x. Trong ví dụ trên chỉ có bản mã 3 mới thoả mãn tính chất độ mật hoàn thiện, các bản mã khác không có tính chất này. Sau đây sẽ nghiên cứu độ mật hoàn thiện trong trường hợp chung. Trước tiên thấy rằng, (sử dụng định lý Bayes) điều kiện để pP(x|y)= pP(x) với mọi ,x P y P  là tương đương với pC(y|x)= pC(y) với mọi ,x P y P  . Giả sử rằng ( ) 0Cp y  với mọi ( ( ) 0)Cy C p y  thì bản mã sẽ không được dùng và có thể loại khỏi C. Cố định một giá trị nào đó x P , với mỗi y C có pC(y|x)= pC(y) >0. Bởi vậy, với mỗi y C phải có ít nhất một khoá K và một x sao cho ( )Ke x y . Điều này dẫn đến | | | |K C . Trong một hệ mật bất kỳ phải có | | | |C P vì mỗi quy tắc mã hóa là một đơn ánh. Trong trường hợp giới hạn, | | | | | |K C P  , có định lý sau (Theo Shannon). Định lý 1.2. Giả sử (P, C, K, E, D) là một hệ mật, trong đó |K|=|C|=|P|. Khi đó, hệ mật có độ mật hoàn thiện khi và chỉ khi khoá K được dùng với xác suất như nhau bằng 1/|K|, và với mỗi xP, mỗi y C có một khoá duy nhất K sao cho eK(x)=y
• 26. mã học cơ sở Chương 1 26 Chứng minh: Giả sử hệ mật đã cho có độ mật hoàn thiện. Như đã thấy ở trên: với mỗi xP, mỗi y C, phải có ít nhất một khoá K sao cho eK(x)=y. Bởi vậy có bất đẳng thức: |C|=|{eK(x):KK}|=|K| Tuy nhiên, giả sử rằng |C|= |K| , bởi vậy phải có: |{eK(x):KC}|=|K| Tức là ở đây không tồn tại hai khoá K1 và K2 khác nhau để eK1(x)=eK2(x)=y. Như vậy đã chứng minh được rằng, với bất kỳ xP và yC có đúng một khoá K eK(x)=y. Ký hiệu n=|K|. Giả sử P={xi:1≤i≤n} và cố định một giá trị yC. Có thể ký hiệu các khoá K1, K2,…Kn sao cho eKi(xi)=yi, 1≤i≤n. Sử dụng định lý Bayes có: ( | ) ( ) ( ).( ( )) ( | ) ( ) ( ) C i P i K i P i P i C C p y x p x p K p x p x y p y p y   (1.15) Xét điều kiện độ mật hoàn thiện pP(xi|y)=pP(xi). Điều kiện này kéo theo pK(Ki)=pC(y) với 1 ≤ i≤ n. Tức là khoá được dùng với xác suất như nhau (chính bằng pC(y)). Tuy nhiên vì số khoá là n=|K| nên có pK(K)=1/|K| với mỗi KK Mật mã khoá sử dụng một lần của Vernam (One-Time-Pad: OTP) là một ví dụ quen thuộc về hệ mật có độ mật hoàn thiện. Gillbert Vernam lần đầu tiên mô tả hệ mật này vào năm 1917. Hệ OTP dùng để mã hóa và giải mã tự động các thông điệp điện báo. Điều thú vị là trong nhiều năm OTP được coi là một hệ mật không thể bị phá nhưng không thể chứng minh cho tới khi Shannon xây dựng được khái niệm về độ mật hoàn thiện hơn 30 năm sau đó. Giả sử n (n≥1) là số nguyên và P=C=K=(Z2)n . Với 2( )n K Z , xác định eK(x) là tổng vector theo modulo 2 của K và x (hay tương đương với phép hoặc loại trừ của hai dãy bit tương ứng). Như vậy, nếu x=(x1,…,xn) và K=(K1,…,Kn) thì: 1 1( ) ( ,..., )mod2K n ne x x K x K  
• 27. mã học cơ sở Chương 1 27 Phép mã hóa là đồng nhất với phép giải mã. Nếu y=(y1,…,yn) thì: 1 1( ) ( ,..., )mod2K n nd x y K y K   1.6.1.2. Entropy Phần trước đã trình bày về khái niệm độ mật hoàn thiện và thể hiện mối quan tâm vào một trường hợp đặc biệt, khi một khoá chỉ được dùng cho một lần mã. Trong phần này, bài giảng sẽ nghiên cứu khi có nhiều thông điệp được mã hóa bằng cùng một khoá và bằng cách nào mà thám mã có thể thực hiện có kết quả phép tấn công chỉ với bản mã trong thời gian đủ lớn. Công cụ cơ bản trong nghiên cứu bài toán này là khái niệm Entropy. Đây là khái niệm trong lý thuyết thông tin do Shannon đưa ra vào năm 1948. Có thể coi Entropy là đại lượng đo thông tin hay còn gọi là độ bất định. Nó được tính như một hàm của phân bố xác suất. Giả sử có một biến ngẫu nhiên X nhận các giá trị trên một tập hữu hạn theo một phân bố xác suất p(X). Thông tin thu nhận được bởi một sự kiện xảy ra tuân theo một phân bố p(X) là gì?. Tương tự, nếu sự kiện còn chưa xảy ra thì cái gì là độ bất định và kết quả bằng bao nhiêu?.Đại lượng này được gọi là Entropy của X và được ký hiệu là H(X). Các ý tưởng này có vẻ như khá trừu tượng, bởi vậy sẽ xét một ví dụ cụ thể hơn. Giả sử biến ngẫu nhiên X biểu thị phép tung đồng xu. Phân bố xác suất là: p(mặt sấp) = p(mặt ngửa) = 1/2. Có thể nói rằng, thông tin (hay Entropy) của phép tung đồng xu là một bit vì có thể mã hóa mặt sấp bằng 1 và mặt ngửa bằng 0. Tương tự Entropy của n phép tung đồng tiền có thể mã hóa bằng một xâu bit có độ dài n. Định nghĩa 1.3 Giả sử X là một biến ngẫu nhiên lấy các giá trị trên một tập hữu hạn theo phân bố xác suất p(X). Khi đó Entropy của phân bố xác suất này được định nghĩa là lượng: 2 1 ( ) log n i i i H X p P    (1.16) Nếu các giá trị có thể của X là xi, 1≤ i≤ n thì có:
• 28. mã học cơ sở Chương 1 28 2 1 ( ) ( )log ( ) n i i i H X p X x P X x      (1.17) Nhận xét: Nhận thấy rằng log2pi không xác định nếu pi=0. Bởi vậy đôi khi Entropy được định nghĩa là tổng tương ứng trên tất cả các xác suất khác 0. Vì 0lim x xlog2x=0 nên trên thực tế cũng không có trở ngại gì nếu cho pi=0 với giá trị i nào đó. Tuy nhiên tuân theo giả định là khi tính Entropy của một phân bố xác suất pi, tổng trên sẽ được lấy trên các chỉ số i sao cho pi≠0 cũng thấy rằng việc chọn cơ số của logarit là tuỳ ý; cơ số này không nhất thiết phải là 2. Với một cơ số khác sẽ chỉ làm thay đổi giá trị của Entropy đi một hằng số. Chú ý rằng, nếu pi=1/n với 1≤ i≤ n thì H(X)=log2n thì dễ dàng thấy rằng H(X)≥0 và H(X)=0 khi và chỉ khi pi=1 với một giá trị i nào đó và pj=0 với j≠i. Xét Entropy của các thành phần khác nhau của một hệ mật. Có thể coi khoá là một biến ngẫu nhiên K nhận các giá trị tuân theo phân bố xác suất pK và bởi vậy có thể tính được H(K). Tương tự có thể tính các Entropy H(P) và H(C) theo các phân bố xác suất tương ứng của bản mã và thông điệp. Các tính chất của Entropy: Trong phần này sẽ chứng minh một số kết quả quan trọng liên quan đến Entropy. Trước tiên sẽ nghiên cứu về bất đẳng thức Jensen. Bất đẳng thức Jensen có liên quan đến hàm lồi có định nghĩa như sau: Định nghĩa 1.4 Một hàm có giá trị thực f là lồi trên khoảng I nếu: ( ) ( ) ( ) 2 2 x y f x f y f    (1.18) với mọi ,x y I ,F là hàm lồi thực sự trên khoảng I nếu: ( ) ( ) ( ) 2 2 x y f x f y f    (1.19) với mọi ,x y I , x ≠ y. Định lý 1.3: (Bất đẳng thức Jensen không chứng minh)
• 29. mã học cơ sở Chương 1 29 Giả sử h là một hàm lồi thực sự và liên tục trên khoảng l, 1 1  n i ia và ai>0; 1 ≤ I ≤ n. Khi đó: 1 1 ( ) n n i i i i i i a f x f a x            (1.20) trong đó ;1ix I i n   . Ngoài ra dấu “=” chỉ xảy ra khi và chỉ khi x1= x2=...= xn Tiếp theo sẽ đưa ra một số kết quả về Entropy. Trong định lý 1.4 sử dụng khẳng định: hàm log2 x là một hàm lồi thực sự trong khoảng (0,∞).. Định lý 1.4 Giả sử X là biến ngẫu nhiên có phân bố xác suất p1, p2,..., pn trong đó pi >0; 1≤i≤n. Khi đó H(X)
• 30. mã học cơ sở Chương 1 30 ij ( , ),1 ,1i jr p X x Y y i j n       (Đây là phân bố xác suất). Nhận thấy rằng: ij 1 ;(1 ) n i j p r i m     ij 1 ;(1 ) m j i q r j n     Có: 2 2 1 1 ( log log ) m n i i j j i j p p q q      ij 2 ij 2 1 1 1 1 ( log log ) m n n m i j i j j i r p r q        ij 2 1 1 log m n i j i j r p q    ij 2 ij 1 1 log m n i j r r    Kết hợp lại được kết quả sau: ij 2 ij 1 1 log (1/ ) m n i j r r    + ij 2 1 1 log m n i j i j r p q    2 2 1 1 log log 1 0 m n i j i j p q      (Ở đây đã áp dụng bất đẳng thức Jensen khi biết rằng các rij tạo nên một phân bố xác suất) Khi đẳng thức xảy ra, có thể thấy rằng phải có một hằng số c sao cho pij/rij=c với mọi i,j. Áp dụng đẳng thức sau: ij 1 1 m n i j r    1 1 m n i j i j p q    Điều này dẫn đến c=1. Bởi vậy đẳng thức xảy ra khi và chỉ khi rij=piqj, nghĩa là: P(X=xi,Y=yj)=p(X=xi)p(Y=yj) với 1≤i≤m, 1≤j≤n. Điều này có nghĩa là X và Y độc lập. H(X)+H(Y) = = = Mặt khác: H(X, Y) = H(X,Y) – H(X) – H(Y) = = = 1
• 31. mã học cơ sở Chương 1 31 Tiếp theo sẽ đưa ra khái niệm Entropy có điều kiện: Định nghĩa 1.5: Giả sử X và Y là hai biến ngẫu nhiên. Khi đó với giá trị xác định bất kỳ y của Y có một phân bố xác suất có điều kiện p(X|y). Rõ ràng là: 2( | ) ( | )log ( | ) x H X y p x y p x y  (1.22) Định nghĩa 1.6: Entropy có điều kiện H(X|Y) là trung bình có trọng số (ứng với các xác suất p(y) của Entropy H(X|y) trên mọi giá trị có thể y. H(X|y) được tính bằng: 2( | ) ( ) ( | )log ( | ) y x H X Y p y p x y p x y  (1.23) Entropy có điều kiện đo lượng thông tin trung bình về X do Y mang lại. Sau đây là 2 kết quả trực tiếp. Định lý 1.6: H(X,Y)=H(Y)+H(X|Y) (1.24) Hệ quả 1.2: H(X|Y)≤H(X) Dấu “=” xảy ra khi và chỉ khi X và Y độc lập. Các khóa giả và khoảng duy nhất: Trong phần này sẽ áp dụng các kết quả về Entropy ở trên cho các hệ mật. Trước tiên sẽ chỉ ra một quan hệ cơ bản giữa các Entropy của các thành phần trong hệ mật. Entropy có điều kiện H(K|C) được gọi là độ bất định về khoá. Nó cho biết về lượng thông tin về khoá thu được từ bản mã. Định lý 1.7: Giả sử (P, C, K, E, D) là một hệ mật. Khi đó: H(K|C) = H(K) + H(P) - H(C) (1.25) Giả sử (P, C, K, E, D) là hệ mật đang được sử dụng. Một xâu của thông điệp x1,x2,...,xn sẽ được mã hóa bằng một khoá để tạo ra bản mã y1,y2,...,yn. Nhớ lại rằng, mục
• 32. mã học cơ sở Chương 1 32 đích cơ bản của thám mã là phải xác định được khoá. Xem xét các phương pháp tấn công chỉ với bản mã và coi Oscar có khả năng tính toán vô hạn. Cũng giả sử Oscar biết thông điệp là một văn bản theo ngôn ngữ tự nhiên (chẳng hạn văn bản tiếng Anh). Nói chung Oscar có khả năng rút ra một số khoá nhất định (các khoá có thể hay các khoá chấp nhận được) nhưng trong đó chỉ có một khoá đúng, các khoá có thể còn lại (các khoá không đúng) được gọi là các khoá giả. Ví dụ, giả sử Oscar thu được một xâu bản mã WNAJW mã bằng phương pháp mã dịch vòng (MDV). Dễ dàng thấy rằng, chỉ có hai xâu thông điệp có ý nghĩa là river và arena tương ứng với các khoá F(= 5) và W(= 22). Trong hai khoá này chỉ có một khoá đúng, khoá còn lại là khoá giả. Trên thực tế, việc tìm một bản mã của MDV có độ dài 5 và 2 bản giải mã có nghĩa không phải quá khó khăn, bạn đọc có thể tìm ra nhiều ví dụ khác. Mục đích của là phải tìm ra giới hạn cho số trung bình các khoá giả. Trước tiên, phải xác định giá trị này theo Entropy (cho một ký tự) của một ngôn ngữ tự nhiên L (ký hiệu là HL). HL là lượng thông tin trung bình trên một ký tự trong một xâu có nghĩa của thông điệp. Chú ý rằng, một xâu ngẫu nhiên các ký tự của bảng chữ cái sẽ có Entropy trên một ký tự bằng log2 26  4,76. Có thể lấy H(P) là xấp xỉ bậc nhất cho HL. Trong trường hợp L là Anh ngữ, tính được H(P)  4,19. Dĩ nhiên các ký tự liên tiếp trong một ngôn ngữ không độc lập với nhau và sự tương quan giữa các ký tự liên tiếp sẽ làm giảm Entropy. Ví dụ, trong Anh ngữ, chữ Q luôn kéo theo sau là chữ U. Để làm xấp xỉ bậc hai, tính Entropy của phân bố xác suất của tất cả các bộ đôi rồi chia cho 2. Một cách tổng quát, định nghĩa Pn là biến ngẫu nhiên có phân bố xác suất của tất cả các bộ n của thông điệp. Sẽ sử dụng tất cả các định nghĩa sau: Định nghĩa 1.7: Giả sử L là một ngôn ngữ tự nhiên. Entropy của L được xác định là lượng sau: ( ) lim n L n H P H n  (1.26) Độ dư của L là: 21 ( / log | |)L LR H P  (1.27)
• 33. mã học cơ sở Chương 1 33 Nhận xét: HL đo Entropy trên mỗi ký tự của ngôn ngữ L. Một ngôn ngữ tự nhiên sẽ có Entropy là log2|P|. Bởi vậy đại lượng RL đo phần "ký tự vượt trội" là phần dư. Trong trường hợp Anh ngữ, dựa trên bảng chứa một số lớn các bộ đôi và các tần số, có thể tính được H(P2 ) . Ước lượng theo cách này, tính được H(P2 )  3,90. Cứ tiếp tục như vậy bằng cách lập bảng các bộ ba v.v... thu được ước lượng cho HL. Trên thực tế, bằng nhiều thực nghiệm khác nhau, có thể đi tới kết quả sau 1,0 1,5LH  . Tức là lượng thông tin trung bình trong tiếng Anh vào khoảng 1 bit tới 1,5 bit trên mỗi ký tự. Giả sử lấy 1,25 là giá trị ước lượng của giá trị của HL. Khi đó độ dư vào khoảng 0,75. Tức là tiếng Anh có độ dư vào khoảng 75%! (Điều này không có nghĩa loại bỏ tuỳ ý 3 trên 4 ký tự của một văn bản tiếng Anh mà vẫn có khả năng đọc được nó. Nó chỉ có nghĩa là tìm được một phép mã Huffman cho các bộ n với n đủ lớn, phép mã này sẽ nén văn bản tiếng Anh xuống còn 1/4 độ dài của bản gốc). Với các phân bố xác suất Cn đã cho trên K và Pn . Có thể xác định phân bố xác suất trên là tập các bộ n của bản mã. Đã xác định Pn là biến ngẫu nhiên biểu diễn bộ n của thông điệp. Tương tự Cn là biến ngẫu nhiên biểu thị bộ n của bản mã. Định lý 1.8: Giả sử (P, C, K, E, D) là một hệ mật trong đó |C|=|P| và các khóa được chọn đồng xác suất. Giả sử RL là độ dư của ngôn ngữ gốc. Khi đó với một xâu bản mã độ dài n cho trước(n đủ lớn), số trung bình các khóa giả sn thỏa mãn bất đẳng thức sau: {| | /(| | )} 1Ls K P nR  Lượng | | /(| | )} 1LK P nR  tiến tới 0 theo hàm mũ khi n tăng. Ước lượng này có thể không chính xác với các giá trị n nhỏ. Đó là do H(Pn )/n không phải là một ước lượng tốt cho HL nếu n nhỏ. Định nghĩa 1.8: Khoảng duy nhất của một hệ mật được định nghĩa là giá trị của n mà ứng với giá trị này, số khoá giả trung bình bằng 0 (ký hiệu giá trị này là n0 ). Điều đó có nghĩa là n0 là độ dài trung bình cần thiết của bản mã để thám mã có thể tính toán khoá một cách duy nhất với thời gian đủ lớn.
• 34. mã học cơ sở Chương 1 34 1.6.2. Lý thuyết số 1.6.2.1. Số nguyên Tập các số nguyên:{..., -3, -2, -1, 0, 1, 2, 3,...}=Z Định nghĩa 1.9: Cho ,a b Z, a là ước nguyên của b, nếu : .c b ac   . Ký hiệu a|b Các tính chất chia hết: , ,a b c   có:  a|a  Nếu a|b và b|c thì a|c  Nếu a|b và a|c thì a|(bx+cy) ,x y   Nếu a|b và b|a thì a=  b Định nghĩa 1.10: Thuật toán chia đối với các số nguyên: Nếu a và b là các số nguyên với b ≥1 thì a = qb +r , 0 ≤r
• 35. mã học cơ sở Chương 1 35  a|d, b|d.  Nếu có a|c, b|c thì d|c Như vậy d là số nguyên dương nhỏ nhất là bội của cả a và b. Tính chất: . ( , ) ( , ) a b BCNN a b a b  Ví dụ:(12,18) =6  BCNN(12,18)= 12.18 6 =36 Định nghĩa 1.14: Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau nếu (a,b)=1. Định nghĩa 1.15: Số nguyên p≥2 được gọi là số nguyên tố nếu các ước dương của nó chỉ là 1 và p. Ngược lại p được gọi là hợp số. Định lý 1.9: (Định lý cơ bản của số học) Với mỗi số nguyên n≥2 luôn phân tích được dưới dạng tích của lũy thừa các số nguyên tố. 1 2 1 2 ... kee e kn p p p (1.28) Trong đó pi là các số nguyên tố khác nhau và ei là các số nguyên dương. Hơn nữa phân tích trên là duy nhất. Định nghĩa 1.16: Với n≥2, hàm ( )n được xác định là các số nguyên trong khoảng [1.n] nguyên tố cùng nhau với n. Các tính chất của hàm ( )n - Nếu p là số nguyên tố thì ( ) 1p p   - Nếu (m,n)=1 thì ( . ) ( ). ( )m n m n   - Nếu 1 2 1 2 ... kee e kn p p p là phân tích ra thừa số nguyên tố của n thì: 1 2 1 1 1 ( ) (1 )(1 )...(1 ) k n n p p p      (1.29)
• 36. mã học cơ sở Chương 1 36 1.6.2.2. Khái niệm đồng dư modulo Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó viết ab(mod m) nếu a và b khi chia cho m có cùng số dư, tức là (a-b) chia hết cho m. Mệnh đề ab(mod m) được gọi là “a đồng dư với b theo mođun m”. Chứng minh: Giả sử chia a và b cho m và thu được thương nguyên và phần dư, các phần dư nằm giữa 0 và m-1. Nghĩa là: a = q1 m + r1 và b = q2 m + r2 Trong đó : 0r1m-1 và 0r2m-1. Khi đó có thể dễ dàng thấy rằng: a  b(mod m) khi và chỉ khi r1 = r2 Tiếp theo sẽ dùng ký hiệu a mod m để xác định phần dư khi a được chia cho m (chính là giá trị r1 ở trên). Như vậy: ab(mod m) khi và chỉ khi: (a mod m) = (b mod m) Nếu thay giá trị của a bằng giá trị (a mod m) thì nói a được rút gọn theo modulo m 1.6.2.3. Số học modulo Định nghĩa số học mođun m: Zm được coi là tập hợp {0,1,…,m-1} có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong Zm được thực hiện giống như cộng và nhân các số thực ngoại trừ một điểm là các kết quả được rút gọn theo mođun m. Ví dụ: Z26 được coi là tập hợp {0,1, 2…,25} có trang bị hai phép toán cộng và nhân. 25+7 = 32 mod 26 = 6 ( ví dụ K=7, ‘Z’  ‘H’) 5*9 = 45 mod 26 = 19 Định lý về đồng dư thức Đồng dư thức ax b (mod m) chỉ có một nghiệm duy nhất x Zm với mọi bZm khi và chỉ khi UCLN(a,m) =1. Chứng minh: - Giả sử rằng, UCLN(a,m) = d >1.
• 37. mã học cơ sở Chương 1 37 - Với b = 0 thì đồng dư thức ax0 (mod m) sẽ có ít nhất hai nghiệm phân biệt trong Zm là x = 0 và x = m/d. Khái niệm phần tử nghịch đảo: - Giả sử a  Zm. - Phần tử nghịch đảo (theo phép nhân) của a là phần tử a-1  Zm sao cho: aa-1  a-1 a1 (mod m) Tính chất - a có nghịch đảo theo mođun m khi và chỉ khi UCLN(a,m) = 1, - Nếu nghịch đảo tồn tại thì phải là duy nhất. - Nếu b = a-1 thì a = b-1 . - Nếu m là số nguyên tố thì mọi phần tử khác không của Zm đều có nghịch đảo. 1.6.3. Độ phức tạp thuật toán 1.6.3.1. Khái niệm về thuật toán Có thể định nghĩa thuật toán theo nhiều cách khác nhau. Ở đây sẽ hiểu khái niệm thuật toán theo một cách thông thường nhất. Định nghĩa: Thuật toán là một quy tắc để với những dữ liệu ban đầu đã cho, tìm được lời giải của bài toán được xét sau một khoảng thời gian hữu hạn. Để minh họa cách ghi một thuật toán cũng như tìm hiểu các yêu cầu đề ra cho thuật toán, xét trên các ví dụ cụ thể sau đây: Cho n số X[1], X[2],…, X[n], cần tìm m và j sao cho: m=X[j] = 1 max [ ] k n X k   và j là lớn nhất có thể. Điều đó có nghĩa là cần tìm cực đại của các số đã cho và chỉ số lớn nhất trong các số cực đại. Với mục tiêu tìm số cực đại với chỉ số lớn nhất, xuất phát từ giá trị X [n]. Bước thứ nhất, vì mới chỉ có một số có thể tạm thời xem m = X [n] và j = n. Tiếp theo so sánh X [n] với X[n-1]. Nếu X[n] không nhỏ hơn X [n-1] thì giữ nguyên, trong trường hợp ngược lại, X[n-1] chính là số cực đại trong hai số đã xét và phải thay đổi m và j. Đặt m = X [n-1], j=1,...,n-1. Với cách làm như trên, ở mỗi bước luôn nhận được số cực
• 38. mã học cơ sở Chương 1 38 đại trong số những số đã xét. Bước tiếp theo là so sánh nó với những số đứng trước hoặc kết thúc thuật toán trong trường hợp không còn số nào đứng trước nó. 1.6.3.2. Độ phức tạp của thuật toán Thời gian làm việc của máy tính khi chạy một thuật toán nào đó không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào máy tính được sử dụng. Vì thế, để có một tiêu chuẩn chung, sẽ đo độ phức tạp của một thuật toán bằng số các phép tính phải làm khi thực hiện thuật toán. Khi tiến hành cùng một thuật toán, số các phép tính phải thực hiện còn phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp của thuật toán sẽ là một hàm số của độ lớn đầu vào. Trong những ứng dụng thực tiễn, không cần biết chính xác hàm này mà chỉ cần biết “cỡ” của chúng, tức là cần có một ước lượng đủ tốt của chúng. Trong khi làm việc, máy tính thường ghi các chữ số bằng bóng đèn “sáng, tắt”, bóng đèn sáng chỉ số 1, bóng đèn tắt chỉ số 0. Vì thế để thuận tiện nhất là dùng hệ đếm cơ số 2, trong đó để biểu diễn một số, chỉ cần dùng hai ký hiệu 0 và 1. Một ký hiệu 0 hoặc 1 được gọi là 1bit “viết tắt của binary digit”. Một số nguyên n biểu diễn bởi k chữ số 1 và 0 được gọi là một số k bit . Độ phức tạp của một thuật toán được đo bằng số các phép tính bit. Phép tính bit là một phép tính logic hay số học thực hiện trên các số một bit 0 và 1. Để ước lượng độ phức tạp của thuật toán dùng khái niệm bậc O lớn. Định nghĩa: Giả sử f[n] và g[n] là hai hàm xác định trên tập hợp các số nguyên dương. Nói f[n] có bậc O lớn của g[n] và viết f[n] =O(g[n]), nếu tồn tại 1 số C>0 sao cho với n đủ lớn, các hàm f[n] và g[n] đều dương thì f[n] < C g[n]. Ví dụ:  Giả sử f[n] là đa thức có công thức: 1 1 1 0[ ] ...d d d df n a n a n a n a      trong đó ad>0. Dễ dàng chứng minh được f[n]=O(nd ).  Nếu f1[n]=O(g[n]), f2[n]=O(g[n]) thì f1+f2=O(g).  Nếu f1=O(g1), f2=O(g2) thì f1f2=O(g1g2).  Nếu tồn tại giới hạn hữu hạn:
• 39. mã học cơ sở Chương 1 39 [ ] lim [ ]n f n g n thì f=O(g)  Với mọi số ε > 0, log n = O( n ) Định nghĩa: Một thuật toán được gọi là có độ phức tạp đa thức hoặc có thời gian đa thức, nếu số các phép tính cần thiết để thực hiện thuật toán không vượt quá O(log )d n , trong đó n là độ lớn của đầu vào và d là số nguyên dương nào đó. Nói cách khác nếu đầu vào là các số k bit thì thời gian thực hiện thuật toán là O(kd ), tức là tương đương với một đa thức của k . Các thuật toán với thời gian O( ), 0n   được gọi là thuật toán với độ phức tạp mũ hoặc thời gian mũ. Chú ý rằng nếu một thuật toán nào đó có độ phức tạp O(g) thì cũng có thể nói nó có độ phức tạp O(h) với mọi hàm h > g. Tuy nhiên luôn luôn cố gắng tìm ước lượng tốt nhất có thể để tránh hiểu sai về độ phức tạp thực sự của thuật toán. Cũng có những thuật toán có độ phức tạp trung gian giữa đa thức và mũ. Thường gọi đó là thuật toán dưới mũ. Chẳng hạn thuật toán nhanh nhất được biết hiện nay để phân tích một số nguyên n ra thừa số là thuật toán có độ phức tạp: exp ( log loglog )n n Khi giải một bài toán không những chỉ cố gắng tìm ra một thuật toán nào đó, mà còn muốn tìm ra thuật toán “tốt nhất”. Đánh giá độ phức tạp là một trong những cách để phân tích, so sánh và tìm ra thuật toán tối ưu. Tuy nhiên độ phức tạp không phải là tiêu chuẩn duy nhất để đánh giá thuật toán. Có những thuật toán về lý thuyết thì có độ phức tạp cao hơn một thuật toán khác, nhưng khi sử dụng lại có kết quả (gần đúng) nhanh hơn nhiều. Điều này còn tùy thuộc vào những bài toán cụ thể, những mục tiêu cụ thể và cả kinh nghiệm của người sử dụng.
• 40. mã học cơ sở Chương 1 40 Cần lưu ý thêm một số điểm sau đây: Mặc dù định nghĩa thuật toán đưa ra chưa phải là chặt chẽ, nó vẫn quá “cứng nhắc” trong những ứng dụng thực tế. Bởi vậy cần đến các thuật toán “xác suất”, tức là các thuật toán phụ thuộc vào một hay nhiều tham số ngẫu nhiên. Những “thuật toán” này về nguyên tắc không được gọi là thuật toán vì chúng có thể không bao giờ kết thúc với xác suất rất bé. Tuy nhiên thực nghiệm chỉ ra rằng, các thuật toán xác suất thường hữu hiệu hơn các thuật toán không xác suất. Thậm chí trong rất nhiều trường hợp, chỉ có các thuật toán như thế là sử dụng được. Khi làm việc với các thuật toán xác suất, thường hay phải sử dụng các số “ngẫu nhiên”. Khái niệm chọn số ngẫu nhiên cũng cần được chính xác hóa. Thường thì người ta sử dụng một “máy” sản xuất số giả ngẫu nhiên nào đó. Tuy nhiên ở đây khi nói đến việc chọn số ngẫu nhiên, có thể hiểu đó là việc được thực hiện trên máy. Cần chú ý ngay rằng, đối với các thuật toán xác suất, không thể nói đến thời gian tuyệt đối, mà chỉ có thể nói đến thời gian hy vọng (expected). Để hình dung được phần nào “độ phức tạp” của các thuật toán khi làm việc với những số lớn, xem Bảng 1.1 dưới đây cho khoảng thời gian cần thiết để phân tích một số nguyên n ra thừa số nguyên tố bằng thuật toán nhanh nhất được biết hiện nay. Bảng 1. 1. Độ phức tạp để phân tích số nguyên ra thừa số nguyên tố Số chữ số thập phân Số phép tính bit Thời gian 50 1,4.1010 3,9 giờ 75 9.1012 104 ngày 100 2,3.1015 74 năm 200 1,2.1023 3,8.109 năm 300 1,5.1029 4,9.1015 năm 500 1,3.1039 4,2.1025 năm Từ Bảng 1.1, thấy rằng ngay với một thuật toán dưới mũ, thời gian làm việc với các số nguyên lớn là quá lâu. Vì thế nói chung con người luôn cố gắng tìm những thuật toán đa thức.
• 41. mã học cơ sở Chương 1 41 1.7. CÂU HỎI VÀ BÀI TẬP 1) Độ an toàn thuật toán là gì?. Hãy trình bày một số tiêu chí cơ bản để đánh giá độ an toàn của một thuật toán?. 2) Hãy trình bày về các phương pháp phân loại mã hóa?. 3) Hãy nêu vai trò của mật mã học?. 4) Trình bày ưu nhược điểm của giao thức Kerberos?. 5) Hãy trình bày khái quát về Krypto Knight?. 6) Hãy trình bày về các mô hình hoạt động của PGP?. 7) Thẻ thông minh được chia thành mấy loại?. Hãy nêu chức năng và vai trò của thẻ thông minh?. 8) Hãy nêu định nghĩa về độ an toàn tính toán của hệ mật trong lý thuyết xác suất?. 9) Hãy nêu định nghĩa về độ phức tạp tính toán?.
• 42. mã học cơ sở Chương 2 42 CHƯƠNG 2: MÃ HÓA KHÓA ĐỐI XỨNG Chương 2 cung cấp các kiến thức về hệ mật khóa đối xứng cũng như nguyên tắc mã hóa, giải mã của một số thuật toán mã hóa khóa đối xứng. Ngoài ra, chương 2 trình bày một số ưu và nhược điểm của các kỹ thuật mã hóa khóa đối xứng. 2.1. GIỚI THIỆU VỀ MÃ HÓA KHÓA ĐỐI XỨNG Trong phần giới thiệu về mật mã học ở chương 1, bài giảng đã giới thiệu về một số khái niệm trong mật mã. Trong phần này, bài giảng sẽ giới thiệu về đặc điểm của mã hóa khóa đối xứng. Hình 2.1 mô tả quy trình mã hóa và giải mã của mã hóa khóa bất đối xứng. Hình 2. 1: Mô hình mã hóa đối xứng Một hệ mật là một bộ 5 (P, C, K, E, D) thoả mãn các điều kiện sau: - P là một tập hữu hạn các bản rõ có thể. - C là một tập hữu hạn các bản mã có thể. - K là một tập hữu hạn các khoá có thể (không gian khoá). - Đối mỗi Kk  có một quy tắc mã Eek  CPek : và quy tắc giải mã tương ứng Ddk  PCdk : sao cho    xxed kk  với Px .
• 43. mã học cơ sở Chương 2 43 Lịch sử ra đời mã hóa cách đây hàng ngàn năm. Trong quá trình phát triển thì các kỹ thuật mã hóa trước kia đều sử dụng 1 khóa cho cả quá trình mã hóa và giải mã. Chính vì vậy, trong mã hóa khóa đối xứng chia thành 2 giai đoạn phát triển chính đó là: các kỹ thuật mã hóa cổ điển và các kỹ thuật mã hóa hiện đại. Phần tiếp theo, bài giảng trình bày một số thuật toán thuộc cả 2 giai đoạn phát triển này. 2.2. CÁC KỸ THUẬT MÃ HÓA ĐỐI XỨNG CỔ ĐIỂN 2.2.1. Phương pháp thay thế Mã hóa thay thế là phương pháp thay thế mỗi ký tự thông điệp thành ký tự bản mã. Từ đó, người nhận có thể thay thế ngược lại những ký tự của bản mã để được thông điệp. Trong mật mã học cổ điển, có một số phương pháp mã hóa thay thế : - Mã hóa thay thế đơn bảng. - Mã hóa thay thế đa ký tự. - Mã hóa thay thế đa bảng. 2.2.1.1. Phương pháp mã hóa thay thế đơn bảng Trước khi tìm hiểu phương pháp thay thế đơn bảng, hãy đi tìm hiểu mã hóa Caesar (Caesar Cipher). a. Phương pháp Caesar Thế kỷ thứ 3 trước công nguyên, nhà quân sự người La Mã Julius Caesar đã nghĩ ra phương pháp mã hóa một thông điệp như sau: thay thế mỗi chữ trong thông điệp bằng chữ đứng sau nó k vị trí trong bảng chữ cái. Giả sử chọn k = 3, có bảng chuyển đổi như sau: Chữ ban đầu a b c d e f g h i j k l m n o p q r s t u v w x y z Chữ thay thế D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
• 44. mã học cơ sở Chương 2 44 Chú ý: sau Z sẽ vòng lại là A, do đó x  A, y  B và z  C Giả sử có thông điệp gốc: meet me after the toga party Như vậy bản mã sẽ là: PHHW PH DIWHU WKH WRJD SDUWB Thay vì gửi trực tiếp thông điệp cho các cấp dưới, Ceasar gửi bản mã. Khi cấp dưới nhận được bản mã, tiến hành giải mã theo quy trình ngược lại để có được thông điệp. Như vậy nếu đối thủ của Ceasar có lấy được bản mã, thì cũng không hiểu được ý nghĩa của bản mã. Gán cho mỗi chữ cái theo thứ tự từ A đến Z một con số nguyên theo thứ tự từ 0 đến 25. Phương pháp Ceasar được biểu diễn như sau: với mỗi chữ cái p thay bằng chữ mã hóa C, trong đó: C = (p + k) mod 26 (trong đó mod là phép chia lấy số dư) Và quá trình giải mã đơn giản là: p = (C – k) mod 26. Trong đó k được gọi là khóa. Dĩ nhiên là Ceasar và cấp dưới phải cùng dùng chung một giá trị khóa k, nếu không thông điệp giải mã sẽ không giống thông điệp ban đầu. Ngày nay phương pháp mã hóa của Ceasar không được xem là an toàn. Giả sử đối thủ của Ceasar có được bản mã PHHW PH DIWHU WKH WRJD SDUWB và biết được phương pháp mã hóa và giải mã là phép cộng trừ modulo 26. “Kẻ tấn công” có thể thử tất cả 25 trường hợp của k như bảng 2.1: Bảng 2. 1: Bảng thống kê kết quả tấn công vét cạn KEY PHHW PH DIWHU WKH WRJD SDUWB 1 oggv og chvgt vjg vqic rctva 2 nffu nf bgufs uif uphb qbsuz 3 meet me after the toga party 4 ldds ld zesdq sgd snfz ozqsx 5 kccr kc ydrcp rfc rmey nyprw 6 jbbq jb xcqbo qeb qldx mxoqv 7 iaap ia wbpan pda pkcw lwnpu 8 hzzo hz vaozm ocz ojbv kvmot
• 45. mã học cơ sở Chương 2 45 9 gyyn gy uznyl nby niau julns 10 fxxm fx tymxk max mhzt itkmr 11 ewwl ew sxlwj lzw lgys hsjlq 12 dvvk dv rwkvi kyv kfxr grikp 13 cuuj cu qvjuh jxu jewq fqhjo 14 btti bt puitg iwt idvp epgin 15 assh as othsf hvs hcuo dofhm 16 zrrg zr nsgre gur gbtn cnegl 17 yqqf yq mrfqd ftq fasm bmdfk 18 xppe xp lqepc esp ezrl alcej 19 wood wo kpdob dro dyqk zkbdi 20 vnnc vn jocna cqn cxpj yjach 21 ummb um inbmz bpm bwoi xizbg 22 tlla tl hmaly aol avnh whyaf 23 skkz sk glzkx znk zumg vgxze 24 rjjy rj fkyjw ymj ytlf ufwyd 25 qiix qi ejxiv xli xske tevxc Trong 25 trường hợp trên, chỉ có trường hợp k = 3 thì bản giải mã tương ứng là có ý nghĩa. Do đó “Kẻ tấn công” có thể chắc chắn rằng “meet me after the toga party” là thông điệp ban đầu. b. Phương pháp thay thế đơn bảng (Monoalphabetic Substitution Cipher) Xét lại phương pháp Caersar với k = 3: Chữ ban đầu a b c d e f g h i j k l m n o p q r s t u v w x y z Chữ thay thế D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Phương pháp đơn bảng tổng quát hóa phương pháp Ceasar bằng cách dòng mã hóa không phải là một dịch chuyển k vị trí của các chữ cái A, B, C, …nữa mà là một hoán vị
• 46. mã học cơ sở Chương 2 46 của 26 chữ cái này. Lúc này mỗi hoán vị được xem như là một khóa. Giả sử có hoán vị sau: Chữ ban đầu a b c d e f g h i j K l m n o p q r s t u v w x y z Khóa Z P B Y J R S K F L X Q N W V D H M G U T O I A E C Như vậy thông điệp meet me after the toga party được mã hóa thành: NJJU NJ ZRUJM UKJ UVSZ DZMUE Quá trình giải mã được tiến hành ngược lại để cho ra thông điệp ban đầu. Việc mã hóa được tiến hành bằng cách thay thế một chữ cái trong thông điệp thành một chữ cái trong bản mã, nên phương pháp này được gọi là phương pháp thay thế. Số lượng hoán vị của 26 chữ cái là 26!, đây cũng chính là số lượng khóa của phương pháp này. Vì 26! là một con số khá lớn nên việc tấn công phá mã vét cạn khóa là bất khả thi (6400 thiên niên kỷ với tốc độ thử khóa là 109 khóa/giây). Vì vậy mã hóa đơn bảng đã được xem là một phương pháp mã hóa an toàn trong suốt 1000 năm sau công nguyên. 2.2.1.2. Phương pháp thay thế đa ký tự a. Mã hóa Playfair Bảng 2. 2: Ma trận mã hóa Playfair M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z
• 47. mã học cơ sở Chương 2 47 Mã hóa Playfair sử dụng đơn vị mã hóa là 2 ký tự đứng sát nhau. Như vậy hai ký tự này được thay thế cùng một lúc bởi hai ký tự khác. Mã hóa Playfair dùng một ma trận 5x5 (Matrix State). Trong bảng trên, khóa MONARCHY được điền vào dòng đầu tiên và 3 ký tự dòng thứ 2 của bảng. Các ô còn lại được điền các chữ cái theo thứ tự của bảng chữ cái Tiếng Anh. Riêng 2 chữ I và J được điền vào chung 1 ô vì trong Tiếng Anh hai chữ cái này ít bị nhầm lẫn. Ví dụ: khi gặp chữ SM_LE thì sẽ đoán được chữ đó là SMILE chứ không thể nào là SMJLE được. Trước khi tiến hành mã hóa, thông điệp được tách ra thành các cặp ký tự. Nếu 2 ký tự trong một cặp giống nhau thì sẽ được thay chữ cái đứng sau trong cặp đó bằng chữ X (vì trong Tiếng Anh thì thường 2 chữ X rất hiếm khi đứng cạnh nhau). Ví dụ: từ football sẽ được tách thành 4 cặp fo ot ba lx. Quy tắc mã hóa như sau : - Nếu 2 ký tự được mã hóa thuộc cùng 1 hàng, thì được thay thế bằng 2 ký tự tiếp theo trong hàng. Nếu đến cuối hàng thì quay về đầu hàng. Ví dụ: cặp LP thay bằng PQ, cặp ST thay bằng TU. - Nếu 2 ký tự trong cặp thuộc cùng 1 cột, thì được thay bằng 2 ký tự tiếp theo trong cột. Nếu đến cuối cột thì quay về đầu cột. Ví dụ cặp OV được mã hóa thành HO. - Trong các trường hợp còn lại, 2 ký tự được mã hóa sẽ tạo thành đường chéo của 1 hình chữ nhật và được thay bằng 2 ký tự trên đường chéo kia. Ví dụ: HS trở thành BP (B cùng dòng với H và P cùng dòng với S); EA trở thành IM (hoặc JM). Như vậy nếu chỉ xét trên 26 chữ cái thì mã hóa Playfair có 26x26=676 cặp chữ cái, do đó các cặp chữ cái này ít bị chênh lệch về tần suất hơn so với sự chênh lệnh tần suất của từng chữ cái. Ngoài ra số lượng các cặp chữ cái nhiều hơn cũng làm cho việc phá mã tần suất khó khăn hơn. Đây chính là lý do mà người ta tin rằng mã hóa Playfair không thể bị phá và được quân đội Anh sử dụng trong chiến tranh thế giới lần thứ nhất.
• 48. mã học cơ sở Chương 2 48 b. Mã hóa Hill Trong mã hóa Hill, mỗi chữ cái (A – Z) được gán tương ứng với 1 số nguyên từ 0 đến 25. Đơn vị mã hóa của mã hóa Hill là 1 khối (block) m ký tự thông điệp (ký hiệu p1p2…pm) thành 1 khối (block) m ký tự bản mã (ký hiệu c1c2…cm). Việc thay thế này được thực hiện bằng m phương trình tuyến tính. Giả sử m = 3, minh họa m phương trình đó như sau: Dạng phương trình : c1 = k11p1 + k12p2 + k13p3 mod 26 c2 = k21p1 + k22p2 + k23p3 mod 26 c3 = k31p1 + k32p2 + k33p3 mod 26 Dạng ma trận : 11 12 131 2 21 22 23 3 31 32 33 p1 mod 26p2 p3 k k kc k kc k c k kk                             Hay: C = KP mod 26 với P và C là vector đại diện cho thông điệp và bản mã, còn K là ma trận dùng làm khóa. Xét ví dụ thông điệp là paymoremoney cùng với khóa K là : K = 17 17 5 21 18 21 2 2 19          Ba chữ cái đầu tiên của thông điệp tương ứng với vector (15, 0, 24). Vậy 17 17 5 5 11 21 18 21 0 mod 26 23 2 2 19 24 18 LNS                              Thực hiện tương tự có bản mã đầy đủ là LNSHDLEWMTRW.