krone
VIP Members
-
26/07/2016
-
141
-
259 bài viết
Kiến trúc mã hoá khối (Block Cipher) – P2
Phần trước chúng ta đã so sánh về Stream Cipher và Block Cipher, qua đó cũng có một cái nhìn tổng quát về Block Cipher là như thế nào. Chúng ta cũng biết được Feistel encryption, kiến trúc và cách tính toán cơ bản. Tiếp theo chúng ta sẽ nói về Feistel Cipher và thuật toán cấu thành nên nó.
Feistel Cipher
Feistel đã đề xuất rằng chúng ta có thể tính gần đúng “idea block cipher” bằng cách sử dụng khái niệm về “product cipher”, đó là việc thực hiện hai hoặc nhiều loại mã hoá đơn giản theo cách sao cho kết quả cuối cùng hoặc sản phẩm được mã hóa mạnh hơn bất kỳ mã hoá thành phần nào. Bản chất của phương pháp này là phát triển một mật mã khối với độ dài khóa là k bit và chiều dài khối là n bit, cho phép tổng cộng 2^k biến đổi có thể, thay vì (2^n)! biến đổi có sẵn với “idea block cipher”.
Cụ thể, Feistel đề xuất sử dụng một mã hoá thay thế các thay thế và hoán vị, trong đó các thuật ngữ này được định nghĩa như sau:
- Substitution (Thay thế): Mỗi thành phần hoặc nhóm yếu tố văn bản gốc được thay thế duy nhất bằng một yếu tố mã hóa tương ứng hoặc nhóm các yếu tố mã hoá liên quan.
- Permutation (Hoán vị): Một chuỗi các thành phần của văn bản được thay thế bằng hoán vị của chuỗi đó. Đó là, không có phần tử nào được thêm hoặc xóa hoặc thay thế trong chuỗi, thay vào đó là thứ tự các phần tử xuất hiện trong chuỗi được thay đổi.
Kiến trúc bên trong của Feistel Cipher
Phía bên trái của hình trên mô tả cấu trúc mã hóa được đề xuất bởi Feistel. Các đầu vào của thuật toán mã hóa là một khối văn bản có độ dài 2w bit và khóa K. Khối plaintext được chia thành hai nửa, LE0 và RE0. Hai nửa dữ liệu đi qua n vòng xử lý và sau đó kết hợp để tạo ra khối ciphertext.
Mỗi vòng i có đầu vào LEi - 1 và REi - 1 xuất phát từ vòng trước, cũng như một khóa con Ki có nguồn gốc từ tất cả K. Nói chung, các khóa con Ki khác với K và khác nhau. Trong hình trên, 16 round được sử dụng, mặc dù số lượng round có thể được thực hiện nhiều hơn.
Tất cả các round có cấu trúc giống nhau. Một substitution(Thay thế) được thực hiện ở nửa bên trái của dữ liệu. Điều này được thực hiện bằng cách áp dụng 1 round function F cho nửa bên phải của dữ liệu và sau đó lấy exclusive-OR của đầu ra của chức năng đó và nửa bên trái của dữ liệu.
Round function có cấu trúc chung giống nhau cho mỗi round nhưng được tham số hóa bởi khóa con Ki. Một cách khác để diễn đạt điều này là nói rằng F là một hàm của nửa bit bên phải và một khóa con của các bit y, tạo ra giá trị đầu ra có độ dài w bit: F (REi, Ki + 1).
Sau substitution này, một permutation (hoán vị) được thực hiện bao gồm sự trao đổi của hai nửa dữ liệu. Cấu trúc này là một dạng đặc biệt của mạng hoán vị thay thế (SPN) do Shannon đề xuất.
Việc thực hiện chính xác mạng Feistel phụ thuộc vào việc lựa chọn các tham số và tính năng thiết kế sau:
- Block size: Block size lớn hơn có nghĩa là bảo mật cao hơn (tất cả những thứ khác đều bằng nhau) nhưng giảm tốc độ encrypt/decrypt cho một thuật toán nhất định. Bảo mật hơn đạt được bằng sự khuếch tán lớn hơn. Theo truyền thống, kích thước khối 64 bit đã được coi là sự đánh đổi hợp lý và gần như phổ biến trong thiết kế block cipher. Tuy nhiên, AES mới sử dụng kích thước khối 128 bit.
- Key size: Key size lớn hơn có nghĩa là bảo mật cao hơn nhưng có thể làm giảm tốc độ encrypt/decrypt. Bảo mật cao hơn đạt được nhờ khả năng chống lại các cuộc tấn công brute-force. Kích thước khóa từ 64 bit trở xuống hiện được coi là không đủ và 128 bit đã trở thành kích thước phổ biến.
- Số round: Bản chất của mật mã Feistel là một round duy nhất cung cấp bảo mật không đầy đủ nhưng nhiều round cung cấp bảo mật càng tăng lên. Số round điển hình là 16 vòng.
- Thuật toán tạo khóa con: Độ phức tạp lớn hơn trong thuật toán này sẽ dẫn đến khó khăn hơn về “cryptanalysis”.
Có hai cân nhắc khác trong thiết kế mật mã Feistel:
- Fast software encryption/decryption: Trong nhiều trường hợp, mã hóa được nhúng trong các ứng dụng hoặc chức năng tiện ích theo cách ngăn chặn việc triển khai phần cứng. Theo đó, tốc độ thực hiện của thuật toán trở thành một mối quan tâm lớn.
- Dễ phân tích: Mặc dù chúng ta muốn làm cho thuật toán của chúng ta trở nên khó khăn nhất có thể để mã hóa, nhưng có lợi ích lớn trong việc làm cho thuật toán dễ dàng phân tích. Nếu thuật toán có thể được giải thích chính xác và rõ ràng, việc phân tích thuật toán đó cho các lỗ hổng “cryptanalysis” sẽ dễ dàng hơn và do đó phát triển mức độ đảm bảo cao hơn về độ mạnh của nó. Ví dụ, DES không có chức năng dễ dàng để bị phân tích.
Trên đây là cơ sở về Block Cipher, nguồn gốc cũng như mô tả cơ bản block cipher là gì, cách thức hoạt động cũng như hướng thiết kế một block cipher cho ứng dụng.
Feistel Cipher
Feistel đã đề xuất rằng chúng ta có thể tính gần đúng “idea block cipher” bằng cách sử dụng khái niệm về “product cipher”, đó là việc thực hiện hai hoặc nhiều loại mã hoá đơn giản theo cách sao cho kết quả cuối cùng hoặc sản phẩm được mã hóa mạnh hơn bất kỳ mã hoá thành phần nào. Bản chất của phương pháp này là phát triển một mật mã khối với độ dài khóa là k bit và chiều dài khối là n bit, cho phép tổng cộng 2^k biến đổi có thể, thay vì (2^n)! biến đổi có sẵn với “idea block cipher”.
Cụ thể, Feistel đề xuất sử dụng một mã hoá thay thế các thay thế và hoán vị, trong đó các thuật ngữ này được định nghĩa như sau:
- Substitution (Thay thế): Mỗi thành phần hoặc nhóm yếu tố văn bản gốc được thay thế duy nhất bằng một yếu tố mã hóa tương ứng hoặc nhóm các yếu tố mã hoá liên quan.
- Permutation (Hoán vị): Một chuỗi các thành phần của văn bản được thay thế bằng hoán vị của chuỗi đó. Đó là, không có phần tử nào được thêm hoặc xóa hoặc thay thế trong chuỗi, thay vào đó là thứ tự các phần tử xuất hiện trong chuỗi được thay đổi.
Kiến trúc bên trong của Feistel Cipher
Phía bên trái của hình trên mô tả cấu trúc mã hóa được đề xuất bởi Feistel. Các đầu vào của thuật toán mã hóa là một khối văn bản có độ dài 2w bit và khóa K. Khối plaintext được chia thành hai nửa, LE0 và RE0. Hai nửa dữ liệu đi qua n vòng xử lý và sau đó kết hợp để tạo ra khối ciphertext.
Mỗi vòng i có đầu vào LEi - 1 và REi - 1 xuất phát từ vòng trước, cũng như một khóa con Ki có nguồn gốc từ tất cả K. Nói chung, các khóa con Ki khác với K và khác nhau. Trong hình trên, 16 round được sử dụng, mặc dù số lượng round có thể được thực hiện nhiều hơn.
Tất cả các round có cấu trúc giống nhau. Một substitution(Thay thế) được thực hiện ở nửa bên trái của dữ liệu. Điều này được thực hiện bằng cách áp dụng 1 round function F cho nửa bên phải của dữ liệu và sau đó lấy exclusive-OR của đầu ra của chức năng đó và nửa bên trái của dữ liệu.
Round function có cấu trúc chung giống nhau cho mỗi round nhưng được tham số hóa bởi khóa con Ki. Một cách khác để diễn đạt điều này là nói rằng F là một hàm của nửa bit bên phải và một khóa con của các bit y, tạo ra giá trị đầu ra có độ dài w bit: F (REi, Ki + 1).
Sau substitution này, một permutation (hoán vị) được thực hiện bao gồm sự trao đổi của hai nửa dữ liệu. Cấu trúc này là một dạng đặc biệt của mạng hoán vị thay thế (SPN) do Shannon đề xuất.
Việc thực hiện chính xác mạng Feistel phụ thuộc vào việc lựa chọn các tham số và tính năng thiết kế sau:
- Block size: Block size lớn hơn có nghĩa là bảo mật cao hơn (tất cả những thứ khác đều bằng nhau) nhưng giảm tốc độ encrypt/decrypt cho một thuật toán nhất định. Bảo mật hơn đạt được bằng sự khuếch tán lớn hơn. Theo truyền thống, kích thước khối 64 bit đã được coi là sự đánh đổi hợp lý và gần như phổ biến trong thiết kế block cipher. Tuy nhiên, AES mới sử dụng kích thước khối 128 bit.
- Key size: Key size lớn hơn có nghĩa là bảo mật cao hơn nhưng có thể làm giảm tốc độ encrypt/decrypt. Bảo mật cao hơn đạt được nhờ khả năng chống lại các cuộc tấn công brute-force. Kích thước khóa từ 64 bit trở xuống hiện được coi là không đủ và 128 bit đã trở thành kích thước phổ biến.
- Số round: Bản chất của mật mã Feistel là một round duy nhất cung cấp bảo mật không đầy đủ nhưng nhiều round cung cấp bảo mật càng tăng lên. Số round điển hình là 16 vòng.
- Thuật toán tạo khóa con: Độ phức tạp lớn hơn trong thuật toán này sẽ dẫn đến khó khăn hơn về “cryptanalysis”.
Có hai cân nhắc khác trong thiết kế mật mã Feistel:
- Fast software encryption/decryption: Trong nhiều trường hợp, mã hóa được nhúng trong các ứng dụng hoặc chức năng tiện ích theo cách ngăn chặn việc triển khai phần cứng. Theo đó, tốc độ thực hiện của thuật toán trở thành một mối quan tâm lớn.
- Dễ phân tích: Mặc dù chúng ta muốn làm cho thuật toán của chúng ta trở nên khó khăn nhất có thể để mã hóa, nhưng có lợi ích lớn trong việc làm cho thuật toán dễ dàng phân tích. Nếu thuật toán có thể được giải thích chính xác và rõ ràng, việc phân tích thuật toán đó cho các lỗ hổng “cryptanalysis” sẽ dễ dàng hơn và do đó phát triển mức độ đảm bảo cao hơn về độ mạnh của nó. Ví dụ, DES không có chức năng dễ dàng để bị phân tích.
Trên đây là cơ sở về Block Cipher, nguồn gốc cũng như mô tả cơ bản block cipher là gì, cách thức hoạt động cũng như hướng thiết kế một block cipher cho ứng dụng.
Chỉnh sửa lần cuối bởi người điều hành: