第6章(其它公钥密码体制)1

第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的本原元或生成元.1mgpp一般地,如果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很大时，该算法也是不可行的。2133explnlnlnOpp6.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+bkey6.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个有序对1pm.,10),(modjmjpamj；得到表1)),(mod,(Lpajmj3.计算4.用第二个坐标来排序m个有序对;,10),(modimipbai；得到表2)),(mod,(Lpbaii5.寻找一对6.于是有21),(),(LyiLyj和一对)).1(mod(logpimjba例6.5设p=809,求解:因为所以首先计算有序对525log3,29808m.99)809(mod3)809(mod29ma；得到表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,(