公钥密码学

ΓВ1公钥密码学南京理工大学自动化学院项文波ΓВ2公钥密码学公钥密码学思想RSA算法公钥的应用ΓВ3公钥密码学的发展是整个密码学发展历史中最伟大的一次革命。公钥密码体制公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥，在消息的保密性、密钥分配和认证领域有重要意义。ΓВ4公钥密码比传统密码更安全两个误解公钥密码是一种通用的方法，所以传统密码已经过时。ΓВ5密钥分配问题：如果密钥被偷，设计再好的密码体制都没有用传统密码中的两个问题数字签名问题：能否设计一种方法确保数字签名出自某个特定的人，并且各方无异议？ΓВ61976年Diffie和Hellman针对上述问题提出了一种方法，它是密码学的一次革命密码学革命ΓВ7公钥密码体制介绍ΓВ8仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。公钥密码体制特点两个密钥中的任何一个可以用来加密，另一个用来解密。有6个组成部分：明文、加密算法、公钥、私钥、密文、解密算法ΓВ9用公钥进行加密2Alice产生一对密钥，用于加密和解密3Alice将一个密钥公开，另一个密钥私有BobAlice1Bob要发送消息给Alice4Bob用Alice的公钥对消息加密，发送给Alice。只有Alice能解密ΓВ10公钥进行加密B的公钥KUbB的私钥KRb待发送的明文XA要发消息给BY=EKUb(X)X=DKRb(Y)破译者ΓВ11用公钥进行认证BobAliceΓВ12用公钥进行认证A用自己的私钥进行加密Y=EKRa(X)B用A的公钥钥进行解密认证X=DKUa(Y)ΓВ13用公钥进行认证:问题？？问题1需要对整条消息加密，占用大量存储空间解决的方法：仅对消息的认证符加密问题2不能提供保密性如何解决？？ΓВ14公钥体制：保密和认证ΓВ15公钥密码体制的应用1加密/解密2数字签名3密钥交换算法RSA椭圆曲线Diffie-HellmanDSS是是是是是是否否是否是否ΓВ16对公钥密码体制的要求：1B产生一对密钥（KUb，KRb）在计算上是容易的2发送方A加密消息C=EKUb(M)在计算上是容易的3接收方B对密文解密M=DKRb(C)在计算上是容易的4攻击者从KUb计算出KRb在计算上不可行的5攻击者从KUb和C计算出M在计算上不可行的6附加条件（并非所有都满足）：加密解密顺序可交换：M=EKUb(DKRb(M))=DKUb(EKRb(M))ΓВ17只有两个算法被普遍接受1RSA2椭圆曲线就是要找一个单向陷门函数：不太容易ΓВ18单向陷门函数（1）Y=fk(X)容易(k和X已知)X=fk-1(Y)计算上不可行（k未知，Y已知）X=fk-1(Y)容易（k已知，Y已知）寻找合适的单向陷门函数是公钥密码体制应用关键！ΓВ19单向陷门函数（2）困难程度举例打碎/拼接、平方/开方、乘法/分解*单向函数存在否尚无严格的数学证明ΓВ20单向陷门函数（3）单向陷门函数如果知道某个陷门(秘诀)，即能容易恢复x（陷门即为私钥）举例魔方的置乱/恢复如果有那个口诀，就能很快恢复加密/解密ΓВ21RSA算法先从一个简单例子开始给出算法证明ΓВ22简单例子选中两个素数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请练习计算M1=Cd(modn)=?请练习d=77c=66ΓВ23RSA示例总结选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ΓВ24ΓВ25RSA算法作者1977年，R,S,ARonRivest~rivest/AdiShamir~shamir/LenAdleman基本参数分组密码算法基于整数乘法明/密文分组以及公/私钥被看作小于n的整数加/解密是模乘运算ΓВ26RSA算法总结：密钥产生找素数选取两个大的随机的素数p，q计算模n和Euler函数φ(n)n＝pqφ(n)=(p-1)(q-1)找ed≡1modφ(n)随机取一个数e(与φ(n)互素)，用扩展Euclid算法求d即可发布d保密，(d,n)是私钥KU发布(e,n)，这是公钥KR销毁p、qΓВ27RSA的正确性加密明文分组m做为整数须小于nc=memodn解密m=cdmodn证明依据Euler定理，在modn的含义下有：cd＝(me)d＝med＝mkφ(n)+1＝(mφ(n))km＝mΓВ28RSA考虑素数必须够大，否则对手可能很快分解n判定，采用Miller-Rabin概率测试方法假素数意味着加解密不能正确进行，故可放弃之强素数(p-1)/2和(q-1)/2应是素数选取较小的e和较大的de：3、65537快速计算x^y%z发布公钥证书中心CAΓВ29攻击RSA数学方法分解n得到p和q，就可以知道φ(n)，就可从e求得d直接求φ(n)不分解n，而直接求φ(n)，再求d直接求d不求φ(n)，直接求dΓВ30ΓВ31使用公钥传递会话密钥直接使用公钥算法－太慢对称算法一般几十兆字节/秒1024位RSA解密约100多次/秒(加密快10倍以上)只用来传递会话密钥(假设A已经有B的公钥KeB)A发起和B的通信A产生会话密钥Ks，并用KeB加密后传给BB能用自己的私钥KdB解开他人不会知道KsΓВ32对称算法vs.公钥算法安全性速度典型相差1000倍密钥管理对称算法需要额外安全信道公钥证书中心混合密码体制公钥算法用于签名和认证用公钥算法传输会话密钥用会话密钥/对称算法加密批量(bulk)数据ΓВ33作业：用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能够求出吗？