Cryptography Reference
In-Depth Information
n
m
Proposition 4.2.3. Given n and m, it takes O(m
2
) time to generate
the set EI
m
using Theorem 4.2.2.
Proof: One needs to check a total of
n
m
},
and using the independence criteria of Theorem 4.2.2, it takes O(m
2
) amount
of time to determine if each tuple belongs to EI
m
or not.
Proposition 4.2.4. Suppose we have an independent system of equations of
the form S
r
[y
q
] = f
y
q
involving the l key bytes as variables corresponding to the
tuple {y
1
,y
2
,...,y
m
many m tuples {y
1
,y
2
,...,y
m
}, 0 ≤ y
q
≤ n−1, 1 ≤q ≤ m. If there is one equation in
l−1
K[x], then there are at most ⌊
l
the system involving s =
⌋ many solutions
x=0
for the key.
Proof: If the coe
cient of s is a, then by Linear Congruence Theo-
rem [169, Page 56], we would have at most gcd(a,N) many solutions for s,
each of which would give a different solution for the key. To find the maximum
possible number of solutions, we need to find an upper bound of gcd(a,N).
Since the key is of length l, the coe
cient a of s would be ⌊
y
l
⌋, where
y
s
is the y-value ∈{y
1
,y
2
,...,y
m
} corresponding to the equation involving s.
Thus,
y
s
l
n
l
gcd(a,N) ≤ a =
≤
.
Let us provide an example to demonstrate the case when we have two y-
values (equation numbers) from the same residue class in the selected system
of m equations, but still the system is independent and hence solvable.
Example 4.2.5. Assume that the secret key is of length 5 bytes. Consider 16
equations of the form S
N
[y] = f
y
, 0 ≤ y ≤ 15. One can study all possible sets
of 5 equations chosen from the above 16 equations and then try to solve them.
One such set would correspond to y = 0,1,2,3 and 13. Let the corresponding
S
N
[y] values be 246, 250, 47, 204 and 185 respectively. Then we can form the
following equations:
K[0]
=
246
(4.1)
K[0] + K[1] + (12)/2
=
250
(4.2)
K[0] + K[1] + K[2] + (23)/2
=
47
(4.3)
K[0] + K[1] + K[2] + K[3] + (34)/2
=
204
(4.4)
K[0] + ... + K[13] + (1314)/2
=
185.
(4.5)
From the first four equations, one readily gets K[0] = 246,K[1] = 3,K[2] = 51
and K[3] = 154. Since the key is 5 bytes long, K[5] = K[0],...,K[9] =
K[4],K[10] = K[0],...,K[13] = K[3]. Denoting the sum of the key bytes
K[0] + ... + K[4] by s, we can rewrite Equation (4.5) as:
2s + K[0] + K[1] + K[2] + K[3] + 91 = 185
(4.6)
