Cryptography Reference
In-Depth Information
Input
:
P
[0
. . .
511].
Output
:
P
N
[0
. . .
511]
, Q
N
[0
. . .
511].
First Phase
:
for i ←
0
to
511
do
1
Determine
P
N
[
i
] using (10.14);
2
end
Second Phase
:
Form a bipartite graph
G
= (
V
1
, V
2
, E
) as follows;
3
V
1
←{
0
, . . . ,
255
}
;
V
2
←{
256
, . . . ,
511
}
;
E ←∅
;
4
for i ←
0
to
511
do
5
Determine
l
i
and
u
i
using (10.17);
6
E ← E ∪{l
i
, u
i
}
;
7
end
Find all connected components of
G
;
8
Let
C
=
{y
1
, y
2
, . . . , y
M
}
be the largest component with size
M
;
9
Guess
Q
[
y
1
] and thereby determine
Q
[
y
2
]
, . . . , Q
[
y
M
] from (10.16);
10
and for each such guess of
Q
[
y
1
], repeat the three Phases below;
Third Phase
:
for j ←
1
to M do
11
y ← y
j
;
12
while y ≤
499
do
13
if Q
[
y
+ 12]
IS STILL UNKNOWN then
14
h
i
h
i
(
Q
[
y
])
(0)
256 + (
Q
[
y
])
(2)
Q
[
y
+ 12]
← s
1,y+12
⊕
P
+
P
;
15
end
y ← y
+ 12;
16
end
end
Fourth Phase
:
for i ←
0
to
11
do
17
h
i
h
i
(
Q
[500 +
i
])
(0)
256 + (
Q
[500 +
i
])
(2)
Q
N
[
i
]
← s
3,i
⊕
P
N
+
P
N
;
18
y ← i
;
20
while y ≤
499
do
21
h
i
h
i
(
Q
N
[
y
])
(0)
256 + (
Q
N
[
y
])
(2)
Q
N
[
y
+ 12]
← s
3,y+12
⊕
P
N
+
P
N
;
22
y ← y
+ 12;
23
end
end
Fifth Phase
:
With the new
Q
N
, generate 512 keystream words by updating
P
N
;
24
Verify correctness of the guess in Step 10 by matching these keystream
25
words with the observed keystream words of block
B
4
;
Algorithm 10.5.1: ReconstructState
