yugt / sha256-prefix-collision Goto Github PK

Current data structure uses C++ STL std::unordered_map which uses hash table. This can be suboptimal.

Trie data structure insertion and look-up time complexity are both O(log(n)) where n is the length of prefix, and for 16 hex-digit prefix, this can be treated as constant time, and may be faster than std::unordered_map by a constant factor.

argv[1] is the first character of input text (of length 6). For example,
./a.out z
finds the prefix collisions where
SHA256(z?????)[0:16] == SHA256(z?????)[0:16]
where ? represents a character among {0, ..., 9, A, ..., Z, a, ..., z} (Shell convention for single wildcard and Python convention for slicing).
Moreover,
./a.out y
finds the prefix collisions where
SHA256(y?????)[0:16] == SHA256(y?????)[0:16] and SHA256(y?????)[0:16] == SHA256(z?????)[0:16].

Similarly,
./a.out x
finds the prefix collisions where
SHA256(x?????)[0:16] == SHA256(x?????)[0:16] and
SHA256(x?????)[0:16] == SHA256(y?????)[0:16] and
SHA256(x?????)[0:16] == SHA256(z?????)[0:16].

So on so forth.

A corollary is that ./a.out z runs for shortest time while ./a.out 0 runs for the longest time since it needs to find prefix collisions where
SHA256(0?????)[0:16] == SHA256(0?????)[0:16] and
SHA256(0?????)[0:16] == SHA256(1?????)[0:16]
...
SHA256(0?????)[0:16] == SHA256(y?????)[0:16] and
SHA256(0?????)[0:16] == SHA256(z?????)[0:16].

This search algorithm can be adapted to run on GPU to speed up the SHA256 calculation.