第一章 公钥密码学

ΓВ1第一章公钥密码学公钥密码学思想RSA算法公钥的应用ΓВ2公钥密码体制公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥，在消息的保密性、密钥分配和认证领域有重要意义。ΓВ3密钥分配问题：如果密钥被偷，设计再好的密码体制都没有用传统密码中的三个问题数字签名问题：能否设计一种方法确保数字签名出自某个特定的人，并且各方无异议？密钥管理问题：n个用户需要n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大ΓВ4是密码学一次伟大的革命1976年，Diffie和Hellman在“密码学新方向”一文中提出。使用两个密钥：公开密钥、私有密钥加解密的非对称性利用数论的方法是对对称密码的重要补充ΓВ5公钥密码系统和对称密码系统互为补充公钥密码系统的出现并不会取消对称密钥密码系统。原因就是非对称密钥密码系统是用数学函数进行加密和解密，比对称密钥密码系统要慢得多。对于大信息的加密，对称密钥密码系统还是需要的。另一方面，对称密钥密码系统在速度方面的优势也不能成为取消公钥密码系统的理由。在公证、数字签名和密钥交换等方面还是需要非对称密钥密码系统的。ΓВ6公钥密码体制的特点无需密钥的安全传递n个用户仅需n个“公钥-私钥”对支持数字签名机制安全性基于带陷门的单向函数加密、解密速度比DES、AES等对称密码体制慢可用于对称密钥的交换ΓВ7公钥密码体制的种类1加密/解密2数字签名3密钥交换算法RSA椭圆曲线Diffie-HellmanDSS是是是是是是否否是否是否ΓВ8对公钥密码体制的要求：1B产生一对密钥（Kpb，Ksb）在计算上是容易的2发送方A加密消息C=EKpb(M)在计算上是容易的3接收方B对密文解密M=DKsb(C)在计算上是容易的4攻击者从Kpb计算出Ksb在计算上不可行的5攻击者从Kpb和C计算出M在计算上不可行的ΓВ9公钥密码的用法用公钥加密、私钥解密（可以）用私钥加密、公钥解密（可以）用公钥加密、公钥解密（不行）用私钥加密、私钥解密（不行）ΓВ10只有两个算法被普遍接受1RSA2椭圆曲线就是要找一个单向陷门函数：不太容易所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在反方向上要计算是不可行的。ΓВ11单向陷门函数（1）Y=fk(X)容易(k和X已知)X=fk-1(Y)计算上不可行（k未知，Y已知）X=fk-1(Y)容易（k已知，Y已知）寻找合适的单向陷门函数是公钥密码体制应用的关键！ΓВ12单向陷门函数（2）困难程度举例–打碎/拼接、平方/开方、乘法/分解*单向函数存在否–尚无严格的数学证明ΓВ13单向陷门函数（3）单向陷门函数–如果知道某个陷门(秘诀)，即能容易恢复x–（陷门即为私钥）举例–魔方的置乱/恢复如果有那个口诀，就能很快恢复ΓВ14简单例子选中两个素数p＝7，q＝17n＝pq＝φ(n)＝请练习任务：对明文M=19加密n＝pq＝119φ(n)＝(p-1)(q-1)＝6×16＝96选取整数1eφ(n)与φ(n)互素：e＝5求e的逆元d：ed≡1modφ(n)请练习计算C=Me(modn)=?其中M=19请练习计算M=Cd(modn)=?请练习d=77c=66ΓВ15RSA示例总结选p＝7，q＝17则n＝pq＝119且φ(n)＝(p-1)(q-1)＝6×16＝96取e＝5则d＝77(5×77＝385＝4×96＋1≡1mod96)公钥（5，119），私钥（77，119）加密m＝19则c＝memodn=195mod119=66mod119解密c＝66m＝cdmodn=6677mod119＝19mod119ΓВ16RSA算法基本参数–分组密码算法–基于整数乘法–明/密文分组以及公/私钥被看作小于n的整数–加/解密是模乘运算ΓВ17RSA算法总结：密钥产生找素数–选取两个大的随机的素数p，q计算模n和Euler函数φ(n)–n＝pq–φ(n)=(p-1)(q-1)找ed≡1modφ(n)–随机取一个数e(与φ(n)互素)，用扩展Euclid算法求d即可发布–d保密，(d,n)是私钥Ks–发布(e,n)，这是公钥Kp–销毁p、qΓВ18RSA的正确性加密明文分组m做为整数须小于nc=memodn解密m=cdmodnΓВ19RSA考虑素数–必须够大，否则对手可能很快分解n–判定，采用Miller-Rabin概率测试方法假素数意味着加解密不能正确进行，故可放弃之–强素数(p-1)/2和(q-1)/2应是素数选取较小的e和较大的d–e：3、65537ΓВ20RSA参数的考虑•p和q在长度上应仅差几个数位，即p和q应是1075到10100（p-1）和（q-1）都应包含一个较大的素数因子，r-1也有一个大的素因子gcd(p-1,q-1)应比较小如果en且dn1/4,则d可以很容易确定ΓВ21攻击RSA数学方法分解n–得到p和q，就可以知道φ(n)，就可从e求得d直接求φ(n)–不分解n，而直接求φ(n)，再求d直接求d–不求φ(n)，直接求dΓВ22椭圆曲线密码系统设p是大于3的素数，且4a3+27b2≠0modp,则称曲线y2＝x3+ax+b,a,b€GF(p)为GF(p)上的椭圆曲线有限域GF(p)上的椭圆曲线的一些点构成交换群，而且离散对数问题是难解的椭圆曲线密码建立在椭圆曲线群的离散对数问题的困难性之上ΓВ23需要澄清的问题不要误认为公钥密码加密在防止密码攻击方面更安全可靠（任何加密方案的安全性都依赖于密钥的长度和加密算法的计算复杂度）不要误认为公钥密码加密使得常规加密技术过时（公钥密码加密开销更大，所以公认为仅用于密钥管理和数字签名）不要误认为公钥密码技术使得密钥管理非常简单，事实上，仍需要一个代理中心，而且整个过程既不简单，也不是更有效.ΓВ24使用公钥传递会话密钥直接使用公钥算法－太慢只用来传递会话密钥–(假设A已经有B的公钥KeB)–A发起和B的通信–A产生会话密钥Ks，并用KeB加密后传给B–B能用自己的私钥KdB解开–他人不会知道KsΓВ25对称算法vs.公钥算法速度–典型相差1000倍密钥管理–对称算法需要额外安全信道–公钥证书中心混合密码体制–公钥算法用于签名和认证–用公钥算法传输会话密钥–用会话密钥/对称算法加密批量(bulk)数据ΓВ26作业：用RSA加密解密p=3,q=11,e=7,M=5p=5,q=11,e=3,M=9如果：e=31,n=3599,d=?c=10,e=5,n=35,M能够求出吗？