How to blow up too weak hashing without thinking

Правка en1, от physics0523, 2024-05-02 23:23:42

Sadly, until today, many people use single $$$\rm{mod} = 10^9+7$$$ or so on for hashing, so why not write how to blow up them easily, with minimized thinking process?

The key idea is simple. Just use Birthday attack.

  1. Write a function to calculate the hash value
  2. Write a random generator of string
  3. When there are $$$k$$$ possible distinct hash values, look up $$$O(\sqrt{k})$$$ random candidates
  4. Now we get a pair of strings that has exactly the same hash value!

In this method, the only things we should consider are that $$$k$$$ is small enough (around $$$k \le 10^{12}$$$ ), and the number of possible candidates is large enough. We don't need to care about what the hashing function is!

Example Code(C++)

Exercise:
Find two $$$18$$$-digit integers $$$x,y$$$ such that:

  • Each digit of $$$x,y$$$ are $$$1,3,5,7,9$$$
  • $$$x \equiv y \mod 998244353$$$
Short Explanation
Example Code(C++)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский physics0523 2024-05-02 23:29:44 281 Tiny change: 'hash value.\n- Add r' -> 'hash values.\n- Add r'
en1 Английский physics0523 2024-05-02 23:23:42 3408 Initial revision (published)