离散对数问题（ DLP ） 给定素数 p, α alpha α, β beta β 是模 p 非零的整数，令 β = α x m o d p beta = alpha^xmod p β=αxmodp ，则求 x 的问题称为离散对数问题。
生日攻击是一种密码攻击，它利用概率论中生日问题背后的数学原理。攻击取决于随机攻击中的高 碰撞 概率和固定置换次数（ 鸽巢原理 ）。通过生日攻击，可以在 2 n = 2 n / 2 sqrt{2^n} = 2 ^ {n / 2} 2n =2n/2中找到哈希函数的碰撞碰撞，其中 2 n 2 ^ {n} 2n 是经典的预测阻力安全。生日攻击是用来指代一类暴力攻击的名称。它得名于一个令人惊讶的结果：在一个23人的群体中，两个或更多人拥有相同生日的概率大于1/2；这种结果被称为生日悖论。
生日问题例如，考虑这样一个场景：一个班级有30名学生（n = 30）的教师要求每个人的生日（为简单起见，忽略闰年），以确定是否有任何两个学生具有相同的生日（对应于进一步描述的哈希冲突）。直观地说，这个机会可能看起来很小。与直觉相反，至少有一个学生的概率与任何一天的任何其他学生的生日相同，大约为70%（对于n = 30），公式 1 − 365 ! ( 365 − n ) ! ⋅ 36 5 n 1-frac{365!}{(365-n)!·365^n} 1−(365−n)!⋅365n365!
如果老师选择了一个特定的日期（比如9月16日），那么至少有一个学生出生在那个特定日期的几率是，大约是 1 − ( 364 / 365 ) 30 1 - (364/365)^{30} 1−(364/365)30 7.9%。
实现输入为生成元 α alpha α 的阶 p − 1 p - 1 p−1 和元 β beta β；输出为离散对数 x = log α β x = log_alpha beta x=logαβ，即要求解 β ≡ α x m o d p beta equiv alpha^x mod p β≡αxmodp。
设置两个长度为 p sqrt p p 的列表：
-
列表 1 包含 α k m o d p alpha^kmod p αkmodp，通过随机选取 p sqrt p p 个 k k k得到；
-
列表 2 包含 β α − l m o d p betaalpha^{-l}mod p βα−lmodp，通过随机选取 p sqrt p p 个 l l l得到；
则 在 两 个 列 表 中 很 有 可 能 出 现 重 复 的 项 ， 即 α k = β α − l alpha^k=betaalpha^{-l} αk=βα−l， 因 此 α k + l = β m o d p alpha^{k+l}=beta mod p αk+l=βmodp，那么 x = k + l m o d ( p − l ) x=k+l mod {(p-l)} x=k+lmod(p−l)就是要找的离散对数 。
import math
import random
def getRandomList(n):
"""集合方式实现生成n个随机数"""
numbers = []
while len(numbers) < n:
i = random.randint(0, 100)
if i not in numbers:
numbers.append(i)
return numbers
def 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并放入集合，同时在另一列表记录下k
item_k = pow(alpha, list_k[i], p)
list_k_value.append(item_k)
# 计算出 beta * alpha^{-l} mod p 并放入集合,同时在另一列表记录下l
item_l = beta * pow(alpha, -list_l[i], p) % p
list_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 False
else:
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_value
print("求出了x")
print(x % (p - 1))
return True
if __name__ == '__main__':
while True:
if brithAttack(alpha=19, beta=298, p=521):
break
带入数据检测发现结果正确
298 = 1 9 17 m o d 521 , 17 = log 19 298 m o d 521 298=19^{17} mod 521,17 = log_{19}298 mod 521 298=1917mod521,17=log19298mod521
