Cryptography Reference
In-Depth Information
is the sum (truncated to n bits),
T = X ⊕Y ⊕Z
is their bitwise XOR. Let C
b
denote the carry bit generated in the b-th step
of the addition of X,Y and Z. C
b
can take the values 0,1 and 2, since three
bits are involved in the addition. For the LSB addition, C
−1
is assumed to be
0. Let
ρ
b,v
= Prob(C
b
= v),
b ≥−1,v ∈{0,1,2}.
We can write
Prob(S
b
= T
b
)
= Prob(C
b−1
= 0 or 2)
= ρ
b−1,0
+ ρ
b−1,2
=
1−ρ
b−1,1
.
One can easily show the following recurrences.
1. ρ
b+1,0
=
2
ρ
b,0
+
8
ρ
b,1
.
2. ρ
b+1,1
=
2
ρ
b,0
+
4
ρ
b,1
+
1
2
ρ
b,2
.
3. ρ
b+1,2
=
8
ρ
b,1
+
2
ρ
b,2
.
The solution gives ρ
b,1
=
3
(1−
1
4
b+1
) and so we can state the following result.
Proposition 10.2.1. For 0 ≤b ≤ n−1, Prob([S]
b
= [T]
b
) =
3
(1 +
1
2
2b−1
).
An immediate approximation to Proposition 10.2.1 is given in the following
corollary.
Corollary 10.2.2. For 0 ≤b ≤ n−1, Prob([S]
b
= [T]
b
) = p
b
, where
8
<
:
1
if b = 0;
1
2
p
b
=
if b = 1;
1
3
(approximately)
if 2 ≤ b ≤n−1.
During the keystream generation part of HC-128, the array P is updated
as
P[i mod 512] = P[i mod 512] + g
1
(P[i ⊟ 3],P[i ⊟ 10],P[i ⊟ 511]),
where
(x 10)⊕(z 23)
g
1
(x,y,z) =
+ (y 8).
Thus, we can restate the update rule as
P
up
[i mod 512]
= P[i mod 512] + ((P[i ⊟ 3] 10)⊕(P[i ⊟ 511] 23))
+(P[i ⊟ 10] 8).
(10.1)
