密码学系列之:生日攻击
简介
生日攻击其实是一个概率论的问题,也就是说一个看起来很难发生的事情,事实上它发生的概率却很大。这种主观上和事实上的概率差距,让随机攻击成功的几率变的更高,这样的攻击就叫做生日攻击。
生日问题的由来
生日问题也叫做生日悖论,它是这样这样描述的。
假如随机选择n个人,那么这个n个人中有两个人的生日相同的概率是多少。如果要想概率是100%,那么只需要选择367个人就够了。因为只有366个生日日期(包括2月29日)。
如果想要概率达到99.9% ,那么只需要70个人就够了。50%的概率只需要23个人。
对于现在的幼儿园小朋友来说,一个班上差不多有30人,那么将会有大于50%的几率,班上有两个人的生日是一样的。
听起来是不是很神奇?跟我们第一映像中的基数是不是要少很多。
我们看一张概率图:
在实际应用中,可以应用生日问题中的概率模型,从而减少碰撞攻击的复杂度,或者来评估一个hash函数中可能出现碰撞攻击的几率。
怎么计算呢?
假如P(A) 是生日相同的概率,那么P(A) = 1 – P(A’) ,其中P(A’)是生日不同的概率。
一个人生日不同的概率是365/365,两个人生日不同的概率就是365/365 * 364/365 ,依次类推。
我们可以得到23个人生日不同的概率大概就是 0.492703。
也就是说23个人中有两个人生日相同的概率可以大于50%。
再看一张表来个更加直观的描述:
生日问题的衍生
生日问题的取值范围是在一年的365天之内,也就是说生日只可能有365种可能性。
我们将这个问题扩展一下到一般的情况,假设有一个函数f,它的输出范围是H,那么我们的攻击就是找到两个不同的x,y,让f(x)=f(y)。
这时候,我们可以称x和y发生了碰撞。
根据概率论的公式,我们想要达到50%的几率,那么需要尝试的次数是:
如果以bits位来表示可能计算出的结果的话,我们可以参考下面的概率表:
生日攻击的应用
生日攻击一般应用在数字签名中。一般来说为了对机密消息进行签名,因为加密的限制,如果消息很大的情况下,不可能对所有的消息进行签名,通常会对消息计算hash值,然后对这个hash值进行签名。
比如有人想做一个欺诈性的合同,那么会在原合同的基础上进行修改,不断的进行尝试,从而找到一个修改后的合同,让合同和之前合同的hash是一样的,从而导致两者的签名也是一样的。
怎么抵御这种攻击呢?根据我们生日攻击的公式,当然是将签名方案使用的哈希函数的输出长度选择得足够大,以使生日攻击在计算上变得不可行。
本文已收录于 http://www.flydean.com/birthday-attack/
最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!
欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
数据管理:业务数据清洗,落地实现方案
一、业务背景 在系统业务开发的过程中,都会面临这样一个问题:面对业务的快速扩展,很多版本在当时没有时间去全局考虑,导致很多业务数据存储和管理并不规范,例如常见的问题: 地址采取输入的方式,而非三级联动; 没有统一管理数据字典获取接口; 数据存储的位置和结构设计不合理; 不同服务的数据库之间存在同步通道; 而分析业务通常都是要面对全局数据,如果出现大量的上述情况,就会导致数据在使用的时候难度非常大,随之也会带来很多问题:数据分散不规范,导致响应性能差,稳定性低,同时提高管理成本。 当随着业务发展,数据的沉淀越来越多,使用的难度就会陡增,会导致在数据分析之前,需要大量时间去清洗数据。 二、数据清洗概述 1、基本方案 核心思想: 读-洗-写入业务库持续服务; 读-洗-写入档案数据资产库; 业务数据清洗本质上理解起来并不难,即读取待清洗的数据源,经过清洗服务规范化处理后,再把数据放到指定的数据源,但是实际操作起来绝对叫人眼花撩到。 2、容器迁移 数据存储的方式本身就是多种选择,清洗数据要面对的第一个问题就是:数据容器的迁移; 读数据源:文件、缓存、数据库等; 临时容器:清洗过程存储节点数据; ...
- 下一篇
小白必看!JS中循环语句大集合
摘要:JavaScript中,一共给开发者提供了一下几种循环语句,分别是while循环,do…while循环,for循环,for Each,for…in循环和for…of循环。 本文分享自华为云社区《JS中循环语句大集合丨【WEB前端大作战】》,原文作者:hwJw19 。 JavaScript中,一共给开发者提供了一下几种循环语句,分别是while循环,do…while循环,for循环,for Each,for…in循环和for…of循环。 下面我们就通过本文来仔细分辨一下,各个循环的使用差异。 while循环 语法: while (expr){ statement } expr为条件表达式,当expr为真时,执行statement语句,执行结束后,再次进入下一轮循环,直到条件表达式为假时,跳出循环。 代码示例: var n = 1; //声明并初始化循环变量 while(n <= 100){ //循环条件 n++; //递增循环变量 if (n % 2 == 0) document.write(n + ""); //执行循环操作 } d...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7设置SWAP分区,小内存服务器的救世主
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- 设置Eclipse缩进为4个空格,增强代码规范
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2全家桶,快速入门学习开发网站教程
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题