欢迎来到天天文库
浏览记录
ID:37789331
大小:615.00 KB
页数:40页
时间:2019-05-31
《《公钥密码体制》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、公钥密码学1公钥密码学公钥密码学思想RSA算法公钥的应用2密码体制产生俄罗斯人邮寄盒子的故事3公钥密码学的发展是整个密码学发展历史中最伟大的一次革命。公钥密码体制公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥,在消息的保密性、密钥分配和认证领域有重要意义。4密钥分配问题:如果密钥被偷,设计再好的密码体制都没有用传统密码中的两个问题数字签名问题:能否设计一种方法确保数字签名出自某个特定的人,并且各方无异议?51976年Diffie和Hellman针对上述问题提出了一种方法,它是密码学的一次革命密码学革命6公钥密码体制介绍7是密码学一次伟大的革命1976年,Diffi
2、e和Hellman在“密码学新方向”一文中提出。使用两个密钥:公开密钥、私有密钥加解密的非对称性利用数论的方法是对对称密码的重要补充8仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。公钥密码体制特点两个密钥中的任何一个可以用来加密,另一个用来解密。有6个组成部分:明文、加密算法、公钥、私钥、密文、解密算法9用公钥进行加密2Alice产生一对密钥,用于加密和解密3Alice将一个密钥公开,另一个密钥私有BobAlice1Bob要发送消息给Alice4Bob用Alice的公钥对消息加密,发送给Alice。只有Alice能解密10用公钥进行认证BobAlice11用公钥进行
3、认证:问题??问题1需要对整条消息加密,占用大量存储空间解决的方法:仅对消息的认证符加密问题2不能提供保密性如何解决??12公钥密码体制的种类1加密/解密2数字签名3密钥交换算法RSA椭圆曲线Diffie-HellmanDSS是是是是是是否否是否是否13对公钥密码体制的要求:1B产生一对密钥(Kpb,Ksb)在计算上是容易的2发送方A加密消息C=EKpb(M)在计算上是容易的3接收方B对密文解密M=DKsb(C)在计算上是容易的4攻击者从Kpb计算出Ksb在计算上不可行的5攻击者从Kpb和C计算出M在计算上不可行的14只有两个算法被普遍接受1RSA2椭圆曲线就是要找一个单向陷门
4、函数:不太容易所谓单向陷门函数是这样的函数,即除非知道某种附加的信息,否则这样的函数在一个方向上容易计算,而在反方向上要计算是不可行的。15单向陷门函数(1)Y=fk(X)容易(k和X已知)X=fk-1(Y)计算上不可行(k未知,Y已知)X=fk-1(Y)容易(k已知,Y已知)寻找合适的单向陷门函数是公钥密码体制应用的关键!16单向陷门函数(2)困难程度举例打碎/拼接、平方/开方、乘法/分解*单向函数存在否尚无严格的数学证明17单向陷门函数(3)单向陷门函数如果知道某个陷门(秘诀),即能容易恢复x(陷门即为私钥)举例魔方的置乱/恢复如果有那个口诀,就能很快恢复1819RSA算法
5、先从一个简单例子开始给出算法证明201.素数:素数是一个比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
6、和5倍数的数,即除掉{3,5,6,9,10,12}。21补充一些数学知识同余a≡bmodmB≡modma≡cmodm22补充一些数学知识欧拉函数不超过n,且与n互素的正整数个数,Ф(2)=1。推论:任何自然数都可以表示为素数米的乘积。6=2*3Ф(p)=p-123RSA加密算法实现过程(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(
7、n))(保密d,解密密钥,陷门信息)。(5)将明文x(其值的范围在0到n-1之间)按模为n自乘e次幂以完成加密操作,从而产生密文y(其值也在0到r-1范围内)y=xe(modn)。将密文y按模为r自乘d次幂,完成解密操作x=yd(modn)=xedmodn=x。24简单例子选中两个素数p=7,q=17n=pq=φ(n)=请练习任务:对明文M=19加密n=pq=119φ(n)=(p-1)(q-1)=6×16=96选取整数1
此文档下载收益归作者所有