Hiểu tính phi tuyến tính trong Salsa20 trên các vòng khác nhau

Trong thiết kế Salsa20 của mình, Bernstein viết để đảm bảo tính phi tuyến tính mà ông đã chọn

Bổ sung 32-bit (phá vỡ tuyến tính trên $Z/2$), Xor 32 bit (phá vỡ tuyến tính trên $Z/2^32) và xoay 32 bit khoảng cách không đổi (sự thay đổi khuếch tán từ bit cao sang bit thấp).

Bạn có thể giúp tôi hiểu điều này? Hàm tuyến tính là hàm sao cho $f(ax+by) = af(x) + bf(y)$. Có vẻ như phép cộng và xor có tuyến tính hay không phụ thuộc vào định nghĩa của phép cộng và phép nhân mà bạn đang sử dụng, điều này phụ thuộc vào việc bạn đang sử dụng vòng nào, nhưng phép quay là tuyến tính trong bất kỳ vòng nào.

Cũng thế, $f$ nhận một đầu vào, trong khi add hoặc xor 32 bit nhận hai đầu vào, mỗi đầu vào là một phần của phần tử 512 bit. Tôi giả sử hàm 2-ary là tuyến tính nếu, việc sửa đầu vào đầu tiên sẽ tạo ra hàm 1-ary tuyến tính.

Có vẻ như phép cộng và xor có tuyến tính hay không phụ thuộc vào định nghĩa của phép cộng và phép nhân mà bạn đang sử dụng, điều này phụ thuộc vào việc bạn đang sử dụng vòng nào

Điều đó hoàn toàn chính xác; các hoạt động tuyến tính trong một vòng không nhất thiết phải tuyến tính trong một vòng khác.

nhưng phép quay là tuyến tính trong bất kỳ vòng nào

Không; quay không tuyến tính trong vòng $\mathbb{Z}/{2^{32}}$

Đây là một ví dụ: hãy để $F(x)$ thì là ở $x$ quay sang phải một vị trí.

Sau đó, $F(1+1) = F(2) = 1$, Tuy vậy $F(1) + F(1) = 2^{31} + 2^{31} = 0$, vì thế $F$ là không tuyến tính.

Tôi giả sử hàm 2-ary là tuyến tính nếu, việc sửa đầu vào đầu tiên sẽ tạo ra hàm 1-ary tuyến tính.

Không; nếu đúng như vậy, thì phép nhân sẽ là một phép toán tuyến tính (bởi vì nếu bạn sửa một trong các đầu vào, thì nó sẽ tuyến tính ở đầu vào kia).