Cryptography Reference
In-Depth Information
When there is talk about linear cryptanalysis, you can often read: '
...
works
with linear approximations, thus trying to recover the key', or perhaps: 'you
XOR a few bits of the plaintext and the ciphertext, and there is a certain
probability that you will obtain a value produced by XORing several key bits'.
Such statements don't explain the background. A few theoretical comments
will be useful before describing the method itself.
Linear Method
What does 'linear' mean? In algebra, a linear expression in variables,
x
1
,...,x
n
,
has the form
a
1
x
1
+a
2
x
2
+ ... + a
n
x
n
where
a
i
are constants. We are not looking at integer or real numbers in this
discussion, but at the 'value range' of a bit, which is the numbers 0 and 1. We
know that an addition is defined on this two-element number field, namely the
XOR operation:
⊕
0=0
0
0
⊕
1=1
⊕
0=1
1
⊕
1=0
The commutative and associative laws hold, similarly to a normal addition:
⊕
b=b
⊕
a
a
⊕
⊕
c)=(a
⊕
⊕
a
(b
b)
c
There is also a multiplication in set
{
0,1
}
(or we couldn't call it a number field).
This is the 'AND' link ('&' in C):
0*0 = 0*1 = 1*0 = 0
1*1=1
The usual arithmetic rules for real numbers apply here, too, though they may
seem a bit odd. Analogous operations can be defined bitwise, e.g., on 64-bit
blocks.
