3.5. Mô hình Feistel¶
3.5.1. Mô tả mô hình Feistel¶
Trong mô hình Feistel, mỗi block đầu vào được chia thành hai nửa trái phải có số bit bằng nhau.
Một cách hình thức, giả sử plaintext đầu vào là \(P\) có \(2n\) bit, thì \(P\) được chia thành nửa trái \(L_0\) và \(R_0\), mỗi nửa có \(n\) bits.
Mỗi hệ mã Feistel có một hàm \(F(R_{i-1}, K_i)\) nhận đầu vào là nửa phải ở vòng thứ \((i-1)\) và khóa \(K_i\) ở vòng thứ \(i\). Hàm \(F\) được gọi là round function.
Ở mỗi vòng \(i = 1, 2, \ldots\), hai nửa trái phải mới sẽ được tính theo công thức
trong đó:
\(L_{i-1}\) và \(R_{i-1}\) là nửa trái và nửa phải ở vòng thứ \((i-1)\);
\(L_i\) và \(R_i\) là nửa trái và nửa phải ở vòng thứ \(i\);
\(K_i\) là khóa con được dùng ở vòng \(i\);
\(F\) là round function.
Hình 3.14 Mô hình Feistel¶
Nếu thuật toán kết thúc sau \(r\) vòng (với \(r\) khóa con) thì ciphertext tương ứng sẽ là \(C = L_r \Vert R_r\).
3.5.2. Tính chất của mô hình Feistel¶
Mô hình Feistel không đòi hỏi round function \(F\) phải khả nghịch. Giả sử ciphertext là \(C = L_r \Vert R_r\). Khi đó dựa trên công thức mã hóa ở trên thì có thể dễ dàng suy ra công thức giải mã là
với \(i = r-1, \ldots, 0\).
Plaintext nhận được sẽ là \(P = L_0 \Vert R_0\).
3.5.3. Một số thuật toán sử dụng mô hình Feistel¶
3.5.3.1. Mô hình Feistel chuẩn¶
Mô hình Feistel chuẩn là mô hình ở trên. Các thuật toán sử dụng mô hình Feistel chuẩn có thể kể đến là: DES, Magma (tiêu chuẩn mã hóa Nga, định nghĩa trong GOST 34.12.2015, version \(64\) bit), CAST-128 (tiêu chuẩn mã hóa Canada).
3.5.3.2. Mô hình Feistel tổng quát¶
Mô hình Feistel tổng quát (generalized Feistel model) có nhiều biến thể. Trong đó khối đầu vào không được chia thành hai nửa trái phải mà có thể được chia thành bốn phần \(P = X_0 \Vert X_1 \Vert X_2 \Vert X_3\), mỗi phần có số bit bằng nhau.
Sau đó, ở mỗi vòng, bốn phần ở vòng \(i\) nhận được từ bốn phần ở vòng \((i - 1)\), thông thường là từ việc giữ lại ba phần (nhưng ở vị trí khác) và XOR phần còn lại với một round function lấy tham số là ba phần kia cùng với khóa con ở vòng \(i\). Ví dụ
trong đó:
\(X^{(i)}_0\), \(X^{(i)}_1\), \(X^{(i)}_2\), \(X^{(i)}_3\) là bốn phần ở vòng thứ \(i\);
\(X^{(i-1)}_0\), \(X^{(i-1)}_1\), \(X^{(i-1)}_2\), \(X^{(i-1)}_3\) là bốn phần ở vòng thứ \((i-1)\);
\(K_i\) là khóa con ở vòng thứ \(i\);
\(F\) là round function nhận bốn đầu vào gồm ba phần ở vòng thứ \((i-1)\) và khóa con ở vòng thứ \(i\).
Lưu ý rằng trên đây chỉ trình bày một dạng biến thể của mô hình Feistel tổng quát.
Một số thuật toán sử dụng mô hình Feistel tổng quát: SM4 (tiêu chuẩn mã hóa mạng không dây của Trung Quốc).