4-密码学基本理论.ppt

回顾上次授课的内容，古典密码时代的近代密码时代是从20世纪到20世纪的50年代，即第一次世界大战时期和第二次世界大战时期的手工作业和电力机械所实现的复杂的替代和转换通信手段：电报通信现代密码时代，古典密码时代是从古代到19世纪末，数千年的纸， 笔或简单机器实现的替代或转换通信手段：信使现代密码时代是从20世纪到20世纪的50年代，即第一次世界大战时期和第二次世界大战时期手动或电力机器实现的复杂替代或转换通信手段：电报通信现代密码时期是从1950年代初到现在分组的密码， 序列密码和公钥密码、数学理论基础通信手段：无线通信、有线通信、计算机网络等密码学基础理论，现代密码学始于1950年代，1949年Shannon的TheCommunicationTheoryofSecretSystems为现代密码学奠定了数学理论基础。 密码体制的分类现代密码体制的数学理论密码解读香农秘密理论，密码体制的分类(1)，密码体制的序列和组密码体制的对称和非对称密钥密码体制的转换，打破明文中的一些固定结构模式，将明文和密钥信息扩散到密文中。 相反，明文和密钥信息混合(混淆)。 系列：明文和密钥进行比特对比特的运算。 核心是密钥生成算法设计。 数据包：所有明文数据包在相同的密钥控制下分别被加密变换。 核心是设计复杂高效的密码解密算法。 用于密码方式分类(2)、密码方式系列和组密码方式的对称和非对称密钥密码方式、对称密钥密码方式(单密钥密码方式、私钥密码方式)、非对称密钥密码方式(双密钥密码方式、公钥密码方式)、密钥、解密密钥、密钥、解密密钥、密码算法的设计。 从概率统计角度研究信息传播和保密问题。 可以分析加密算法的复杂性，确定算法的安全性。 为了安全起见，数学皇后、素数互素模拟演算、模逆元同馀方程、孙问题、中国馀数定理因子分解、素数、公钥密码必须使用大素数(1024比特的素数)，梅森数以17世纪法国数学家马兰梅森的名字命名，梅森数指的是形状为2n1的数，标记为Mn 挪威计算机专家奥德斯特林莫通过参加名为“互联网梅森素数大搜索”(GIMPS )的国际合作项目，于2009年4月发现了第47个梅森素数。 这个素数是“2的42643801次方减1”。 12837064位数字，用普通大小连续写这个数字，其长度超过50公里，梅森素数列表(1)，1772年，Euler被称为“数学英雄”，以惊人的毅力证明“2的31次方减1”是第8个梅森素数、梅森素数列表(2)、计算机的发明革命化改进了梅森素数的探索。 最初的成功案例是M521的证明，那是在莱默的指导下，利用R.M.Robinson教授编写的软件，洛杉矶加利福尼亚大学的数据分析协会的属于美国国家标准局的西部自动计算机(SWAC )于1952年1月30日晚上获得了10:00。 然后不到2小时，就发现了下一个主素数m67。 在随后的几个月中，用同样的程序发现了另3个主素数M1279、M2203、M2281。 梅森素数清单(3)、电子新领域基金会(EFF )最初给超过1000万位数的个人和机构10万美元的奖金。 时代周刊被评价为“年度50件最佳发明”之一，指数学女王、素数互素模式运算、模逆元联合方程式、孙问题、中国剩馀定理因子分解、互素、互素：任意正整数a和b，它们除1以外没有共同因子时，记为gcd(a，b)=1、a和b互素。gcd (15，28 )=1g CD (15，27 )=3，数学论-数学皇后，素数互素模式运算，模反元同馀方程式，孙问题，中国馀数定理因子分解，模式运算，模式运算：简单地说，求馀数。 如果r是a除以b的馀数，则a和b的关系可表示为a=r(modb )，其为模拟运算。 例如： 23=11 (mod12 ) 29 (mod26 )=310 (mod26 )=3-1(mod26 )=25，模拟运算广泛应用于数学逻辑和编程，从奇偶校验的判别到素数的判别、从应模拟运算到最大公约数的求法、从孙子问题到凯撒密码问题，存在模拟运算的形态在逆元(1)、公钥密码方式中，大多需要解逆元。 求模块逆元。 即，a*x=1(modn )或1=(a*x)modn。 这里，a和n是正整数，x被称为a的模数n逆元。 a-1=xmodn示例：4-1mod7=？ 5-1mod14=？ 2-1mod14=？ 4*2(mod7)=1、2、3，无逆元！ 解逆元问题很难，有结果，没有结果。 此外，若模型逆元(2)、a与n为要素，则存在a模型n的逆元。 如果a和n不是互素，就不存在a型n的逆元。 如果n是素数，那么从1到n-1的各个数和n互为素数，在该范围内恰好有倒数。 例如，n=51234模反元1324、gcd(a，n)=1、扩展欧几里德算法、数论-数学皇后、素数互素模运算、模反元同馀方程、孙问题、中国馀数定理因子分解、同馀方程、连立k个同馀方程x=b1(modn1)、x=b2(modn2)、x=bk(modnk )为同馀方程孙问题- 孙子算经“现在什么不知道那个数，三三数的其馀二，五五数的其馀三，七七七数的其馀二.问什么？ “回答日23 .”若将求出的数设为x，则用x=2(mod3)、x=3(mod5)、x=2(mod7)、孙子的问题、孙子的问题- 孙子算经“现在不知道数量，问三三数的剩馀的二、五五数的剩馀的三、七七七数的剩馀的二、物的几何”这样的方程式表示。 “答日二十三.”解法明代程大位算法统宗 (1593 )的诗：人同道七十稀，五树梅的甘一枝，七子团圆半个月，除一百零五次航班外得知。 另外，假定x=70 *2*3*2(mod 105 )=233 mod 105=23，定理(中国馀数定理)为m-1、m-2，和mk为两个像素的正整数，则针对模型m，唯一的解：的ei满足同馀方程式，其中，Mi=M/mi，ei=mi=mi-1 (mod mi ) x=m 1a1m 2a 2mkmkAK (modm )、x70a 21b 15c(mod105 )、中国馀数定理，如果某一用途知道某些二元素数的汇总，则可重新配置此数目。 数量用小数表示，数量的运算用小数来实现。 思考试题，汉信点兵：有兵一队，成为5行纵队的话，最后一行成为一人的6行纵队的话，最终成为5人的7行纵队的话，最后一行成为4人的11行纵队的话，最后十人行进，求士兵数。 解设x是求兵数，问题意思：x1(mod5)、x5(mod6)、x4(mod7)、x10(mod11 )、2100、数论-数学的皇后、素数互素模式运算、模逆元同馀方程式、孙问题、中国馀数定理因子分解、因子分解、因子分解是对数的分解。 例如18=2*32、96=25*3、110=2*5*11的良好的因子分解方法：试除法、数域筛选法、椭圆曲线法等。 但是，对大的数(1024比特以上的数)进行因子分解所需的计算时间在当前的条件下是天文数字。 因此，知道两个大的素数p和q，求其积很容易，相反，很难知道n求p和q。 RSA公钥密码体制，这种分解是独特的数学理论、数学逻辑复杂度理论和研究整数性质的数学分支。 用于密码算法的设计。 从概率统计角度研究信息传播和保密问题。 可以分析加密算法的复杂性，确定算法的安全性。 信息论、信息论是应用概率论与数学统计方法研究信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。 一般来说，香农在1948年10月发表于贝尔系统技术学报的论文AMathematicalTheoryofCommunication (通信的数学理论)是现代情报论研究的开始。 信息和消息、信息和消息是密切的两个不同的概念。信息论在密码学中的应用(1)，多重熵解开唯一距离，多重性在密码学中并不理想。the、of、and、to、a、in、that、it、is、I，任何一篇文章中1/4的篇幅都被这十个词占据。 多馀度越小，破译解析越困难，有利于保密！ 信息论在密码学中的应用(二)，熵：表示信息量的方法。 即，表示不同信息所需的二进制比特的数目。 例如，熵H(X)3表示一周中的一天，熵H(X)3)表示一个事件的不确定性，其中状态111未被使用并且信息论在密码学中的应用(3)。 不确定性大，熵值大，在一个系统中发生所有事件等概率时，不确定性最大，熵最大，达到最大熵。 某个事件必然发生，不确定度为0，熵为0，加密系统的H(M )越大，表示哪个密文对应哪个明文的不确定度越大，即由密文分析明文的概率越小，加密系统越安全！ 密码学中信息论的应用(4)，唯一的解读距离，解读分析的困难性，含义：密码分析者进行网络攻击时，解读唯一有意义的明文所需要的最小限度的密码量。 描述被截获的密文量与成功解密的可能性之间的关系，u :唯一性解密距离H(K ) :密钥熵d :语言的多重性，明文的多重性越大，唯一性解密距离越小。 因此，为了提高加密体制的安全性，必须尽量减少明文的多少度。 数学理论、数学理论、信息理论、复杂度理论、研究整数性质的数学分支。 用于密码算法的设计。 从概率统计角度研究信息传播和保密问题。 可以分析加密算法的复杂性，确定算法的安全性。 复杂度理论，算法复杂度o时间复杂度t空间复杂度s问题NP类问题NPC问题，t和s通常是n的函数n测量输入算法中的大小，例如T=O(n )，算法的安全性，解密能力，在不同算法之间在时间成本方面，理论上消耗的时间较少，有多少密码学的基本理论，现代密码学始于20世纪50年代，1949年Shannon的TheCommunicationTheoryofSecretSystems为现代密码学的数学理论奠定了基础。 密码体制的分类现代密码体制的数学理论密码解读香农秘密理论、密码解读(密码分析)、密码学加密、密码分析学密码分析、区分：解密(解密)和密码解读、密码解读规则密码解读方式密码解读程序、所谓拷问入室强盗键盘记录仪、 密码解读规则密码规则表代替密码明密异同规则改变密码一次性不变规则文字统计特性在电报文件形式规则战争中发生重大事件的两国会谈期间，明密文字虽然不同，但出现频率相同，各文字以明文频率等于密码文字频率，考虑：单文字、双文字、 三重文字，想法：在标题、报尾、常用文字、语言、军事电报/政府报告/外交报告密码解读方式中，已知只有密码文攻击者有加密的密码文攻击者在对应的明文选择攻击开始前选择明文，从系统中取得对应的密码文。 选择密文攻击攻击者可以在发起攻击前选择密文，并从系统获得相应的明文。 最难！ 另外，解密步骤将对相同加密方式的加密进行整理分类而得到的密文进行分类。 统计分析对密文进行单、双、三字等统计，确定密码制作的方法，揭露密码规则。 假设和反证是在规则性强的场所进行的，例如标题的末尾、可能词、大段重复信息成为突破口。 密码学的基本理论，现代密码学始于20世纪50年代，1949年Shannon的TheCommunicationTheoryofSecretSystems为现代密码学的数学理论奠定了基础。密码体制的分类现代密码体制的数学理论密码解读香农秘密理论、理论秘密体制、理论无法解读的密码体制完全秘密体制理想秘密体制、前提：仅密码分析，明文数=密码数=密码数，唯一解析距离u，即语言