资源描述：
《第8讲 公钥密码学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8讲公钥密码学1公钥密码学公钥密码学思想RSA算法公钥的应用2公钥密码学的发展是整个密码学发展历史中最伟大的一次革命。公钥密码体制公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥，在消息的保密性、密钥分配和认证领域有重要意义。3公钥密码比传统密码更安全两个误解公钥密码是一种通用的方法，所以传统密码已经过时。4密钥分配问题：如果密钥被偷，设计再好的密码体制都没有用传统密码中的两个问题数字签名问题：能否设计一种方法确保数字签名出自某个特定的人，并且各方无异议？51976年Diffie和Hellman针对上述问题提出了一种方法，它是密码学的一次革命密码学革命6公钥
2、密码体制介绍7仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。公钥密码体制特点两个密钥中的任何一个可以用来加密，另一个用来解密。有6个组成部分：明文、加密算法、公钥、私钥、密文、解密算法8用公钥进行加密2Alice产生一对密钥，用于加密和解密3Alice将一个密钥公开，另一个密钥私有BobAlice1Bob要发送消息给Alice4Bob用Alice的公钥对消息加密，发送给Alice。只有Alice能解密9公钥进行加密B的公钥KUbB的私钥KRb待发送的明文XA要发消息给BY=EKUb(X)X=DKRb(Y)破译者10用公钥进行认证BobAlice11用公钥进行认
3、证A用自己的私钥进行加密Y=EKRa(X)B用A的公钥钥进行解密认证X=DKUa(Y)12用公钥进行认证:问题？？问题1需要对整条消息加密，占用大量存储空间解决的方法：仅对消息的认证符加密问题2不能提供保密性如何解决？？13公钥体制：保密和认证14公钥密码体制的应用1加密/解密2数字签名3密钥交换算法RSA椭圆曲线Diffie-HellmanDSS是是是是是是否否是否是否15对公钥密码体制的要求：1B产生一对密钥（KUb，KRb）在计算上是容易的2发送方A加密消息C=EKUb(M)在计算上是容易的3接收方B对密文解密M=DKRb(C)在计算上是容易的4攻击者从KUb计算出
4、KRb在计算上不可行的5攻击者从KUb和C计算出M在计算上不可行的6附加条件（并非所有都满足）：加密解密顺序可交换：M=EKUb(DKRb(M))=DKUb(EKRb(M))16公钥密码学的研究情况与计算复杂性理论密切相关计算复杂性理论可以提供指导但是需求不尽相同计算复杂性通常针对一个孤立的问题进行研究而公钥密码学往往需要考虑一些相关的问题 比如，密码分析还需要考虑已知明文、选择明文等相关的情形讨论的情形不同计算复杂性考虑最坏的情形而对于公钥密码学则是不够的一个困难问题必然会导致一个保密性很好的密码系统吗？不一定，还需要有好的构造17背包(knapsack)问题0-1背包
5、问题：给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程S=∑aixi的二进制向量X=(x1,…,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题用于公钥密码学做法方法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题18易解的背包问题——超递增背包满足下列条件的背包ai>∑aj(j=1,…,i-1)这样的背包也被称为简单背包求解从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0
6、如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包结果为{2,3,13,52}所以，密文70对应的明文为11010119转换背包简单背包用作私钥如何产生相应的公钥——转换做法：选择一个整数m>∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后ai’=wai(modm)(i=1,…,n)这里的ai’是伪随机分布的这样得到的背包是非超递增背包20基于背包问题的公钥密码系统 ——MH公钥算法加密将明文分为长度为n的块X=(x1,…,xn)然后用公钥A’=(a1’,…,an’)，将明文变为密文S S=E(X)=∑ai’xi解密先计算S’=w
7、-1Smodm再求解简单背包问题S’=∑aixi21背包密码系统的意义是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷22只有两个算法被普遍接受1RSA2椭圆曲线就是要找一个单向陷门函数：不太容易23单向陷门函数（1）Y=fk(X)容易(k和X已知)X=f-1k(Y)计算上不可行（k未知，Y已知）X=f-1k(Y)容易（k已知，Y已知）寻找合适的单向陷门函数是公钥密码体制应用关键！24单向陷门函数（2）困难程度举例打碎/拼接、平方/开方、乘法/分解*单向函数存在否尚无严格的数学证明
