非对称加密算法的几个问题

非对称加密算法的几个问题

数字签名的本质是一种非对称加密。与普通加密算法的一个显著不同，密钥系统由一对不平等的密钥组成，称为密钥和密钥。加密和解密使用不同的钥匙,用公钥加密,再用私钥解密,反之亦然。非对称加密算法的难点在于构造一个恰当的函数,加密和解密都使用该函数,算法也完全相同,只是钥匙不同而已。设E为加密算法,Ke为加密密码,D为解密算法,Kd为解密密码,对于所有的明文M有:D(E(Μ,Κe),Κd)=Μ。(1)D(E(M,Ke),Kd)=M。(1)式(1)中的算法D和E必须都是高效的,而且在数学上不能由Ke很快求出Kd。然而寻找这样的函数并非易事。在密码理论的发展史中,尽管许多函数被提出,但经得起时间考验的却寥寥无几。其中最著名的有RSA算法,该算法是利用二个大素数相乘容易,而大数分解成二个素数乘积很难而实现加密;ElGamal密码是除了RSA密码之外最有代表性的公开密钥密码,它是建立在离散对数求解的困难之上的。有限的离散的循环群由于其特殊的性质使其可以用做非对称加密,例如其除幺元以外任何元素都可以作为生成元。如何构造这样一个循环的有限的阿贝尔群,这成为非对称加密算法的关键。1有限环组结构1.1利用同一直线,把同一点打造成形Weierstrass方程是一个如下的齐次方程y2z+a1xyz+a3yz2=x3+a2x2z+a4xz2+a6z2‚(2)y2z+a1xyz+a3yz2=x3+a2x2z+a4xz2+a6z2‚(2)当z=1时,式(2)变为平面曲线,也就是椭圆曲线,即y2+a1xy+a3y=x3+a2x2+a4x+a6。(3)y2+a1xy+a3y=x3+a2x2+a4x+a6。(3)为了使问题简化些,令:a1=0,a3=0,a2=0,则式(3)变为y2=x3+a4x+a6。(4)y2=x3+a4x+a6。(4)设有一直线y=kx+c。(5)y=kx+c。(5)由式(4)和(5)可得x3-k2x2+(a4-2kc)x+a6-c2=0。(6)x3−k2x2+(a4−2kc)x+a6−c2=0。(6)曲线(4)与直线(5)相交,多数情况下有3个点,设这三个点为P(x1,y1),Q(x2,y2),R(x3,y3)。显然可见,这3个点的横坐标x1,x2,x3为方程(6)的3个解,于是有(x-x1)(x-x2)(x-x3)=0。(7)(x−x1)(x−x2)(x−x3)=0。(7)展开后得x3-(x1+x2+x3)x2+(x1x2+x2x3+x1x3)x-x1-x2-x3=0。(8)x3−(x1+x2+x3)x2+(x1x2+x2x3+x1x3)x−x1−x2−x3=0。(8)式(6)与(8)为同一方程式,故对比它们的系数有k2=x1+x2+x3,(9)(a4-2kc)=x1x2+x2x3+x1x3,(10)c2-b=x1+x2+x3。(11)k2=x1+x2+x3,(9)(a4−2kc)=x1x2+x2x3+x1x3,(10)c2−b=x1+x2+x3。(11)式(9),(10),(11)为P,Q,R三点的横坐标的关系。用同样的方法,可以求得P,Q,R纵坐标的关系。注意,可以由P,Q,R中的其中的二点的坐标求出另外一个点的坐标,比如由P和Q求出R。k为直线的斜率,由(x1,y1)和(x2,y2)在直线上,显然有k=(y2-y1)/(x2-x1)。(12)由式(9)有x3=k2-x1-x2。(13)又因k=(y3-y1)/(x3-x1),于是有y3=k(x3-x1)+y1。(14)所以,可以由式(12)～(14),从P,Q,R中的任意二点求得第三点的坐标。1.2有限域gfn取一个素数n,构造一个有限域GF(n)。现研究式(4)在GF(n)上的解。于是,式(4)变为y2=x3+a4x+a6(modn),(15)式(15)中a4和a6也是有限域GF(n)中的元素。因式(2)为一齐次方程,故4a34与27a26不能互为逆元,即4a34+27a26≠0(modn)。利用式(15)在有限域GF(n)中的解构造一个代数系统G(E,+),设P(x,y)为式(15)的解,集合E由有序对P(x,y)所组成。为了构造该阿贝尔群,作如下定义。(1)解点的组成设幺元为e(x,y),其中的x和y均为无穷点,即e(∞,∞),幺元e同式(15)的所有的解点构成集合E。设无穷点e(∞,∞)为幺元,其有如下性质:e(∞‚∞)+e(∞‚∞)=e(∞‚∞),(16)p(x‚y)+e(∞‚∞)=e(∞‚∞),(17)e(∞‚∞)+p(x‚y)=e(∞‚∞)。(18)(2)x,-y为r的逆元对于式(15)任何解点r(x,y),由于式(15)是x轴对称的,故(x,-y)必定也是式(15)的解,故可以定义点r-1(x,-y)为r的逆元,即有r(x‚y)+r-1(x‚-y)=e(∞‚∞)。(19)(3)加r-1.x,y3型如上所设,P(x1,y1),Q(x2,y2),R(x3,y3)三点是式(15)位于同一直线上的三个解,现用这三个点定义加法运算“+”,该运算满足交换律及结合律,则Ρ(x1‚y1)+Q(x2‚y2)+R(x3‚y3)=e(∞‚∞)。(20)由于R(x3,y3)的逆元为R-1(x3,-y3),在式(20)二边加上R-1(x3,-y3),于是得出Ρ(x1‚y1)+Q(x2‚y2)=R-1(x3‚-y3)。(21)同理有Ρ(x1‚y1)+R(x3‚y3)=Q-1(x2‚-y2),(22)Q(x2‚y2)+R(x3‚y3)=Ρ-1(x1‚-y1)。(23)用式(21)来定义加法运算。设S(x,y)是R(x3,y3)的逆元,即x=x3,y=-y3,于是有S(x‚y)=Ρ(x1‚y1)+Q(x2‚y2)。(24)又因为P,Q,R在同一直线上,按照式(12),(13)与(14),可以由P和Q的坐标求出坐标(x,y)k=((y2-y1)/(x2-x1))(modn),(25)x=x3≡k2-x1-x2(modn),(26)y=-y3≡k(x1-x)-y1(modn)。(27)式(24)到(27)定义了曲线上离散解的加法运算,其几何意义为一条直线与曲线有三个交点,其中的二点相加等于另一点的对称点(即该点的逆元)。(4)有限域gfnΡ(x1‚y1)2=Ρ(x1‚y1)+Ρ(x1‚y1)。(28)如果按式(25)的方法,当x1=x2时,k=(y1-y2)/(x1-x2)=∞,显然无法求出S(x,y),所以要对与自己相加重新规定,同时又必须同上面定义的加法保持统一。假定直线y=kx+c在P(x1,y1)点与曲线(15)相切,k为该切线的斜率,则可假设直线y=kx+c与曲线也有3个交点,其中二个交点同为P,另一交点为R(x3,y3)。设R-1(x,y)为R的逆,这里x=x3,y=-y3,于是有Ρ(x1‚y1)+Ρ(x1‚y1)=S-1(x‚y)。(29)k的值为式(15)在P(x1,y1)点的导数,即k=(3x21+a4)/(2y1)。(30)又因为P(x1,y1),P(x1,y1),R(x3,y3)为式(6)的3个解,可以通过如上所述的比较系数法得出x=x3=k2-2x1,(31)y=-y3=k(x1-x)-y1,(32)式(31),(32)分别为P2的x,y坐标的取值。这样在有限域GF(n)中,代数系统G(E,+)是一个加法满足交换律、结合律、有幺元,每个元有逆元的有限阶的阿贝尔群。由有限域性质知该阿贝尔群G为一个循环群。2用户隐私信息加密由于群G(E,+)为一个有限循环群,所以集合E中的任何元素(无穷点e除外)都可以当作群G的生成元,从E中任取一个值B作为该群的生成元,并将B点当作基点。随机地任取一个自然数d(满足条件:0<d<n-1),作为一用户的加密的私钥。而用户的公钥Q为群G上的一个元,可以由下面的公式得到Q=dB。B和Q是公开的,而d为保密的。由d很容易求出Q,而由B和Q很难求出d。例如用户A,选择一个随机整数k,计算出C1=kB,C2=kQ,然后用户A用C2作为密码对数据进行加密,将加密的数据连同C1发送给用户B。C1是不能解密数据的,必须通过C1计算出C2才能解密,而用户B拥有密钥d,他可以通过密钥d和C1把C2求出dC1=d(kB)=k(dB)=kQ=C2。计算出C2,便可实现解密了。当n的值足够大时,可以证明,已知k和B,Q计算C1,C2比较容易,而由C1和C2计算k则比较困难,我们构造的有限循环群,是实现非对