Mã hóa khối

Trong mật mã học, mã hóa khối (tiếng Anh: block cipher) là những thuật toán mã hóa đối xứng hoạt động trên những khối thông tin có độ dài xác định (block) với những chuyển đổi xác định. Chẳng hạn một thuật toán mã hóa khối có thể xử lý khối 128 bít đầu vào và biến nó thành khối 128 bít ở đầu ra. Quá trình chuyển đổi còn sử dụng thêm một tham số nữa: khóa bí mật để cá biệt hóa quá trình. Việc giải mã cũng diễn ra tương tự: xử lý khối mã hóa 128 bít cùng với khóa để trả về khối 128 bít bản rõ ban đầu.

Để mã hóa những văn bản có độ dài vượt quá độ dài của khối, người ta sử dụng thuật toán theo một chế độ mã hóa khối nào đó.

Phân biệt với mã hóa khối là mã hóa dòng. Mã hóa dòng làm việc trên từng bít của dòng dữ liệu và quá trình biến đổi thay đổi theo quá trình mã hóa. Tuy nhiên, sự phân biệt giữa 2 phương pháp nhiều khi không rõ ràng vì mã hóa khối khi hoạt động theo một chế độ nào đó thì có tác dụng như một phương pháp mã hóa dòng.

Thuật toán mã hóa khối ra đời sớm và có nhiều ảnh hưởng là thuật toán DES (Data Encryption Standard - Tiêu chuẩn mã hóa dữ liệu) do công ty IBM phát triển và được ban hành làm tiêu chuẩn năm 1977. Tiêu chuẩn thay thế DES có tên là AES (Advanced Encryption Standard - Tiêu chuẩn mã hóa nâng cao) được ban hành năm 2001.

Tổng quan

Quá trình mã hóa khối bao gồm 2 thuật toán: mã hóa - ký hiệu E và giải mã - ký hiệu E^-1. Cả hai thuật toán đều tác động lên một khối đầu vào n bít sử dụng một khóa k bít để cho ra một khối đầu ra n bít. Đối với bất kỳ khóa nào, giải mã là hàm ngược của mã hóa, nghĩa là:

E_{K}^{-1}(E_{K}(M))=M

trong đó M là khối thông tin và K là khóa bất kỳ.

Với mỗi khóa K, E_K là một hoán vị (song ánh) của khối đầu vào. Mỗi khóa sẽ xác định một hoán vị trong tổng số $2^{n}!$ khả năng.

Độ dài của khối thông tin, ký hiệu là n, thông thường là cố định ở 64 hoặc 128 bít. Một số thuật toán có độ dài khối thay đổi nhưng không phổ biến. Tính đến trước những năm giữa của thập kỷ 1990 thì độ dài 64 bít thường được sử dụng. Từ đó trở về sau thì khối 128 bít được sử dụng rộng rãi hơn. Trong các chế độ mã hóa khối thì người ta thường phải bổ sung thêm một số bít cho văn bản (tiếng Anh: padding) để văn bản chứa số nguyên lần các khối. Mỗi chế độ mã hóa có đặc tính khác nhau về lan truyền lỗi (lỗi mã hóa trong khối này ảnh hưởng tới khối khác), khả năng truy xuất ngẫu nhiên và khả năng chống lại các kiểu tấn công khác nhau. Độ dài thông thường của khóa, k, là 40, 56, 64, 80, 128, 192 và 256 bít. Hiện tại (năm 2006) thì 80 bít là độ dài tối thiểu của khóa để có thể chống lại tấn công kiểu duyệt toàn bộ.

Mã hóa khối gồm nhiều quá trình lặp lại

Hầu hết các thuật toán mã hóa khối sử dụng lặp đi lặp lại các hàm đơn giản. Phương pháp này còn được gọi là mã hóa khối lặp (xem thêm product cipher). Mỗi chu kỳ lặp được gọi là một vòng (tiếng Anh: round) và thông thường các thuật toán có từ 4 tới 32 vòng.

Rất nhiều thuật toán mã hóa khối có tính chất của mạng Feistel, hay tổng quát hơn là hệ thống thế và hoán vị. Các thành phần sử dụng trong thuật toán là các hàm toán học, các hàm lô gíc (đặc biệt là hàm XOR), hộp thế (S-box) và các phương pháp hoán vị.

Lịch sử

Thuật toán mã hóa Lucifer do công ty IBM phát triển dựa trên những nghiên cứu của Horst Feistel được xem là thuật toán mã hóa đầu tiên dùng cho mục đích dân sự. Sau đó, thuật toán này được sửa đổi và trở thành tiêu chuẩn mã hóa của chính phủ Hoa Kỳ vào năm 1976 với tên gọi là DES (Tiêu chuẩn mã hóa dữ liệu, tiếng Anh: Data Encryption Stardard). Từ đó, DES được sử dụng rất rộng rãi.

DES đã được thiết kế chống lại một số dạng tấn công mà Cơ quan an ninh quốc gia Hoa Kỳ (NSA) và IBM đã biết vào thời điểm thiết kế. Tuy nhiên, những thông tin này đã không được công bố và chỉ được biết đến vào cuối những năm 1980 nhờ những nghiên cứu của Eli Biham và Adi Shamir. Kỹ thuật đó có tên là tấn công vi sai. Kỹ thuật tấn công tuyến tính là một dạng tấn công khác chỉ được làm sáng tỏ sau xuất bản của Mitsuru Matsui. DES đã tạo nên một làn sóng nghiên cứu trong lĩnh vực mật mã học và thám mã. Từ đó nhiều vấn đề được làm sáng tỏ và nhiều thuật toán mã hóa mới đã ra đời.

Khối dữ liệu trong DES có độ dài 64 bít (khối 64 bít trở nên phổ biến sau DES) và độ dài khóa là 56 bít. Độ dài khóa phụ thuộc nhiều yếu tố, trong đó bao gồm cả quy định của chính phủ. Ngay từ những năm 1970, nhiều người đã cho rằng độ dài khóa 56 bít là không đủ an toàn. Cùng với sự phát triển của khả năng tính toán, vấn đề này ngày càng trở nên cấp thiết. Năm 1998, một hệ thống dành riêng cho thám mã DES của tổ chức Electronic Frontier Foundation đã phá được khóa DES trong thời gian hơn 2 ngày. Một số biến thể của DES như Triple DES hay 2TDES có độ dài khóa hiệu dụng 112 và 80 bít vẫn được coi là an toàn vào thời điểm năm 2004.

DES được thay thế như là một tiêu chuẩn bởi AES (thuật toán mã hóa nâng cao, tiếng Anh: Advanced Encryption Standard) vào năm 2001 sau một cuộc thi rộng rãi. Tác giả của AES là 2 người Bỉ: Joan Daemen và Vincent Rijmen (lấy tên chung là Rijndael). AES có độ dài khối là 128 bít và khóa có độ dài có thể là 128, 192 hay 256 bít. Chính phủ Hoa Kỳ cho phép sử dụng AES với các thông tin mật do NSA xếp loại.

Phá mã

Bên cạnh tấn công tuyến tính và vi sai còn có rất nhiều kiểu tấn công khác lên mã hóa khối: tấn công vi sai từng phần (tiếng Anh: truncated and partial differential cryptanalysis), tấn công kiểu XLS, tấn công kiểu bu mê răng (tiếng Anh: boomerang attack)... Để một thuật toán mới được chấp nhận, nó phải được chứng minh có khả năng chống lại các dạng tấn công đã biết.

Các hàm băm dựa trên mã hóa khối

Các thuật toán mã hóa khối có thể sử dụng theo một số cách để tạo ra hàm băm mật mã. Những phương pháp này tương tự với các chế độ mã hóa khối dùng cho mã hóa

Sử dụng mã hóa khối cho hàm băm thường chậm hơn so với dùng các hàm băm chuyên dụng. Tuy nhiên dùng mã hóa khối cho cả hai mục đích (mã hóa và hàm băm) lại tiện lợi vì chỉ phải thực hiện 1 lần. Điều này càng có ý nghĩa cho các hệ thống nhúng (chẳng hạn như thẻ thông minh) do không gian dành cho phát triển phần mềm bị hạn chế.

Mã hóa khối với tham số

M. Liskov, R. Rivest, và D. Wagner đã mô tả một dạng tổng quát hơn là mã hóa khối với tham số (tiếng Anh:"tweakable" block ciphers). Đầu vào của thuật toán dạng này bên cạnh bản rõ/bản mã và khóa còn có thêm một tham số nữa gọi là tweak. Tweak cùng với khóa sẽ lựa chọn cách hoán vị của thuật toán. Nếu việc thay đổi tweak yêu cầu khối lượng tính toán nhỏ (so với quá trình tạo khóa) thì ta sẽ có thêm một số chế độ hoạt động khác. Xem thêm bài mã hóa ổ đĩa để có thêm thông tin về vấn đề này.

Tham khảo

M. Liskov, R. Rivest, and D. Wagner, "Tweakable Block Ciphers", Crypto 2002 PDF.

Xem thêm

Liên kết ngoài

Danh sách một số thuật toán mã hóa đối xứng, phần lớn là mã hóa khối.
The block cipher lounge
What is a block cipher? Lưu trữ 2005-02-07 tại Wayback Machine from RSA FAQ
Block Ciphers and Cryptanalysis (PDF). Giới thiệu về cơ sở toán học của mã hóa khối và các phương pháp thám mã.

Mã hóa khối