密码学中的生日攻击

什么是密码术？

密码学是一种将信息转换为特殊代码的方法，这些代码只能被发送者和接收者理解。使用密码学的原因是为了保护数据免受网络安全攻击。

密码学由两个词组成：'crypt'，指的是隐藏，'graphy' 意味着写作。因此，我们将信息以隐藏的形式编写，以使其免受漏洞和攻击。

可能存在各种类型的网络安全攻击，而暴力破解攻击是常见的网络安全攻击之一。

什么是暴力破解攻击？

这是一种攻击，黑客试图通过各种方法获取电子邮件、密码和加密密钥。

什么是生日攻击？

生日攻击也是一种暴力破解类型的密码学攻击。这种攻击用于利用标准概率论问题的数学原理，该问题称为生日悖论问题。 这种攻击的成功与这些攻击之间的碰撞次数直接成正比，这些攻击是随机的并且是置换的程度。

生日悖论问题

问题陈述是，假设我们有一个包含 N 个学生的班级和一位老师。 老师想知道有多少对学生的生日在同一天。 为了得到这个解决方案，他要求每个学生的出生日期，并找出对数。

假设他选择一个随机日期，例如 11 月 5 日，并想知道至少一名学生的生日在 11 月 5 日的概率。 因此，为此，他将使用概率论，并且他将获得没有学生在 11 月 5 日过生日的概率，并且将结果从 1 中减去以获得所需的结果。

假设学生人数等于 30，因此 N=30

至少一名学生的生日在 11 月 5 日的概率 = 1- (364/365)³⁰ = 0.079 或 7.9%。

至少一名学生的生日与另一名学生的生日在同一天的概率

= 1 - 365! / ((365-n!)*(365)ⁿ) 其中 n = 30，该值约为 0.7 或 70%

说明

在上述解决方案中，我们推导了 N 个学生的公式，即至少有两个学生的生日在同一天。

我们可以通过注意到没有人同一天过生日，然后从 1 中减去它来获得所需的结果来推导出它。

(365/365)*(365-1/365)*(365-2/365)*...(365-n+1)/365 = 365!/((365-n!)*(365)ⁿ)

所需结果 = 1-365!/((365-n!)*(365)ⁿ)

哈希函数

密码学中的哈希函数是一个接受可变大小的输入并返回结果作为固定长度字符串的函数。 输出字符串称为输入的哈希值。

它由 H 表示。

结果 h =H(X) 其中 x 是输入

在密码学中，哈希函数应遵循以下约束

• 函数的输入变量应该是可变大小的。
• 输出变量始终是固定长度的。
• 对于任何输入 X，H(X) 都更容易计算。
• H(X) 应该是无冲突的。
• H(X) 是单向函数。

单向哈希函数

对于任何输入 X，我们通过 H(X) 函数获得输出 Y 的值。

所以 Y= H(X)。

如果我们给出 Y，并且我们可以找到哈希函数 H，对于该函数 H(X) = Y，则该函数称为双向或可逆的。 因此，在密码学中，我们的哈希函数应该是不可逆的，这意味着不可能获得输出为 Y 的哈希函数 H。 它应该很难反转。

无冲突哈希函数

如果对于输入 X，哈希函数的输出为 H(X)，并且如果可能 X 不等于 Y 但 H(X) = H(Y)，则当前哈希函数称为弱无冲突哈希函数。

如果对于任何输入 X，不可能找到 Y 使得 X 不等于 Y 且 H(X) = H(Y)，则这称为强无冲突函数。

我们可以通过一个例子来理解它

示例

让哈希函数 H:M = {0,1}n 对于 |M|>>2ⁿ

• 因此，我们将使用以下步骤来查找冲突
• 我们将选择随机消息作为输入 m₁,m₂….
• 对于每个 m_i，计算输出 ti，其中 i= 1,2,3….
• 如果 t_i = t_j，我们将检查冲突，如果未找到，我们将重复此过程。

时间复杂度

上述算法的时间复杂度将为 O(2^n/2)。