Một số câu hỏi về cách xây dựng hoán vị từ các hàm boolean
Tôi đã thấy nhiều ví dụ về các hàm boolean được sử dụng như một hoán vị.
Ví dụ hàm Keccak Chi: 2.3.1 :
từ https://keccak.team/figures.html
Hoặc như một công thức: cho $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ với các chỉ số được tính theo modulo 5
Câu hỏi đầu tiên sẽ là, cơ sở lý luận (hoặc bằng chứng) tại sao đây là một hoán vị là gì?
Điều thứ hai, liên quan: Các thuộc tính, hàm boolean có để thỏa mãn rằng nó dẫn đến một hoán vị là gì?
Và bây giờ liên quan đến nghịch đảo của một hoán vị như vậy.
Có bất kỳ phương pháp / thuật toán chung nào để tìm ra nghịch đảo của cấu trúc như vậy không?
Ngoài ra, những yếu tố góp phần chính cho sự phức tạp của nghịch đảo (số lượng biến, mức độ đại số, v.v.) là gì?
Và nếu một phương pháp như vậy được áp dụng cho đầu vào lớn hơn - giả sử $i=\{0..127\}$, là nghịch đảo khó tính hơn, nếu hàm chỉ có một vài (như 3 đối với Chi) hoặc nhiều, chẳng hạn 128, biến đầu vào?
Bất kỳ câu trả lời / con trỏ nào được đánh giá cao.
Trả lời
Câu hỏi đại số tổng quát có nhiều nghĩa và có thể khá phức tạp. Một số phụ thuộc vào không gian vectơ, một số phụ thuộc vào thuộc tính trường mở rộng.
Như đã đề cập trong các nhận xét, việc kiểm tra tài sản có thể đơn giản hơn.
Tôi đã trả lời một câu hỏi liên quan Ví dụ về các hàm Boolean cân bằng bit đa đầu ra
Các bài báo của Nyberg được đề cập đến có
K. Nyberg, Ánh xạ đồng nhất khác biệt cho mật mã , 1993 và
K Nyberg, Hộp chữ S phi tuyến hoàn hảo , 1992
cả hai đều dễ dàng định vị trên google học giả.
Chỉnh sửa : Keccak$\chi$ bản đồ $\{0,1\}^5$ cho chính nó.
tôi sẽ sử dụng $a_i$ như đầu vào và $A_i$ dưới dạng các biến đầu ra như trong câu hỏi đã chỉnh sửa.
Đếm chỉ số modulo 5, nếu không có $i$ như vậy mà $(a_i,a_{i+2})=(0,1)$ sau đó $\chi$có một điểm cố định cho đầu vào đó. Để cho$W=\{i: (a_i,a_{i+2})=(0,1)\},$ thì ánh xạ chung chỉ đảo ngược các bit thuộc về $i.$
Lưu ý rằng các bộ $J_i,J_j$ Ở đâu $J_i=\{i,i+2\}$ rời rạc ngoại trừ khi $j=i+2$ hoặc là $i=j+2.$Vì vậy, không có gì mơ hồ để xác định nghịch đảo trừ khi chúng ta ở trong trường hợp đặc biệt này, do đó nghịch đảo tồn tại ngoại trừ trường hợp đặc biệt này. Nhưng ngay cả trong trường hợp này, các mẫu$(a_i,a_{i+2},a_{i+4})$ mà kết quả là bitflips là rõ ràng.
Nếu $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ sau đó $a_{i+1}$ sẽ được lật nhưng không $a_{i+3}$. Vì thế$A_{i+1}=1\oplus a_{i+1},$ và $A_{i+3}=a_{i+3}.$
Nếu $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ sau đó $a_{i+1}$ sẽ được lật nhưng không nhất thiết $a_{i+3}$, điều đó sẽ phụ thuộc vào giá trị của $a_{i+6}=a_{i+1}$. Nhưng bit đó không bị ảnh hưởng bởi đối số trước đó vì$J_i$ và $J_j$ rời rạc nếu $i=j+1\pmod 2.$
Vì vậy, một ánh xạ nghịch đảo duy nhất tồn tại.
Nhận xét : Nhìn chung việc đi lại giữa các công thức trường mở rộng "độc lập cơ sở" của hoán vị và hoán vị vectơ bit "phụ thuộc cơ sở" là khó dễ dàng. Tôi không thấy một công thức trường mở rộng độc lập cơ sở ngay lập tức cho hoán vị này, và như đã chỉ ra trong các nhận xét cho câu hỏi các công thức như vậy thu được (giả sử) bằng nội suy Lagrange, có thể khá phức tạp và mức độ cao.
Các $\chi$chức năng được định nghĩa và phân tích trong Joan Daemen Ph.D. Luận văn
- Các chiến lược thiết kế hàm mã hóa và hàm băm dựa trên phân tích mã hóa tuyến tính và vi phân, 1995
Chương 6: Phép biến đổi bất biến (SIT) là nơi lý thuyết được đề cập đến. Tôi sẽ cung cấp một cái nhìn sơ lược về nó (rất nhiều định nghĩa và kết quả).
Các thuộc tính của SIT khiến chúng trở nên hữu ích;
- Trong phần cứng, các phép biến đổi này có thể được thực hiện như một mảng được kết nối với nhau của các “bộ xử lý” đầu ra 1 bit giống hệt nhau.
- Sự thay đổi-bất biến đảm bảo rằng tải tính toán được phân phối tối ưu.
- Trong phần mềm, tính thường xuyên của chúng cho phép triển khai hiệu quả bằng cách sử dụng các phép toán logic bit.
- Hơn nữa, các phép biến đổi nhị phân-bất biến có thể được chỉ định bởi một hàm Boolean duy nhất.
SIT rất liên quan đến tự động tế bào hữu hạn, tập trung vào cấu trúc và mô hình dài hạn theo thời gian, công việc này tập trung vào các khía cạnh ngắn hạn của tính không thuận nghịch và lan truyền cục bộ và các đặc tính tương quan.
Định nghĩa 6.1: Một phép biến hình$\phi: \mathcal{A} \to \mathcal{A}$là thay đổi bất biến nếu
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ Ở đâu $\mathcal{A}$ là tất cả các trạng thái có thể.
Sau đó, nó xác định các bản đồ địa phương nơi hình ảnh chỉ phụ thuộc vào một số đầu vào.
Định lý 6.1 (D. Richardson) Nếu một phép biến hình$\phi$ với hữu hạn $\nu$ là nghịch đảo, sau đó là nghịch đảo của nó $\phi^{−1}$ là một phép biến đổi bất biến với hữu hạn $\nu$.
Ở đâu $\nu$xác định vùng lân cận, xem 6.3 Bản đồ địa phương . Định lý này không cung cấp cấu trúc của nghịch đảo một cách rõ ràng.
Phần 6.6 Các phép biến đổi phi tuyến với hữu hạn $\nu$ là nơi bắt đầu hành động.
Ở đây, bản đồ địa phương được xác định bởi một tập hợp các mẫu, được gọi là các cảnh quan bổ sung (CL). Giá trị của một thành phần được bổ sung nếu vùng lân cận của nó có một trong những mẫu này. Phong cảnh là một mẫu bao gồm các biểu tượng$1, 0$, và $\textbf{-}$ biểu thị "không quan tâm", được định vị so với nguồn gốc, được biểu thị bằng $∗$. Trong ngữ cảnh này, trạng thái hoàn toàn bằng không sẽ được ký hiệu bằng$0^*$ và trạng thái tất cả bởi $1^*$.
Sự nghịch đảo của $\chi$được nói đến trong các phần về khả năng biến tần cục bộ và toàn cầu đòi hỏi lý thuyết sâu hơn. Một bài đọc hay để tìm hiểu nếu bạn muốn.
Vì vậy, Như tôi đã nói trong phần bình luận, người ta có thể tìm kiếm tất cả các hoán vị có thể có để xem thuộc tính mong muốn, hoặc xem xét trên lý thuyết như Daemen, đã làm. Họ sử dụng lý thuyết này nhiều năm sau đó trong việc xây dựng Sponge, nơi$\chi$ là phần phi tuyến tính duy nhất của SHA-3.
Vì câu hỏi đầu tiên của tôi đã được trả lời chi tiết trong câu trả lời của kodlu và kelalaka, tôi muốn chia sẻ kết quả mà tôi thu thập được về câu hỏi thứ hai của mình kể từ khi đăng:
Các tính chất, hàm boolean có để thỏa mãn nó dẫn đến một hoán vị là gì?
Trong nhiều lần đọc thêm, tôi phát hiện ra rằng đây có vẻ là một tài sản tốt (nhưng không được nhiều người biết đến). Ví dụ được nêu và chứng minh trong Các hàm Boolean Vectơ cho Mật mã chương 2.3.1 như Mệnh đề 2:
Một (n, m)-hàm là cân bằng nếu và chỉ khi các hàm thành phần của nó là cân bằng, nghĩa là, nếu và chỉ khi, với mọi khác 0 v ∈ $F^2_m$, hàm Boolean v · F là cân bằng.
với thực tế bổ sung từ chương 2.3:
Các hàm cân bằng (n, n) là các hoán vị trên $F^2_n$
Vì vậy, một (n, n)-hàm là một hoán vị, nếu và chỉ khi nó là cân bằng theo định nghĩa trên.
Nói cách khác, mọi chức năng thành phần phải được cân bằng, cũng như mọi sự kết hợp có thể có của các chức năng thành phần, bao gồm cả. tất cả các chức năng cùng một lúc, phải được cân bằng.
Nhân tiện, tính chất này cũng được nêu, ít rõ ràng hơn, trong Chiến lược thiết kế hàm mã hóa và hàm băm dựa trên phân tích mật mã tuyến tính và vi phân, 1995 Định lý 5.1
Điều này cũng có nghĩa là, việc kiểm tra thuộc tính này cho trường hợp chung cho các hàm lớn hơn, ví dụ: rộng 64 bit (n = 64), là không khả thi vì nó sẽ yêu cầu kiểm tra tính cân bằng cho 2 ^ 64 - 1 kết hợp khác nhau (cho 2 ^ 64 đầu vào có thể cho mỗi đầu vào) . Vì vậy, một số thủ thuật hoặc phím tắt có thể sẽ được yêu cầu.