Thuật Toán Mã Hóa Khối(block Cipher)- AES - W3seo

5/5 - (2 bình chọn)

Tóm tắt nội dung

Toggle

• Giới thiệu về AES
• Mật mã Rijndael (AES)
  • Các tham số của thuật toán AES được biểu diễn trong bảng sau:
  • Sơ đồ mã hoá và giải mã của AES được mô tả như sau:
  • S-box của AES là một bảng như sau:
  • Biến đổi khóa
• Sử dụng AES trong thực tế
  • Kiểu ECB (Electronic Code Book)
  • Kiểu CBC (Cipher Block Chaining)
  • Kiểu OFB (Output Feedback)
  • Kiểu CFB (Cipher Feedback)

Giới thiệu về AES

Vào những năm cuối của thập kỷ 90, chuẩn mật mã khối DES đã bị bẻ khoá bằng vét cạn khoá và trở nên không còn an toàn nữa. Việc thay thế DES bằng một mật mã mới, hiệu quả hơn là cần thiết. Viện chuẩn và công nghệ của Mỹ (NIST) đã tổ chức cuộc thi thiết kế thuật toán cho chuẩn mật mã mới (được đặt tên là Advanced Encryption Standard – AES).

Chuẩn mật mã mới dự kiến sẽ được tìm ra trong một cuộc thi công khai trên mạng Internet. Cuộc thi được công bố vào tháng 9/1997. Đến tháng 6/1998, đã có 15 thuật toán ứng viên được chấp nhận. Tất cả các thuật toán đều được phân tích bởi các nhà mật mã học dựa trên các tiêu chí về bảo mật và hiệu suất thực hiện (trên các máy tính với cấu hình khác nhau, trên thẻ thông minh, hoặc được cài đặt trực tiếp trên phần cứng) và tính khả thi khi bộ nhớ hạn chế.

Hướng dẫn khác:

1. Thuật toán mã hóa khối(block cipher) – DES
2. Mã hóa Stream Cipher
3. SSL (secure socket layer) là gì ?
4. S-Box trong AES
5. Thuật toán BKZ (Block Korkin-Zolotarev)
6. Tấn công Power Analysis

NIST đã tổ chức hai hội thảo khoa học để đánh giá các thuật toán này vào các tháng 8/1998 và tháng 3/1999. Đến tháng 8/1999, NIST công bố 5 thuật toán tốt nhất vào chung kết là: MARS, RC6, Rijndael, Serpent, và Twofish. Tháng 5/2000, NIST tổ chức hội thảo khoa học lần thứ ba để đánh giá toàn diện 5 thuật toán chung kết này. Tại hội thảo, đại diện tác giả các thuật toán đã trình bày kỹ những ý tưởng của mình để các đại biểu đánh giá.

Cuối cùng, tháng 10/2000, NIST chính thức công bố Rijndael thắng cuộc để trở thành chuẩn mật mã mới AES. Tháng 11/2001, thiết kế chi tiết của AES được chính thức công bố trên FIPS PUB 197.

Xem thêm Một số thuật ngữ Bảo mật Internet [RFC 2828].

Mật mã Rijndael (AES)

Mật mã Rijndael được thiết kế bởi hai nhà mật mã học người Bỉ là Vincent Rijmen và Joan Daemen. Đây là mật mã khối với khoá mã hoá có thể được lựa chọn với độ dài khác nhau 128/192/256 bit; khối dữ liệu mã hoá đầu vào dài 128 bit. Dữ liệu mã hoá được phân thành 4 nhóm, mỗi nhóm 32 bit (4 byte). Số vòng lặp tương ứng với các khoá là: 10/12/14, trong đó, mỗi vòng lặp bao gồm các phép biến đổi sau:

• Thay thế byte (dùng một S-box duy nhất)
• Đổi chỗ theo dòng (đổi chỗ các byte trong từng dòng)
• Trộn các cột (sử dụng phép nhân ma trận)
• XOR với khóa con (XOR với khóa con của vòng lặp)

Bên ngoài các vòng lặp còn có các bước khởi tạo, XOR các khóa con và một vòng kết thúc chỉ gồm ba bước (thiếu bước trộn cột). Tất cả các phép toán được tổ hợp dựa vào phép tính XOR và các bảng dữ liệu nên rất nhanh và hiệu quả. Thuật toán cũng hiệu quả hơn cho các máy tính 32 bit.

Các tham số của thuật toán AES được biểu diễn trong bảng sau:

Độ dài khoá (words/bytes/bits)	4/16/128	6/24/192	8/32/256
Độ lớn dữ liện đầu vào (words/bytes/bits)	4/16/128	4/16/128	4/16/128
Số vòng lặp	10	12	14
Độ lớn khoá vòng lặp (words/bytes/bits)	4/16/128	4/16/128	4/16/128
Độ lớn khoá mở rộng (words/bytes/)	44/176	52/208	60/240

Như đã trình bày ở trên, thuật toán AES cho phép người sử dụng có thể lựa chọn độ dài khoá phù hợp. Có ba bộ tham số khác nhau tương ứng với ba độ dài khoá khác nhau là 128 bit, 192 bit và 256 bit. Sau đây chúng ta chỉ xét trường hợp khoá 128 bit, các trường hợp khác có thể xem thêm trong tài liệu về chuẩn AES, FIPS PUB 197.

Sơ đồ mã hoá và giải mã của AES được mô tả như sau:

Tương ứng với sơ đồ trên ta có mã giả của AES như sau:

Thuật toán AES nhận đầu vào là dữ liệu cần mã hoá gồm 16 byte được lưu trong mảng in[16] với kiểu phần tử là byte, khoá mở rộng gồm 44 word được lưu trong mảng w[44] với kiểu phần tử là word. AES xuất dữ liệu đã mã hoá gồm 16 byte được lưu trong mảng out[16] với kiểu phần tử là byte.

Biến tạm state[4,4] là mảng hai chiều có kiểu phần tử là byte dùng để lưu trữ dữ liệu trong quá trình biến đổi. Đầu tiên, dữ liệu đầu vào in[16] sẽ được gán cho state[4,4], tiếp theo sẽ được XOR với 16 byte đầu của khoá mở rộng. Sau đó là 9 vòng lặp, mỗi vòng có 4 phép biến đổi: SubBytes, ShiftRows, MixColumns and AddRoundKey và như đã nói ở trên, tất cả nhằm biến đổi giá trị state. Sau đó là 3 phép biến đổi nữa và cuối cùng là gán kết quả cho giá trị out[16] để xuất ra ngoài như là dữ liệu đã được mã hoá.

Xem thêm Phân khối khóa (key) trong mã hóa

Chúng ta sẽ lần lượt khảo sát các phép biến đổi chính của AES. Đầu tiên là phép gán in cho state:

Bản chất ở đây là việc chuyển ma trận một chiều thành ma trận hai chiều. Có thể sử dụng công thức chuyển đổi sau: s [r, c] = in [r + 4c], trong đó r là chỉ số của hàng và c là chỉ số của cột.

Sau khi mã hoá xong sẽ có phép gán state cho out:

Bản chất ở đây là việc chuyển ma trận hai chiều thành ma trận một chiều. Có thể sử dụng công thức biến đổi sau: out[i] = s[i mod 4, i div 4], với i = [0..15]. Một vòng tính toán của AES gồm có các bước như sau:

Ta sẽ khảo sát các phép biến đổi trong các vòng tính toán này. Đầu tiên là phép biến đổi SubBytes.

AES sử dụng S-box để biến đổi một byte thành một byte khác bằng cách tách byte đầu vào thành hai số 4 bit. Các số này là chỉ số hàng và chỉ số cột của S-box để từ đó xuất ra byte đầu ra.

S-box của AES là một bảng như sau:

S-box được xây dựng từ phép biến đổi Affine: b‟i = bi xor b(i +4)mod8 xor b(i +5)mod8 xor b(i +6)mod8 xor b(i +7) mod 8 xor ci với 0 £ i < 8 và bi là bit thứ i của byte đầu vào, ci là bit thứ i của byte {63}= {0110 0011} = {c7c6c5c4 c3c2c1c0}. Biểu diễn biến đổi này dưới dạng ma trận như sau:

Phép biến đổi thứ ba là MixColumns. Đây là phép biến đổi phức tạp bao gồm phép nhân ma trận và rút gọn hệ số trên trường GF(28) với đa thức tối giản: x4 + 1 và rút gọn kết quả trên trường GF(28) với đa thức tối giản:

x8+ x4 + x3 + x + 1 (1 0001 1011).

Đa thức 4 số hạng với các hệ số là các phần tử của trường GF(28) có dạng: a(x) = a3x3 + a2x2 + a1x + a0, trong đó ai là các số thuộc GF(28). Tương tự b(x) = b3x3 + b2x2 + b1x + b0. Khi nhân hai đa thức với nhau: c(x) = a(x)·b(x) thì c(x) sẽ có dạng: c(x) = c6x6 + c5x5 + c4x4 + c3x3 + c2x2 + c1x + c0

• Với: c0 = a0 ·b0
• c1 = a1 · b0 xor a0 · b1
• c2 = a2 · b0 xor a1 · b1 xor a0 · b2
• c3 = a3 · b0 xor a2 · b1 xor a1 · b2 xor a0 · b3 c4 = a3 · b1 xor a2 · b2 xor a1 · b3
• c5 = a3 · b2 xor a2 · b3 c6 = a3 · b3

Nếu muốn chuyển c(x) thành đa thức có 4 số hạng thì phải rút gọn (ví dụ cho x4 + 1. Khi đó xi mod (x4 + 1) = xi mod 4, (x6 = x2, x5 = x, x4 = x0).

Giả sử sau khi rút gọn ta nhận được:

d(x) = d3x3 + d2x2 + d1x + d0.

Lúc đó: d0 = c0 xor c4 = (a0 · b0) xor (a3 · b1) xor (a2 · b2) xor (a1 · b3) d1 = c1 xor c5 = (a1 · b0) xor (a0 · b1) xor (a3 · b2) xor (a2 · b3) d2 = c2 xor c6 = (a2 · b0) xor (a1 · b1) xor (a0 · b2) xor (a3 · b3) d3 = c3 = (a3 · b0) xor (a2 · b1) xor (a1 · b2) xor (a0 · b3)

Có thể viết lại kết quả dưới dạng tích ma trận như sau:

Trong biến đổi MixColumns ta có: a(x) = {03} x3 + {01} x2 + {01} x

+ {02}. Khi đó: s‟(x) = a(x) xor s(x) (Phép nhân đa thức 4 số hạng với hệ số GF(28), rút gọn cho x4 + 1). Cụ thể ta sẽ có:

. Với c = [0..3]

Như vậy ta có thể viết triển khai thành:

• s‟0,c = ( {02} · s0,c ) xor ( {03} · s1,c ) xor s2,c xor s3,c
• s‟1,c = s0,c xor ( {02} · s1,c ) xor ( {03} · s2,c ) xor s3,c
• s‟2,c = s0,c xor s1,c xor ( {02} · s2,c ) xor ( {03} · s3,c )

s‟3,c = ( {03} · s0,c ) xor s1,c xor s2,c xor ( {02} · s3,c ) Ví dụ ta có: [s0,0 s1,0 s2,0 s3,0] = [d4 bf 5b 30], lúc đó: s‟0,c = ( {02} · {d4}) xor ( {03} · {bf}) xor {5b} xor {30}

= {02} · 1101 0100 xor {03} · 1011 1111 xor 0101 1101 xor 0011 0000

= 1101 01000 xor (1011 11110 xor 1011 1111) xor 0101 1101 xor 0011 0000

= (1101 01000 xor 1011 11110) xor 1011 1111 xor 0101 1101 xor 0011 0000

= 0000 0100 = {04}.

Phép biến đổi cuối cùng trong vòng lặp là XOR với khoá con. Các bit sẽ được XOR theo từng bit tương ứng:

[s‟0,c, s‟1,c, s‟2,c, s‟3,c] = [s0,c, s1,c, s2,c, s3,c] xor [ wround*4+c ], với c = [0..3].

Biến đổi khóa

Khóa mở rộng gồm 44 word sẽ được tạo ra từ khóa ban đầu 4 word (1 word = 32 bits). Các khóa con (round key) dài 4 word sẽ được lấy tuần tự từ khóa mở rộng 44 word (Tổng cộng có 11 khóa con).

Mã giả tạo khoá mở rộng như sau:

Thuật toán nhận đầu vào là khoá mã hoá gồm 16 byte được lưu trong mảng key[16] với kiểu phần tử là byte, đầu ra là khoá mở rộng gồm 44 word được lưu trong mảng w[44] với kiểu phần tử là word. Biến tạm temp có kiểu word.

16 byte đầu tiên của khoá mở rộng chính là khoá mã hoá ban đầu. Các khóa sau đó sẽ được tính theo công thức: w[ i ] = w[ i-4 ] xor temp, trong đó, temp = w[i-1] nếu i không chia hết cho 4, ngược lại, temp sẽ được tính mới dựa trên giá trị temp cũ.

Ý nghĩa các hàm như sau:

• RotWord: Quay trái một byte trong word: [b0,b1,b2,b3] à [b1,b2,b3,b0]
• SubWord: Thay thế từng byte trong word, sử dụng S-box.
• Rcon[ j ]: = (RC[ j ], 00, 00, 00), với RC[1] = 1, RC[j] = 2 · RC[j-1] (Nhân trong GF(28), với đa thức rút gọn là x8 + x4 + x3 + x + 1 hay {01}{0b}).

Sử dụng AES trong thực tế

AES là chuẩn mật mã khối sử dụng rộng rãi trong ngày nay. AES đã có mặt tại nhiều quy trình an toàn khác nhau. Trong thực tế, để mã hoá dữ liệu có độ lớn khác nhau, người ta cũng sử dụng các phương pháp khác nhau giống như khi ta đã khảo sát cho DES và các thuật toán mật mã khối khác, đó là: ECB, CBC, OFB và CFB.

Thuật toán AES cho phép lựa chọn độ dài của khoá là 128, 192 và 256 bit. Nhưng trên thực tế, người ta thường hay sử dụng hai lựa chọn 128 và 256 bit. Cho đến hiện nay, năm 2012, thuật toán AES còn an toàn và chưa bị bẻ khoá.

Kiểu ECB (Electronic Code Book)

Dữ liệu được chia thành các khối 8 byte và được mã hoá riêng rẽ bằng DES với cùng một khoá K: Ci = DESK (Pi). Sau đó, các khối kết quả Ci sẽ được ghép nối lại với nhau:

Quá trình giải mã diễn ra hoàn toàn ngược lại với quá trình mã hoá. Ưu điểm của ECB là đơn giản và nhanh. Nhược điểm của nó là không an toàn: Các khối nguồn giống nhau sẽ tạo thành các khối mã giống nhau, hơn nữa, do các khối được mã hoá độc lập nên kẻ gian có thể chèn một vài khối 8 byte vào trong quá trình mã hoá và quan sát kết quả để lấy thông tin thám mã mà người sử dụng có thể không biết. Vì vậy, trên thực tế ECB ít khi dùng để mã hoá dữ liệu lớn mà chỉ dùng để mã hoá dữ liệu nhỏ, ví dụ như các khoá mật mã.

Xem thêm 50 + câu hỏi trắc nghiệm về testing software

Kiểu CBC (Cipher Block Chaining)

Để tránh các nhược điểm của ECB, người ta sử dụng CBC với việc liên kết quá trình mã hoá các khối với nhau. Kết quả mã hoá của khối trước sẽ tham gia làm một thành phần đầu vào cho khối tiếp theo. Đối với khối đầu tiên, sẽ sử dụng một vector khởi tạo (Initial Vector – IV) làm đầu vào. C0 = IV; Ci = DESK (Pi XOR Ci-1), i = 1, 2,…n.

CBC đã hoàn toàn loại bỏ được nhược điểm của ECB. Mỗi khối đích phụ thuộc vào tất cả các khối nguồn trước đó và mọi thay đổi trên đường truyền hoặc ở khối nguồn sẽ được thể hiện ở các khối mã sau khi xảy ra sự thay đổi. Điểm yếu của CBC chính là IV: nếu IV được gửi công khai cho người nhận, kẻ lạ có thể thay đổi đồng thời IV và các bit ở khối thứ nhất theo ý muốn. Do đó, IV cần được cố định hoặc được mã hóa và gửi bằng ECB cho người nhận ở phần đầu của thông điệp.

Cả trong ECB lẫn CBC chúng ta cần phải xử lý điều kiện biên. Đó là khi khối cuối cùng không đủ 8 byte. Trường hợp này, chúng ta phải bổ sung vào khối cuối cùng một số byte 0 và ghi nhớ số byte vừa bổ sung vào để xử lý dữ liệu sau khi giải mã. Ví dụ, nếu byte cuối cùng là: [b1 b2 b3] thì ta có thể bổ sung thêm 5 byte mới để có đủ 8 byte như sau: [b1 b2 b3 00 00 00 00 05] (thêm 5 byte). Xử lý khối cuối cùng có thể bằng nhiều cách khác nhau, tuy nhiên, cần thống nhất trong các thuật toán mã hoá và giải mã. CBC là kiểu sử dụng phổ biến, dùng để mã hoá các khối dữ liệu lớn, do tính tiện lợi và an toàn của nó.

Trong CBC, kết quả của khối cuối cùng là Cn phụ thuộc vào toàn bộ các khối nguồn trước của dữ liệu Pi (i = 1..n) nên có thể được sử dụng như là một giá trị băm (hash value) của thông điệp P. Khi đó CBC có thể được sử dụng như là một hàm băm (hash function) 64 bit.

Xem thêm numpy.dot() trong Python

Kiểu OFB (Output Feedback)

Thông điệp nguồn được chia thành các khối 64 bit Pi và được coi như là một dòng bit. Đầu ra của thuật toán khối, một mặt XOR với các khối Pi để cho các khối Ci, mặt khác sẽ làm đầu vào cho mã hoá khối sau.

O0 = IV; Oi = DESK (Oi-1); Ci = Pi XOR Oi với (i = 1..n). Do các Oi không phụ thuộc vào thông điệp mã hoá (Ci) nên có thể tính dòng khoá gồm tất cả dãy Oi trước sau đó mới sử dụng chúng để mã hoá Pi. Quá trình giải mã thực hiện hoàn toàn ngược lại với quá trình mã hoá.

Kiểu CFB (Cipher Feedback)

Kiểu này gần giống với OFB, chỉ khác là giá trị tham gia vào vòng mã hoá cho khối sau (Ji) không phải là Oi mà chính là Ci:

Khi đó: C0 = IV; Ji = Ci-1 ; Ci = Pi XOR DESK (Ji) với i = 1..n.

Bốn kiểu sử dụng trình bày trên đây không những thích hợp cho thuật toán DES mà còn có thể dùng cho các thuật toán mã hoá khối khác.

Xem thêm Các hàm số và ký tự trong R