扭曲雅可比相交曲線上的斜-Frobenius映射

曹鴻鈺,王鯤鵬

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

扭曲雅可比相交曲線上的斜-Frobenius映射

曹鴻鈺,王鯤鵬

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

利用扭曲的雅可比相交曲線上的Frobenius自同態映射,構造在扭曲的雅可比相交曲線二次扭曲線上的一個斜-Frobenius映射,可用于制定扭曲的雅可比相交曲線的快速點乘算法,而不需要使用任何倍點。采用GLV方法加快扭曲的雅可比相交曲線上的點乘運算,給出斜的Frobenius映射的特征多項式。實例結果表明,該映射能夠加速扭曲雅可比相交曲線上的標量乘運算。

雅可比相交曲線;雙有理等價;扭曲曲線;斜-Frobenius映射;τ-展開;GLV方法

1 概述

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

雅可比相交曲線是一種三維空間中2個曲面的交,其上不僅可以有一般的標量乘,還可以實現配對計算。文獻[2]給出了雅可比相交曲線上雅可比相交曲線上配對的具體計算方法。

本文回顧扭曲雅可比相交曲線和橢圓曲線上的Frobenius映射。介紹扭曲雅可比相交曲線上的Frobenius映射。引入斜-Frobenius映射,并應用Frobenius映射和斜-Frobenius映射來加速扭曲雅可比相交曲線上的的標量乘運算。

2 預備知識

2.1 背景介紹

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

由于計算Frobenius映射比計算倍點效率高,文獻[8]提出了利用二次 twised橢圓曲線上的Frobenius映射替代倍點。文獻[9]稱這種映射為斜-Frobenius映射,并構造了虧格為2和3的超橢圓曲線上的斜-Frobenius映射。

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

利用扭曲雅可比相交曲線上的Frobenius映射和文獻[8]中的方法,構造了扭曲雅可比相交曲線上的斜-Frobenius映射。借鑒文獻[11]中的方法,結果表明斜-Frobenius映射可以用來加速扭曲雅可比相交曲線上的標量乘。擴展文獻[12]的方法,文獻[13]方法也可以應用在加速扭曲雅可比相交曲線的標量乘上。

2.2 雅可比相交曲線與扭曲雅可比相交曲線

特征不為2的域k上的雅可比相交曲線定義為:

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

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

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

更加完整的群律可以參考文獻[14]。

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

一條扭曲雅可比相交曲線EJ,a,b是雅可比相交曲線EJ,1,b/a的二次扭曲曲線。 更一般地,EJ,a,b是的二次扭曲曲線,其中。反過來,每個扭曲雅可比相交曲線的二次twist曲線是一個扭曲雅可比相交曲線。

2.3 橢圓曲線上的Frobenius映射

設Fq是一個特征大于2的有限域。Fq上的橢圓曲線定義為:

其中,∞ 為無窮遠點。橢圓曲線E上的q次Frobenius映射πq定義為:

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

3 Frobenius映射

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

并且證明如下結論。

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

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

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

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

是EJ,a,b到E雙有理等價映射,同時它的逆映射φ為:

點(u,v,w)=(0,1,1)對應點(x,y)=∞,點(u,v,w)=(0,1,-1)對應點(x,y)=(b,0)。

引理2EJ,a,b是定義在Fq上的扭曲雅可比相交曲線且E是形式為y2=x(x-a)(x-b)的橢圓曲線。設#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),Ψ滿足:

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

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

根據文獻[15]的定理4.8得到:

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

可以用這樣的Frobenius映射加速扭曲雅可比相交曲線上的標量乘。

4 斜-Frobenius映射

利用第3節中的扭曲雅可比相交曲線上的Frobenius映射構造雅可比相交曲線的二次twist曲線上的斜-Frobenius映射。這個構造是文獻[8,11]中結果的擴展。

Fq上的EJ,a,b是的二次扭曲曲線,其中,滿足,令:

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

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

和 Frobenius映射 Πq類似,上 的 斜-Frobenius映射可以用來加速扭曲雅可比相交曲線上的標量乘。

5 方法應用描述與實例

為了加速標量乘,文獻[16-17]利用Frobenius自同構映射開發出了不利用倍點公式的標量乘算法。這種基于Frobenius自同構的特征方程的nP分解已經被用來計算標量乘:

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

若Fq是一個小域時,標量乘可以使用不相鄰形式以τ為基展開nP來加速[18-19]。當Fq非常大時,文獻[13]設計了一種方法來加速標量乘。

5.1 τ-進制展開方法

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

其中,t=q+1-#EJ,a,b(Fq)。可以將k∈Z[τ]的ω寬窗口τ的不相鄰形式(ω-τNAF)表示如下:

其中,ci∈{-q/2,…,q/2},i=0,1,…,t-1;如果ci,ci+1,…,ci+ω-1是ω個連續系數,那么它們當中至多一個非零。

利用EJ,a,b上的Frobenius映射Πq,上述方法可以應用在扭曲雅可比相交曲線上。

5.2 GLV方法

擴展文獻[11]的方法,將GLV方法應用在扭曲雅可比相交曲線的標量乘上。

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

則對于任一P∈Et J;a;滿足:

由于r是素數且r＞2q,因此根據定理假設,可以得到,但是。這意味著若,則屬于,那么就存在λ∈Z滿足

例1p=2192-264-1是一個素數。d=264+1是Fp上的一個二次非剩余。則在上,EJ,1,λ(λ=-421)的二次扭曲曲線是。 在上,EJ,1,λ到的扭曲同構映射定義為:

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

例2p=2255-19是一個素數。d=121 665/ 121 666是Fp上的一個二次非剩余,則是EJ,-1,λ(λ=-5 737)在上的二次扭曲曲線。可以定義EJ,1,λ到的上的扭曲同構映射為:

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

同時由于EJ,a,b是的二次扭曲曲線,其中這樣可以選小一點的,使得是EJ,a,b的二次扭曲曲線。

6 結束語

本文論述了定義在有限域Fq上的扭曲雅可比相交曲線中的自同構,介紹了扭曲雅可比相交曲線上Frobenius映射的性質并給出了這個Frobenius映射的特征方程。應用扭曲雅可比相交曲線上的Frobenius映射,構造了定義在扭曲雅可比相交曲線二次扭曲曲線上的斜-Frobenius映射。結果表明,扭曲雅可比相交曲線的Frobenius映射和斜-Frobenius映射可以加速扭曲雅可比相交曲線上的標量乘運算。

[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交上的配對計算[J].計算機工程與科學,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特征域橢圓曲線群點的快速計算算法[J].解放軍理工大學學報:自然科學版,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

國家“973”計劃基金資助項目(2013CB338001);國家自然科學基金資助項目(61272040);中國科學院戰略性先導科技專項基金資助項目(XDA06010702)。

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

2014-02-18

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

中文引用格式:曹鴻鈺,王鯤鵬.扭曲雅可比相交曲線上的斜-Frobenius映射[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.