drangon2020密码学部分详解
Bit_Flip1
题目信息
附件是一个Python脚本，Gitee备份在此
分析
1.过一遍程序
生成16个随机的字节作为alice_seed，与接收到的flip_str异或取后32个字节(不够在前面加\x00)即为seed；
由于alice = DiffieHellman(flip_str(alice_seed))没有设置prime，因此alice初始化时会调用get_prime()来生成素数；
重点来看get_prime()这个函数；它不停的调用getbits(512)直到生成的数是一个素数；
来看getbits()的原理：先调用more_bytes()积累足够的“随机”字节，每次调用more_bytes()都会在generated后面加上seed的sha256哈希值(长256比特)；
seed的更新方式为seed=long_to_bytes(bytes_to_long(seed)+1,32)，在这里简单看作seed的值增1即可；
generated收集到足够的字节之后，取后num比特作为生成的随机数，未用到的“随机”字节仍然保存在generated中；
判断getbits(512)生成的是否为素数，若不是继续调用getbits(512)；
得到素数之后，会告知你iter——相对于一次生成就能得到素数，对getbits(512)增加的调用次数(易知每调用一次getbits(512)，seed自增2)；
返回prime后；调用getbits()生成64位的mysecret(DH算法的私钥)，然后计算$mynumber\equiv 5^{mysecret}\ \textrm{mod}\ prime$(DH算法的公钥)，设置shared为1337后，alice的初始化工作完成。
bob=DiffieHellman(urandom(16), alice.prime)按照同样的方式完成初始化工作，只不过此时bob的prime直接使用alice的prime；
alice与bob经密钥协商得到双方都知道的协商密钥(与DH算法略有不同，多了一个与1337的异或操作)，该密钥作为AES的加密密钥对FLAG进行加密。
2.寻找突破
我相信程序输出的数据都是有它的作用的，print(“bob number”, bob.my_number)给出bob的公钥是为了让我们得到prime与secret之后可以同样计算出协商密钥；输出iv与enc_flag作用也很明显；那么程序输出iter就值得注意了，一定是对我们解题有用！
3.利用iter
那么我们如何借助iter来获取足够多的信息以致于解出FLAG；iter间接体现了get_prime()调用getbits()的次数！
由于程序会接收我发送的flip_str，因此我们可以改变seed的值，即使我们不知道seed的值，但是这仍然有用！
既然我们不知道seed的值(是因为我们不知道alice_seed的值)，那我们记alice_seed的值为$s_{127}\cdots s_{1}s_{0}$，我们的考虑这样的情况：
我发送如下两个flip_str：
flip_str_1：空字节
flip_str_2：|$1$|$0$|
那么经bit_flip()就能生成如下2种seed：
seed_1：|$s_{127}$|$\cdots$|$s_{1}$|$s_{0}$|
seed_2：|$s_{127}$|$\cdots$|$1\oplus s_{1}$|$s_{0}$|
由这2个seed生成素数的iter分别记为iter_1与iter_2；
分类讨论：
$s_{1}=0$，seed_1+2=seed_2，如果iter_1非0，必有iter_1-iter_2=1；
$s_{1}=1$，seed_2+2=seed_1，如果iter_2非0，必有iter_2-iter_1=1；
那么当$iter_1\cdot iter_2\neq 0$时，由于$s_{j}$非0即1，因此此时iter_1-iter_2=1与iter_2-iter_1=1至少(没写错，确实是至少)有一个成立！此时$s_{j}=0\Rightarrow$iter_1-iter_2=1，因此(原命题的真假性与逆否命题的真假性一致)$iter_1-iter_2\neq 1\Rightarrow s_{j}\neq 0\Rightarrow s_{j}=1$，即iter_1-iter_2=-1$\Rightarrow s_{j}=1$。
那如果$iter_1\cdot iter_2=0$怎么办？这时根据iter_1-iter_2的值是无法判断$s_{1}$的值的！由于我们只需要保持|seed_1-seed_2|=2即可，因此我们可以改变flip_str前面的字节，这样得到的seed_x(x=1,2)的哈希值与原来显著不同，从而$iter_1\cdot iter_2$的值有可能发生改变，不停的改变flip_str前面的字节直到$iter_1\cdot iter_2\neq 0$，就可以由上述分析过程解出$s_{1}$！
一般地，类似于数学归纳法；假设我已经分析出$s_{j-1}\cdots s_{1}$(这里没写错，$s_{0}$我是没有分析出来的)，借助已经得到的信息分析出$s_{j}$，思路如下：
- 发送如下4种flip_str：
flip_str_1：| $0$ | $1\oplus s_{j-1}$ | $\cdots$ | $1\oplus s_{1}$ | $0$ |
flip_str_2：| $1$ | $s_{j-1}$ | $\cdots$ | $s_{1}$ | $0$ |
flip_str_3：| $1$ | $1\oplus s_{j-1}$ | $\cdots$ | $1\oplus s_{1}$ | $0$ |
flip_str_4：| $0$ | $s_{j-1}$ | $\cdots$ | $s_{1}$ | $0$ |
那么经bit_flip()就能生成如下4种seed：
seed_1：| $s_{127}$ | $\cdots$ | $s_{j}$ | $1$ | $\cdots$ | $1$ | $s_{0}$ |
seed_2：| $s_{127}$ | $\cdots$ | $1\oplus s_{j}$ | $0$ | $\cdots$ | $0$ | $s_{0}$ |
seed_3：| $s_{127}$ | $\cdots$ | $1\oplus s_{j}$ | $1$ | $\cdots$ | $1$ | $s_{0}$ |
seed_4：| $s_{127}$ | $\cdots$ | $s_{j}$ | $0$ | $\cdots$ | $0$ | $s_{0}$ |
由这4个seed生成素数的iter分别记为iter_1、iter_2、iter_3与iter_4；
分类讨论：
$s_{j}=0$，seed_1+2=seed_2，如果iter_1非0，必有iter_1-iter_2=1；
$s_{j}=1$，seed_3+2=seed_4，如果iter_3非0，必有iter_3-iter_4=1；
那么当$iter_1\cdot iter_3\neq 0$，由于此时$s_{j}$非0即1，因此iter_1-iter_2=1与iter_3-iter_4=1必有一个成立！同样地，$iter_1-iter_2\neq 1\Rightarrow s_{j}\neq 0\Rightarrow s_{j}=1$；因此，当$iter_1\cdot iter_3\cdot ((iter_1-iter_2)\cdot (iter_3-iter_4)-1)\neq 0$时，$iter_3-iter_4=1\Rightarrow iter_1-iter_2\neq 1\Rightarrow s_{j}\neq 0\Rightarrow s_{j}=1$。
如果$iter_1\cdot iter_3\cdot ((iter_1-iter_2)\cdot (iter_3-iter_4)-1)=0$，同样地，改变flip_str前面的字节直到进入上述情形!
综上，我给出了对$s_{1}$的分析思路，也给出了由$s_{j-1}\cdots s_{1}$推出$s_{j}$的分析思路；最终我可以还原出alice_seed除$s_{0}$之外的所有比特位，而$s_{0}$非0即1，因此最后解出的结果与alice_seed的值相差不超过1！
接下来按照同样的方式生成AES密钥，对密文进行解密即可！
解题
这道题我并没有在比赛的时候做出来，因此我对task.py的交互方式作了一些改变；flag是自己设置的；上述链接中的solve.py为解题脚本，程序运行结果如下：
1 | λ python3 solve.py |
Bit_Flip2
题目信息
附件仍然是一个Python脚本，相对于Bit_Flip1只有1行代码不同，它将print(“bob number”, bob.my_number)这一行注释起来；Gitee备份在此
分析
同Bit_Flip1的方法可解出alice_seed，可此时我并不知道bob.my_number；虽然当时想过控制alice.my_secret为0，但是觉得太不切实际，而事实上writeup就是这么做的！这需要你对比特币有一定的了解，知道使用块散列算法(可参见此处)可以生成以一定长度的0字节结尾的哈希值。按同样的方法推测出alice_seed后发送特定的flip_str使得alice以特定的seed初始化，使得alice.my_secret为0，那么bob.my_number就对我们解密出flag无关紧要了。
解题
上述链接中的solve.py为解题脚本，同样因为题目没有在比赛的时候做出了，flag是我自己设置的；程序运行结果如下：
1 | $ python solve.py |