Giáo trình Mã hóa và ứng dụng

289 trang ngocly 160

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Mã hóa và ứng dụng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ma_hoa_va_ung_dung.pdf

Nội dung text: Giáo trình Mã hóa và ứng dụng

Lời giới thiệu Mật mã (Cryptography) là ngành khoa học là ngành nghiên cứu các kỹ thuật tốn học nhằm cung cấp các dịch vụ bảo vệ thơng tin [44]. Đây là ngành khoa học quan trọng, cĩ nhiều ứng dụng trong đời sống – xã hội. Khoa học mật mã đã ra đời từ hàng nghìn năm. Tuy nhiên, trong suốt nhiều thế kỷ, các kết quả của lĩnh vực này hầu như khơng được ứng dụng trong các lĩnh vực dân sự thơng thường của đời sống – xã hội mà chủ yếu được sử dụng trong lĩnh vực quân sự, chính trị, ngoại giao Ngày nay, các ứng dụng mã hĩa và bảo mật thơng tin đang được sử dụng ngày càng phổ biến trong các lĩnh vực khác nhau trên thế giới, từ các lĩnh vực an ninh, quân sự, quốc phịng , cho đến các lĩnh vực dân sự như thương mại điện tử, ngân hàng Với sự phát triển ngày càng nhanh chĩng của Internet và các ứng dụng giao dịch điện tử trên mạng, nhu cầu bảo vệ thơng tin trong các hệ thống và ứng dụng điện tử ngày càng được quan tâm và cĩ ý nghĩa hết sức quan trọng. Các kết quả của khoa học mật mã ngày càng được triển khai trong nhiều lĩnh vực khác nhau của đời sống – xã hội, trong đĩ phải kể đến rất nhiều những ứng dụng đa dạng trong lĩnh vực dân sự, thương mại Các ứng dụng mã hĩa thơng tin cá nhân, trao đổi thơng tin kinh doanh, thực hiện các giao dịch điện tử qua mạng đã trở nên gần gũi và quen thuộc với mọi người. Cùng với sự phát triển của khoa học máy tính và Internet, các nghiên cứu và ứng dụng của mật mã học ngày càng trở nên đa dạng hơn, mở ra nhiều hướng nghiên cứu chuyên sâu vào từng lĩnh vực ứng dụng đặc thù với những đặc trưng riêng. Ứng dụng của khoa học mật mã khơng chỉ đơn thuần là mã hĩa và giải mã thơng tin mà cịn bao gồm nhiều vấn đề khác nhau cần được nghiên cứu và giải quyết, ví dụ như chứng thực nguồn gốc 1
nội dung thơng tin (kỹ thuật chữ ký điện tử), chứng nhận tính xác thực về người sở hữu mã khĩa (chứng nhận khĩa cơng cộng), các quy trình giúp trao đổi thơng tin và thực hiện giao dịch điện tử an tồn trên mạng Các ứng dụng của mật mã học và khoa học bảo vệ thơng tin rất đa dạng và phong phú; tùy vào tính đặc thù của mỗi hệ thống bảo vệ thơng tin mà ứng dụng sẽ cĩ các tính năng với đặc trưng riêng. Trong đĩ, chúng ta cĩ thể kể ra một số tính năng chính của hệ thống bảo vệ thơng tin: • Tính bảo mật thơng tin: hệ thống đảm bảo thơng tin được giữ bí mật. Thơng tin cĩ thể bị phát hiện, ví dụ như trong quá trình truyền nhận, nhưng người tấn cơng khơng thể hiểu được nội dung thơng tin bị đánh cắp này. • Tính tồn vẹn thơng tin: hệ thống bảo đảm tính tồn vẹn thơng tin trong liên lạc hoặc giúp phát hiện rằng thơng tin đã bị sửa đổi. • Xác thực các đối tác trong liên lạc và xác thực nội dung thơng tin trong liên lạc. • Chống lại sự thối thác trách nhiệm: hệ thống đảm bảo một đối tác bất kỳ trong hệ thống khơng thể từ chối trách nhiệm về hành động mà mình đã thực hiện Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu cầu đa dạng của các hệ thống ứng dụng khác nhau trong thực tế, ví dụ như hệ thống bỏ phiếu bầu cử qua mạng, hệ thống đào tạo từ xa, hệ thống quản lý an ninh của các đơn vị với hướng tiếp cận sinh trắc học, hệ thống cung cấp dịch vụ đa phương tiện trên mạng với yêu cầu cung cấp dịch vụ và bảo vệ bản quyền sở hữu trí tuệ đối với thơng tin số 2
Khi biên soạn tập sách này, nhĩm tác giả chúng tơi mong muốn giới thiệu với quý độc giả những kiến thức tổng quan về mã hĩa và ứng dụng, đồng thời trình bày và phân tích một số phương pháp mã hĩa và quy trình bảo vệ thơng tin an tồn và hiệu quả trong thực tế. Bên cạnh các phương pháp mã hĩa kinh điển nổi tiếng đã được sử dụng rộng rãi trong nhiều thập niên qua như DES, RSA, MD5 , chúng tơi cũng giới thiệu với bạn đọc các phương pháp mới, cĩ độ an tồn cao như chuẩn mã hĩa AES, phương pháp ECC, chuẩn hàm băm mật mã SHA224/256/384/512 Các mơ hình và quy trình chứng nhận khĩa cơng cộng cũng được trình bày trong tập sách này. Nội dung của sách gồm 10 chương. Sau phần giới thiệu tổng quan về mật mã học và khái niệm về hệ thống mã hĩa ở chương 1, từ chương 2 đến chương 5, chúng ta sẽ đi sâu vào tìm hiểu hệ thống mã hĩa quy ước, từ các khái niệm cơ bản, các phương pháp đơn giản, đến các phương pháp mới như Rijndael và các thuật tốn ứng cử viên AES. Nội dung của chương 6 giới thiệu hệ thống mã hĩa khĩa cơng cộng và phương pháp RSA. Chương 7 sẽ trình bày về khái niệm chữ ký điện tử cùng với một số phương pháp phổ biến như RSA, DSS, ElGamal. Các kết quả nghiên cứu ứng dụng lý thuyết đường cong elliptic trên trường hữu hạn vào mật mã học được trình bày trong chương 8. Chương 9 giới thiệu về các hàm băm mật mã hiện đang được sử dụng phổ biến như MD5, SHS cùng với các phương pháp mới được cơng bố trong thời gian gần đây như SHA-256/384/512. Trong chương 10, chúng ta sẽ tìm hiểu về hệ thống chứng nhận khĩa cơng cộng, từ các mơ hình đến quy trình trong thực tế của hệ thống chứng nhận khĩa cơng cộng, cùng với một ví dụ về việc kết hợp hệ thống mã hĩa quy ước, hệ thống mã hĩa khĩa cơng cộng và chứng nhận khĩa cơng cộng để xây dựng hệ thống thư điện tử an tồn. 3
Với bố cục và nội dung nêu trên, chúng tơi hi vọng các kiến thức trình bày trong tập sách này sẽ là nguồn tham khảo hữu ích cho quý độc giả quan tâm đến lĩnh vực mã hĩa và ứng dụng. Mặc dù đã cố gắng hồn thành sách với tất cả sự nỗ lực nhưng chắc chắn chúng tơi vẫn cịn những thiếu sĩt nhất định. Kính mong sự cảm thơng và sự gĩp ý của quý độc giả. NHĨM TÁC GIẢ: TS. Dương Anh Đức - ThS. Trần Minh Triết cùng với sự đĩng gĩp của các sinh viên Khoa Cơng nghệ Thơng tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia thành phố Hồ Chí Minh. Văn Đức Phương Hồng Phan Thị Minh Đức Nguyễn Minh Huy Lương Vĩ Minh Nguyễn Ngọc Tùng Thành phố Hồ Chí Minh, tháng 01 năm 2005 4
Mục lục Chương 1 Tổng quan 15 1.1 Mật mã học 15 1.2 Hệ thống mã hĩa (cryptosystem) 16 1.3 Hệ thống mã hĩa quy ước (mã hĩa đối xứng) 18 1.4 Hệ thống mã hĩa khĩa cơng cộng (mã hĩa bất đối xứng) 19 1.5 Kết hợp mã hĩa quy ước và mã hĩa khĩa cơng cộng 19 Chương 2 Một số phương pháp mã hĩa quy ước 20 2.1 Hệ thống mã hĩa quy ước 20 2.2 Phương pháp mã hĩa dịch chuyển 21 2.3 Phương pháp mã hĩa thay thế 22 2.4 Phương pháp Affine 23 2.5 Phương pháp Vigenere 28 2.6 Phương pháp Hill 29 2.7 Phương pháp mã hĩa hốn vị 30 2.8 Phương pháp mã hĩa bằng phép nhân 31 2.8.1 Phương pháp mã hĩa bằng phép nhân 31 2.8.2 Xử lý số học 32 2.9 Phương pháp DES (Data Encryption Standard) 33 2.9.1 Phương pháp DES 33 2.9.2 Nhận xét 36 2.10 Phương pháp chuẩn mã hĩa nâng cao AES 37 Chương 3 Phương pháp mã hĩa Rijndael 39 3.1 Giới thiệu 39 3.2 Tham số, ký hiệu, thuật ngữ và hàm 40 3.3 Một số khái niệm tốn học 42 5
3.3.1 Phép cộng 43 3.3.2 Phép nhân 43 3.3.3 Đa thức với hệ số trên GF(28) 46 3.4 Phương pháp Rijndael 49 3.4.1 Quy trình mã hĩa 50 3.4.2 Kiến trúc của thuật tốn Rijndael 52 3.4.3 Phép biến đổi SubBytes 53 3.4.4 Phép biến đổi ShiftRows 55 3.4.5 Phép biến đổi MixColumns 56 3.4.6 Thao tác AddRoundKey 58 3.5 Phát sinh khĩa của mỗi chu kỳ 59 3.5.1 Xây dựng bảng khĩa mở rộng 59 3.5.2 Xác định khĩa của chu kỳ 61 3.6 Quy trình giải mã 62 3.6.1 Phép biến đổi InvShiftRows 63 3.6.2 Phép biến đổi InvSubBytes 64 3.6.3 Phép biến đổi InvMixColumns 66 3.6.4 Quy trình giải mã tương đương 67 3.7 Các vấn đề cài đặt thuật tốn 69 3.7.1 Nhận xét 72 3.8 Kết quả thử nghiệm 73 3.9 Kết luận 74 3.9.1 Khả năng an tồn 74 3.9.2 Đánh giá 75 Chương 4 Phương pháp Rijndael mở rộng 77 4.1 Nhu cầu mở rộng phương pháp mã hĩa Rijndael 77 4.2 Phiên bản mở rộng 256/384/512-bit 78 4.2.1 Quy trình mã hĩa 79 4.2.2 Phát sinh khĩa của mỗi chu kỳ 86 4.2.3 Quy trình giải mã 88 4.2.4 Quy trình giải mã tương đương 93 4.3 Phiên bản mở rộng 512/768/1024-bit 94 4.4 Phân tích mật mã vi phân và phân tích mật mã tuyến tính 95 4.4.1 Phân tích mật mã vi phân 95 4.4.2 Phân tích mật mã tuyến tính 96 6
4.4.3 Branch Number 98 4.4.4 Sự lan truyền mẫu 99 4.4.5 Trọng số vết vi phân và vết tuyến tính 107 4.5 Khảo sát tính an tồn đối với các phương pháp tấn cơng khác 108 4.5.1 Tính đối xứng và các khĩa yếu của DES 108 4.5.2 Phương pháp tấn cơng Square 109 4.5.3 Phương pháp nội suy 109 4.5.4 Các khĩa yếu trong IDEA 110 4.5.5 Phương pháp tấn cơng khĩa liên quan 110 4.6 Kết quả thử nghiệm 111 4.7 Kết luận 113 Chương 5 Các thuật tốn ứng cử viên AES 115 5.1 Phương pháp mã hĩa MARS 115 5.1.1 Quy trình mã hĩa 116 5.1.2 S–box 117 5.1.3 Khởi tạo và phân bố khĩa 118 5.1.4 Quy trình mã hĩa 123 5.1.5 Quy trình giải mã 135 5.2 Phương pháp mã hĩa RC6 137 5.2.1 Khởi tạo và phân bố khĩa 138 5.2.2 Quy trình mã hĩa 139 5.2.3 Quy trình giải mã 143 5.3 Phương pháp mã hĩa Serpent 144 5.3.1 Thuật tốn SERPENT 144 5.3.2 Khởi tạo và phân bố khĩa 144 5.3.3 S–box 147 5.3.4 Quy trình mã hĩa 148 5.3.5 Quy trình giải mã 153 5.4 Phương pháp mã hĩa TwoFish 154 5.4.1 Khởi tạo và phân bố khĩa 154 5.4.2 Quy trình mã hĩa 163 5.4.3 Quy trình giải mã 169 5.5 Kết luận 169 7
Chương 6 Một số hệ thống mã hĩa khĩa cơng cộng 172 6.1 Hệ thống mã hĩa khĩa cơng cộng 172 6.2 Phương pháp RSA 174 6.2.1 Phương pháp RSA 174 6.2.2 Một số phương pháp tấn cơng giải thuật RSA 175 6.2.3 Sự che dấu thơng tin trong hệ thống RSA 182 6.2.4 Vấn đề số nguyên tố 183 6.2.5 Thuật tốn Miller-Rabin 184 6.2.6 Xử lý số học 186 6.3 Mã hĩa quy ước và mã hĩa khĩa cơng cộng 186 Chương 7 Chữ ký điện tử 191 7.1 Giới thiệu 191 7.2 Phương pháp chữ ký điện tử RSA 192 7.3 Phương pháp chữ ký điện tử ElGamal 193 7.3.1 Bài tốn logarit rời rạc 193 7.3.2 Phương pháp ElGamal 194 7.4 Phương pháp Digital Signature Standard 194 Chương 8 Phương pháp ECC 197 8.1 Lý thuyết đường cong elliptic 197 8.1.1 Cơng thức Weierstrasse và đường cong elliptic 198 8.1.2 Đường cong elliptic trên trường R2 199 8.1.3 Đường cong elliptic trên trường hữu hạn 204 8.1.4 Bài tốn logarit rời rạc trên đường cong elliptic 212 8.1.5 Áp dụng lý thuyết đường cong elliptic vào mã hĩa 213 8.2 Mã hĩa dữ liệu 213 8.2.1 Thao tác mã hĩa 214 8.2.2 Kết hợp ECES với thuật tốn Rijndael và các thuật tốn mở rộng 215 8.2.3 Thao tác giải mã 215 8.3 Trao đổi khĩa theo phương pháp Diffie - Hellman sử dụng lý thuyết đường cong elliptic (ECDH) 216 8.3.1 Mơ hình trao đổi khĩa Diffie-Hellman 216 8.3.2 Mơ hình trao đổi khĩa Elliptic Curve Diffie - Hellman 217 8.4 Kết luận 218 8
Chương 9 Hàm băm mật mã 222 9.1 Giới thiệu 222 9.1.1 Đặt vấn đề 222 9.1.2 Hàm băm mật mã 223 9.1.3 Cấu trúc của hàm băm 225 9.1.4 Tính an tồn của hàm băm đối với hiện tượng đụng độ 226 9.1.5 Tính một chiều 226 9.2 Hàm băm MD5 227 9.2.1 Giới thiệu MD5 227 9.2.2 Nhận xét 231 9.3 Phương pháp Secure Hash Standard (SHS) 232 9.3.1 Nhận xét 235 9.4 Hệ thống chuẩn hàm băm mật mã SHA 236 9.4.1 Ý tưởng của các thuật tốn hàm băm SHA 236 9.4.2 Khung thuật tốn chung của các hàm băm SHA 237 9.4.3 Nhận xét 240 9.5 Kiến trúc hàm băm Davies-Mayer và ứng dụng của thuật tốn Rijndael và các phiên bản mở rộng vào hàm băm 241 9.5.1 Kiến trúc hàm băm Davies-Mayer 241 9.5.2 Hàm AES-Hash 242 9.5.3 Hàm băm Davies-Mayer và AES-Hash 244 9.6 Xây dựng các hàm băm sử dụng các thuật tốn mở rộng dựa trên thuật tốn Rijndael 245 Chương 10 Chứng nhận khĩa cơng cộng 246 10.1 Giới thiệu 246 10.2 Các loại giấy chứng nhận khĩa cơng cộng 250 10.2.1 Chứng nhận X.509 250 10.2.2 Chứng nhận chất lượng 252 10.2.3 Chứng nhận PGP 253 10.2.4 Chứng nhận thuộc tính 253 10.3 Sự chứng nhận và kiểm tra chữ ký 254 10.4 Các thành phần của một cở sở hạ tầng khĩa cơng cộng 257 10.4.1 Tổ chức chứng nhận – Certificate Authority (CA) 257 10.4.2 Tổ chức đăng ký chứng nhận – Registration Authority (RA) 258 9
10.4.3 Kho lưu trữ chứng nhận – Certificate Repository (CR) 259 10.5 Chu trình quản lý giấy chứng nhận 259 10.5.1 Khởi tạo 259 10.5.2 Yêu cầu về giấy chứng nhận 259 10.5.3 Tạo lại chứng nhận 262 10.5.4 Hủy bỏ chứng nhận 262 10.5.5 Lưu trữ và khơi phục khĩa 264 10.6 Các mơ hình CA 264 10.6.1 Mơ hình tập trung 264 10.6.2 Mơ hình phân cấp 265 10.6.3 Mơ hình “Web of Trust” 266 10.7 Ứng dụng “Hệ thống bảo vệ thư điện tử” 268 10.7.1 Đặt vấn đề 268 10.7.2 Quy trình mã hĩa thư điện tử 269 10.7.3 Quy trình giải mã thư điện tử 270 10.7.4 Nhận xét – Đánh giá 271 Phụ lục A S-box của thuật tốn MARS 272 Phụ lục B Các hốn vị sử dụng trong thuật tốn Serpent 275 Phụ lục C S-box sử dụng trong thuật tốn Serpent 276 Phụ lục D S-box của thuật tốn Rijndael 277 Phụ lục E Hằng số và giá trị khởi tạo của SHA 279 E.1 Hằng số sử dụng trong SHA 279 E.1.1 Hằng số của SHA-1 279 E.1.2 Hằng số của SHA-224 và SHA-256 279 E.1.3 Hằng số của SHA-384 và SHA-512 280 E.2 Giá trị khởi tạo trong SHA 281 Tài liệu tham khảo 284 10
Danh sách hình Hình 2.1. Mơ hình hệ thống mã hĩa quy ước 21 Hình 2.2. Biểu diễn dãy 64 bit x thành 2 thành phần L và R 34 Hình 2.3. Quy trình phát sinh dãy LiiR từ dãy Lii−−11R và khĩa Ki 35 Hình 3.1. Biểu diễn dạng ma trận của trạng thái (Nb = 6) và mã khĩa (Nk = 4) 49 Hình 3.2. Một chu kỳ mã hĩa của phương pháp Rijndael (với Nb = 4) 52 Hình 3.3. Thao tác SubBytes tác động trên từng byte của trạng thái 54 Hình 3.4. Thao tác ShiftRows tác động trên từng dịng của trạng thái 55 Hình 3.5. Thao tác MixColumns tác động lên mỗi cột của trạng thái 57 Hình 3.6. Thao tác AddRoundKey tác động lên mỗi cột của trạng thái 59 Hình 3.7. Bảng mã khĩa mở rộng và cách xác định mã khĩa của chu kỳ (Nb = 6 và Nk = 4) 61 Hình 3.8. Thao tác InvShiftRows tác động lên từng dịng của trạng thái hiện hành 63 Hình 4.1. Kiến trúc một chu kỳ biến đổi của thuật tốn Rijndael mở rộng 256/384/512-bit với Nb = 4 80 Hình 4.2. Bảng mã khĩa mở rộng và cách xác định mã khĩa của chu kỳ (với Nb = 6 và Nk = 4) 88 Hình 4.3. Sự lan truyền mẫu hoạt động qua từng phép biến đổi trong thuật tốn mở rộng 256/384/512-bit của phương pháp Rijndael với Nb = 6 100 Hình 4.4. Sự lan truyền mẫu hoạt động (thuật tốn mở rộng 256/384/512-bit) 102 Hình 4.5. Minh họa Định lý 4.1 với Q = 2 (thuật tốn mở rộng 256/384/512-bit) 103 11
Hình 4.6. Minh họa Định lý 4.2 với Wc (a1 )=1 (th-tốn mở rộng 256/384/512bit) 105 Hình 4.7. Minh họa Định lý 4.3 (thuật tốn mở rộng 256/384/512-bit) 107 Hình 5.1. Quy trình mã hĩa MARS 116 Hình 5.2. Cấu trúc giai đoạn “Trộn tới” 125 Hình 5.3. Hệ thống Feistel loại 3 127 Hình 5.4. Hàm E 128 Hình 5.5. Cấu trúc giai đoạn “Trộn lùi” 130 Hình 5.6. Cấu trúc mã hĩa RC6 140 Hình 5.7. Chu kỳ thứ i của quy trình mã hĩa RC6 141 Hình 5.8. Mơ hình phát sinh khĩa 146 Hình 5.9. Cấu trúc mã hĩa 149 Hình 5.10. Chu kỳ thứ i (i = 0, , 30) của quy trình mã hĩa Serpent 150 Hình 5.11. Cấu trúc giải mã 153 Hình 5.12. Hàm h 157 Hình 5.13. Mơ hình phát sinh các S–box phụ thuộc khĩa 159 Hình 5.14. Mơ hình phát sinh subkey Kj 160 Hình 5.15. Phép hốn vị q 162 Hình 5.16. Cấu trúc mã hĩa 164 Hình 5.17. Hàm F (khĩa 128 bit) 166 Hình 5.18. So sánh quy trình mã hĩa (a) và giải mã (b) 169 Hình 6.1. Mơ hình hệ thống mã hĩa với khĩa cơng cộng 174 Hình 6.2. Quy trình trao đổi khĩa bí mật sử dụng khĩa cơng cộng 187 Hình 6.3. Đồ thị so sánh chi phí cơng phá khĩa bí mật và khĩa cơng cộng 189 Hình 8.1. Một ví dụ về đường cong elliptic 199 12
Hình 8.2. Điểm ở vơ cực 200 Hình 8.3. Phép cộng trên đường cong elliptic 201 Hình 8.4. Phép nhân đơi trên đường cong elliptic 203 Hình 8.5: So sánh mức độ bảo mật giữa ECC với RSA / DSA 220 Hình 9.1. Khung thuật tốn chung cho các hàm băm SHA 238 Hình 10.1. Vấn đề chủ sở hữu khĩa cơng cộng 247 Hình 10.2. Các thành phần của một chứng nhận khĩa cơng cộng 248 Hình 10.3. Mơ hình Certification Authority đơn giản 249 Hình 10.4. Phiên bản 3 của chuẩn chứng nhận X.509 251 Hình 10.5. Phiên bản 2 của cấu trúc chứng nhận thuộc tính 254 Hình 10.6. Quá trình ký chứng nhận 255 Hình 10.7. Quá trình kiểm tra chứng nhận 256 Hình 10.8. Mơ hình PKI cơ bản 257 Hình 10.9. Mẫu yêu cầu chứng nhận theo chuẩn PKCS#10 260 Hình 10.10. Định dạng thơng điệp yêu cầu chứng nhận theo RFC 2511 261 Hình 10.11. Phiên bản 2 của định dạng danh sách chứng nhận bị hủy 263 Hình 10.12. Mơ hình CA tập trung 264 Hình 10.13. Mơ hình CA phân cấp 266 Hình 10.14. Mơ hình “Web of trust” 267 Hình 10.15. Quy trình mã hĩa thư điện tử 269 Hình 10.16. Quy trình giải mã thư điện tử 270 13
Danh sách bảng Bảng 3.1. Giá trị di số shift(r, Nb) 55 Bảng 3.2. Tốc độ xử lý của phương pháp Rijndael 73 Bảng 4.1. Ảnh hưởng của các phép biến đổi lên mẫu hoạt động 101 Bảng 4.2. Tốc độ xử lý phiên bản 256/384/512-bit trên máy Pentium IV 2.4GHz 111 Bảng 4.3. Tốc độ xử lý phiên bản 512/768/1024-bit trên máy Pentium IV 2.4 GHz 112 Bảng 4.4. Bảng so sánh tốc độ xử lý của phiên bản 256/384/512-bit 112 Bảng 4.5. Bảng so sánh tốc độ xử lý của phiên bản 512/768/1024-bit 112 Bảng 6.1. So sánh độ an tồn giữa khĩa bí mật và khĩa cơng cộng 188 Bảng 8.1. So sánh số lượng các thao tác đối với các phép tốn trên đường cong elliptic trong hệ tọa độ Affine và hệ tọa độ chiếu 211 Bảng 8.2. So sánh kích thước khĩa giữa mã hĩa quy ước và mã hĩa khĩa cơng cộng với cùng mức độ bảo mật 218 Bảng 8.3. So sánh kích thước khĩa RSA và ECC với cùng mức độ an tồn 219 Bảng 9.1. Chu kỳ biến đổi trong MD5 230 Bảng 9.2. Các tính chất của các thuật tốn băm an tồn 241 Bảng D.1. Bảng thay thế S-box cho giá trị {xy} ở dạng thập lục phân. 277 Bảng D.2. Bảng thay thế nghịch đảo cho giá trị {xy} ở dạng thập lục phân. 278 14
Tổng quan Chương 1 Tổng quan " Nội dung của chương 1 giới thiệu tổng quan các khái niệm cơ bản về mật mã học và hệ thống mã hĩa, đồng thời giới thiệu sơ lược về hệ thống mã hĩa quy ước và hệ thống mã hĩa khĩa cơng cộng. 1.1 Mật mã học Mật mã học là ngành khoa học ứng dụng tốn học vào việc biến đổi thơng tin thành một dạng khác với mục đích che dấu nội dung, ý nghĩa thơng tin cần mã hĩa. Đây là một ngành quan trọng và cĩ nhiều ứng dụng trong đời sống xã hội. Ngày nay, các ứng dụng mã hĩa và bảo mật thơng tin đang được sử dụng ngày càng phổ biến hơn trong các lĩnh vực khác nhau trên thế giới, từ các lĩnh vực an ninh, quân sự, quốc phịng , cho đến các lĩnh vực dân sự như thương mại điện tử, ngân hàng Cùng với sự phát triển của khoa học máy tính và Internet, các nghiên cứu và ứng dụng của khoa học mật mã ngày càng trở nên đa dạng hơn, mở ra nhiều hướng nghiên cứu chuyên sâu vào từng lĩnh vực ứng dụng đặc thù với những đặc trưng 15
Chương 1 riêng. Ứng dụng của khoa học mật mã khơng chỉ đơn thuần là mã hĩa và giải mã thơng tin mà cịn bao gồm nhiều vấn đề khác nhau cần được nghiên cứu và giải quyết: chứng thực nguồn gốc nội dung thơng tin (kỹ thuật chữ ký điện tử), chứng nhận tính xác thực về người sở hữu mã khĩa (chứng nhận khĩa cơng cộng), các quy trình giúp trao đổi thơng tin và thực hiện giao dịch điện tử an tồn trên mạng Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu cầu đa dạng của các hệ thống ứng dụng khác nhau trong thực tế, ví dụ như hệ thống bỏ phiếu bầu cử qua mạng, hệ thống đào tạo từ xa, hệ thống quản lý an ninh của các đơn vị với hướng tiếp cận sinh trắc học, hệ thống cung cấp dịch vụ multimedia trên mạng với yêu cầu cung cấp dịch vụ và bảo vệ bản quyền sở hữu trí tuệ đối với thơng tin số 1.2 Hệ thống mã hĩa (cryptosystem) Định nghĩa 1.1: Hệ thống mã hĩa (cryptosystem) là một bộ năm (P, C, K, E, D) thỏa mãn các điều kiện sau: 1. Tập nguồn P là tập hữu hạn tất cả các mẩu tin nguồn cần mã hĩa cĩ thể cĩ 2. Tập đích C là tập hữu hạn tất cả các mẩu tin cĩ thể cĩ sau khi mã hĩa 3. Tập khĩa K là tập hữu hạn các khĩa cĩ thể được sử dụng 4. E và D lần lượt là tập luật mã hĩa và giải mã. Với mỗi khĩa k∈ K , tồn tại luật mã hĩa eEk ∈ và luật giải mã dDk ∈ tương ứng. Luật mã hĩa ePk : → C và luật giải mã eCk : → P là hai ánh xạ thỏa mãn dexkk(()),=∀∈ x x P 16
Tổng quan Tính chất 4 là tính chất chính và quan trọng của một hệ thống mã hĩa. Tính chất này bảo đảm một mẩu tin xP∈ được mã hĩa bằng luật mã hĩa eEk ∈ cĩ thể được giải mã chính xác bằng luật dDk ∈ . Định nghĩa 1.2: Zm được định nghĩa là tập hợp {0,1, ,m − 1} , được trang bị phép cộng (ký hiệu +) và phép nhân (ký hiệu là ×). Phép cộng và phép nhân trong Zm được thực hiện tương tự như trong Z , ngoại trừ kết quả tính theo modulo m. Ví dụ: Giả sử ta cần tính giá trị 11× 13 trong Z16 . Trong Z , ta cĩ kết quả của phép nhân 11×= 13 143. Do 143≡ 15 (mod 16) nên 11×= 13 15 trong Z16 . Một số tính chất của Zm 1. Phép cộng đĩng trong Zm , ∀∈ab, Zm , ab+∈Zm 2. Tính giao hốn của phép cộng trong Zm , ∀∈ab, Zm , abba+=+ 3. Tính kết hợp của phép cộng trong Zm , ∀∈abc,, Zm , ()ab++=++ c a () bc 4. Zm cĩ phần tử trung hịa là 0, ∀∈ab, Zm , aaa+=+=00 5. Mọi phần tử a trong Zm đều cĩ phần tử đối là ma− 6. Phép nhân đĩng trong Zm , ∀∈ab, Zm , ab×∈Zm 7. Tính giao hốn của phép nhân trong Zm , ∀∈ab, Zm , ab×=× ba 8. Tính kết hợp của phép nhân trong Zm , ∀∈abc,, Zm , ()ab××=×× c a () bc 17
Chương 1 9. Zm cĩ phần tử đơn vị là 1, ∀∈ab, Zm , aaa×=×11 = 10. Tính phân phối của phép nhân đối với phép cộng, ∀∈abc,, Zm , ()ab+×=×+× c acbc Zm cĩ các tính chất 1, 3 – 5 nên tạo thành một nhĩm. Do Zm cĩ tính chất 2 nên tạo thành nhĩm Abel. Zm cĩ các tính chất (1) – (10) nên tạo thành một vành. 1.3 Hệ thống mã hĩa quy ước (mã hĩa đối xứng) Trong hệ thống mã hĩa quy ước, quá trình mã hĩa và giải mã một thơng điệp sử dụng cùng một mã khĩa gọi là khĩa bí mật (secret key) hay khĩa đối xứng (symmetric key). Do đĩ, vấn đề bảo mật thơng tin đã mã hĩa hồn tồn phụ thuộc vào việc giữ bí mật nội dung của mã khĩa đã được sử dụng. Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý hiện nay, phương pháp mã hĩa chuẩn (Data Encryption Standard – DES) đã trở nên khơng an tồn trong bảo mật thơng tin. Do đĩ, Viện Tiêu chuẩn và Cơng nghệ Quốc gia Hoa Kỳ (National Institute of Standards and Technology – NIST) đã quyết định chọn một chuẩn mã hĩa mới với độ an tồn cao nhằm phục vụ nhu cầu bảo mật thơng tin liên lạc của chính phủ Hoa Kỳ cũng như trong các ứng dụng dân sự. Thuật tốn Rijndael do Vincent Rijmen và Joan Daeman đã được chính thức chọn trở thành chuẩn mã hĩa nâng cao (Advanced Encryption Standard – AES) từ 02 tháng 10 năm 2000. 18
Tổng quan 1.4 Hệ thống mã hĩa khĩa cơng cộng (mã hĩa bất đối xứng) Nếu như vấn đề khĩ khăn đặt ra đối với các phương pháp mã hĩa quy ước chính là bài tốn trao đổi mã khĩa thì ngược lại, các phương pháp mã hĩa khĩa cơng cộng giúp cho việc trao đổi mã khĩa trở nên dễ dàng hơn. Nội dung của khĩa cơng cộng (public key) khơng cần phải giữ bí mật như đối với khĩa bí mật trong các phương pháp mã hĩa quy ước. Sử dụng khĩa cơng cộng, chúng ta cĩ thể thiết lập một quy trình an tồn để truy đổi khĩa bí mật được sử dụng trong hệ thống mã hĩa quy ước. Trong những năm gần đây, các phương pháp mã hĩa khĩa cơng cộng, đặc biệt là phương pháp RSA [45], được sử dụng ngày càng nhiều trong các ứng dụng mã hĩa trên thế giới và cĩ thể xem như đây là phương pháp chuẩn được sử dụng phổ biến nhất trên Internet, ứng dụng trong việc bảo mật thơng tin liên lạc cũng như trong lĩnh vực thương mại điện tử. 1.5 Kết hợp mã hĩa quy ước và mã hĩa khĩa cơng cộng Các phương pháp mã hĩa quy ước cĩ ưu điểm xử lý rất nhanh và khả năng bảo mật cao so với các phương pháp mã hĩa khĩa cơng cộng nhưng lại gặp phải vấn đề khĩ khăn trong việc trao đổi mã khĩa. Ngược lại, các phương pháp mã hĩa khĩa cơng cộng tuy xử lý thơng tin chậm hơn nhưng lại cho phép người sử dụng trao đổi mã khĩa dễ dàng hơn. Do đĩ, trong các ứng dụng thực tế, chúng ta cần phối hợp được ưu điểm của mỗi phương pháp mã hĩa để xây dựng hệ thống mã hĩa và bảo mật thơng tin hiệu quả và an tồn. 19
Chương 2 Chương 2 Một số phương pháp mã hĩa quy ước " Trong chương 1, chúng ta đã tìm hiểu tổng quan về mật mã học và hệ thống mã hĩa. Nội dung của chương 2 sẽ giới thiệu chi tiết hơn về hệ thống mã hĩa quy ước (hay cịn gọi là hệ thống mã hĩa đối xứng). Một số phương pháp mã hĩa quy ước kinh điển như phương pháp dịch chuyển, phương pháp thay thế cùng với các phương pháp mã hĩa theo khối được sử dụng phổ biến trong những thập niên gần đây như DES, Tripple DES, AES cũng được giới thiệu trong chương này. 2.1 Hệ thống mã hĩa quy ước Hệ thống mã hĩa quy ước là hệ thống mã hĩa trong đĩ quy trình mã hĩa và giải mã đều sử dụng chung một khố - khĩa bí mật. Việc bảo mật thơng tin phụ thuộc vào việc bảo mật khĩa. Trong hệ thống mã hĩa quy ước, thơng điệp nguồn được mã hĩa với mã khĩa k được thống nhất trước giữa người gửi A và người nhận B. Người A sẽ sử dụng 20
Một số phương pháp mã hĩa quy ước mã khĩa k để mã hĩa thơng điệp x thành thơng điệp y và gửi y cho người B; người B sẽ sử dụng mã khĩa k để giải mã thơng điệp y này. Vấn đề an tồn bảo mật thơng tin được mã hĩa phụ thuộc vào việc giữ bí mật nội dung mã khĩa k. Nếu người C biết được mã khĩa k thì C cĩ thể “mở khĩa” thơng điệp đã được mã hĩa mà người A gửi cho người B. Khĩa bí mật Thơng điệp Mã hĩa Thơng điệp Giải mã Thơng điệp nguồn đã mã hĩa đã giải mã Hình 2.1. Mơ hình hệ thống mã hĩa quy ước 2.2 Phương pháp mã hĩa dịch chuyển Phương pháp mã hĩa dịch chuyển là một trong những phương pháp lâu đời nhất được sử dụng để mã hĩa. Thơng điệp được mã hĩa bằng cách dịch chuyển xoay vịng từng ký tự đi k vị trí trong bảng chữ cái. Trong trường hợp đặc biệt k = 3 , phương pháp mã hĩa bằng dịch chuyển được gọi là phương pháp mã hĩa Caesar. 21
Chương 2 Thuật tốn 2.1. Phương pháp mã hĩa dịch chuyển Cho PCK===Zn Với mỗi khĩa kK∈ , định nghĩa: exk ()=+ ( xk )mod n và dyk ()=− ( yk )mod n với xy, ∈Zn E =∈{ekk , K} và D =∈{dkk , K} Mã hĩa dịch chuyển là một phương pháp mã hĩa đơn giản, thao tác xử lý mã hĩa và giải mã được thực hiện nhanh chĩng. Tuy nhiên, trên thực tế, phương pháp này cĩ thể dễ dàng bị phá vỡ bằng cách thử mọi khả năng khĩa kK∈ . Điều này hồn tồn cĩ thể thực hiện được do khơng gian khĩa K chỉ cĩ n phần tử để chọn lựa. Ví dụ: Để mã hĩa một thơng điệp được biểu diễn bằng các chữ cái từ A đến Z (26 chữ cái), ta sử dụng PCK===Z26 . Khi đĩ, thơng điệp được mã hĩa sẽ khơng an tồn và cĩ thể dễ dàng bị giải mã bằng cách thử lần lượt 26 giá trị khĩa kK∈ . Tính trung bình, thơng điệp đã được mã hĩa cĩ thể bị giải mã sau khoảng n /2 lần thử khĩa kK∈ . 2.3 Phương pháp mã hĩa thay thế Phương pháp mã hĩa thay thế (Substitution Cipher) là một trong những phương pháp mã hĩa nổi tiếng và đã được sử dụng từ hàng trăm năm nay. Phương pháp này thực hiện việc mã hĩa thơng điệp bằng cách hốn vị các phần tử trong bảng chữ cái hay tổng quát hơn là hốn vị các phần tử trong tập nguồn P. 22
Một số phương pháp mã hĩa quy ước Thuật tốn 2.2. Phương pháp mã hĩa bằng thay thế Cho P = C = Zn K là tập hợp tất cả các hốn vị của n phần tử 0,1, ,n − 1 . Như vậy, mỗi khĩa π ∈ K là một hốn vị của n phần tử 0,1, ,n − 1 . Với mỗi khĩa π ∈ K , định nghĩa: ex()= π() x và dy()= π-1 () y với xy, ∈ Z π π n E =∈{eKπ , π } và D =∈{DKπ , π } Đây là một phương pháp đơn giản, thao tác mã hĩa và giải mã được thực hiện nhanh chĩng. Phương pháp này khắc phục điểm hạn chế của phương pháp mã hĩa bằng dịch chuyển là cĩ khơng gian khĩa K nhỏ nên dễ dàng bị giải mã bằng cách thử nghiệm lần lượt n giá trị khĩa kK∈ . Trong phương pháp mã hĩa thay thế cĩ khơng gian khĩa K rất lớn với n! phần tử nên khơng thể bị giải mã bằng cách “vét cạn” mọi trường hợp khĩa k. Tuy nhiên, trên thực tế thơng điệp được mã hĩa bằng phương pháp này vẫn cĩ thể bị giải mã nếu như cĩ thể thiết lập được bảng tần số xuất hiện của các ký tự trong thơng điệp hay nắm được một số từ, ngữ trong thơng điệp nguồn ban đầu! 2.4 Phương pháp Affine Nếu như phương pháp mã hĩa bằng dịch chuyển là một trường hợp đặc biệt của phương pháp mã hĩa bằng thay thế, trong đĩ chỉ sử dụng n giá trị khĩa k trong số n! phần tử, thì phương pháp Affine lại là một trường hợp đặc biệt khác của mã hĩa bằng thay thế. 23
Chương 2 Thuật tốn 2.3. Phương pháp Affine Cho P = C = Zn Kab=∈×{( ,:gcd,1) ZZnn ( an) =} Với mỗi khĩa kabK=∈(,) , định nghĩa: −1 exk ( ) =+()mod axb n và dxk ()=− ( a ( yb ))mod n với xy, ∈ Zn E =∈{ekk , K} và D =∈{Dkk , K} Để cĩ thể giải mã chính xác thơng tin đã được mã hĩa bằng hàm eEk ∈ thì ek phải là một song ánh. Như vậy, với mỗi giá trị y ∈ Zn , phương trình ax+≡ b y(mod n ) phải cĩ nghiệm duy nhất x ∈ Zn . Phương trình ax+≡ b y (mod n ) tương đương với ax≡−( y b )(mod n ) . Vậy, ta chỉ cần khảo sát phương trình ax≡− ( y b )(mod n ) . Định lý 2.1: Phương trình ax+≡ b y(mod n ) cĩ nghiệm duy nhất x ∈ Zn với mỗi giá trị b ∈ Zn khi và chỉ khi a và n nguyên tố cùng nhau. Vậy, điều kiện a và n nguyên tố cùng nhau bảo đảm thơng tin được mã hĩa bằng hàm ek cĩ thể được giải mã và giải mã một cách chính xác. Gọi φ(n ) là số lượng phần tử thuộc Zn và nguyên tố cùng nhau với n. 24
Một số phương pháp mã hĩa quy ước m Định lý 2.2: Nếu n = p ei với p là các số nguyên tố khác nhau và e ∈ Z+ , ∏ i i i i=1 m ei ei −1 1 ≤≤im thì φ()n = ∏(pi − pi ). i=1 Trong phương pháp mã hĩa Affine, ta cĩ n khả năng chọn giá trị b, φ(n ) khả năng chọn giá trị a. Vậy, khơng gian khĩa K cĩ tất cả nnφ () phần tử. Vấn đề đặt ra cho phương pháp mã hĩa Affine là để cĩ thể giải mã được thơng tin −1 đã được mã hĩa cần phải tính giá trị phần tử nghịch đảo a ∈ Zn . Thuật tốn Euclide mở rộng cĩ thể giải quyết trọn vẹn vấn đề này [45]. Trước tiên, cần khảo sát thuật tốn Euclide (ở dạng cơ bản) sử dụng trong việc tìm ước số chung lớn nhất của hai số nguyên dương r0 và r1 với rr01> . Thuật tốn Euclide bao gồm một dãy các phép chia: rqrr0112=+, 0 <<rr21 rqrr1223=+, 0 <<rr32 rqrrmmmm−−−211=+, 0 <<rrmm−1 rqrmmm−1 = (2.1) Dễ dàng nhận thấy rằng: gcd(rr01 , )=== gcd( rr 12 , ) gcd( rmm− 1 , r ) r m. Như vậy, ước số chung lớn nhất của r0 và r1 là rm . 25
Chương 2 Xây dựng dãy số tt01, , , tm theo cơng thức truy hồi sau: t0 = 0 t1 = 1 ttjj=−()mod−−−2110 qt jj r với j ≥ 2 (2.2) Định lý 2.3: Với mọi j, 0 ≤≤j m , ta cĩ rtrjj≡ 10(mod r ) , với q j và rj được xác định theo thuật tốn Euclide và t j được xác định theo cơng thức truy hồi nêu trên. Định lý 2.4: Nếu r0 và r1 nguyên tố cùng nhau (với rr01> ) thì tm là phần tử nghịch đảo của r trong Z . 1 r0 −1 gcd(rr01 , )=⇒ 1 tm = r 1 mod r 0 (2.3) Trong thuật tốn Euclide, dãy số{}t j cĩ thể được tính đồng thời với dãy số {}q j và{rj } . Thuật tốn Euclide mở rộng dưới đây được sử dụng để xác định phần tử nghịch đảo (nếu cĩ) của một số nguyên dương a (modulo n). Trong thuật tốn khơng cần sử dụng đến cấu trúc dữ liệu mảng để lưu giá trị của dãy số {}t j ,{q j } hay {rj } vì tại mỗi thời điểm, ta chỉ cần quan tâm đến giá trị của hai phần tử cuối cùng của mỗi dãy tại thời điểm đang xét. 26
Một số phương pháp mã hĩa quy ước Thuật tốn 2.4. Thuật tốn Euclide mở rộng xác định phần tử nghịch đảo của a (modulo n) nn0 = aa0 = t0 = 0 t = 1 ⎡⎤n0 q = ⎢⎥ ⎣⎦a0 rn=−00 qa while r > 0 do temp=− t0 qt if temp ≥ 0 then temp= temp mod n end if if temp < 0 then temp=−− n (( temp ) mod n ) end if tt0 = ttemp= na00= ar0 = ⎡⎤n0 q = ⎢⎥ ⎣⎦a0 rn=−00 qa end while if a0 ≠ 1 then a khơng cĩ phần tử nghịch đảo modulo n else at−1 = mod n end if 27
Chương 2 2.5 Phương pháp Vigenere Trong phương pháp mã hĩa bằng thay thế cũng như các trường hợp đặc biệt của phương pháp này (mã hĩa bằng dịch chuyển, mã hĩa Affine, ), ứng với một khĩa k được chọn, mỗi phần tử xP∈ được ánh xạ vào duy nhất một phần tử yC∈ . Nĩi cách khác, ứng với mỗi khĩa kK∈ , một song ánh được thiết lập từ P vào C. Khác với hướng tiếp cận này, phương pháp Vigenere sử dụng một từ khĩa cĩ độ dài m. Cĩ thể xem như phương pháp mã hĩa Vigenere Cipher bao gồm m phép mã hĩa bằng dịch chuyển được áp dụng luân phiên nhau theo chu kỳ. Khơng gian khĩa K của phương pháp Vigenere Cipher cĩ số phần tử là nm , lớn hơn hẳn phương pháp số lượng phần tử của khơng gian khĩa K trong phương pháp mã hĩa bằng dịch chuyển. Do đĩ, việc tìm ra mã khĩa k để giải mã thơng điệp đã được mã hĩa sẽ khĩ khăn hơn đối với phương pháp mã hĩa bằng dịch chuyển. Thuật tốn 2.5. Phương pháp mã hĩa Vigenere m Chọn số nguyên dương m. Định nghĩa PCK===(Zn ) r Kkkk=∈{(01 , , ,rn− 1 ) (Z ) } Với mỗi khĩa kkkk=∈(01 , , ,r − 1 ) K, định nghĩa: exxkm(12 , , , x )=+ (( x 1 k 1 )mod nx ,( 2 + k 2 )mod n , ,( x mm + k )mod n ) dyykm(12 , , , y )=− (( y 1 k 1 )mod ny ,( 2 − k 2 )mod n , ,( y mm − k )mod n ) m với xy,∈ (Zn ) . 28
Một số phương pháp mã hĩa quy ước 2.6 Phương pháp Hill Phương pháp Hill được Lester S. Hill cơng bố năm 1929: Cho số nguyên dương m m, định nghĩa PC==(Zn ) . Mỗi phần tử xP∈ là một bộ m thành phần, mỗi thành phần thuộc Zn . Ý tưởng chính của phương pháp này là sử dụng m tổ hợp tuyến tính của m thành phần trong mỗi phần tử xP∈ để phát sinh ra m thành phần tạo thành phần tử yC∈ . Thuật tốn 2.6. Phương pháp mã hĩa Hill Chọn số nguyên dương m. Định nghĩa: m PC==()Zn và K là tập hợp các ma trận mm× khả nghịch ⎛ k k " k ⎞ ⎜ 1,1 1,2 1,m ⎟ ⎜ k " " k ⎟ Với mỗi khĩa k = 2,1 2,m ∈ K , định nghĩa: ⎜ # # # ⎟ ⎜ ⎟ ⎜ ⎟ ⎝km,1 km,2 " km,m ⎠ ⎛ k k " k ⎞ ⎜ 1,1 1,2 1,m ⎟ ⎜ k " " k ⎟ e ()x = xk = (x , x , , x ) 2,1 2,m với xxxx=∈( , , , ) P k 1 2 m ⎜ # # # ⎟ 12 m ⎜ ⎟ ⎜ ⎟ ⎝km,1 km,2 " km,m ⎠ −1 và dyk ()= yk với yC∈ . Mọi phép tốn số học đều được thực hiện trên Zn . 29
Chương 2 2.7 Phương pháp mã hĩa hốn vị Những phương pháp mã hĩa nêu trên đều dựa trên ý tưởng chung: thay thế mỗi ký tự trong thơng điệp nguồn bằng một ký tự khác để tạo thành thơng điệp đã được mã hĩa. Ý tưởng chính của phương pháp mã hĩa hốn vị (Permutation Cipher) là vẫn giữ nguyên các ký tự trong thơng điệp nguồn mà chỉ thay đổi vị trí các ký tự; nĩi cách khác thơng điệp nguồn được mã hĩa bằng cách sắp xếp lại các ký tự trong đĩ. Thuật tốn 2.7. Phương pháp mã hĩa bằng hốn vị Chọn số nguyên dương m. Định nghĩa: m PC==()Zn và K là tập hợp các hốn vị của m phần tử {1,2, ,m} Với mỗi khĩa π ∈ K , định nghĩa: exx, , , x= x , x , , x và π ()12 m ( π()1 π (2 )π (m )) dyy, , , y= y , y , , y π ()12 m ( π−−11()1 π (2 )π − 1 (m )) với π–1 hốn vị ngược của π Phương pháp mã hĩa bằng hốn vị chính là một trường hợp đặc biệt của phương pháp Hill. Với mỗi hốn vị π của tập hợp {1, 2, , m} , ta xác định ma trận kkπ = ()ij, theo cơng thức sau: ⎧1, ij= π ⎪ nếu ( ) (2.4) kij, = ⎨ ⎩⎪0, trong trường hợp ngược lại 30
Một số phương pháp mã hĩa quy ước Ma trận kπ là ma trận mà mỗi dịng và mỗi cột cĩ đúng một phần tử mang giá trị 1, các phần tử cịn lại trong ma trận đều bằng 0. Ma trận này cĩ thể thu được bằng cách hốn vị các hàng hay các cột của ma trận đơn vị Im nên kπ là ma trận khả nghịch. Rõ ràng, mã hĩa bằng phương pháp Hill với ma trận kπ hồn tồn tương đương với mã hĩa bằng phương pháp hốn vị với hốn vị π. 2.8 Phương pháp mã hĩa bằng phép nhân 2.8.1 Phương pháp mã hĩa bằng phép nhân Thuật tốn 2.8. Phương pháp mã hĩa bằng phép nhân m Cho PC==(Zn ) , Kk=∈{Zn : gcd( kn , ) = 1} Với mỗi khĩa k ∈ Zn , định nghĩa: −1 exkx()= k mod n và dyk ()= ky mod n với xy, ∈ Zn Phương pháp mã hĩa bằng phép nhân (Multiplicative Cipher) là một phương pháp mã hĩa đơn giản. Khơng gian khĩa K cĩ tất cả φ()n phần tử. Tuy nhiên, việc chọn khĩa kK=∈ 1 sẽ khơng cĩ ý nghĩa trong việc mã hĩa thơng nên số lượng phần tử thật sự được sử dụng trong K là φ (n )− 1. Vấn đề được đặt ra ở đây là độ an tồn của phương pháp này phụ thuộc vào số lượng phần tử trong tập khĩa K. Nếu giá trị φ()n − 1 khơng đủ lớn thì thơng tin được mã hĩa cĩ thể bị giải mã bằng cách thử tồn bộ các khĩa kK∈ . Để nâng 31
Chương 2 cao độ an tồn của phương pháp này, giá trị n được sử dụng phải cĩ φ (n ) đủ lớn hay chính giá trị n phải đủ lớn. Khi đĩ, một vấn đề mới được đặt ra là làm thế nào thực hiện được một cách nhanh chĩng các phép tốn trên số nguyên lớn. 2.8.2 Xử lý số học Trong phương pháp mã hĩa này, nhu cầu tính giá trị của biểu thức z =×()modab n được đặt ra trong cả thao tác mã hĩa và giải mã. Nếu thực hiện việc tính giá trị theo cách thơng thường thì rõ ràng là khơng hiệu quả do thời gian xử lý quá lớn. Sử dụng thuật tốn phép nhân Ấn Độ, ta cĩ thể được sử dụng để tính giá trị biểu thức z =×(ab ) mod n một cách nhanh chĩng và hiệu quả. Thuật tốn 2.9. Thuật tốn phép nhân Ấn Độ để tính giá trị z =×()modab n z = 0 aa= mod n bb= mod n Biểu diễn b dưới dạng nhị phân bbll−−12, , , bb 21 , , bi ∈{0,1} , 0 ≤<il for i = 0 to l −1 if bi = 1 then z =+ ()modza n end if aa= (2 )mod n end for z =+()modza n 32
Một số phương pháp mã hĩa quy ước 2.9 Phương pháp DES (Data Encryption Standard) 2.9.1 Phương pháp DES Khoảng những năm 1970, tiến sĩ Horst Feistel đã đặt nền mĩng đầu tiên cho chuẩn mã hĩa dữ liệu DES với phương pháp mã hĩa Feistel Cipher. Vào năm 1976 Cơ quan Bảo mật Quốc gia Hoa Kỳ (NSA) đã cơng nhận DES dựa trên phương pháp Feistel là chuẩn mã hĩa dữ liệu [25]. Kích thước khĩa của DES ban đầu là 128 bit nhưng tại bản cơng bố FIPS kích thước khĩa được rút xuống cịn 56 bit. Trong phương pháp DES, kích thước khối là 64 bit. DES thực hiện mã hĩa dữ liệu qua 16 vịng lặp mã hĩa, mỗi vịng sử dụng một khĩa chu kỳ 48 bit được tạo ra từ khĩa ban đầu cĩ độ dài 56 bit. DES sử dụng 8 bảng hằng số S-box để thao tác. Quá trình mã hĩa của DES cĩ thể được tĩm tắt như sau: Biểu diễn thơng điệp nguồn xP∈ bằng dãy 64bit. Khĩa k cĩ 56 bit. Thực hiện mã hĩa theo ba giai đoạn: 1. Tạo dãy 64 bit x0 bằng cách hốn vị x theo hốn vị IP (Initial Permutation). Biểu diễn xIPxLR000==() , L0 gồm 32 bit bên trái của x0, R0 gồm 32 bit bên phải của x0. 33
Chương 2 L0 R0 x 0 Hình 2.2. Biểu diễn dãy 64 bit x thành 2 thành phần L và R 2. Thực hiện 16 vịng lặp từ 64 bit thu được và 56 bit của khố k (chỉ sử dụng 48 bit của khố k trong mỗi vịng lặp). 64 bit kết quả thu được qua mỗi vịng lặp sẽ là đầu vào cho vịng lặp sau. Các cặp từ 32 bit Li, Ri (với 1≤≤i 16 ) được xác định theo quy tắc sau: Lii= R −1 Rii=⊕LfRK−−11(,) i i (2.5) với ⊕ biểu diễn phép tốn XOR trên hai dãy bit, K1, K2, , K16 là các dãy 48 bit phát sinh từ khĩa K cho trước (Trên thực tế, mỗi khĩa Ki được phát sinh bằng cách hốn vị các bit trong khĩa K cho trước). −1 3. Áp dụng hốn vị ngược IP đối với dãy bit R16L 16 , thu được từ y gồm −1 64 bit. Như vậy, yIPRL= ()16 16 . Hàm f được sử dụng ở bước 2 là hàm cĩ gồm hai tham số: Tham số thứ nhất A là một dãy 32 bit, tham số thứ hai J là một dãy 48 bit. Kết quả của hàm f là một dãy 32 bit. Các bước xử lý của hàm f (AJ , ) như sau: Tham số thứ nhất A (32 bit) được mở rộng thành dãy 48 bit bằng hàm mở rộng E. Kết quả của hàm E (A ) là một dãy 48 bit được phát sinh từ A bằng cách hốn vị 34
Một số phương pháp mã hĩa quy ước theo một thứ tự nhất định 32 bit của A, trong đĩ cĩ 16 bit của A được lặp lại hai lần trong E (A ) . Li-1 Ri-1 f Ki ⊕ Li Ri Hình 2.3. Quy trình phát sinh dãy LiiR từ dãy Lii−−11R và khĩa Ki Thực hiện phép tốn XOR cho hai dãy 48 bit E (A ) và J, ta thu được một dãy 48 bit B. Biểu diễn B thành từng nhĩm 6 bit như sau: B = BBBBBBBB12345678. Sử dụng tám ma trận SS12, , , S 8, mỗi ma trận Si cĩ kích thước 4× 16 và mỗi dịng của ma trận nhận đủ 16 giá trị từ 0 đến 15. Xét dãy gồm 6 bit B j = bbbbbb123456, SBj (j ) được xác định bằng giá trị của phần tử tại dịng r cột c của Sj, trong đĩ, chỉ số dịng r cĩ biểu diễn nhị phân là bb16, chỉ số cột c cĩ biểu diễn nhị phân là bbbb2345. Bằng cách này, ta xác định được các dãy 4 bit CSBj = jj(), 18≤≤j . 35
Chương 2 Tập hợp các dãy 4 bit Cj lại, ta cĩ được dãy 32 bit CCCCCCCCC= 12345678. Dãy 32 bit thu được bằng cách hốn vị C theo một quy luật P nhất định chính là kết quả của hàm F (AJ , ) . Quá trình giải mã chính là thực hiện theo thứ tự đảo ngược các thao tác của quá trình mã hĩa. 2.9.2 Nhận xét Do tốc độ tính tốn của máy tính ngày càng tăng cao và DES đã được sự quan tâm chú ý của các nhà khoa học lẫn những người phá mã (cryptanalyst) nên DES nhanh chĩng trở nên khơng an tồn. Năm 1997, một dự án đã tiến hành bẻ khĩa DES chưa đến 3 ngày với chi phí thấp hơn 250.000 dollars. Và vào năm 1999, một mạng máy tính gồm 100.000 máy cĩ thể giải mã một thư tín mã hĩa DES chưa đầy 24 giờ. Trong quá trình tìm kiếm các thuật tốn mới an tồn hơn DES, Tripple DES ra đời như một biến thể của DES. Tripple DES thực hiện ba lần thuật tốn DES với 3 khố khác nhau và với trình tự khác nhau. Trình tự thực hiện phổ biến là EDE (Encrypt – Decrypt – Encrypt), thực hiện xen kẽ mã hĩa với giải mã (lưu ý là khĩa trong từng giai đoạn thực hiện khác nhau). 36
Một số phương pháp mã hĩa quy ước 2.10 Phương pháp chuẩn mã hĩa nâng cao AES Để tìm kiếm một phương pháp mã hĩa quy ước mới với độ an tồn cao hơn DES, NIST đã cơng bố một chuẩn mã hĩa mới, thay thế cho chuẩn DES. Thuật tốn đại diện cho chuẩn mã hĩa nâng cao AES (Advanced Encryption Standard) sẽ là thuật tốn mã hĩa khĩa quy ước, sử dụng miễn phí trên tồn thế giới. Chuẩn AES bao gồm các yêu cầu sau [23]: o Thuật tốn mã hĩa theo khối 128 bit. o Chiều dài khĩa 128 bit, 192 bit và 256 bit. o Khơng cĩ khĩa yếu. o Hiệu quả trên hệ thống Intel Pentium Pro và trên các nền phần cứng và phần mềm khác. o Thiết kế dễ dàng (hỗ trợ chiều dài khĩa linh hoạt, cĩ thể triển khai ứng dụng rộng rãi trên các nền và các ứng dụng khác nhau). o Thiết kế đơn giản: phân tích đánh giá và cài đặt dễ dàng. o Chấp nhận bất kỳ chiều dài khĩa lên đến 256 bit. o Mã hĩa dữ liệu thấp hơn 500 chu kỳ đồng hồ cho mỗi khối trên Intel Pentium, Pentium Pro và Pentium II đối với phiên bản tối ưu của thuật tốn. o Cĩ khả năng thiết lập khĩa 128 bit (cho tốc độ mã hĩa tối ưu) nhỏ hơn thời gian địi hỏi để mã hĩa các khối 32 bit trên Pentium, Pentium Pro và Pentium II. o Khơng chứa bất kỳ phép tốn nào làm nĩ giảm khả năng trên các bộ vi xử lý 8 bit, 16 bit, 32 bit và 64 bit. o Khơng bao hàm bất kỳ phần tử nào làm nĩ giảm khả năng của phần cứng. o Thời gian mã hĩa dữ liệu rất thấp dưới 10/1000 giây trên bộ vi xử lý 8 bit. o Cĩ thể thực hiện trên bộ vi xử lý 8 bit với 64 byte bộ nhớ RAM. 37
Chương 2 Sau khi thực hiện hai lần tuyển chọn, cĩ năm thuật tốn được vào vịng chung kết, gồm cĩ: MARS, RC6, SERPENT, TWOFISH và RIJNDAEL. Các thuật tốn này đều đạt các yêu cầu của AES nên được gọi chung là các thuật tốn ứng viên AES. Các thuật tốn ứng viên AES cĩ độ an tồn cao, chi phí thực hiện thấp. Chi tiết về các thuật tốn này được trình bày trong Chương 3 - Phương pháp mã hĩa Rijndael và Chương 5 - Các thuật tốn ứng cử viên AES. 38
Phương pháp mã hĩa Rijndael Chương 3 Phương pháp mã hĩa Rijndael " Nội dung của chương 3 trình bày chi tiết về phương pháp mã hĩa Rijndael của hai tác giả Vincent Rijmen và Joan Daeman. Đây là giải thuật được Viện Tiêu chuẩn và Cơng nghệ Hoa Kỳ (NIST) chính thức chọn làm chuẩn mã hĩa nâng cao (AES) từ ngày 02 tháng 10 năm 2000. 3.1 Giới thiệu Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý hiện nay, phương pháp mã hĩa chuẩn (Data Encryption Standard – DES) trở nên khơng an tồn trong bảo mật thơng tin. Do đĩ, Viện Tiêu chuẩn và Cơng nghệ Hoa Kỳ (National Institute of Standards and Technology – NIST) đã quyết định chọn một chuẩn mã hĩa mới với độ an tồn cao nhằm phục vụ nhu cầu bảo mật thơng tin liên lạc của Chính phủ Hoa Kỳ cũng như trong các ứng dụng dân sự. Thuật tốn Rijndael do Vincent Rijmen và Joan Daeman đã được chính thức chọn trở thành chuẩn mã hĩa nâng cao AES (Advanced Encryption Standard) từ ngày 02 tháng 10 năm 2000. 39
Chương 3 Phương pháp mã hĩa Rijndael là phương pháp mã hĩa theo khối (block cipher) cĩ kích thước khối và mã khĩa thay đổi linh hoạt với các giá trị 128, 192 hay 256 bit. Phương pháp này thích hợp ứng dụng trên nhiều hệ thống khác nhau từ các thẻ thơng minh cho đến các máy tính cá nhân. 3.2 Tham số, ký hiệu, thuật ngữ và hàm AddRoundKey Phép biến đổi sử dụng trong mã hĩa và giải mã, thực hiện việc cộng mã khĩa của chu kỳ vào trạng thái hiện hành. Độ dài của mã khĩa của chu kỳ bằng với kích thước của trạng thái. SubBytes Phép biến đổi sử dụng trong mã hĩa, thực hành việc thay thế phi tuyến từng byte trong trạng thái hiện hành thơng qua bảng thay thế (S-box). InvSubBytes Phép biến đổi sử dụng trong giải mã. Đây là phép biến đổi ngược của phép biến đổi SubBytes. MixColumns Phép biến đổi sử dụng trong mã hĩa, thực hiện thao tác trộn thơng tin của từng cột trong trạng thái hiện hành. Mỗi cột được xử lý độc lập. InvMixColumns Phép biến đổi sử dụng trong giải mã. Đây là phép biến đổi ngược của phép biến đổi MixColumns. 40
Phương pháp mã hĩa Rijndael ShiftRows Phép biến đổi sử dụng trong mã hĩa, thực hiện việc dịch chuyển xoay vịng từng dịng của trạng thái hiện hành với di số tương ứng khác nhau InvShiftRows Phép biến đổi sử dụng trong giải mã. Đây là phép biến đổi ngược của phép biến đổi ShiftRows. Nw Số lượng byte trong một đơn vị dữ liệu “từ”. Trong thuật tốn Rijndael, thuật tốn mở rộng 256/384/512 bit và thuật tốn mở rộng 512/768/1024 bit, giá trị Nw lần lượt là 4, 8 và 16 K Khĩa chính. Nb Số lượng cột (số lượng các từ 8×Nw bit) trong trạng thái. Giá trị Nb = 4, 6, hay 8. Chuẩn AES giới hạn lại giá trị của Nb = 4. Nk Số lượng các từ (8×Nw bit) trong khĩa chính. Giá trị Nk = 4, 6, hay 8. Nr Số lượng chu kỳ, phụ thuộc vào giá trị Nk and Nb theo cơng thức: Nr = max (Nb, Nk)+6. 41
Chương 3 RotWord Hàm được sử dụng trong quá trình mở rộng mã khĩa, thực hiện thao tác dịch chuyển xoay vịng Nw byte thành phần của một từ. SubWord Hàm được sử dụng trong quá trình mở rộng mã khĩa. Nhận vào một từ (Nw byte), áp dụng phép thay thế dựa vào S-box đối với từng byte thành phần và trả về từ gồm Nw byte thành phần đã được thay thế. XOR Phép tốn Exclusive-OR. ⊕ Phép tốn Exclusive-OR. ⊗ Phép nhân hai đa thức (mỗi đa thức cĩ bậc < Nw) modulo cho đa thức xNw + 1. • Phép nhân trên trường hữu hạn. 3.3 Một số khái niệm tốn học Đơn vị thơng tin được xử lý trong thuật tốn Rijndael là byte. Mỗi byte xem như một phần tử của trường Galois GF(28) được trang bị phép cộng (ký hiệu ⊕) và phép nhân (ký hiệu •). Mỗi byte cĩ thể được biểu diễn bằng nhiều cách khác 42
Phương pháp mã hĩa Rijndael nhau: dạng nhị phân ({b7b6b5b4b3b2b1b0}), dạng thập lục phân ({h1h0}) hay dạng 7 i đa thức cĩ các hệ số nhị phân ∑bi x i=0 3.3.1 Phép cộng Phép cộng hai phần tử trên GF(28) được thực hiện bằng cách “cộng” (thực chất là phép tốn XOR, ký hiệu ⊕) các hệ số của các đơn thức đồng dạng của hai đa thức tương ứng với hai tốn hạng đang xét. Như vậy, phép cộng và phép trừ hai phần tử bất kỳ trên GF(28) là hồn tồn tương đương nhau. Nếu biểu diễn lại các phần tử thuộc GF(28) dưới hình thức nhị phân thì phép cộng giữa {a7a6a5a4a3a2a1a0} với {b7b6b5b4b3b2b1b0} là {c7c6c5c4c3c2c1c0} với cabii=⊕ j, 0≤ i ≤ 7. 3.3.2 Phép nhân Khi xét trong biểu diễn đa thức, phép nhân trên GF(28) (ký hiệu •) tương ứng với phép nhân thơng thường của hai đa thức đem chia lấy dư (modulo) cho một đa thức tối giản (irreducible polynomial) bậc 8. Đa thức được gọi là tối giản khi và chỉ khi đa thức này chỉ chia hết cho 1 và chính mình. Trong thuật tốn Rijndael, đa thức tối giản được chọn là mxxxxx()=++++843 1 (3.1) hay 1{1b} trong biểu diễn dạng thập lục phân. 43
Chương 3 Kết quả nhận được là một đa thức bậc nhỏ hơn 8 nên cĩ thể được biểu diễn dưới dạng 1 byte. Phép nhân trên GF(28) khơng thể được biểu diễn bằng một phép tốn đơn giản ở mức độ byte. Phép nhân được định nghĩa trên đây cĩ tính kết hợp, tính phân phối đối với phép cộng và cĩ phần tử đơn vị là {01}.Với mọi đa thức b(x) cĩ hệ số nhị phân với bậc nhỏ hơn 8 tồn tại phần tử nghịch đảo của b(x), ký hiệu b-1(x) (được thực hiện bằng cách sử dụng thuật tốn Euclide mở rộng [45]). Nhận xét: Tập hợp 256 giá trị từ 0 đến 255 được trang bị phép tốn cộng (được định nghĩa là phép tốn XOR) và phép nhân định nghĩa như trên tạo thành trường hữu hạn GF(28). 3.3.2.1 Phép nhân với x Phép nhân (thơng thường) đa thức 7 7 6 5 4 3 2 i b()x = b7 x + b6 x + b5 x + b4 x + b3 x + b2 x + b1x + b0 = ∑bi x (3.2) i=0 với đa thức x cho kết quả là đa thức 8 7 6 5 4 3 2 b7 x + b6 x + b5 x + b4 x + b3 x + b2 x + b1x + b0 x (3.3) Kết quả xbx• () được xác định bằng cách modulo kết quả này cho đa thức m(x). 1. Trường hợp b7 = 0 7 6 5 4 3 2 x • b(x) = b6 x + b5 x + b4 x + b3 x + b2 x + b1x + b0 x (3.4) 44
Phương pháp mã hĩa Rijndael 2. Trường hợp b7 = 1 8 7 6 5 4 3 2 x • b(x) =(b7 x + b6 x + b5 x + b4 x + b3 x + b2 x + b1x + b0 x)mod m()x 8 7 6 5 4 3 2 =(b7 x + b6 x + b5 x + b4 x + b3 x + b2 x + b1 x + b0 x)− m()x (3.5) 8 Như vậy, phép nhân với đa thức x (hay phần tử {00000010} ∈ GF(2 )) cĩ thể được thực hiện ở mức độ byte bằng một phép shift trái và sau đĩ thực hiện tiếp phép tốn XOR với giá trị {1b}nếu b7 = 1 .Thao tác này được ký hiệu là xtime(). Phép nhân với các lũy thừa của x cĩ thể được thực hiện bằng cách áp dụng nhiều lần thao tác xtime(). Kết quả của phép nhân với một giá trị bất kỳ được xác định bằng cách cộng ( ⊕ ) các kết quả trung gian này lại với nhau. Khi đĩ, việc thực hiện phép nhân giữa hai phần tử a, b bất kỳ thuộc GF(28) cĩ thể được tiến hành theo các bước sau: 1. Phân tích một phần tử (giả sử là a) ra thành tổng của các lũy thừa của 2. 2. Tính tổng các kết quả trung gian của phép nhân giữa phần tử cịn lại (là b) với các thành phần là lũy thừa của 2 được phân tích từ a. Ví dụ: {57} • {13} = {fe} vì {57} • {02} = xtime({57}) = {ae} {57} • {04} = xtime({ae}) = {47} {57} • {08} = xtime({47}) = {8e} {57} • {10} = xtime({8e}) = {07}, 45
Chương 3 Như vậy: {57} • {13} = {57} • ({01} ⊕ {02} ⊕ {10}) = {57} ⊕ {ae} ⊕ {07} = {fe} 3.3.3 Đa thức với hệ số trên GF(28) Xét đa thức a(x) và b(x) bậc 4 với các hệ số thuộc GF(28): 3 3 i i a(x) = ∑ ai x và b()x = ∑bi x (3.6) i=0 i=0 Hai đa thức này cĩ thể được biểu diễn lại dưới dạng từ gồm 4 byte [a0 , a1 , a2 , a3 ] và [b0 , b1 , b2 , b3 ]. Phép cộng đa thức được thực hiện bằng cách cộng (chính là phép tốn XOR trên byte) các hệ số của các đơn thức đồng dạng với nhau: 3 i a(x) + b(x) = ∑(ai ⊕ bi )x (3.7) i=0 Phép nhân giữa a(x) với b(x) được thực hiện thơng qua hai bước. Trước tiên, thực hiện phép nhân thơng thường c(x) = a(x)b(x) . 6 5 4 3 2 c(x) = c6 x + c5 x + c4 x + c3 x + c2 x + c1x + c0 (3.8) với c0 = a0 • b0 c4 = a3 • b1 ⊕ a2 • b2 ⊕ a1 • b3 c1 = a1 • b0 ⊕ a0 • b1 c5 = a3 • b2 ⊕ a2 • b3 c2 = a2 • b0 ⊕ a1 • b1 ⊕ a0 • b2 c6 = a3 • b3 (3.9) c3 = a3 • b0 ⊕ a2 • b1 ⊕ a1 • b2 ⊕ a0 • b3 . 46
Phương pháp mã hĩa Rijndael Rõ ràng là c(x) khơng thể được biểu diễn bằng một từ gồm 4 byte. Đa thức c(x) cĩ thể được đưa về một đa thức cĩ bậc nhỏ hơn 4 bằng cách lấy c(x) modulo cho một đa thức bậc 4. Trong thuật tốn Rijndael, đa thức bậc 4 được chọn là Mx()=+ x4 1. Do x j mod(x 4 +1)= x j mod 4 nên kết quả d(x) = a(x) ⊗ b(x) được xác định bằng 3 2 d()x = d3 x + d2 x + d1x + d0 (3.10) với d0 = a0 • b0 ⊕ a3 • b1 ⊕ a2 • b2 ⊕ a1 • b3 d1 = a1 • b0 ⊕ a0 • b1 ⊕ a3 • b2 ⊕ a2 • b3 d2 = a2 • b0 ⊕ a1 • b1 ⊕ a0 • b2 ⊕ a3 • b3 d3 = a3 • b0 ⊕ a2 • b1 ⊕ a1 • b2 ⊕ a0 • b3 (3.11) Trong trường hợp đa thức a(x) cố định, phép nhân d(x) = a(x) ⊗ b(x) cĩ thể được biểu diễn dưới dạng ma trận như sau ⎡d0 ⎤ ⎡a0 a3 a2 a1 ⎤⎡b0 ⎤ ⎢d ⎥ ⎢a a a a ⎥⎢b ⎥ ⎢ 1 ⎥ = ⎢ 1 0 3 2 ⎥⎢ 1 ⎥ (3.12) ⎢d2 ⎥ ⎢a2 a1 a0 a3 ⎥⎢b2 ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎣d3 ⎦ ⎣a3 a2 a1 a0 ⎦⎣b3 ⎦ Do x4 +1 khơng phải là một đa thức tối giản trên GF(28) nên phép nhân với một đa thức a(x) cố định được chọn bất kỳ khơng đảm bảo tính khả nghịch. Vì vậy, trong phương pháp Rijndael đã chọn đa thức a(x) cĩ phần tử nghịch đảo (modulo M(x)) 3 2 a(x) = {03}x + {01}x + {01}x + {02} (3.13) -1 3 2 a(x) = {0b}x + {0d}x + {09}x + {0e} (3.14) 47
Chương 3 3.3.3.1 Phép nhân với x Xét đa thức 3 2 b()x = b3 x + b2 x + b1x + b0 (3.15) Kết quả của phép nhân c(x) = b(x) ⊗ x được xác định bằng 3 2 c()x = b2 x + b1x + b0 x + b3 (3.16) Phép nhân với x tương đương với phép nhân ở dạng ma trận như đã trình bày ở phần trên với các giá trị a0 = a2 = a3 = {00} và a1 = {01}. ⎡c0 ⎤ ⎡00 00 00 01⎤⎡b0 ⎤ ⎢ ⎥ ⎢ ⎥ c ⎢01 00 00 00⎥ b ⎢ 1 ⎥ = ⎢ ⎥⎢ 1 ⎥ (3.17) ⎢c2 ⎥ ⎢00 01 00 00⎥⎢b2 ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎣c3 ⎦ ⎣00 00 01 00⎦⎣b3 ⎦ Như vậy, phép nhân với x hay các lũy thừa của x sẽ tương ứng với phép dịch chuyển xoay vịng các byte thành phần trong một từ. 3 Trong thuật tốn Rijndael cần sử dụng đến đa thức x (a0 = a1 = a2 = {00} và a3 = {01})trong hàm RotWord nhằm xoay vịng 4 byte thành phần của một từ được đưa vào. Như vậy, nếu đưa vào từ gồm 4 byte [b0, b1, b2, b3] thì kết quả nhận được là từ gồm 4 byte [b1, b2, b3, b0]. 48
Phương pháp mã hĩa Rijndael 3.4 Phương pháp Rijndael Phương pháp mã hĩa Rijndael bao gồm nhiều bước biến đổi được thực hiện tuần tự, kết quả đầu ra của bước biến đổi trước là đầu vào của bước biến đổi tiếp theo. Kết quả trung gian giữa các bước biến đổi được gọi là trạng thái (state). Một trạng thái cĩ thể được biểu diễn dưới dạng một ma trận gồm 4 dịng và Nb cột với Nb bằng với độ dài của khối chia cho 32. Mã khĩa chính (Cipher Key) cũng được biểu diễn dưới dạng một ma trận gồm 4 dịng và Nk cột với Nk bằng với độ dài của khĩa chia cho 32. Trong một số tình huống, ma trận biểu diễn một trạng thái hay mã khĩa cĩ thể được khảo sát như mảng một chiều chứa các phần tử cĩ độ dài 4 byte, mỗi phần tử tương ứng với một cột của ma trận. Số lượng chu kỳ, ký hiệu là Nr, phụ thuộc vào giá trị của Nb và Nk theo cơng thức: Nr=+max{ Nb , Nk } 6 k k k k a0,0 a0,1 a0,2 a0,3 a0,4 a0,5 0,0 0,1 0,2 0,3 a1,0 a1,1 a1,2 a1,3 a1,4 a1,5 k1,0 k1,1 k1,2 k1,3 a2,0 a2,1 a2,2 a2,3 a2,4 a2,5 k2,0 k2,1 k2,2 k2,3 a3,0 a3,1 a3,2 a3,3 a3,4 a3,5 k3,0 k3,1 k3,2 k3,3 Hình 3.1. Biểu diễn dạng ma trận của trạng thái (Nb = 6) và mã khĩa (Nk = 4) 49
Chương 3 3.4.1 Quy trình mã hĩa Quy trình mã hĩa Rijndael sử dụng bốn phép biến đổi chính: 1. AddRoundKey: cộng (⊕) mã khĩa của chu kỳ vào trạng thái hiện hành. Độ dài của mã khĩa của chu kỳ bằng với kích thước của trạng thái. 2. SubBytes: thay thế phi tuyến mỗi byte trong trạng thái hiện hành thơng qua bảng thay thế (S-box). 3. MixColumns: trộn thơng tin của từng cột trong trạng thái hiện hành. Mỗi cột được xử lý độc lập. 4. ShiftRows: dịch chuyển xoay vịng từng dịng của trạng thái hiện hành với di số khác nhau. Mỗi phép biến đổi thao tác trên trạng thái hiện hành S. Kết quả S’ của mỗi phép biến đổi sẽ trở thành đầu vào của phép biến đổi kế tiếp trong quy trình mã hĩa. Trước tiên, tồn bộ dữ liệu đầu vào được chép vào mảng trạng thái hiện hành. Sau khi thực hiện thao tác cộng mã khĩa đầu tiên, mảng trạng thái sẽ được trải qua Nr = 10, 12 hay 14 chu kỳ biến đổi (tùy thuộc vào độ dài của mã khĩa chính cũng như độ dài của khối được xử lý). Nr − 1 chu kỳ đầu tiên là các chu kỳ biến đổi bình thường và hồn tồn tương tự nhau, riêng chu kỳ biến đổi cuối cùng cĩ sự khác biệt so với Nr −1 chu kỳ trước đĩ. Cuối cùng, nội dung của mảng trạng thái sẽ được chép lại vào mảng chứa dữ liệu đầu ra. Quy trình mã hĩa Rijndael được tĩm tắt lại như sau: 50
Phương pháp mã hĩa Rijndael 1. Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ mã hĩa. 2. Nr – 1 chu kỳ mã hĩa bình thường: mỗi chu kỳ bao gồm bốn bước biến đổi liên tiếp nhau: SubBytes, ShiftRows, MixColumns, và AddRoundKey. 3. Thực hiện chu kỳ mã hĩa cuối cùng: trong chu kỳ này thao tác MixColumns được bỏ qua. Trong thuật tốn dưới đây, mảng w[] chứa bảng mã khĩa mở rộng; mảng in[] và out[] lần lượt chứa dữ liệu vào và kết quả ra của thuật tốn mã hĩa. Cipher( byte in[4 * Nb], byte out[4 * Nb], word w[Nb * (Nr + 1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w) // Xem phần 3.4.6 for round = 1 to Nr – 1 SubBytes(state) // Xem phần 3.4.2 ShiftRows(state) // Xem phần 3.4.4 MixColumns(state) // Xem phần 3.4.5 AddRoundKey(state, w + round * Nb) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w + Nr * Nb) out = state end 51
Chương 3 3.4.2 Kiến trúc của thuật tốn Rijndael Thuật tốn Rijndael được xây dựng theo kiến trúc SPN sử dụng 16 s-box (kích thước 8 × 8) để thay thế. Trong tồn bộ quy trình mã hĩa, thuật tốn sử dụng chung bảng thay thế s-box cố định. Phép biến đổi tuyến tính bao gồm 2 bước: hốn vị byte và áp dụng song song bốn khối biến đổi tuyến tính (32 bit) cĩ khả năng khuếch tán cao. Hình 3.2 thể hiện một chu kỳ mã hĩa của phương pháp Rijndael. Trên thực tế, trong mỗi chu kỳ mã hĩa, khĩa của chu kỳ được cộng (XOR) sau thao tác biến đổi tuyến tính. Do chúng ta cĩ thực hiện thao tác cộng khĩa trước khi thực hiện chu kỳ đầu tiên nên cĩ thể xem thuật tốn Rijndael thỏa cấu trúc SPN [29]. Hình 3.2. Một chu kỳ mã hĩa của phương pháp Rijndael (với Nb = 4) 52
Phương pháp mã hĩa Rijndael 3.4.3 Phép biến đổi SubBytes Thao tác biến đổi SubBytes là phép thay thế các byte phi tuyến và tác động một cách độc lập lên từng byte trong trạng thái hiện hành. Bảng thay thế (S-box) cĩ tính khả nghịch và quá trình thay thế 1 byte x dựa vào S-box bao gồm hai bước: -1 8 -1 1. Xác định phần tử nghịch đảo x ∈ GF(2 ). Quy ước {00} = {00}. 2. Áp dụng phép biến đổi affine (trên GF(2)) đối với x-1 (giả sử x-1 cĩ biểu diễn nhị phân là {}x7 x6 x5 x4 x3 x2 x1x0 ): ⎡y0 ⎤ ⎡1 0 0 0 1 1 1 1⎤⎡x0 ⎤ ⎡1⎤ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ y1 ⎥ ⎢1 1 0 0 0 1 1 1⎥⎢ x1 ⎥ ⎢1⎥ ⎢y2 ⎥ ⎢1 1 1 0 0 0 1 1⎥⎢x2 ⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ y 1 1 1 1 0 0 0 1 x 0 ⎢ 3 ⎥ = ⎢ ⎥⎢ 3 ⎥ + ⎢ ⎥ (3.18) ⎢y ⎥ ⎢1 1 1 1 1 0 0 0⎥⎢x ⎥ ⎢0⎥ ⎢ 4 ⎥ ⎢ ⎥⎢ 4 ⎥ ⎢ ⎥ ⎢ y5 ⎥ ⎢0 1 1 1 1 1 0 0⎥⎢x5 ⎥ ⎢1⎥ ⎢y ⎥ ⎢0 0 1 1 1 1 1 0⎥⎢x ⎥ ⎢1⎥ ⎢ 6 ⎥ ⎢ ⎥⎢ 6 ⎥ ⎢ ⎥ ⎣⎢y7 ⎦⎥ ⎣⎢0 0 0 1 1 1 1 1⎦⎥⎣⎢x7 ⎦⎥ ⎣⎢0⎦⎥ hay yi = xi ⊕ x(i+4)mod8 ⊕ x(i+5)mod8 ⊕ x(i+6) mod8 ⊕ x(i+7) mod8 ⊕ ci (3.19) với ci là bit thứ i của {63}, 0 ≤ i ≤ 7. 53
Chương 3 Hình 3.3. Thao tác SubBytes tác động trên từng byte của trạng thái Bảng D.1 thể hiện bảng thay thế S-box được sử dụng trong phép biến đổi SubBytes ở dạng thập lục phân. Ví dụ: nếu giá trị {xy} cần thay thế là {53} thì giá trị thay thế S-box ({xy}) được xác định bằng cách lấy giá trị tại dịng 5 cột 3 của Bảng D.1. Như vậy, S-box ({xy}) = {ed}. Phép biến đổi SubBytes được thể hiện dưới dạng mã giả: SubBytes(byte state[4,Nb]) begin for r = 0 to 3 for c = 0 to Nb - 1 state[r,c] = Sbox[state[r,c]] end for end for end 54
Phương pháp mã hĩa Rijndael 3.4.4 Phép biến đổi ShiftRows Hình 3.4. Thao tác ShiftRows tác động trên từng dịng của trạng thái Trong thao tác biến đổi ShiftRows, mỗi dịng của trạng thái hiện hành được dịch chuyển xoay vịng đi một số vị trí. Byte Src, tại dịng r cột c sẽ dịch chuyển đến cột (c - shift(r, Nb)) mod Nb hay: ' sr,c = sr,()c+shift()r,Nb mod Nb với 0 < r < 8 và 0 ≤ c < Nb (3.20) Giá trị di số shift(r, Nb) phụ thuộc vào chỉ số dịng r và kích thước Nb của khối dữ liệu. Bảng 3.1. Giá trị di số shift(r, Nb) r shift(r, Nb) 1 2 3 4 1 2 3 Nb 6 1 2 3 8 1 3 4 55
Chương 3 Phép biến đổi ShiftRows được thể hiện dưới dạng mã giả: ShiftRows(byte state[4,Nb]) begin byte t[Nb] for r = 1 to 3 for c = 0 to Nb - 1 t[c] = state[r, (c + h[r,Nb]) mod Nb] end for for c = 0 to Nb – 1 state[r,c] = t[c] end for end for end 3.4.5 Phép biến đổi MixColumns Trong thao tác biến đổi MixColumns, mỗi cột của trạng thái hiện hành được biểu diễn dưới dạng đa thức s(x) cĩ các hệ số trên GF(28). Thực hiện phép nhân s'(x) = a(x)⊗ s(x) (3.21) với 3 2 a(x) = {03}x + {01}x + {01}x + {02} (3.22) Thao tác này được thể hiện ở dạng ma trận như sau: ⎡ ' ⎤ s0,c ⎡02 03 01 01⎤ ⎡s0,c ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ s ' 01 02 03 01 s ⎢ 1,c ⎥ = ⎢ ⎥ ⎢ 1,c ⎥ (3.23) ⎢ ' ⎥ s ⎢01 01 02 03⎥ ⎢s2,c ⎥ ⎢ 2,c ⎥ ⎢ ⎥ ⎢ ⎥ ' s ⎣⎢s3,c ⎦⎥ ⎣03 01 01 02⎦ ⎣⎢ 3,c ⎦⎥ 56
Phương pháp mã hĩa Rijndael Hình 3.5. Thao tác MixColumns tác động lên mỗi cột của trạng thái Trong đoạn mã chương trình dưới đây, hàm FFmul(x, y) thực hiện phép nhân (trên trường GF(28)) hai phần tử x và y với nhau MixColumns(byte state[4,Nb]) begin byte t[4] for c = 0 to Nb – 1 for r = 0 to 3 t[r] = state[r,c] end for for r = 0 to 3 state[r,c] = FFmul(0x02, t[r]) xor FFmul(0x03, t[(r + 1) mod 4]) xor t[(r + 2) mod 4] xor t[(r + 3) mod 4] end for end for end 57
Chương 3 3.4.6 Thao tác AddRoundKey Phương pháp Rijndael bao gồm nhiều chu kỳ mã hĩa liên tiếp nhau, mỗi chu kỳ cĩ một mã khĩa riêng (Round Key) cĩ cùng kích thước với khối dữ liệu đang được xử lý và được phát sinh từ mã khĩa chính (Cipher Key) cho trước ban đầu. Mã khĩa của chu kỳ cũng được biểu diễn bằng một ma trận gồm 4 dịng và Nb cột. Mỗi cột của trạng thái hiện hành được XOR với cột tương ứng của mã khĩa của chu kỳ đang xét: [s'0,c , s'1,c , s'2,c , s'3,c ] = [s0,c , s1,c , s2,c , s3,c ] ⊕[wround∗Nb+c ], (3.24) với 0 ≤ c < Nb. Thao tác biến đổi ngược của AddRoundKey cũng chính là thao tác AddRoundKey. Trong đoạn chương trình dưới đây, hàm xbyte(r, w) thực hiện việc lấy byte thứ r trong từ w. AddRoundKey(byte state[4,Nb], word rk[]) // rk = w + round * Nb begin for c = 0 to Nb – 1 for r = 0 to 3 state[r,c] = state[r,c] xor xbyte(r, rk[c]) end for end for end 58
Phương pháp mã hĩa Rijndael Hình 3.6. Thao tác AddRoundKey tác động lên mỗi cột của trạng thái 3.5 Phát sinh khĩa của mỗi chu kỳ Các khĩa của mỗi chu kỳ (RoundKey) được phát sinh từ khĩa chính. Quy trình phát sinh khĩa cho mỗi chu kỳ gồm 2 giai đoạn:: 1. Mở rộng khĩa chính thành bảng khĩa mở rộng, 2. Chọn khĩa cho mỗi chu kỳ từ bảng khĩa mở rộng. 3.5.1 Xây dựng bảng khĩa mở rộng Bảng khĩa mở rộng là mảng 1 chiều chứa các từ (cĩ độ dài 4 byte), được ký hiệu là w[Nb*(Nr + 1)]. Hàm phát sinh bảng khĩa mở rộng phụ thuộc vào giá trị Nk, tức là phụ thuộc vào độ dài của mã khĩa chính. 59
Chương 3 Hàm SubWord(W) thực hiện việc thay thế (sử dụng S-box) từng byte thành phần của từ 4 byte được đưa vào và trả kết quả về là một từ bao gồm 4 byte kết quả sau khi thực hiệc việc thay thế. Hàm RotWord(W) thực hiện việc dịch chuyển xoay vịng 4 byte thành phần (a, b, c, d) của từ được đưa vào. Kết quả trả về của hàm RotWord là một từ gồm 4 byte thành phần là (b, c, d, a). KeyExpansion(byte key[4 * Nk], word w[Nb * (Nr + 1)], Nk) begin i=0 while (i < Nk) w[i] = word[key[4*i],key[4*i+1], key[4*i+2],key[4*i+3]] i = i + 1 end while i = Nk while (i < Nb * (Nr + 1)) word temp = w[i - 1] if (i mod Nk = 0) then temp = SubWord(RotWord(temp)) xor Rcon[i / Nk] else if (Nk = 8) and (i mod Nk = 4) then temp = SubWord(temp) end if w[i] = w[i - Nk] xor temp i = i + 1 end while end 60
Phương pháp mã hĩa Rijndael Các hằng số của mỗi chu kỳ hồn tồn độc lập với giá trị Nk và được xác định 8 bằng Rcon[i] = (RC[i], {00}, {00}, {00}) với RC[i] ∈ GF(2 ) và thỏa: RC[1]=1 ({01}) (i–1) RC[i] =x ({02})•(RC[i-1]) = x (3.25) 3.5.2 Xác định khĩa của chu kỳ Khĩa của chu kỳ thứ i được xác định bao gồm các từ (4 byte) cĩ chỉ số từ Nb* i đến Nb* ( i +− 1) 1 của bảng mã khĩa mở rộng. Như vậy, mã khĩa của chu kỳ thứ i bao gồm các phần tử wNb[*] i , wNb[ * i+ 1] , , wNb[ *( i+− 1) 1] . w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 w11 w12 w13 w14 w15 w16 w17 Mã khóa chu kỳ 0 Mã khóa chu kỳ 1 Mã khóa chu kỳ 2 Hình 3.7. Bảng mã khĩa mở rộng và cách xác định mã khĩa của chu kỳ (Nb = 6 và Nk = 4) Việc phát sinh mã khĩa cho các chu kỳ cĩ thể được thực hiện mà khơng nhất thiết phải sử dụng đến mảng wNb[ *( Nr+ 1)] . Trong trường hợp dung lượng bộ nhớ hạn chế như ở các thẻ thơng minh, các mã khĩa cho từng chu kỳ cĩ thể được xác định khi cần thiết ngay trong quá trình xử lý mà chỉ cần sử dụng max(Nk , Nb )* 4 byte trong bộ nhớ. Bảng khĩa mở rộng luơn được tự động phát sinh từ khĩa chính mà khơng cần phải được xác định trực tiếp từ người dùng hay chương trình ứng dụng. Việc 61
Chương 3 chọn lựa khĩa chính (Cipher Key) là hồn tồn tự do và khơng cĩ một điều kiện ràng buộc hay hạn chế nào. 3.6 Quy trình giải mã Quy trình giải mã được thực hiện qua các giai đoạn sau: 1. Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ giải mã. 2. Nr −1 chu kỳ giải mã bình thường: mỗi chu kỳ bao gồm bốn bước biến đổi liên tiếp nhau: InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns. 3. Thực hiện chu kỳ giải mã cuối cùng. Trong chu kỳ này, thao tác InvMixColumns được bỏ qua. Dưới đây là mã giả của quy trình giải mã: InvCipher( byte in[4 * Nb], byte out[4 * Nb], word w[Nb * (Nr + 1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w + Nr * Nb) // Xem phần 3.4.6 for round = Nr - 1 downto 1 InvShiftRows(state) // Xem phần 3.6.1 InvSubBytes(state) // Xem phần 3.6.2 AddRoundKey(state, w + round * Nb) InvMixColumns(state) // Xem phần 3.6.3 end for 62
Phương pháp mã hĩa Rijndael InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w) out = state end 3.6.1 Phép biến đổi InvShiftRows Hình 3.8. Thao tác InvShiftRows tác động lên từng dịng của trạng thái hiện hành InvShiftRows chính là phép biến đổi ngược của phép biến đổi ShiftRows. Dịng đầu tiên của trạng thái sẽ vẫn được giữ nguyên trong khác ba dịng cuối của trạng thái sẽ được dịch chuyển xoay vịng theo chiều ngược với phép biến đổi ShiftRows với các di số Nb–shift (r, Nb) khác nhau. Các byte ở cuối dịng được đưa vịng lên đầu dịng trong khi các byte cịn lại cĩ khuynh hướng di chuyển về cuối dịng. ' sr,(c+shift (r,Nb)) mod Nb = sr,c với 0 < r < 4 và 0 ≤ c < Nb (3.26) 63
Chương 3 Giá trị của di số shift(r,Nb) phụ thuộc vào chỉ số dịng r và kích thước Nb của khối và được thể hiện trong Bảng 3.1. InvShiftRows(byte state[4,Nb]) begin byte t[Nb] for r = 1 to 3 for c = 0 to Nb - 1 t[(c + h[r,Nb]) mod Nb] = state[r,c] end for for c = 0 to Nb – 1 state[r,c] = t[c] end for end for end 3.6.2 Phép biến đổi InvSubBytes Phép biến đổi ngược của thao tác SubBytes, ký hiệu là InvSubBytes, sự dụng 8 -1 bảng thay thế nghịch đảo của S-box trên GF(2 ), ký hiệu là S-box . Quá trình -1 thay thế 1 byte y dựa vào S-box bao gồm hai bước sau: 1. Áp dụng phép biến đổi affine (trên GF(2)) sau đối với y (cĩ biểu diễn nhị phân là {}y7 y6 y5 y4 y3 y2 y1 y0 ): 64
Phương pháp mã hĩa Rijndael ⎡x0 ⎤ ⎡0 0 1 0 0 1 0 1⎤⎡y0 ⎤ ⎡1⎤ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ x1 ⎥ ⎢1 0 0 1 0 0 1 0⎥⎢ y1 ⎥ ⎢0⎥ ⎢x2 ⎥ ⎢0 1 0 0 1 0 0 1⎥⎢y2 ⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ x 1 0 1 0 0 1 0 0 y 0 ⎢ 3 ⎥ = ⎢ ⎥⎢ 3 ⎥ + ⎢ ⎥ (3.27) ⎢x ⎥ ⎢0 1 0 1 0 0 1 0⎥⎢y ⎥ ⎢0⎥ ⎢ 4 ⎥ ⎢ ⎥⎢ 4 ⎥ ⎢ ⎥ ⎢x5 ⎥ ⎢0 0 1 0 1 0 0 1⎥⎢ y5 ⎥ ⎢0⎥ ⎢x ⎥ ⎢1 0 0 1 0 1 0 0⎥⎢y ⎥ ⎢0⎥ ⎢ 6 ⎥ ⎢ ⎥⎢ 6 ⎥ ⎢ ⎥ ⎣⎢x7 ⎦⎥ ⎣⎢0 1 0 0 1 0 1 0⎦⎥⎣⎢y7 ⎦⎥ ⎣⎢0⎦⎥ hay xi = y()i+2 mod 8 ⊕ y(i+5) mod 8 ⊕ y(i+7) mod 8 ⊕ di , với di là bit thứ i của giá trị {05},0 ≤ i ≤ 7. (3.28) Rõ ràng đây chính là phép biến đổi affine ngược của phép biến đổi affine ở bước 1 của S-box. 8 2. Gọi x là phần tử thuộc GF(2 ) cĩ biểu diễn nhị phân là {}x7 x6 x5 x4 x3 x2 x1x0 . -1 8 -1 Xác định phần tử nghịch đảo x ∈ GF(2 ) với quy ước {00} = {00} InvSubBytes(byte state[4,Nb]) begin for r = 0 to 3 for c = 0 to Nb - 1 state[r,c] = InvSbox[state[r,c]] end for end for end 65
Chương 3 Bảng D.2 thể hiện bảng thay thế nghịch đảo được sử dụng trong phép biến đổi InvSubBytes 3.6.3 Phép biến đổi InvMixColumns InvMixColumns là biến đổi ngược của phép biến đổi MixColumns. Mỗi cột của trạng thái hiện hành được xem như đa thức s(x) bậc 4 cĩ các hệ số thuộc GF(28) và được nhân với đa thức a-1(x) là nghịch đảo của đa thức a(x) (modulo M(x)) được sử dụng trong phép biến đổi MixColumns. -1 3 2 a(x) = {0b}x + {0d}x + {09}x + {0e} (3.29) Phép nhân s′(x) = a−1(x) ⊗ s(x ) cĩ thể được biểu diễn dưới dạng ma trận: ⎡ ' ⎤ s0,c ⎡0e 0b 0d 09⎤ ⎡s0,c ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ s ' 09 0e 0b 0d s ⎢ 1,c ⎥ = ⎢ ⎥ ⎢ 1,c ⎥ với 0 ≤ c < Nb (3.30) ⎢ ' ⎥ s ⎢0d 09 0e 0b⎥ ⎢s2,c ⎥ ⎢ 2,c ⎥ ⎢ ⎥ ⎢ ⎥ ' s ⎣⎢s3,c ⎦⎥ ⎣0b 0d 09 0e⎦ ⎣⎢ 3,c ⎦⎥ Trong đoạn mã chương trình dưới đây, hàm FFmul(x, y) thực hiện phép nhân (trên trường GF(28)) hai phần tử x và y với nhau. InvMixColumns(byte block[4,Nb]) begin byte t[4] for c = 0 to Nb – 1 for r = 0 to 3 t[r] = block[r,c] end for for r = 0 to 3 66
Phương pháp mã hĩa Rijndael block[r,c] = FFmul(0x0e, t[r]) xor FFmul(0x0b, t[(r + 1) mod 4]) xor FFmul(0x0d, t[(r + 2) mod 4]) xor FFmul(0x09, t[(r + 3) mod 4]) end for end for end 3.6.4 Quy trình giải mã tương đương Nhận xét: 1. Phép biến đổi InvSubBytes thao tác trên giá trị của từng byte riêng biệt của trạng thái hiện hành, trong khi phép biến đổi InvShiftRows chỉ thực hiện thao tác di chuyển các byte mà khơng làm thay đổi giá trị của chúng. Do đĩ, thứ tự của hai phép biến đổi này trong quy trình mã hĩa cĩ thể được đảo ngược. 2. Với phép biến đổi tuyến tính A bất kỳ, ta cĩ A (xk+= ) AxAk ( ) + ( ) . Từ đĩ, suy ra InvMixColumns(state XOR Round Key)= InvMixColumns(state) XOR InvMixColumns(Round Key) Như vậy, thứ tự của phép biến đổi InvMixColumns và AddRoundKey trong quy trình giải mã cĩ thể được đảo ngược với điều kiện mỗi từ (4 byte) trong bảng mã khĩa mở rộng sử dụng trong giải mã phải được biến đổi bởi InvMixColumns. Do trong chu kỳ mã hĩa cuối cùng khơng thực hiện thao tác MixColumns nên khơng 67
Chương 3 cần thực hiện thao tác InvMixColumns đối với mã khĩa của chu kỳ giải mã đầu tiên cũng như chu kỳ giải mã cuối cùng. Vậy, quy trình giải mã Rijndael cĩ thể được thực hiện theo với trình tự các phép biến đổi ngược hồn tồn tương đương với quy trình mã hĩa. EqInvCipher(byte in[4*Nb], byte out[4*Nb], word dw[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, dw + Nr * Nb) for round = Nr - 1 downto 1 InvSubBytes(state) InvShiftRows(state) InvMixColumns(state) AddRoundKey(state, dw + round * Nb) end for InvSubBytes(state) InvShiftRows(state) AddRoundKey(state, dw) out = state end Trong quy trình trên, bảng mã khĩa mở rộng dw được xây dựng từ bảng mã khĩa w bằng cách áp dụng phép biến đổi InvMixColumns lên từng từ (4 byte) trong w, ngoại trừ Nb từ đầu tiên và cuối cùng của w. 68
Phương pháp mã hĩa Rijndael for i = 0 to (Nr + 1) * Nb – 1 dw[i] = w[i] end for for rnd = 1 to Nr – 1 InvMixColumns(dw + rnd * Nb) end for 3.7 Các vấn đề cài đặt thuật tốn Gọi a là trạng thái khi bắt đầu chu kỳ mã hĩa. Gọi b, c, d, e lần lượt là trạng thái kết quả đầu ra sau khi thực hiện các phép biến đổi SubBytes, ShiftRows, MixColumns và AddRoundKey trong chu kỳ đang xét. Quy ước: trong trạng thái s (,,,,s = abcde), cột thứ j được kí hiệu sj, phần tử tại dịng i cột j kí hiệu là si, j. ⎡b0, j ⎤ ⎡S[a0, j ]⎤ ⎢b ⎥ ⎢S[a ]⎥ Sau biến đổi SubBytes: ⎢ 1, j ⎥ = ⎢ 1, j ⎥ (3.31) ⎢b2, j ⎥ ⎢S[a2, j ]⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢b3, j ⎦⎥ ⎣⎢S[a3, j ]⎦⎥ ⎡c0, j ⎤ ⎡ b0, j ⎤ ⎢ ⎥ ⎢ ⎥ c1, j b1,()j+ shift ()1,Nb mod Nb Sau biến đổi ShiftRows: ⎢ ⎥ = ⎢ ⎥ (3.32) ⎢c 2, j ⎥ ⎢b2,()j+ shift ()2,Nb mod Nb ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢c3, j ⎦⎥ ⎣⎢b3,()j+ shift ()3,Nb mod Nb ⎦⎥ ⎡d0, j ⎤ ⎡02 03 01 01⎤⎡c0, j ⎤ ⎢ ⎥ ⎢ ⎥ d ⎢01 02 03 01⎥ c Sau biến đổi MixColumns: ⎢ 1, j ⎥ = ⎢ ⎥⎢ 1, j ⎥ (3.33) ⎢d2, j ⎥ ⎢01 01 02 03⎥⎢c2, j ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎣⎢d3, j ⎦⎥ ⎣03 01 01 02⎦⎣⎢c3, j ⎦⎥ 69
Chương 3 ⎡e0, j ⎤ ⎡d0, j ⎤ ⎡k0, j ⎤ ⎢e ⎥ ⎢d ⎥ ⎢k ⎥ Sau biến đổi AddRoundKey: ⎢ 1, j ⎥ = ⎢ 1, j ⎥ ⊕ ⎢ 1, j ⎥ (3.34) ⎢e2, j ⎥ ⎢d2, j ⎥ ⎢k2, j ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢e3, j ⎦⎥ ⎣⎢d3, j ⎦⎥ ⎣⎢k3, j ⎦⎥ Kết hợp các kết quả trung gian của mỗi phép biến đổi trong cùng chu kỳ với nhau, ta cĩ: ⎡e0, j ⎤ ⎡02 03 01 01⎤⎡ S[a0, j ] ⎤ ⎡k0, j ⎤ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ e1, j 01 02 03 01 S[]a1,()j+shift()1,Nb mod Nb k1, j ⎢ ⎥ = ⎢ ⎥⎢ ⎥ ⊕ ⎢ ⎥ (3.35) ⎢e2, j ⎥ ⎢01 01 02 03⎥⎢S[]a2,()j+shift()2,Nb mod Nb ⎥ ⎢k2, j ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣⎢e3, j ⎦⎥ ⎣03 01 01 02⎦⎣⎢S[]a3,()j+shift()3,Nb mod Nb ⎦⎥ ⎣⎢k3, j ⎦⎥ Ký hiệu j[]r = ( j + shift(r, Nb))mod Nb , biểu thức (3.35) cĩ thể viết lại như sau: ⎡⎤Sa[]0,j[] 0 ⎡⎤ek0,j ⎡⎤02 03 01 01 ⎢⎥ ⎡⎤ 0, j ⎢⎥⎢⎥⎢⎥Sa⎡⎤ ⎢⎥ ek01 02 03 01 ⎣⎦1,j[] 1 ⎢⎥1,j =⊕⎢⎥⎢⎥ ⎢⎥ 1, j (3.36) ⎢⎥ ⎢⎥ek2,j ⎢⎥01 01 02 03 Sa⎡⎤ ⎢⎥ 2, j ⎢⎥⎢⎥⎢⎥⎣⎦2,j[] 2 ⎢⎥ ⎢⎥ek3,j ⎣⎦03 01 01 02 ⎢⎥ ⎢⎥ 3, j ⎣⎦Sa⎡⎤ ⎣⎦ ⎣⎦⎢⎥⎣⎦3,j[] 3 Khai triển phép nhân ma trận, ta cĩ: ⎡⎤ek0, j ⎡⎤02 ⎡⎤ 03 ⎡⎤ 01 ⎡⎤ 01 ⎡⎤0, j ⎢⎥ ⎢⎥ ek⎢⎥01 ⎢⎥ 02 ⎢⎥ 03 ⎢⎥ 01 ⎢⎥1, j =⊕⊕⊕⊕Sa⎡⎤⎢⎥ Sa ⎡⎤ ⎢⎥ Sa ⎡⎤ ⎢⎥ Sa ⎡⎤ ⎢⎥ ⎢⎥1, j ⎣⎦0,jjj[] 0 ⎣⎦ 1, [] 1 ⎣⎦ 2, [] 2 ⎣⎦ 3, j [] 3 ⎢⎥ek2, j ⎢⎥01 ⎢⎥ 01 ⎢⎥ 02 ⎢⎥ 03 ⎢⎥2, j ⎢⎥⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎣⎦⎢⎥ek3, j ⎣⎦03 ⎣⎦ 01 ⎣⎦ 01 ⎣⎦ 02 ⎣⎦⎢⎥3, j (3.37) 70
Phương pháp mã hĩa Rijndael Định nghĩa các bảng tra cứu T0, T1, T2, T3 như sau: ⎡S[]a • 02⎤ ⎡S[]a • 03⎤ ⎢ S[]a ⎥ ⎢S[]a • 02⎥ T []a = ⎢ ⎥ , T []a = ⎢ ⎥ , 0 ⎢ S[]a ⎥ 1 ⎢ S[]a ⎥ ⎢ ⎥ ⎢ ⎥ ⎣S[]a • 03⎦ ⎣ S[]a ⎦ ⎡ S[]a ⎤ ⎡ S[]a ⎤ ⎢S[]a • 03⎥ ⎢ S[]a ⎥ T []a = ⎢ ⎥ , T []a = ⎢ ⎥ (3.38) 2 ⎢S[]a • 02⎥ 3 ⎢S[]a • 03⎥ ⎢ ⎥ ⎢ ⎥ ⎣ S[]a ⎦ ⎣S[]a • 02⎦ Khi đĩ, biểu thức (3.38) được viết lại như sau: ⎛ 3 ⎞ e T a w (3.39) j = ⎜⊕ i []i, j[i] ⎟ ⊕ round*Nb+ j ⎝ i=0 ⎠ với round là số thứ tự của chu kỳ đang xét. Như vậy, mỗi cột ej của trạng thái kết quả sau khi thực hiện một chu kỳ mã hĩa cĩ thể được xác định bằng bốn phép tốn XOR trên các số nguyên 32 bit sử dụng bốn bảng tra cứu T0, T1, T2 và T3. Cơng thức (3.39) chỉ áp dụng được cho Nr-1 chu kì đầu. Do chu kỳ cuối cùng khơng thực hiện phép biến đổi MixColumns nên cần xây dựng 4 bảng tra cứu riêng cho chu kì này: ⎡S[a]⎤ ⎡ 0 ⎤ ⎡ 0 ⎤ ⎡ 0 ⎤ ⎢ 0 ⎥ ⎢S[a]⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ U []a = ⎢ ⎥ ,U []a = ⎢ ⎥ ,U []a = ⎢ ⎥ ,U []a = ⎢ ⎥ (3.40) 0 ⎢ 0 ⎥ 1 ⎢ 0 ⎥ 2 ⎢S[a]⎥ 3 ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 0 ⎦ ⎣ 0 ⎦ ⎣ 0 ⎦ ⎣S[a]⎦ 71
Chương 3 3.7.1 Nhận xét Kỹ thuật sử dụng bảng tra cứu giúp cải thiện tốc độ mã hĩa và giải mã một cách đáng kể. Ngồi ra, kỹ thuật này cịn giúp chống lại các phương pháp phá mã dựa trên thời gian mã hĩa do khi sử dụng bảng tra cứu, thời gian mã hĩa dữ liệu bất kỳ đều như nhau. Kỹ thuật này cĩ thể được sử dụng trong quy trình mã hĩa và quy trình giải mã tương đương do sự tương ứng giữa các bước thực hiện của hai quy trình này. Khi đĩ, chúng ta cĩ thể dùng chung một quy trình cho việc mã hĩa và giải mã nhưng sử dụng bảng tra khác nhau. Trên thực tế, các bảng tra cứu cĩ thể được lưu trữ sẵn hoặc được xây dựng trực tiếp dựa trên bảng thay thế S-Box cùng với thơng tin về các khuơn dạng tương ứng. Trên các bộ vi xử lý 32-bit, những thao tác biến đổi sử dụng trong quy trình mã hĩa cĩ thể được tối ưu hĩa bằng cách sử dụng bốn bảng tra cứu, mỗi bảng cĩ 256 phần tử với kích thước mỗi phần tử là 4 byte. Với mỗi phần tử a ∈ GF(28), đặt: ⎡S[]a • 02⎤ ⎡S[]a • 03⎤ ⎢ S[]a ⎥ ⎢S[]a • 02⎥ T []a = ⎢ ⎥ , T []a = ⎢ ⎥ , 0 ⎢ S[]a ⎥ 1 ⎢ S[]a ⎥ ⎢ ⎥ ⎢ ⎥ ⎣S[]a • 03⎦ ⎣ S[]a ⎦ ⎡ S[]a ⎤ ⎡ S[]a ⎤ ⎢S[]a • 03⎥ ⎢ S[]a ⎥ T []a = ⎢ ⎥ , T []a = ⎢ ⎥ (3.41) 2 ⎢S[]a • 02⎥ 3 ⎢S[]a • 03⎥ ⎢ ⎥ ⎢ ⎥ ⎣ S[]a ⎦ ⎣S[]a • 02⎦ 72
Phương pháp mã hĩa Rijndael i Nhận xét: Ti[a] = RotWord(Ti-1[a]) với i = 1,2,3 . Ký hiệu RotWord là hàm xử lý gồm i lần thực hiện hàm RotWord, ta cĩ: i Ti []a = RotWord ()T0 []a (3.42) Như vậy, thay vì dùng 4 kilobyte để lưu trữ sẵn cả bốn bảng, chỉ cần tốn 1 kilobyte để lưu bảng đầu tiên, các bảng cịn lại cĩ thể được phát sinh lại khi sử dụng. Các hạn chế về bộ nhớ thường khơng được đặt ra, trừ một số ít trường hợp như đối với các applet hay servlet. Khi đĩ, thay vì lưu trữ sẵn bảng tra cứu, chỉ cần lưu đoạn mã xử lý phát sinh lại các bảng này. Lúc đĩ, cơng thức (3.39) sẽ trở thành: 3 3 i (3.43) e j = k j ⊕Ti [ai, j[]i ] = k j ⊕ RotWord ()T0 [ai, j []i ] i=0 i=0 3.8 Kết quả thử nghiệm Bảng 3.2. Tốc độ xử lý của phương pháp Rijndael Tốc độ xử lý (Mbit/giây) Kích thước Pentium Pentium II Pentium III Pentium IV (bit) 200 MHz 400 MHz 733 MHz 2.4 GHz Khĩa Khối C++ C C++ C C++ C C++ C 128 128 69.4 70.5 138.0 141.5 252.9 259.2 863.0 884.7 192 128 58.0 59.8 116.2 119.7 212.9 219.3 726.5 748.3 256 128 50.1 51.3 101.2 101.5 185.5 186.1 633.5 634.9 Kết quả thử nghiệm thuật tốn Rijndael được ghi nhận trên máy Pentium 200 MHz (sử dụng hệ điều hành Microsoft Windows 98), máy Pentium II 400 MHz, Pentium III 733 MHz (sử dụng hệ điều hành Microsoft Windows 2000 Professional), Pentium IV 2,4GHz (sử dụng hệ điều hành Microsoft Windows XP Service Pack 2). 73
Chương 3 3.9 Kết luận 3.9.1 Khả năng an tồn Việc sử dụng các hằng số khác nhau ứng với mỗi chu kỳ giúp hạn chế khả năng tính đối xứng trong thuật tốn. Sự khác nhau trong cấu trúc của việc mã hĩa và giải mã đã hạn chế được các khĩa “yếu” (weak key) như trong phương pháp DES (xem phần 4.5.1). Ngồi ra, thơng thường những điểm yếu liên quan đến mã khĩa đều xuất phát từ sự phụ thuộc vào giá trị cụ thể của mã khĩa của các thao tác phi tuyến như trong phương pháp IDEA (International Data Encryption Algorithm). Trong các phiên bản mở rộng, các khĩa được sử dụng thơng qua thao tác XOR và tất cả những thao tác phi tuyến đều được cố định sẵn trong S-box mà khơng phụ thuộc vào giá trị cụ thể của mã khĩa (xem phần 4.5.4). Tính chất phi tuyến cùng khả năng khuếch tán thơng tin (diffusion) trong việc tạo bảng mã khĩa mở rộng làm cho việc phân tích mật mã dựa vào các khĩa tương đương hay các khĩa cĩ liên quan trở nên khơng khả thi (xem phần 4.5.5). Đối với phương pháp vi phân rút gọn, việc phân tích chủ yếu khai thác đặc tính tập trung thành vùng (cluster) của các vết vi phân trong một số phương pháp mã hĩa. Trong trường hợp thuật tốn Rijndael với số lượng chu kỳ lớn hơn 6, khơng tồn tại phương pháp cơng phá mật mã nào hiệu quả hơn phương pháp thử và sai (xem phần 4.5.2). Tính chất phức tạp của biểu thức S-box trên GF(28) cùng với hiệu ứng khuếch tán giúp cho thuật tốn khơng thể bị phân tích bằng phương pháp nội suy (xem phần 4.5.3). 74
Phương pháp mã hĩa Rijndael 3.9.2 Đánh giá Phương pháp Rijndael thích hợp cho việc triển khai trên nhiều hệ thống khác nhau, khơng chỉ trên các máy tính cá nhân mà điển hình là sử dụng các chip Pentium, mà cả trên các hệ thống thẻ thơng minh. Trên các máy tính cá nhân, thuật tốn AES thực hiện việc xử lý rất nhanh so với các phương pháp mã hĩa khác. Trên các hệ thống thẻ thơng minh, phương pháp này càng phát huy ưu điểm khơng chỉ nhờ vào tốc độ xử lý cao mà cịn nhờ vào mã chương trình ngắn gọn, thao tác xử lý sử dụng ít bộ nhớ. Ngồi ra, tất cả các bước xử lý của việc mã hĩa và giải mã đều được thiết kế thích hợp với cơ chế xử lý song song nên phương pháp Rijndael càng chứng tỏ thế mạnh của mình trên các hệ thống thiết bị mới. Do đặc tính của việc xử lý thao tác trên từng byte dữ liệu nên khơng cĩ sự khác biệt nào được đặt ra khi triển khai trên hệ thống big-endian hay little-endian. Xuyên suốt phương pháp AES, yêu cầu đơn giản trong việc thiết kế cùng tính linh hoạt trong xử lý luơn được đặt ra và đã được đáp ứng. Độ lớn của khối dữ liệu cũng như của mã khĩa chính cĩ thể tùy biến linh hoạt từ 128 đến 256-bit với điều kiện là chia hết cho 32. Số lượng chu kỳ cĩ thể được thay đổi tùy thuộc vào yêu cầu riêng được đặt ra cho từng ứng dụng và hệ thống cụ thể. Tuy nhiên, vẫn tồn tại một số hạn chế mà hầu hết liên quan đến quá trình giải mã. Mã chương trình cũng như thời gian xử lý của việc giải mã tương đối lớn hơn việc mã hĩa, mặc dù thời gian này vẫn nhanh hơn đáng kể so với một số phương pháp khác. Khi cài đặt bằng chương trình, do quá trình mã hĩa và giải mã khơng giống nhau nên khơng thể tận dụng lại tồn bộ đoạn chương trình mã hĩa cũng như các bảng tra cứu cho việc giải mã. Khi cài đặt trên phần cứng, việc giải mã 75
Chương 3 chỉ sử dụng lại một phần các mạch điện tử sử dụng trong việc mã hĩa và với trình tự sử dụng khác nhau. Phương pháp Rijndael với mức độ an tồn rất cao cùng các ưu điểm đáng chú ý khác chắc chắn sẽ nhanh chĩng được áp dụng rộng rãi trong nhiều ứng dụng trên các hệ thống khác nhau. 76
Phương pháp Rijndael mở rộng Chương 4 Phương pháp Rijndael mở rộng " Trong chương 3, chúng ta đã tìm hiểu về phương pháp mã hĩa Rijndael. Nội dung của chương 4 sẽ trình bày một số phiên bản mở rộng của chuẩn mã hĩa Rijndael. Một số kết quả thử nghiệm cùng với phần phân tích và chứng minh khả năng an tồn của phương pháp Rijndael và các phiên bản mở rộng này cũng được trình bày trong chương 4. 4.1 Nhu cầu mở rộng phương pháp mã hĩa Rijndael Vào thập niên 1970-1980, phương pháp DES vốn được xem là rất an tồn và chưa thể cơng phá bằng các cơng nghệ thời bấy giờ. Tuy nhiên, hiện nay phương pháp này cĩ thể bị phá vỡ và trở nên khơng cịn đủ an tồn để bảo vệ các thơng tin quan trọng. Đây chính là một trong những lý do mà NIST quyết định chọn một thuật tốn mã hĩa mới để thay thế DES nhằm phục vụ nhu cầu bảo mật thơng tin của Chính phủ Hoa Kỳ cũng như trong một số ứng dụng dân sự khác. Phương pháp mã hĩa Rijndael được đánh giá cĩ độ an tồn rất cao và phương pháp vét cạn vẫn là cách hiệu quả nhất để cơng phá thuật tốn này. Với khả năng 77
Chương 4 hiện nay của các hệ thống máy tính trên Thế giới thì giải pháp vét cạn vẫn là khơng khả thi. Tuy nhiên, với sự phát triển ngày càng nhanh của cơng nghệ thơng tin, các thế hệ máy tính mới ra đời với năng lực và tốc độ xử lý ngày càng cao, thuật tốn Rijndael sẽ cĩ thể bị cơng phá trong tương lai. Khi đĩ, những thơng tin quan trọng vốn đã được bảo mật bằng phương pháp Rijndael cần phải được mã hĩa lại bằng một phương pháp mã hĩa mới an tồn hơn. Vấn đề tái tổ chức dữ liệu quan trọng được tích lũy sau nhiều thập niên là hồn tồn khơng đơn giản. Điều này đã dẫn đến yêu cầu mở rộng để nâng cao độ an tồn của thuật tốn, chẳng hạn như tăng kích thước khĩa và kích thước khối được xử lý. Các phiên bản mở rộng 256/384/512-bit và phiên bản mở rộng 512/768/1024-bit của thuật tốn Rijndael được trình bày dưới đây được chúng tơi xây dựng trên cùng cơ sở lý thuyết của thuật tốn nguyên thủy và cĩ khả năng xử lý các khĩa và khối dữ liệu lớn hơn nhiều lần so với phiên bản gốc. 4.2 Phiên bản mở rộng 256/384/512-bit Trong thuật tốn mở rộng 256/384/512-bit của phương pháp Rijndael, mỗi từ gồm cĩ Nw=8 byte. Mỗi trạng thái cĩ thể được biểu diễn dưới dạng một ma trận gồm 8 dịng và Nb cột với Nb bằng với độ dài của khối chia cho 64. Khĩa chính cũng được biểu diễn dưới dạng một ma trận gồm 8 dịng và Nk cột với Nk bằng với độ dài của khĩa chia cho 64. Ma trận biểu diễn 1 trạng thái hay khĩa cĩ thể được khảo sát dưới dạng mảng 1 chiều các từ (Nw byte), mỗi phần tử tương ứng với 1 cột của ma trận. Số lượng chu kỳ, ký hiệu là Nr, cĩ giá trị là Nr = max{Nb, Nk}+ 6 (4.1) 78
Phương pháp Rijndael mở rộng 4.2.1 Quy trình mã hĩa Trong quy trình mã hĩa vẫn sử dụng 4 phép biến đổi chính như đã trình bày trong thuật tốn mã hĩa Rijndael cơ bản: 1. AddRoundKey: cộng ( ⊕ ) mã khĩa của chu kỳ vào trạng thái hiện hành. Độ dài của mã khĩa của chu kỳ bằng với kích thước của trạng thái. 2. SubBytes: thay thế phi tuyến mỗi byte trong trạng thái hiện hành thơng qua bảng thay thế (S-box). 3. MixColumns: trộn thơng tin của từng cột trong trạng thái hiện hành. Mỗi cột được xử lý độc lập. 4. ShiftRows: dịch chuyển xoay vịng từng dịng của trạng thái hiện hành với di số khác nhau. Mỗi phép biến đổi thao tác trên trạng thái hiện hành S. Kết quả S’ của mỗi phép biến đổi sẽ trở thành đầu vào của phép biến đổi kế tiếp trong quy trình mã hĩa. Trước tiên, tồn bộ dữ liệu đầu vào được chép vào mảng trạng thái hiện hành. Sau khi thực hiện thao tác cộng mã khĩa đầu tiên, mảng trạng thái sẽ được trải qua Nr = 10, 12 hay 14 chu kỳ biến đổi (tùy thuộc vào độ dài của mã khĩa chính cũng như độ dài của khối được xử lý). Nr − 1 chu kỳ đầu tiên là các chu kỳ biến đổi bình thường và hồn tồn tương tự nhau, riêng chu kỳ biến đổi cuối cùng cĩ sự khác biệt so với Nr −1 chu kỳ trước đĩ. Cuối cùng, nội dung của mảng trạng thái sẽ được chép lại vào mảng chứa dữ liệu đầu ra. 79
Chương 4 Hình 4.1 thể hiện kiến trúc của một chu kỳ biến đổi trong thuật tốn Rijndael mở rộng 256/384/512-bit với Nb = 4. Quy trình mã hĩa Rijndael mở rộng được tĩm tắt lại như sau: 1. Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ mã hĩa. 2. Nr–1 chu kỳ mã hĩa bình thường: mỗi chu kỳ bao gồm 4 bước biến đổi liên tiếp nhau: SubBytes, ShiftRows, MixColumns, và AddRoundKey. 3. Thực hiện chu kỳ mã hĩa cuối cùng: trong chu kỳ này thao tác MixColumns được bỏ qua. Hình 4.1. Kiến trúc một chu kỳ biến đổi của thuật tốn Rijndael mở rộng 256/384/512-bit với Nb = 4 Trong thuật tốn dưới đây, mảng w[] chứa bảng mã khĩa mở rộng; mảng in[] và out[] lần lượt chứa dữ liệu vào và kết quả ra của thuật tốn mã hĩa. 80
Phương pháp Rijndael mở rộng Cipher(byte in[8 * Nb], byte out[8 * Nb], word w[Nb * (Nr + 1)]) begin byte state[8,Nb] state = in AddRoundKey(state, w) // Xem phần 4.2.1.4 for round = 1 to Nr – 1 SubBytes(state) // Xem phần 4.2.1.1 ShiftRows(state) // Xem phần 4.2.1.2 MixColumns(state) // Xem phần 4.2.1.3 AddRoundKey(state, w + round * Nb) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w + Nr * Nb) out = state end 4.2.1.1 Phép biến đổi SubBytes Thao tác biến đổi SubBytes là phép thay thế các byte phi tuyến và tác động một cách độc lập lên từng byte trong trạng thái hiện hành. Bảng thay thế (S-box) cĩ tính khả nghịch và quá trình thay thế 1 byte x dựa vào S-box bao gồm hai bước: −1 8 −1 1. Xác định phần tử nghịch đảo x ∈ GF(2 ). Quy ước {00} = {00} 81
Chương 4 2. Áp dụng phép biến đổi affine (trên GF(2)) đối với x−1 (giả sử x−1 cĩ biểu diễn nhị phân là {}x7 x6 x5 x4 x3 x2 x1x0 ): yi = xi ⊕ x(i+4)mod8 ⊕ x(i+5)mod8 ⊕ x(i+6) mod8 ⊕ x(i+7) mod8 ⊕ ci (4.2) với ci là bit thứ i của {63}, 0 ≤ i ≤ 7. Phép biến đổi SubBytes được thể hiện dưới dạng mã giả: SubBytes(byte state[8,Nb]) begin for r = 0 to 7 for c = 0 to Nb - 1 state[r,c] = Sbox[state[r,c]] end for end for end Bảng D.2 thể hiện bảng thay thế nghịch đảo được sử dụng trong phép biến đổi SubBytes. 4.2.1.2 Phép biến đổi ShiftRows Trong thao tác biến đổi ShiftRows, mỗi dịng của trạng thái hiện hành được dịch chuyển xoay vịng với độ dời khác nhau. Byte Sr,c tại dịng r cột c sẽ dịch chuyển đến cột (c - shift(r, Nb)) mod Nb hay: ' sr,c = sr,()c+shift ()r,Nb mod Nb với 0 < r < 8 và 0 ≤ c < Nb (4.3) với shift()r, Nb = r mod Nb (4.4) 82
Phương pháp Rijndael mở rộng Phép biến đổi ShiftRows được thể hiện dưới dạng mã giả: ShiftRows(byte state[8,Nb]) begin byte t[Nb] for r = 1 to 7 for c = 0 to Nb - 1 t[c] = state[r, (c + shift[r,Nb]) mod Nb] end for for c = 0 to Nb – 1 state[r,c] = t[c] end for end for end 4.2.1.3 Phép biến đổi MixColumns Trong thao tác biến đổi MixColumns, mỗi cột của trạng thái hiện hành được biểu diễn dưới dạng đa thức s(x) cĩ các hệ số trên GF(28). Thực hiện phép nhân: 7 a x = a xi 8 s'(x) = a(x)⊗ s(x) với () ∑ i , ai ∈GF(2 ) (4.5) i=0 ⎡α 0 α 7 α 6 α 5 α 4 α 3 α 2 α1 ⎤ ⎢ ⎥ ⎢α1 α 0 α 7 α 6 α 5 α 4 α 3 α 2 ⎥ ⎢α 2 α1 α 0 α 7 α 6 α 5 α 4 α 3 ⎥ ⎢ ⎥ α α α α α α α α Đặt M = ⎢ 3 2 1 0 7 6 5 4 ⎥ (4.6) a ⎢α α α α α α α α ⎥ ⎢ 4 3 2 1 0 7 6 5 ⎥ ⎢α 5 α 4 α 3 α 2 α1 α 0 α 7 α 6 ⎥ ⎢α α α α α α α α ⎥ ⎢ 6 5 4 3 2 1 0 7 ⎥ ⎣⎢α 7 α 6 α 5 α 4 α3 α 2 α1 α 0 ⎦⎥ 83
Chương 4 ⎡s'0,c ⎤ ⎡s0,c ⎤ ⎢ ⎥ ⎢ ⎥ ⎢s'1,c ⎥ ⎢s1,c ⎥ ⎢s'2,c ⎥ ⎢s2,c ⎥ ⎢ ⎥ ⎢ ⎥ s' s Ta cĩ: ⎢ 3,c ⎥ = M ⎢ 3,c ⎥ , 0≤ c≤ Nb (4.7) ⎢s' ⎥ a ⎢s ⎥ ⎢ 4,c ⎥ ⎢ 4,c ⎥ ⎢s'5,c ⎥ ⎢s5,c ⎥ ⎢s' ⎥ ⎢s ⎥ ⎢ 6,c ⎥ ⎢ 6,c ⎥ ⎣⎢s'7,c ⎦⎥ ⎣⎢s7,c ⎦⎥ Chúng ta cĩ nhiều khả năng chọn lựa đa thức a(x) khác nhau mà vẫn đảm bảo tính hiệu quả và độ an tồn của thuật tốn. Để đảm bảo các tính chất an tồn của mình, các hệ số của ma trận này phải thỏa các tính chất sau: 1. Khả nghịch. 2. Tuyến tính trên GF(2). 3. Các phần tử ma trận (các hệ số) cĩ giá trị càng nhỏ càng tốt. 4. Khả năng chống lại các tấn cơng của thuật tốn (xem 4.4 - Phân tích mật mã vi phân và phân tích mật mã tuyến tính) Đoạn mã chương trình dưới đây thể hiện thao tác biến đổi MixColumns với đa thức được trình bày trong cơng thức (2.6). Trong đoạn chương trình này, hàm 8 FFmul(x,y) thực hiện phép nhân (trên trường GF(2 )) hai phần tử x và y với nhau. 84
Phương pháp Rijndael mở rộng MixColumns(byte state[8, Nb]) begin byte t[8] for c = 0 to Nb – 1 for r = 0 to 7 t[r] = state[r,c] end for for r = 0 to 7 state[r,c] = FFmul(0x01, t[r]) xor FFmul(0x05, t[(r + 1) mod 8]) xor FFmul(0x03, t[(r + 2) mod 8]) xor FFmul(0x05, t[(r + 3) mod 8]) xor FFmul(0x04, t[(r + 4) mod 8]) xor FFmul(0x03, t[(r + 5) mod 8]) xor FFmul(0x02, t[(r + 6) mod 8]) xor FFmul(0x02, t[(r + 7) mod 8]) xor end for end for end 4.2.1.4 Thao tác AddRoundKey Mã khĩa của chu kỳ được biểu diễn bằng 1 ma trận gồm 8 dịng và Nb cột. Mỗi cột của trạng thái hiện hành được XOR với cột tương ứng của mã khĩa của chu kỳ đang xét: [s'0,c , s'1,c , s'2,c , s'3,c , s'4,c , s'5,c , s'6,c , s'7,c ] = với 0 ≤ c < Nb, (4.8) [s0,c , s1,c , s2,c , s3,c , s4,c , s5,c , s6,c , s7,c ] ⊕[wround∗Nb+c ] 85
Chương 4 Nhận xét: Thao tác biến đổi ngược của AddRoundKey cũng chính là thao tác AddRoundKey. Trong đoạn chương trình dưới đây, hàm xbyte(r, w) thực hiện việc lấy byte thứ r trong từ w. AddRoundKey(byte state[8,Nb], word rk[]) // rk = w + round * Nb begin for c = 0 to Nb – 1 for r = 0 to 7 state[r,c] = state[r,c] xor xbyte(r, rk[c]) end for end for end 4.2.2 Phát sinh khĩa của mỗi chu kỳ Quy trình phát sinh khĩa cho mỗi chu kỳ bao gồm hai giai đoạn: 1. Mở rộng khĩa chính thành bảng mã khĩa mở rộng, 2. Chọn khĩa cho mỗi chu kỳ từ bảng mã khĩa mở rộng. 4.2.2.1 Xây dựng bảng khĩa mở rộng Bảng khĩa mở rộng là mảng 1 chiều chứa các từ (cĩ độ dài 8 byte), được ký hiệu là w[Nb*(Nr + 1)]. Hàm phát sinh bảng khĩa mở rộng phụ thuộc vào giá trị Nk, tức là phụ thuộc vào độ dài của mã khĩa chính. 86
Phương pháp Rijndael mở rộng Hàm SubWord(W) thay thế (sử dụng S-box) từng byte thành phần của một từ (cĩ độ dài 8 byte). Hàm RotWord(W) thực hiện việc dịch chuyển xoay vịng 8 byte thành phần (b0, b1, b 2, b 3, b 4, b 5, b 6, b7) của từ được đưa vào. Kết quả trả về của hàm RotWord là 1 từ gồm 8 byte thành phần là (b1, b 2, b 3, b 4, b 5, b 6, b7, b0). KeyExpansion(byte key[8 * Nk], word w[Nb * (Nr + 1)], Nk) begin i = 0 while (i < Nk) w[i]=word[ key[8*i] , key[8*i+1], key[8*i+2], key[8*i+3], key[8*i+4], key[8*i+5], key[8*i+6], key[8*i+7]] i = i + 1 end while i = Nk while (i < Nb * (Nr + 1)) word temp = w[i - 1] if (i mod Nk = 0) then temp = SubWord(RotWord(temp)) xor Rcon[i / Nk] else if ((Nk = 8) and (i mod Nk = 4)) then temp = SubWord(temp) end if end if w[i] = w[i - Nk] xor temp i = i + 1 end while end Các hằng số của mỗi chu kỳ hồn tồn độc lập với giá trị Nk và được xác định bằng Rcon[i] = (xi−1, 0, 0, 0, 0, 0, 0, 0), i ≥ 1 87
Chương 4 4.2.2.2 Xác định khĩa của chu kỳ Mã khĩa của chu kỳ thứ i được xác định bao gồm các từ (8 byte) cĩ chỉ số từ Nb* i đến Nb*( i +− 1) 1 của bảng mã khĩa mở rộng. Như vậy, mã khĩa của chu kỳ thứ i bao gồm các phần tử wNb[*] i ,[wNb * i+ 1], , wNb [ *( i+− 1) 1] . w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 w11 w12 w13 w14 w15 w16 w17 Mã khóa chu kỳ 0 Mã khóa chu kỳ 1 Mã khóa chu kỳ 2 Hình 4.2. Bảng mã khĩa mở rộng và cách xác định mã khĩa của chu kỳ (với Nb = 6 và Nk = 4) 4.2.3 Quy trình giải mã Quy trình giải mã được thực hiện qua các giai đoạn sau: 1. Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ giải mã. 2. Nr – 1 chu kỳ giải mã bình thường: mỗi chu kỳ bao gồm bốn bước biến đổi liên tiếp nhau: InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns. 3. Thực hiện chu kỳ giải mã cuối cùng. Trong chu kỳ này, thao tác InvMixColumns được bỏ qua. 88
Phương pháp Rijndael mở rộng InvCipher( byte in[8 * Nb], byte out[8 * Nb], word w[Nb * (Nr + 1)]) begin byte state[8,Nb] state = in AddRoundKey(state, w + Nr * Nb) // Xem phần 0 for round = Nr - 1 downto 1 InvShiftRows(state) // Xem phần 4.2.3.1 InvSubBytes(state) // Xem phần 0 AddRoundKey(state, w + round * Nb) InvMixColumns(state) // Xem phần 0 end for InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w) out = state end 4.2.3.1 Phép biến đổi InvShiftRows InvShiftRows là biến đổi ngược của biến đổi ShiftRows. Mỗi dịng của trạng thái được dịch chuyển xoay vịng theo chiều ngược với biến đổi ShiftRows với độ dời Nb–shift (r, Nb) khác nhau. Các byte ở cuối dịng được đưa vịng lên đầu dịng trong khi các byte cịn lại cĩ khuynh hướng di chuyển về cuối dịng. ' sr,(c+shift(r,Nb))mod Nb = sr,c với 0 < r < 8 và 0 ≤ c < Nb (4.9) 89
Chương 4 InvShiftRows(byte state[8,Nb]) begin byte t[Nb] for r = 1 to 7 for c = 0 to Nb - 1 t[(c + shift[r,Nb]) mod Nb] = state[r,c] end for for c = 0 to Nb – 1 state[r,c] = t[c] end for end for end 4.2.3.2 Phép biến đổi InvSubBytes Phép biến đổi ngược của thao tác SubBytes, ký hiệu là InvSubBytes, sử dụng bảng thay thế nghịch đảo của S-box trên GF(28) được ký hiệu là S-box-1. Quá trình thay thế 1 byte y dựa vào S-box-1 bao gồm hai bước sau: 1. Áp dụng phép biến đổi affine (trên GF(2)) sau đối với y (cĩ biểu diễn nhị phân là {}y7 y6 y5 y4 y3 y2 y1 y0 ): xi = y()i+2 mod 8 ⊕ y(i+5) mod 8 ⊕ y(i+7) mod 8 ⊕ di , với di là bit thứ i của giá trị {05},0 ≤ i ≤ 7. (4.10) Đây chính là phép biến đổi affine ngược của phép biến đổi affine ở bước 1 của S-box. 90
Phương pháp Rijndael mở rộng 8 2. Gọi x là phần tử thuộc GF(2 ) cĩ biểu diễn nhị phân là {}x7 x6 x5 x4 x3 x2 x1x0 . -1 8 -1 Xác định phần tử nghịch đảo x ∈ GF(2 ) với quy ước {00} = {00} Bảng D.2 thể hiện bảng thay thế nghịch đảo được sử dụng trong phép biến đổi InvSubBytes InvSubBytes(byte state[8,Nb]) begin for r = 0 to 7 for c = 0 to Nb - 1 state[r,c] = InvSbox[state[r,c]] end for end for end 4.2.3.3 Phép biến đổi InvMixColumns InvMixColumns là biến đổi ngược của phép biến đổi MixColumns. Mỗi cột của trạng thái hiện hành được xem như đa thức s(x) bậc 8 cĩ các hệ số thuộc GF(28) và được nhân với đa thức a−1(x) là nghịch đảo của đa thức a(x) (modulo 8 M (x) = x + 1) được sử dụng trong phép biến đổi MixColumns. Với a(x) = {05}x7 + {03}x6 + {05}x5 + {04}x4+ {03}x3 + {02}x2 + {02}x + {01} (4.11) ta cĩ: a-1(x) = {b3}x7 + {39}x6 + {9a}x5 + {a1}x4+ {db}x3 + {54}x2 + {46}x + {2a} (4.12) 91
Chương 4 Phép nhân s′(x) = a−1(x) ⊗ s(x) được biểu diễn dưới dạng ma trận như sau: ⎡s'0,c ⎤ ⎡s0,c ⎤ ⎢ ⎥ ⎢ ⎥ ⎢s'1,c ⎥ ⎢s1,c ⎥ ⎢s'2,c ⎥ ⎢s2,c ⎥ ⎢ ⎥ ⎢ ⎥ ⎢s'3,c ⎥ ⎢s3,c ⎥ = M −1 , 0≤ c≤ Nb (4.13) ⎢s' ⎥ a ⎢s ⎥ ⎢ 4,c ⎥ ⎢ 4,c ⎥ ⎢s'5,c ⎥ ⎢s5,c ⎥ ⎢s' ⎥ ⎢s ⎥ ⎢ 6,c ⎥ ⎢ 6,c ⎥ ⎣⎢s'7,c ⎦⎥ ⎣⎢s7,c ⎦⎥ Đoạn chương trình sau thể hiện thao tác InvMixColumns sử dụng đa thức a-1(x) trong cơng thức (4.12). InvMixColumns(byte block[8,Nb]) begin byte t[8] for c = 0 to Nb – 1 for r = 0 to 7 t[r] = block[r,c] end for for r = 0 to 7 block[r,c] = FFmul(0x2a, t[r]) xor FFmul(0xb3, t[(r + 1) mod 8]) xor FFmul(0x39, t[(r + 2) mod 8]) xor FFmul(0x9a, t[(r + 3) mod 8]) xor FFmul(0xa1, t[(r + 4) mod 8]) xor FFmul(0xdb, t[(r + 5) mod 8]) xor FFmul(0x54, t[(r + 6) mod 8]) xor 92
Phương pháp Rijndael mở rộng FFmul(0x46, t[(r + 7) mod 8]) end for end for end 4.2.4 Quy trình giải mã tương đương Quy trình giải mã Rijndael cĩ thể được thực hiện theo với trình tự các phép biến đổi ngược hồn tồn tương đương với quy trình mã hĩa (xem chứng minh trong phần 3.6.4-Quy trình giải mã tương đương). EqInvCipher(byte in[8*Nb], byte out[8*Nb], word dw[Nb*(Nr + 1)]) begin byte state[8,Nb] state = in AddRoundKey(state, dw + Nr * Nb) for round = Nr - 1 downto 1 InvSubBytes(state) InvShiftRows(state) InvMixColumns(state) AddRoundKey(state, dw + round * Nb) end for InvSubBytes(state) InvShiftRows(state) AddRoundKey(state, dw) out = state end 93
Chương 4 Bảng mã khĩa mở rộng dw được xây dựng từ bảng mã khĩa w bằng cách áp dụng phép biến đổi InvMixColumns lên từng từ (8 byte) trong w, ngoại trừ Nb từ đầu tiên và cuối cùng của w. for i = 0 to (Nr + 1) * Nb – 1 dw[i] = w[i] end for for rnd = 1 to Nr – 1 InvMixColumns(dw + rnd * Nb) end for 4.3 Phiên bản mở rộng 512/768/1024-bit Thuật tốn mở rộng 512/768/1024-bit dựa trên phương pháp Rijndael được xây dựng tương tự như thuật tốn mở rộng 256/384/512-bit: • Trong thuật tốn 512/768/1024 bit, mỗi từ cĩ kích thước Nw=16 byte. • Đa thức được chọn trong thao tác MixColumns cĩ bậc 15 và phải cĩ hệ số Branch Number là 17. Chúng ta cĩ thể chọn đa thức sau để minh họa: a(x) = {07}x15 +{09}x14+{04}x13+{09}x12+{08}x11+{03}x10+{02}x9+{08}x8 + {06}x7+{04}x6+{04}x5+{01}x4+{08}x3+{03}x2+{06}x+{05} (4.14) Và đa thức nghịch đảo a-1(x) tương ứng là a-1(x)={1e}x15+{bc}x14+{55}x13+{8d}x12+{1a}x11+{37}x10+{97}x9+{10}x8+ {f0}x7+{d5}x6+{01}x5+{ad}x4+{59}x3+{82}x2+{59}x+{3a} (4.15) Chi tiết về thuật tốn được trình bày trong [12], [16]. 94
Phương pháp Rijndael mở rộng 4.4 Phân tích mật mã vi phân và phân tích mật mã tuyến tính 4.4.1 Phân tích mật mã vi phân Phương pháp phân tích mật mã vi phân (Differential Cryptanalysis) được Eli Biham và Adi Shamir trình bày trong [3]. Phương pháp vi phân chỉ cĩ thể được áp dụng nếu cĩ thể dự đốn được sự lan truyền những khác biệt trong các mẫu đầu vào qua hầu hết các chu kỳ biến đổi với số truyền (prop ratio [10]) lớn hơn đáng kể so với giá trị 21-n với n là độ dài khối (tính bằng bit). Như vậy, để đảm bảo an tồn cho một phương pháp mã hĩa, điều kiện cần thiết là khơng tồn tại vết vi phân (differential trail) lan truyền qua hầu hết các chu kỳ cĩ số truyền lớn hơn đáng kể so với giá trị 21–n. Đối với phương pháp Rijndael, các tác giả đã chứng minh khơng tồn tại vết vi phân lan truyền qua bốn chu kỳ cĩ số truyền lớn hơn 2-30(Nb+1) [8] với Nb = n Nw = n 32 . Như vậy, khơng tồn tại vết vi phân lan truyền qua tám chu kỳ cĩ số truyền lớn hơn 2-60(Nb+1). Điều này đủ để đảm bảo tính an tồn cho thuật tốn Rijndael. 95
Chương 4 Phần chứng minh được trình bày trong 4.4.5-Trọng số vết vi phân và vết tuyến tính cho chúng ta các kết luận sau: • Đối với thuật tốn mở rộng 256/384/512-bit, khơng tồn tại vết vi phân lan truyền qua bốn chu kỳ cĩ số truyền lớn hơn 2-54(Nb+1) với Nb = n Nw = n 64 . Như vậy, khơng tồn tại vết vi phân lan truyền qua tám chu kỳ cĩ số truyền lớn hơn 2-108(Nb+1). • Đối với thuật tốn mở rộng 512/768/1024-bit, khơng tồn tại vết vi phân lan truyền qua bốn chu kỳ cĩ số truyền lớn hơn 2-102(Nb+1) với Nb = n Nw = n 128 . Như vậy, khơng tồn tại vết vi phân lan truyền qua tám chu kỳ cĩ số truyền lớn hơn 2-204(Nb+1). Các kết luận trên đảm bảo tính an tồn cho thuật tốn mở rộng 256/384/512 bit và 512/768/1024-bit đối với phương pháp phân tích mật mã vi phân. 4.4.2 Phân tích mật mã tuyến tính Phương pháp phân tích mật mã tuyến tính (Linear Cryptanalysis) được Mitsuru Matsui trình bày trong [32]. Phương pháp tuyến tính chỉ cĩ thể được áp dụng nếu sự tương quan giữa đầu ra với đầu vào của thuật tốn qua hầu hết các chu kỳ cĩ giá trị rất lớn so với 2-n/2. 96
Phương pháp Rijndael mở rộng Như vậy, để đảm bảo an tồn cho một phương pháp mã hĩa, điều kiện cần thiết là khơng tồn tại vết tuyến tính (linear trail [10]) lan truyền qua hầu hết các chu kỳ cĩ số truyền lớn hơn đáng kể so với giá trị 2–n/2. Đối với phương pháp Rijndael, các tác giả đã chứng minh được rằng khơng tồn tại vết tuyến tính nào lan truyền qua bốn chu kỳ với độ tương quan lớn hơn 2-15(Nb + 1) [8]. Như vậy, khơng tồn tại vết tuyến tính nào lan truyền qua tám chu kỳ với độ tương quan lớn hơn 2-39(Nb+1). Điều này đủ để đảm bảo tính an tồn cho thuật tốn Rijndael. Phần chứng minh được trình bày trong 4.4.4-Sự lan truyền mẫu cho chúng ta các kết luận sau: • Đối với thuật tốn mở rộng 256/384/512-bit, khơng tồn tại vết tuyến tính lan truyền qua bốn chu kỳ với độ tương quan lớn hơn 2-27(Nb+1). Như vậy, khơng tồn tại vết tuyến tính nào lan truyền qua tám chu kỳ với độ tương quan lớn hơn 2-54(Nb+1). • Đối với thuật tốn mở rộng 512/768/1024-bit, khơng tồn tại vết tuyến tính lan truyền qua bốn chu kỳ với độ tương quan lớn hơn 2-51(Nb+1). Như vậy, khơng tồn tại vết tuyến tính nào lan truyền qua tám chu kỳ với độ tương quan lớn hơn 2-102(Nb+1). Các kết luận trên đảm bảo tính an tồn cho thuật tốn mở rộng 256/384/512 bit và 512/768/1024-bit đối với phương pháp phân tích mật mã tuyến tính. 97
Chương 4 4.4.3 Branch Number Xét phép biến đổi tuyến tính F trên vector các byte. Một byte khác 0 được gọi là byte hoạt động (active). Trọng số byte của một vector a, ký hiệu là W(a), là số lượng byte hoạt động trong vector này. Định nghĩa 4.1: Branch Number B của phép biến đổi tuyến tính F là độ đo khả năng khuếch tán của F, được định nghĩa như sau: B(F) = mina≠0 (W(a) + W(F(a))) (4.16) Nhận xét: Branch Number càng lớn thì khả năng khuếch tán thơng tin của F càng mạnh, giúp cho hệ thống SPN càng trở nên an tồn hơn. Trong phép biến đổi MixColumns, nếu trạng thái ban đầu cĩ 1 byte hoạt động thì trạng thái kết quả nhận được sau khi áp dụng MixColumns cĩ tối đa Nw byte hoạt động. Do đĩ, ta cĩ: B(MixColumns) ≤ Nw + 1 (4.17) với Nw lần lượt nhận giá trị là 4, 8 và 16 trong thuật tốn Rijndael, thuật tốn mở rộng 256/384/512 bit và thuật tốn mở rộng 512/768/1024 bit. Như vậy, để đạt được mức độ khuếch tán thơng tin cao nhất, chúng ta cần phải chọn phép biến đổi MixColumns sao cho hệ số Branch Number đạt được giá trị cực đại là Nw + 1 . Nĩi cách khác, Branch Number của MixColumns trong thuật tốn Rijndael, thuật tốn mở rộng 256/384/512 bit và thuật tốn mở rộng 512/768/1024 bit phải đạt được giá trị lần lượt là 5, 9 và 17. Khi đĩ, quan hệ tuyến tính giữa các bit trong trạng thái đầu vào và đầu ra của MixColumns liên quan đến các Nw + 1 byte khác nhau trên cùng một cột. 98