曹鴻鈺,王鯤鵬

(中國(guó)科學(xué)院信息工程研究所,北京100093)

扭曲雅可比相交曲線(xiàn)上的斜-Frobenius映射

曹鴻鈺,王鯤鵬

(中國(guó)科學(xué)院信息工程研究所,北京100093)

利用扭曲的雅可比相交曲線(xiàn)上的Frobenius自同態(tài)映射,構(gòu)造在扭曲的雅可比相交曲線(xiàn)二次扭曲線(xiàn)上的一個(gè)斜-Frobenius映射,可用于制定扭曲的雅可比相交曲線(xiàn)的快速點(diǎn)乘算法,而不需要使用任何倍點(diǎn)。采用GLV方法加快扭曲的雅可比相交曲線(xiàn)上的點(diǎn)乘運(yùn)算,給出斜的Frobenius映射的特征多項(xiàng)式。實(shí)例結(jié)果表明,該映射能夠加速扭曲雅可比相交曲線(xiàn)上的標(biāo)量乘運(yùn)算。

雅可比相交曲線(xiàn);雙有理等價(jià);扭曲曲線(xiàn);斜-Frobenius映射;τ-展開(kāi);GLV方法

1 概述

早在1829年,Jacobi研究了雅可比相交(Jacobi intersection)形式的橢圓曲線(xiàn)(簡(jiǎn)稱(chēng)雅可比相交曲線(xiàn)),給出了其上的群律。雅可比相交曲線(xiàn)在1986年被Chudnovsky和Chudnovsky[1]引入橢圓曲線(xiàn)密碼學(xué)。

雅可比相交曲線(xiàn)是一種三維空間中2個(gè)曲面的交,其上不僅可以有一般的標(biāo)量乘,還可以實(shí)現(xiàn)配對(duì)計(jì)算。文獻(xiàn)[2]給出了雅可比相交曲線(xiàn)上雅可比相交曲線(xiàn)上配對(duì)的具體計(jì)算方法。

本文回顧扭曲雅可比相交曲線(xiàn)和橢圓曲線(xiàn)上的Frobenius映射。介紹扭曲雅可比相交曲線(xiàn)上的Frobenius映射。引入斜-Frobenius映射,并應(yīng)用Frobenius映射和斜-Frobenius映射來(lái)加速扭曲雅可比相交曲線(xiàn)上的的標(biāo)量乘運(yùn)算。

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

2.1 背景介紹

雅可比相交曲線(xiàn)上的標(biāo)量乘速度是比較有競(jìng)爭(zhēng)力的,例如在其上可以進(jìn)行快速倍點(diǎn)和三倍點(diǎn)計(jì)算。其中,文獻(xiàn)[1]給出了射影坐標(biāo)中雅可比相交曲線(xiàn)上的快速倍點(diǎn)和點(diǎn)加公式。文獻(xiàn)[3-4]對(duì)快速倍點(diǎn)和點(diǎn)加公式給出了一些改進(jìn)。文獻(xiàn)[5]給出了雅可比相交曲線(xiàn)上的快速三倍點(diǎn)公式。文獻(xiàn)[6]給出了更快速的公式。另外,文獻(xiàn)[7]的分析表明特征3的域上雅可比相交曲線(xiàn)上的標(biāo)量乘計(jì)算得更快。

由于計(jì)算Frobenius映射比計(jì)算倍點(diǎn)效率高,文獻(xiàn)[8]提出了利用二次 twised橢圓曲線(xiàn)上的Frobenius映射替代倍點(diǎn)。文獻(xiàn)[9]稱(chēng)這種映射為斜-Frobenius映射,并構(gòu)造了虧格為2和3的超橢圓曲線(xiàn)上的斜-Frobenius映射。

文獻(xiàn)[10]將雅可比相交曲線(xiàn)推廣為扭曲雅可比相交形式的橢圓曲線(xiàn)(簡(jiǎn)稱(chēng)扭曲雅可比相交曲線(xiàn))。在一個(gè)特征不為2的域k上,任一扭曲雅可比相交曲線(xiàn)雙有理等價(jià)于一條橢圓曲線(xiàn)。利用扭曲雅可比相交曲線(xiàn)和橢圓曲線(xiàn)間的雙有理映射,構(gòu)造了域k上的扭曲雅可比相交曲線(xiàn)上的Frobenius映射,并給出這一Frobenius的特征方程。利用扭曲雅可比相交曲線(xiàn)上的Frobenius自同構(gòu)映射可以構(gòu)造快速標(biāo)量乘算法。

利用扭曲雅可比相交曲線(xiàn)上的Frobenius映射和文獻(xiàn)[8]中的方法,構(gòu)造了扭曲雅可比相交曲線(xiàn)上的斜-Frobenius映射。借鑒文獻(xiàn)[11]中的方法,結(jié)果表明斜-Frobenius映射可以用來(lái)加速扭曲雅可比相交曲線(xiàn)上的標(biāo)量乘。擴(kuò)展文獻(xiàn)[12]的方法,文獻(xiàn)[13]方法也可以應(yīng)用在加速扭曲雅可比相交曲線(xiàn)的標(biāo)量乘上。

2.2 雅可比相交曲線(xiàn)與扭曲雅可比相交曲線(xiàn)

特征不為2的域k上的雅可比相交曲線(xiàn)定義為:

其中,b∈k,(1-b)b≠0,(0,1,1)為零元。其上的群律由以下方程給出:

文獻(xiàn)[10]將雅可比相交曲線(xiàn)推廣為廣義形式的扭曲雅可比相交曲線(xiàn)EJ,a,b,定義為:

其中,a,b∈k,(a-b)ab≠0。扭曲雅可比相交曲線(xiàn)的群律定義為[10]:

更加完整的群律可以參考文獻(xiàn)[14]。

扭曲雅可比相交曲線(xiàn)是光滑曲線(xiàn)并且雙有理等價(jià)于橢圓曲線(xiàn)y2=x(x-a)(x-b)。

一條扭曲雅可比相交曲線(xiàn)EJ,a,b是雅可比相交曲線(xiàn)EJ,1,b/a的二次扭曲曲線(xiàn)。 更一般地,EJ,a,b是的二次扭曲曲線(xiàn),其中。反過(guò)來(lái),每個(gè)扭曲雅可比相交曲線(xiàn)的二次twist曲線(xiàn)是一個(gè)扭曲雅可比相交曲線(xiàn)。

2.3 橢圓曲線(xiàn)上的Frobenius映射

設(shè)Fq是一個(gè)特征大于2的有限域。Fq上的橢圓曲線(xiàn)定義為:

其中,∞ 為無(wú)窮遠(yuǎn)點(diǎn)。橢圓曲線(xiàn)E上的q次Frobenius映射πq定義為:

記N=#E(Fq),根據(jù)Hasse定理得到N=q+1-t,這里,且πq的特征方程aq(λ)為:

3 Frobenius映射

設(shè)Fq是一個(gè)特征大于2的有限域且EJ,a,b是定義在Fq的扭曲雅可比相交曲線(xiàn)。考慮如下的EJ,a,b上的q次Frobenius映射:

并且證明如下結(jié)論。

定理1EJ,a,b是定義在Fq上的扭曲雅可比相交曲線(xiàn)且#EJ,a,b=q+1-t。那么對(duì)于任一P∈EJ,a,b(Fq),EJ,a,b上的Frobenius映射Πq滿(mǎn)足:

為了證明這一定理,引入如下的引理。

引理1Fq是一個(gè)特征大于2的有限域。任意一個(gè)Fq上的扭曲雅可比相交曲線(xiàn)在Fq中雙有理等價(jià)于一個(gè)形式為y2=x(x-a)(x-b)的橢圓曲線(xiàn)[10]。

根據(jù)引理1,存在Fq上的一個(gè)形式為y2=x(xa)(x-b)的橢圓曲線(xiàn)E,滿(mǎn)足設(shè)ψ是EJ,a,b到E的同構(gòu)映射,φ是ψ的逆映射。由文獻(xiàn)[10]中的定理3.2,得到映射:

是EJ,a,b到E雙有理等價(jià)映射,同時(shí)它的逆映射φ為:

點(diǎn)(u,v,w)=(0,1,1)對(duì)應(yīng)點(diǎn)(x,y)=∞,點(diǎn)(u,v,w)=(0,1,-1)對(duì)應(yīng)點(diǎn)(x,y)=(b,0)。

引理2EJ,a,b是定義在Fq上的扭曲雅可比相交曲線(xiàn)且E是形式為y2=x(x-a)(x-b)的橢圓曲線(xiàn)。設(shè)#E(Fq)=q+1-t,ψ是如上定義的雙有理映射,πq是E上的q次Frobenius映射。定義Ψ=ψ-1° πq°ψ,那么:

(1)Ψ∈End(EJ,a,b)(即 Ψ 是EJ,a,b上的同源映射);

(2)任一P∈EJ,a,b(Fq),Ψ滿(mǎn)足:

證明:根據(jù)對(duì)引理1的討論,ψ是EJ,a,b到E的Fq中的同構(gòu)映射,πq是E上到自身的Fq中的同源映射。根據(jù)Ψ的定義,Ψ是EJ,a,b到自身的Fq中的同源映射。

對(duì)于任一P∈EJ,a,b(Fq),記Q=ψ(P)∈E(Fq),則:

根據(jù)文獻(xiàn)[15]的定理4.8得到:

定理1的證明:E是Fq上的一個(gè)形式為y2=x(x-a)(x-b)的橢圓曲線(xiàn),Ψ是引理2中的EJ,a,b自同構(gòu)映射。根據(jù) Ψ 的定義,對(duì)于任一P=,有:

可以用這樣的Frobenius映射加速扭曲雅可比相交曲線(xiàn)上的標(biāo)量乘。

4 斜-Frobenius映射

利用第3節(jié)中的扭曲雅可比相交曲線(xiàn)上的Frobenius映射構(gòu)造雅可比相交曲線(xiàn)的二次twist曲線(xiàn)上的斜-Frobenius映射。這個(gè)構(gòu)造是文獻(xiàn)[8,11]中結(jié)果的擴(kuò)展。

Fq上的EJ,a,b是的二次扭曲曲線(xiàn),其中,滿(mǎn)足,令:

其中,α=。若α是k=Fq上的二次非剩余,則映射?是在域上的EJ,a,b到的同構(gòu)映射,記的二次twist曲線(xiàn)為

定理2EJ,a,b是k=Fq上的扭曲雅可比相交曲線(xiàn)且是EJ,a,b的二次扭曲曲線(xiàn)。設(shè)#EJ,a,b(Fq)=q+1-t,映射?是上的到的同構(gòu)映射。設(shè)Πq是EJ,a,b上的q次Frobenius映射。定義,則對(duì)于任一滿(mǎn)足:

和 Frobenius映射 Πq類(lèi)似,上 的 斜-Frobenius映射可以用來(lái)加速扭曲雅可比相交曲線(xiàn)上的標(biāo)量乘。

5 方法應(yīng)用描述與實(shí)例

為了加速標(biāo)量乘,文獻(xiàn)[16-17]利用Frobenius自同構(gòu)映射開(kāi)發(fā)出了不利用倍點(diǎn)公式的標(biāo)量乘算法。這種基于Frobenius自同構(gòu)的特征方程的nP分解已經(jīng)被用來(lái)計(jì)算標(biāo)量乘:

其中,ci是固定集合中的元素,例如{-q/2,…,q/2}。

若Fq是一個(gè)小域時(shí),標(biāo)量乘可以使用不相鄰形式以τ為基展開(kāi)nP來(lái)加速[18-19]。當(dāng)Fq非常大時(shí),文獻(xiàn)[13]設(shè)計(jì)了一種方法來(lái)加速標(biāo)量乘。

5.1 τ-進(jìn)制展開(kāi)方法

EJ,a,b是k=Fq上的扭曲雅可比相交曲線(xiàn)且EJ,a,b是EJ,a,b的二次扭曲曲線(xiàn)。根據(jù)定理 2,存在一個(gè)復(fù)數(shù)τ使得上的斜-Frobenius映射可以被認(rèn)為是τ。τ是一個(gè)由以下方程給出的復(fù)數(shù):

其中,t=q+1-#EJ,a,b(Fq)?？梢詫∈Z[τ]的ω寬窗口τ的不相鄰形式(ω-τNAF)表示如下:

其中,ci∈{-q/2,…,q/2},i=0,1,…,t-1;如果ci,ci+1,…,ci+ω-1是ω個(gè)連續(xù)系數(shù),那么它們當(dāng)中至多一個(gè)非零。

利用EJ,a,b上的Frobenius映射Πq,上述方法可以應(yīng)用在扭曲雅可比相交曲線(xiàn)上。

5.2 GLV方法

擴(kuò)展文獻(xiàn)[11]的方法,將GLV方法應(yīng)用在扭曲雅可比相交曲線(xiàn)的標(biāo)量乘上。

定理3設(shè)Fq的特征大于3,EJ,a,b是k=Fq上的扭曲雅可比相交曲線(xiàn),且#EJ,a,b(Fq)=q+1-t。令是上的EJ,a,b的二次扭曲曲線(xiàn),則設(shè)是一個(gè)素?cái)?shù)且r＞2q。?:是一個(gè)定義在上的扭曲同構(gòu)映射。令:

則對(duì)于任一P∈Et J;a;滿(mǎn)足:

由于r是素?cái)?shù)且r＞2q,因此根據(jù)定理假設(shè),可以得到,但是。這意味著若,則屬于,那么就存在λ∈Z滿(mǎn)足

例1p=2192-264-1是一個(gè)素?cái)?shù)。d=264+1是Fp上的一個(gè)二次非剩余。則在上,EJ,1,λ(λ=-421)的二次扭曲曲線(xiàn)是。 在上,EJ,1,λ到的扭曲同構(gòu)映射定義為:

由于d是Fp上的一個(gè)二次非剩余且p≡ 1(mod4),因此在上對(duì)于任一滿(mǎn)足

例2p=2255-19是一個(gè)素?cái)?shù)。d=121 665/ 121 666是Fp上的一個(gè)二次非剩余,則是EJ,-1,λ(λ=-5 737)在上的二次扭曲曲線(xiàn)?？梢远xEJ,1,λ到的上的扭曲同構(gòu)映射為:

d是Fp上的一個(gè)二次非剩余且p≡1(mod4),則在

同時(shí)由于EJ,a,b是的二次扭曲曲線(xiàn),其中這樣可以選小一點(diǎn)的,使得是EJ,a,b的二次扭曲曲線(xiàn)。

6 結(jié)束語(yǔ)

本文論述了定義在有限域Fq上的扭曲雅可比相交曲線(xiàn)中的自同構(gòu),介紹了扭曲雅可比相交曲線(xiàn)上Frobenius映射的性質(zhì)并給出了這個(gè)Frobenius映射的特征方程。應(yīng)用扭曲雅可比相交曲線(xiàn)上的Frobenius映射,構(gòu)造了定義在扭曲雅可比相交曲線(xiàn)二次扭曲曲線(xiàn)上的斜-Frobenius映射。結(jié)果表明,扭曲雅可比相交曲線(xiàn)的Frobenius映射和斜-Frobenius映射可以加速扭曲雅可比相交曲線(xiàn)上的標(biāo)量乘運(yùn)算。

[1] Chudnovsky D V,Chudnovsky G V.Sequencesof Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests[J].Advances in Applied Mathematics,1986,7(4):385-434.

[2] 唐春明,徐茂智,亓延峰.Jacobi交上的配對(duì)計(jì)算[J].計(jì)算機(jī)工程與科學(xué),2011,33(10):25-29.

[3] Liardet P Y,Smart N P.Preventing SPA/DPA in ECC Systems Using the Jacobi Form[C]//Proceedings of the 3rd International Workshop on Cryptographic Hardware and Embedded Systems.Berlin,Germany:Springer, 2001:391-401.

[4] Bernstein D J,Lange T.Explicit-formulae Database [EB/OL].(2008-03-12).http://www.hyperelliptic. org/EFD.

[5] Hisil H,CarterG,DawsonE.New Formulaefor Efficient Elliptic Curve Arithmetic[C]//Proceedings of the 8th International Conference on Cryptology in India. Berlin,Germany:Springer,2007:138-151.

[6] Hisil H,Wong K K H,Carter G,et al.Faster Group Operations on Elliptic Curves[C]//Proceedings of the 7th Australasian Conference on Information Security. [S.l.]:Australian Computer Society Inc.,2009:7-20.

[7] 端木慶峰,張雄偉,王衍波,等.3特征域橢圓曲線(xiàn)群點(diǎn)的快速計(jì)算算法[J].解放軍理工大學(xué)學(xué)報(bào):自然科學(xué)版,2011,12(1):1-6.

[8] Iijima T,Matsuo K,Chao J,et al.Construction of Frobenius Maps ofTwistsEllipticCurvesand Its Application to Elliptic Scalar Multiplication[C]// Proceedings of Conference on Small Computer System Interface.Berlin,Germany:Springer,2002:699-702.

[9] Kozaki S,Matsuo K,Shimbara Y.Skew-Frobenius Maps on Hyperelliptic Curves[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2008,91(7):1839-1843.

[10] Feng Rongquan,Nie Menglong,Wu Hongfeng.Twisted Jacobi Intersections Curves[J].Theoretical Computer Science,2013,494:24-35.

[11] Wang Mingqiang,Wang Xiaoyun,Zhan Tao,et al. Skew-Frobenius Map on Twisted Edwards Curve[C]// Proceedings of the 7th International Conference on Theory and Application of Models of Computation. Prague,Czech:[s.n.],2010:199-210.

[12] Gallant R P,Lambert R J,Vanstone S A.Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms[C]//Advances in Cryptology-CRYPTO’01.Berlin,Germany:Springer,2001:190-200.

[13] Galbraith S D,Lin X,Scott M.Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves[J].Journal of Cryptology,2011,24(3): 446-469.

[14] Wu H,Feng R.A Complete Set of Addition Laws for Twisted Jacobi Intersection Curves[J].Wuhan University Journal of Natural Sciences,2011,16(5): 435-438.

[15] Silverman J H.The Arithmetic of Elliptic Curves[M]. Dordrecht,the Netherlands:Springer,2009.

[16] Solinas J A.Efficient Arithmetic on Koblitz Curves[J]. Designs,Codes and Cryptography,2000,19(2/3): 195-249.

[17] Solinas J A.An Improved Algorithm for Arithmetic on a Family of Elliptic Curves[C]//Proceedings of CRYPTO’97.Berlin,Germany:Springer,1997:357-371.

[18] Koblitz N. CM-curves with Good Cryptographic Properties[C]//Proceedings of CRYPTO’91.Berlin, Germany:Springer,1992:279-287.

[19] Blake I F,KumarM V,Xu Guangwu.Efficient Algorithms for Koblitz Curves over Fields of Characteristic Three[J].Journal of Discrete Algorithms, 2005,3(1):113-124.

編輯 顧逸斐

Skew-Frobenius Mapping on Twisted Jacobi Intersection Curve

CAO Hongyu,WANG Kunpeng
(Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China)

Using the Frobenius endomorphism on twisted Jacobi intersection curve,this paper constructs a skew-Frobenius mapping which is defined on the quadratic twist of twisted Jacobi intersection curve.It can be exploited to devise fast point multiplication algorithm on twisted Jacobi intersection curve that does not use any point doubling.The Gallant-Lamber-Vanstone(GLV)method can be used for speeding up point multiplication on twisted Jacobi intersection curve.The characteristic polynomial of the mapping is given.Example results show that the mapping can speed up the scalar multiplication of twisted Jacobi intersection curve.

Jacobi intersection curve;birationally equivalent;twist curve;skew-Frobenius mapping;τ-expansion; Gallant-Lamber-Vanstone(GLV)method

1000-3428(2015)01-0270-05

A

TP391

10.3969/j.issn.1000-3428.2015.01.051

國(guó)家“973”計(jì)劃基金資助項(xiàng)目(2013CB338001);國(guó)家自然科學(xué)基金資助項(xiàng)目(61272040);中國(guó)科學(xué)院戰(zhàn)略性先導(dǎo)科技專(zhuān)項(xiàng)基金資助項(xiàng)目(XDA06010702)。

曹鴻鈺(1988-),男,碩士研究生,主研方向:信息安全;王鯤鵬,教授。

2014-02-18

2014-03-20 E-mail:feng_896@163.com

中文引用格式:曹鴻鈺,王鯤鵬.扭曲雅可比相交曲線(xiàn)上的斜-Frobenius映射[J].計(jì)算機(jī)工程,2015,41(1):270-274.

英文引用格式:Cao Hongyu,Wang Kunpeng.Skew-Frobenius Mapping on Twisted Jacobi Intersection Curve[J]. Computer Engineering,2015,41(1):270-274.