密码学的现在

1、密码学的”现在”清华大学 彭天翼密钥分配的困难性lInternet的发展l总统的电话？什么是公钥加密体系？lAlice和Bob之间不再拥有私密的信息l这还可能可以加密么？公钥加密体系l公钥加密体系：挂锁的思想l1. Alice加上一把锁发给Bobl2. Bob再加上一把锁发给Alicel3. Alice解掉自己的那把锁，再发给Bobl4. Bob解开锁之后，得到Alice发给他的信息公钥加密体系l公钥加密体系：挂锁的思想l1. 加锁容易解开难l2. 加锁的可交换性公钥加密体系l单向函数：l计算f(x)=y速度很快l计算f-1(y) = x速度很慢公钥加密体系lPNPlP问题的定义 ：在多项式时

2、间内可以解决的问题。lNP问题的定义：在多项式时间内可以验证的问题。lNPC难题：极大团，哈密尔顿环等公钥加密体系l单向函数的存在性= PNP公钥加密体系l数论中的难题：l离散对数问题l给定素数P，给定数g，a。l已知gx = a (mod P)l求x公钥加密体系l给定素数P，给定数g，a。已知gx = a (mod P)求xBaby-Step-Giant-Step:x = c*sqrt(P)+d预处理集合S1=g(sqrt(P)*c) | c = sqrt(P), S2=gd|d=sqrt(P)公钥加密体系l给定素数P，给定数g，a。已知gx = a (mod P)求x复杂度O(sqrt(P

3、)仍然是一个指数算法公钥加密体系l公钥加密体系：l1. Alice发送(g,P,gx) Bobl2. Bob发送gy Alicel3.共享密钥gxylEve可以获得什么？公钥加密体系l公钥加密体系：单向函数l单向函数2：质因数分解l两个数相乘很容易l分解很难公钥加密体系l公钥加密体系：单向函数l（RSA）N=p*ql1. Alice 发送(N,e) Bobl2. Bob发送xe Alicel3. Alice解密:x(e*d)。其中(e*d mod (p-1)*(q-1) = 1)公钥加密体系l欧拉定理laphi(n) = 1 (mod n)l其中phi(n)定义小于等于n并且与n互质的数的个数

4、lphi(p) = p-1lphi(n) = n*(p1-1)/p1*(p2-1)/p2.公钥加密体系l证明：若n=p1l1 * p2l2 * . pklkl则phi(n) = n*(p1-1)/p1*(p2-1)/p2.公钥加密体系l证明：若n=p1l1 * p2l2 * . pklkl则phi(n) = n*(p1-1)/p1*(p2-1)/p2.l容斥原理：n-n/p1 - n/p2 - n/pkl+ n/(p1p2) + n/(p1p3) l- n/(p1p2p3)公钥加密体系l欧拉定理证明：laphi(n) = 1 (mod n) (a,n) = 1)公钥加密体系l如何随机出一个素数

5、？l随机一个数以后再进行检测公钥加密体系lMiller-Rabin Testl则n是一个合数公钥加密体系l确定性-多项式时间算法：l2002，AKS primality test O(logn12)进一步改进到(logn6)公钥加密体系lRSA的故事公钥加密体系l三个人风格迥异：Ron Rivest，RSA 中的 R。他在耶鲁读数学系，随后跑到斯坦福读计算机科学系研究人工智能。他所研究的课题让机器人在没有人干预的情况下在停车场散步，在那个计算机科学系仅成立四年的年代明显太过乐观，但他依然乐此不疲。毕业后他接受 MIT 任教的工作机会。也许是因为多年积累的科研氛围，他对新技术非常兴奋，大量阅读前

6、沿文献。与此同时，他认为迷人的理论应该与现实世界相结合，才能散发魅力，对世界有所改变，这也是他的理想。公钥加密体系l三个人风格迥异：Adi Shamir，RSA 中的 S。他是以色列人，和 Rivest 一样，学数学后转计算机科学进一步深造，毕业后以访问学者的身份来到 MIT。他很聪明，学习能力超强。虽然他在数学上的造诣颇深，但起初他在算法方面的知识十分匮乏，当他接到 Rivest 关于算法高级课程讲授的邀请信时连连叫苦，教算法已经够呛了，还什么高级课程？给博士生讲的么？虽然如此，他还是硬着头皮前往 MIT，之后很快投入到学习中，整天泡在图书馆，读了一书架关于算法的书籍，最终仅用两周便掌握了所

7、需的知识。公钥加密体系l三个人风格迥异：Leonard Adleman，RSA 中的 A。自幼胸无大志，从未想过做什么数学家。读大学时受各方面影响，甚至包括电视节目的影响，在专业选择上犹豫不决，最终因为学数学会有大量时间做别的而选择就读数学系。毕业后在美国银行做程序员，之后想去学医，被录取了却又改变主意想研究物理，上了几堂课又觉得没意思。最后他怕挂科对找工作有影响，跑去图书馆借了本计算机科学的书，一直没还，学校就会因此扣留成绩单。辗转几次后，他最终选择读计算机科学 PhD。毕业后同样在 MIT 任教。公钥加密体系l故事从一次串门开始：l一天A无意走到了R的办公室，R正在看一篇最新的密码学文章，

8、他本以为这只是一个平凡的工作，没想到。公钥加密体系l42个错误方案。1977 年 4 月，Rivest 和其余两人参加了犹太逾越节的 Party，喝了些酒。到家后 Rivest 睡不着，随手翻了翻数学书，随后一个灵感逐渐清晰起来。他大气不敢出一口，冷静下来连夜整理自己的思路，一气呵成写就了一篇论文。次日，Rivest 把论文拿给 Adleman，做好再一次徒劳的心理准备，但这一次 Adleman 认输了，认为这个方案应该是可行的。公钥加密体系l从ARS到RSA。公钥加密体系l英国的保密：数学家Clifford Cocksl国家安全局（NSA）:lNever say anythinglNo such agency质因数分解l来自解密师的反击：大整数质因数分解质因数分解lPollard-rhoPollard-Rhol举例说明：f(x) = x2+1 (mod p)Pollard-RhoPollard-Rhol复杂度分析：l考虑随机性，出现周期的时间期望？l通过生日悖论，大概sqrt(p)的时间，这里的p是指待分解整数N的一个因子。l严格证明：open领先算法General number field sieve2009年，RSA-768，232bit s