现代密码学第七讲：公钥密码学

1公钥密码（一）《现代密码学》第七章上讲内容回顾单向函数Hash函数的定义MD5算法SHA-256算法SHA-512和SHA-384算法消息鉴别码简介CBC-MAC算法HMAC算法3本章主要内容公钥密码体制的提出及分类公钥密码体制的基本概念单向陷门函数的概念设计公钥加密算法--背包密码体制RSA算法及攻击方法ElGmal算法及椭圆曲线密码体制密钥分配：加密者指定一个密钥后，必须得想方设法把密钥分发出去给解密者，同时还得小心翼翼确保密钥不被泄露。这是对称密码算法固有的一个矛盾，如何解决呢？对称密码进行密钥分配的要求：已经共享一个密钥：利用密钥分配中心：第一个密钥如何获得和KDC之间的密钥如何获得公钥密码体制的提出密钥管理：在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是n*（n-1）/2无签名功能当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。公钥密码体制的提出6公钥加密体制的原理邮箱的例子任何人可以向邮箱投举报信用户(审计人员)才能打开邮箱，读信的内容7公钥加密模型公钥加密体制的原理密钥分配8参数生成过程：1）要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥.2）端系统B将加密密钥（图中的PKB）予以公开，另一密钥被保密(图中的SKB).公钥加密体制的原理9公钥加密体制的原理参数生成需满足的要求：公开密钥(public-key),可以被任何人知道,用于加密或验证签名；私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名；由私钥及公开参数容易计算出公开密钥；由公钥及公开参数推导私钥是困难的；10加解密过程：1)A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKB[m],其中c是密文，E是加密算法.2)B收到密文c后，用自己的秘密钥SKB解密，表示为m=DSKB[c]，其中D是解密算法.公钥密码体制的原理11PublicKeyEstablishmentSchemes(PKES)用于交换秘密信息常用于对称加密算法的密钥分配PublicKeyEncryption(PKE)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS一些公钥加密方案也是数字签名方案SignatureSchemes(SS)用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名公钥密码体制的分类12公钥密码体制的发展历史1976年Diffie和Hellman在《密码学的新方向》中首次公开提出了非对称密码算法的思想，但是没有实现加密方案，只给出一个密钥协商协议；1978年Rivest,Shamir和Adleman提出应用广泛的RSA算法；1984年Shamir提出基于身份的密码体制，没有实现加密体制，只给出一个基于身份的数字签名算法2001年Boneh,Franklin和Cocks分别独立提出基于身份的加密算法2003年Al-Riyami提出的无证书的密码体制公钥密码体制的发展历史Diffie和Hellman公钥密码体制的发展历史RonaldRivest,AdiShamir,andLenAdleman15基本概念：公钥密码体制也称为双钥密码体制/非对称密码体制；算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密.利用公开密钥（及公开参数）推导私有密钥困难。公钥加密算法的特点16公钥加密体制框图公钥加密算法的特点发送者接收者信源分析者加密解密无噪信道安全信道MMMCKK’密钥源无噪信道17加解密算法需满足要求：加、解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)]这一条虽然非常有用，但不是对所有的算法都作要求.加解密速度比对称算法慢，因此公钥密码体制目前主要用于密钥管理和数字签字.类似于对称算法,穷搜索在理论上是能够破解公钥密码.实际上,密钥足够长(512bits)保证计算安全.安全性依赖于足够大的困难性差别，如NP和P问题（利用公钥及公开参数加密明文容易计算；利用私钥及公开参数解密密文容易计算；只利用公钥解密密文困难）；公钥加密算法的特点18定义单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的.一个函数是单向陷门函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成.单向陷门函数19单向陷门函数是一族可逆函数fk，满足①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、903、561、1165}.背包密码体制21原则上讲，通过检查A的所有子集，总可找出问题的解（如果有解的话）.上例中，A的子集共有210=1024个（包括空集）.如果A中元素个数n很大，子集个数2n将非常大,且寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NP问题.只要n足够大，那么，计算不可行.背包密码体制背包密码体制背包问题可以构造一个单向函数f.将x(1≤x≤2n-1)写成长为n的二元表示:则，f(x)定义为.上例中f(364)=f(0101101100)=129+473+903+561+1165=3231，类似地可求出:f(609)=2942,f(686)=3584,f(32)=903,f(46)=3326,f(128)=215,f(261)=2817.12(,,,),{0,1},1niXxxxxin1()niiifxAXxaf的定义可见：已知x很容易求f(x)，但已知f(x)求x就是要解背包问题，当n较大时是计算不可行的.在实际应用中，n不能太小，至少为200.23若用f充当加密函数对明文消息m加密:首先将m写成二元表示，再将其分成长为n的分组；然后求每一分组的函数值，以函数值(背包容积)作为密文分组.背包密码体制24例.背包向量仍取上例中的A，设待加密的明文是SAUNAANDHEALTH.因为A长为10，所以应将明文分成长为10比特（即两个明文字母）的分组SA，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,…,an)中的元素满足下列性质，则称其为超递增的.112,,jjiiaajn背包密码体制怎样解密？26超递增背包向量对应的背包问题存在多项式时间解法.解法：已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中:1)若s≥an，则an在解中，令xn=1；若san，则an不在解中，令xn=0.然后令2)对an-1重复上述过程，一直下去，直到检查出a1是否在解中.3)检查结束后得解x=(x1x2…xn).,,nnnssassasa背包密码体制若XA=S，则背包问题的解为X；否则原背包问题无解27为此需要对超递增背包向量A进行伪装，使攻击者看到的只是一般背包向量A’，接收者知到超递增背包向量A.方法一：用模乘和位置置换函数伪装.模数k和乘数t皆取常量，满足k∑ai，且gcd(t,k)=1，即t在模k下有乘法逆元.bi≡t·aimodk,i=1,2,…,n.得新的背包向量B=(b1,b2,…,bn)，记为B≡t·Amodk.用户以B作为自己的公开密钥,t、t-1和k可作为其秘密的陷门信息，即解密密钥.背包密码体制利用超递增背包函数作加密变换，明文接收者可以在多项式时间解密，但是敌手如果也知道超递增背包向量，同样也很容易解密.28例：A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量.取k=1590，t=43，满足gcd(43,1590)=1.计算得B=(43,129,215,473,903,302,561,1165,697,1523).背包密码体制29背包密码体制加密运算对明文分组X=(x1x2…xn)的加密为c=f(x)=B·X≡t·A·Xmodk解密运算首先由s≡t-1cmodk，求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2…xn).因为t-1cmodk≡t-1tAXmodk≡AXmodk，而由k∑ai，知AXk，所以t-1cmodk=AX，是惟一的.30例：A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量.k=1590，t=43，得t-1≡37mod1590.用户收到的密文是(2942,3584,903,3326,215,2817,2629,819)，1)由37×2942≡734mod1590,37×3584≡638mod1590,37×903≡21mod1590,37×3326≡632mod1590,37×215≡5mod1590,37×2817≡879mod1590,37×2629≡283mod1590,37×819≡93mod1590,得(734,638,21,632,5,879,283,93).背包密码体制312)取s=734，由734701，得x10=1；令s=734-701=33，由33349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA；3)类似地得其他明文分组;4)解密结果为SAUNAANDHEALTH.背包密码体制32背包密码体制是继Diffie和Hellman1976年提出公钥密码体制设想后的第一个公钥密码算法.上述方案由Merkle和Hellman于1978年提出.两年后该体制即被破译，破译的基本思想是找出任意模数k′和乘数t’,使得用k’和t’去乘公开的背包向量B时，能够产生超递增的背包向量即可.背包密码体制本节要点小结公钥密码体制的提出及分类公钥密码体制的基本概念单向陷门函数的概念设计公钥加密算法--背包密码体制作业1设背包密码系统的超递增序列为(3,4,9,17,35)乘数t=19，模数k=73，1)求系统的公钥；2)写出对明文“goodnight”加解密的详细步骤.35THEEND！