《现代密码学第七讲公钥密码学》由会员分享，可在线阅读，更多相关《现代密码学第七讲公钥密码学（35页珍藏版）》请在金锄头文库上搜索。
1、1,公钥密码（一）,现代密码学第七章,上讲内容回顾,单向函数 Hash函数的定义 MD5算法 SHA-256算法 SHA-512和SHA-384算法 消息鉴别码简介 CBC-MAC算法 HMAC算法,3,本章主要内容,公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法-背包密码体制 RSA算法及攻击方法 ElGmal算法及椭圆曲线密码体制,密钥分配：加密者指定一个密钥后，必须得想方设法把密钥分发出去给解密者，同时还得小心翼翼确保密钥不被泄露。这是对称密码算法固有的一个矛盾，如何解决呢？ 对称密码进行密钥分配的要求： 已经共享一个密钥： 利用密钥分配中心：,第
2、一个密钥如何获得,和KDC之间的密钥如何获得,公钥密码体制的提出,密钥管理：在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是n（n-1）/2 无签名功能 当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。,公钥密码体制的提出,6,公钥加密体制的原理,邮箱的例子 任何人可以向邮箱投举报信 用户(审计人员)才能打开邮箱，读信的内容,7,公钥加密模型,公钥加密体制的原理,密钥分配,8,参数生成过程： 1） 要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PK
3、B是公开钥，SKB是秘密钥. 2）端系统B将加密密钥（图中的PKB）予以公开，另一密钥被保密 (图中的SKB).,公钥加密体制的原理,9,公钥加密体制的原理,参数生成需满足的要求： 公开密钥(public-key), 可以被任何人知道, 用于加密或验证签名； 私钥(private-key), 只能被消息的接收者或签名者知道,用于解密或签名； 由私钥及公开参数容易计算出公开密钥； 由公钥及公开参数推导私钥是困难的；,10,加解密过程： 1) A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKBm, 其中c是密文，E是加密算法. 2) B收到密文c后，用自己的秘密钥SKB解密，表示为m
4、=DSKBc，其中D是解密算法.,公钥密码体制的原理,11,Public Key Establishment Schemes (PKES) 用于交换秘密信息 常用于对称加密算法的密钥 Public Key Encryption (PKE) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案 Signature Schemes (SS) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名 任何人可以用公钥验证签名,公钥密码体制的分类,12,公钥密码体制的发展历史,1976年 Diffie和Hell
5、man 在密码学的新方向中首次公开提出了非对称密码算法的思想，但是没有实现加密方案，只给出一个密钥协商协议； 1978年 Rivest,Shamir和Adleman提出应用广泛的RSA算法； 1984年 Shamir提出基于身份的密码体制，没有实现加密体制，只给出一个基于身份的数字签名算法 2001年 Boneh,Franklin和Cocks分别独立提出基于身份的加密算法 2003年 Al-Riyami提出的无证书的密码体制,公钥密码体制的发展历史,Diffie和Hellman,公钥密码体制的发展历史,Ronald Rivest, Adi Shamir, and Len Adleman,15,
6、基本概念： 公钥密码体制也称为双钥密码体制/非对称密码体制； 算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密. 利用公开密钥（及公开参数）推导私有密钥困难。,公钥加密算法的特点,16,公钥加密体制框图,公钥加密算法的特点,17,加解密算法需满足要求： 加、解密次序可换，即 EPKBDSKB(m)=DSKBEPKB(m) 这一条虽然非常有用，但不是对所有的算法都作要求. 加解密速度比对称算法慢，因此公钥密码体制目前主要用于密钥管理和数字签字. 类似于对称算法,
7、穷搜索在理论上是能够破解公钥密码. 实际上,密钥足够长 (512bits)保证计算安全. 安全性依赖于足够大的困难性差别，如NP和P问题（利用公钥及公开参数加密明文容易计算；利用私钥及公开参数解密密文容易计算；只利用公钥解密密文困难）；,公钥加密算法的特点,18,定义 单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像xX，且由x易于计算它的像y，由y计算它的原像x是不可行的. 一个函数是单向陷门函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成.,单向陷门函数,19,单向陷门函数是一族可逆函数fk，满
8、足 Y=fk(X)易于计算（当k和X已知时）. X=f-1k(Y)易于计算（当k和Y已知时）. X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）. 研究公钥密码算法就是要找出合适的陷门单向函数,单向陷门函数,20,背包问题：设A=(a1,a2,an)是由n个不同的正整数构成的背包向量，s是背包容积.求A的子集A，使子集中的元素ai的和恰好等于s. 例. A=（43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523），s=3231. 由于 3231=129+473+903+561+1165. 所以从A中找出的满足要求的子集合是129、473、9
9、03、561、1165.,背包密码体制,21,原则上讲，通过检查A的所有子集，总可找出问题的解（如果有解的话）. 上例中，A的子集共有210=1024个（包括空集）. 如果A中元素个数n很大，子集个数2n将非常大, 且寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NP问题. 只要n足够大，那么，计算不可行.,背包密码体制,背包密码体制,背包问题可以构造一个单向函数f. 将x(1x2n-1)写成长为n的二元表示: 则，f(x)定义为 . 上例中 f(364) = f(0101101100)=129+473+903+561+1165 = 3231， 类似地可求出: f(609)=29
10、42, f(686)=3584, f(32)=903, f(46)=3326, f(128)=215, f(261)=2817.,f的定义可见： 已知x很容易求f(x)，但已知f(x)求x就是要解背包问题，当n较大时是计算不可行的. 在实际应用中，n不能太小，至少为200.,23,若用f充当加密函数对明文消息m加密: 首先将m写成二元表示，再将其分成长为n的分组； 然后求每一分组的函数值，以函数值(背包容积)作为密文分组.,背包密码体制,24,例. 背包向量仍取上例中的A，设待加密的明文是SAUNA AND HEALTH. 因为A长为10，所以应将明文分成长为10比特（即两个明文字母）的分组S
11、A，UN，A ，AN，D ，HE，AL，TH, 其相应的二元序列为 1001100001，1010101110，0000100000，0000101110，0010000000，0100000101，0000101100，1010001000. 分别对以上二元序列作用于函数f，得密文:（2942，3584，903，3326，215，2817，2629，819）.,背包密码体制,若明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，再将该序号转换为二进制形式（5位即可），其中符号 表示空格,25,构造单向陷门函数f(x)，为此引入一种特殊类型的背包向量. 定义 背包向量A=(a1,a2,
12、an)中的元素满足下列性质， 则称其为超递增的.,背包密码体制,怎样解密？,26,超递增背包向量对应的背包问题存在多项式时间解法. 解法：已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中: 1) 若san，则an在解中，令xn=1；若san，则an不在解中，令xn=0. 然后令 2) 对an-1重复上述过程，一直下去，直到检查出a1是否在解中. 3) 检查结束后得解 x=(x1x2xn).,背包密码体制,若XA=S，则背包问题的解为X；否则原背包问题无解,27,为此需要对超递增背包向量A进行伪装，使攻击者看到的只是一般背包向量A，接收者知到超递增背包向量A. 方法一：用模乘和位置置
13、换函数伪装. 模数k和乘数t皆取常量，满足kai，且gcd(t,k)=1，即t在模k下有乘法逆元. bitai mod k, i=1,2,n. 得新的背包向量B=(b1,b2,bn)，记为 BtA mod k. 用户以B作为自己的公开密钥, t、t-1和k可作为其秘密的陷门信息，即解密密钥.,背包密码体制,利用超递增背包函数作加密变换， 明文接收者可以在多项式时间解密， 但是敌手如果也知道超递增背包向量， 同样也很容易解密.,28,例：A=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是一超递增背包向量. 取k=1590，t=43， 满足gcd(43, 159
14、0)=1. 计算得 B=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523).,背包密码体制,29,背包密码体制,加密运算 对明文分组X=(x1x2xn)的加密为 c=f(x)=BXtAX mod k 解密运算 首先由st-1 c mod k，求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2xn). 因为t-1 c mod kt-1tAX mod kAX mod k，而由kai，知AXk，所以t-1c mod k=AX，是惟一的.,30,例： A=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是
15、一超递增背包向量. k=1590，t=43，得t-1 37 mod 1590. 用户收到的密文是(2942, 3584, 903, 3326, 215, 2817, 2629, 819) ， 1) 由 372942734 mod 1590, 373584638 mod 1590, 3790321 mod 1590, 373326632 mod 1590, 37215 5 mod 1590, 372817879 mod 1590, 372629283 mod 1590, 3781993 mod 1590, 得(734, 638, 21, 632, 5, 879, 283, 93).,背包密码体制
16、,31,2) 取s=734，由734701，得x10=1；令s=734-701=33，由33349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA； 3) 类似地得其他明文分组; 4) 解密结果为SAUNA AND HEALTH.,背包密码体制,32,背包密码体制是继Diffie和Hellman 1976年提出公钥密码体制设想后的第一个公钥密码算法. 上述方案由Merkle和Hellman 于1978年提出. 两年后该体制即被破译，破译的基本思想是找出任意模数k和乘数t, 使得用k和t去乘公开的背包向量B时，能够产生超递增的背包向量即可.,背包密码体制,本节要点小结,公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法-背包密码体制,作业,1 设背包密码系统的超递增序列为(3, 4, 9, 17, 35)乘数t=19，模数k=73， 1) 求系统的公钥； 2) 写出对明文“good night”加解密的详细步骤.,35,TH
