[Crypto] hashcoll - CirQ xp0int Posted on Aug 25 2018 有点气，早点发现的话说不定能拿一血，名次还能进个位数，可惜当时跟permgame杠上了。。。 每次拿到crypto题目的python源码时都有种prettyfy的冲动，例如改成这样： ```python def shitty_hash(msg): h = 45740974929179720441799381904411404011270459520712533273451053262137196814399 g = 0x1000000000000000000000000000000000000000163 # 2**168 + 355 for i in map(ord, msg): h = (h + i)*g # This line is just to screw you up :)) h = h % 0x10000000000000000000000000000000000000000000000000000000000000000 return h - 0xe6168647f636 ``` 题目通过上面的算法生成字符串的hash，把代码写成数学表达式： $$H(c)=h_0g^n+c_0g^{n}+c_1g^{n-1}+\dots+c_{n-1}g\ mod\ N-C$$ $c_i$表示字符，那么上式的变量部分只有中间的多项式。本来卡在这里了，晚上再仔细一查，发现这种通过多项式生成hash的算法叫做rolling hash，然后找到了一篇[论文](https://www.mii.lt/olympiads_in_informatics/pdf/INFOL119.pdf)描述如何在$N=2^k$的情况下生成碰撞的原像，不再赘述。 打赏还是打残，这是个问题 赏 Wechat Pay Alipay [Rev]beijing-MF [Rev]advanced-sherlly
没有帐号? 立即注册