Cryptography Reference
In-Depth Information
Now, suppose that the condition (ii) holds. Then there exists exactly one
pair a,b ∈{1,...,m}, a = b, where y
a
= y
b
mod l. Without loss of generality,
let y
a
< y
b
. So we can subtract S
r
[y
a
] = f
y
a
from S
r
[y
b
] = f
y
b
to get one
l−1
equation involving some multiple of the sum s =
K[x] of the key bytes.
x=0
Thus, one can replace exactly one equation involving either y
a
or y
b
with the
new equation involving s, which will become a different equation with a new
variable K[l−1], since l−1 ∈{y
1
mod l,y
2
mod l,...,y
m
mod l}. Hence the
resulting system is independent.
Next, we show that the conditions are necessary. Suppose that neither
condition (i) nor condition (ii) holds. Then either we will have a triplet a,b,c
such that y
a
= y
b
= y
c
= mod l, or we will have a pair a,b with y
a
= y
b
mod l
and l− 1 ∈{y
1
mod l,y
2
mod l,...,y
m
mod l}. In the first case, subtracting
two of the equations from the third one would result in two equations involving
s and the same key bytes as variables. Thus the resulting system will not be
independent. In the second case, subtracting one equation from the other will
result in an equation which is dependent on the equation involving the key
byte K[l−1].
Part 2. We know that n = (⌊
l
⌋)l + (n mod l). If we compute y mod l,
for y = 0,1,...n−1, then we will have the following residue classes:
n
l
[0]
=
0,l,2l,...,
l
n
l
[1]
=
1,l + 1,2l + 1,...,
l + 1
.
.
.
[n mod l−1]
=
n mod l−1,l + (n mod l−1),2l + (n mod l−1),...,
n
l
l + (n mod l−1)
n
l
[n mod l]
=
n mod l,l + (n mod l),2l + (n mod l),...,
−1
l
+(n mod l)
.
.
.
n
l
[l−1]
=
l−1,l + (l−1),2l + (l−1),...,
−1
l + (l−1)
The set of these l many residue classes can be split into two mutually exclusive
subsets, namely A = {[0],...,[n mod l−1]} and B = {[n mod l],...,[l−1]},
such that each residue class ∈ A has ⌊
l
⌋+ 1 members and each residue class
∈B has ⌊
l
⌋ members. Note that |A| = n mod l and |B| = l−(n mod l).
Now, the independent systems of m equations can be selected in three
mutually exclusive and exhaustive ways. Case I corresponds to the condition
(i) and Cases II & III correspond to the condition (ii) stated in the theorem.
