HASH函数

hash函数就是将映射到的函数，即将任意长度的比特串映射为n-bits

即其中H叫做像，M是原像

一个好的hash函数需要满足一下属性

1.抗原像攻击

给定H,找到X，使得h(X)=H是困难的

2.抗第二原像攻击（弱抗碰撞）

给定X,找到X’使得h(X)=h(X’)是困难的

3.抗碰撞攻击

找到任意两个X和X’,满足h(X)=h(X’)是困难的

（任何一个第二原像都不存在）

为什么抗碰撞性更强？

如果一个哈希函数是抗碰撞的，那么它必然也是抗第二原像的。

理由：如果攻击者能对一个给定的 x
成功进行第二原像攻击（找到 x’ 使得
H(x’) = H(x)），那么他实际上就找到了一个碰撞对
(x, x’)。所以，抗碰撞失败必然导致抗第二原像失败。

反之则不然！一个哈希函数可以是抗第二原像的，但却不抗碰撞。

理由：攻击者可能无法为某个特定的、随机的
x 找到碰撞伙伴
x’（满足抗第二原像），但他可能通过精心构造的方法找到任意一对特殊的消息
y 和 y’（y 和 y’
都不是那个特定的 x），使得
H(y) = H(y’)（即不抗碰撞）。MD5
就是一个经典例子：虽然在实际中寻找第二原像仍然非常困难（理论上有弱点），但找到碰撞对在普通计算机上几秒内即可完成。

4.抗长度拓展攻击

给定h(X)和X的长度|X|,找到H’和Z,使得h(X||Z)=H‘是困难得

hash函数设计

1.先进行填充，使填充后的消息长度为m的整数倍，

2.分组，分为

3.压缩，将压缩到

令,然后依次计算

ezhash？！

这个题目同样是比较简单的一个题目，给出解题思路，代码交给读者复现

第一部分得到key

“用最合适的工具解决最合适的问题，Gurobi 解决线性优化最快，SAT
求解器解决布尔逻辑最快，Z3 处理复杂混合逻辑最灵活。”

使用z3求解器，使用一组test就能得到key

第二部分构造格求解

在这个逐字节加密的hash函数中异或是极难处理的，但是他其实只有7比特大小，所以
异或我们可以把他当作加上一个7比特的随机数，于是我们就可以写成这样的式子
然后用这个式子去构造格就好了

from lbc_toolkit import ehnp
import json
from sage.all import *
from hashlib import md5

with open('data.json', 'r') as f:
    json_data = json.load(f)

xbar, p, Pi, Nu, Alpha, Rho, Mu, Beta = (json_data[key] for key in ('xbar', 'p', 'Pi', 'Nu', 'Alpha', 'Rho', 'Mu', 'Beta'))
sol = ehnp(xbar, p, Pi, Nu, Alpha, Rho, Mu, Beta, delta=1/10^12, verbose=True)
print('  Found  solution:', sol, end='\n\n')
print('  Correctness',sol == _x)

print('flag :'+ 'flag{' + md5(str(sol).encode()).hexdigest() + "}")