Cryptography Reference
In-Depth Information
Corollary 4.5.7. For 0 ≤ w ≤ l−1, given a threshold H, the expected number
of distinct values ∈
Z
N
, each occurring > H times in T
w
, can be estimated
as N −
T H
E
c
, where E
c
is the expected number of distinct values ∈
Z
N
, each
c=0
occurring exactly c times in T
w
, as given in Theorem 4.5.6, item 2.
Now let us see how close the theoretical estimates are to the experimental
ones. Table 4.4 depicts some results corresponding to Theorems 4.5.4, 4.5.6.
For all key lengths, the estimates are given for κ[3] (i.e. for w = 3 and c = 2)
only as a representative. The experimental results are obtained by averaging
over 1 million runs, each with a randomly chosen key.
Similar results hold for all key bytes κ[w], 0 ≤ w ≤ l − 1, for each key
length l = 5,8,10,12 and 16, and for different values of c.
l
5
8
10
12
16
Theory 0.9991 0.9881 0.9729 0.9532 0.8909
Exp.
P
(
κ
[
w
]
∈ T
w
)
0.9994 0.9902 0.9764 0.9578 0.8970
Theory 0.0225 0.1210 0.1814 0.2243 0.2682
Exp.
P
(
freq
w
=
c
)
0.0186 0.1204 0.1873 0.2353 0.2872
Theory
6.8
4.3
3.5
3.0
2.1
E
(
freq
w
)
Exp.
6.8
4.3
3.5
2.9
2.1
Theory
138.5
99.2
84.2
73.4
55.9
E
dist
Exp.
138.2
98.9
84.0
73.2
55.8
Theory
34.7
18.1
13.1
10.0
5.8
E
c
Exp.
35.2
18.6
13.6
10.4
6.2
TABLE 4.4: Theoretical vs. empirical estimates with w = 3 and c = 2 for
Theorems 4.5.4, 4.5.6.
There are a few exceptions where the theoretical and the empirical values
are not close (e.g., the values in the second row and the column corresponding
to l = 5). These cases arise because the idealistic assumption of independence
of events does not always hold in practice. However, in general the theoretical
formula fits the empirical data to a very good approximation.
4.5.2 A Set of Recovery Methods
The above results can be used to devise an algorithm BuildKeyTable for
building a frequency table for each key byte and one can use the table to
extract information about the key.
Arrays jarr1 and jarr2 contain the values of j
y
's estimated from S
N
and
S
−
N
respectively. For each key byte κ[w], 0 ≤ w ≤ l−1, karr[w][y] stores the
frequency of the value y ∈
Z
N
. “x += 1” is a short form for “x←−x + 1.”
When guessing a specific key byte κ[w], Algorithm 4.5.1 considers all values
in Z
N
that have occurred at least once. However, other alternatives may
