生日攻击

离散对数问题（ DLP ） 给定素数 p, $\alpha$ , $\beta$ 是模 p 非零的整数，令 $\beta = \alpha^x\mod p$ ，则求 x 的问题称为离散对数问题。

生日攻击是一种密码攻击，它利用概率论中生日问题背后的数学原理。攻击取决于随机攻击中的高碰撞概率和固定置换次数（鸽巢原理）。通过生日攻击，可以在 $\sqrt{2^n} = 2 ^ {n / 2}$ 中找到哈希函数的碰撞碰撞，其中 $2 ^ {n}$ 是经典的预测阻力安全。生日攻击是用来指代一类暴力攻击的名称。它得名于一个令人惊讶的结果：在一个23人的群体中，两个或更多人拥有相同生日的概率大于1/2；这种结果被称为生日悖论。

生日问题

例如，考虑这样一个场景：一个班级有30名学生（n = 30）的教师要求每个人的生日（为简单起见，忽略闰年），以确定是否有任何两个学生具有相同的生日（对应于进一步描述的哈希冲突）。直观地说，这个机会可能看起来很小。与直觉相反，至少有一个学生的概率与任何一天的任何其他学生的生日相同，大约为70%（对于n = 30），公式 $1-\frac{365!}{(365-n)!·365^n}$

如果老师选择了一个特定的日期（比如9月16日），那么至少有一个学生出生在那个特定日期的几率是，大约是 $1 - (364/365)^{30}$ 7.9%。

实现

输入为生成元 $\alpha$ 的阶 $p - 1$ 和元 $\beta$ ；输出为离散对数 $\log_\alpha \beta$ ，即要求解 $\beta \equiv \alpha^x \mod p$ 。

设置两个长度为 $\sqrt p$ 的列表：

列表 1 包含 $\alpha^k\mod p$ ，通过随机选取 $\sqrt p$ 个 $k$ 得到；
列表 2 包含 $\beta\alpha^{-l}\mod p$ ，通过随机选取 $\sqrt p$ 个 $l$ 得到；

则在两个列表中很有可能出现重复的项，即 $\alpha^k=\beta\alpha^{-l}$ ，因此 $\alpha^{k+l}=\beta \mod p$ ，那么 $x=k+l \mod {(p-l)}$ 就是要找的离散对数。

import math
import randomdef getRandomList(n):"""集合方式实现生成n个随机数"""numbers = []while len(numbers) < n:i = random.randint(0, 100)if i not in numbers:numbers.append(i)return numbersdef brithAttack(alpha, beta, p):sqrt_p = int(math.sqrt(p))# 初始化两个列表list_k_value = []list_l_value = []# 生成 sqrt(p) 长度的随机数集合list_k = getRandomList(sqrt_p)list_l = getRandomList(sqrt_p)# 生成 sqrt(p) 长度的for i in range(sqrt_p):# 计算出 alpha^k mod p并放入集合，同时在另一列表记录下kitem_k = pow(alpha, list_k[i], p)list_k_value.append(item_k)# 计算出 beta * alpha^{-l} mod p 并放入集合,同时在另一列表记录下litem_l = beta * pow(alpha, -list_l[i], p) % plist_l_value.append(item_l)print(list_k_value)print(list_l_value)# 求出合集coincide = set(list_k_value) & set(list_l_value)print(coincide)if not coincide:print("集合为空")return Falseelse:for same in coincide:k_index = list_k_value.index(same)l_index = list_l_value.index(same)k_value = list_k[k_index]l_value = list_l[l_index]x = k_value + l_valueprint("求出了x")print(x % (p - 1))return Trueif __name__ == '__main__':while True:if brithAttack(alpha=19, beta=298, p=521):break