密码学中的生日攻击

什么是密码学？

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

密码学是由两个词组成的。crypt “指的是隐藏，”graphy “指的是书写。因此，我们将信息以隐藏的形式写出来，使其免受漏洞和攻击。

网络安全攻击可能有多种类型，而暴力攻击是常见的网络安全攻击之一。

什么是 “强力攻击”（Bruteforce Attack）？

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

什么是生日攻击？

生日附加也是一种蛮力攻击类型的密码学攻击。这种攻击是用来利用一个标准概率论问题的数学知识，这个问题被称为生日悖论问题。这种攻击的成功率与这些攻击之间的碰撞次数成正比，这些攻击是随机的，而且是排列组合的程度。

生日悖论问题

问题陈述说，假设我们有一个由N个学生组成的班级，班上有一位老师。老师想知道有多少对学生的生日是在同一日期。为了得到这个答案，他要求每个学生的出生日期，并找出成对的人数。

假设他选择了一个随机的日期，如11月5日，想知道至少有一个学生在11月5日过生日的概率。因此，他将使用概率论，他将得到没有学生在11月5日过生日的概率，然后用1减去这个结果，得到所需的结果。

我们假设学生人数等于30，所以N=30

至少有一个学生在11月5日过生日的概率=1- (364/365) 30 = 0.079 或 7.9%。

至少有一个学生的生日是在另一个学生的生日当天的概率

= 1 – 365!/ ( (365-n!)*(365) n ) 其中n = 30，其值将是0.7或70%左右。

解释

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

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

(365/365)(365-1/365)(365-2/365)…(365-n+1)/365 = 365!/((365-n!)(365) n )

而期望的结果=1-365！/（（365-n！）*（365）n ）。

哈希函数

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

它由H代表。

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

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

• 函数的输入变量应该是可变大小的。
• 输出变量将始终是固定长度。
• 对于任何输入的X，H(X)是比较容易计算的。
• H(X)应该是无碰撞的。
• H(X)是一个单向的函数。

单向哈希函数

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

所以Y= H(X)。

如果我们给了Y，而我们可以找出H(X)=Y的哈希函数H，那么这个函数被称为双向或可逆的。因此，在密码学中，我们的哈希函数应该是不可反转的，这意味着不可能得到输出为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 n

• 因此，我们将使用以下步骤来寻找碰撞。
• 我们将选择随机信息作为输入m 1 ,m 2 ….
• 对于每个m i，计算输出ti，其中i= 1,2,3….
• 如果t i = t j，我们将检查是否有碰撞，如果没有发现，那么我们将重复这个过程。

时间复杂度：

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