生日悖论在密码学中的应用（可编辑）

生日悖论在密码学中的应用（可编辑） 生日悖论在密码学中的应用 ?淼‰ 硕士学位论文 生日悖论在密码学中的应用 论文作者:喻秋叶 指导教师:李波副教授 学科专业:概率论与数理统计 研究方向:应用概率统计 华中师范大学数学与统计学学院 年月 彳砀缈括..铲讯 . ?: : 厶刃 .硕士学位论文 ’ ? 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师指导下,独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外,本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名: 日期:扣,乃年,月冶日 匀? 勺” 学位论文版权使用 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定,即:研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版,允许学位论文被查阅和借阅; 学校可以公布学位论文的全部或部分内容,可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。保密的学位论文在解密后遵守此规定 保密论文注释:本学位论文属于保密,在??年解密后适用本授权书。 非保密论文注释:本学位论文不属于保密范围,适用本授权书。 作者签名:钙社寸 导师签名:蒈段 日期:知,;年,月夕日 日期:护哆年月心日 本人已经认真阅读“高校学位论文全文数据库发布章程”,同意将本人 的学位论文提交“高校学位论文全文数据库”中全文发布,并可按“章程” 中的规定享受相关权益。回童途窒量变卮进卮旦圭生;旦二生;旦三生筮查 储虢名视叶 孙签名:连址 日期:。尸吗耵月捻日 日期:小哆盼月汐日硕士学位论文 、 ? 摘要 生日问题在数学史上为一个经典的案列。随着数学基础学科的不断完善,科 学 知识的不断更新,概率理论在很多相关领域都做出了相关的理论基垫。在密 码学中, 生日问题有着广泛的应用。首先它为密码学的生日攻击?方法生日攻击是由 提出的一种攻击方法提供了理论依据;其次它已成功的用于攻击‘函数, 以及对 、锄‘以及 的低轮攻击。本文基于生日攻击的基本 思想,对于高级数据加密算法进行,得到的主要结论有:、对于概 率中的生日悖论给出了证明和推广,在文献【】等研究基础上,将一般性的分 组密 码攻击模型??”个候选密钥中选的穷举问题数据复杂度为”,转换为”个 候选密钥中寻找碰撞的生日问题数据复杂度为?”;、给出了对于曲函数 碰撞攻击和分组密码中间相遇攻击的一般性方法;、在文献【、】所提 方法的基础上,对于给出了新的攻击路径,总复杂度为俐,该攻击方法效 率低于穷举攻击,与文献】给出的复杂度相当,但使用了新的差分路径;、给 出 的对于的攻击的新的差分路径,对于高级数据加密标准这一国 际标准算法的安全性分析具有一定的参考价值。 关键词:密码学;分组密码;生日问题;;差分路径嬲 弱 . ? 】 呼 ? ’ 觚, 锄 巧弱.叫伊印. 也【 】 咖簪咖:‰ ?; 矗【】,仳.’【】,【】 【】 ,勰 : ,锄四, 趾 :, 仃 妇 :够也’ ?一 砌 “白【 】, 砌 “锄 ;舭 【哆 ”, ” 量岫 锣 ?一 ?” 灿 砒 缸 ;,嬲 ??? ;, 眦嗣 撒 , 血 ,】, 柚,,也?觚腼 孤? 毋 ‰. ? 锄嬲 撒 】, 航 疏 恤 ‰, ;,龇锄 此锄砌 叫 砌垣 耐够 鹤 . . 吼叫 :; ;硼咖;;虢以 吐 硕士学位论文 ’ ? 目 录 摘要??. 觚。 第一章绪论?. .概率理论??. .概率论在密码学中的应用?. .本文主要工作. 第二章密码学研究背景。 .密码学概述?. .密码学基础知识??. ..密码学简介..分组密码 ..评价一个密码体制的主要参考指标? ..复杂度? ..攻击方法 . 分组密码。 .. 概述 .. 的研究现状??.. 第三章 生日问题及已有应用??.. . 数学知识:生日悖论及其解法. 生日悖论的推广 ..生日问题引发的思考。 . 生日悖论在密码中的已有应用 ..在函数中的应用 ..中间相遇攻击. ..对?的低轮攻击??. 第四章对?的轮攻击? . 攻击方法?. .. 简介? .. 的相关知识? .对一的轮攻击?硕士学位论文 ’ ? ..密钥空间承【,刀的造构..的维轮构造以及前后配对时的前后计算图?一 第五章新路径的一 ?攻击. .密钥部分. 维轮?一 .. 维的构造? ..自订轮的配对计算?. ..密钥恢复的复杂度?. .新路径的分析 ..新路径的构造. ..新路径的数据结果?. 第六章与展望 参考文献??. 附录?. 【谢?.第一章绪论 .概率理论 概率论够巧?是数学的一个分支,研究的是随机现象的数量规 律。近几十年来,概率论结合各个工程技术和社会科学,形成了大量边缘科学,如 信息论、排队论、可靠性理论、数理金融学等。尤其伴随着统计学在世纪初期的 引入与迅速兴起,以概率理论为基础,又为概率论提供了又有力的工具。二者联合 起来,在强大的计算能力的支持之下,已成为最有力的定量分析手段,在近代通讯、 物理、无线电与自动控制、网络通信、生物工程、农业和医药实验、金融保险业以 及密码学等方面都得到了重要应用。 由于各学科的知识交叉性,概率论知识涉及物理、化学、生物统计、机械工 程、 数量经济学等学科。尤其是连续性随机变量的随机过程和玛氏链在经济学中的广泛 应用。 正如钟开莱年所说:“在过去半个世纪中,概率论从一个较小的、孤立的课 题发展为一个与数学许多其它分支相互影响、内容宽广而深入的学科。眨 .概率论在密码学中的应用 概率理论的不断完善,为解决生活问题提供了充足的理论依据。除了之前提到 的赌博问题,还有六合彩,轮盘游戏,竞技比赛以及生日悖论详见第二章等等。 世纪为信息时代,信息已成为社会发展的重要战略。随着信息技术的日新月 异,信息安全也成为时代需要的利刃。密码学在信息安全系统中为保障数据安全 的关键技术。密码学是研究数学技术及相关的保密性、数据完整性、实体认证、数 据资源认证等信息安全各领域的综合性学科。它运用了数论、概率论、统计学、组 合学等数学知识,并涉及其他的信息论等计算机学科;并且在分组密码的检测评估时,就用到很多统计检测手段。由此看来,概率论在密码学上的应用是不可忽略的。 密码学是一门有着厚实的数学基础的学科。纵观密码的研究发展历程,在 年,裴定一和祝跃飞就发表过《算法数论》的文章;同年,孙琦等在第七届中国密 码学学术会议论文集上发表《计算群元的整数倍的一种算法及其在公钥体制中的应 用》;至年,覃中平和张焕国谈及《信息安全数学基础》;这些相关论文,可 以看出,密码学中的数学理论站着举足轻重的作用。概率中的生日问题在密码学中 有着理论贡献,给密码的编译及破译提供了一个知识平台。本文主要对于概率论中 的生日悖论给出了证明和推广,在文献】等研究之上,将一般性的分组密码攻击 模型即”个候选密钥中选的穷举问题,其复杂度为”转换为”个候选密钥 中寻找碰撞的生日问题,其复杂度为?”。在文章的第五章将给出具体的分析及计 算过程。 .本文主要工作 本文旨在介绍生日问题在密码学中的应用问题,主要工作是利用攻击 方法,在对.的轮迭代中,在第.轮构造,得出与文献 复杂度相当的结果,但给出新的差分路径。主要从以下几个方面入手; 本文的第一章是绪论部分,意在指明,数学在密码学中有着广泛的应用,尤其 是概率论和统计学,在分组密码的检测评估时,就用到很多统计检测手段。 在第二章部分,讲述了相关的密码学基础知识,有密码学的发展历程、密码学 中普通的加解密过程和典型的分组密码;的加解密过程的介绍,为第五章 的新轮构造提供了理论基础。 第三章给出了概率理论中的生日悖论的证明及推广,考虑在不同的条件下小样 本的计算;也指出生日问题在密码学中已有的应用,主要体现在嬲函数的碰撞 攻击和分组密码中间相遇攻击一般性方法的应用。 第四章为文献【】中提出的一种新的密码攻击算法,主要介绍了什么是 、如何构造;并介绍了文献【】中,利用构造轮,成功将 其应用到一的轮攻击,得出复杂度为’。 第五章为本文的创新部分,找到了一条异于文献【】的差分路径,构造轮 鹏时,在第轮加密,子密钥,,,构造出?;差分,同样在构造另一个』差分, 在?处取得差分,该攻击方法效率低于穷举复杂度,得出最后的计算复杂度为 ,数据复杂度为。第二章密码学研究背景 .密码学概述 密码学唰是一门古老的科学。人类对其的研究和应用自人类社会出现 战争便开始了。但其正式成为一门科学,还经历了漫长的过程。在年,信息论创始 人商农..砌发表了著名论文??《保密系统的通信理论》“,这标志着密码 学作为一门科学的形成。 其主要发展历程如下表所示: 表.密码学发展历程 时期 相关人物 发展阶段 标注 年之 产生了密码学,但处于萌芽阶 ?,上. 刖 段 信息论创始人 密码学成为一门 年 发表《保密系统的通信理论》 ..趾 独立的科学 在密码学历史上 .和 年 提出公开密钥 开辟了一条新的 :伍 追跆 综合运用置换、代 美国联邦政府颁布数据加密 替、代数等多种密 年 公司成员 标准 聊 码技术,为密码史 觚,简称 上的一个创举 美国联邦政府颁布密钥托管 加密标准 年 美国联邦政府颁布数字签名 标准 美国联邦政府颁布高级加密 引起世界各国密 咖 标准觚 码学者的高度重 哪 和. 年 加,简称,为 视,为一个重要的 苟 ?扑算法 里程碑 密码学是数学、计算机、信息技术和通信等多学科的交叉学科, 是一门正在快速发展的综合性新学科。现在密码学使用大量的数学,包括组 合数学、 硕士学位论文 ’ ? 概率论与数理统计、抽象代数、数论以及离散对数等。其理论基础还依托计 算机、 信息论、编码、通信技术和物理学等。其中概率统计主要用于测试和分析密码算法, 为编码人员和密码分析人员提供参考数据。 密码学主要分为两个部分:密码编制学鳓和密码分析学 删。密码编制学主要研究密码的设计和编制,保证信息的安全和可认 证信;密码分析学主要研究密码的破译和攻击,对加密的信息进行破解和伪造信息。 两者相互制约又相互促进,共同促进密码学的发展。 .密码学基础知识 ..密码学简介 密码技术是将原始数据进行伪装,使未授权者即使截获信息,也不能理解信息 的真正含义。所谓的伪装,可理解为对数据进行的一组数学变换。整个密码编码过 程,又包括以下五个部分:明文,密文,密钥,加密算法,解密算法。 原始的数据或者信息称为明文,用或尸表示; 原始数据被伪装后的消息称为密文,用表示; 参与伪装的参数称为密钥,用表示;密钥的所有可能的取值称为 密钥空间 ; 将明文伪装成密文的变换过程称为加密聊,此时的变换称为加 密算法,用表示; 将密文通过一个数学变换重新转化成明文的过程称为解密, 此时的数学变换称为解密算法,用表示; 无论在加密过程还是解密过程中,都需要密钥的参与,两个密钥在单钥密码 体 制中相同,但在公钥密码体制中却不同,因此分别称两个密钥称为加密密钥 疋和解 密密钥髟。硕士学位论丈 ’ ? 加密和解密过程图如下所示: 加密密钥疋 解密密钥畅 锢?盏媚 园一 图.加、解密过程 由于加密和解密算法均相当于数学变换,整个过程用数学形式表示如下: . 吆;杨 这五个部分尸,,,,相当于一个五元组,可以描述所有的密码体制。但密 码体制因为明文转化成密文的信息长度的变化,又形式各异。设明文信息长 度为行, 密钥长度为,经过加密后,明文转换成长度为所的密文。 若甩聊,则为输入大于输出的密码算法; 若刀,则是有数据扩充,为输出大于输入的密码算法; 若刀,输入输出的长度相同。密钥长度不影响输入输出长度。 再联系.式,以加密过程为例,明文尸的取值相当于定义域,密文的值 域相当于值域,而加密算法瓦相当于对应法则。同理有解密过程的数学表示。 类 似于数学学科里的满射、单射、双射。 ..分组密码 根据处理明文的形式不同,单钥密码分为两种体制:分组密码和流密码。顾名 思义,分组密码的加密密钥和解密密钥是同一个密钥,即髟,后文讨论的分 组密码密钥均用表示。 分组密码 是将明文、密钥和密文信息按固定长分块处理,使得 在加解密算法过程中更好的表示以及计算。具体过程如下:对明文依次进行 编号, 将长度为疗的密码划分为数字序列的形式;如信息,‰忱屯卜??矗一。”表 示字符串间的连接符号;可用而,而,而,?,矗一,表示;相应的密钥可分块为 经过加 ,,疋,?,一。密钥长度可以与明密文长度不同,故分为块, 密转换得到输出的密文消息为%,。,奶,?,%一。。在密码学中,明密文均设为 二元数字和序列,即,只?凹,相应明文空问为凹”,密文空问为 凹”,密钥空间为凹。。则一个分组密码可定义为如下形式: 定义.分组密码的函数映射形式: . :舒”×凹‘专舒” ..评价一个密码体制的主要参考指标 一个密码体制,主要包括,,,,五个部分。要评价设计它的优劣性,主 要从信息安全、容易实现、使用方便和设计精巧等几个方面考虑。 信息安全方面:数据的传递间导致的主要信息泄露与密码的安全性是息息相 关的。 容易实现:密钥的长短会给攻击者破译密码提供信息,密钥太短,保密强度 太弱;密钥过长又不便于传递、保管和记忆。同时密钥要经常更替,保障信息 传递 的安全性。 使用方便:当输入长度小于输出长度时,密文信息长度的过度增加将导致通 信效率的降低;同时算法的复杂度要有限度,否则开销过大。 设计精巧:加解密算法的合理设计,使整个密码体制更具探索性。 ..复杂度 算法的复杂度是衡量一个密码体制的参考指标之一,也是衡量一个攻击方法 的硕士学位论文 ’ ◎ 参考依据。算法的复杂度 畸简称由三部分组成:数据复杂 度 时简称、时间复杂度弛 够简称、记 忆复杂度 够简称。 ?数据复杂度:实施攻击时所输入的明文信息量; ?时间复杂度:攻击算法所需的计算步骤,通过加密解密的次数来计算; ?记忆复杂度:攻击算法所需的存储量。 在进行攻击时,所输入的明文信息量可以自由选取,通过算法的计算,会得到 一些中间变量,需要进行存储,此时大的输入量会影响到记忆复杂度的计算。在算 法的复杂度中,加解密的计算次数,会直接关联整个算法的结果和运行速度,故时 间复杂度在整个算法复杂度中占主体作用。在刻画一个攻击方法的好坏时,主要考 察它的时间复杂度和记忆复杂度。 ..攻击方法 密码分析学是研究密码破译的科学。分析者可以利用各种方法来攻击密码,以 破译整个密码系统。常用的攻击密码的方法如下:穷举攻击、统计分析攻击、数学 分析攻击。但依据分析者所拥有的数据资源不同,又有如下攻击方法的分类: :攻击者在未知明文和密钥的情况下, 唯密文攻击. 截获了密文,然后利用密文穷举攻击;此种情况对分析者来说是最不利的。 已知明文攻击鼬?础:攻击者获得了某些明文的同时, 也获得了相应的加密了的密文;通过这些已知的明密文对来推出密钥,以便 给定任 何的密文,都可以对其进行解密。 :指攻击者能在当前未知的密钥情 选择明文攻击 况下,随意选择明文并获得相应的密文。在尽可能恢复出密钥的情况下选择 明文进 行攻击。这是十分有利于攻击者的分析的。 选择密文攻击喇 :类似选择明文攻击,是指攻击 者在当前未知的密钥情况下,随意选择密文并获得相应的明文。在尽可能恢 复出密 钥的情况下选择密文进行攻击。这种攻击多用于公钥密码。硕士学位论文 ’ ? . 分组密码 是一个典型的分组密码,以下将详细介绍它的历史背景、加密算法以及已 有的相关分析研究。为第四章做好知识铺垫。 . 概述 是年正式颁布的高级数据加密标准算法。究其发展历程就不得不提 到。是美国政府于年颁布的数据加密标准算法,其颁布之后,相关 密码分析者证明了它的安全性,于是在之后的几十年的时间里,几乎全球的 商用计 算机数据加密都采用了算法.这是史无前例的,以此我们可以看出在密码 学的历史上创造了一个奇迹。直到年,美国密码学着 就宣布通过 穷举方法破译了‘。由于的不安全性,于是美国政府开始向全球公开征 集新的数据加密标准算法,以取代。经过三轮的筛选,由比利时密码学家 ?砒和 提出的算法被最终选定为。在经过严 谨的安全认证与公开测评后,从年月日起作为美国新的数据加密标准 .,从而取代了,同时将会在金融、商业和界等领域获得广泛应 用。 的建立是有着坚实的数学基础的。因为算法是按字节运算的,而 每一个字节可以表示为域上的一个多项式,有限域中每一元素为二元 域上的小于次的多项式口。 是继分组密码之后的一个重要的分组密码算法。它的每个输入输出 均为比特。每经过一次变换所产生的值叫作一个中间状态证删她此, ? 碣 弛如 % 强 醛 曲 简称,中间状态可看作一个×的矩阵。例如 ,参与 碣 碣 岛 运算时的输出顺序是:‰,哦。,括。:,蚝,碗。,碗,,玛:,碗,,西:。,西:。, 捃::, 且 捃, 括,。, 呜, 括,, 西。中每个元素为一个字节, 嘞??,?,??舒。当然首次输入的明文也称为一个嚣。 硕士学位论文 ’ ? 每次的输入相当明文为比特,密钥的长度可取 //比特。根据密钥的分组长度不同,可以分别表示为.、 .和.,也可以类似状态分别表示成×、×、×的矩阵。且有 着类似的函数迭代结构见图.,只是迭代轮数不同见表. 表. 一 一 . 类型数据块长度 × × × 密钥 迭代轮数 困 ?占 初始密钥 密 钥 扩 展 每 轮 密 钥 取 值 不 同 图.函数迭代结构 硕士学位论文 ’ ? 现对图.的算法结构作如下解释: 符号说明: :为在首轮中,随意选定的.的明文数据; %:为从给定的初始密钥中取出的比特位; :。 :二进制的异或运算,例如: 上图的虚框:进行函数迭代,在迭代的最后一轮中,进行完行位移后直接与最 后一个子密钥异或出密文,不进行列变换。 输入的明文信息,攻击者可以任意选定。可作如下处理: 肌? 肌力% , 朋妒??,?/??泸进入迭代结构后,输出顺序与类似。 盒变换 盒变换是一个按字节进行运算的非线性部件,即为非线性的函数;通常也称 字节代替变换。它将的每个字节非线性地变换成另一个字节除外。须做两 个步骤: ?:在有限域卯中,每一个状态的元素均找到它的乘法逆元,规定。 ?:将?中的结果做仿射变换。详见参考文献【】。 在本文中,我们可简单理解为当输入为确,得到输出为;当输入为%?,, 则输出不为,而是 ?。,则称此时的输入是有差分的,用来表示,没有差分 的字节用表示;简而言之,若输入为非零,则输出也为非零;若输入相同,则输 出也相同。 行位移沁 行位移是一个状态值内部每行循环左移若干字节,即第??行循环左移硕士 学位论文 ’ ? 位。 ‰ 瑶 岛 ?、嘞碣 碣 黾 % 例如: ’ :? 墨丛逝塑墨? 坫 聒 硌 坫 硌 为 疆 岛行位移只改变了字节的位置,没有取到任何的混淆作用。 列变换 列变换也称列混淆。顾名思义,对进行行位移之后的状态逐列进行变换。变换 后的元素与原像有着一定的函数关系本文可不考虑函数关系。 心 碣。 曲。 括’ 括’ 话’ 括’ 坫 碣 硌 为 西’ 如’ 西’ 括’ 西’ %邑 括’ 括’ 西’ 碣括’ “ 括’ 括’ 此时可以理解为每一个字中只要有一个字节有差分输入,则在经过列混淆后, 此列的每个字节均有差分,严格意义上说差分的大小不等,本文只考虑是否有差分 的情况,不考虑它的大小关系。 轮密钥加张 轮密钥加是指每一轮的密钥与状态的异或。 轮密钥的产生密钥扩展算法 假设为整个密钥空间,由于一的轮迭代,需要个子密钥,划分 为%,,局,?,局,。,其中%为给定的初始密钥。从到。可通过密钥扩展算法 算出。 对于每一个?,?为一个的状态。可分成×的矩阵,每一列为 个字节,取作一个字。则个子密钥就有个字,×个字节。每个字 分别用砜,硒,?,硒。,表示: 磷硒醚城四个字为给定的初始子密钥%,其他子密钥以此类推。要求得 髓, ?,密钥的扩展算法如下两种情况: . 步骤?:若,.?时,陋陋一 陋一 . 步骤?:若,.时,陋呱一 算法步骤的几点说明: 字与字之间的异或为字节间的异或; 为字内的字节循环左移若干位; 为一个盒变换,不同于迭代函数里的盒; 为一个轮常数。 示例.密钥的分块表示: 按,轧,~ ,~四个字的方式写入计算机程序。 示例.简单的两轮密钥扩展: ? ? ? ? ?第一轮 第二轮 ??????????????? ,竹 ,竹 ? ? ? ? ? ? 】 上例中,歹,所处均表示有差分值,只是差分的大小不同。空白处表示没有差 分。 至于更多轮数的密钥扩展,按照.、.式计算。 对于图.的~的解释,为的加密算法的详细介绍。美国不仅 公布了加密算法,也公布了解密算法。对于解密算法,它的运算与加密类似, 只是 运算顺序为加密的倒序,且用到的各种变换变为加密算法中的逆变换。本文 不再具 体介绍。硕士学位论文 ’ ? .. 的研究现状 作为现代密码学的主要分组密码,有很多密码学者正尝试破译它,至今它 仍然是一个迷,而且至今没有任何一种有效的攻击能完全恢复出密钥。但是, 任何 一个密码设计出来并投入广泛的应用,这既有它设计的优点,同时也有缺点。现已 有大批密码学者尝试用不同攻击方法在研究的破译,相信它的破译指日可待。 当然这与现今已有的一些攻击模型和结果有着不可分割的关联。 早在 年,就有两位密码学者. 鼬采用积分密码分析方 法对进行了轮攻击‘。之后,又涌现出各国的密码学者对的安全论证 分析。他们采用了碰撞攻击、不可能差分密码分析、相关密钥密码分析、飞来去器 密码分析和代数攻击,且都获得了若干进展,最值得一提的是 等人 提出的针对的代数攻击略。以下表.给的几个攻击的代表性成果。 表.的几个攻击 攻击复杂度 密码 攻击方法 敬由托致 发表年限积分密码分析轮 年 ?篮 轮 年 碰撞攻击 勰~ 积分密码分析 轮 年 蛳 年 轮 眦攻击‘ ? 轮 年 鹏.觚试‘ 一 年 代数攻击 ,. 不可能差分攻击川 轮 年 中间相遇攻击? 轮 年轮 年 眦. ,’ ,. 二 轮 年 钔 第三章生日问题及已有应用 .数学知识:生日悖论及其解法 生日悖论源于数学,在不同的书籍,也给出不同的解法。其主要内容及解法过 程如下: 问题陈述:假设有刀个人参加一个集会,且每个人的生日均是相互独立的;那 这刀个人的生日全不同的概率见是多少 解析:此问题很容易解决,在不考虑特殊的情况下,假设一年为日,且这 刀个人的生日是均匀分布的。若把这刀个人看做拧个小球,而把一年的天看 成 是?个格子??刀,则“刀个人的生日全不同”就相当于“?个格子中恰 好有玎个格子中各有一球”。所以玎个人的生日全不同的概率为: 、 、 “ 、‘。 胪嘉墅丝嚣坠业一去×一去×...一蒙? ? ” 上式看似简单,但由于珂未知,若刀很大时,计算起来还是非常繁琐的。对此 可用以下方法作近似计算: 当刀较小时,?式右边各因子的第二项的乘积蠢×蠡 ,/?,,?,聆一都可以忽略不计,于是就有近似公式: , 见小旦学小等 当刀较大时,因为对小的正数,有衄一?一,所以由.式得 , 胪一丝掣一等 岛一??虿?一一苛 例如,当刀:时,由算式.得近似值为.,与精确值相等;当刀 时,由算式.的近似值为.,而精确值为见.?;刀时,近似硕士学位论文 ’ ? 值为.,精确值为以.。表.给出当行取定时,概率的取值。 表.给定刀的概率取值. . . . . . . . . . . . . . 一仇 上表数据表明,在一个屋子里只需要个人就会以吉的概率找到两个或两个 以上相同生日的人。 .生日悖论的推广 通过.的描述,可知这刀个人的生日均是相互独立的,且均匀分布在一年中 的天。并已讨论在未知刀个人中任何人的生日情况下,两两生日是否相同的问 题。同时,读者可以思考,当玎为多大时,有一个人的生日可以在指定的某曰过生 日这是问题的其一。接着问题二,这刀个人中,如果固定某一个人的生日,则另 外刀.个人的生日与之相同的概率又如何计算利用所学概率知识,可以对以上两 个问题作出解答。 ..生日问题引发的思考 问题一 一间屋子有刀名学生,当刀最小为多少时,才能使得超过昙概率的最少有一名 学生在假定的那一天过生日 解析:此问题可做如下处理,由于这刀名同学的生日均在?此题中? 天中,而又由假设,可看作一个随机变量,服从有?个取值的均匀分布,随机变量 的取值次数刀至少为多大,才能使得超过昙概率的最少有一种情况为预先假 定的那 个值 硕士学位论文 ’ ? 此题的突破口在已经告诉最少有一名学生在假定的那一天过生日的概率? 去。 故求刀的范围,即求最小样本的集合。 :第名同学的生日为指定生日的概率,,,?.,刀; : 一,,,,?.,刀; :至少有一个样本等于预先假定值的概率。 由于每一个样本是相互独立的,故/?,吼卜/?, 尸卜卜/?”; . ?.’尸?丢,.?./?兰 . 解算式.可得:?/??昙; 根据泰勒展式‘备?, . 可得‘与等价无穷小,即。? 令.式中:一/?,代入.式有一删?昙以??,. 对于问题一,取?,代入.式求解,可得出刀?。 问题二 刀个人在一间屋子,假设为从中选出来的人,其生日可知,那么在屋子里至 少找到一个人与生日相同,且其概率超过昙,此时疗最小为多少 解析:假设的生日是一年中的某一天,若他人与不是同一天生日,那么 他的生日必是一年中的其他天。假设所有生日日期等可能出现,那么随机选择 一人与的生日相同的概率是罢。那么所有刀.个人没有同生日相同的概率就 . 是焉筹”,那么至少有一个人与生日相同的概率是:一罢”令上式等于一豢”?三,则刀?? 此结果看似是合理的。硕士学位论文 ’ ? 为方便后面的讨论,在此称.提出的问题为生日问题三。 .生日悖论在密码中的已有应用 生日问题在数学史上为一个经典的案列,随着数学基础学科的不断完善,科学 知识的不断更新,生日悖论在很多相关领域都做出了相关的理论基垫。在密码学中, 生日问题有着广泛的应用。首先它为密码学的生日攻击?方法生日攻击是由? 提出的一种攻击方法提供了理论依据;其次它已成功的用于攻击函数, 以及对‘们、锄‘以及‘的低轮攻击。接下来主要介绍生日攻击 嬲函数,以及对.的低轮攻击。 定理.生日碰撞?设随机函数:专,其中是朋个值的集合。选取 ?磊个的随机元素就能以去的概率产生一个碰撞。 定理.假设现有掰个小球,?个篮子,且所??,把小球随机的投入篮子, 用聊,?表示一个篮子中至少有两球的概率,即为发生碰撞的概率‘。则有: 跏??等; 二竺二 ‘?; 聊,??卜 对髓?历?瓜,有聃,?.×竿; 证明: 欲瓦丽:一个篮子中最多有一球的概率,且,?一瓦瓦丽。 丽争扣一知一争一等, 】一?兰?:::?塑二 朋一 ? 一一 :盹?莉?警硕士学位论文 ’ ? 五‘.’丽务。一枷一知一?一等, ? 历一 ; 一? 一????, ?? 二竺二 一一三 ? 一 .。.聊,?一聊,??一 一? 在中,令占一 ?,那么有?一一所肌一 此时??? 相对于可忽略不计 当足够小时,芒足够大接近于,则??两 考虑:丢时,?.瓜 说明只需将大约?万个球投入?个篮子,就可以以至少昙的概率发生碰撞。 气气寿叠鼙甬莉巾的府田 础函数密码学里的一种主要用于认证和数据签名的密码算法。它是典型的输 入大于输出的即..中刀所时算法。目前使用较多的础函数有 ,,.,.,一等,且都有着相似的迭代函数结构,如下图所 不: 图. 嬲函数的迭代结构 硕士学位论丈 ’ ? 数据块是可以任意选择输入长度的明文,链式变量是具有初始值的可通过函 数扩展的参与压缩函数厂的值,厂是一个将任意长的明文信息变成长度为办 的 值日,且称厂为压缩函数。 嬲函数的应用之广泛,对它的安全性提出要求。现作如下分析: 抗原像攻击即单向性:对任意给定的嬲值办,攻击者无法根据 日办推算出明文; 抗第二原像攻击抗弱碰撞性:对任意给定的信息,攻击者无法找到 ’使得’: 抗强碰撞性:攻击者无法找到不同的信息,’使得日’; 以上三类安全性要求分别对应生日问题一、二、三。现设函数的输出长 度为聊,且每个值出现是均匀分布的。压缩函数值相当于生日问题里的那天, 输入的明文信息块就相当于理个人的生日,则当这刀个人至少两个人的生日 相同, 即任意信息经过压缩函数后,使得有输出的嬲值相同,即发生了碰撞。 函数的输出长度为聊,且均匀分布,则所有值的所有可能为”,现 假设尝试次,选择不同的输入,得出的嬲值不同,即不发生碰撞;超过次 即发生碰撞称为碰撞阀值,则对于尝试次时没有碰撞的概率为: 一专一;一;..?一等 凰一专 ?? 。 一?~。 ?弦专 一嘉~一必 。 而的数学期望: ?× ?×卜一?×尸卜一?×尸一 ?×一?×尸? ??尸 ; ?妻劬州 止~出 ? 扛历 这里?孚?詈,即平均尝试超过三次选择明文攻击,就可以产生一次碰撞。 早在年,..等人在应用密码学手册中,就曾提及关于生日碰撞的问 题,参看定理.. 很好的将生日问题应用到了密码学中,给出了如下的生日攻击础函数 的方法: ?给定的一个单向函数忙日,,任何数据日的输出长度为 厅位; ?先给定一个合法的生成数据,对其进行改动变成种变式; 再给出一个伪造的数据鸠,对其进行改动变成:种变式; ?对应会产生日,日鸠,当两者相等时即发生碰撞,可找出对应的一对 数据,鸠。 以上柚函数的碰撞攻击,其方法类似生日问题;由于曲函数的输出长度 为办位,且每比特位只能取和,则满足均匀分布条件,当找到发生碰撞的数据 对,鸩,它的概率大于.,此时攻击的时间复杂度为?次曲运算,而直 接穷举的复杂度为。 ..中间相遇攻击 中间相遇攻击..血是基于生日问题的一种密码攻击方法,但 它也有别于生日攻击。它最早于年由和提出,是用来对分组密 码的一种尝试性扩展进行攻击。在攻击过程中,有别于嬲函数中的比较值, 而是比较链中的中间变量。 中间相遇攻击有着类似生日问题的数学原理。中间相遇是通过穷举明文加密 得 一组中间变量,解密已经获得的密文得到另一组中间变量,这些中间变量的 每个字 节的每一位均是以和等概率出现的,则在此每个中间变量均是等概率出现。 当 这两组中间变量相等时,即类似生日问题里的两两相同问题。 分组密码的中间相遇攻击过程如下所示: 给定一个密钥空间,设每个密钥表示成×的矩阵: ,,】 ??一,?歹?一 取定一个中间变量,给出如下算法: . . ,.寸 . ?对【’,的每一行做同一样的变换:尸; . ?对【,卅的每一列做另一种的变换:品掣 :。蜀为加密算法。现在在未知密钥删下选择明密文对,,攻击者 可根据.、.式计算出个可能值二和个可能值品。二为和有关的 密钥部分,可记作九,;为和有关的密钥部分,记作若邢产朋』,则对应 【,/】?如删,否则不然;且称配对成功的,/】为候选密钥。计算的次数与中 间 变量的“位长度有关,设的长度为,,则计算次数为叫“。由于,专,则 。,所它可以以小于的运算次数检验个密钥,这远远优于穷举攻击。硕士学位 论丈 ’ ? 针对多重,就存在中间相遇攻击。双重使用不同的密钥加密两次的 ;如下图所示: 如 曰 由 一 一口 加密 ........................ 曰 卣 一 一田 解密 图.双重的加解密 这样的是不安全的,因为存在中间相遇攻击。其明密文均为“,密钥 ,岛均为,对已知的明密文对,,先用个可能的加密,得到 个中间变量值,将这些值从小到大存入一个表中;再对可能的匠解密,得 到个中间变量值?,将这些值与表中的值比较,如果产生配对厂;则它们 的密钥可能是,%。用一个新的明密文对检测所得两个密钥,如果两密钥产生 正 确的密文,则他们是正确的密钥。文献【】给出了中间相遇攻击方法计算复 杂度的 算法,得此时的复杂度为××?’。 ..对.的低轮攻击 基于生日攻击原理的碰撞攻击已成功地用于分组密码的攻击,就是典型代 表。下面着重介绍一的轮碰撞攻击。 . .给出了如下的轮区分器,,,分别表示轮区分 器的输入,表示第四轮的输出。硕士学位论文 ’ ?巳? 墨 尺 ‰互 互 五 图. 轮区分器 上图中,令‰,。,。:,‰巳,其中,:,,表示】,中固定的三个字 节;表示】,中可随意取定的字节,为一个位,可取遍种可能。其硕士学位论文 ’ ? 他的“”表示不考虑在内的字节,它的值为固定值。记作,乞,乞为一个常数 三元组。 】,为区分器的第一轮输入,根据的加密算法,第二轮的输入应等于第一 轮的输出,的值依赖于和以及这一轮的加密密钥。依次类推可知,的值也 依赖于和。可以写成陟】,表示里的字节与和有关。根据生日攻击原理, ,?舒,且?,使得。。。:陟】对砂?,,,??,成立,即以大于 /的概率发生碰撞。 由于是丁的解密,而勋似?‰?互 ?%?‰‰,‰ 为第四轮子密钥的一个字节,可以通过这个方法来检查碰撞是否发生。与的 关系表明?‰?互 ?疋 ?‰是一个与密钥和、有关的函数。那么 只要知道几组、少,代入上式求解,可以判断结果是否相同,如果,乞代入的 结果相等,即就发生了碰撞。具体攻击方法的构造如下: ?取定一个包含个元素的集合,选择一个包含个元素的集合人; ?丁。 ?丁。 ?对?,?人,计算厶?丁。? ?丁。?,计算 个线性组合的计算量不超过的一次加密,以此大大减少了复杂度。 ?检测是否存在,:使得乞厶:。 区分器总共需要选择明密文对,时间复杂度小于,因此复杂度由数据复 杂度决定。 把区分器至于加密的第轮至第轮,其余轮数的子密钥。文章结果显 示,对一个密钥的测试所需的时间复杂度不超过一次的轮加密,总攻击 的时间复杂度接近于穷举密钥恢复攻击。硕士学位论文 ’ ? 第四章对一的轮攻击 . 攻击方法 .. 简介 是近几年提出的一种新的攻击工具,它主要中间相遇攻击 配合使用。年由仃 等学者在文献【 】中用于原像攻击 一种函数和一系列。并且在一系列的嬲函数里,构 造的路径导致了最好的原像攻击。的发现源于?.眨, 算法模式。在年,?.已用于、、一//等函 数的攻击,虽然可以攻击,但是要在一系列中得以广泛应用,还是不可能的, 因为在应用..时,还是受到消息扩展的限制。使用? 和中间相遇攻击时都会出现一个相同的问题,“迭代过程中,信息的扩散程度 不能 过大,因此攻击的轮数均不长。技术的构造,建立在这个基础上加以改进。 技术的引入,使得原像攻击和分组密码的密钥恢复攻击有了新奇的发现, 由此迅速成为分组密码中的密钥恢复工具。诸多密码学者利用它攻击、 ??、、、燃一和的全轮攻击,并给出全新的结果, 这足以看出它的应用之广泛。 .. 的相关知识 是一个全新的概念,在迭代函数中,需配合中间相遇攻击进行运算。 接下来,介绍什么是中间相遇攻击,的构造以及如何配合使用中 间相遇。 、概念 设厂:厶嚣是一个个中间状态值溉映射到个密文的函数。给 出如下个密钥:硕士学位论丈 ’ ? ,】 【,】 ,一】 【,】 研,】 【,一】 . ~个密钥空间研,月 ?,】【一,】?一,一】 对于满足厶爪码,/?,,...,一的三元数组?,溉,皿【,/刚称作为 维。结构图如下: 、 ,】 【,一图. 结构图 、的构造 对于个一分组密码,给定.式的密钥空间。对于每一个加密算法,可写 成厂。,对明密文作如下处理: 在删下的解密 图.加解密处理过程 选取的在密钥删下解密得到只,然后再利用中间相遇攻击检查是否 了,,:粤码,如果配对成功,则存在的【,】为一个候选密钥。 、的独立相关密钥差分 的概念给出维的构造,关键在于厂函数和【,/】的选取。给 硕士学位论文 ’ ? 出初始值【,砜,,有如下关系: . 甄』 再考虑密钥差分群,岁。 矿 . ?:??,当《时,?。; 即在厂和密钥差分群作用下,把差分为。的输入变为输出非; 甲。 . :,?,当芋时,。; 即在厂和密钥差分笋作用下,把差分为非。的输入变为输出; 当?,,,差分没有共同的活跃的盒在里满足时,也就是运算时?, 和,的差分互不影响可构造如下的联合差分: . ,,....,,?? .,挚?,,,。 再联系.式,有 . 砜。.,』盟蝎。?, 令? 【,,】【,】群笋 由此可以构造出一个维,如果?,?,,,则所有的,卅均不 同。这样的构造意在减少?,,』的运算,列举了个参数,仅有×个中间状 态值,且计算次数?×。硕士学位论丈 ’ ? 、匹配计算及复杂度 的构造有两个特征,一是构造的运算轮数为的长度; 二是维数。这两个性质都是与的构造复杂度有关,除此外,带有 的密钥恢复攻击主要消耗还体现在配对计算过程的消耗。 『门 匹配计算主要是用来检验是否了,歹:鼻尽,,接下来介绍配对预计算的思想: 尸?屿矿?屿四?屿 攻击者根据图.,将鼻骘尽,细分为: 。, 选择适当的密钥得出×个需要配对的变量值,然后对它们进行匹配: 。 卫, ‘/ 半;兰;《码. .式不再利用中间相遇的攻击方法去算,而是根据构造的来计算。 只需计算对明文 的加密值和对四,的解密值是否相等。计算量由轮函数的扩 散性 质和密钥的扩展性质共同决定。 匹配计算在整个计算中占了很大比重,而选择合适的密钥【,,】可以尽量的 减 少匹配计算的复杂度,从而减少整个计算的复杂度。未知密钥删的长度为聆 有”种可能,尝试的密钥空问【,『】有个值,利用匹配预算的一个密钥 候选算法的运算次数为次,所有要恢复出整个密钥,运算次数为”埘。 . 锄厅一幻搬蠢计算叠新计算岳误对 缸妇。:表示构造一个的复杂度; 五., 蠢计算:表示计算只?’码的次数?算法的计算次数; 重新计算:表示匹配计算的复杂度; 毒误对:表示配对错误对的产生的复杂度,如果是以字节做运算,错误对的数 硕士学位论文 ’ ? 量大约是扣。 .对一的轮攻击 仃?等人在文献【】中给出一的轮攻击。 并得出如下结果: 表. 一的轮攻击数据 构造 轮数 维数 世字节 置字节 时间复杂度 记忆复杂巴。叫 . , ,配对 预计算 重新计算 轮数 计算步骤 记忆复杂度 前计算盒 后计算盒 ,’一占 . . 厶 撑 总复杂度 巴删叫 。,理 皇新计算 预计算 错误对 。扣盯 ,’. 二 ..密钥空间伍【,刀的造构 给定初始密钥【,】,固定第和个字节为,其余字节取遍所有可能,则 有个初始密钥: ?裟哪 【,】: 再构造,歹差分: ,】: 【,巾一, .,,歹】,】 【,刀 【,】 , , 【,刀为所有取遍,字节的差分和,字节的差分: .. 的维轮构造以及前后配对时的前后计算图 ?。??~, 』书;卜尸主囊羞隅;隅主霎嘉;主曩参乏爱参冈毒主要爱阿 ’比出 比出巳出 ?出 ?? 吐埔吐埔吐出 。阡羽 阡 习 :芝州蒯 一?““?‘“ ‘吐制 吐划 霉 图.向后计算 ?????“~ 寸 图.向前计算 ?堪曲嘲 ?珏赫鳓硅蓐 饿 乞 .丛参 匪 匪 厍 ??厍 闹牛 隔哇 吐 吐 划年 划击 隹 匪 ? .。 专 蛰 誊 匪 匪 习止 溺吐 阡 阡 吐 巳 划匝 型匠 匪 匪 ? ’ 》 ? 羔 羔 匪 匪 阡羽吐 阡羽攀 隆 翻蠢 比出乖 ‘ 庄 匪 。. : : ,. 殛呵 图.构造