橢圓曲線加法運(yùn)算的數(shù)據(jù)仿真

劉增芳，韋性佳，蘆殿軍

(青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，青海 西寧，810008)

隨著信息技術(shù)的高速發(fā)展，信息安全已經(jīng)成為全社會(huì)所面臨的重大挑戰(zhàn)，橢圓曲線密碼體制(Elliptic curve cryptosystem，簡稱ECC)已經(jīng)廣泛的應(yīng)用于各類密碼學(xué)方案的構(gòu)造之中，作為保障信息安全性的核心工具之一，具有十分重要的研究價(jià)值。1985年Neal Koblitz和Victor Miller首次在密碼學(xué)的研究之中啟用了橢圓曲線公鑰密碼體制[1-2]。經(jīng)過研究發(fā)現(xiàn)，ECC具有如下兩方面優(yōu)勢：1)密鑰具有較小的存儲(chǔ)空間與運(yùn)算量，這就極大的簡化了密碼體制的運(yùn)算成本，具有更高的實(shí)用性。2)可定義群之間基于Weil對(duì)或是Tate對(duì)的雙線性映射[3-4]，基于此ECC已成為理想的公鑰密碼體制之一。3)橢圓曲線的加法運(yùn)算，在很大程度上加快了密碼體制的運(yùn)算速度。目前對(duì)于ECC的硬件實(shí)現(xiàn)已成為許多學(xué)者研究的重要課題之一。2013年，宋春玉[5]利用matlab軟件，編譯了橢圓曲線密碼系統(tǒng)的基本運(yùn)算與原理，并且第一次將其應(yīng)用于漢字的加密和解密之中。2016年，謝天藝等人[6]利用ECC硬件加速器實(shí)現(xiàn)了硬件可配的點(diǎn)乘和素?cái)?shù)檢測。同年，王千喜等人[7]對(duì)于ECC算法的硬件的實(shí)現(xiàn)進(jìn)行了優(yōu)化，使得在主時(shí)鐘為300M、密鑰長度是160bit的條件下，ECC加密解密的效率提升至大約5k/s，這極大的提高了目前ECC加密和解密的速度。

文中討論的是基于有限域上橢圓曲線的群中加法運(yùn)算的實(shí)現(xiàn)方案。橢圓曲線加法運(yùn)算的數(shù)據(jù)模擬并不是一件簡單的事情，需要做如下幾項(xiàng)工作：第一，判斷兩數(shù)是否互素。這個(gè)工作是為下一步模逆運(yùn)算做準(zhǔn)備的，因?yàn)橹挥袃蓚€(gè)互素的數(shù)才可求逆，否則不成立。第二，實(shí)現(xiàn)有限域上的模逆運(yùn)算，這也是橢圓曲線加法群運(yùn)算中的關(guān)鍵性算法。第三，對(duì)有限域上的橢圓曲線利用Euler準(zhǔn)則測試給定一個(gè)x對(duì)應(yīng)的y值是否是一個(gè)二次剩余，如果是二次剩余，文中將給出相應(yīng)的點(diǎn)，并輸出點(diǎn)的個(gè)數(shù)。第四，實(shí)現(xiàn)橢圓曲線加法運(yùn)算。

1 預(yù)備知識(shí)

1.1 有限域Fp上的橢圓曲線

定義1 令p>3是一個(gè)奇素?cái)?shù)。有限域Fp上的橢圓曲線E可以定義為等式[8]

y2=x3+ax+b，a,b∈Fp

并且4a3+27b2≠0(modp)，集合E(Fp)包括所有的點(diǎn)(x,y)，x∈Fp，y∈Fp，且點(diǎn)坐標(biāo)(x,y)滿足等式y(tǒng)2=x3+ax+b,集合E(Fp)還有一個(gè)特殊的點(diǎn)稱作無窮遠(yuǎn)點(diǎn)。

1.2 Euclidean算法

給出兩數(shù)a,b∈Z+，利用Euclidean算法求兩數(shù)的最大公因子。令r0=a,r1=b，ri(i=2,…,m)：ri/ri+1所得余數(shù)，qj(j=1,2,…,m)：ri/ri+1所得商。具體算法執(zhí)行如下(即輾轉(zhuǎn)相除法)：

容易看到

gcd(r0,r1)=gcd(r1,r2)=…=gcd(rm-1,rm)=rm

因此，可以得到gcd(a,b)=rm。

擴(kuò)展的Euclidean算法，它以兩個(gè)整數(shù)a和b作為輸入，計(jì)算出整數(shù)r,s和t使得r=gcd(a,b)且sa+tb=r。若r=1即gcd(a,b)=1，則有b-1moda=tmoda。

1.3 二次剩余

設(shè)E是Zp上的橢圓曲線y2=x3+ax+b。首先確定E的點(diǎn)。這可以通過對(duì)每個(gè)x∈Zp，計(jì)算x3+ax+b(modp)解方程

y2≡x3+ax+b(modp)

求y。對(duì)于給定的x，可用Euler準(zhǔn)則測試是否z=x3+ax+b是一個(gè)二次剩余。對(duì)于素?cái)?shù)p≡3(mod4)，利用公式z(p-1)/2modp判斷z是否為一個(gè)二次剩余。若此值等于1，則說明z是一個(gè)二次剩余，否則z不是一個(gè)二次剩余。二次剩余z的平方根是±z(p+1)/4modp。

1.4 橢圓曲線的群的加法運(yùn)算

橢圓曲線上的加法運(yùn)算定義如下(這里的所有運(yùn)算都在Zp中)。假設(shè)P=(x1,y1)并且Q=(x2,y2)是E上的點(diǎn)。

1)如果x1=x2且y1=-y2，則P+Q=O(無窮遠(yuǎn)點(diǎn))

2)否則P+Q=(x3,y3)，其中

并且對(duì)λ有如下定義：

3)最后，對(duì)于所有的P∈E，有P+O=O+P=P

需要注意的是，Zp上的橢圓曲線沒有像實(shí)數(shù)域上的橢圓曲線那樣直觀的幾何解釋。然而，定義加法運(yùn)算亦可用同樣的公式，(E,+)仍是一個(gè)阿貝爾群。

2 模素?cái)?shù)的橢圓曲線加法

2.1 判斷兩數(shù)互素

利用Euclidean算法計(jì)算兩數(shù)的最大公約數(shù)，若最大公約數(shù)為1，則說明兩數(shù)互素。C語言程序如下：

#include

void main()

{int a,b,m;printf("please input two number:");

{scanf("%d%d",&a,&b);if(a==0‖b==0)

{printf("wrong input ");}

else{m=a%b;while(m!=0)

{ a=b;b=m;m=a%b;}

printf("%d ",b);}}}

2.2 模逆運(yùn)算

設(shè)對(duì)于任意的a,b∈Zn，且gcd(a,b)=1。因?yàn)槟Ｄ孢\(yùn)算所得到的值不唯一，文中取其最小值，利用擴(kuò)展Euclidean算法可實(shí)現(xiàn)模逆運(yùn)算?；舅枷肴缦?分情況論述)：

1)當(dāng)b>0時(shí)，計(jì)算模數(shù)a的正整數(shù)倍：1×a,2×a,3×a,…,n×a，將所得到的模數(shù)a的正整數(shù)倍加1，即1×a+1,2×a+1,3×a+1,…,n×a+1 。采用試除法，將模數(shù)a的倍數(shù)加1的每一項(xiàng)都除以b，直到余數(shù)為0即正好整除，則所得到的商即為b-1moda的值。

2)當(dāng)b<0時(shí)，計(jì)算模數(shù)a的負(fù)整數(shù)倍：(-1)×a,(-2)×a,(-3)×a,…,(-n)×a，將所得到的模數(shù)a的負(fù)整數(shù)倍加1，即(-1)×a+1,(-2)×a+1,(-3)×a+1,…,(-n)×a+1。利用試除法，將模數(shù)a的倍數(shù)加1的每一項(xiàng)都除以b，直到余數(shù)為0即正好整除，這時(shí)將所得到的商是負(fù)數(shù)，因此文中再將商模a得到正值，故而此時(shí)的正值即為b-1moda的值。

根據(jù)上述算法，相應(yīng)的C語言程序如下所示：

#include

#include

int gcd(int a,int b);

void main()

{int a,b,i,s;printf("input two number:");scanf("%d%d",&a,&b);a=a%b;

if(gcd(a,b)==1){for(i=1;i<100000;i++)

{if(a>0){if((i*b+1)%a==0) s=(i*b+1)/a;s=s%b;}

else{if(((-1)*i*b+1)%a==0)

{s=((-1)*i*b+1)/a;s=s+b;s=(b+s%b)%b;}}}

printf("%d ",s);}

else {printf("waring ! waring ! wrong input: ");}

int gcd(int a,int b){int m;if(a>0) {m=a%b;while(m!=0) {a=b;b=m;m=a%b;} return b;}

else{a=a+b;m=a%b;while(m!=0) {a=b; b=m;m=a%b;} return b;}}

2.3 判斷二次剩余

判斷二次剩余的目的是為了選取生成元。對(duì)于橢圓曲線y2=x3+ax+b，令a=-1，b=8即y2=x3-x+8，如圖1所示：

圖1 y2=x3-x+8的函數(shù)圖像Fig.1 The functional image of y2=x3-x+8

依據(jù)模數(shù)要求選取模數(shù)p為11。相應(yīng)的C語言程序如下：

#include

#include

void main()

{int z,x,p,y1,y2,k=0;scanf("%d",&p);

if(p%4!=3) {printf("wrong input，please change the number: ");scanf("%d",&p);}

else{for(x=0;x<=p-1;x++) {z=(x*x*x-x+8)%p;if((int)(pow(z,(p-1)/2))%p==1)

{y1=(int)(pow(z,(p+1)/4))%p; y2=(p-(int)(pow(z,(p+1)/4))%p)%p;

printf("x=%d,y1=%d,y2=%d ",x,y1,y2);k=k+2;}}printf("k=%d ",k);}}

運(yùn)行此程序，文中得到了相應(yīng)的數(shù)據(jù)，如表1所示：

表1Z11上的橢圓曲線y2=x3-x+8的點(diǎn)

Table 1 The point of the elliptic curvey2=x3-x+8inZ11

xx3-x+8(mod11)是二次剩余嗎y08否18否23是5,6310否42否57否69是3,873是5,686否92否108否

由上表可知產(chǎn)生6個(gè)點(diǎn)，還有一個(gè)點(diǎn)是無窮遠(yuǎn)點(diǎn)，所以E共有7個(gè)點(diǎn)。

2.4 橢圓曲線加法運(yùn)算

對(duì)于模素?cái)?shù)橢圓曲線y2≡x3-x+8(mod 11)加法運(yùn)算的C語言程序如下：

#include

#include

int ECCadd(int x1,int y1,int x2,int y2,int k，int p)

{int x3,y3,r,m,i;for(i=2;i<=k;i++) {if(x1==x2&&y1==-y2) {printf("無窮遠(yuǎn)點(diǎn) ");}

else if(x1==x2&&y1==y2)

{m=invert(2*y1,p);r=((3*x1*x1-1)*m)%p;x3=(p*p+(r*r-x1-x2))%p;

y3=(p*p+(r*(x1-x3)-y1))%p;printf("%da=(%d,%d) ",i,x3,y3);}

else{m=invert(x2-x1,p);r=(p*p+((y2-y1)*m)%p)%p;x3=(p*p+(r*r-x1-x2)%p)%p;

y3=(p*p+(r*(x1-x3)-y1)%p)%p;printf("%da=(%d,%d) ",i,x3,y3);} x2=x3;y2=y3;}}

int sy(int p) {int z,x,y1,y2,k=0;if(p%4!=3) {printf("please change the number: ");}

else{for(x=0;x<=p-1;x++) {z=(x*x*x-x+8)%p;if((int)(pow(z,(p-1)/2))%p==1)

{y1=(int)(pow(z,(p+1)/4))%p;y2=(p-(int)(pow(z,(p+1)/4))%p)%p;

printf("x=%d,y1=%d,y2=%d ",x,y1,y2);k=k+2;}} printf("k=%d ",k);}}

void main()

{int x1,y1,t,u,p,z,x,k=0;printf("p=");scanf("%d",&p);sy(p);

for(x=0;x<=p-1;x++) {z=(x*x*x-x+8)%p;if((int)(pow(z,(p-1)/2))%p==1){ k=k+2;}}

printf("x1=");scanf("%d",&x1);printf("y1=");scanf("%d",&y1);

printf("a=(%d,%d) ",x1,y1);t=x1;u=y1;ECCadd(x1,y1,t,u,k,p);}

運(yùn)行程序后得到的結(jié)果如下：由判斷二次剩余的表可知，任意選取一對(duì)生成元α=(2,5)。則相應(yīng)的結(jié)果為：

α=(2,5) 2α=(7,6) 3α=(6,3)

4α=(6,8) 5α=(7,5) 6α=(2,6)

由此可以看出，α=(2,5)確是本原元。因此，完成了對(duì)橢圓曲線y2=x3-x+8，且模素?cái)?shù)11的數(shù)據(jù)仿真。

3 總結(jié)

文中運(yùn)用C語言完成了判斷兩數(shù)互素，利用擴(kuò)展的Euclidean算法實(shí)現(xiàn)有限域上的模逆運(yùn)算，對(duì)模素?cái)?shù)橢圓曲線y2≡x3-x+8(mod 11)利用Euler準(zhǔn)則判斷二次剩余且給出列表。以及任意選取一個(gè)生成元，實(shí)現(xiàn)有限域上橢圓曲線的群的加法運(yùn)算，并給出相應(yīng)的結(jié)果。

參考文獻(xiàn):

[1]KOBLITZ N.Elliptic curve cryptosystems[J].Mathematics of Computation，1987，48(177):203-209.

[2]MILLER VS.Use of elliptic curve in cryptography[J].Lecture Notes in Computer Science,1986,218(01):417-426.

[3]MENEZES A，OKAMOTO T，VANSTONE S.Reducing elliptic curve logarithms to logarithms in a finite field[J].IEEE Transaction on Information Theory,1993，39(05):1639-1646.

[4]CHEN L，HARRISION K，MOSS A，et al.Certification of public keys within an identity based system[C]//Lecture Notes in Computer Science.5th International Conference on Information Security.Berlin Germany:Springer-Verlag，2002,2433:322-333.

[5]宋春玉.橢圓曲線密碼系統(tǒng)的matlab實(shí)現(xiàn)[J].西北民族大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,34(02):14-17.

[6]謝天藝,黃凱,修思文,等.素?cái)?shù)域橢圓曲線密碼加速器的VLSI實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(01):89-94.

[7]王千喜,劉海法,王占厚,等.橢圓曲線密碼(ECC)算法的一種硬件實(shí)現(xiàn)方案[J].信息通信,2016,(08):87-88.

[8]戶占良.橢圓曲線密碼體制的研究與應(yīng)用[J].山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，24(03)：13-17.