2.2. Các tính chất mật mã của hàm boolean¶
2.2.1. Bậc đại số cao¶
Tham số \(\deg f\) phải cao. Điều này đặc biệt quan trọng trong các stream cipher sử dụng LFSR.
2.2.2. Nonlinearity cao¶
Nonlinearity cực kì quan trọng trong việc chống phá mã tuyến tính (linear cryptanalysis). Nonlinearity càng cao, dấu vết tuyến tính càng thấp.
Hàm boolean có nonlinearity cực đại được gọi là hàm bent (hay bent function).
Theo phần đại số boolean ở trước thì
khi \(n\) chẵn.
Điều kiện cần và đủ để tồn tại hàm bent \(n\) biến là \(n\) chẵn.
Nếu \(n\) lẻ thì không tồn tại hàm bent \(n\) biến. Tuy nhiên chúng ta vẫn có thể xem xét các hàm có nonlinearity \(N_f\) lớn nhất và gọi chúng là Almost Bent (AB).
Khi đó
2.2.3. Balanced¶
Hàm Boolean được gọi là balanced (hay cân bằng, сбалансированный) nếu nhận giá trị \(0\) và \(1\) nhiều như nhau. Như vậy nếu hàm boolean \(f\) trên \(n\) biến cân bằng khi và chỉ khi
Bài tập: Xác định số lượng hàm boolean cân bằng có \(n\) biến.
2.2.4. \(r\)-resillient¶
Đặt \(r\) là số nguyên không âm nhỏ hơn \(n\). Hàm boolean \(f\) với \(n\) biến được gọi là \(r\)-resillient (hay \(r\)-устойчивой) nếu với mọi hàm con mà nhận được từ việc cố định \(r\) biến thì đều là hàm cân bằng.
Hàm boolean này có độ an toàn cao hơn so với hàm cân bằng, giúp chống lại cách tấn công correlation cryptanalysis.
2.2.5. Correlation immune¶
Hàm boolean \(f\) với \(n\) biến được gọi là correlation immune of order \(r\) (корреляционно-иммунной порядка \(r\), tạm dịch là kháng tương quan bậc \(r\)) với \(1 \leqslant r \leqslant n\) nếu với mọi hàm con \(f^{a_1, \ldots, a_r}_{i_1, \ldots, i_r}\) nhận được từ việc cố định \(r\) biến thì đều thỏa đẳng thức
2.2.6. Algebraic immune¶
Tính chất này được giới thiệu vào năm 2004.
Algebraic immune (tạm dịch là kháng đại số) của hàm boolean \(f\) là số \(d\) nhỏ nhất sao cho tồn tại hàm boolean \(g\) bậc \(d\), không đồng nhất với \(0\), thỏa mãn \(f g = 0\) hoặc \((f \oplus \bm{1}) g = 0\).
Algebraic immune của hàm \(f\) được kí hiệu là \(\mathsf{AI}(f)\).
Ví dụ algebraic immune hàm \(f(\bm{x}) = x_1 x_2 x_3 \oplus x_1\) bằng \(1\), vì ta có thể chọn \(g(\bm{x}) = x_1 \oplus 1\). Khi đó \(f g = (x_1 x_2 x_3 \oplus x_1) (x_1 \oplus 1) = 1\).
2.2.7. Differentially \(\delta\)-uniform¶
2.2.7.1. Differential \(\delta\)-uniform¶
Khái niệm này lần đầu được định nghĩa trong [24].
Hàm boolean vector \(F : \mathbb{F}_2^n \to \mathbb{F}_2^n\) gọi là differentially \(\delta\)- uniform nếu với mọi vector \(\bm{a}\) khác không và vector \(\bm{b}\) bất kì thì phương trình
có không quá \(\delta\) nghiệm với \(\delta\) là số nguyên dương.
Để ý rằng nếu phương trình có nghiệm là \(\bm{x}\) thì cũng có nghiệm \(\bm{x} \oplus \bm{a}\). Số \(\delta\) càng nhỏ thì phép biến đổi của thuật toán mã hóa càng ít có dấu hiệu vi sai, tăng khả năng kháng phá mã vi sai.
Một cách tổng quát ta có định nghĩa sau.
Định nghĩa 2.18 (Differential \(\delta\)-uniform)
Hàm boolean vector từ \(\mathbb{F}_p^n\) tới \(\mathbb{F}_p^m\) được gọi là differential \(\delta\)- uniform nếu với mọi \(\bm{a} \in \mathbb{F}_p^n\) khác không và với mọi \(\mathbb{F}_p^m\) thì phương trình
có không quá \(\delta\) nghiệm.
Trong mật mã học thường dùng \(p = 2\). Thông thường các hàm boolean tập trung vào việc xây dựng các S-box nên \(n\) thường là \(4\) hoặc \(8\).
2.2.7.2. Perfect Nonlinear và Almost Perfect Nonlinear¶
Định nghĩa 2.19 (Hàm Perfect Nonlinear)
Hàm boolean vector \(F\) từ \(\mathbb{F}_p^n\) tới \(\mathbb{F}_p^m\) được gọi là hàm Perfect Nonlinear (PN) nếu phương trình
có đúng \(p^{n-m}\) nghiệm với mọi vector \(\bm{a} \in \mathbb{F}_p^n\) khác không và \(\bm{b} \in \mathbb{F}_p^m\).
Số lượng hàm PN rất ít. Đối với các giá trị \(n\) và \(p\) thường được sử dụng trong mật mã thậm chí không tồn tại hàm PN. Do đó chúng ta sẽ nới lỏng điều kiện thành hàm Almost Perfect Nonlinear (APN).
Định nghĩa 2.20 (Hàm Almost Perfect Nonlinear)
Hàm boolean vector \(F\) từ \(\mathbb{F}_p^n\) tới \(\mathbb{F}_p^m\) được gọi là hàm Almost Perfect Nonlinear (APN) nếu phương trình
có không quá hai nghiệm với mọi \(\bm{a} \in \mathbb{F}_p^n\) khác không và với mọi \(\bm{b} \in \mathbb{F}_p^m\).
Bài toán khó hiện nay là xây dựng hàm APN là song ánh với số biến \(n\) chẵn. Đặc biệt là \(n\) có dạng lũy thừa của \(2\).
Như vậy, theo định nghĩa có thể thấy điều tương đương sau
APN là differential \(2\)-uniform.
PN là differential \(1\)-uniform khi \(n = m\).
2.2.7.3. Hoán vị APN¶
Từ trước tới nay có ba phương pháp xây dựng hoán vị APN trên \(\mathbb{F}_2^n\). Tuy nhiên cả ba phương pháp chỉ hoạt động trên \(n\) lẻ. Câu hỏi về việc xây dựng hoán vị APN tới giờ vẫn là vấn đề mở với \(n\) chẵn, dặc biệt là \(n\) có dạng lũy thừa của \(2\) như đã nói ở trên.
Lời giải cho các bài tập trên ở chương Симметричная криптография.