Cryptography Reference
In-Depth Information
Subtracting Equation (4.4) from Equation (4.6), and solving for s, we get
s = 76 or 204. Taking the value 76, we get
K[0] + K[1] + K[2] + K[3] + K[4] = 76
(4.7)
Subtracting Equation (4.4) from Equation (4.7), we get K[4] = 134. Taking
s = 204 does not give the correct key, as can be verified by running the KSA
and observing the permutation obtained.
We now present the general algorithm for recovering the secret key bytes
from the permutation at any stage of the KSA.
Input:
1. Number of key bytes: l.
2. Number of key bytes to be solved from equations: m (≤ l).
3. Number of equations to be tried: n (≥ m).
4. The stage r of the PRGA.
5. The permutation bytes S
r
[y], 0 ≤ y ≤ r−1.
Output: The recovered key bytes K[0],K[1],...,K[l−1] or FAIL.
for each distinct tuple {y
1
,y
2
,...,y
m
}, 0 ≤y
q
≤n−1, 1 ≤ q ≤m
1
do
if the tuple belongs to EI
m
then
2
Arbitrarily select any m variables present in the system;
3
Solve for the m variables in terms of the remaining l−m
4
variables;
for each possible assignment of the l−m variables do
5
Find values of the other m key bytes;
6
If the correct key is found, return it;
7
end
end
end
if none of the |EI
m
| systems of m independent equations yields the
correct key then
Return FAIL;
end
Algorithm 4.2.1: RecoverKey
Note that the correctness of a key can be verified by running the KSA and
comparing the resulting permutation with the permutation at hand.
If one does not use the independence criteria (Theorem 4.2.2), all
n
m
sets of equations need to be checked. However, the number of independent
