Înțelegerea neliniarității în Salsa20 pe diferite inele

În designul său pentru Salsa20, Bernstein scrie pentru a asigura neliniaritatea pe care a ales-o

Adăugarea pe 32 de biți (ruperea liniarității peste $Z/2$), Xor pe 32 de biți (liniaritatea de rupere peste $Z/2^32) și rotație pe 32 de biți la distanță constantă (difuzarea modificărilor de la biți înalți la biți mici).

Mă poți ajuta să înțeleg asta? O funcție liniară este una astfel încât $f(ax+by) = af(x) + bf(y)$. Se pare că dacă adunarea și xor sunt liniare depinde de definiția adunării și înmulțirii pe care o utilizați, care depinde de inelul pe care îl utilizați, dar rotația este liniară în orice inel.

De asemenea, $f$ ia o intrare, în timp ce 32 biți add sau xor iau două intrări, fiecare dintre acestea fiind o porțiune a elementului de 512 biți. Presupun că o funcție 2-ară este liniară dacă, fixând prima intrare, o funcție liniară 1-ară.

Se pare că dacă adunarea și xor sunt liniare depinde de definiția adunării și înmulțirii pe care o utilizați, care depinde de inelul pe care îl utilizați

Este destul de corect; operațiile care sunt liniare într-un inel nu trebuie să fie liniare într-un inel diferit.

dar rotația este liniară în orice inel

Nu; rotația nu este liniară în inel $\mathbb{Z}/{2^{32}}$

Iată un exemplu: lasă $F(x)$ fi $x$ rotit la dreapta o poziție.

Atunci, $F(1+1) = F(2) = 1$, in orice caz $F(1) + F(1) = 2^{31} + 2^{31} = 0$, prin urmare $F$ nu este liniară.

Presupun că o funcție 2-ară este liniară dacă, fixând prima intrare, o funcție liniară 1-ară.

Nu; dacă ar fi așa, atunci înmulțirea ar fi o operație liniară (pentru că dacă remediați una dintre intrări, este liniară în cealaltă).