Top > Search of International Patents > SCALAR MULTIPLIER AND SCALAR MULTIPLICATION PROGRAM

SCALAR MULTIPLIER AND SCALAR MULTIPLICATION PROGRAM

Foreign code F110002875
File No. S2009-0170-C0
Posted date May 6, 2011
Country WIPO
International application number 2009JP070127
International publication number WO 2010/061951
Date of international filing Nov 30, 2009
Date of international publication Jun 3, 2010
Priority data
  • P2008-305121 (Nov 28, 2008) JP
Title SCALAR MULTIPLIER AND SCALAR MULTIPLICATION PROGRAM
Abstract Provided are a scalar multiplier which makes it possible to execute scalar multiplication at high speed, and a scalar multiplication program. When calculating a scalar multiplication [s]P of a rational point P of an additive group E (Fp) comprising rational points on an elliptical curve wherein a characteristic p, an order r, and a trace t of a Frobenius endomorphism map at an embedded degree k = 12 using an integer variable .chi. are provided as p(.chi.)=36.chi.4-36.chi.3+24.chi.2-6.chi.+1, r(.chi.)=36.chi.4-36.chi.3+18.chi.2-6.chi.+1=p(.chi.)+1-t(.chi.), t(.chi.)=6.chi.2+1, assuming that the twist degree d is 6 and a positive integer e is 2 where k=d * e, [s]P=([A].phi.'2+[B])P is calculated using the Frobenius map .phi.'2 where [p2]P=.phi.'2(P).
Scope of claims (In Japanese)
【請求項1】 整数変数χを用いて、埋め込み次数k=12における標数p、位数r、フロベニウス自己準同型写像のトレースtが、
  p(χ)=36χ4-36χ3+24χ2-6χ+1,
  r(χ)=36χ4-36χ3+18χ2-6χ+1=p(χ)+1-t(χ),
  t(χ)=6χ2+1,
として与えられる楕円曲線の有理点が成す加法群E(Fp)の有理点Pのスカラ倍算[s]Pを演算するスカラ倍算器であって、
 ツイスト次数dを6とし、k=d×eとなる正整数eを2として、
  [p2]P=φ'2(P),
となるフロベニウス写像φ'2を用い、
  [6χ2-4χ+1]P=[(-2χ+1)p2]P=[-2χ+1]φ'2(P)
であることから、6χ2-4χ+1=νとして前記スカラsをν進数展開することにより
  s=s1ν+s2,s2<ν,
とし、
  s≡(-2χ+1)s1p2+s2 mod r,
であることから、(-2χ+1)s1部分をν進数展開して、
  s≡(s3ν+s4)p2+s2≡s5p4+s4p2+s2 mod r,
とし、p4≡p2-1 mod rであることから、
  s≡(s4+s5)p2+(s2-s5) mod r,
であることを利用して、スカラ倍算[s]Pを、
  [s]P=([s4+s5]φ'2+[s2-s5])P,
として演算すべく、
 前記スカラsの値を記憶する記憶手段と、
 前記係数s1,s2,s3,s4,s5をそれぞれ記憶する第1~5補助記憶手段と
を設け、
 前記スカラsをν進数展開して得られた値を前記第1補助記憶手段と前記第2補助記憶手段に記憶させ、(-2χ+1)s1をν進数展開して得られた値を前記第3補助記憶手段と前記第4補助記憶手段に記憶させ、(-2χ+1)s3の値を前記第5補助記憶手段に記憶させているスカラ倍算器。

【請求項2】 整数変数χを用いて、埋め込み次数k=12における標数p、位数r、フロベニウス自己準同型写像のトレースtが、
  p(χ)=36χ4-36χ3+24χ2-6χ+1,
  r(χ)=36χ4-36χ3+18χ2-6χ+1=p(χ)+1-t(χ),
  t(χ)=6χ2+1,
として与えられる楕円曲線の有理点が成す加法群E(Fp)の有理点Pのスカラ倍算[s]Pを、CPUを備えた電子計算機に演算させるスカラ倍算プログラムであって、
 ツイスト次数dを6とし、k=d×eとなる正整数eを2として、
  [p2]P=φ'2(P),
となるフロベニウス写像φ'2を用い、
  [6χ2-4χ+1]P=[(-2χ+1)p2]P=[-2χ+1]φ'2(P)
であることから、6χ2-4χ+1=νとして前記スカラsをν進数展開することにより
  s=s1ν+s2,s2<ν,
とし、
  s≡(-2χ+1)s1p2+s2 mod r,
であることから、(-2χ+1)s1部分をν進数展開して、
  s≡(s3ν+s4)p2+s2≡s5p4+s4p2+s2 mod r,
とし、p4≡p2-1 mod rであることから、
  s≡(s4+s5)p2+(s2-s5) mod r,
であることを利用して、スカラ倍算[s]Pを、
  [s]P=([s4+s5]φ'2+[s2-s5])P,
として前記電子計算機に演算させるべく、
 前記スカラsをν進数展開して得られる前記s1を第1のレジスタに格納させるとともに前記s2を第2のレジスタに格納させるステップと、
 (-2χ+1)s1をν進数展開して得られる前記s3を第3のレジスタに格納させるとともに前記s4を第4のレジスタに格納させるステップと、
 (-2χ+1)s3の値を前記s5の値として第5のレジスタに格納させるステップと、
を有するスカラ倍算プログラム。

【請求項3】 整数変数χを用いて、埋め込み次数k=8における標数p、位数r、フロベニウス自己準同型写像のトレースtが、
  p(χ)=(81χ6+54χ5+45χ4+12χ3+13χ2+6χ+1)/4,
  r(χ)=9χ4+12χ3+8χ2+4χ+1,
  t(χ)=-9χ3-3χ2-2χ,
として与えられる楕円曲線の有理点が成す加法群E(Fp)の有理点Pのスカラ倍算[s]Pを演算するスカラ倍算器であって、
 ツイスト次数dを4とし、k=d×eとなる正整数eを2として、
  [p2]P=φ'2(P),
となるフロベニウス写像φ'2を用い、
  [3χ2+2χ]P=[(-2χ-1)p2]P=[-2χ-1]φ'2(P)
であることから、3χ2+2χ=νとして前記スカラsをν進数展開することにより
  s=s1ν+s2,s2<ν,
とし、
  s≡(-2χ-1)s1p2+s2 mod r,
であることから、(-2χ-1)s1部分をν進数展開して、
  s≡(s3ν+s4)p2+s2≡s5p4+s4p2+s2 mod r,
とし、p4≡-1 mod rであることから、
  s≡s4p2+(s2-s5) mod r,
であることを利用して、スカラ倍算[s]Pを、
  [s]P=([s4]φ'2+[s2-s5])P,
として演算すべく、
 前記スカラsの値を記憶する記憶手段と、
 前記係数s1,s2,s3,s4,s5をそれぞれ記憶する第1~5補助記憶手段と
を設け、
 前記スカラsをν進数展開して得られた値を前記第1補助記憶手段と前記第2補助記憶手段に記憶させ、(-2χ-1)s1をν進数展開して得られた値を前記第3補助記憶手段と前記第4補助記憶手段に記憶させ、(-2χ-1)s3の値を前記第5補助記憶手段に記憶させているスカラ倍算器。

【請求項4】 整数変数χを用いて、埋め込み次数k=8における標数p、位数r、フロベニウス自己準同型写像のトレースtが、
  p(χ)=(81χ6+54χ5+45χ4+12χ3+13χ2+6χ+1)/4,
  r(χ)=9χ4+12χ3+8χ2+4χ+1,
  t(χ)=-9χ3-3χ2-2χ,
として与えられる楕円曲線の有理点が成す加法群E(Fp)の有理点Pのスカラ倍算[s]Pを、CPUを備えた電子計算機に演算させるスカラ倍算プログラムであって、
 ツイスト次数dを4とし、k=d×eとなる正整数eを2として、
  [p2]P=φ'2(P),
となるフロベニウス写像φ'2を用い、
  [3χ2+2χ]P=[(-2χ-1)p2]P=[-2χ-1]φ'2(P)
であることから、3χ2+2χ=νとして前記スカラsをν進数展開することにより
  s=s1ν+s2,s2<ν,
とし、
  s≡(-2χ-1)s1p2+s2 mod r,
であることから、(-2χ-1)s1部分をν進数展開して、
  s≡(s3ν+s4)p2+s2≡s5p4+s4p2+s2 mod r,
とし、p4≡-1 mod rであることから、
  s≡s4p2+(s2-s5) mod r,
であることを利用して、スカラ倍算[s]Pを、
  [s]P=([s4]φ'2+[s2-s5])P,
として前記電子計算機に演算させるべく、
 前記スカラsをν進数展開して得られる前記s1を第1のレジスタに格納させるとともに前記s2を第2のレジスタに格納させるステップと、
 (-2χ-1)s1をν進数展開して得られる前記s3を第3のレジスタに格納させるとともに前記s4を第4のレジスタに格納させるステップと、
 (-2χ-1)s3の値を前記s5の値として第5のレジスタに格納させるステップと、
を有するスカラ倍算プログラム。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • NATIONAL UNIVERSITY CORPORATION OKAYAMA UNIVERSITY
  • Inventor
  • NOGAMI, Yasuyuki
  • SAKEMI, Yumi
  • MORIKAWA, Yoshitaka
IPC(International Patent Classification)
Specified countries AE(UTILITY MODEL),AG,AL(UTILITY MODEL),AM(PROVISIONAL PATENT)(UTILITY MODEL),AO(UTILITY MODEL),AT(UTILITY MODEL),AU,AZ(UTILITY MODEL),BA,BB,BG(UTILITY MODEL),BH(UTILITY MODEL),BR(UTILITY MODEL),BW(UTILITY MODEL),BY(UTILITY MODEL),BZ(UTILITY MODEL),CA,CH,CL(UTILITY MODEL),CN(UTILITY MODEL),CO(UTILITY MODEL),CR(UTILITY MODEL),CU(INVENTOR'S CERTIFICATE),CZ(UTILITY MODEL),DE(UTILITY MODEL),DK(UTILITY MODEL),DM,DO(UTILITY MODEL),DZ,EC(UTILITY MODEL),EE(UTILITY MODEL),EG(UTILITY MODEL),ES(UTILITY MODEL),FI(UTILITY MODEL),GB,GD,GE(UTILITY MODEL),GH(UTILITY CERTIFICATE),GM,GT(UTILITY MODEL),HN,HR(CONSENSUAL PATENT),HU(UTILITY MODEL),ID,IL,IN,IS,JP(UTILITY MODEL),KE(UTILITY MODEL),KG(UTILITY MODEL),KM,KN,KP(INVENTOR'S CERTIFICATE)(UTILITY MODEL),KR(UTILITY MODEL),KZ(PROVISIONAL PATENT)(UTILITY MODEL),LA,LC,LK,LR,LS(UTILITY MODEL),LT,LU,LY,MA,MD(UTILITY MODEL),ME,MG,MK,MN,MW,MX(UTILITY MODEL),MY(UTILITY-INNOVATION),MZ(UTILITY MODEL),NA,NG,NI(UTILITY MODEL),NO,NZ,OM(UTILITY MODEL),PE(UTILITY MODEL),PG,PH(UTILITY MODEL),PL(UTILITY MODEL),PT(UTILITY MODEL),RO,RS(PETTY PATENT),RU(UTILITY MODEL),SC,SD,SE,SG,SK(UTILITY MODEL),SL(UTILITY MODEL),SM,ST,SV(UTILITY MODEL),SY,TJ(UTILITY MODEL),TM(PROVISIONAL PATENT),TN,TR(UTILITY MODEL),TT(UTILITY CERTIFICATE),TZ,UA(UTILITY MODEL),UG(UTILITY CERTIFICATE),US,UZ(UTILITY MODEL),VC(UTILITY CERTIFICATE),VN(PATENT FOR UTILITY SOLUTION),ZA,ZM,ZW,EP(AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MK,MT,NL,NO,PL,PT,RO,SE,SI,SK,SM,TR),OA(BF(UTILITY MODEL),BJ(UTILITY MODEL),CF(UTILITY MODEL),CG(UTILITY MODEL),CI(UTILITY MODEL),CM(UTILITY MODEL),GA(UTILITY MODEL),GN(UTILITY MODEL),GQ(UTILITY MODEL),GW(UTILITY MODEL),ML(UTILITY MODEL),MR(UTILITY MODEL),NE(UTILITY MODEL),SN(UTILITY MODEL),TD(UTILITY MODEL),TG(UTILITY MODEL)),AP(BW(UTILITY MODEL),GH(UTILITY MODEL),GM(UTILITY MODEL),KE(UTILITY MODEL),LS(UTILITY MODEL),MW(UTILITY MODEL),MZ(UTILITY MODEL),NA(UTILITY MODEL),SD(UTILITY MODEL),SL(UTILITY MODEL),SZ(UTILITY MODEL),TZ(UTILITY MODEL),UG(UTILITY MODEL),ZM(UTILITY MODEL),ZW(UTILITY MODEL)),EA(AM,AZ,BY,KG,KZ,MD,RU,TJ,TM)

PAGE TOP

close
close
close
close
close
close