Crypto入门-密码学杂谈
Crypto入门-密码学杂谈
Diffie-Hellman密钥交换
在双方先前没有任何共同知识的情况下通过不安全信道协商出一个对称密钥。
DH密钥交换算法：双方选择一个$p\in\mathbb P$和$\mathbb Zp*$的一个生成元$g$，在不安全的信道上发送。A选择一个秘密$a\in\mathbb Z$，计算$A=g^a\bmod p$并发送给B。B选择一个秘密$b\in\mathbb Z$，计算$B=g^b\bmod p$并发送给A。A与B可共同得出密钥$k=A^b\bmod p=B^a\bmod p=g^{ab}\bmod p$。
当中间人截获信息但不能修改时，知道$A,B,g,p$而不知道$a,b$，计算$\log_aA,\log_bB$很困难。
DH中间人攻击
当中间人可以截获并修改信息时。
中间人获取到$p$和$g$。现在A正要把$A$发给B，此时中间人截获$A$，自己选定一个随机数$e_1$，将$A$换成$E_1=g^{e_1}\bmod p$发给B。B把$B$发给A时同理，选定随机数$e_2$，将$B$换成$E_2=g^{e_2}\bmod p$转发给A。
此时A计算出的密钥为$k_1=E_2^a\bmod p=g^{e_2a}\bmod p=A^{e_2}\bmod p$，而B计算出的密钥为$k_2=E_1^b\bmod p=g^{e_2a}\bmod p=B^{e_1}\bmod p$。此时中间人也可通过$A,B,e_1,e_2$计算出$k_1,k_2$，A向B发送加密消息时中间人拦截用$k_1$解密，并用$k_2$再次加密转发给B。
Hash长度扩展攻击
先了解基础知识：
以SHA-1举例，哈希函数拿到字符串后，将字节长度整除$64$取余数，如果正好等于$56$，则在字符串最后添上$8$字节长度描述符。如果不等于$56$，就先填充，填充的第一个字节为$0\mathrm x80$，其他字节均用$0\mathrm x00$，填充至余数为$56$后同样增加$8$个字节的长度描述符，这称为补位。
补位后，字符串每$64$字节为一组进行分组，每次进行一次逻辑函数序列后产生一组新的$H$值供下一次使用。当全部分组被处理完后，$H$中的值作为最终结果。
一般选择形如$H(\mathrm{key}\mid\mathrm{message})$的Hash函数，即在消息前固定一个密钥。但在MD型Hash算法（MD5、SHA-1等）的密钥长度已知、消息可控时易受到Hash长度扩展攻击。
具体攻击没看懂，挖坑待填。
例题：
1 |
|
将$secret看成密钥，第一个“admin”当作密钥后半部分的可控制部分，这样一来密钥总长度为$20$，数据为第二个“admin”。
数据随便篡改为“pcat”，使用工具HashPump：
1 | # hashpump |
得到结果：
1 | 3e67e8f0c05e1ad68020df30bbc505f5 |
第一行塞Cookies的getmein中，第二行把“\x”改成“%”然后POST。
HashPump不好使，建议用pip安装hashpumpy，用法：
1 | import hashpumpy |
Shamir门限方案
一种秘密共享方案，将秘密信息分成$n$份，只要有其中的$k$份即可将秘密解出。
设需要$k$份解出秘密消息$m$，选择$k-1$个随机数$a_1,\cdots,a_{k-1}$和大数$p\in\mathbb P,p>m$，列出模$p$多项式$\displaystyle f(x)=m+\sum_{i=1}^{k-1}a_ix^i\bmod p$。随机选择$n$个整数$x$，代入上式得到$n$个数$(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_n,f(x_n))$。恢复秘密信息时只需要$k$个$(x_i,f(x_i))$对，利用拉格朗日插值法或矩阵乘法可求得秘密信息$m$。
1 | from secretsharing import PlaintextToHexSecretSharer |