Cryptography Reference
In-Depth Information
Input: Key pair (K
1
,K
2
) satisfying Equation (3.4).
Output: A colliding or near-colliding key pair.
r = MCS(K
1
,K
2
);
if r = N then
Stop (found a (near-)colliding pair) or return (to find more);
end
maxr =
max
0≤y≤N−1,y=d,d+1
1≤δ≤N−1
MCS(K
1
y,δ,K
2
y,δ);
if maxr ≤ r then
Return;
end
c = 0;
for all y from 0 to N −1 except d and d + 1 and for all δ from 1 to
N −1 do
if MCS(K
1
y,δ,K
2
y,δ) = maxr then
Call CollisionSearch(K
1
y,δ,K
2
y,δ);
c = c + 1;
if c = maxc then
Return;
end
end
end
Return;
Algorithm 3.4.1: CollisionSearch
