搜索
ΓВ1公钥密码学ΓВ2公钥密码学公钥密码学思想RSA算法公钥的应用ΓВ3密码体制产生俄罗斯人邮寄盒子的故事ΓВ4公钥密码学的发展是整个密码学发展历史中最伟大的一次革命。公钥密码体制公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥，在消息的保密性、密钥分配和认证领域有重要意义。ΓВ5密钥分配问题：如果密钥被偷，设计再好的密码体制都没有用传统密码中的两个问题数字签名问题：能否设计一种方法确保数字签名出自某个特定的人，并且各方无异议？ΓВ61976年Diffie和Hellman针对上述问题提出了一种方法，它是密码学的一次革命密码学革命ΓВ7公钥密码体制介绍ΓВ8是密码学一次伟大的革命1976年，Diffie和Hellman在“密码学新方向”一文中提出。使用两个密钥：公开密钥、私有密钥加解密的非对称性利用数论的方法是对对称密码的重要补充ΓВ9仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。公钥密码体制特点两个密钥中的任何一个可以用来加密，另一个用来解密。有6个组成部分：明文、加密算法、公钥、私钥、密文、解密算法ΓВ10用公钥进行加密2Alice产生一对密钥，用于加密和解密3Alice将一个密钥公开，另一个密钥私有BobAlice1Bob要发送消息给Alice4Bob用Alice的公钥对消息加密，发送给Alice。只有Alice能解密ΓВ11用公钥进行认证BobAliceΓВ12用公钥进行认证:问题？？问题1需要对整条消息加密，占用大量存储空间解决的方法：仅对消息的认证符加密问题2不能提供保密性如何解决？？ΓВ13公钥密码体制的种类1加密/解密2数字签名3密钥交换算法RSA椭圆曲线Diffie-HellmanDSS是是是是是是否否是否是否ΓВ14对公钥密码体制的要求：1B产生一对密钥（Kpb，Ksb）在计算上是容易的2发送方A加密消息C=EKpb(M)在计算上是容易的3接收方B对密文解密M=DKsb(C)在计算上是容易的4攻击者从Kpb计算出Ksb在计算上不可行的5攻击者从Kpb和C计算出M在计算上不可行的ΓВ15只有两个算法被普遍接受1RSA2椭圆曲线就是要找一个单向陷门函数：不太容易所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在反方向上要计算是不可行的。ΓВ16单向陷门函数（1）Y=fk(X)容易(k和X已知)X=fk-1(Y)计算上不可行（k未知，Y已知）X=fk-1(Y)容易（k已知，Y已知）寻找合适的单向陷门函数是公钥密码体制应用的关键！ΓВ17单向陷门函数（2）困难程度举例–打碎/拼接、平方/开方、乘法/分解*单向函数存在否–尚无严格的数学证明ΓВ18单向陷门函数（3）单向陷门函数–如果知道某个陷门(秘诀)，即能容易恢复x–（陷门即为私钥）举例–魔方的置乱/恢复如果有那个口诀，就能很快恢复ΓВ19ΓВ20RSA算法先从一个简单例子开始给出算法证明ΓВ211.素数：素数是一个比1大，其因子只有1和它本身，没有其它数可以整除它的数。素数是无限的。例如，2，3，5，7……等。2.两个数互为素数：指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如，4和9，13和27等。用gcd（x,y）=1表示x和y互素。3.模运算：如A模N运算，它给出了A的余数，余数是从0到N-1的某个整数，这种运算称为模运算。4.Euler函数：设p=3,q=5,那么φ（15）=（3-1）*（5-1）=8，这8个模15的剩余类是：{1，2，4，7，8，11，13，14}，其中剩余类是在1至14中除掉是3和5倍数的数，即除掉｛3，5，6，9，10，12｝。ΓВ22补充一些数学知识同余a≡bmodmB≡modma≡cmodmΓВ23补充一些数学知识欧拉函数不超过n，且与n互素的正整数个数，Ф(2)=1。推论：任何自然数都可以表示为素数米的乘积。6=2*3Ф(p)=p-1ΓВ24RSA加密算法实现过程(1)取两个随机大素数p和q（保密）。(2)计算公开的模数n=pq（公开）。(3)计算秘密的欧拉函数（n）=（p-1）（q-1）（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道。(4)随机选取整数e，满足gcd（e,（n））=1（公开e，加密密钥）。计算d，满足de≡1（mod（n））（保密d，解密密钥，陷门信息）。(5)将明文x（其值的范围在0到n-1之间）按模为n自乘e次幂以完成加密操作，从而产生密文y（其值也在0到r-1范围内）y=xe（modn）。将密文y按模为r自乘d次幂，完成解密操作x=yd（modn）=xedmodn=x。ΓВ25简单例子选中两个素数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ΓВ26RSA示例总结选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ΓВ27RSA算法总结：密钥产生找素数–选取两个大的随机的素数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ΓВ28【例1】取两个素数p=11，q=13，p和q的乘积为r=p×q=143，算出秘密的欧拉函数（r）=（p-1）×（q-1）=120，再选取一个与（r）=120互质的数，例如e=7，作为公开密钥，e的选择不要求是素数，但不同的e的抗攻击性能力不一样，为安全起见要求选择为素数。对于这个e值，可以算出另一个值d=103，d是私有密钥，满足e×d=1mod（r），其实7×103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找解密密钥。120=7×17+11=120-7×17mod120=120-7×（-120+17）mod120=120+7×103mod120（r,e）=（143,7）这组数公开，即公钥，（r,d）=（143,103）这组数保密，为私钥ΓВ29设想需要发送信息x=85。利用（n,e）=（143,7）计算出加密值：y=xe（modn）=857mod143=123收到密文y=123后，利用（n,d）=（143,103）计算明文：x=yd（modn）=123103mod143=85加密信息x（二进制表示）时，首先把x分成等长数据块x1,x2,...,xi，块长s，其中2s≤n，s尽可能的大。对应的密文是：yi=xie（modn）解密时作如下计算：xi=yid（modn）ΓВ30RSA的正确性加密明文分组m做为整数须小于nc=memodn解密m=cdmodnΓВ31RSA考虑素数–必须够大，否则对手可能很快分解n–判定，采用Miller-Rabin概率测试方法假素数意味着加解密不能正确进行，故可放弃之–强素数(p-1)/2和(q-1)/2应是素数选取较小的e和较大的d–e：3、65537发布公钥–证书中心CAΓВ32攻击RSA数学方法分解n–得到p和q，就可以知道φ(n)，就可从e求得d直接求φ(n)–不分解n，而直接求φ(n)，再求d直接求d–不求φ(n)，直接求dΓВ33使用公钥传递会话密钥直接使用公钥算法－太慢只用来传递会话密钥–(假设A已经有B的公钥KeB)–A发起和B的通信–A产生会话密钥Ks，并用KeB加密后传给B–B能用自己的私钥KdB解开–他人不会知道KsΓВ34对称算法vs.公钥算法速度–典型相差1000倍密钥管理–对称算法需要额外安全信道–公钥证书中心混合密码体制–公钥算法用于签名和认证–用公钥算法传输会话密钥–用会话密钥/对称算法加密批量(bulk)数据ΓВ35作业：用RSA加密解密p=5,q=11,e=3,M=9如果：e=31,n=3599,d=?c=10,e=5,n=35,M能够求出吗？ΓВ36模幂运算的扩展如197405368125mod101怎么计算ΓВ37直接计算的问题1.缓冲区溢出缓冲区溢出的原理voidfuncton（char*str）{charbuffer[16]；strcpy（buffer，str）；}该程序的功能是通过strcpy函数把str中的字符串拷贝到数组buffer[16]中去，如果str的长度超过16就会造成数组buffer的溢出，使程序出错。ΓВ38(ab)modc=((amodc)*(amodc))modc当a=b时，(ab)modc==(amodc)2modcΓВ39计算abb=20+21+22+2Nab=a(20+21+22+2N)=[(amodc)(a2modc）….（anmodc）]modcΓВ408125mod11125=20+22+23+24+25+26序号6543210乘方8648328168884828对应的指数位1111101余数49354982取模数取模数