Cryptography Reference
In-Depth Information
For example, when the success probability increases from 0.0006 to 0.006 (i.e.
increases by 10 times), the complexity increases by a factor of 2
14.7
.
4.3 Improvement by Difference Equations
The above algorithm was improved in [15] to achieve faster recovery of the
secret key at the same success probability.
Let
C
y
= S
N
[y]−
y(y + 1)
2
.
The equations of Section 4.2 can be rewritten as
K[0⊎y
1
]
= C
y
1
,
(4.8)
K[0⊎y
2
]
= C
y
2
,
(4.9)
b
etc., where K[a⊎b] has the usual meaning of
K[x]. One can subtract the
x=a
equations of the above form to generate more equations of the form
K[0⊎y
2
]−K[0⊎y
1
]
= K[y
1
+ 1⊎y
2
]
= C
y
2
−C
y
1
.
(4.10)
The approach in [15] makes use of the fact that Equation (4.10) holds with
more probability than the product of the probabilities of Equations (4.8)
and (4.9). For example, according to Corollary 3.1.6, P(K[0 ⊎ 50] = C
50
) =
0.0059 and P(K[0 ⊎ 52] = C
52
) = 0.0052, but P(K[51⊎ 52] = C
52
−C
50
) =
0.0624. Hence the use of the difference equations can give a more e
cient key
reconstruction. We summarize this technique in the following discussion.
Among the sums K[a⊎b] for different a,b, the sum
s = K[0⊎l−1]
of all the key bytes is guessed first. Plugging in the value of s reduces all the
remaining equations to sums of fewer than l variables, of the form
K[y
1
⊎y
2
],
0 ≤y
1
< l,y
1
≤ y
2
< y
1
+ l−1.
At each stage, the value for a new sum of key bytes is guessed. Equations
linearly dependent on prior guesses are no longer considered. After l such
guesses, the resulting set of equations reveals the key. Below we enumerate
additional techniques used in [15] toward improvement.
