生日攻击

离散对数问题（ DLP ） 给定素数 p, $\alpha$, $\beta$ 是模 p 非零的整数，令$\beta ={\alpha }^x\mathrm{m}\mathrm{o}\mathrm{d}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$；输出为离散对数 $x={\log }_{\alpha }\beta$，即要求解$\beta \equiv {\alpha }^x\mathrm{m}\mathrm{o}\mathrm{d}p$。

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

• 列表 1 包含${\alpha }^k\mathrm{m}\mathrm{o}\mathrm{d}p$，通过随机选取 $\sqrt{p}$个$k$得到；

• 列表 2 包含$\beta {\alpha }^{?l}\mathrm{m}\mathrm{o}\mathrm{d}p$，通过随机选取 $\sqrt{p}$个$l$得到；

则 在 两 个 列 表 中 很 有 可 能 出 现 重 复 的 项 ， 即 ${\alpha }^k=\beta {\alpha }^{?l}$， 因 此${\alpha }^{k+l}=\beta \mathrm{m}\mathrm{o}\mathrm{d}p$，那么$x=k+l\mathrm{m}\mathrm{o}\mathrm{d}(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=19^{17}\mathrm{m}\mathrm{o}\mathrm{d}521,17={\log }_{19}298\mathrm{m}\mathrm{o}\mathrm{d}521$