Bài giảng An toàn và bảo mật thông tin - Trần Minh Văn (Phần 2)

85 trang phuongnguyen 3390

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng An toàn và bảo mật thông tin - Trần Minh Văn (Phần 2)", để 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:

an_toan_va_bao_mat_thong_tin_tran_minh_van_phan_2.pdf

Nội dung text: Bài giảng An toàn và bảo mật thông tin - Trần Minh Văn (Phần 2)

CHƢƠNG 6. GIAO THỨC Trong các chương trước, chúng ta đã tìm hiểu về cách thức thực hiện tính bảo mật, tính chứng thực và tính không thoái thác của các phương pháp mã hóa đối xứng và mã hóa khóa công khai. Chương này trước tiên tìm hiểu cơ chế chống lại hình thức tấn công phát lại thông điệp (replay attack). Tiếp theo trình bày về các giao thức bảo mật, là các nguyên tắc áp dụng các kỹ thuật mã hóa nhằm đảm bảo việc truyền dữ liệu là an toàn trước những hình thức tấn công đã được đề cập trong chương một. Chương này trình bày các giao thức dưới dạng nguyên tắc lý thuyết, chương tiếp theo trình bày một số giao thức ứng dụng thực tiễn. 6.1 Phát lại thông điệp (Replay Attack) Trong hình thức tấn công phát lại thông điệp, Trudy chặn thông điệp của Alice gửi cho Bob, và sau đó một thời gian gửi lại thông điệp này cho Bob. Như vậy Bob sẽ nghĩ rằng Alice gửi thông điệp hai lần khác nhau. Tuy nhiên thực sự thì Alice chỉ gửi một lần. Chỉ sử dụng mã hóa đối xứng và mã hóa khóa công khai thì không thể ngăn cản hình thức tấn công này. Để chống lại reply attack có 3 phương pháp: 1) Dùng số định danh: trong mỗi thông điệp gửi cho Bob, Alice nhúng vào đó một con số định danh thông điệp S. Mỗi thông điệp ứng với một S khác nhau. || là phép nối dãy bít Do đó nếu Trudy phát lại thông điệp, Bob biết được hai thông điệp có cùng số định danh và loại bỏ thông điệp thứ hai. Tuy nhiên, phương pháp này có hạn chế là Bob phải lưu trữ số định danh của Alice để có cơ sở so sánh. Do đó phương pháp này thường chỉ sử dụng cho một phiên làm việc (connection oriented). 2) Dùng timestamp: trong mỗi thông điệp gửi cho Bob, Alice nhúng vào một timestamp T xác định thời điểm gửi. Bob chỉ chấp nhận thông điệp nếu nó đến được Bob trong một giới hạn thời gian nào đó kể từ lúc gửi. Tuy nhiên phương pháp này yêu cầu đồng hồ của Alice và của Bob phải đồng bộ, không được sai lệch đáng kể. Ngoài ra độ trễ của việc truyền tin trên mạng cũng là một trở ngại đối với phương pháp này. 3) Dùng cơ chế challenge/response: để bảo đảm thông điệp từ Alice không phải là replay, Bob gửi 1 số ngẫu nhiên N cho Alice (gọi là nounce). Alice sẽ nhúng N trong thông điệp gửi cho Bob. N Mã hóa đối xứng A C=E(P||N, KAB) B A N Mã hóa khóa công khai A C=E(M||N, KUB) B A 100
Khi Bob giải mã thì sẽ kiểm tra N mà Bob nhận được xem có trùng khớp với N Bob gửi đi không. Như vậy Trudy không thể replay thông điệp E(P||N, KAB) được vì mỗi lần Bob sẽ gửi một số N khác nhau. Tuy nhiên phương pháp này đòi hỏi thêm một bước là Bob phải gửi N trước cho Alice. Vì vậy trong thực tế tùy trường hợp mà người ta sẽ sử dụng một trong 3 kỹ thuật trên cho hợp lý. 6.2 Giao thức bảo mật Trong thực tế, khi hai người bất kỳ chưa biết trước muốn trao đổi dữ liệu với nhau, họ phải xác định người kia là ai, sau đó thống nhất với nhau là phải dùng phương pháp mã hóa nào, khóa là gì, Để làm được điều đó họ phải tiến hành thông qua giao thức bảo mật. Như vậy có thể định nghĩa giao thức bảo mật là các quy định mà nếu hai cá thể tuân theo các quy định đó, thì họ có thể trao đổi dữ liệu với nhau một cách an toàn bảo mật. Một giao thức bảo mật thường nhằm xác định các yếu tố sau: . Định danh hai cá thể trao đổi dữ liệu, chống replay attack. . Trao đổi khóa phiên bí mật để mã hóa dữ liệu. Vì mã đối xứng thực hiện nhanh hơn mã hóa công khai nên ngày nay người ta dùng mã đối xứng để mã hóa dữ liệu, còn việc trao đổi khóa phiên bí mật thì có thể dùng mã hóa đối xứng hay mã hóa khóa công khai. Trong phần 3.9 hay phần 4.6.2 và 4.7 chúng ta đã xem một số giao thức tập trung vào việc trao đổi khóa phiên. Trong phần này, ta sẽ mở rộng các giao thức trên nhằm định danh cá thể trao đổi dữ liệu và chống replay attack. 6.2.1 Định danh và trao đổi khóa phiên dùng mã hóa đối xứng với KDC Xét lại mô hình phần 3.9 trao đổi khóa phiên KDC 1. REQUEST to B 2. E(KAB, KA)||E(KAB, KB) 4. E(KAB, KB) A B 5. E(P, K ) AB Mô hình trên có thể bị tấn công replay attack. Ví dụ, Trudy có thể replay bước 4 mà B vẫn nghĩ là A gửi và B tiếp tục dùng KAB này làm khóa phiên. Dựa trên cơ sở đó Trudy tiếp tục replay bước 5. (việc replay dữ liệu tại bước 5 sẽ gây ra hậu quả không mong muốn như chúng ta đã đề cập trong chương 1). Needham and Schroeder đã đề xuất sửa đổi mô hình trên như sau: 1) A KDC: IDA||IDB||N1 2) KDC A: E(KS||IDB||N1||E(KS||IDA, KB), KA) // KS là khóa phiên, IDB ể A biết khóa phiên này dùng với B 101
3) A giải mã có được KS và E(KS||IDA, KB) 4) A B: E(KS||IDA, KB) // IDA ể B biết khóa phiên này dùng với A 5) B A: E(N2, KS) 6) A B: E(f(N2), KS) // f là hàm bất kỳ 7) A B: E(P, KS) Tại bước 1, A gửi cho KDC nounce N1 và KDC nhúng N1 vào trong bản rõ ở bước 2. Do đó bước 2 không thể bị replay attack (theo phương pháp challenge/response). Tại bước 5, B gửi cho A giá trị nounce N2, và chờ A gửi lại giá trị f(N2), f là một hàm được chọn trước. Do đó nếu Trudy replay attack tại bước 4 thì Trudy không thể thực hiện bước 6 vì Trudy không có KS để tính N2 và f(N2). Bob nhận biết Trudy là giả mạo và Trudy không thể replay dữ liệu tiếp tại bước 7. Như vậy có thể thấy các bước 4, 5, 6 cũng là một hình thức challenge/response để chống replay attack. Để phòng Trudy replay bước 4 để sử dụng lại một KS cũ. Bob challenge tại bước 5 và yêu cầu được response tại bước 6 xem người gửi có biết KS không (chỉ có Alice mới biết KS) Tuy nhiên giao thức này chưa hoàn toàn chặc chẽ, có một khuyết điểm là nếu sau này Trudy biết được KS và E(KS||IDA, KB) tương ứng thì Trudy có thể replay attack bước 4, sau đó dựa trên KS tính được N2 và phản hồi N2 cho Bob. Như vậy Bob không biết được là Trudy đã mạo danh Alice và tiếp tục dùng khóa phiên KS đã bị lộ này. Do đó giao thức Needham/Schroeder tiếp tục được sửa lại như sau: 1) A B: IDA ||NA 2) B KDC: IDB||NB||E(IDA||NA, KB) 3) KDC A: E(IDB||NA||KS, KA)|| E(IDA|| KS, KB)|| NB 4) A B: E(IDA||KS, KB)|| E(NB, KS) 5) A B: E(P, KS) Trong giao thức trên A gửi NA cho Bob, Bob gửi tiếp cho KDC, KDC nhúng NA vào bản rõ gửi cho A. Do đó nếu A nhận được NA thì có nghĩa là bản mã E(IDB||NA||KS, KA) trong bước 3 không bị replay attack. B gửi NB cho KDC, KDC gửi lại cho A, A gửi lại NB cho B dưới dạng mã hóa. Đo đó nếu B nhận được NB thì có nghĩa E(IDA||KS, KB) trong bước 4 không bị replay attack. Do đó KS mà Alice và Bob nhận được là khóa phiên mới. Trudy không thể replay lại các bản mã E(P, KS) cũ trong các lần trước tại bước 5. 6.2.2 Định danh và trao đổi khóa phiên dùng mã hóa khóa công khai Xét lại mô hình phần 4.6.2 1.CA 2.CB A B 3.E( E(KS , KRA), KUB) 4. E(P, KS) 102
Trong mô hình trên, Trudy có thể replay bước 3 mà B vẫn nghĩ là A gửi và B tiếp tục dùng KS này làm khóa phiên. Dựa trên cơ sở đó Trudy tiếp tục replay bước 4. Ở đây áp dụng một cơ chế challenge/response khác để chống replay như sau: 1. CA 2. CB||NB 3. E(E(S , K ), K ) RA UB A 4. H (KS) B A 5. E(P ||KS) Mô tả: - Bước 1: A gửi chứng chỉ CA cho B. - Bước 2: B gửi chứng chỉ CB và nounce NB cho A. - Bước 3: A chọn một tiền khóa phiên S và tính được khóa phiên KS = H(S||NB). A gửi chứng thực và bảo mật S cho B. B cũng tính khóa phiên KS. - Bước 4: A gửi giá trị hash H(KS) cho B, B kiểm tra giá trị hash này với giá trị hash do B tự tính. Nếu khớp, B biết được rằng bước 3 không thể bị replay attack. Giả sử Trudy replay bước 3 nhưng không biết S, vậy Trudy không tính được KS tương ứng với NB mới của Bob, từ đó Trudy cũng không thể tính được H(KS). Do đó Trudy không thể replay bước 4 mà không bị Bob phát hiện. - Bước 5: A và B tiến hành trao đổi dữ liệu. 6.3 Câu hỏi ôn tập 1) Tấn công phát lại thông điệp là gì? Nêu tác hại của thao tác tấn công này và so sánh với việc sửa đổi thông điệp vào mạo danh. 2) Nêu các phương pháp chống lại tấn công phát lại thông điệp. 3) Nêu các mục đích của giao thức. 6.4 Bài tập Xét giao thức sau: 1. IDA 2. CB||NB 3. E(S , KUB) A 4. H(KS) B A 5. E(P||KS) 103
a) B có thể chắc chắn A là người ứng với IDA không? Nếu Trudy mạo danh A sử dụng IDA thì B có phát hiện được không? Giải thích b) Giả sử A có password để định danh với B, B lưu trữ giá trị hash password của A. Hãy sửa giao thức trên để B có thể định danh được A. 104
CHƢƠNG 7. MỘT SỐ ỨNG DỤNG THỰC TIỄN 7.1 Giới thiệu Trong chương này, chúng ta sẽ tìm hiểu việc áp dụng các mô hình lý thuyết trong các chương trước vào một số giao thức thực tiễn. Trước hết là chuẩn chứng thực X.509, là một chuẩn thực tiễn áp dụng trong vấn đề trao đổi khóa công khai mà đã được đề cập trong phần 4.6.1. Tiếp theo sau đó chúng ta sẽ tìm hiểu về giao thức bảo mật web Secure Socker Layer (SSL), giao thức bảo mật mạng cục bộ Keberos. Có thể minh họa các giao thức trên trong mô hình mạng OSI như sau: Application Layer HTTP PGP S/MIME SSL Keberos SMTP Transport Layer TCP/ UDP Network Layer IP/IPSec Link Layer Physical Layer Trong mô hình trên có thể thấy việc ứng dụng bảo mật vào truyền thông trên mạng có thể được tiến hành tại các tầng khác nhau như tầng mạng hay tầng ứng dụng. Trong giao thức TCP/IP, người ta có thể thay giao thức IP thường bằng giao thức IP Security để việc bảo mật được thực hiện tại tầng mạng. Do đó các ứng dụng khác trong tầng ứng dụng sẽ không cần quan tâm đến bảo mật nữa, mọi việc bảo mật đã được IPSec thực hiện. Chi tiết về IPSec được trình bày trong [3]. Các giao thức SSL, Keberos, PGP hay S/MIME được thực hiện trong tầng ứng dụng. Vì vậy mỗi giao thức phải thực hiện cơ chế bảo mật cho riêng mình. 7.2 Chứng thực X.509 7.2.1 Cấu trúc chứng thực Chứng thực X.509 là một áp dụng dựa trên lý thuyết về chữ ký điện tử trong phần 5.4. Sơ đồ nguyên tắc để sinh ra chứng thực X.509 như sau: Tính Hash Chứng chỉ chưa được ký, gồm ID và public H key của người sử dụng Mã hóa bằng KRCA E khóa riêng của CA để tạo chữ ký Chứng chỉ đã được ký bởi CA, người sử dụng có thể kiểm tra bằng khóa công khai của CA Certificate = ID||KU||E(H(ID, KU), KRCA) Hình 7-1. Sơ đồ tạo chứng chỉ X.509 105
Cấu trúc một chứng chỉ X.509 gồm có các thành phần sau: Version Version 3 Serial Number 05:A0:4C Certificate Signature Algorithm PKCS #1 SHA-1 With RSA Encryption Issuer Name OU = Equifax Secure Certificate Authority; O = Equifax Validity (Not Before, Not After) 04/01/2006 17:09:06 PM GMT - 04/01/2011 17:09:06 PM GMT 1 Subject CN= login.yahoo.com; OU= Yahoo; O= Yahoo! Inc. ersion Subject Public Key Algorithm PKCS #1 RSA Encryption 2 v 3 Subject Public Key 30 81 89 02 81 81 00 b5 6c 4f ee ef 1b 04 5d be ersion v Issuer Unique Identifie ersion v Subject Unique Identifier Extension for version 3 all Certificate Signature Algorithm PKCS #1 SHA-1 With RSA Encryption version Certificate Signature Value 50 25 65 10 43 e1 74 83 2f 8f 9c 9e dc 74 64 4e Hình 7-2. Cấu trúc và ví dụ một chứng chỉ X.509 Mục đích của các thành phần trên là: Version: phiên bản X.509 của chứng chỉ này, có 3 phiên bản là 1, 2 và 3. Serial Number: số serial của chứng chỉ này do trung tâm chứng thực CA ban hành. Certificate Signature Algorithm: thuật toán ký chứng chỉ, gồm loại hàm Hash và phương pháp mã hóa khóa công khai. Issuer name: Tên của trung tâm chứng thực CA (CN: common name, O: organization, OU: organization unit). Validity: thời gian hiệu lực của chứng chỉ. Subject: tên chủ sở hữu chứng chỉ, cũng gồm có CN, O, OU, Subject Public Key Algorithm: thuật toán mã hóa khóa công khai mà tương ứng với khóa công khai trong chứng chỉ. Subject Public Key: khóa công khai trong chứng chỉ, tức khóa công khai của chủ sở hữu. Đối với RSA thì thuộc tính này lưu giữ giá trị Modulus và Exponent nối tiếp nhau (N và e). Issuer Unique Identifier, Subject Unique Identifier: dành cho version 2, ít được sử dụng. Extension: dành cho version 3. Certificate Signature Algorithm: thuật toán ký chứng chỉ, giống mục thứ 3. Certificate Signature Value: giá trị của chữ ký. Đối với version 3 phần Extension có thể gồm các thông tin sau: Authority key identifier: Một con số dùng để định danh trung tâm chứng thực. Thuộc tính Issuer Name cung cấp tên trung tâm chứng thực dưới dạng text, điều này có thể gây nhầm lẫn. Subject key identifier: Một con số dùng để định danh người sử dụng được chứng thực. Tương tự như Issuer Name, thuộc tính Subject cũng cung cấp tên 106
người dưới dạng text, điều này có thể gây nhầm lẫn. Ngoài ra việc dùng một con số định danh cho phép một người sử dụng có thể có nhiều chứng chỉ khác nhau. Key Usage: mục đích sử dụng của chứng chỉ. Mỗi chứng chỉ có thể có một hoặc nhiều mục đích sử dụng như: mã hóa dữ liệu, mã hóa khóa, chữ ký điện tử, không thoái thác CRL Distribution Point: địa chỉ để lấy danh sách các chứng chỉ đã hết hạn hay bị thu hồi (certificate revocation list). Một chứng chỉ thường được lưu trên một file có phần mở rộng là .cer. Hình 7-3. Xem nội dung một chứng thực trong Firefox 2.0 (dùng trong giao thức SSL) Vì chứng chỉ được ký bằng khóa riêng của CA, nên bảo đảm rằng chữ ký không thể bị làm giả và bất cứ ai tin tưởng vào khóa công khai của CA thì có thể tin tưởng vào chứng chỉ mà CA đó cấp phát. Do đó khóa công khai của CA phải được cung cấp một cách tuyệt đối an toàn đến tay người sử dụng. Trong ví dụ trên chứng thực của Yahoo được cung cấp bởi Equifax Secure. FireFox tin tưởng vào Equifax và khóa công khai của Equifax được tích hợp sẵn trong bộ cài đặt của FireFox. Vì vậy khi duyệt đến trang web của Yahoo, FireFox có được chứng chỉ của Yahoo, vì FireFox tin tưởng vào Equifax nên cũng sẽ tin tưởng vào Yahoo và cho phép người sử dụng duyệt trang web này (xem thêm phần giao thức SSL bên dưới). Trên thế giới hiện nay có nhiều tổ chức cung cấp chứng thực X509 như VeriSign, Equifax, Thawte, SecureNet VeriSign hiện là tổ chức lớn nhất. Verisign cung cấp chứng chỉ X509 theo ba mức độ (class): 107
- Class 1: ID của một đối tượng là email của đối tượng đó. Sau khi đối tượng đăng ký email và public key qua mạng Internet, Verisign gửi email để kiểm tra địa chỉ email hợp lệ và cấp chứng thực. - Class 2: ID là địa chỉ nơi ở của đối tượng, Verisign sẽ gửi confirm qua đường bưu điện để kiểm tra địa chỉ hợp lệ. - Class 3: đối tượng cần có giấy tờ pháp lý để chứng minh tư cách pháp nhân. 7.2.2 Phân cấp chứng thực Trên thế giới không thể chỉ có một trung tâm chứng thực CA duy nhất mà có thể có nhiều trung tâm chứng thực. Những người sử dụng khác nhau có thể đăng ký chứng thực tại các CA khác nhau. Do đó để có thể trao đổi dữ liệu, một người cần phải tin tưởng vào khóa công khai của tất cả các trung tâm chứng thực. Để giảm bớt gánh nặng này, X.509 đề ra cơ chế phân cấp chứng thực. Ví dụ, Alice chỉ tin tưởng vào trung tâm chứng thực X1, còn chứng thực của Bob là do trung tâm chứng thực X2 cung cấp. Nếu Alice không có khóa công khai của X2, thì làm sao Alice có thể kiểm tra được chứng thực của Bob? Biện pháp giải quyết là Alice có thể đọc Authority key identifier (tức ID của X2) trong chứng thực của Bob. Sau đó Alice kiểm tra xem X1 có cấp chứng thực nào cho X2 hay không. Nếu có, Alice có thể tìm thấy được khóa công khai của X2 và tin tưởng vào khóa này (do đã được X1 xác nhận). Từ đó Alice có thể kiểm tra tính xác thực của chứng chỉ của Bob. X1 X2 Alice Bob Việc phân cấp chứng thực này không chỉ giới hạn trong hai trung tâm chứng thực mà có thể thông qua một dãy các trung tâm chứng thực tạo thành một mạng lưới chứng thực (Web of Trust). Hình dưới minh họa một ví dụ thực tế. 108
Hình 7-4. Minh họa mô hình phân cấp chứng thực Trong ví dụ trên chứng thực MSN-Passport của Microsoft được chứng thực bởi “Verisign Class 3 Extended Validation SSL CA”, Firefox không có sẵn khóa công khai của trung tâm này. Tuy nhiên Firefox có khóa công khai của “Verisign Class 3 Public Primary CA”, từ đó FireFox có thể chứng thực trung tâm “Verisign Class 3 Public Primary CA – G5” và qua đó có thể chứng thực được “Verisign Class 3 Extended Validation SSL CA”. 7.2.3 Các định dạng file của chứng chỉ X.509 1) Dạng DER (.cer): nội dung của chứng chỉ X.509 được lưu dưới format DER, một định dạng dữ liệu binary chuẩn cho các môi trường máy tính. 2) Dạng PEM (.pem): là dạng DER và được mã hóa dưới dạng text theo chuẩn Base64. Một file text PEM bắt đầu bằng dòng BEGIN CERTIFICATE và kết thúc bằng dòng END CERTIFICATE 3) Dạng PKCS#7 (.p7c hay .p7b): là một định dạng dữ liệu được mã hóa hay ký. Do đó có đi kèm cả chứng chỉ. 4) Dạng PKCS#10 (.p10 hay .p10): là một định dạng dùng để gửi yêu cầu cấp chứng chỉ X509 đến trung tâm chứng thực. Định dạng này có ID và public key của người yêu cầu. 5) Dạng PKCS#12 (.p12): lưu trữ chứng chỉ X509 và private key tương ứng (có password bảo vệ) trong cùng 1 file. 6) Dạng PFX (.pfx): cũng lưu chứng chỉ X509 và private key theo định dạng của Microsoft. Hình bên dưới là một chứng chỉ của Verisign được cung cấp dưới dạng PEM 109
7.3 Giao thức bảo mật web Secure Socket Layer version 3 - SSLv3 Dữ liệu Web được trao đổi giữa trình duyệt và web server được thực hiện qua giao thức HTTP. Client kết nối với server qua socket của giao thức TCP/IP. HTTP HTTP HTTP Data TCP/IP TCP/IP Socket Hình sau minh họa dữ liệu của giao thức HTTP khi thực hiện tìm kiếm từ “Nha Trang” trong website vn.search.yahoo.com. GET /search?p=Nha+Trang&fcss=on&fr=yfp-t-101&toggle=1&cop=&ei=UTF-8 HTTP/1.1 Host: vn.search.yahoo.com User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.13) Gecko/2009073022 Firefox/3.0.13 (.NET CLR 3.5.30729) Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8 Accept-Language: en-us,en;q=0.5 Accept-Encoding: gzip,deflate Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7 Keep-Alive: 300 Connection: keep-alive Referer: và hình dưới là dữ liệu phản hồi của server yahoo. Dữ liệu này gồm hai phần, phần đầu theo quy định của giao thức HTTP, phần sau là dữ liệu HTML. 110
HTTP/1.1 200 OK Date: Fri, 14 Aug 2009 10:25:49 GMT Cache-Control: private Content-Type: text/html; charset=UTF-8 Transfer-Encoding: chunked Connection: Keep-Alive Content-Encoding: gzip . Giao thức SSL bảo mật dữ liệu trao đổi qua socket. Vì vậy nên có tên gọi là Secure Socket Layer (URL bắt đầu bằng https://). Đây là giao thức bảo mật kết hợp mã hóa khóa công khai và khóa đối xứng như đã trình bày trong phần 4.6.2 trong đó mã hóa RSA được dùng để trao đổi khóa phiên của mã hóa đối xứng. Xét lại mô hình trao đổi khóa phiên trong phần 6.2.2. 1. CA 2. CB||NB 3. E(E(S , KRA), KUB) A 4. H(KS) B A 5. E(P||KS) Mô hình này yêu cầu mỗi người duyệt web (A) và mỗi website (B) đều phải có cặp khóa riêng và khóa công khai. Hay nói cách khác website và người duyệt phải có chứng thực. Điều này sẽ gây khó khăn cho người duyệt web vì phải có chứng chỉ. Đây là yêu cầu cần thiết để đảm bảo tuyệt đối tính chứng thực cho cả hai phía website và người duyệt. Nghĩa là khóa KS phải xuất phát từ một người duyệt A cụ thể nào đó mà website biết, đồng thời khóa KS đến đúng website B chứ không phải là website khác. 111
Tuy nhiên trong thực tế không phải lúc nào cũng cần chứng thực từ phía người sử dụng. Ví dụ, khi bạn mua hàng tại cửa hàng sách Amazon. Amazon không cần biết bạn là ai, chỉ cần bạn có tài khoản để mua hàng (việc bảo mật tài khoản người mua là trách nhiệm của mã hóa đối xứng). Do đó Amazon không cần chứng thực người duyệt web. Vì vậy trong trường hợp này, người duyệt không cần có chứng chỉ. Lúc này mô hình trao đổi khóa là: 1. IDA 2. CB||NB 3. E(S , KUB) A 4. H(KS) B A 5. E(P||KS) Hình 7-5. Sơ đồ trao đổi khóa phiên chỉ cần chứng thực 1 phía Mô hình trên đảm bảo ngoài người duyệt A chỉ có website B là biết được khóa phiên KS, còn A là ai thì website không cần biết. Để chứng thực người sử dụng, website có thể đơn giản lưu password của người sử dụng và chứng thực qua cơ chế login. Cách thức này hiện nay đang được sử dụng phổ biến hơn là phải yêu cầu người sử dụng cung cấp chứng chỉ chứng thực. Giao thức SSL cho phép thực hiện cả hai khả năng trao đổi khóa nói trên. Một phương pháp khác mà SSL cũng sử dụng để trao đổi khóa là phương pháp Diffie-Hellman. SSL có ba dạng Diffie-Hellman. - Fixed Diffie-Hellman: là phương pháp trao đổi khóa Diffie-Hellman mà trong đó các yếu tố công khai (g, t) được chứng thực giống như chứng thực khóa công khai của RSA. Điều này giúp ngăn chặn hình thức tấn công kẻ-đứng-giữa. - Ephemeral Diffie-Hellman: là phương pháp trao đổi khóa Diffie-Hellman được bảo vệ bằng mã hóa khóa công khai RSA. Đây là hình thức Diffie-Hellman an toàn nhất. - Anonymous Diffie-Hellman: Diffie-Hellman thường, do đó có thể bị tấn công theo hình thức kẻ-đứng-giữa. Các phương pháp mã hóa đối xứng mà SSL có thể thực hiện là RC4, RC2, DES, 3DES, IDEA, AES. Hình sau đây minh họa mô hình đơn giản của giao thức SSL. 112
Pha 1: Chọn thuật toán mã hóa Pha 2: Server cung cấp chứng chỉ Pha 3: Trao đổi khóa phiên client Pha 4: Hoàn tất bắt tay server Truyền dữ liệu của giao thức HTTP Do có thể áp dụng nhiều phương pháp mã hóa khác nhau nên đặc tả của giao thức SSL khá phức tạp. Phần tiếp theo sẽ chủ yếu trình bày giao thức SSL version 3 trong trường hợp sử dụng RSA. SSL gồm có hai phần cơ bản là giao thức bắt tay và giao thức truyền dữ liệu. 7.3.1 Giao thức bắt tay - SSL Handshaking Protocol Trước khi tiến hành truyền số liệu, SSL thực hiện giao thức bắt tay để chứng thực website và chứng thực người duyệt web, trao đổi khóa phiên và thống nhất các thuật toán mã hóa được sử dụng. Sơ đồ bắt tay được minh họa trong hình bên dưới. Client Server c lient_hello Phase 1 llo server_he certificate t te_reques certifica Phase 2 llo_done server_he certificate client_exc hange_key Phase 3 certific ate_verify finished finished Phase 4 (đường nét đứt là các thông điệp không bắt buộc, chỉ sử dụng khi cần chứng thực từ phía client) 113
Hình 7-6. Giao thức bắt tay SSL Sơ đồ trên gồm có 10 loại thông điệp và được chia thành 4 pha: 1) Pha 1: thỏa thuận về phương pháp mã hóa được sử dụng. Pha này bắt đầu bằng thông điệp client_hello được gửi từ client đến website, thông điệp này gồm các tham số sau: Version: phiên bản SSL cao nhất mà client sử dụng Random: là một cấu trúc ngẫu nhiên gồm 32 byte SessionID: nếu bằng 0 có nghĩa là client muốn thiết lập một session mới hoàn toàn. Nếu khác 0 nghĩa là client muốn thiết lập một kết nối mới trong session này. Việc dùng session giúp cho client và server giảm các bước thỏa thuận trong quá trình bắt tay. CompressionMethod: phương pháp nén dữ liệu sử dụng trong quá trình truyền dữ liệu CipherSuite: Các phương pháp mã hóa khóa công khai dùng để trao đổi khóa phiên như RSA, Fixed Diffie-Hellman, Ephemeral Diffie-Hellman, Anonymous Diffie-Hellman. Phương pháp nào liệt kê trước thì có được ưu tiên hơn. Ứng với mỗi phương pháp trao đổi khóa là danh sách các loại mã hóa đối xứng được sử dụng. Gồm các tham số sau: - CipherAlgorithm: phương pháp mã hóa đối xứng sử dụng (là một trong các phương pháp mã khối RC2, DES, 3DES, IDEA, AES, Fortezza hay mã dòng RC4) - Hash Algorithm: MD5 hay SHA-1. - CipherType: mã hóa đối xứng là mã khối hay mã dòng. - KeyMaterial: một chuỗi byte được dùng để sinh khóa. - IV Size: kích thước của IV dùng trong mô hình CBC của mã khối. Sau khi nhận được client_hello server sẽ trả lời bằng thông điệp server_hello để xác các thuật toán được sử dụng. 2) Pha 2: chứng thực server và trao đổi khóa của mã hóa công khai. Sau khi đã xác nhận thuật toán mã hóa với client, server tiếp tục thực hiện các thông điệp sau: - Thông điệp certificate: server cung cấp certificate của mình cho client (dưới dạng chứng chỉ X.509) . - Thông điệp certificate_request: trong trường hợp server cần chứng thực người sử dụng, server sẽ gửi thông điệp này để yêu cầu client cung cấp chứng chỉ. - Thông điệp server_hello_done: báo hiệu server đã hoàn tất pha 2. 3) Pha 3: chứng thực client và trao đổi khóa của mã hóa đối xứng - Thông điệp certificate: nếu server yêu cầu certificate, client cung cấp certificate của mình cho server. - Thông điệp client_key_exchange: trong bước này client gửi các thông số cần thiết cho server để tạo khóa bí mật. Ta cũng sẽ chỉ đề cập đến trường hợp RSA. Trong trường hợp này client tạo một giá trị bất kỳ gọi là “tiền khóa chủ” (pre-master secret) có kích thước 48 byte, mã hóa bằng khóa 114
công khai của server. Sau khi có “pre-master secret”, client và server sẽ tính giá trị “khóa chủ” (master-secret) như sau: master_secret = MD5(pre_master_secret || SHA('A' || pre_master_secret ||ClientHello.random || ServerHello.random)) || MD5(pre_master_secret || SHA('BB' || pre_master_secret || ClientHello.random || ServerHello.random)) || MD5(pre_master_secret || SHA('CCC' || pre_master_secret || ClientHello.random || ServerHello.random)) Master_secret cũng có chiều dài là 48 byte (384 bít). Phép toán || là phép nối - Thông điệp certificate_verify: là chữ ký của client trong trường hợp server cần chứng thực client. Client phải dùng khóa riêng để ký chữ ký, do đó server có thể đảm bảo được là không ai khác dùng certificate của client để giả mạo. 4) Pha 4: hoàn tất quá trình bắt tay. Trong pha này client và server gửi thông điệp finished để thông báo hoàn tất quá trình bắt tay lẫn nhau. Tham số của thông điệp này là một giá trị hash để hai bên có thể kiểm tra lẫn nhau. Giá trị hash này kết nối của 2 giá trị hash: MD5(master_secret || pad2 || MD5(handshake_messages || Sender || master_secret || pad1)) SHA(master_secret || pad2 || SHA(handshake_messages || Sender || master_secret || pad1)) Trong đó handshake_messages là tất cả các thông điệp đầu đến trước thông điệp finished này. Sender là mã để phân biệt thông điệp finished này là từ client hay từ server. Đây là cơ chế chống replay attack dùng hàm hash mà chúng ta đã tìm hiểu trong chương 6. Dựa trên giá trị master_secret, client và server sẽ tính các tham số cần thiết cho mã hóa đối xứng như sau: - Hai khóa dành cho việc mã hóa dữ liệu, một khóa dành cho chiều server gửi client và 1 khóa dành cho chiều client và server. - Hai giá trị IV, cũng dành cho server và client tương ứng - Hai khóa dành cho việc tính giá trị MAC, cũng tương ứng cho server và client Tùy theo phương pháp mã hóa đối xứng được sử dụng mà các tham số này có chiều dài khác nhau. Tuy nhiên, chúng được lấy từ dãy bít theo công thức sau: key_block = MD5(master_secret || SHA('A' || master_secret || ServerHello.random || ClientHello.random)) || MD5(master_secret || SHA('BB' || master_secret || ServerHello.random || ClientHello.random)) || MD5(master_secret || SHA('CCC' || master_secret || ServerHello.random ||ClientHello.random)) || . . . 115
Việc dùng các giá trị ClientHello.random và ServerHello.random sẽ làm phức tạp việc phá mã hơn. Đến đây client và server đã hoàn tất quá trình bắt tay trao đổi khóa, sẵn sàng để truyền số liệu theo giao thức truyền số liệu. 7.3.2 Giao thức truyền số liệu - SSL Record Protocol Hình bên dưới minh họa các bước thực hiện trong quá trình truyền số liệu: Dữ liệu Chia nhỏ Nén Tính MAC Mã hóa Thêm SSL header Hình 7-7. Truyền dữ liệu theo khối trong SSL Trong giao thức truyền số liệu, dữ liệu được chia thành các khối có kích thước là 214 byte (16384) Sau đó, dữ liệu này được nén lại. Tuy nhiên hiện nay trong SSL version 3 chưa mô tả cụ thể một phương pháp nén nào nên mặc định xem như là không nén. Bước tiếp theo giá trị MAC của khối dữ liệu nén được tính theo công thức sau: hash(MAC_key || pad_2 ||hash(MAC_key || pad_1 || seq_num ||type ||length || data)) trong đó: - Hàm hash là hàm MD5 hay SHA-1 - MAC_key: khóa tính MAC đã được client và server thống nhất trong phần bắt tay - pad_1: byte 0x36 (00110110) được lặp lại 48 lần (384 bít) đối với hàm hash MD5 và 40 lần (320 bít) đối với hàm hash SHA-1 - pad_2: byte 0x5C (10101100) được lặp lại 48 lần đối với MD5 và 40 lần với SHA-1 - seq_num: số thứ tự của khối dữ liệu - type: loại khối dữ liệu (xem phần bên dưới) - length: kích thước khối dữ liệu - data: khối dữ liệu Sau khi tính MAC xong, khối dữ liệu cùng với giá trị MAC được mã hóa bằng một thuật toán mã khối đã được lựa chọn trong giao thức bắt tay. Cuối cùng một SSL header được gắn vào đầu khối dữ liệu. SSL header gồm các field sau: - Content Type (1 byte): Ngoài việc truyền dữ liệu của giao thức HTTP, SSL Record Protocol còn được dùng để truyền dữ liệu của giao thức Handshake cũng như hai giao thức còn lại SSL Change Cipher Spec và SSL Alert. Giá trị 116
của field này dùng để xác định loại giao thức đang được sử dụng. Đối với giao thức giao thức Handshake dữ liệu được truyền thẳng không cần nén, tính MAC và mã hóa. - Major Version (1 byte): số hiệu chính của phiên bản SSL. Với SSLv3 field này có giá trị là 3. - Minor Version (1 byte): số hiệu phụ của phiên bản SSL. Với SSLv3 field này có giá trị là 0. - Compressed Length (2 byte): kích thước tính bằng byte của khối dữ liệu sau bước nén. SSL SSL Change SSL Alert Handshake Cipher Spec Protocol HTTP Protocol Protocol SSL Record Protocol TCP IP Hình 7-8. Mối liên hệ giữa các giao thức con của SSL 7.3.3 SSL Session và SSL Connection Để tránh việc mỗi lần kết nối với server là client phải tiến hành giao thức bắt tay lại từ đầu, SSL đưa ra khái niệm Session và Connection. Có thể hình dung, khi bạn mở trình duyệt và kết nối đến trang chủ một website, là bạn tạo một session mới, còn khi bạn click vào các link để đi đến các trang web khác trong cùng website, là bạn tạo connection mới trong session đã có này. Do đó SSL chỉ cần thực hiện giao thức bắt tay khi tạo session, còn khi tạo mới connection, SSL sẽ giữ nguyên tất cả các phương pháp mã hóa đã được chọn, giữ nguyên giá trị “pre-master secret”. Lúc này SSL chỉ cần thay đổi hai giá trị ClientHello.Random và ServerHello.Random, sau đó tính lại các giá trị “master secret” và 2 khóa MAC, 2 khóa mã hóa và 2 IV. Và việc trao đổi dữ liệu trên connection mới đã có thể bắt đầu mà không phải thực hiện giao thức bắt tay lại từ đầu. 7.4 Giao thức bảo mật mạng cục bộ Keberos 7.4.1 Keberos version 4. Trong các phần trên, chúng ta đã tìm hiểu về chứng thực X.509 và giao thức SSL dùng để bảo mật dữ liệu truyền đi trên mạng Internet. Mỗi server trên internet đều có chứng chỉ X.509 và cơ chế xác thực mật khẩu người sử dụng để bảo đảm tính chứng thực của cả hai bên, đồng thời thiết lập khóa phiên để bảo mật dữ liệu. Giao thức Keberos là một giao thức chứng thực sử dụng trong môi trường mạng quy mô nhỏ hơn như là mạng cục bộ LAN. Trong mạng LAN sử dụng trong các tổ chức và doanh nghiệp, cũng có các dịch vụ được cung cấp qua mạng như dịch vụ in ấn, dịch vụ chia sẻ file, cơ sở dữ liệu, email Mỗi dịch vụ này đều cần chứng thực người sử dụng cũng như bảo mật. Dĩ nhiên là có thể dùng chứng thực X509. Tuy nhiên trong môi trường 117
mạng nhỏ như mạng LAN, giao thức Keberos có thể được sử dụng như là một giải pháp thay thế. Keberos là giao thức chứng thực dựa trên khái niệm trung tâm phân phối khóa KDC (xem phần 3.9 và mô hình mở rộng chống replay attack trong chương 6), tức Keberos chỉ dựa trên mã hóa đối xứng. Giao thức này do MIT chuẩn hóa. Mục đích của Keberos là để trao đổi khóa phiên, thông qua đó đảm bảo tính bảo mật và tính chứng thực. Do nguyên tắc của Keberos dựa trên KDC nên Keberos cũng kế thừa được những ưu điểm của mô hình KDC như tính phi trạng thái. Hình dưới minh họa mô hình hoạt động của Keberos version 4. Keberos et- t Tick Thực hiện 1 ques t . Re Ticke Authentication 1 ting lần lúc logon Gran Server(AS) n Key o ` Sessi ket+ 2. Tic 3. Request Service- Granting Ticket Ticket-Granting 4. Ticket+Session Key Server (TGS) Client A 5. Re qu Thực hiện 1 lần es t S theo loại dịch vụ erv ice 6 . P Thực hiện 1 lần tại rov au ide mỗi phiên dịch vụ the se nt rv ica er tor Server B Hình 7-9. Mô hình chứng thực và trao đổi khóa phiên Keberos Trong mô hình trên, client A cần kết nối sử dụng dịch vụ tại server B. Authentication Server AS (chỉ có một AS) và Ticket-Granting Server TGS (có thể có nhiều TGS) đóng vai trò là các KDC. Server AS có nhiệm vụ cung cấp khóa đối xứng cho trao đổi giữa client A và server TGS. Server TGS có nhiệm vụ cung cấp khóa đối xứng cho trao đổi giữa client A và server dịch vụ B. Các người sử dụng A cần đăng ký mật khẩu KA của mình với Server AS. Các server dịch vụ B đăng ký khóa bí mật KB với Server TGS. Server TGS cũng đăng ký khóa bí mật KTGS với Server AS. Quá trình phân phối khóa phiên KAB để người sử dụng A kết nối với Server B trải qua ba giai đoạn như sau. a) Giai đoạn đăng nhập: có hai thông điệp 1. A AS: IDA|| IDTGS|| TS1 2. AS A: E(KATGS||IDTGS||TS2||Lifetime2||TicketTGS, KA) TicketTGS = E(KATGS||IDA||ADA||IDTGS||TS2||Lifetime2 , KTGS) Trước tiên A sẽ gửi yêu cầu đến server AS, đề nghị cung cấp khóa phiên để kết nối với server TGS. IDA và IDTGS nhằm định danh client A và server TGS, TS1 là timestamp xác định thời điểm client A gửi yêu cầu. Sau đó server AS sẽ phát sinh khóa phiên KATGS này và mã hóa thành hai bản, một bản dành cho A (được mã hóa bởi KA) và một bản dành cho TGS (được mã hóa bởi KTGS). Tuy nhiên bản dành cho TGS được giao cho A quản lý và được gọi là Ticket-Granting Ticket (TGT). A sẽ 118
dùng ticket này để thiết lập kết nối với TGS. TS2 là timestamp xác định thời điểm cấp thẻ, Lifetime2 là thời hạn hiệu lực của thẻ này. ADA là địa chỉ mạng của client A, yếu tố này dùng để chống lại phá hoại replay attack. b) Giai đoạn đăng ký sử dụng dịch vụ: 3. A TGS: IDB|| TicketTGS|| Authenticator Authenticator = E(IDA||ADA||TS3 , KATGS) 4. TGS A: E(KAB||IDB||TS4||TicketB, KATGS) TicketB = E(KAB||IDA||ADA||IDV||TS4||Lifetime4 , KB) Sau khi được cấp ticket TGT và khóa phiên KATGS để trao đổi với server TGS, client A gửi ticket này cho server TGS cùng với một autheticator để TGS chứng thực client A. Trong thông điệp này client cũng yêu cầu TGS cấp khóa phiên để kết nối với server dịch vụ B. IDB nhằm xác định server dịch vụ này. TS3 là timestamp xác định thời điểm A sử dụng KATGS (chống replay attack). Sau khi giải mã ticket, TGS có được khóa phiên KATGS. Từ đó TGS có thể kiểm tra tính chứng thực của client A qua Authenticator. Sau đó TGS sẽ phát sinh khóa phiên KAB và mã hóa thành hai bản, một bản dành cho A (được mã hóa bởi KATGS ) và một bản dành cho B (được mã hóa bằng KB). Tương tự như TGT, bản dành cho B cũng được giao cho A quản lý và được gọi là service ticket. A dùng ticket này trao đổi dữ liệu với B. TS4 và Lifetime4 là thời điểm hiệu lực và thời hạn hiệu lực của ticket này. c) Giai đoạn sử dụng dịch vụ: 5. A B: TicketB|| Authenticator Authenticator = E(IDA||ADA||TS5 , KAB) 6. B A: E(TS5 + 1, KAB) Tương tự như ở thông điệp 3, sau khi được cấp service ticket và khóa phiên KAB để trao đổi với server B, client A gửi ticket này cho server B cùng với một Autheticator để B chứng thực A (tương tự như authenticator để TGS chứng thực A). B giải mã ticket này để có được khóa phiên KAB và từ đó B giải mã authenticator để kiểm tra tính chứng thực của A. TS5 là timestamp xác định thời điểm A sử dụng KAB (chống replay attack) Tiếp theo B có thể gửi lại TS5+1 cho A để A chứng thực B. Sau thông điệp này A và B có thể tiến hành trao đổi dữ liệu thông qua khóa phiên KAB. A có thể sử dụng TicketB để kết nối với server B nhiều lần trong thời hạn TicketB còn hiệu lực. Khi ticket này hết hạn, A có thể gửi lại yêu cầu mới cho TGS để TGS cấp ticket khác. 7.5 Câu hỏi ôn tập 1. Tại sao nếu Bob tin tưởng vào khóa công khai của trung tâm chứng thực X thì Bob có thể tin tưởng vào khóa công khai của Alice? (khóa này được nhúng trong chứng chỉ X.509 do X cấp cho Alice) 119
2. Trong giao thức SSL, client có cần cung cấp chứng chỉ X.509 cho server không? 3. Trong giao thức SSL, dữ liệu Web (HTML) được mã hóa dùng phương pháp mã hóa khóa công khai hay mã hóa đối xứng? 4. Giao thức SSL có thể bảo đảm dữ liệu truyền trên mạng. Vậy mục đích của giao thức Keberos là gì? 7.6 Bài tập thực hành 1. Tạo chứng chỉ X.509 theo các cách thức: . Dùng công cụ makecert của microsoft . Dùng công cụ openssl . Đăng ký tại Verisign 2. Lập trình xem nội dung của một chứng chỉ X509, trích khóa công khai từ chứng chỉ. 3. Cài đặt SSL cho web server Internet Information Server IIS 4. Cài đặt SSL cho web server Apache. 120
CHƢƠNG 8. PHÁ MÃ VI SAI VÀ PHÁ MÃ TUYẾN TÍNH Trong chương 3 chúng ta đã đề cập sơ lược đến ba cách thức phá mã DES. Chương này trình bày cách thức phá mã vi sai và phá mã tuyến tính. Việc tìm hiểu hai cách thức tấn công này giúp chúng ta hiểu rõ hơn về đặc điểm và cách thức xây dựng mã khối. Để đơn giản, chúng ta sẽ tìm hiểu phá mã TinyDES. Việc phá mã DES cũng thực hiện theo nguyên tắc tương tự. 8.1 Phá mã vi sai (Differential Cryptanalysis) Trong chương 3, chúng ta đã tìm hiểu hiệu ứng lan truyền của mã DES, dưới tác động của các S-box và khóa K, chỉ cần thay đổi một bít trong bản rõ hay trong khóa sẽ dẫn đến sự thay đổi của nhiều bít trong các giá trị trung gian LiRi và trong bản mã. Do đó người phá mã khó phân tích được mối liên quan giữa bản rõ, bản mã và khóa – cho dù phá mã trong trường hợp known-plaintext hay chosen-plaintext. Li-1 Ri-1 Expand X K i S-box Y P-box Z Li Ri Tuy nhiên, nếu xét dưới góc độ giá trị vi sai (differential) thì tác dụng lan truyền của khóa K và hàm S-box lại mất hiệu lực. Ta định nghĩa khái niệm vi sai như sau: Giả sử hai giá trị X1 và X2 cùng số bít, thì vi sai giữa X1 và X2 là: X = X1  X2 Tính chất của giá trị vi sai qua các phép biến đổi: 1) Phép XOR với giá trị khóa: Cho   thì:   như vậy input XOR bằng output XOR, điều đó có nghĩa là giá trị vi sai không chịu tác động của khóa. Đây là yếu tố quan trọng của phá mã vi sai. 2) Phép P-box: Cho - - 121
thì:  -  điều đó có nghĩa là nếu vi sai của đầu vào (input XOR) là cố định thì vi sai của đầu ra (output XOR) cũng cố định. Phép biến đổi P-box là tuyến tính, ứng với mỗi giá trị đầu vào có 1 giá trị đầu ra và ngược lại. 3) Phép Expand: Cho thì:   tương tự như hàm P-box, trong hàm Expand, nếu input XOR là cố định thì output XOR cũng cố định. Hàm Expand cũng là phép biến đổi tuyến tính. 4) Phép S-box Xét S-box của mã TinyDES (cũng là hộp S1 của mã DES) với 6 bít đầu vào và 4 bít đầu ra: Cho - - Trong trường hợp này output XOR  không cố định và S-box không phải là phép biến đổi tuyến tính. Ví dụ, xét bảng dưới đây trong trường hợp input XOR là 000001: X1 X2 X1  X2 Y1 Y2 Y1  Y2 000000 000001 000001 1110 0000 1110 001000 001001 000001 0010 1110 1100 100000 100001 000001 0100 1111 1011 Ứng với mỗi giá trị của X1 thì có một X2 tương ứng để giá trị XOR là 000001. 6 Do đó bảng trên có 2 = 64 dòng tương ứng với 64 cặp (X1, X2). Tương tự như vậy đối với các input XOR khác. Dù rằng ứng với cùng một input XOR thì các giá trị output XOR là khác nhau, nhưng nếu xét dưới góc độ thống kê thì vẫn tồn tại mối quan hệ giữa input XOR và output XOR, điều đó được thể hiện qua bảng sau: 122
Input XOR Output XOR (4 bít) (6 bít) 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 64 1 6 2 4 4 10 12 4 10 6 2 4 2 8 4 4 4 6 8 6 12 6 4 2 3 14 4 2 2 10 6 4 2 6 4 4 2 2 2 4 6 10 10 6 4 6 4 2 8 6 2 5 4 8 6 2 2 4 4 2 4 4 12 2 4 6 6 4 2 4 8 2 6 2 8 4 4 2 4 2 12 7 2 4 10 4 4 8 4 2 4 8 2 2 2 4 4 8 12 8 8 4 6 2 8 8 2 2 4 9 10 2 4 2 4 6 2 2 8 10 2 12 A 8 6 2 2 8 6 6 4 6 4 2 10 B 2 4 10 2 2 4 2 6 2 6 6 4 2 12 C 8 6 6 6 6 4 6 6 14 2 D 6 6 4 8 4 8 2 6 6 4 6 2 2 E 4 8 8 6 6 4 6 6 4 4 8 F 2 2 4 4 6 4 2 4 8 2 2 2 6 8 8 10 2 14 6 6 12 4 6 8 6 11 6 8 2 4 6 4 8 6 4 6 6 4 12 8 4 2 6 6 4 6 6 4 2 6 6 4 13 2 4 4 6 2 4 6 2 6 8 4 6 4 6 14 8 8 10 4 2 8 2 2 4 4 8 4 15 4 6 4 2 2 4 10 6 2 10 4 6 4 16 8 10 8 2 2 6 10 2 2 6 2 6 17 4 4 6 10 6 2 4 4 4 6 6 6 2 18 6 6 8 4 2 2 2 4 6 8 6 6 2 2 19 2 6 2 4 8 4 6 10 4 4 2 8 4 1A 6 4 4 6 6 6 6 22 2 4 4 6 8 1B 4 4 2 4 10 6 6 4 6 2 2 4 2 2 4 2 1C 10 10 6 6 12 6 4 2 4 4 1D 4 2 4 8 2 12 2 6 6 6 14 1E 2 6 14 2 6 4 10 8 2 2 6 2 1F 2 4 10 6 2 2 2 8 6 8 4 6 4 20 10 12 8 2 6 4 4 4 2 12 21 4 2 4 4 8 10 4 4 10 4 2 8 22 10 4 6 2 2 8 2 2 2 2 6 4 4 10 23 4 4 8 2 6 6 6 2 10 2 4 10 24 12 2 2 2 2 14 14 2 2 6 2 4 25 6 4 4 12 4 4 4 10 2 2 2 4 2 2 2 26 4 10 10 10 2 4 4 6 4 4 4 2 27 10 4 2 2 4 2 4 8 4 8 8 4 4 28 12 2 2 8 2 6 12 2 6 4 6 2 29 4 2 2 10 2 4 14 10 2 4 6 4 2A 4 2 4 6 2 8 2 2 14 2 6 2 6 2 2 2B 12 2 2 2 4 6 6 2 2 6 2 6 8 4 2C 4 2 2 4 2 10 4 2 2 4 8 8 4 2 6 2D 6 2 6 2 8 4 4 4 2 4 6 8 2 6 2E 6 6 2 2 2 4 6 4 6 2 12 2 6 4 2F 2 2 2 2 2 6 8 8 2 4 4 6 8 3 4 3 30 4 6 12 6 2 2 8 2 4 4 6 2 2 4 31 4 8 2 10 2 2 2 2 6 2 2 4 10 8 32 4 2 6 4 4 2 2 4 6 6 4 8 2 2 8 33 4 4 6 2 10 8 4 2 4 2 2 4 6 2 4 34 8 16 6 2 12 6 8 6 35 2 2 4 8 14 4 6 8 2 14 36 2 6 2 2 8 2 2 4 2 6 8 6 4 10 37 2 2 12 4 2 4 4 10 4 4 2 6 2 2 4 38 6 2 2 2 2 2 4 6 4 4 4 6 10 10 39 6 2 2 4 12 6 4 8 4 2 4 2 4 4 3A 6 4 6 4 6 8 6 2 2 6 2 2 6 4 3B 2 6 4 2 4 6 4 6 8 6 4 4 6 2 3C 10 4 12 4 2 6 4 12 4 4 2 3D 8 6 2 2 6 8 4 4 4 12 4 4 3E 4 8 2 2 2 4 4 14 4 2 2 8 4 4 3F 4 8 4 2 4 2 4 4 2 4 8 8 6 2 2 123
Trong bảng trên tổng của mỗi dòng là 64 (là số cặp X1, X2 ứng với input XOR tương ứng), tuy nhiên số 64 này không phân bố đều trên các output XOR. Ta có kết luận về giá trị vi sai của S-box này như sau: - Nếu input XOR là 00 thì output XOR chắc chắn là 0. - Nếu input XOR là 10 thì output XOR là 7 với xác suất 14/64. Bảng dưới liệt kê các cặp đầu vào và đầu ra tương ứng X1  X2 = 10 Y1  Y2=7 X1 X2 Y1 Y2 08 18 2 5 09 19 E 9 0B 1B 2 5 23 33 C B 24 34 E 9 2C 3C 2 5 2D 3D 1 6 - Nếu input XOR là 34 thì output XOR là 2 với xác suất 16/64. Bảng dưới liệt kê các cặp đầu vào và đầu ra tương ứng X1  X2 = 34 Y1  Y2=2 X1 X2 Y1 Y2 04 30 D F 05 31 7 5 0E 3A 8 A 11 25 A 8 12 26 A 8 14 20 6 4 1A 2E 9 B 1B 2F 5 7 Từ đó ta có kết luận sau về giá trị vi sai của hàm F trong TinyDES, với input XOR và output XOR của hàm F là 4 bít: F = P-box(S-box(Expand( Ri-1) Ki)) - Nếu input XOR của F là 0: output XOR của Expand là 0 (6 bít) input XOR của S-box là 0 (khóa không ảnh hưởng đến vi sai) input XOR của P-box (4 bít) chắn chắn là 0 output XOR của F chắn chắn là 0. - Nếu input XOR của F là 3: output XOR của Expand là 34 input XOR của P-box (4 bít) là 2 với xác suất 16/64 output XOR của F là 8 với xác suất 16/64 = 1/4. - Nếu input XOR của F là 1: output XOR của Expand là 10 input XOR của P-box (4 bít) là 7 với xác suất 14/64 output XOR của F là B với xác suất 14/64 = 7/32. 124
Như vậy, dù không biết giá trị của khóa K nhưng ta vẫn có thể tín được sự lan truyền của giá trị vi sai qua 3 vòng của TinyDES. Xét ví dụ sau: Chọn và ̅ ̅ ̅ sao cho vi sai ̅ 83 (83: số thập lục phân). Quá trình lan truyền vi sai qua các vòng TinyDES được thể hiện trong bảng bên dưới. ̅ ̅ ̅ ̅ ̅ 83 Xác suất 1 ̅1 ̅ ̅ ̅ ̅ ̅ ̅ 3 1/4 2 1 ̅2 ̅1 ̅ ̅ ̅ ̅ ̅ 3 (1/4)×1 ̅ 3 2 ̅3 ̅2 ̅ ̅ ̅ ̅ ̅ 38 (1/4)×(1/4) Như vậy vi sai của bản mã là 38 với xác suất 1/16. Điều đó có nghĩa là trung bình trong 16 cặp bản rõ có vi sai là 83 thì sẽ tìm thấy 1 cặp có vi sai bản mã là 38. Với 1 khóa K cụ thể nào đó, giả sử ta thực hiện chosen-plaintext cho 16 cặp (bản rõ, bản mã) và tìm thấy 1 cặp sau: 2 5 ̅ ̅ ̅ 8 ̅ ̅ ̅ (có vi sai bản rõ là 83 và vi sai bản mã là 38) Như vậy, tại vòng thứ 3, input của hàm F trong hai trường hợp tương ứng là ̅ ̅ . Do đó output của hàm Expand trong 2 trường hợp là 2F và 1B. Vì input XOR và output XOR của S-box trong vòng thứ 3 này là 34 và 2. Tra bảng, ta có các khóa K3 có thể có là: X1  X2 = 34 X1  X2 = 34 K3 K3 X1=2F  K3 X2=1B  K3 X1=1B  K3 X2=2F  K3 04 30 2B 04 30 1F 05 31 2A 05 31 1E 0E 3A 21 0E 3A 15 11 25 3E 11 25 0A 12 26 3D 12 26 09 14 20 3B 14 20 0F 1A 2E 35 1A 2E 01 1B 2F 34 1B 2F 00 Tương tự, chọn và ̅ ̅ ̅ sao cho vi sai ̅ 1. Quá trình lan truyền vi sai qua các vòng TinyDES được thể hiện trong bảng bên dưới. ̅ ̅ ̅ ̅ ̅ 1 Xác suất 1 ̅1 ̅ ̅ ̅ ̅ ̅ ̅ 1 7/32 2 1 ̅2 ̅1 ̅ ̅ ̅ ̅ ̅ 1 (7/32)×1 ̅ 3 2 ̅3 ̅2 ̅ ̅ 2 ̅ ̅ ̅ 1 (7/32) 0.048 125
Như vậy vi sai của bản mã là 1B với xác suất 0.048. Điều đó có nghĩa là trung bình trong 21 cặp bản rõ có vi sai là B1 thì sẽ tìm thấy 1 cặp có vi sai bản mã là 1B. Với 1 khóa K cụ thể nào đó, giả sử ta thực hiện chosen-plaintext cho 21 cặp (bản rõ, bản mã) và tìm thấy 1 cặp sau: 3 83 ̅ ̅ ̅ 8 ̅ ̅ ̅ 98 (có vi sai bản rõ là B1 và vi sai bản mã là 1B) Tại vòng thứ 3, input của hàm F trong hai trường hợp tương ứng là 8 ̅ ̅ 9. Do đó output của hàm Expand trong 2 trường hợp là 01 và 11. Vì input XOR và output XOR của S-box trong vòng thứ 3 này là 10 và 7. Tra bảng, ta có các khóa K3 có thể có là: X1  X2 = 10 X1  X2 = 10 K3 K3 X1=01  K3 X2=11  K3 X1=11  K3 X2=01  K3 08 18 09 08 18 19 09 19 08 09 19 18 0B 1B 0A 0B 1B 1A 23 33 22 23 33 32 24 34 25 24 34 35 2C 3C 2D 2C 3C 3D 2D 3D 2C 2D 3D 3C Kết hợp 2 bảng, thì K3 phải là giá trị thuộc tập { 09, 0A, 35, 3D }. Gọi 8 bít của khóa K là k0k1k2k3k4k5k6k7 , thì 6 bít của K3 là k5k1k3k2k7k0. Như vậy với từng trường hợp của K3 chúng ta có thể thử các giá trị của k4 và k6. Ví dụ giả sử K3 là 09 (nhị phân 001001), như vậy khóa K có dạng 1001x0x0, và khóa K có 4 trường hợp: 10010000, 10010010, 10011000, 10011010. Lần lượt mã hóa bản rõ 2B với 4 trường hợp trên của khóa K, thì chỉ có trường hợp K = 1001.1010 cho ra bản rõ E5. Như vậy thay vì vét cạn 256 trường hợp của khóa K, chúng ta chỉ cần thử 16+21= 37 cặp bản rõ-bản mã, sau đó thử thêm 16 trường hợp của khóa K thì tìm ra được giá trị chính xác của K. Điều này chứng tỏ phương pháp phá mã vi sai là có hiệu quả để phá mã TinyDES. 8.2 Phá mã tuyến tính (Linear Cryptanalysis) Trong phần mã TinyDES, chúng ta đã nói S-box là một cấu trúc phi tuyến, tức với Y=S-box(X) thì giữa X và Y không có mối liên hệ toán học. Tuy nhiên nếu chỉ xét một số bít của X và Y lại bộc lộ một số quan hệ tuyến tính. Chúng ta ký hiệu các bít của X và Y như sau: Gọi a là các giá trị từ 1 đến 64 và b là các giá trị từ 1 đến 15, a0a1a2a3a4a5 và b0b1b2b3 là biểu diễn nhị phân tương ứng của a và b. Với một a và b cụ thể, tính: 1 126
1 Với 64 trường hợp của Y=S-box(X), ta định nghĩa số S(a, b) như sau: S(a, b) là số trường hợp mà LX(X, a) = LY(Y, b) Bảng bên dưới liệt kê các giá trị S(a, b) 32 với a từ 1 đến 32 và b từ 1 đến 15. b a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 -2 -2 -4 -2 0 -4 6 2 0 0 6 4 -2 -6 4 3 -2 -2 -4 -2 0 -4 6 2 8 0 -2 4 6 -6 -4 4 2 -2 -4 -2 0 -4 -6 -2 4 8 2 0 -2 -6 12 5 -2 -2 0 -2 -4 -4 -2 2 -4 -4 2 4 -10 -2 -4 6 0 0 4 0 4 0 0 0 -4 4 4 0 0 -4 -8 7 -4 0 8 0 0 0 4 4 -4 -8 -4 4 0 0 0 8 4 -2 6 -6 -6 0 -4 -4 -4 2 -2 2 -2 0 0 9 0 6 -6 -2 -6 4 -4 0 -4 -2 6 2 -6 0 -4 10 -2 0 2 0 6 8 2 -2 0 -2 4 -2 0 -2 4 11 2 -8 -2 -4 -10 4 2 -6 8 2 4 -2 -4 -2 0 12 -2 0 6 0 2 0 2 2 0 6 -4 2 -4 6 0 13 6 0 6 4 -2 -4 -2 2 0 6 4 -2 8 -6 -4 14 0 -2 -2 2 2 0 0 4 4 6 -2 2 2 -4 4 15 0 -2 6 -2 -2 4 -4 -4 -4 -2 -2 -2 -2 0 0 16 2 2 0 -2 0 4 -6 0 6 2 -4 6 -4 -4 -18 17 2 -2 -4 2 -4 -4 10 -4 2 2 -4 -2 -4 0 -6 18 4 0 0 -4 4 0 4 -6 2 2 6 2 6 6 -10 19 4 -4 -4 0 0 -8 -12 -2 -2 -6 6 2 6 2 2 20 4 0 4 -8 -4 4 0 2 6 -2 2 6 2 -2 2 21 0 4 -4 -4 4 4 -4 10 2 2 2 -6 2 6 -2 22 6 2 0 2 -4 0 2 4 2 2 0 -2 0 0 2 23 2 6 -8 6 4 0 -2 -12 -2 -2 0 -6 0 0 -2 24 2 8 2 0 6 4 2 4 -2 4 6 0 -2 -4 2 25 -2 4 -6 0 -6 0 2 4 -6 8 6 0 2 0 -6 26 0 -6 2 -2 -2 4 4 -2 -2 0 0 -4 4 2 2 27 4 6 2 -10 2 -8 4 -2 -6 4 0 4 0 -2 2 28 -4 2 2 2 -6 0 -4 -2 -2 4 0 0 4 2 2 29 4 -2 -2 2 -6 -4 0 2 2 -4 0 -12 0 -6 -6 30 2 0 -2 4 -2 0 -2 0 6 -4 -2 0 -2 0 2 31 2 -4 2 -4 -2 4 2 4 -6 4 -2 -4 2 0 2 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Nếu S(a, b) = 32, thì các bít theo a của X và các bít theo b của Y không có mối quan hệ tuyến tính Xét S(16, 15) = 14 , điều này có nghĩa là: xảy ra với xác suất 14/64 hay xảy ra với xác suất 50/64 ta viết lại mối quan hệ này Y[0,1,2,3] = X[1] Như vậy nếu xét Y=F(X, K) với F là hàm Feistel trong 1 vòng của mã TinyDES: Thì ta có quan hệ tuyến tính sau: [ 1 2 3] [3] [1] Bây giờ ta liên kết mối quan hệ này qua ba vòng của TinyDES Xác suất 1 [ 1 2 3] [ 1 2 3] [3] [1] 14/64 127
2 1 3 2 [ 1 2 3] [ 1 2 3] [3] [1] 14/64 [ 1 2 3] [ 1 2 3] [3] [1] Suy ra: [ 1 2 3] [ 1 2 3] [3] [3] [1] [1] hay [1] 3[1] 3[ 1 2 3] [ 1 2 3] [3] 3[3] Phương trình trên thỏa mãn với xác suất (14/64)2 + (1-14/64)2 = 0.66. Giả sử ta phá mã known-plaintext với 100 cặp bản rõ-bản mã và có được kết quả sau: [ 1 2 3] [ 1 2 3] [3] [3] 1 xuất hiện 66 lần [ 1 2 3] [ 1 2 3] [3] [3] xuất hiện 34 lần Thì ta có thể kết luận [1] 3[1] 1 hay 2 1 với k1, k2 là bít thứ 1 và thứ 2 trong khóa K ban đầu. Như vậy ta đã biết được mối quan hệ giữa hai bít k1, k2 của khóa K ban đầu, điều này giúp ta chỉ cần tìm trong 128 giá trị của khóa K mà thôi. Điều này chứng tỏ phương pháp phá mã tuyến tính là có hiệu quả để phá mã TinyDES hơn là phương pháp vét cạn khóa. 8.3 Kết luận về nguyên tắc thiết kế mã khối. Vì chúng ta không thể chứng minh về mặt lý thuyết là mã khối có an toàn tuyệt đối hay không nên các nhà nghiên cứu tìm cách chống lại các hình thức phá mã đã biết. Để chống lại hai hình thức phá mã vi sai và tuyến tính, một số nguyên tắc sau được đặt ra. 1) Tăng số vòng mã hóa: vì phá mã vi sai và tuyến tính thực hiện theo xác suất nên số vòng càng nhiều thì xác suất càng giảm. 2) Cải thiện hàm S-box: hàm S-box phải được cải tiến sao cho dấu vết vi sai và dấu vết tuyến tính càng ít càng tốt (xác suất vi sai và xác suất tuyến tính giảm). 3) Cải thiện việc xáo trộn (mix) kết quả trung gian từ vòng này qua vòng khác, thể hiện ở các hàm Expand và P-box. Việc xáo trộn tốt hơn sẽ làm cho việc liên kết vi sai và liên kết tuyến tính giữa các vòng giảm đi. Trong chương tiếp theo, chúng ta sẽ tìm hiểu về mã hóa AES. Mã hóa này thực hiện rất tốt hàm S-box và P-box nên mã AES chỉ cần thực hiện 10 vòng so với 16 vòng của mã DES. 128
CHƢƠNG 9. ADVANCED ENCRYPTION STANDARD – AES 9.1 Nhóm, vành, trường Nhóm, vành, trường các yếu tố cơ bản của một ngành toán học gọi là đại số trừu trượng (abstract algebra). Trong ngành toán này, chúng ta quan tâm đến một tập các phần tử, cách thức kết hợp phần tử thứ nhất và phần tử thứ hai để tạo thành một phần tử thứ ba (giống như trong số học thường ta dùng phép cộng và phép nhân áp dụng trên hai số cho ra kết quả số thứ ba) 9.1.1 Nhóm (Group) Một nhóm, ký hiệu là {G, }, là một tập G các phần tử và một phép kết hợp 2 ngôi  thỏa mãn các điều kiện sau: A1) Tính đóng: A2) Tính kết hợp: A3) Phần tử đơn vị: A4) Phần tử nghịch đảo: Ví dụ 1: Dễ thấy tập số nguyên Z và phép cộng số nguyên là một nhóm. Phần tử đơn vị là 0. Với a Z thì nghịch đảo của a là – a. Tập Z có vô hạn phần tử nên nhóm này được gọi là nhóm vô hạn. Ví dụ 2: xét một tập S gồm n số nguyên { 1, 2, , n }. Định nghĩa tập T có các phần tử là các hoán vị của tập S. Ví dụ n = 4, như vậy {1, 2, 3, 4} T, {3, 2, 1, 4} T, Tập T có 4! = 24 phần tử. Tiếp theo, định nghĩa phép kết hợp  như sau: c = a b là một hoán vị của a theo thứ tự trong b. Ví dụ: a = { 2, 3, 4, 1}, b = {3, 2, 4, 1 }. Hoán vị của a theo b là { 4, 3, 1, 2}. c cũng là phần tử thuộc T nên thỏa tính chất A1. Nếu chọn e = {1, 2, 3, 4} thì không làm thay đổi thứ tự của a, còn sẽ hoán vị e trở thành a. Vì vậy {1, 2, 3, 4} là phần tử đơn vị theo tính chất A3. Ta cũng có thể chứng minh tập T và phép hoán vị thỏa mãn hai tính chất còn lại A2 và A4. Nghĩa là T và phép hoán vị tạo thành một nhóm. Tập T có hữu hạn phần tử nên nhóm này được gọi là nhóm hữu hạn. Một nhóm được gọi là nhóm Abel nếu có thêm tính chất sau: A5) Tính giao hoán: Dễ thấy tập Z là nhóm Abel trên phép cộng. Còn tập T và phép hoán vị không phải là nhóm Abel với n>2 Nhóm vòng: Cho nhóm {G, }, ta định nghĩa phép lũy thừa như sau: 129
Ví dụ: . Ta gọi G là nhóm vòng nếu mọi phần tử của G đều biểu diễn được dưới dạng với a thuộc G và k là một số nguyên. Lúc này a được gọi là phần tử sinh của tập G. Ví dụ tập Z là một nhóm vòng với a là 1: 5 = 15, – 4 = (– 1)4 Mọi nhóm vòng đều có tính giao hoán nên đều là nhóm Abel. 9.1.2 Vành (Ring) Một vành R, ký hiệu { R, +, }, là một tập các phần tử và hai phép kết hợp 2 ngôi, gọi là phép cộng và phép nhân, nếu các tính chất sau được thỏa mãn: A1-A5) R là một nhóm Abel theo phép cộng: R thỏa mãn các tính chất từ A1 đến A5, ta ký hiệu phần tử đơn vị là 0 và phần tử nghịch đảo của a trong phép cộng là – a. Ta định nghĩa phép trừ là a – b = a + (–b) M1) Tính đóng đối với phép nhân: (viết tắt thay cho dấu ) M2) Tính kết hợp đối với phép nhân: M3) Tính phân phối giữa phép cộng và phép nhân: Ngắn gọn, trong một vành, chúng ta có thể thực hiện các phép cộng, trừ, nhân mà không ra khỏi vành (kết quả các phép toán cộng, trừ, nhân thuộc R) Ví dụ: cho tập các ma trận vuông cấp n với số thực, các phép cộng và nhân ma trận tạo thành một vành. Một vành được gọi là vành giao hoán nếu có thêm tính giao hoán đối với phép nhân: M4) Tính giao hoán với phép nhân: Ví dụ: cho tập các số nguyên chẵn, với các phép cộng và nhân thông thường, tạo thành một vành giao hoán, tập ma trận vuông cấp n như trên không phải là vành giao hoán. Một vành được gọi là miền nguyên (integral domain) nếu đó là vành giao hoán và có thêm hai tính chất sau: M5) Tồn tại phần tử đơn vị phép nhân: 1 1 M6) Liên quan giữa phép nhân và phần tử đơn vị phép cộng : 9.1.3 Trường (Field) Một trường, ký hiệu { F, +, }, là một tập các phần tử và hai phép kết hợp 2 ngôi, gọi là phép cộng và phép nhân, nếu các tính chất sau được thỏa mãn: A1-A5, M1-M6) F là một miền nguyên (thỏa các tính chất A1 đến A5 và M1 đến M6) M7) Tồn tại phần tử nghịch đảo của phép nhân: 1 Ngắn gọn, trong một trường, chúng ta có thể thực hiện các phép cộng, trừ, nhân, chia mà không ra khỏi trường (kết quả các phép toán cộng, trừ, nhân, chia thuộc F). Định nghĩa phép chia là: 130
Ví dụ: tập các số thực với phép cộng và nhân thông thường là một trường. Tập các số nguyên không phải là trường vì không thực hiện được phép chia. 9.2 Số học modulo và trường hữu hạn GF(p) Trong chương 4 chúng ta đã tìm hiểu về phép toán modulo. Dựa trên phép toán modulo, chúng ta xây dựng một tập Zn như sau: Cho một số nguyên n: Zn = { 0, 1, 2, , n-1 } Tương tự như tập số nguyên Z, trên tập Zn ta cũng định nghĩa các phép cộng và nhân như sau:  a , b, c Zn : Phép cộng: c = a + b Phép cộng trong Zn nếu c Phép cộng trong số học thường Phép nhân: c = a.b nếu c Dễ thấy rằng tập Zn cùng với phép cộng trên thỏa mãn các tính chất của một nhóm Abel với phần tử đơn vị của phép cộng là 0 (các tính chất từ A1 đến A5). Bên cạnh đó, tập Zn cùng với phép cộng và phép nhân trên thỏa mãn các tính chất của một miền nguyên với phần tử đơn vị của phép nhân là 1 (các tính chất từ M1 đến M6). Ví dụ, với n = 7 thì phép nhân và phép cộng là như sau: + 0 1 2 3 4 5 6 x 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 1 2 3 4 5 6 0 1 0 1 2 3 4 5 6 2 2 3 4 5 6 0 1 2 0 2 4 6 1 3 5 3 3 4 5 6 0 1 2 3 0 3 6 2 5 1 4 4 4 5 6 0 1 2 3 4 0 4 1 5 2 6 3 5 5 6 0 1 2 3 4 5 0 5 3 1 6 4 2 6 6 0 1 2 3 4 5 6 0 6 5 4 3 2 1 Tuy nhiên không phải tập Zn nào cũng thỏa tính chất M7, nghĩa là mọi phần tử khác 0 của Zn phải có phần tử nghịch đảo của phép nhân. Chỉ có với những n là số nguyên tố thì Zn mới thỏa tính chất M7. (xem khái niệm 6 trong phần Lý thuyết số chương 4). Ví dụ với n=8 (không thỏa M7) và n= 7 (thỏa M7). a -a a-1 a -a a-1 0 0 - 0 0 - 1 7 1 1 6 1 2 6 - 2 5 4 3 5 3 3 4 5 4 4 - 4 3 2 5 3 5 5 2 3 6 2 - 6 1 6 7 1 7 131
Ta cũng dùng thuật toán Euclid mở rộng để tìm phần tử nghịch đảo phép nhân trong tập Zn. Ví dụ phép chia: 5/4 = 5(4-1) = 5.2 = 3. Như vậy với n là số nguyên tố, thì tập Zn trở thành một trường hữu hạn mà ta gọi là trường Galois (tên nhà toán học đã tìm hiểu về trường hữu hạn này). Ta đổi ký hiệu Zn thành Zp với quy định p là số nguyên tố. Ký hiệu trường hữu hạn trên là GF(p) 9.3 Số học đa thức và trường hữu hạn GF(2n) 9.3.1 Phép toán đa thức thông thường Trong đại số, chúng ta định nghĩa một đa thức bậc n (n 0) dưới dạng ∑ Trong đó các ai R, an 0 được gọi là các hệ số. Và ta cũng định nghĩa các phép cộng, trừ, nhân đa thức như sau: Cho ∑ ∑ Phép cộng: ∑ Phép nhân: ∑ Phép trừ: ∑ Trong 3 phép toán trên ta giả định ai = 0 nếu i > n và bi = 0 nếu i > m. Phép chia đa thức f(x) cho g(x) cũng tương tự như phép chia trên số nguyên, gồm một đa thức thương q(x) và một đa thức dư r(x). r(x) có bậc nhỏ hơn g(x) Ví dụ: 2 , 1 2 3 1 3 2 2 đa thức phần thương 2 và đa thức phần dư Với các phép toán cộng và nhân như trên thì tập các đa thức (mỗi đa thức là một phần tử của tập) tạo thành một vành, với phần tử đơn vị của phép cộng là đa thức e(x) = 0 và phần tử đơn vị của phép nhân là đa thức d(x) = 1. 132
Tuy nhiên tập các đa thức trên không tạo thành một trường vì không tồn tại phần tử nghịch đảo của phép nhân (nên phép chia 2 đa thức tồn tại phần dư). 9.3.2 Đa thức định nghĩa trên tập Zp Trong phần trên ta đã định nghĩa đa thức có các hệ số trong trường số thực (tập R). Trong phần này ta sẽ xem xét tập các đa thức Wp có hệ số thuộc trường Zp . { ∑ } Trên tập Wp ta định nghĩa các phép cộng, trừ, nhân, chia như sau: ∑ ∑ Phép cộng: ∑ Phép nhân: ∑ Phép trừ: ∑ Phép chia: à đ à Trong đó các phép toán , được định nghĩa trong tập Zp Ví dụ: xét trường 1 1 , 1 1 1 và . Trong ví dụ trên có thể xem g(x) và q(x) là đa thức ước số của đa thức f(x). f(x) = g(x). q(x). Những đa thức f(x) như vậy gọi là đa thức không tối giản. Đa thức tối giản là đa thức chỉ có ước số là đa thức 1 và chính nó (khái niệm tối giản tương tự như khái niệm số nguyên tố trong tập số tự nhiên). Ví dụ (cũng xét trong trường Z2): 1 là đa thức tối giản 1 không phải là đa thức tối giản vì 1 1 1 Tương tự như khái niệm ước số chung lớn nhất của 2 số tự nhiên, chúng ta cũng có khái niệm ước số chung lớn nhất của 2 đa thức. Khái niệm lớn ở đây là bậc lớn, ví dụ 1 lớn hơn 1 133
Ví dụ: xét trong trường Z2 , USCLN của hai đa thức 1 và 1 là 1 Tương tự như để tìm USCLN của 2 số nguyên, chúng ta có thể sử đổi thuật toán Eulid để tìm USCLN của hai đa thức /* Thuật toán Euclid tính gcd(a(x),b(x)) */ EUCLID (a(x),b(x)) A(x) = a(x); B(x) = b(x); while B(x)<>0 do R(x) = A(x) mod B(x); A(x) = B(x); B(x) = R(x); end while return A(x); 9.3.3 Phép modulo đa thức Tương tự như phép chia modulo trong tập số nguyên, ta định nghĩa một phép chia modulo đa thức trong tập các hàm đa thức. Giả sử ta có hai đa thức f(x) và m(x) định nghĩa trên trường Zp. Ta định nghĩa phép chia modulo của f(x) cho m(x) như sau: là phần dư của phép chia Ví dụ: thuật toán AES sử dụng đa thức 1 được định nghĩa trên trường Z2. Cũng trên Z2 xét đa thức: 1 Ta có: 1 9.3.4 Trường hữu hạn GF(2n) Tương tự như việc xây dựng tập Zp dùng phép modulo p với p là số nguyên tố, trong phần này ta sẽ xây dựng một tập Wpm các đa thức dùng phép modulo đa thức. Chọn một đa thức m(x l a thức tối giản trên Zp có bậc là n. Tập Wpm bao gồm các đa thức trên Zp có bậc nhỏ hơn n. Như vậy các đa thức thuộc Wpm có dạng: ∑ 1 1 Tập Wpm có pn phần tử. Ví dụ: - p=3, n = 2 tập Wpm có 9 phần tử: 1 2 1 2 2 2 1 2 2 - p=2, n = 3 tập Wpm có 8 phần tử: 1 1 1 1 . Ta định nghĩa lại phép cộng và phép nhân đa thức như sau: - Phép cộng, tương tự như phép cộng trên Wp - Phép nhân, cũng tương tự như phép nhân trên Wp, và kết quả cuối cùng được modulo với m(x) để bậc của kết quả nhỏ hơn n. 134
Vì m(x) là đa thức tối giản nên tương tự như số học modulo, các phần tử trong Wpm tồn tại phần tử nghịch đảo của phép nhân: 1 Do tồn tại phần tử nghịch đảo, nên ta có thể thực hiện được phép chia trong tập Wpm như sau: Lúc này Wpm thỏa mãn các tính chất của một trường hữu hạn và ta ký hiệu trường hữu hạn này là GF(pn) (cũng theo tên của nhà bác học Galois). Trong mã hóa, chúng ta chỉ quan tâm đến p =2 tức trường đa thức hữu hạn GF(2n) trên tập Z2. Ví dụ xét GF(23), chọn đa thức tối giản 1, bảng bên dưới thể hiện phép cộng và phép nhân. + 0 1 x x+1 x2 x2 + 1 x2+x x2+x+1 0 0 1 x x+1 x2 x2 + 1 x2+x x2+x+1 1 1 0 x+1 x x2+1 x2 x2+x+1 x2+x x x x+1 0 1 x2+x x2+x+1 x2 x2+1 x + 1 x+1 x 1 0 x2+x+1 x2+x x2+1 x2 x2 x2 x2+1 x2+x x2+x+1 0 1 x x+1 x2 + 1 x2+1 x2 x2+x+1 x2+x 1 0 x+1 x x2 + x x2+x x2+x+1 x2 x2+1 x x+1 0 1 x2 + x + 1 x2+x+1 x2+x x2+1 x2 x+1 x 1 0 a) Bảng phép cộng x 0 1 x x+1 x2 x2 + 1 x2+x x2+x+1 0 0 0 0 0 0 0 0 0 1 0 1 x x+1 x2 x2 + 1 x2+x x2+x+1 x 0 x x2 x2 + x x+1 1 x2+x+1 x2+1 x + 1 0 x + 1 x2 + x x2 + 1 x2+x+1 x2 1 x x2 0 x2 x+1 x2+x+1 x2 + x x x2 + 1 1 x2 + 1 0 x2 + 1 1 x2 x x2+x+1 x+1 x2+x x2 + x 0 x2 + x x2+x+1 1 x2 + 1 x+1 x x2 x2 + x + 1 0 x2+x+1 x2+1 x 1 x2+x x2 x+1 b) Bảng phép nhân Để tìm phân tử nghịch đảo của phép nhân đa thức, ta cũng sử dụng thuật toán Euclid mở rộng tương tự như tìm nghịch đảo trong tập Zp. /* Thuật toán Euclid mở rộng trả về hai giá trị: */ /* - gcd(m(x),b(x)); */ /* - nếu gcd(m(x),b(x))=1; trả về b-1(x) mod m(x) */ EXTENDED_EUCLID(m(x),b(x)) A1(x) = 1; A2(x) = 0; A3(x) = m(x); B1(x) = 0; B2(x) = 1; B3(x) = b(x); while (B3(x) 1) do Q(x) = phần thương của A3(x) / B3(x); 135
T1(x) = A1(x) – Q(x)B1(x); T2(x) = A2(x) – Q(x)B2(x); T3(x) = A3(x) – Q(x)B3(x); A1(x) = B1(x); A2(x) = B2(x); A3(x) = B3(x); B1(x) = T1(x); B2(x) = T2(x); B3(x) = T3(x); end while If B3(x)=0 then return A3(x); no inverse; If B3(x)=1 then return 1; B2(x); 9.3.5 Ứng dụng GF(2n) trong mã hóa Khi thực hiện mã hóa, đối xứng hay công khai, bản rõ và bản mã là các con số, việc mã hóa và giải mã có thể quy về việc thực hiện các phép cộng, trừ, nhân, chia. Do đó bản rõ và bản mã phải thuộc một trường nào đó để việc tính toán không ra khỏi trường. Việc quy bản rõ và bản mã về trường số thực không phải là phương án hiệu quả vì tính toán trên số thực tốn kém nhiều thời gian. Máy tính chỉ hiệu quả khi tính toán trên các số nguyên dưới dạng byte hay bít. Do đó trường Zp là một phương án được tính đến. Tuy nhiên trường Zp đòi hỏi p phải là một số nguyên tố, trong khi đó nếu biểu diễn bản rõ bản mã theo bít thì số lượng phần tử có dạng 2n lại không phải là số nguyên tố. Ví dụ, xét tập các phần tử được biểu diễn bởi các số nguyên 8 bít, như vậy có 256 phần tử. Tuy nhiên Z256 lại không phải là một trường. Nếu ta chọn trường Z251 thì chỉ sử dụng được các số từ 0 đến 250, các số từ 251 đến 255 không tính toán được. Trong bối cảnh đó, việc sử dụng trường GF(2n) là một phương án phù hợp vì trường GF(2n) cũng có 2n phần tử. Ta có thể ánh xạ giữa một hàm đa thức trong GF(2n) thành một số nhị phân tương ứng bằng cách lấy các hệ số của đa thức tạo thành dãy bít an-1an-2 a1a0. Ví dụ xét trường GF(23) với đa thức tối giản 1 tương ứng với số nguyên 3 bít như sau: Đa thức trong GF(23) Số nguyên tương ứng thập lục phân 0 000 0 1 001 1 x 010 2 x+1 011 3 x2 100 4 x2+1 101 5 x2+x 110 6 x2+x+1 111 7 Bảng phép cộng và bảng phép nhân tương ứng là 136
+ 0 1 2 3 4 5 6 7 x 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 1 0 3 2 5 4 7 6 1 0 1 2 3 4 5 6 7 2 2 3 0 1 6 7 4 5 2 0 2 4 6 3 1 7 5 3 3 2 1 0 7 6 5 4 3 0 3 6 5 7 4 1 2 4 4 5 6 7 0 1 2 3 4 0 4 3 7 6 2 5 1 5 5 4 7 6 1 0 3 2 5 0 5 1 4 2 7 3 6 6 6 7 4 5 2 3 0 1 6 0 6 7 1 5 3 2 4 7 7 6 5 4 3 2 1 0 7 0 7 5 2 1 6 4 3 Bảng nghịch đảo của phép cộng và phép nhân: a -a a-1 dạng đa dạng đa dạng đa dạng số dạng số dạng số thức thức thức 0 0 0 0 - - 1 1 1 1 1 1 x 2 x 2 x2+1 5 x+1 3 x+1 3 x2+x 6 x2 4 x2 4 x2+x+1 7 x2+1 5 x2+1 5 x 2 x2+x 6 x2+x 6 x+1 3 x2+x+1 7 x2+x+1 7 x2 4 Ngoài ra nếu xét bảng phép nhân của Z8 x 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 4 0 4 0 4 0 4 0 4 5 0 5 2 7 4 1 6 3 6 0 6 4 2 0 6 4 2 7 0 7 6 5 4 3 2 1 Thì phân bố tần suất của các số không đều. Ta có bảng so sánh sau: Số nguyên 1 2 3 4 5 6 7 Xuất hiện trong Z8 4 8 4 12 4 8 4 Xuất hiện trong GF(23) 7 7 7 7 7 7 7 Vì vậy nếu dùng GF(23) thì sẽ thuận lợn hơn cho mã hóa, tránh việc sử dụng tần suất để phá mã. 9.3.6 Tính toán trong GF(2n) Với việc biểu diễn một hàm đa thức trong GF(2n) thành một số nguyên n bít. Ta có thể thực hiện phép cộng và phép nhân đa thức như sau: 137
1) Phép cộng: cho hai đa thức ∑ ∑ Phép cộng chính là phép XOR hai dãy bít an-1an-2 a1a0 và bn-1bn-2 b1b0. 2) Phép nhân: liên quan đến phép modulo đa thức tối giản Chúng ta sẽ xem xét phép nhân hai đa thức trong trường GF(28) dùng đa thức nguyên tố 1 (dùng trong mã hóa AES). Từ đó có thể tổng quát hóa cho trường GF(2n) bất kỳ. Trước hết nhận xét rằng: [ ] 1 (vì 1 1 ) Một đa thức trong GF(28) có dạng: Suy ra: Nếu b7 = 0 thì: Nếu b7 = 1 thì: 4 3 1 Nếu viết theo dãy bít thì điều đó nghĩa là: 1 {  11 11 1 Áp dụng lặp lại như vậy để tính với k bất kỳ, và từ đó tính được Ví dụ: tính 1 ( 7 1) Phép nhân trên viết theo bít là 01010111 10000011 01010111  00000010 = 10101110 01010111  00000100 = 01011100  00011011 = 01000111 01010111  00001000 = 10001110 01010111  00010000 = 00011100  00011011 = 00000111 01010111  00100000 = 00001110 01010111  01000000 = 00011100 01010111  10000000 = 00111000 Vì vậy 01010111 10000011 = 01010111 [00000001  00000010  10000000] = 01010111  10101110  00111000 = 11000001 Vậy 1 ( 7 1) 7 6 1 9.3.7 Tính toán trong GF(2n) với phần tử sinh Ngoài cách thức tính phép cộng và phép nhân đa thức dùng phép XOR và Shift dãy bít, ta có thể tính bằng cách dùng phần tử sinh. 138
Khái niệm phần tử sinh: giá trị g được gọi là phần tử sinh của trường GF(2n) với đa thức tối giản m(x) nếu các lũy thừa (gồm 2n-1 phần tử) sinh ra các đa thức khác không của trường. Phép lũy thừa trên thực hiện modulo cho đa thức m(x). Điều kiện để g là phần tử sinh là: Ví dụ, xét lại trường GF(23) với 1 Như vậy để g là phần tử sinh thì 1. Ta thực hiện việc sinh các phần tử của trường như sau: 1 1 1 1 Biểu diễn lũy Đa thức trong Số nguyên tương thập lục thừa GF(23) ứng phân 0 0 000 0 g0 1 001 1 g1 g 010 2 g2 g2 100 4 g3 g+1 011 3 g4 g2+g 110 6 g5 g2+g+1 111 7 g6 g2+1 101 5 Dựa vào phần tử sinh ta có thể thực hiện phép nhân đa thức bằng một phép modulo 2n-1. Ví dụ, để tính 1 . Ta chuyển thành 1 (kết quả này giống với kết quả trong bảng phép nhân trong phần 9.3.4) 9.4 Mã hóa AES Mã hóa AES là một mã hóa theo khối 128 bít không sử dụng nguyên tắc của hệ mã Feistel mà sử dụng mô hình mạng SPN. AES dùng 4 phép biến đổi chính để mã hóa một khối: Add row key, Substitute bytes, Shift rows, Mix columns. Mỗi phép biến đổi nhận tham số đầu vào có kích thước 128 bít và cho ra kết quả cũng có kích thước 128 bít. AES thực hiện 4 phép biến đổi trên nhiều lần tạo thành 10 vòng biến đổi như hình bên dưới. 139
key 128 bít Bản rõ 128 bít Bản rõ 128 bít 128 128 Add round key w[0,3] Add round key R10 128 R1 Substitute bytes Expand Key Inverse sub bytes Shift rows Inverse shift rows Mix columns Inverse mix cols R9 128 128 Add round key w[4,7] Add round key 128 . Inverse sub bytes R9 Substitute bytes Inverse shift rows Shift rows . 128 Mix columns Inverse mix cols R1 128 128 Add round key w[36,39] Add round key R10 Substitute bytes Inverse sub bytes Shift rows Inverse shift rows 128 128 128 Add round key w[40,43] Add round key Bản mã 128 bít Bản mã 128 bít a) Giai đoạn mã hóa b) Giai đoạn giải mã Các phép biến đổi Substitute bytes, Shift rows, Mix columns có phép biến đổi ngược tương ứng là Inverse sub bytes, Inverse shift rows, Inverse mix cols. Riêng phép biến đổi Add row key đơn giản chỉ là phép XOR nên phép biến đổi ngược cũng là Add row key. Vận dụng các phép biến đổi ngược trên, thuật toán giải mã AES cũng gồm 10 vòng thực hiện theo chiều ngược lại. Kích thước khóa ban đầu là 128 bít (gồm 16 byte). AES dùng hàm Expand key để mở rộng kích thước khóa thành 44 word 32 bít. 44 word này được chia thành 11 cụm khóa con, mỗi khóa con 4 word làm tham số cho 11 thao tác Add row key. 140
k0 k4 k8 k12 k1 k5 k9 k13 w0 w1 w2 w3 w4 w5 w42 w43 k2 k6 k10 k14 k3 k7 k11 k15 Expand key Mỗi khối bản rõ gồm 16 byte p0 p1 p15 được tổ chức dưới dạng một ma trận 4x4 (ma trận state). Chúng ta đổi ký hiệu cho ma trận này dưới dạng s00 s10 s20 s30 s01 s11 s23 s33. p0 p4 p8 p12 S00 S01 S02 S03 p1 p5 p9 p13 S10 S11 S12 S13 p2 p6 p10 p14 S20 S21 S22 S23 p3 p7 p11 p15 S30 S31 S32 S33 Các phép biến đổi Add row key, Substitute bytes, Shift rows, Mix columns sẽ thực hiện trên ma trận S 4x4 này. Các phép tính số học trong AES được thực hiện trong trường GF(28) với đa thức tối giản là 1. Từ đây về sau ta chỉ nói đơn giản là GF(28). Phần sau trình bày chi tiết các thao tác Add row key, Substitute bytes, Shift rows, Mix columns và Expand key. 9.4.1 Substitute bytes Trong phần này, ta sử dụng một bảng tra cứu 16 16 byte (gọi là S-box). Bảng này được thiết lập như sau: Bước 1: điền các con số từ 0 đến 255 vào bảng theo từng hàng. Vậy hàng 0 gồm các con số {00}, {01}, {0F} (thập lục phân). Hàng 1 gồm các con số {10}, {11}, , {1F}. Điều này có nghĩa là tại hàng x cột y có giá trị {xy} Bước 2: thay thế mỗi byte trong bảng bằng giá trị nghịch đảo trong trường GF(28). Quy ước nghịch đảo của {00} cũng là {00} Bước 3: Đối với mỗi byte trong bảng, ký hiệu 8 bít là b7b6b5b4b3b2b1b0. Thay thế mỗi bít bằng giá trị được tính sau:      Với ci là bít thứ i của số {63}, tức 11 11. Việc tính toán trên tương đương với phép nhân ma trận sau trên GF(28) (B’ = XB  C): 141
b’0 1 0 0 0 1 1 1 1 b0 1 b’1 1 1 0 0 0 1 1 1 b1 1 b’2 1 1 1 0 0 0 1 1 b2 0 b’3 1 1 1 1 0 0 0 1 b3 0 = + b’4 1 1 1 1 1 0 0 0 b4 0 b’5 0 1 1 1 1 1 0 0 b5 1 0 0 1 1 1 1 1 0 b 1 b’6 6 0 0 0 1 1 1 1 1 b7 0 b’7 Trong đó phép cộng thực hiện như phép XOR. Hình dướ i trình bày nội dung bảng S-box sau khi tính toán. 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0 2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15 3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75 4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84 5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF 6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8 7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2 8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73 9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB {95} {8A} {2A} A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79 B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 C BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A D 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16 Ví dụ: xét giá trị {95}, tại bước 1, giá trị tại dòng 9 cột 5 là {95}, sau bước 2 tính nghịch đảo giá trị của ô này là {8A} có dạng nhị phân là 10001010. Thực hiện phép nhân ma trận: 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 + = + = 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 Kết quả dưới dạng thập lục phân là {2A} 142
Dựa trên bảng tra cứu S-box, phép biến đổi Substitute bytes thực hiện như sau: Mỗi byte trong ma trận state S, dưới dạng thập lục phân là {xy}, được thay thế bằng giá trị trong bảng S-box tại dòng x cột y. y x S00 S01 S02 S03 S00 S01 S02 S03 S10 S11 S12 S13 S10 S11 S12 S13 S20 S21 S22 S23 S20 S21 S22 S23 S30 S31 S32 S33 S30 S31 S32 S33 Sau đây là một ví dụ về phép substitute bytes EA 04 65 85 87 F2 4D 97 83 45 5D 96 EC 6E 4C 90 5C 33 98 B0 4A C3 46 E7 F0 2D AD C5 8C D8 95 A6 Phép biến đổi ngược Inverse sub bytes: Trước tiên, ta cũng phải xây dựng một bảng Inverse S-box (IS-box). Nghĩa là nếu với đầu vào {95}, S-box cho ra kết quả {2A}, thì với đầu vào là {2A}, IS-box sẽ cho ra lại kết quả {95}. Việc xây dựng IS-box cũng giống như xây dựng S-box tại bước 1 và bước 2. Tại bước 3, IS-box thực hiện phép thay thế sau:    Với di là bít thứ i của số {05}, tức 1 1. Và phép nhân ma trận tương đương là (B = YB’  D): b0 0 0 1 0 0 1 0 1 b'0 1 b1 1 0 0 1 0 0 1 0 b’1 0 b2 0 1 0 0 1 0 0 1 b’2 1 b3 1 0 1 0 0 1 0 0 b’3 0 = + b4 0 1 0 1 0 0 1 0 b’4 0 b5 0 0 1 0 1 0 0 1 b’5 0 1 0 0 1 0 1 0 0 b’ 0 b6 6 b 0 1 0 0 1 0 1 0 b’7 0 7 143
Hình dưới trình bày nội dung bảng IS-box 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB 1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB 2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E {2A} {95} 3 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25 4 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92 5 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84 6 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06 7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B 8 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73 9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E A 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4 C 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F D 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61 F 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D Như vậy phép biến đổi Inverse sub bytes thực hiện như sau: Mỗi byte trong ma trận state S, dưới dạng thập lục phân là {xy}, được thay thế bằng giá trị trong bảng IS-box tại dòng x cột y. Để chứng minh Inverse sub bytes là phép biển đổi ngược của Substitute bytes, ta cần chứng minh Y(XB  C)  D = B, nghĩa là YXB  YC  D = B. Ta có 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 b0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 b1 0 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 b2 1 0 1 0 0 1 0 0 1 1 1 1 0 0 0 1 b3 + 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 b4 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 b5 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 b 6 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 b7 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 b0 1 1 b0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 b1 0 0 b1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 b2 1 1 b2 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 b3 0 0 b3 + = + + = 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 b4 0 0 b4 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 b5 0 0 b5 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 b6 0 0 b6 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 b7 0 0 b7 (YXB = IB và YC = D) Mục đích của Substitute bytes : 144
Bảng S-box dùng để chống lại hình thức tấn công known-plaintext. Giữa input và output của phép Substitute bytes không thể mô tả bằng một công thức toán đơn giản. (xem phần mã khối an toàn lý tưởng trong chương 3) 9.4.2 Shift rows Thao tác Shift rows thực hiện hoán vị các byte trong ma trận state theo cách thức sau: - Dòng thứ nhất giữ nguyên - Dòng thứ 2 dịch vòng trái 1 byte - Dòng thứ 3 dịch vòng trái 2 byte - Dòng thứ 4 dịch vòng trái 3 byte S00 S01 S02 S03 S10 S11 S12 S13 S20 S21 S22 S23 S30 S31 S32 S33 Thao tác Inverse shift rows thực hiện ngược lại, các dòng thứ 2, thứ 3, thứ 4 được dịch vòng phải tương ứng 1 byte, 2 byte và 3 byte. Mục đích của Shift rows: Xáo trộn các byte để tạo các cột khác nhau trước khi sử dụng cột cho thao tác Mix columns. 9.4.3 Mix columns Thao tác Mix column biến đổi độc lập từng cột trong ma trận state bằng một phép nhân đa thức. Một cột trong ma trận state có thể xem là một đa thức bậc 3, ví dụ cột 1 của ma trận viết dưới dạng đa thức là: Đa thức trên được nhân với đa thức: 3 1 1 2 Trong đó phép cộng và nhân các hệ số được thực hiện trong trường GF(28). Đa thức kết quả có bậc lớn hơn 3 (ví dụ hệ số của bậc 6 là {03}s01), tuy nhiên ta chỉ cần sử dụng 4 hệ số cho giá trị cột mới nên đa thức kết quả sẽ được modulo thêm cho đa thức 1. Bốn byte hệ số của được thay thế cho bốn byte ban đầu trong cột. 145
S00 S01 S02 S03 S00 S01 S02 S03 S10 S11 S12 S13 S10 S11 S12 S13 S20 S21 S22 S23 S20 S21 S22 S23 S30 S31 S32 S33 S30 S31 S32 S33 Phép nhân đa thức trên có thể biểu diễn dưới dạng phép nhân ma trận như sau: s’01 02 03 01 01 s01 s’11 01 02 03 01 s11 = s’21 01 01 02 03 s21 s’31 03 01 01 02 s31 Hình sau là một ví dụ về phép Mix columns 87 F2 4D 97 47 40 A3 4C 6E 4C 90 EC 37 D4 70 9F 46 E7 4A C3 94 E4 3A 42 A6 8C D8 95 ED A5 A6 BC Trong phép biến đổi ngược Inverse mix cols, mỗi cột của ma trận state được nhân với đa thức 9 và modulo cho đa thức 1. Hay viết dưới dạng ma trận s’01 0E 0B 0D 09 s01 s’11 09 0E 0B 0D s11 = s’21 0D 09 0E 0B s21 s’31 0B 0D 09 0E s31 Có thể dễ dàng kiểm tra các tính chất sau trong GF(28) 1 1 và 0E 0B 0D 09 02 03 01 01 1 0 0 0 09 0E 0B 0D 01 02 03 01 0 1 0 0 = 0D 09 0E 0B 01 01 02 03 0 0 1 0 0B 0D 09 0E 03 01 01 02 0 0 0 1 và từ đó chứng minh được Inverse mix cols là phép biến đổi ngược của Mix columns Mục đích của Mix columns: Việc nhân mỗi cột với đa thức và modulo là cho mỗi byte trong cột kết quả đều phụ thuộc vào bốn byte trong cột ban đầu. Thao tác Mix columns kết hợp với Shift 146
rows đảm bảo rằng sau một vài vòng biến đổi, 128 bít trong kết quả đều phụ thuộc vào tất cả 128 bít ban đầu. Điều này tạo ra tính khuếch tán (diffusion) cần thiết cho mã hóa. 9.4.4 Add row key Trong thao tác Add row key, 128 bít của ma trận state sẽ được XOR với 128 bít của khóa con của từng vòng. Vì sử dụng phép XOR nên phép biến đổi ngược của Add row key cũng chính là Add row key. Việc kết hợp với khóa bí mật tạo ra tính làm rối (confusion) của mã hóa. Sự phức tạp của thao tác Expand key giúp gia tăng tính làm rối này. 9.4.5 Expand key Thao tác Expand key có input là 16 byte (4 word) của khóa bí mật, và sinh ra một mảng 44 word (176 byte). 44 word này được sử dụng cho 11 vòng mã hóa của AES, mỗi vòng dùng 4 word. Từ bốn word đầu vào w0w1w2w3, trong lần lặp đầu tiên thao tác Expand key sinh ra bốn word w4w5w6w7, lần lặp thứ 2 từ w4w5w6w7 sinh ra w8w9w10w11 , cứ như thế cho đến lần lặp thứ 10 sinh ra bốn word cuối cùng w40w41w42w43 như hình vẽ bên dưới k0 k4 k8 k12 k1 k5 k9 k13 If i mod 4 = 0: k2 k6 k10 k14 g = SubWord(RotWord(wi-1))  Rcon[i/4] k3 k7 k11 k15 wi = wi-4  g If i mod 4 0: wi = wi-4  wi-1 w0 w1 w2 w3 g      w4 w5 w6 w7 g       w8 w9 w10 w11  Trong mỗi lần lặp để sinh ra 4 word, word đầu tiên sinh ra theo quy tắc w = w  g i i-4 với g = SubWord(RotWord(wi-1))  Rcon[i/4]. Ba word tiếp theo sinh ra theo quy tắc wi = wi-4  wi-1. Sau đây chúng ta sẽ tìm hiểu các hàm SubWord, RotWord và mảng Rcon. RotWord: dịch vòng trái một byte. Giả sử word đầu vào có 4 byte là [b0, b1, b2, b3] thì kết quả của RotWord là [b1, b2, b3, b4]. SubWord: thay thế mỗi byte trong word đầu vào bằng cách tra cứu bảng S-box trong thao tác Substitute Bytes. 147
Rcon: là một mảng hằng số. Mảng này gồm 10 word ứng với 10 vòng AES. Bốn byte của một phần tử Rcon[ j] là (RC[ j], 0, 0, 0) với RC[ j] là mảng 10 byte như sau: j 1 2 3 4 5 6 7 8 9 10 RC[ j] 1 2 4 8 10 20 40 80 1B 36 (RC[ j] = RC[ j-1]*2 với phép nhân thực hiện trong GF(28) Mục đích của Expand key: dùng để chống lại known-plaintext attack - Biết một số bít của khóa hay khóa con cũng không thể tính các bít còn lại. - Không thể tính ngược: biết một khóa con cũng không thể tính lại các khóa con trước đó. - Tính khuếch tán: một bít của khóa chính tác động lên tất cả các bít của các khóa con. 9.4.6 Kết luận Phương pháp mã hóa AES đơn giản, có thể thực hiện hiệu quả trên các vi xử lý 8 bít (dùng trong smartcard) cũng như trên các vi xử lý 32 bít, chỉ dùng phép XOR và phép Shift bít. Đây chính là yếu tố cơ bản để phương pháp này được chọn làm chuẩn mã hóa của Hoa Kỳ. Mã hóa AES còn có 1 số biến thể khác cho phép chiều dài của khóa có thể là 192 bít và 256 bít. Nếu khóa là 192 bít thì kích thước khóa mở rộng là 52 word 4 byte và do đó AES thực hiện 12 vòng, nếu khóa là 256 bít thì kích thước khóa mở rộng là 60 word và AES thực hiện 14 vòng. 148
CHƢƠNG 10.MÃ HÓA ĐƯỜNG CONG ELLIPTIC Trong chương 4 về mã hóa khóa công khai, chúng ta đã tìm hiểu phương pháp mã hóa RSA và phương pháp trao đổi khóa Diffie-Hellman. RSA dùng hàm một chiều là phép phân tích một số lớn thành tích hai thừa số nguyên tố. Diffie-Hellman dùng hàm một chiều là hàm logarit rời rạc. Trong chương này chúng ta tiếp tục tìm hiểu một loại hàm một chiều khác dựa trên số học Elliptic. Từ đó chúng ta sẽ xây dựng một phương pháp mã hóa đường cong Elliptic (ECC) và phương pháp trao đổi khóa phiên ECDiffie-Hellman. Đối với phương pháp RSA, để bảo đảm an toàn, chúng ta phải chọn số N lớn (1024 bít), điều này khiến cho RSA thực hiện chậm. Mã hóa ECC giải quyết vấn đề này khi dùng các tham số có kích thước ngắn hơn (168 bít) tuy nhiên vẫn đảm bảo độ an toàn như RSA 1024 bít. 10.1 Đường cong Elliptic trên số thực Đường cong Elliptic là đường cong có dạng: Trước khi khảo sát đồ thị của đường cong Elliptic, chúng ta xem lại đường bậc 3 sau: Nếu đơn điệu tăng. Nếu có 4 trường hợp sau: đặt 4 27 Từ đó chúng ta có các trường hợp sau đây của đường cong Elliptic (không sử dụng trường hợp =0 vì lúc này đường cong bị gãy): Hình dưới minh họa hai đường cong Elliptic 1 149
-1 1 -1 0 1 1 Trong đường cong Elliptic, chúng ta định nghĩa thêm một điểm O (điểm vô cực). Gọi E(a, b) là tập các điểm thuộc đường cong cùng với điểm O. ta định nghĩa phép cộng trên tập các điểm thuộc E(a, b) như sau: 1) Điểm O là phần tử đơn vị của phép cộng. Như vậy với . Trong phần tiếp theo, ta giả định . 2) Phần tử nghịch đảo của điểm P trong phép cộng, ký hiệu – P, là điểm đối xứng với P qua trục hoành, như vậy 3) Với 2 điểm P, Q bất kỳ, kẻ một đường thẳng đi qua P và Q thì sẽ cắt đường cong Elliptic tại một điểm thứ 3 là điểm S. Phép cộng P và Q sẽ là Q S Q S P P P R= P+Q= -S R= P+Q= -S Q Trong trường hợp P và Q đối xứng qua trục hoành, hay nói cách khác thì đường thẳng nối P, Q sẽ cắt đường cong Elliptic tại vô cực, hay . Điều này phù hợp với định nghĩa 2. 4) Để tính , ta vẽ đường thẳng tiếp tuyến với đường cong Elliptic tại P, đường thẳng này cắt đường cong tại điểm S, lúc đó P -R R = P+P 150
Có thể thấy, tập E(a, b) cùng với phép cộng định nghĩa như trên tạo thành một nhóm Abel Tính giá trị của phép cộng: Gọi tọa độ của điểm , của điểm . Ta tính tọa độ điểm như sau: Đặt hệ số góc đường thẳng là : a t nh ược: Chứng minh: Để ngắn gọn, ký hiệu . Ta có: (1) (2) (3) (điểm S thuộc đường thẳng nối P và Q) (4) Thay (4) vào (3): 2 Thay vào phương trình trên, ta có: 2 2 (5) Lấy (2) trừ cho (1) ta có: 2 2 (6) Thay (6) vào (5) ta có: Hay nói cách khác và , từ đó ta có đpcm. Tương tự, thực hiện tính tọa độ của điểm , khi ta có: 151
3 ( ) 2 2 3 ( ) 2 Chứng minh: Không mất tổng quát xét một nửa đường cong elliptic: √ Gọi là hệ số góc của tiếp tuyến với đường cong elliptic tại điểm P, như vậy: 1 3 2 3 2 Tương tự như trong cách tính ta cũng có phương trình (5), trong đó (x3, y3) là tọa độ điểm S: 2 3 2 ( 2 ) Vậy ta có: 2 và từ đó suy ra đpcm. 10.2 Đường cong Elliptic trên trường Zp. Đường cong Elliptic trên trường Zp là đường cong có các hệ số thuộc trường Zp, đường cong này có dạng: Ví dụ trong trường Z23, chọn 1 1 9 7 ta có: 7 23 9 9 1 23 49 23 739 23 3 Khác với đường cong Elliptic trong trường số thực, chúng ta không thể biểu diễn đường cong Elliptic Zp bằng đồ thị hàm số liên tục. Bảng bên dưới liệt kê các điểm (x, y) của đường cong trong trường Z23 với a=1, b=1: (0, 1) (6, 4) (12, 19) (0, 22) (6, 19) (13, 7) (1, 7) (7, 11) (13, 16) (1, 16) (7, 12) (17, 3) (3, 10) (9, 7) (17, 20) (3, 13) (9, 16) (18, 3) (4, 0) (11, 3) (18, 20) 152
(5, 4) (11, 20) (19, 5) (5, 19) (12, 4) (19, 18) Cũng tương tự như khái niệm đối xứng qua trục hoành của đường cong Elliptic số thực, đường cong Elliptic Zp cũng đối xứng theo nghĩa đối xứng modulo. Giả sử điểm (x, y) thuộc đường cong Elliptic Zp trên thì điểm (x, p - y) cũng thuộc đường cong trên vì: 2 Ví dụ (1, 7) đối xứng với (1, 16) vì 7+16 = 0 mod 23. Hình vẽ bên dưới minh họa tính đối xứng này. 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Các điểm đối xứng với nhau qua đường y = 11.5 . Riêng điểm (4, 0) xem như là đối xứng với chính nó. Cũng tương tự như nhóm Abel định nghĩa trên đường cong Elliptic số thực, chúng ta cũng định nghĩa một nhóm Abel gồm các điểm của đường cong Elliptic Zp cùng với điểm vô cực O. 1) Điểm O là phần tử đơn vị của phép cộng. . 2) Phần tử nghịch đảo của điểm P trong phép cộng, ký hiệu – P, là điểm đối xứng với P, như vậy 3) Với 2 điểm P, Q bất kỳ, phép cộng được xác định bằng công thức: Trong đó: 153
3 ( ) { 2 Chú ý rằng khái niệm kẻ đường thẳng không còn áp dụng trong đường cong Elliptic Zp. Do đó, với cách tính trên, ta cần chứng minh tính đóng, tức là điểm thuộc đường cong. Xét trường hợp : (1) (2) (3) (x3, y3 là tọa độ điểm S) (4) Ta cần chứng minh (x3, y3) thuộc đường cong, nghĩa là: 2 2 (5) Vì p là số nguyên tố nên tồn tại phần tử nghịch đảo của trong phép modulo p. Do đó (5) tương đương với: 2 (6) Để chứng minh (6), lấy (2) trừ cho (1) ta cũng có: 2 2 (7) Từ (3) ta có: Thay (7) vào phương trình trên ta có: 2 2 Vậy (6) đúng, nghĩa là điểm thuộc đường cong, do đó cũng thuộc đường cong. Chứng minh tương tự cho trường hợp . Ví dụ: trong 1 1 , chọn P = (3,10), Q=(9,7), vậy: 23 23 2 4 23 11 11 3 9 23 17 154
11 3 17 1 23 2 (17, 20) là điểm thuộc đường cong 1 1 10.3 Đường cong Elliptic trên trường GF(2m). Đường cong Elliptic trên trường GF(2m) là đường cong có các hệ số thuộc trường GF(2m), đường cong này có dạng hơi khác so với trên Zp: 2 Đường cong trên trường số thực Bây giờ chúng ta sẽ xét tập gồm các điểm trên đường cong Elliptic này cùng với điểm vô cực O. Ví dụ, xét trường GF(24) với đa thức tối giản là 1. Phần tử sinh g của trường này có điều kiện 1 . Bảng các lũy thừa của g là: Biểu diễn Đa thức trong Số nhị Biểu diễn Đa thức Số nhị lũy thừa GF(23) phân lũy thừa trong GF(23) phân 0 0 0000 g7 g3+g+1 1011 g0 1 0001 g8 g2+ 1 0101 g1 g 0010 g9 g3 + g 1010 g2 g2 0100 g10 g2+g+1 0111 g3 g3 1000 g11 g3+ g2+g 1110 g4 g+1 0011 g12 g3+ g2+g+1 1111 g5 g2+ g 0110 g13 g3+ g2 + 1 1101 g6 g3 + g2 1100 g14 g3+ 1 1001 Xét ví dụ về đường cong Elliptic trên GF(24): 1 1 Bảng bên dưới liệt kê các điểm thuộc đường cong này (0, 1) (g5, g3) (g9, g13) (1, g6) (g5, g11) (g10, g) (1, g13) (g6, g8) (g10, g8) (g3, g8) (g6, g14) (g12, 0) (g3, g13) (g9, g10) (g12, g12) Tương tự như nhóm Abel , chúng ta cũng xây dựng một nhóm Abel m gồm các điểm của đường cong Elliptic GF(2 ) cùng với điểm vô cực O. 1) Điểm O là phần tử đơn vị của phép cộng. . 155
2) Phần tử nghịch đảo của điểm P trong phép cộng, ký hiệu – P, là điểm đối xứng với P, ký hiệu P 3) Với 2 điểm P, Q bất kỳ (P Q) phép cộng được xác định bằng công thức: Trong đó: 4) phép cộng được xác định bằng công thức: 1 Trong đó: 10.4 Đường cong Elliptic trong mã hóa - ECC Đối với mã hóa đường cong Elliptic, chúng ta xây dựng hàm một chiều như sau: Trong nhóm Abel xây dựng từ đường cong Elliptic Zp, xét phương trình: (điểm Q là tổng của k điểm P, k < p) Cho trước k và P, việc tính Q thực hiện dễ dàng. Tuy nhiên nếu cho trước P và Q, việc tìm ra k là công việc khó khăn. Đây chính là hàm logarit rời rạc của đường cong Elliptic. Ví dụ: Xét nhóm 9 17 với phương trình : 23 9 7 23 Cho điểm P=(16, 5), Q=(4, 5), chúng ta chỉ có cách là vét cạn các giá trị của k từ 2 đến p-1 để tìm ra k: 16 5 2 2 2 3 14 14 4 19 2 5 13 1 6 7 3 7 8 7 8 12 17 9 4 5 Vì 9P = Q nên ta xác định được k = 9. Trong thực tế chúng ta sẽ sử dụng đường cong Elliptic Zp với giá trị p lớn, sao cho việc vét cạn là bất khả thi. Hiện nay người ta đã tìm ra phương pháp tìm k nhanh hơn vét cạn là phương pháp Pollar rho. Dựa vào hàm một chiều trên chúng ta có 2 cách sử dụng đường cong Elliptic trong lĩnh vực mã hóa là trao đổi khóa EC Diffie-Hellman và mã hóa EC. 10.4.1 Trao đổi khóa EC Diffie-Hellman Trong chương 4 chúng ta đã tìm hiểu vấn đề trao đổi khóa Diffie-Hellman dựa trên tính một chiều của hàm logarit rời rạc. Trong phần này chúng ta cũng xem xét một phương thức trao đổi khóa tương tự dùng hàm một chiều của đường cong Elliptic. Trước tiên ta chọn một số nguyên q lớn, với q là số nguyên tố (nếu sử dụng đường m m cong Elliptic Zp) hoặc q có dạng 2 (nếu chọn đường cong GF(2 )), và chọn 2 tham số a, b tương ứng để tạo thành nhóm . Ta gọi G là điểm cơ sở của nhóm nếu tồn tại một số nguyên n sao cho . Số nguyên n nhỏ nhất như vậy được gọi là hạng của G. 156
Trong trao đổi khóa EC Diffie-Hellman, ta chọn một điểm G có hạng n lớn, và giao thức trao đổi khóa giữa Alice và Bob tiến hành như sau: 1) Alice chọn một số và giữ bí mật số này. Sau đó trong Alice tính và gửi cho Bob. 2) Tương tự Bob chọn một số bí mật , tính và gửi cho Alice. 3) Alice tạo khóa phiên bí mật là 4) Bob tạo khóa phiên bí mật là (nhóm Abel có tính giao hoán) giống với khóa của Alice. Trudy có thể chặn được , tuy nhiên chỉ có thể tính được: Để tính được , Trudy phải tìm được từ . Tuy nhiên điều này là bất khả thi như ta đã thấy ở phần trên. Chú ý: khóa phiên K là một điểm trong đường cong Elliptic, để sử dụng khóa này cho mã hóa đối xứng như DES hay AES, ta cần chuyển K về dạng số thường. 10.4.2 Mã hóa và giải mã EC Tương tự như vấn đề trao đổi khóa, trong vấn đề mã hóa/giải mã, ta cũng chọn các tham số để tạo một nhóm Abel và chọn một điểm cơ sở G có hạng n lớn. Các thành phần khóa khóa riêng và công khai trong mã hóa EC được định nghĩa như sau: Trong đó và với d là một số bí mật do người sinh khóa chọn. Do tính chất của hàm một chiều từ E và G không thể suy ra được d. Từ đó chúng ta có hai cách thức thực hiện mã hóa/ giải mã như sau: 1) Phương pháp Elgamal: Giả sử Alice muốn gửi một thông điệp M cho Bob, trước tiên Alice chuyển M từ dạng dãy bít sang dạng điểm PM =(x, y). Bản mã CM (dùng khóa công khai của Bob) được tính là một cặp điểm như sau: với k là một số ngẫu nhiên do Alice chọn Để giải mã dùng khóa riêng, Bob sẽ nhân điểm thứ nhất trong CM với d, sau đó lấy điểm thứ hai trừ cho kết quả: Trong phương thức mã hóa, Alice đã che giấu PM bằng cách cộng PM với kE. Để giải mã, Bob cần trừ ra lại kE. Thay vì gửi trực tiếp k cho Bob để Bob tính kE (Trudy có thể chặn được), Alice gửi một dấu hiệu là kG . Dựa vào kG và d, Bob có thể tính kE. Còn Trudy, dù biết G và kG, tuy nhiên vẫn không thể tính được k do tính chất của hàm một chiều. Ví dụ: chọn p = 751, a = 1, b = 188 ta có đường cong Elliptic trên Z751 như sau 751 188 751 157
Chọn điểm cơ sở là G =(0, 376). Giả sử Alice cần mã hóa bản rõ là điểm PM = (562, 201) dùng khóa công khai E = (201, 5). Alice chọn k = 386. Ta có: 386(0, 376) = (676, 558) (562,201) + 386(201, 5) = (385, 328) Vậy bản mã là cặp điểm { (676, 558), (385, 328) } 2) Phương pháp Menezes - Vanstone: Thông điệp M của Alice được tách thành hai phần M=(m1, m2) sao cho m1, m2 Zp. Alice chọn một số ngẫu nhiên k, kết hợp với khóa công khai của Bob, Alice tính điểm P như sau: Bản mã CM gồm ba thành phần: Để giải mã dùng khóa riêng, từ dấu hiệu kG, Bob tính: và từ đó tính nghịch đảo của trong phép modulo p. Cuối cùng, bản giải mã là: Tương tự như phương pháp Elgamal, dù biết G và kG, Trudy cũng không thể tính được k để tính P. 10.4.3 Độ an toàn của ECC so với RSA Hiện nay, phương pháp nhanh nhất để tính logarit đường cong Elliptic (tính k biết G và kG) là phương pháp Pollar rho. Bảng sau đây liệt kê kích thước khóa của phương pháp ECC và phương pháp RSA dựa trên sự tương đương về chi phí phá mã. Mã hóa đối xứng Mã hóa ECC Mã hóa RSA (số bít của khóa) (số bít của n) (số bít của N) 56 112 512 80 160 1024 112 224 2048 128 256 3072 192 384 7680 256 512 15360 Như vậy với cùng một độ an toàn thì mã hóa ECC chỉ dùng các phép tính có số bít nhỏ hơn nhiều lần so với mã hóa RSA. 10.5 Chuẩn chữ ký điện tử (Digital Signature Standard – DSS) Trong chương 5, chúng ta đã tìm hiểu về cách sử dụng hàm hash cùng với mã hóa RSA để tạo chữ ký điện tử. Hình bên dưới trình bày lại mô hình này: 158
Bên gửi Bên nhận M M M DS Tính Hash HB Tính Hash HA Mã hóa Giải mã HA So sánh KRA KUA Bộ sinh khóa DS: Data signature – chữ ký điện tử DSS là một cách thực hiện chữ ký điện tử khác được đề xuất vào năm 1991. Khác với RSA, DSS không thể dùng để mã hóa hay trao đổi khóa. Tuy nhiên về cơ bản DSS cũng thuộc lĩnh vực khóa công khái. Mô hình thực hiện của DSS được minh họa trong hình bên dưới. Bên gửi Bên nhận M M M s HB Tính Hash Tính r Sign Hash HA Verify So sánh k KUG KRA KUA KUG Bộ sinh khóa Phương pháp DSS cũng dùng hàm Hash. k là một số ngẫu nhiên do bên gửi tự chọn. KUG là một tập các tham số công khai sử dụng chung cho tất cả các bên. Thủ tục Sign sử dụng khóa bí mật để cho ra chữ ký gồm hai tham số s và r. Thủ tục Verify sử dụng khóa công khai để cho ra một thông số. Thông số này được so sánh với r để kiểm tra chữ ký. Chi tiết của thủ tục Sign và Verify được gọi là thuật toán ký (Digital Sinature Algorithm – DSA), được trình bày trong phần tiếp theo. DSA cũng sử dụng hàm một chiều là phép logarith rời rạc như được dùng trong trao đổi khóa Diffie-Hellman. Tuy nhiên cách thức thực hiện thì theo sơ đồ Elgamal-Schnor. Sơ đồ này gồm các thông số như sau: Thông số công khai toàn cục (KUG): - p là số nguyên tố, 2 2 512 1 24 và L chia hết cho 64. (nghĩa là số bít của p từ 512 đến 1024 và chia hết cho 64) - q là một thừa số nguyên tố của p-1, q có chiều dài 160 bít - với h là số nguyên bất kỳ trong khoảng (1, p-1) và 1. Khóa riêng của người gửi (KRA): là số ngẫu nhiên 1 159
Khóa công khai của người gửi (KUA): . Do tính một chiều của logarith rời rạc từ y, g và p không thể tính lại khóa riêng x Số ngẫu nhiên 1 Hàm Sign: - 1 . - 2 M là thông điệp cần gửi, H là hàm SHA-1 - Output của hàm Sign là cặp (r, s) đóng vai trò là chữ ký điện tử Hàm Verify (s’ , r’, M’ là các giá trị người nhận nhận được): - 3 . - 1 [ ] - 2 - Output của hàm verify: 4 [ ] được so sánh với , nếu khớp thì M’ = M chính là thông điệp của người gửi. Chúng ta có thể biểu diễn lại hàm Sign và Verify trên bằng hình bên dưới: p q g r Tính M’ k f1 Hash p q g s' q r' s v f3 f4 M Tính f2 Hash so sánh x q a) Quá trình ký b) Quá trình kiểm tra 160
CHƢƠNG 11.MỘT SỐ VẤN ĐỀ AN TOÀN BẢO MẬT 11.1 Giấu tin trong ảnh số Tương tự như mã hóa - cryptography, giấu tin - steganography cũng là một cách thức nhằm che giấu thông tin để cho người ngoài không nhận biết. Cách thực hiện của mã hóa là biến đổi dữ liệu thành một dạng không nhận ra, còn cách thực hiện của giấu tin là sử dụng một vật mang, sau đó đưa thông tin vào vật mang này nhằm che giấu thông tin, người khác không nhận biết được là có thông tin trong vật mang đó. Phần này trình bày một kỹ thuật giấu tin đơn giản, trong đó vật mang là một ảnh Bitmap. Tên gọi của kỹ thuật này là LSB (Least Significant Bit). Trên máy tính, một tấm ảnh được biểu diễn dưới dạng một ma trận 2 chiều các điểm ảnh. Mỗi điểm ảnh mang một giá trị màu sắc xác định (xanh, đỏ, vàng, ). Tập hợp các giá trị màu sắc của các điểm ảnh này tạo nên cảm nhận của con người về nội dung tấm ảnh. Ở đây chúng ta chỉ xem xét một định dạng ảnh Bitmap phổ biến là định dạng RGB 24 bít, tức mỗi điểm ảnh là một giá trị 24 bít của 3 màu đỏ (R), xanh lá (G), và xanh lam (B), mỗi màu 8 bít. Sự kết hợp 3 màu này tạo thành màu sắc mong muốn. Như vậy mỗi màu có 255 giá trị biểu diễn mức độ đóng góp của màu đó vào màu sắc cuối cùng. Ví dụ: R=255: màu sắc có hàm lượng đỏ cao (đỏ, đỏ tươi, cam, hồng ) R=0: màu sắc không có hàm lượng đỏ (xanh, xanh da trời, xanh lá, xanh lơ ) G=255: màu sắc có hàm lượng xanh lá cây cao. Bảng dưới là ví dụ một số màu sắc kết hợp từ 3 màu R,G,B: (R, G, B) Màu 255, 0, 0 Đỏ 0, 255, 0 Xanh lá 0, 0, 255 Xanh lam 0, 0, 0 Đen 255, 255, 255 Trắng 255, 255, 0 Vàng 128, 0, 0 Đỏ sậm 255, 128, 0 Cam Mỗi màu R, G, B được biểu diễn bởi 8 bít, do đó nếu ta thay đổi bít cuối cùng (bít thứ 8, least significant bit) thì giá trị màu chỉ thay đổi một đơn vị, ví dụ: 255 254, 198 199, 25 24, 72 73, Việc thay đổi này có tác động rất ít đến màu sắc cuối cùng mà mắt người không phân biệt được. Đây là đặc điểm chính để tiến hành giấu tin vào ảnh bitmap, 1 bít dữ liệu được giấu vào 8 bít màu. Ví dụ: Giá trị màu R Bít giấu Màu kết quả 0 00110000 (24) 00110001 (25) 1 00110001 (25) 0 01001000 (72) 01001000 (72) 1 01001001 (73) 161
Một điểm ảnh có thể giấu được 3 bít dữ liệu. Do đó, một tấm ảnh RGB 24 bít kích thước có thể giấu được 3 8 byte dữ liệu. Dĩ nhiên cách giấu tin như trên là rất đơn giản, nếu người ngoài biết được quy tắc giấu thì có thể do ra nội dung được giấu. Trong thực tế, người ta dùng một khóa bí mật và dựa trên khóa này để lựa chọn ra một số điểm ảnh dùng cho việc giấu tin mà thôi. Ngoài ảnh số, âm thanh cũng có thể dùng để giấu tin vì con người cũng không thể phát hiện ra những sự thay đổi nhỏ trong tín hiệu âm thanh. 11.2 Lỗi phần mềm Các phần mềm luôn luôn có lỗi. Những lỗi này làm cho phần mềm hoạt động không như ý muốn người dùng. Tàu hạ cánh Mars Lander của NASA đã đâm vào sao Hỏa do lỗi phần mềm trong việc chuyển đổi từ đơn vị đo Anh sang đơn vị metric. Lỗi trong phần mềm quản lý hành lý khiến sân bay Denver khai trương muộn 11 tháng với thiệt hại 1 triệu USD/ngày. Trong phần này chúng ta quan tâm đến một số loại lỗi phần mềm mà hacker có thể lợi dụng để xâm nhập hệ thống thực hiện các hành vi phá hoại. 11.2.1 Tràn bộ đệm (Buffer Overflow) Lỗi tràn bộ đệm thường xảy ra đối với loại dữ liệu mảng, khi dữ liệu nhập vào vượt quá kích thước mảng. Ví dụ chương trình sau: void checkserial() { char sn[16]; scanf(‚%s‛, sn); } int main() { checkserial(); int i= 7; return 0; } Khi hàm main() gọi hàm checkserial(), trước tiên địa chỉ của lệnh i= 7 sẽ được push vào stack để sau khi hàm checkserial thực hiện xong thì máy tính có thể thi hành tiếp lệnh i= 7. Sau đó, máy tính dành tiếp 16 byte trong stack cho mảng sn. Hình sau minh họa tình trạng bộ nhớ. 162
Code segment 120 checkserial() 128 i=7 hàm main() 132 ret IP 200 scanf(‚%s‛,sn) hàm checkserial() ret SP 300 P Vùng nhớ 3F0 cho biến sn 400 401 128 Stack segment Sau khi hàm checkserial thực hiện xong, lệnh RET sẽ nạp lại giá trị 128 tại địa chỉ 401 trong stack vào con trỏ lệnh IP để quay về lại lệnh i= 7. Nếu trong hàm checkserial, người sử dụng nhập vào chuỗi ít hơn 16 ký tự thì chương trình hoạt động bình thường, tuy nhiên nếu người sử dụng nhập vào chuỗi 16 ký tự trở lên thì lúc này ô nhớ 401 sẽ bị đè bởi ký tự thứ 16, tình trạng tràn bộ đệm xảy ra. Lúc này khi lệnh RET của hàm checkserial thực hiện, con trỏ lệnh IP sẽ có 1 giá trị khác chứ không phải là 128, do đó lệnh i= 7 sẽ không được thực hiện. Hacker có thể lợi dụng điều này để tiến hành các hoạt động phá hoại. Xét chương trình cụ thể sau: void checkserial() { char sn[16]; printf(‚\nEnter a serial number\n‛); scanf(‚%s‛, sn); if (!strncmp(sn, ‚S123N456‛, 8)) { printf(‚Serial number is correct‛); } } int main() { checkserial(); int i=7; return 0; } Mục đích của chương trình trên là khi người dùng nhập vào chuỗi “S123N456” thì chương trình sẽ in ra câu “Serial number is correct”, nếu không thì không in gì cả. 163
Lợi dụng lỗi tràn bộ đệm hacker sẽ tìm cách nhập vào một chuỗi gì đó (khác “S123N456”) mà chương trình vẫn in ra câu “Serial number is correct”. Chúng ta sẽ minh họa cách thức thực hiện bằng chương trình OllyDebugger. Hình trên minh họa hàm main được nạp vào bộ nhớ. Tại địa chỉ 0040130C là lệnh gọi hàm checkserial, tại địa chỉ 00401311 là lệnh để thực hiện lệnh i= 7. Khi thực hiện lệnh gọi hàm checkserial thì tình trạng của Stack segment như sau: 164
Địa chỉ quay về hàm main (tại lệnh i=7) 00401311 được đưa vào stack tại địa chỉ 0022FF2C. Mảng sn được cấp 16 byte bắt đầu tại địa chỉ 0022FF10 đến địa chỉ 0022FF1F (từ ô 0022FF20 đến 0022FF2B , gồm 12 byte, bỏ trống). Do khi thực hiện hàm scanf, nếu người dùng nhập vào 32 ký tự, thì các ký tự thứ 29, 30, 31, 32 sẽ đè lên địa chỉ quay về 00401311 tạo thành một địa chỉ quay về mới. Hacker có thể lựa chọn giá trị nhập vào sao cho địa chỉ quay về là theo ý của hacker. Giả sử hacker muốn in ra câu “Serial number is correct”, hacker có thể chọn giá trị nhập vào sao cho địa chỉ quay về là 004012D4 (nếu biểu diễn bằng ký tự ASCII, 40: @; D4: Ⱡ;12: Ctrl+R). Do đó hacker sẽ nhập vào chuỗi sau: AAAAAAAAAAAAAAAAAAAAAAAAAAAAⱠ^R@ Lúc này tình trạng bộ nhớ stack sẽ là: (41 là mã ASCII của ký tự A) Ô nhớ 0022FF2C trong stack bây giờ có giá trị 004012D4. Do đó, sau khi hàm checkserial thực hiện xong thì lệnh RETN (tại ô nhớ 004012E1) sẽ không nhảy đến lệnh i= 7 của hàm main nữa mà nhảy đến lệnh in câu “Serial number is correct” tại ô nhớ 004012D4. Lệnh này in ra màn hình như bên dưới. 165