Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I was reading this answer, How secure is XOR for encryption, and it stated that XOR's aren't good for securing messages as they are linear in Nature. And therefore should be paired with some non-linear elements like Substitution box to provide strength to the encryption.
My question is, what are linear/Non-linear elements, in context of cryptography? And what are advantages and disadvantages of each over the other.
A mathematical function $f$ is linear if it is of the form $f(t) = c + g(t)$ where $c$ is a constant and $g$ has the property that $g(a + b) = g(a) + g(b)$. (Strictly speaking, in math one usually considers only $g$ to be linear and $f$ to be merely affine, but we don't make that distinction here.) We also say that a function $\phi(s, t)$ of two arguments is bilinear, or again just linear, if for each $s_0$ and $t_0$, the functions $t \mapsto \phi(s_0, t)$ and $s \mapsto \phi(s, t_0)$ are linear.
Exercise. Prove that the function $(s, t) \mapsto s + t$ is bilinear.
If we're talking about real numbers, like 0, −3, 1/48, $\pi$, etc., linear functions are of the form $f(x) = mx + b$ for constants $m$ and $b$, which you may recognize as the equation of a (nonvertical) line. But we don't have to talk about real numbers; we can consider integers too, or even the remainders of integers after dividing by 2 (‘modulo 2’), where $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, and $1 + 1 = 0$. The linear functions in this case are still of the form $f(x) = mx + b$, but the only two possible values for $m$ and $b$ are 0 and 1, so there are only four such linear functions.
We can also do addition and multiplication of polynomials, or of matrices of higher dimensions. Each space has its own notion of linear functions, defined in terms of that space's notion of addition. Linear functions are easy to compute—and easy to invert, or at least partially invert: in spaces where we have a notion of division (like rational numbers), we can recover $x$ from $f(x)$ by $x = (f(x) - b)/m$; in other spaces, like matrices, we have easy algorithms like Gaussian elimination to solve linear systems.
Suppose you have a string of bits, say 10110 or 00111. One way to interpret the bits is an integer, in this case 22 or 7 (in decimal). Another way is to interpret the bits as a polynomial with coefficients modulo 2, in this case $x^4 + x^2 + x$ or $x^2 + x + 1$. If we add these in their respective spaces and convert back to a string of bits, we get different answers:
\begin{gather} 22 +_\mathbb Z 7 = 29 \longrightarrow \mathtt{11101} \\ (x^4 + x^2 + x) +_2 (x^2 + x + 1) = x^4 + x + 1 \longrightarrow \mathtt{10011}. \end{gather}
Exercise. Why did the $x^2$ term disappear?
Here I have labeled the integer addition operation as $+_\mathbb Z$ and the polynomial modulo 2 addition operation as $+_2$. We could also write both sides of the equation as a string of bits; when we use $+_\mathbb Z$ and $+_2$, we may get different answers, as strings of bits:
\begin{align} \mathtt{10110} +_\mathbb Z \mathtt{00111} &= \mathtt{11101} \\ \mathtt{10110} +_2 \mathtt{00111} &= \mathtt{10001}. \end{align}
Exercise. Is there another name for $+_2$?
Exercise. Find two bit strings $s$ and $t$ such that $s +_\mathbb Z t = s +_2 t$.
Although $+_\mathbb Z$ is linear (or, more precisely, bilinear) in integer addition, it is not linear in polynomial modulo 2 addition—in other words, although, e.g., $t \mapsto s_0 +_\mathbb Z t$ is linear over $+_\mathbb Z$ meaning it is of the form $t \mapsto c +_\mathbb Z g(t)$, specifically with $c = s_0$ and $g(t) = t$, this function is not of the form $c +_2 g(t)$ for any $c$ or $g$. Conversely, $+_2$ is linear in polynomial modulo 2 addition but not in integer addition.
In other words, xor is linear in polynomial modulo 2 addition, but not in integer addition; conversely, integer $+$ is linear in integer addition, but not in polynomial modulo 2 addition. When you combine the two—e.g., consider the function $(u, v, w) \mapsto (u +_\mathbb Z v) +_2 w$—the result is a function that is nonlinear in both spaces, which means it does not admit any neat algebraic simplification or inversion like $(f(x) - b)/m$ or Gaussian elimination. This in turn means that cryptanalysis can't take advantage of neat algebraic simplification or inversion, and so may be much harder.
Xor is linear because its answers are predicted and they’re 4 possible outcomes of this. So this can be broken or breached by brute force of some other techniques. On the other hand, non linear operation includes linear plus other s-boxes techniques which is based on some finite-field inverse and some shuffling.
