Chương 1. Mật mã khối: Mô hình mạng Feistel và mạng SPN 1.1 Mạng Fiestel Mạng Feistel là một phương pháp chung để biến đổi một hàm bất kỳ thường được gọi là Hàm F hay F-function) thành một hoán vị. Nó là một cấu trúc đối xứng được sử dụng trong việc xây dựng mật mã khối, được đặt tên theo nhà vật lý và mật mã Horst Feistel người đa nghiên cứu tiên phong trong khi đi làm việc cho IBM(HOA KỲ). Trong mật mã Feistel, mã hóa và giải mã là các hoạt động rất giống nhau và cả hai đều bao gồm việc chạy lặp đi lặp lại một hàm được gọi là “hàm vòng” một số lần cố định.
Khối xây dựng cơ bản của mạng Feistel là hàm F: ánh xạ phụ thuộc khóa của một chuỗi đầu vào một chuỗi đầu ra. Một hàm F là luôn luôn phi tuyến và không thể đảo ngược. Nhiều mật mã khối đối xứng hiện đại dựa trên mạng Feistel. Mạng Feistel lần đầu tiên được thương mại hóa trong IBM’s Lucifer- được thiết kế bởi Horst Feistel và Don Coppersmith vào năm 1973.
Mạng Feistel được biết đến rộng rãi hơn khi Chính phủ Liên bang Hoa Kỳ thông qua DES(một mật mã dựa trên Lucifer, với những thay đổi được thực hiện bởi NSA) vào năm 1976. Giống như các thành phần khác của DES, bản chất lặp đi lặp lại của cấu trúc Feistel làm cho việc triển khai hệ thống mật mã trong phần cứng dễ dàng hơn (đặc biệt là trên phần cứng có sẵn tại thời điểm DES thiết kế). Về thiết kế, mạng Feistel sử dụng hàm vòng, một hàm nhận hai đầu vào, một khối dữ liệu và một khóa con và trả về một đầu ra có cùng kích thước với khối dữ liệu. Trong mỗi vòng, hàm vòng được chạy trên một nửa dữ liệu được mã hóa và đầu ra của nó được XOR với nửa dữ liệu còn lại.
Điều này được lặp lại một số lần cố định và đầu ra cuối cùng là dữ liệu được mã hóa. Một lợi thế quan trọng của mạng Feistel so với các thiết kế mật mã khác như mạng thay thế – hoán vị toàn bộ hoạt động được đảm bảo là không thể đảo ngược (nghĩa là, dữ liệu được mã hóa có thể được giải mã), ngay cả khi bản thân hàm vòng không thể đảo ngược. Hàm vòng có thể được thực hiện phức tạp tùy ý, vì nó không cần được thiết kế để có thể đảo ngược. Hơn nữa, mã hóa và giải mã các hoạt động rất giống nhau, thậm chí giống hệt nhau trong một số trường hợp, chỉ yêu cầu đảo ngược lịch trình chính.
Do đó, kích thước của mã hoặc mạch cần thiết để thực hiện một mật mã như vậy đã giảm gần một nửa. Mở rộng Cấu trúc và đặc tính của mật mã Feistel đã được phân tích rộng rãi bởi những người viết mật mã. Michael Luby và Charles Rackoff đã phân tích cấu trúc mật mã Bài thi cuối kỳ môn ANM Feistel và chứng minh rằng nếu hàm vòng là một mật mã an toàn chức năng giả ngẫu nhiên, với K là seed và 3 hàm vòng là đủ để tạo ra mật mã khối a hoán vị giả ngẫu nhiên, trong khi 4 hàm vòng là đủ để làm cho nó trở thành một hoán vị giả ngẫu nhiên "mạnh" (có nghĩa là nó vẫn là giả ngẫu nhiên ngay cả đối với kẻ thù tiên tri truy cập vào hoán vị nghịch đảo của nó). Do kết quả rất quan trọng này của Luby và Rackoff, mật mã Feistel đôi khi được gọi là mật mã khối Luby-Rackoff.
Cấu trúc Feistel cũng được sử dụng trong các thuật toán mật mã khác với mật mã khối. Ví dụ lược đồ của OAEP sử dụng một mạng Feistel đơn giản để ngẫu nhiên hóa các bản mã trong một số mã hóa khóa bất đối xứng các kế hoạch. Thuật toán Feistel tổng quát có thể được sử dụng để tạo ra các hoán vị mạnh trên các miền nhỏ có kích thước không phải là lũy thừa của hai (xem mã hóa bảo toàn định dạng). Các nghiên cứu lý thuyết sâu hơn đã phần nào khái quát cấu trúc và đưa ra các giới hạn chính xác hơn cho bảo mật.1 Chi tiết cách xây dựng Để cho là hàm tròn và để là khóa phụ cho các vòng tương ứng.
2 Bài thi cuối kỳ môn ANM Sau đó, hoạt động cơ bản như sau: Chia khối văn bản rõ thành hai phần bằng nhau, Đối với mỗi vòng ,ta tính toán: Ở đâu (+) có nghĩa XOR. Sau đó, bản mã là Giải mã bản mã được thực hiện bằng máy tính cho Sau đó lại là bản rõ. Sơ đồ minh họa cả mã hóa và giải mã. Lưu ý sự đảo ngược thứ tự khóa con để giải mã; đây là sự khác biệt duy nhất giữa mã hóa và giải mã.
Sử dụng mạng Feistel như một thành phần thiết kế Cho dù toàn bộ mật mã có phải là mật mã Feistel hay không, các mạng giống Feistel có thể được sử dụng như một thành phần của thiết kế mật mã. Ví dụ, MISTY1 là một mật mã Feistel sử dụng mạng Feistel ba vòng trong chức năng vòng của nó và Skipjack là một mật mã Feistel đã được sửa đổi bằng cách sử dụng mạng Feistel trong hoán vị G của nó.1 Mô tả về mạng SPN Trong mật mã, mạng SP, hay mạng thay thế – hoán vị (substitution – permutation network ), là một loạt các phép toán liên kết được sử dụng trong các thuật toán mật mã khối như AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK,. Một mạng như vậy lấy một khối bản rõ và khóa làm đầu vào, và áp dụng một số "vòng" hoặc "lớp" xen kẽ của hộp thay thế (hộp S) và hộp hoán vị (hộp P) để tạo ra khối bản mã. Các hộp S và hộp P biến đổi các khối (con) của các bit đầu vào thành các bit đầu ra.
Thông thường, các phép biến đổi này là các hoạt động hiệu quả để thực hiện trong phần cứng, chẳng hạn như phép quay độc quyền hoặc (XOR) và quay theo chiều bit. Chìa khóa được giới thiệu trong mỗi vòng, thường ở dạng "phím vòng" bắt nguồn từ đó. (Trong một số thiết kế, bản thân các hộp chữ S phụ thuộc vào khóa.) Việc giải mã được thực hiện đơn giản bằng cách đảo ngược quy trình (sử dụng đảo ngược của hộp S và hộp P và áp dụng các phím tròn theo thứ tự đảo ngược). 3 Bài thi cuối kỳ môn ANM Hình minh họa của một mạng thay thế – hoán vị với 3 vòng, mã hóa khối bản rõ 16 bit thành khối bản mã 16 bit.
Các S-box là chữ S, các P-box là chữ P và các khóa là chữ K.2 Các thành phần của mạng SPN Hộp S thay thế một khối bit nhỏ (đầu vào của hộp S) bằng một khối bit khác (đầu ra của hộp S). Sự thay thế này phải là 1-1, để đảm bảo khả năng nghịch đảo (do đó giải mã). Đặc biệt, độ dài của đầu ra phải giống với độ dài của đầu vào (hình bên phải có S- box với 4 bit đầu vào và 4 bit đầu ra), khác với S-box nói chung cũng có thể thay đổi độ dài, chẳng hạn như trong DES (Tiêu chuẩn mã hóa dữ liệu). Hộp S thường không chỉ đơn giản là một hoán vị của các bit.
Đúng hơn, một hộp S tốt sẽ có đặc tính là thay đổi một bit đầu vào sẽ thay đổi khoảng một nửa số bit đầu ra (hoặc hiệu ứng tuyết lở). Nó cũng sẽ có thuộc tính mà mỗi bit đầu ra sẽ phụ thuộc vào mỗi bit đầu vào.3 Tính chất Một S-box điển hình hoặc một P-box đơn lẻ không có nhiều chức năng mật mã: S-box có thể được coi là mật mã thay thế, trong khi hộp P-box có thể được coi là mật mã chuyển vị. Tuy nhiên, một mạng SP được thiết kế tốt với nhiều vòng xen kẽ của S- box và P-box đã thỏa mãn các đặc tính về sai lệch và khuếch tán của Shannon: • Lý do cho sự khuếch tán là như sau: Nếu người ta thay đổi một bit của bản rõ, thì nó được đưa vào hộp S-box, đầu ra của nó sẽ thay đổi ở một số bit, khi đó tất cả những thay đổi này sẽ được phân phối bởi hộp P-box giữa một số S -boxes, do đó kết quả đầu ra của 4 Bài thi cuối kỳ môn ANM tất cả các S-box này lại bị thay đổi ở một số bit, v. Thực hiện nhiều vòng, mỗi bit thay đổi qua lại nhiều lần, do đó, cuối cùng, bản mã đã thay đổi hoàn toàn, theo cách giả ngẫu nhiên.
Đặc biệt, đối với một khối đầu vào được chọn ngẫu nhiên, nếu một người lật bit thứ i, thì xác suất để bit đầu ra thứ j sẽ thay đổi là khoảng một nửa. Ngược lại, nếu người ta thay đổi một bit của bản mã, sau đó cố gắng giải mã nó, thì kết quả là một thông báo hoàn toàn khác với bản rõ ban đầu — mật mã SP không dễ bị giải mã. • Lý do đặc tính sai lệch hoàn toàn giống với sự khuếch tán: thay đổi một bit của khóa sẽ thay đổi một số khóa vòng, và mọi thay đổi trong mỗi khóa vòng sẽ khuếch tán trên tất cả các bit, thay đổi bản mã một cách rất phức tạp. • Ngay cả khi kẻ tấn công bằng cách nào đó lấy được một bản rõ tương ứng với một bản mã — một cuộc tấn công bản rõ đã biết, hoặc tệ hơn là một cuộc tấn công bản rõ được chọn hoặc bản mã đã chọn — thì sự nhầm lẫn và lan truyền khiến kẻ tấn công khó lấy lại khóa.4 So sánh với mạng Feistel: Mặc dù mạng Feistel sử dụng S-box (chẳng hạn như DES) khá giống với mạng SP, nhưng có một số khác biệt khiến nó được áp dụng nhiều hơn trong một số trường hợp nhất định.
Đối với một số lượng sai lệch và phổ biến nhất định, mạng SP có nhiều "tính song song cố hữu" hơn và do đó - với một CPU có nhiều đơn vị thực thi - có thể tính toán nhanh hơn mạng Feistel. Các CPU có ít đơn vị thực thi - chẳng hạn như hầu hết các smart card - không thể tận dụng tính song song vốn có này. Ngoài ra, mật mã SP yêu cầu các S-box phải có thể đảo ngược (để thực hiện giải mã); Các chức năng bên trong của Feistel không có hạn chế như vậy và có thể được xây dựng như các chức năng một chiều.3 Tổng quan về DES 1.1 Mô tả về DES: DES (viết tắt của Data Encryption Standard, hay Tiêu chuẩn Mã hóa Dữ liệu) là một phương pháp mật mã hóa được FIPS (Tiêu chuẩn Xử lý Thông tin Liên bang Hoa Kỳ) chọn làm chuẩn chính thức vào năm 1976. Sau đó chuẩn này được sử dụng rộng rãi trên phạm vi thế giới.