第6章其它公钥密码体制6.1背包公密钥系统6.2群论中有关概念和结果6.3离散对数公钥密码体制6.4离散对数问题的算法6.5概率公钥体制6.6关于Fq上的椭圆曲线6.7E(Fq)中密码体制与明文嵌入方法6.8有限域Fp上圆锥曲线的公钥密码系统6.9双密钥公开钥密码体制6.10公钥密码系统的应用6.1背包密码体制背包问题已知一长度为b的背包,及厚度分别为a1,a2,…,an的n个物品,假定这些物品的半径和背包相同,要求从这n个物品中选取若干个物品正好装满这背包.这问题导致求xi=0或1,i=1,2,…,n,使其满足a1x1+a2x2+…+anxn=b,其中a1,a2,…,an和b都是正整数.设A=(a1,a2,…,an)是由n个不同的正整数构成的n元组,s是另一已知的正整数。背包问题就是从A中求出所有的ai,使其和等于s。其中A称为背包向量,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。原则上讲,通过检查A的所有子集,总可找出问题的解(如果有解的话)。本例A的子集共有210=1024个(包括空集)。然而如果A中元素个数n很大,子集个数2n将非常大。如A中有300个元素,A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法,因此背包问题是NPC问题。由背包问题构造公钥密码体制同样是要构造一个单向函数f,将x(1≤x≤2n-1)写成长为n的二元表示0…001,0…010,0…011,…,1…111,f(x)定义为A中所有ai的和,其中x的二元表示的第i位为1,即f(1)=f(0…001)=anf(2)=f(0…010)=an-1f(3)=f(0…011)=an-1+an…f(2n-1)=f(1…111)=a1+a2+…+an上例中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,f(44)=2629,f(648)=819。由f的定义可见,已知x很容易求f(x),但已知f(x)求x就是要解背包问题。当然在实际应用中,n不能太小,比如说,至少为200。用f对明文消息m加密时,首先将m写成二元表示,再将其分成长为n的分组(最后一个分组不够长的话,可用短块处理方法处理),然后求每一分组的函数值,以函数值作为密文分组。例如,明文消息是英文文本,则可将每个字母用其在字母表中的序号表示,再将该序号转换为二进制形式(5位即可).背包向量取a=(28,32,11,8,71,51,43),设待加密的明文是m=0100101。所以c=32+71+43=146,即得密文c=146.为使接收方能够解密,就需找出单向函数f(x)的陷门。为此需引入一种特殊类型的背包向量。定义背包向量A=(a1,a2,…,an)称为超递增的,如果112,,jjiiaajn超递增背包向量对应的背包问题很容易通过以下算法求解。已知s为背包容积,对A从右向左检查每一元素,以确定是否在解中。若s≥an,则an在解中,令xn=1;若san,则an不在解中,令xn=0。下面令对an-1重复上述过程,一直下去,直到检查出a1是否在解中。检查结束后得x=(x1x2…xn),Bx=(x1x2…xn)T。,,nnnssassasa然而,敌手如果也知道超递增背包向量,同样也很容易解密。为此可用模乘对A进行伪装,模乘的模数m和乘数w皆取为常量,满足m∑ai,gcd(w,m)=1,即w在模m下有乘法逆元。设bi≡w·aimodm,i=1,2,…,n得一新的背包向量B=(b1,b2,…,bn),记为B≡w·Amodm,用户以B作为自己的公开钥。例6.1A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量,取m=1590,w=43,gcd(43,1590)=1,得B=(43,129,215,473,903,302,561,1165,697,1523)。在得到B后,对明文分组x=(x1x2…xn)的加密运算为c=f(x)=B·Bx≡w·A·Bxmodm对单向函数f(x),w、w-1和m可作为其秘密的陷门信息,即解密密钥。解密时首先由s≡w-1cmodm,求出s作为超递增背包向量A的容积,再解背包问题即得x=(x1x2…xn)。这是因为w-1cmodm≡w-1wABxmodm≡ABxmodm,而由m∑ai,知ABxm,所以m-1cmodm=ABx,是惟一的。例6.2接例6.1,A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量,m=1590,w=43,得w-1≡37mod1590,设用户收到的密文是(2942,3584,903,3326,215,2817,2629,819),由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)。取s=734,由734701,得x10=1;令s=734-701=33,由33349,得x9=0;重复该过程得第一个明文分组是1001100001,它对应的英文文本是tb;类似地得其他明文分组.背包密码体制是Diffie和Hellman1976年提出公钥密码体制的设想后的第一个公钥密码体制,由Merkle和Hellman1978年提出。然而又过了两年该体制即被破译,破译的基本思想是不必找出正确的模数m和乘数w(即陷门信息),只须找出任意模数m′和乘数w′,使得用m′和w′去乘公开的背包向量B时,能够产生超递增的背包向量即可。6.2群论中有关概念和结果定义6.1一个非空集合G对于一个叫乘法的代数运算来说为一个群,假如(1)G对于乘法封闭;(2)结合律成立;(3)G里至少存在一个左单位元e,对任意a属于G,有ea=a;(4)对任意a属于G,G里至少存在一个左逆元a-1,有aa-1=e.定义6.2:有限群、无限群、交换群、循环群;群的阶:一个有限群的元的个数。定义6.3G中元素g的阶为的最小正整数m的值.定理6.1假设G是一个阶为n的乘法群,G中元素g的阶整除n.定理6.2如果p是素数,则是一个循环群.定义6.4如果p是素数,g是中阶为p-1的元,则称g为模p的本原元或生成元.1mgpp一般地,如果a的阶m等于φ(n),则称a为n的本原根。如果a是n的本原根,则a,a2,…,aφ(n)在modn下互不相同且都与n互素。特别地,如果a是素数p的本原根,则a,a2,…,ap-1在modp下都不相同。例如:n=9,则φ(n)=6,考虑2在mod9下的幂21mod9≡2,22mod9≡423mod9≡8,24mod9≡7,25mod9≡5,26mod9≡1。即2的阶为φ(9),所以2为9的本原根。例如:n=19,a=3在mod19下的幂分别为3,9,8,5,15,7,2,6,18,16,10,11,14,4,12,17,13,1。即3的阶为18=φ(19),所以3为19的本原根。本原根不惟一。可验证除3外,19的本原根还有2,10,13,14,15。注意并非所有的整数都有本原根,只有以下形式的整数才有本原根:2,4,pα,2pα其中p为奇素数。离散对数设p是素数,a是p的本原根,即a1,a2,…,ap-1在modp下产生1到p-1b∈{1,…,p-1},有惟一的i∈{1,…,p-1}使得b≡aimodp。称i为模p下以a为底b的离散对数,记为i≡logab(modp)。当a、p、i已知时,用平方和乘法可比较容易地求出b,但如果已知a、b和p,求i则非常困难。目前已知的最快的求离散对数算法其时间复杂度为:所以当p很大时,该算法也是不可行的。2133explnlnlnOpp6.3ElGamal加密系统ElGamal的安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法如下:①选择一个素数p,两个随机数g和x,要求g是模p的本原元,0xp②计算y=gx(modp),则其公钥为y,g和p。私钥是x。g和p可由一组用户共享。ElGamal用于加密假定被加密信息为M,首先选择一个随机数k,k小于p-1的非负整数,计算a=gk(modp)b=ykM(modp)(a,b)为密文,是明文的两倍长。解密时计算M=b/ax(modp)ElGamal用于数字签名ElGamal主要用于数字签名。假定被签信息为M,首先选择一个随机数k,k与p-1互质,计算a=gk(modp),再用扩展Euclidean算法对下面方程求解b:b=(M-xa)/k(modp-1)签名就是(a,b)。随机数k须丢弃。验证时要验证下式:ya*ab(modp)=gM(modp)同时一定要检验是否满足1=ap。否则签名容易伪造。D-H体制建立在DLP(discretelogarithmproblem)上。参数:T={g,p}(p是素数)私钥:ab公钥:gamodp=KA;gbmodp=KB在A方:(gb)amodp=gbamodp=key在B方:(ga)bmodp=gabmodp=key在C方:(ga)(gb)=ga+bkey6.4离散对数问题的算法首先回忆一下一般对数的概念,指数函数y=ax(a0,a≠1)的逆函数称为以a为底x的对数,记为y=logax。对数函数有以下性质:loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。设p是一素数,a是p的本原根,则a,a2,…,ap-1产生出1到p-1之间的所有值,且每一值只出现一次。因此对任意b∈{1,…,p-1},都存在惟一的i(1≤i≤p-1),使得b≡aimodp。称i为模p下以a为底b的离散对数,记为i=logab。离散对数有以下性质:①loga1=0。②logaa=1。分别由以下关系得出:a0modp=1modp=1,a1modp=a。以上假定模数p是素数,对于非素数也有类似的结论。一.Shanks时空存储法记,Shanks算法描述如下:1.计算2.用第二个坐标来排序m个有序对1pm.,10),(modjmjpamj;得到表1)),(mod,(Lpajmj3.计算4.用第二个坐标来排序m个有序对;,10),(modimipbai;得到表2)),(mod,(Lpbaii5.寻找一对6.于是有21),(),(LyiLyj和一对)).1(mod(logpimjba例6.5设p=809,求解:因为所以首先计算有序对525log3,29808m.99)809(mod3)809(mod29ma;得到表1,280)),809(mod99,(Ljjj(0,1),(1,99),(2,93),(3,308),(4,559),(5,329),(6,211),(7,664),(8,207),(9,268),(10,644),(11,654),(12,26),(13,147),(14,800),(15,727),(16,781),(17,464),(18,632),(19,275),(20,528),(21,496),(22,564),(23,15),(24,676),(25,586),(26,575),(27,295),(28,81).第二个表包含有序对:280)),809(mod3525,(