Source: http://www.google.com/patents/US6430588?dq=patent:5881444
Timestamp: 2017-12-12 10:19:25
Document Index: 99932992

Matched Legal Cases: ['art 20', 'art 10', 'art 30', 'art 20', 'art 20', 'art 21', 'art 22', 'art 24', 'art 24', 'art 24', 'art 30', 'art 30', 'art 30', 'art 32', 'art 33', 'art 21', 'art 22', 'art 50', 'art 10', 'art 30', 'art 10', 'art 30', 'art 20', 'art 20', 'art 40', 'art 10', 'art 30', 'art 40', 'art 41', 'art 42', 'art 43', 'art 40', 'art 30', 'art 42', 'art 21', 'art 22', 'art 40', 'art 40', 'art 50', 'art 30', 'art 20', 'art 10', 'art 30', 'art 25', 'art 30', 'art 32', 'art 33', 'art 34', 'art 30', 'art 32', 'art 32', 'art 32', 'art 25', 'art 25', 'art 25', 'art 25', 'art 25', 'art 25', 'art 25', 'art 25', 'art 25', 'art 10', 'arts 14', 'arts 14', 'art 63', 'art 60']

Patent US6430588 - Apparatus and method for elliptic-curve multiplication and recording medium ... - Google Patents
In an apparatus for calculating m-multiplication of a rational point over an elliptic curve defined over a finite field, a base-φ expansion part calculates c0, c1, . . . , cr−1 such that m = ∑ i = 0 r - i   c i  φ i  ( mod   φ k - 1 ) for the input thereinto of integers k and...http://www.google.com/patents/US6430588?utm_source=gb-gplus-sharePatent US6430588 - Apparatus and method for elliptic-curve multiplication and recording medium having recorded thereon a program for implementing the method
Publication number US6430588 B1
Application number US 09/389,233
Also published as DE69906897D1, DE69906897T2, EP0984357A1, EP0984357B1
Publication number 09389233, 389233, US 6430588 B1, US 6430588B1, US-B1-6430588, US6430588 B1, US6430588B1
Inventors Tetsutaro Kobayashi, Hikaru Morita, Kunio Kobayashi, Fumitaka Hoshino
Patent Citations (9), Non-Patent Citations (7), Referenced by (38), Classifications (4), Legal Events (4)
Apparatus and method for elliptic-curve multiplication and recording medium having recorded thereon a program for implementing the method
US 6430588 B1
In an apparatus for calculating m-multiplication of a rational point over an elliptic curve defined over a finite field, a base-φ expansion part calculates c0, c1, . . . , cr−1 such that m = ∑ i = 0 r - i   c i  φ i  ( mod   φ k - 1 )
for the input thereinto of integers k and m, a definition field size q, a GF(qk)-rational point P and a Frobenius map φ, and a Pi generation part generates P0, P1, . . . , Pr−1 from Pi=φi, and a table reference addition part obtains mP by mP = ∑ i = 0 r - 1   c i  P i .
1. An elliptic curve multiplication apparatus for calculating m-multiplication of GF(qk)-rational point P over an elliptic curve E/GF(q) defined over a finite field, said apparatus comprising:
input means for inputting thereinto said GF(qk)-rational point P, a Frobenius map φ defined over said elliptic curve E/GF(q), an integer k, and a prime q exceeding 3 or a power of said prime;
base-φ expansion means for calculating integers r and ci, where 0≦i<r, 0≦r≦k, −q≦ci≦q, which satisfy m = ∑ i = 0 r - 1   c i  φ i (1a)
using said Frobenius map φ dependent on said elliptic curve E/GF(q);
Pi generation means supplied with said GF(qk)-rational point P and said integers r and ci, for calculating r points P0 to Pr−1 such that
Pr−1=φr−1P;
table reference addition means supplied with said r points P0 to Pr−1, for obtaining mP by mP = ∑ i = 0 r - 1   c i  φ i  P (2a)
output means for outputting said mP.
2. The apparatus of claim 1, wherein said table reference addition means comprises means for obtaining a value Sd by adding all Pi for i which correspond to ci not exceeding d and for obtaining said mP by S = ∑ d = 0 b   S d
where b is the maximum among ci.
means for obtaining cij from c i = ∑ j = 0 [ log 2   b ]   2 j  c ij ,
where 0≦cij≦1 and b is the maximum among ci;
means for calculating S j = ∑ i = 0 k - 1   c ij  P i ;
means for obtaining said mP by S = ∑ j = 0 [ log 2   b ] - 1   2 j  S j .
4. The apparatus of claim 1, wherein said table reference addition means is means for obtaining said mP by calculating: S j = ∑ i = 0 k - 1   δ ij  P i
where δij=1 for those m=j and δij=0 otherwise, and S = ∑ j = 0 b - 1   j   S j
where 0≦j<b and b is the maximum among ci.
Sr=O
Si=ciP+φSi+1, 0≦i<r (3a)
said Pi generation means comprises means for calculating
Pi=iP,
where 0<i≦q; and
said table reference addition means is means for performing the calculation of said Equation (3a) as
Si=Pi+φSi+1, where 0≦i<r,
using all or some of said Pi.
where 0<i ≦q, for performing the calculation of said Equation (1a) as
Si=Pi+φSi+1, where 0≦i <r.
φkP=P
(φk−1+φk−2+ . . . +1)P=0
when it holds for said GF(qk)-rational point P over said elliptic curve, calculates c′i and r′ that satisfy ∑ i = 0 r - 1   c j  φ i = ∑ i = 0 r ′ - 1   c i ′  φ i
for a ci-sequence obtained by said base-φ expansion means and for said r and which provides them as said ci and r to said table reference addition means, and wherein said table reference addition means calculates the right-hand side of said Equation (2a) using said ci and r provided from said base-φ expansion adjustment means.
when it holds for said GF(qk)-rational point P over said elliptic curve, and which inputs said k c′i-sequence into said table reference addition means to perform the calculation of the right-hand side of said Equation (1a).
10. The apparatus of claim 8 or 9, wherein said table reference addition means includes means for obtaining Sd by adding together all Pi for those i which correspond to ci not exceeding d and calculates said Equation (1a) by S = ∑ d = 0 r   S d
said base-φ expansion adjustment means includes means for transforming ci to reduce their absolute values through utilization of
when it holds for said GF(qk)-rational point P over said elliptic curve.
said table reference addition means determines cij by c i = ∑ j = 0 [ log   b ]   2 j  c ij ,
where 0≦cij≦1, [log b] is the maximum integer smaller than b and b is the maximum value of |ci|, and obtains said mP by S j = ∑ i = 0 k - 1   c ij  P i S = ∑ j = 0 [ log   b ] - 1   2 j  S j ;
said base-φ expansion adjustment means includes means for transforming ci to minimize the Hamming weight represented by the number of values of other digits than those 0 of a binary or signed binary number of said ci, through utilization of
12. The apparatus of claim 1, 8, or 9, wherein P1, P2, . . . , Pn are input as points P over said elliptic curve, and m1, m2, . . . , mn are input as said integer m to obtain said mP by ∑ i = 0 n   m i  P i
13. The apparatus of claim 12, wherein said Pi generation means increases the efficiency of the calculation by said table reference addition means by obtaining at least one part of Si1, Si2, . . . , Sin, where 0≦ik≦1, which are obtained from said points P1, P2, . . . , Pn by S i   n = ∑ k = 1 n   i k  P k
14. The apparatus of claim 12, wherein the efficiency of the calculation by said table reference addition means is increased by externally inputting at east one part of Si1, Si2, . . . , Sin, where 0≦ik≦1, which are obtained from said points P1, P2, . . . , Pn by S i   n = ∑ k = 1 n   i k  P k
said base-φ expansion means calculates r and ci, where 0≦i<r, 0≦r<k and −q<ci<q, which satisfy m = ∑ i = 0 r - 1   c i  φ i
using said Frobenius map φ which is defined by E/GF(q);
said Pi generation means is means which, for the input thereto of an integer r and s GF(qk)-rational points Qt=dtaP (0≦t<s) over E/GF(q) pre-computed with P (where, letting C=1+max|ci|, a, d and s are positive integers that satisfy a×s≧logd), calculates r×s GF(qk)-rational points Rt,i (0≦t<s, 0≦i<r) over E/GF(q); and
said table reference addition means is a pre-computed table reference addition part which calculates cj,t,iεB (where B is assumed to be a finite set of integers and low in order) such that c i = ∑ j = 0 a - 1   ∑ t = 0 s - 1   d j + ta  c j , t , i (4a)
and obtains said mP by mP = ∑ j = 0 a - 1   ∑ i = 0 r - 1   ∑ t = 0 s - 1   d j  c j , t , i  R t , i . (5a)
means for calculating T j = ∑ j = 0 r - 1   ∑ t = 0 s - 1   c j , t , i  R t , i ; (6a)
and means for calculating said mP by mP = ∑ j = 0 a - 1   d j  T j (7a)
said integer d is 2;
said set B is {0, 1}; and
a Cj,t,i-multiplication is constructed only by 0-multiplication and 1-multiplication in said equation (6a).
said set B is {−1, 0, 1}; and
a Cj,t,i-multiplication is constructed only by (−1)- multiplication, 0-multiplication and 1-multiplication in said equation (6a).
said power operating means comprises:
a polynomial basis calculation part into which, the order q of a finite field GF(q) defined such that f(x) is expressed in the form of xk−β, where βεGF(q), and the degree k set to be relatively prime to said order q are input, and which calculates iq mod k (1≦i≦k−1), then, letting iq/(k) represent the calculated results, rearranges α0=1 and α1q/(k) (1≦i≦k−1) in ascending order of powers and outputs them as new polynomial bases;
a correcting factor calculation part which inputs thereto said order q, said degree k and said β, then divides iq (1≦i≦k−1) by k to obtain an integer [iq/k] with its fraction portion dropped, and calculating β[iq/k] (1≦i≦k−1) as correcting factors of said element ai of GF(q) (1≦i≦k−1);
a coefficient calculation part which inputs thereinto said element ai of GF(q) (1≦i≦k−1) and said correcting factors β[iq/k] (1≦i≦k−1), then calculates aiβ[iq/k]mod q, then, letting aiβ[iq/k]/(q), rearranges a0 and aiβ[iq/k]/(q) (1≦i≦k−1) in an order of corresponding to said new polynomial bases, and outputs them as coefficients of said new polynomial bases; and
an output part which represents the output from said coefficient calculation part as a vector of aq, and outputs, as a polynomial representation of said aq, the result of addition of the results of multiplication of respective elements of said polynomial bases arranged in ascending order of powers by the corresponding coefficients.
20. The apparatus of claim 19, wherein: said coefficient calculation part comprises memory means, a termwise processing part and a replacement processing part; said memory means stores pre-computed correcting factors β[iq/k] (1≦i≦k−1); said termwise processing part inputs thereto said element ai of GF(q) (1≦i≦k−1) and said β[iq/k] (1≦i≦k−1) read out of said memory means, and calculates aiβ[iq/k]mod q; and said replacement processing part rearranges a0 and aiβ[iq/k]/(q) (1≦i≦k−1) in anew order corresponding to said new polynomial bases {1=α0, αiq/(k) (1≦i≦k−1)} arranged in ascending order of powers, and outputs them as coefficients of the corresponding bases.
23. The apparatus of claim 21, further comprising multiplication-addition means which inputs thereto said a0 and a′i (0<i<k) from said multiplying means, then calculates a multiplication-addition a 0 + ∑ i = 1 k - 1   a i  β   q - 1 k  α i
and outputs it as a polynomial representation of said aq.
(A) inputting said GF(qk)-rational point P, a Frobenius map φ defined over said elliptic curve E/GF(q), an integer k, and a prime q exceeding 3 or a power of said prime;
(B) calculating integers r and ci, where 0≦i<r, 0≦r≦k, −q≦ci≦q, which satisfy m = ∑ i = 0 r - 1   c i  φ i (1b)
(C) generating, by the use of said GF(qk)-rational point P and said integers r and ci, r points P0 to Pr−1 such that
(D) calculating mP = ∑ i = 0 r - 1   c i  φ i  P (2b)
for said r points P0 to Pr−1; and
(E) outputting said mP.
25. The method of claim 24, wherein said step (D) comprises the steps of:
(D-1) obtaining a value Sd by adding all Pi for i which correspond to ci not exceeding d; and
(D-2) obtaining said mP by S = ∑ d = 0 b   S d
(D-1) obtaining cij from the following equation: c i = ∑ j = 0 [ log 2   b ]   2 j  c ij ,
(D-2) calculating Sj from the following equation: S j = ∑ i = 0 k - 1   c ij  P i ; and
(D-3) obtaining said mP by calculating the following equation: S = ∑ j = 0 [ log 2   b ] - 1   2 j  S j
(D-1) calculating Sj from the following equation: S j = ∑ i = 0 k - 1   δ ij  P i ,
where δij=1 for those m=j and δij=0 otherwise;
where 0≦j<b and b is the maximum among ci; and
(D-2) calculating S as mP from the following equation: S = ∑ j = 0 b - 1   j   S j
28. The method of claim 24, wherein said step (D) is a step of obtaining S0 as said mP by calculating
Si=ciP+φSi+1, 0≦i<r (3b)
said step (C) includes a step of calculating
said step (D) is a step of performing the calculation of said Equation (3b) as
Si=Pi+φSi+1, where 0<i≦r,
said step (D) is a step of calculating said Equation (1b) as
Si=Pi+φSi+1
where 0≦i<r.
when it holds for said GF(qk)-rational point P over said elliptic curve, c′i and r′ that satisfy ∑ i = 0 r - 1   c i  φ i = ∑ i = 0 r ′ - 1   c i ′  φ i
for a ci-sequence obtained by said step (B) and for said r and providing them as said ci and r to said step (D), and wherein said step (D) calculates the right-hand side of said Equation (2b) using said ci and r generated in said base-φ expansion adjustment step.
said step (D) includes a step of obtaining Sd by adding together all Pi for those i which correspond to ci not exceeding d and calculating said Equation 2-B by S = ∑ d = 0 r   S d ;
said base-φ expansion adjustment step includes a step of transforming ci to reduce their absolute values through utilization of
said step (D) is a step of determining cij by c i = ∑ j = 0 [ log   b ]   2 j  c ij ,
where 0≦cij≦1, [log b] is the maximum integer smaller than b and b is the maximum value of |ci|, and obtaining said mP by S j = ∑ i = 0 k - 1   c ij  P i S = ∑ j = 0 [ log   b ] - 1   2 j  S j ;
said base-φ expansion adjustment step includes a step of transforming ci to minimize the Hamming weight represented by the number of values of other digits than those 0 of a binary or signed binary number of said ci, through utilization of
35. The method of claim 24, 31, or 32, wherein said step (4) is a step of inputting P1, P2, . . . , Pn as points P over said elliptic curve, and m1, m2, . . . , mn as said integer m to obtain said mP by ∑ i = 0 n   m i  P i
36. The method of claim 35, wherein said step (C) is a step of increasing the efficiency of the calculation by obtaining at least one part of Si1, Si2, . . . , Sin, where 0≦ik≦1, which are obtained from said points P1, P2, . . . , Pn by S i   n = ∑ k = 1 n   i k  P k
37. The method of claim 35, wherein the efficiency of the calculation by said step (D) is increased by externally inputting at east one it part of Si1, Si2, . . . , Sin, where 0<ik<1, which are obtained from said points P1, P2, . . . , Pn by S i   n = ∑ k = 1 n   i k  P k
said step (B) includes a step for calculating r and ci, where 0≦i<r, 0≦r<k and −q<ci<q, which satisfy m = ∑ i = 0 r - 1   c i  φ i
said step (C) includes a step for calculating r×s GF(qk)-rational points Rt,i (0≦t<s, 0≦i<r) over E/GF(q) for the input thereto of an integer r and s GF(qk)-rational points Qt=dtaP (0≦t<s) over E/GF(q) pre-computed with P where, letting C=1+max|ci|, a, d and s are positive integers that satisfy a×s≧logd, calculates; and
said step (D) is a pre-computed table reference addition step for calculating cj,t,iεB such that c i = ∑ j = 0 a - 1   ∑ t = 0 s - 1   d j + ta  c j , t , i (4b)
where B is assumed to be a finite set of integers and low in order, and for obtaining said mP by mP = ∑ j = 0 a - 1   ∑ i = 0 r - 1   ∑ t = 0 s - 1   d j  c j , t , i  R t , i . (5b)
(F) calculating T j = ∑ j = 0 r - 1   ∑ t = 0 s - 1   c j , t , i  R t , i ; and (6b)
(G) calculating said mP by mP = ∑ j = 0 a - 1   d j  T j . (7b)
wherein, in said step (F), a Cj,t,i-multiplication is performed only by 0-multiplication and 1-multiplication in said equation (6b).
said set B is {-1, 0, 1}; and
wherein, in said step (F), a Cj,t,i-multiplication is performed only by (−1)-multiplication, 0-multiplication and 1-multiplication in said equation (6b).
said power operating step comprises:
a polynomial basis calculation step inputting, of the order q of a finite field GF(q) defined such that f(x) is expressed in the form of xk−β, where βεGF(q), and the degree k set to be relatively prime to said order q, and calculating iq mod k (1≦i≦k−1), then, letting iq/(k) represent the calculated results, rearranging a0=1 and αiq/(k) (1≦i≦k−1) in ascending order of powers and outputting them as new polynomial bases;
a correcting factor calculation step of inputting said order q, said degree k and said β, then dividing iq (1≦i≦k−1) by k to obtain an integer [iq/k] with its fraction portion dropped, and calculating β[iq/k] (1≦i≦k−1) as correcting factors of said element ai of GF(q) (1≦i≦k−1);
a coefficient calculation step of inputting said element ai of GF(q) (1≦i≦k−1) and said correcting factors β[iq/k] (1≦i≦k−1), then calculating aiβ[iq/k]mod q, then, letting aiβ[iq/k]/(q), rearranging a0 and aiβ[iq/k]/(q) (1≦i ≦k−1) in an order of corresponding to said new polynomial bases, and outputting them as coefficients of said new polynomial bases; and
an output step of representing the output from said coefficient calculation part as a vector of aq, and outputting, as a polynomial representation of said aq, the result of addition of the results of multiplication of respective elements of said polynomial bases arranged in ascending order of powers by the corresponding coefficients.
43. The method of claim 42, wherein said coefficient calculation step comprises:
storing step of pre-computed correcting factors β[iq/k] (1≦i≦k−1) in memory means;
termwise processing step of calculating aiβ[iq/k]mod q based on said element ai of GF(q) (1≦i≦k−1) and said β[iq/k] (1≦i≦k−1) read out of said memory means; and
replacement processing step of rearranging a0 and ajβ[iq/k]/(q) (1≦i≦k−1) in a new order corresponding to a new polynomial bases {1=α0, αiq/(k) (1≦i≦k−1)} arranged in ascending order of powers, and outputting them as coefficients of the corresponding bases.
44. The method of claim 42, which further comprises: an inputting step of inputting βi[(q−1)/k] pre-computed for all integers i that satisfy an inequality 0<i<k using the order q of said finite field GF(q), an extension degree k set to exactly divide q−1 and β; and
multiplying step of inputting said a1, a2, . . . , ai, . . . , ak−1, then calculating aiβi[(q−1)/k] for said all integers i that satisfy said inequality 0<i<k, and outputting each aiβi[(q−1)/k] (0<i<k) as an element a′i of said vector representation of aq corresponding to a basis αj.
45. The method of claim 44, wherein said inputting step reads out pre-computed βi[(q−1)/k] (0<i<k) from memory means for use in said multiplying step.
46. The method of claim 44, further comprising a multiplication-addition step of inputting said a0 and a′i (0<i<k) from said multiplying step, then calculating a multiplication-addition a 0 + ∑ i = 1 k - 1   a i  β   q - 1 k  α i
and outputting it as a polynomial representation of said aq.
(B) calculating integers r and ci, where 0≦i<r, 0≦r≦k, −q≦ci≦q, which satisfy m = ∑ i = 0 r - 1   c i  φ i (1c)
(D) calculating mP = ∑ i = 0 r - 1   c i  φ i  P (2c)
48. The recording medium of claim 47, wherein said step (D) comprises the steps of:
(D-2) calculating Sj from the following equation: S j = ∑ i = 0 k - 1   C ij  P i ;
(D-3)-obtaining said mP by calculating the following equation: S = ∑ j = 0 [ log 2   b ] - 1   2 j  S j
50. The recording medium of claim 47, wherein said step (D) comprises the steps of:
where δij=1 for those m=j and δij=0 otherwise; and
Si=ciP+φSi+1, 0≦i<r (3c).
52. The recording medium of claim 51, wherein:
said step (D) is a step of performing the calculation of said Equation (3c) as
where 0≦i<q; and
said step (D) is a step of calculating said Equation (1c) as
when it holds for said GF(qk)-rational point P over said elliptic curve, c′i and r′ that satisfy ∑ i = 0 r - 1   c j  φ i = ∑ i = 0 r ′ - 1   c i ′  φ i
for a ci-sequence obtained by said step (B) and for said r and providing them as said ci and r to said step (D), and wherein said step (D) calculates the right-hand side of said Equation (2c) using said ci and r generated in said base-φ expansion adjustment step.
said step (D) includes a step of obtaining Sd by adding together all Pi for those i which correspond to cj not exceeding d and calculating said Equation (1c) by S = ∑ d = 0 r   S d ;
58. The recording medium of claim 47, 54, or 55, wherein said step (D) is a step of inputting P1, P2, . . . , Pn as points P over said elliptic curve, and m1, m2, . . . , mn as said integer m to obtain said mP by ∑ i = 0 n   m i  P i .
59. The recording medium of claim 58, wherein said step (C) is a step of increasing the efficiency of the calculation by obtaining at least one part of Si1, Si2, . . . , Sin, where 0≦ik≦1, which are obtained from said points P1, P2, . . . , Pn by S i   n = ∑ k = 1 n   i k  P k .
60. The recording medium of claim 58, wherein the efficiency of the calculation by said step (D) is increased by externally inputting at east one part of Si1, Si2, . . . , Sin, where 0<ik<1, which are obtained from said points P1, P2,. . . , Pn by S i   n = ∑ k = 1 n   i k  P k .
61. The recording medium of claim 47, wherein:
said step (B) includes a step for calculating r and ci, where 0≦i≦r, 0≦r<k and −q<ci<q, which satisfy m = ∑ i = 0 r - 1   c i  φ i
said step (C) includes a step for calculating r×s GF(qk)-rational points Rt,i (0≦t<s, 0≦i<r) over E/GF(q) for the input thereto of an integer r and s GF(qk)-rational points Qt=dtaP (0≦t<s) over E/GF(q) pre-computed with P where, letting C=1+max|ci|, a, d and s are positive
integers that satisfy axs≧logd, calculates; and
said step (D) is a pre-computed table reference addition step for calculating cj,t,iεB such that c i = ∑ j = 0 a - 1   ∑ t = 0 s - 1   d j + ta  c j , t , i (4c)
where B is assumed to be a finite set of integers and low in order, and for obtaining said mP by mP = ∑ j = 0 a - 1   ∑ i = 0 r - 1   ∑ t = 0 s - 1   d j  c j , t , i  R t , i . (5c)
62. The recording medium of claim 61, wherein said program further comprises steps of:
(F) calculating T j = ∑ j = 0 r - 1   ∑ t = 0 s - 1   c j , t , i  R t , i   and (6c)
(G) calculating said mP by mP = ∑ j = 0 a - 1   d j  T j . (7c)
63. The recording medium of claim 62, wherein:
wherein, in said step (F), a Cj,t,i-multiplication is performed only by 0-multiplication and 1-multiplication in said equation (6c).
said set B is {−1, 0, 1}; and wherein, in said step (F), a Cj,t,i-multiplication is performed only by (−1)-multiplication, 0-multiplication and 1-multiplication in said equation (6c).
65. The recording medium of claim 47, wherein: letting GF(qk) represent a k-degree extension field of GF(q), letting GF(qk)-{0} represent an algebraic system GF*(qk), letting a represent a root of a k-degree irreducible polynomial on GF(q) and letting an element a of GF(qk) be represented by a polynomial in the form of a=a0+a1α+a2α2 . . . +ak−1αk−1 using an element ai (0≦i<k) of GF(q) and an element a of GF*(qk), said step (C) includes polynomial-basis power operating step of calculating a power of said a, aq=a0+a1αq+a2α2q . . . +ak−1α(k−1)q;
a polynomial basis calculation step inputting, of the order q of a finite field GF(q) defined such that f(x) is expressed in the form of xk−β, where βεGF(q), and the degree k set to be relatively prime to said order q, and calculating iq mod k (1≦i≦k−1), then, letting iq/(k) represent the calculated results, rearranging α0=1 and αiq/(k) (1≦i≦k−1) in ascending order of powers and outputting them as new polynomial bases;
a correcting factor calculation step of inputting said order q, said degree k and said β, then dividing iq (1<i≦k−1) by k to obtain an integer [iq/k] with its fraction portion dropped, and calculating β[iq/k] (1≦i≦k−1) as correcting factors of said element ai of GF(q) (1≦i≦k−1);
a coefficient calculation step of inputting said element ai of GF(q) (1≦i≦k−1) and said correcting factors β[iq/k] (1<i≦k−1), then calculating aiβ[iq/k]mod q, then, letting aiβ[iq/k]/(q), rearranging a0 and aiβ[iq/k]/(q) (1≦i≦k−1) in an order of corresponding to said new polynomial bases, and outputting them as coefficients of said new polynomial bases; and
66. The recording medium of claim 65, wherein said coefficient calculation step comprises:
replacement processing step of rearranging a0 and aiβ[iq/k]/(q) (1≦i≦k−1) in a new order corresponding to a new polynomial bases {1=α0, αiq/(k) (1≦i≦k−1)} arranged in ascending order of powers, and outputting them as coefficients of the corresponding bases.
67. The recording medium of claim 65, which further comprises: an inputting step of inputting βi[(q−1)/k] pre-computed for all integers i that satisfy an inequality 0<i<k using the order q of said finite field GF(q), an extension degree k set to exactly divide q−1 and β; and
68. The recording medium of claim 67, wherein said inputting step reads out pre-computed βi[(q−1)/k] (0<i<k) from memory means for use in said multiplying step.
69. The method of claim 67, further comprising a multiplication-addition step of inputting said a0 and a′i (0<i<k) from said multiplying step, then calculating a multiplication-addition a 0 + ∑ i = 1 k - 1   a i  β   q - 1 k  α i
The present invention relates to an elliptic-curve arithmetic method and an apparatus therefor and, more particularly, to an apparatus and method for implementing information security techniques (elliptic-curve cryptosystem/signature, factoring) and a recording medium having recorded thereon a program for implementing the method.
It is possible to define an addition and a doubling for a point P over the elliptic curve. These addition and doubling will hereinafter be referred to as “elliptic curve addition” and “elliptic curve doubling” in distinction from ordinary additions and doublings. Of points over the elliptic curve, the identity element of addition will be represented by O. It is customary in the art to construct the m-multiplications (m is 2 or greater integer) by the combined use of the “elliptic curve addition” and the “elliptic curve doubling.” In this specification, the GF(q)-rational point refers to that one of points defined over an elliptic curve whose coordinates are expressed by the element of GF(q).
In some cases, a “Frobenius map” may also be used to compute the m-multiplications. This scheme will hereinafter be called a “base-φ expansion method. Goblitz et al. have proposed a method for m-multiplying a GF(2k)-rational point (k is 2 or greater integer) over the elliptic curve E/GF(2) defined over the finite field GF(2). As described below, however, this method accelerates the multiplication only when q is very small.
φ: (x, y)→(xq, yq)
for a point P=(x, y), where x, yεEGF(q)′, on the elliptic curve. GF(q)′ is an algebraic closure of GF(q).
φ2−[[t]]φ+[[q]]=[[0]], −2{square root over (q)}<t<2{square root over (q)} (1)
Equation (1) has an imaginary root and permits a multiplication different from [[m]] with φ. φ is a value that is determined uniquely to a given elliptic curve, and it can be calculated by known methods.
Let α denote a generator of the normal basis. In the normal basis representation, an element aεEGF(qk) is represented by a=[a0, a1, . . . , ak-1] using aiεEGF(q) which provides a = ∑ i = 0 k - 1   a i  α qi ( 2 )
At this time, aq=[ak−1, a0, a1, . . . , ak−2], and the map φ can be applied by the element replacement.
In the base-φ expansion method, the first step is to transform mP using φ as follows: mP = ∑ i = 0 r   c i  φ i  P ( 3 )
where −q<ci<q and r≅k.
Koblitz presented an m-multiplication algorithm for GF(2k))-rational points over E/GF(2) through utilization of the base-φ expansion method (N. Koblitz. “CM-Curves with Good Cryptographic Properties,” CRYPTO' 91, pp.279-287 (1991)). And, Solinas proposed an improved version of the algorithm (J. A. Solinas, “An Improved Algorithm for Arithmetic on a Family of Elliptic Curves,” CRYPTO' 97, pp.357-371 (1997)). With these algorithms, −1≦ci1 and the m-multiplication can be computed by a maximum of r Frobenius map calculations and elliptic curve additions.
9P=(2×2×2+1)P (4)
The calculation of Equation (4) requires three “elliptic curve doublings” and one “elliptic curve addition” (a total of four computations).
9P=(φ5−φ3+1)P (5)
The calculation of Equation (5) can be conducted by two “elliptic curve additions” since the calculation of φ5P and φ3P takes negligible time. Hence, the computational time can be made shorter than in the case of using Equation (3).
It is an object of the present invention to provide an arithmetic method which permits m-multiplication over an elliptic curve defined over a finite field GF(qk) by the base-φ expansion method irrespective of the magnitude of a prime q, and apparatus for implementing the arithmetic method and a recording medium having recorded thereon a program for implementing the method,
calculating integers r and ci which satisfy the following equation, by using the Frobenius map φ m = ∑ i = 0 r - 1   c i  φ i
where 0≦i<r, 0≦r≦k and −q≦c1≦q;
calculating the following equation: mP = ∑ i = 0 r - 1   c i  φ i  P
by table reference addition means supplied with the r points P0 to Pr−1; and outputting the calculated mP by outputting means.
FIG. 1 is a block diagram illustrating an elliptic-curve m-multiplying apparatus according to the present invention;
Provided that the Frobenius map can be computed fast, the computation of Equation (8) can be performed by the same processing as that of a power operation method using a table with pre-computed data (hereinafter referred to as a “table reference method”).
P0=P, P1=φP, . . . , Pk−1=φk−1P (6)
where k is 2 or greater integer, and Pi is used to perform the m-multiplication by the same method as that of Equation (7) as described later on.
Table Reference Method
In the case of computing mP (which will hereinafter be referred to as an m-multiplication) using a certain elliptic curve point P and m which varies each time, the computation can be conducted fast using the table reference method.
B (m-multiplication): Compute ci such that m=Σiaici and then compute mP using the pre-computed Pi by mP = ∑ i  c i  P i ( 7 )
The table reference method is classified into a “BGMW method”, a “comb method”, a “box method” and a “window method” according to the method of constructing Equation (7). Some table reference methods will be described below in brief. In practice, other table reference methods and combinations thereof are also available. Any table reference methods can be used in the present invention.
In the following description, let log use base 2 and let [x] denote a maximum integer equal to or smaller than x. Let b and k be 2 or greater integers, mi denote a base-b expanded value of m and mij a binary-expanded value (0 or 1) of mi (an integer satisfying 0 mi≦b−1). That is, m = ∑ i = 0 k - 1   m i  b i ( 8 ) m i = ∑ j = 0 [ log   b ]   m ij  2 j ( 9 )
BGMW Method
A (Pre-computation):
P0=P, P1=bP, . . . , Pk−1=bk−1P
B (m-multiplication):
Step 2: Output S = ∑ d = 0 b   S d ( 10 )
B (m-multiplication)
Step 1: S j = ∑ i = 0 k - 1   m ij  P i   ( 0 < j < [ log   b ] + 1 ) ( 11 )
Step 2: S = ∑ j = 0 [ log   b ]   2 j  S j ( 12 )
P0P, P1=bP, . . . , Pk−1=bk−1P
Step 1: S j = ∑ i = 0 k - 1   δ ij  P i ( 13 )
where δij=1 for m=j and δij=0 otherwise.
Step 2: S = ∑ j = 0 b - 1  jS j ( 14 )
P1=P, P2=2P, . . . , Pb−1=(b−1)P
B (m-multiplication): Output S = ∑ i  b i  P i .
In the case of using any one of the BGMW, comb and box methods, the results obtained using the Frobenius map φ (Equation (6)) are regarded as pre-computed values. In the case of using the Window method, the Frobenius map is applied to the b-multiplying part in the m-multiplying part.
FIG. 1 is a block diagram illustrating an elliptic-curve m-multiplying apparatus according to a first embodiment of the present invention. Elliptic-Curve m-Multiplying Apparatus (FIG. 1)
Step S2: For the inputs thereto k, φ, and m, the base-φ expansion part 20 calculates and outputs C0, c1, . . . , cr−1 and r that satisfy the following equation: m = ∑ i = 0 r - 1   c i  φ i  ( mod   φ k - 1 ) ( 15 )
Step S3: For the inputs thereto q, P, k, and r, the Pi generation part 10 calculates and outputs P0, P1, . . . , Pr−1 that satisfy the following equation:
Pi=φiP
Step S4: For the inputs thereto E, Pi and ci, the table reference addition part 30 calculates the following equation: mP = ∑ i = 0 r - 1   c i  P i ( 16 )
and outputs mP.
FIG. 7 illustrates an example of the configuration of the base-φ expansion part 20 which calculates, for the inputs thereto of the definition field size q, the extension order k, the integer m and the Frobenius map φ, and outputs c0, c1, . . . , cr−i and r which satisfy the following equation: m = ∑ i = 0 r - 1   c i  φ i ( 17 )
The base-φ expansion part 20 comprises a trace computing part 21, a control part 22, a memory 23 and a residue part 24.
φ2−tφ+q=0 (18)
Step S3: The residue part 24 computes for the inputs thereto m, φ and k, values x and y which satisfy the following equation and stores them in the memory 23.
x+yφ≡m(mod φk−1) (19)
It is also possible to input pre-computed values x and y from an external source. In such an instance, the input values are x and y in place of the integer m. When this arithmetic operation is not performed, the residue part 24 is unnecessary.
u←x mod q and
v←(x−u)/q (20)
Step S6: Check whether u=0 or 2x+ty>2u−q.
Elliptic-Curve m-Multiplying Apparatus (FIG. 15)
Pi=iP
Step S4: For the inputs E, Pi and ci the power table addition part 30 calculates the following equation: mP = ∑ i = 0 r - 1   φ i  P i ( 21 )
FIG. 19 illustrates an example of the configuration of a table reference addition part 30D, which calculates the following equation for the input thereto of elliptic curve E, elliptic-curve points P0, P1, . . . , Pr−1 and integers c0, c1, . . . , cr−1 and outputs mP. mP = ∑ i = 0 r - 1   c i  φ i  P ( 22 )
The table reference addition part 30D comprises a memory 31D, a control part 32D, an elliptic-curve addition part 33D and Frobenius mapping means 34D. The Frobenius mapping means 34D has the same configuration as depicted in FIG. 5 or 6.
Elliptic-Curve (m and n)-Multiplying Apparatus (FIG. 21)
Step S2: For the inputs k, φ and m, the base-φ expansion part 21 calculates and outputs c0, c1, . . . , cr m −1 and rm (0<i<rm) that satisfy the following equation: m = ∑ i = 0 r m - 1   c i  φ i  ( mod   φ k - 1 ) ( 23 )
Step S3: For the inputs k, φ and n, the base-φ expansion part 22 calculates and outputs d0, d1, . . . , dr n −1 and rn (0<i<rn) that satisfy the following equation: n = ∑ i = 0 r n - 1   d i  φ i ( 24 )
Step S4: The comparison part 50 outputs a larger one of the inputs rm and rn as r.
for the inputs q, P, k and r and outputs P0, P1, . . . , Pr−1.
Qi=φiQ
for the input q, Q, k and r and outputs Q0, Q1, . . . , Qr−1.
Ri=Pi for 0≦i<r
=Qi−r for r≦i<2r
e i =  c i  for   0 ≤ i < r =  d i - r  for   r ≤ i < 2  r
then calculates mP + nQ = ∑ i = 0 2  r - 1   e i  R i ( 25 )
and outputs mP+nQ.
m1P+m2Q+m3R+. . . (26)
In FIGS. 1 and 15, the Pi generation part 10 may be combined with the table reference addition part 30 (30D) into one arithmetic unit. Moreover, the Pi generation part 10 in FIG. 15 may be configured to be supplied with an externally pre-computed version of Pi=iP.
In the first, second and third embodiments described above, the aforementioned Equation (6) is regarded as a pre-computed value and Pi is used to perform the m-multiplication in the same fashion as in the case of Equation (7). However, this method is not always higher in efficiency than in the case of the conventional method using GF(2k). Next, a description will be given of an embodiment which is adapted to reduce the number of operations in the table reference addition part 30 by adjusting or controlling r and ci.
(φk−1)P=0
The number of terms of ci can be decreased through utilization of this relationship.
m=c0+c1φ+c2φ2+c3φ3
when k=3.
m=c′0+c′1φ+c′2φ2
c′0=c0+c3=7
c′1=c1=5
c′2=c2=1
With this scheme, it is possible to convert ci to c′i, thereby decreasing the number of terms to k.
The table reference addition methods using pre-computation differ in processing speed according to the input value of ci. For example, in the case of the “comb-type method” described previously with reference to FIG. 9, the processing time increases with an increase in the number of “1's” (which will hereinafter be referred to as a Hamming weight) of respective digit values (0 or 1) which express ci in binary digit.
(φk−1+φk−2+. . . +φ+1)P=0
since (φk−1)=0 and since (φ−1)≠0. For instance, consider the case where c0=7, c1=5, and c2=1 at the time of calculating mP by using
m=c0+c1φ+c2φ2
when k=3. Let it be assumed here that P is the GF(qk)-rational point and that (φ2+φ+1)P=0 holds. These ci's in binary representation are as follows:
c0=7=1112
c1=5=1012
c2=1=0012
and the number of 1's (the Hamming weight) is 6. By the way, since
φ2+φ1+1=0,
even if the same number is added to or subtracted from each ci, the following equation holds:
m=c0+c1φ+c2φ2.
Then, setting c′i=ci−1, it follows that
c′0=6=1102
c′1=4=1002
c′2=0=0002.
Thus, the Hamming weight can be reduced to 3. Further, by setting c″i=c′1−4, it follows that
c″0=2=0102
c″1=0=0002
c″2=−4={overscore (1)}002
where the symbol {overscore ( )} over a digit represents a negative sign. Thus, the Hamming weight can be reduced to 2.
Step S2: For the inputs k, φ and m the base-φ expansion part 20 calculates and outputs c0, c1, . . . , cr−1, and r that satisfy the following equation: m = ∑ i = 0 r - 1   c i  φ i  ( mod   φ i - 1 ) ( 27 )
Step S3: For the inputs thereto of r and ci from the base-φ expansion part 20, the base-φ expansion adjustment part 40 calculates and outputs c′0, c′1, . . . , c′r−1 and r′ that satisfy the following equation: ∑ i = 0 r - 1   c i  φ i = ∑ i = 0 r ′ - 1   c i ′  φ i ( 28 )
Step S4: For the inputs thereto of q, P, k and r′ the Pi generation part 10 calculates P0, P1, . . . , Pr′−1 from
Step S5: For the input thereto of E, Pi, c′i and r′ the table reference addition part 30 calculates and outputs mP that satisfies the following equation: mP = ∑ i = 0 r ′ - 1   c i ′  P i ( 29 )
Base-φ Expansion Adjustment Part (FIG. 25)
FIG. 25 illustrates in block form the base-φ expansion adjustment part 40, which comprises an addition part 41, an α generation part 42 and a subtraction part 43. The base-φ expansion adjustment part 40 calculates, for the inputs thereto of integers c0, c1, . . . , cr−1, r and k, integers c′0, c′1, . . . c′r−1 and r′ that satisfy the following equation ∑ i = 0 r - 1   c i  P i = ∑ i = 0 r ′ - 1   c i ′  P i ( 30 )
When the table reference addition part 30 used is the comb type depicted in FIG. 9, the α generation part 42 calculates si by s i = 1   for   ∑ j = 0 k - 1   c i , j ′′ > k / 2 = 0   for   ∑ j = 0 k - 1   c i , j ′′ ≤ k / 2 ( 31 )
where c″i,j (0 or 1) is a j-th digit value of c″i expressed in binary digit, then calculates α = ∑ i = 0 [ log 2   b ] + 1   s i  2 i ( 32 )
where b is the maximum one of cij using si, and outputs it.
Elliptic-Curve (m and n)-Multiplying Apparatus (FIG. 28)
Step S2: For the inputs k, φ and m, the base-φ expansion part 21 calculates and outputs c0, c1, . . . , cr m −1 and rm that satisfy the following equation: m = ∑ i = 0 r m - 1   c i  φ i ( 33 )
Step S3: For the inputs k, φ and n, the base-φ expansion part 22 calculates and outputs d0, d1, . . . , dr n −1 and rn that satisfy the following equation: n = ∑ i = 0 r n - 1   d i  φ i ( 34 )
Step S4: For the inputs rm and ci, the base-φ expansion adjustment part 40A calculates and outputs c′i and r′m that satisfy the following equation: ∑ i = 0 I m - 1   c i  φ i = ∑ i = 0 r m ′ - 1   c i ′  φ i ( 35 )
Step S5: For the inputs rm and di, the base-φ expansion adjustment part 40B calculates and outputs d′i and r′n that satisfy the following equation: ∑ i = 0 r n - 1   d i  φ i = ∑ i = 0 r n ′ - 1   d i ′  φ i ( 36 )
Step S6: The comparison part 50 outputs a larger one of the inputs r′m and r′n as r.
Pi=φiP (37a)
Qi=φiQ (37b)
Step S9: For the inputs E, r, Pi, Qi, c′i and d′i, the table reference addition part 30 sets R i =  P i  for   0 ≤ i < r =  Q i - r  for   r ≤ i < 2  r e i =  c i ′  for   0 ≤ i < r =  d i - r ′  for   r ≤ i < 2  r ( 38 )
then calculates mP+nQ by mP + nQ = ∑ i = 0 2  r - 1   e i  R i ( 39 )
m1P+m2Q+m3R +. . . .
The fourth and fifth embodiments permits construction of the reference table without involving the pre-computation, and hence they have a wider range of applications than the conventional table reference addition method; they can be applied, for example, to the signature verification of an elliptic-curve DSA signature scheme.
A typical conventional base-φ expansion method calculates first cj,i that satisfies the following equation: c i = ∑ j = 0 b - 1   2 j  c j , i ( 40 )
(where cj,iε{0, 1} and b is an integer of b≧log2 ci)
using ci (0≦i<k) obtained by the base-φ expansion, then calculates S j = ∑ i = 0 r - 1   c ij  φ i  P ,  0 ≤ j < b ( 41 )
an computes the following equation using Sj: S = ∑ j = 0 b - 1   2 j  S j ( 42 )
thereby obtaining mP. In this case, mP is calculated by performing b−1 “elliptic-curve doublings” in the form of
S=2(2( . . . 2(2(Sb−1)+Sb−2)+ . . . S2)+S1)+S0
The “elliptic-curve addition” and the “elliptic-curve doubling” are far more time-consuming than the φ-multiplication. Attempts have been made to accelerate the “elliptic-curve addition” but no schemes have yet been introduced for faster “elliptic-curve doubling,” which still remains as a bottleneck in the elliptic-curve multiplication.
Output: Value of polynomial f  ( x ) = ∑ j = 0 b - 1   u j  x j
Temporary storage area: Element f of L, integer j
Step 3: f←f×x+uj
Step 4: j←j−1
Output: Value of polynomial f  ( x ) = ∑ j = 0 2  a - 1   u j  x j
Temporary storage area: Element f of L and integer j
Step 3: f←f×x+uj+uj+axa
The calculation of Equation (42) conducted by the conventional base-φ expansion method is none other than the calculation by the Horner's method with L as an integer, uj as a value which satisfies ujP=Sj and x=2. The calculations of Sj (0≦j<b) are usually performed one after another during the execution of the Horner's method. This will be described below by way of simple examples with respect to FIGS. 30A, 30B and 30C. These drawings are schematic showings of processing in the table reference addition part employed in the conventional base-φ expansion method. For the sake of simplicity, let it be assumed that the base-φ expansion coefficient is represented by a binary number or signed binary number of 20 digits from 19th to 0th digit. The traditional table reference addition part receives P, φP, φ2P, c0, c1 and c2 and outputs the value of ∑ i = 0 2   c i  φ i  P ( 43 )
FIGS. 30A, 30B and 30C each represent the processing therefor. Reference character S denotes a temporary storage area which stores the coordinates of elliptic-curve points for computation and holds the value of Equation (43) that is the output of this part at the final stage of computation.
In FIG. 30A, ci,j denotes the numerical value of a j-th digit when the input ci is expressed in the binary or signed binary number of 20 digits from 10th to 0th digit. Accordingly, ci,j is a numerical value that is 0 or ±1, and ci,j-multiplication can be performed easily. Usually, only when this numerical value is other than 0, the “elliptic-curve addition” takes place. In FIG. 30A, the first step is to calculate S19 concerning the 19th digit that is the most significant digit of each of the inputs c0, c1 and c2. The results of the calculation on S19 do not necessarily require the temporary storage area, but they need only to be sequentially written into the temporary storage area for the calculation of Equation (43).
If pre-computed data can be prepared in place of Sj (0≦j<b), then the number of “elliptic-curve doublings” can be cut as is possible with the improved version of the Homer's method.
Tj=Sj+2aSa+j,(0≦j<a) (44)
the following equation needs only to be calculated by the Homer's method: S = ∑ j = 0 a - 1   2 j  T j ( 45 )
If 2aP points over the elliptic curve can be prepared beforehand in addition to point P, Tj can be constructed only by slightly improving the method of calculating S while constructing Sj (0≦j<b) from P as in the conventional base-φ expansion method.
In FIG. 31 to 33, ci,j denotes the numerical value of a j-th digit when the input ci is expressed by the binary or signed binary number of 20 digits from 10th to 0th digit. Accordingly, ci,j is a numerical value that is 0 or ±1 and ci,j-multiplication can be performed easily. Usually, only when this numerical value is other than 0, the “elliptic-curve addition” takes place. In FIGS. 32 and 33, Q0=P and Q1=210P in the interests of simplicity.
The Frobenius map can be computed far faster than the “elliptic-curve addition” and the “elliptic-curve doubling.” Hence, P, φP, φ2P, 210P, φ210P and φ2210P could be computed very fast if P and 210P are prepared beforehand.
Accordingly, in the case of this example, the number of “elliptic-curve doublings” can be reduced by half only by preparing 210P in addition to P.
Step S1: For the inputs thereto k, φ and m the base-φ expansion part 20 calculates and outputs c0, c1, . . . , cr−1 and r that satisfy the following equation: m = ∑ i = 0 r - 1   c i  φ i ( 46 )
Step S2: For the inputs thereto q, k, r, P and 22aP, . . . , 2(s−1)aP, the Rt,i generation part 10 calculates Rt,i(0≦i<r, 0≦t<s) by
Rt,i=φi2taP (47)
Step S3: For the inputs thereto E, Rt,i, ci and r, the pre-computed table reference addition part 30 calculates cj,t,i that satisfies c i = ∑ j = 0 a - 1   ∑ t = 0 s - 1   d j + ta  c j , t , i
then calculates mP by the following equation: mP = ∑ j = 0 a - 1   ∑ t = 0 s - 1   ∑ i = 0 r - 1   d j  c j , t , i  R t , i ( 48 )
Rt,i=φi2taP.
The Frobenius mapping means 14 is identical with that used in FIG. 5 or 6 embodiment in construction and in operation; hence, no description will be repeated. It is also possible to obtain φQt in parallel from a plurality of points on a point sequence Qt by using a plurality of Frobenius mapping means 14.
Step S10: If x=0 and y=0 in step S4, then the base-φ expansion correcting part 25 calculates, from the input values r′, k and c′i, values r and ci such that ∑ i = 0 r ′ - 1   c i ′  φ i = ∑ i = 0 r - 1   c i  φ i ( 49 )
and that r≦k, and outputs them.
As depicted in FIG. 40, the pre-computed table reference addition part 30 comprises a memory 31, a control part 32, an elliptic-curve addition part 33 and an elliptic-curve doubling part 34. For the inputs thereto of elliptic curve E, elliptic-curve rational point sequence Rt,i=φi2taP(0≦i<r, 0≦t<s) and integer ci (0≦t<s), the pre-computed table reference addition part 30 calculates mP by the following equation mP = ∑ i = 0 r - 1   c i  R t , i ( 50 )
Step S2: The control part 32 sets j←a−1 and S←O and stores j and S in the memory 31. Further, the control part 32 generates ct,j such that c i = ∑ t = 0 s - 1   2 ta  c t , i ( 51 )
The memory 31 passes i, t, j and S to the control part 32.
As depicted FIG. 42, the base-φ expansion correcting part 25 in FIG. 38 comprises an addition part 25A, an α generation part 25B and a subtraction part 25C as in the case of FIG. 25. For the inputs thereto of integers c′0, c′1, . . . , c′r−1, r′ and k, the base-φ expansion correcting part 25 calculates and outputs integers c0, c1, . . . , cr−1 and r that satisfy the following equation: ∑ i = 0 r ′ - 1   c i ′  P i = ∑ i = 0 r - 1   c i  P i ( 52 )
The operation of the base-φ expansion correcting part 25 is implemented by computer following the procedure of FIG. 43 as described below.
c″i=c′i+c′i+k+c′i+2k+ . . . , (0≦i<k).
Step S2: The α generation part 25B calculates ci=c″i−α from the inputs thereto c″i and k, and letting wi denote the number of digits other than 0 when ci is expressed in binary or signed binary number, the α generation part 25B calculates an appropriate at that reduces or statistically decreases ∑ i = 0 k - 1   w i ( 53 )
Step S3: The subtraction part 25C calculates and outputs ci=c″i−α (0≦i<k) and, further, outputs k as r.
In each of the embodiments described above, the Pi generation part 10 calculates Pi=φiP (0≦i<k). This calculation is to map Pi times using φ. Letting the elliptic-curve point P0 be represented by (x0, y0), the point (xi, yi) by i-times mapping becomes (Xo iq, y0 iq). That is, an arithmetic operations xq and yq performed for each mapping by the power operating parts 14A and 14B of the Frobenius mapping means 14 depicted in FIG. 5, for instance. This embodiment described below is intended to increase the efficiency of the power operations of the power operating parts 14A and 14B in the Frobenius mapping means 14.
(α, αq, αq 2 , . . . , αq k−1 )
In the case of using the polynomial basis, elements a; (0≦i<k) of the finite field GF(q) are used to provide
a={a0, a1, a2, . . . , ak−1}=a0+a1α+a2α2+. . . +ak−1αk−1.
In the case of using the normal basis, the elements a; (0≦i<k) of the finite field GF(q) are used to provide
a={a0, a1, a2, . . . , ak−1}=a0α+a1αq+a2αq 2 + . . . +ak−1αq k−1
Incidentally, since the generators of the polynomial basis and the normal basis differ in the necessary and sufficient condition, the values do not necessarily become equal to each other. (For particulars, refer to HIRAMATSU Toyokazu, “Applied Algebra,” Shohkaboh, chap. 3,3 and 3.6.)
According to Stinson, “Theory of Cryptography,” translated by Sakurai, Kyoritsu Shuppan, p.198, in the case of performing addition which is a binary operation of elements defined over an elliptic curve,
x3=λ2−x1−x2
y3=λ(x1−x3)−y1
where λ=(3x1 2+c)/(2y1) for x1=x2 and y1=y2, and in the other cases λ=(y2−y1)/(x2−x1). The value c is a quantity that depends on the parameter chosen over the elliptic curve.
αq=αq mod k×β[q/k]
α2q=α2q mod k×β[2q/k]
α3q=α3q mod k×β[3q/k]
α(k−1)q=α(k−1)q mod k×β[(k−1)q/k] (54)
where [iq/k] (0<i<k) represents an integer with the fraction portion of iq/k dropped. Since q and k are relatively prime, iq mod k≠0. Furthermore, since q≠k, jq mod k≠q mod k holds for an arbitrary integer j that satisfies 0<j≠i<k. Accordingly, each element of k−1 bases (αq mod k, α2q mod k, α3q mod k, . . . , α2q mod k) has exponents different from each other, and the bases (αq mod k, α2q mod k, α3q mod k, . . . α(k−1)q mod k) differ only in the basis (α, α2, . . . α(k−1)) and in the order of their elements but form the same space. The results of the operation iq mod k (0<i<k) will hereinafter be identified by iq/(k). The new bases are constructed by rearranging the computed bases (αq/(k), α2q/(k), α3q/(k), . . . , α(k−1)q(k)) in ascending order of powers. In the following description, the replacement operation of rearranging the newly computed bases in a manner to increase iq mod k (0<i<k) will be indicated by < >. Accordingly, <αq/(k), α2q/(k), α3q/(k), . . . α(k−1)q/(k)>={ α, α2, α3, . . . , αk−1}.
The above will be described below, for example, in connection with the case where the bit length |q| of the order q of the finite field GF(q) is 32-bit and k=5. As depicted in FIG. 45, β[q/5], β[2q/5], β[3q/5] and β[4q/5] are stored in the memory 63A, and for the inputs a0, a1, a2, a3 and a4 to the termwise processing part 63B, outputs a0, a1β[q/5], a2β[2q/5], a3β[3q/5] and a4β[4q/5] are generated. Foe instance, when q mod k=2 (i.e. q=5q+2 for a positive integer q), q mod k, 2q mod k, 3q mod k and 4q mod k become 2, 4, 1 and 3, respectively. As a result, new bases become as follows: < 1 , α q   mod   5 , α 2  q   mod   5 , α 3  q   mod   5 , α 4  q   mod   5 >=  { 1 , α 3  q / ( 5 ) , α q / ( 5 ) , α 4  q  ( 5 ) , α 2  q / ( 5 ) } =  { 1 , α , α 2 , α 3 , α 4 }   …
Accordingly, the order of the coefficients
{a0, a1β[q/5]/(q), a2β[2q/5]/(q), a3β[3q/5]/(q), a4β[4q/5]/(q)}
{a0, a3β[3q/5]/(q), a1β[q/5]/(q), a4β[4q/5]/(q), a2β[2q/5]/(q)}.
As the result of this, the replacement corresponding to the following 5 by 5 matrix is performed: ( 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 )  ( a 0 a 1  β [ q / 5 ] a 2  β [ 2  q / 5 ] a 3  β [ 3  q / 5 ] a 4  β [ 4  q / 5 ] ) = ( a 0 a 3  β [ 3  q / 5 ] a 1  β [ q / 5 ] a 4  β [ 4  q / 5 ] a 2  β [ 2  q / 5 ] ) ( 55 )
Accordingly, the vector representation of aq is
Furthermore, the polynomial basis representation of aq is
aq=a0+{a3β[3q/5]/(q)}α+{a1β[q/5]/(q)}α2+{a4β[4q/5]/(q)}α3+{a2β[2q/5]/(q)}α4.
In the FIG. 44 block diagram of the power operating part 60, there are not shown a processor which controls the power operating part to implement the operation schemes using the polynomial bases according to first and third embodiments and a control program which describes procedures necessary for implementing the operation schemes.
A description will be given of another scheme for efficient calculation of the Frobenius map, that is, the q-th power of a.
aq=a0+a1αq+a2α2q+ . . . +aiαiq . . . ak−1α(k−1)q (56)
where aiq (0≦i≦k−1) is given by the following equation applying the definition of the minimal polynomial, αk−β=0, to the minimal polynomial xk−β(βεGF(q)) of α over GF(q): α iq = α i  α i  ( q - 1 ) = α i  β i  [ ( q - 1 ) / k ] ( 57 )
Accordingly, aq is given by the following equation:
aq=a0+a1αβ[(q−1)/k]+a2α2β2[(q−1)/k]+ . . . +aiαiβi[(q−1)/k]+ . . . +ak−1α(k−1)β(k−1)[(q−1)/k] (58)
In Equation (58), since i(q−1)/k (0<i<k) is an integer, aiβi[(q−1)/k]εGF(q) (0<i<k). Hence, Equation (58) indicates that aq is expressed as the polynomial of α over GF(q).
(1) The vector representation of aq using (α0=1, α, α2, . . . , αk−1) as the basis is as follows: a q =  ( a 0 ′ , a 1 ′ , a 2 ′ , …  , a i ′ , …  , a k - 1 ′ ) =  ( a 0 , a 1  β [ ( q - 1 ) / k ] , a 2  β 2  [ ( q - 1 ) / k ] , …  , a i  β   [ ( q - 1 ) / k ] , …  ,  a k - 1  β ( k - 1 )  [ ( q - 1 ) / k ] ) ( 59 )
(2) The polynomial representation of aq using (α0=1, α, α2, . . . , αi, . . . , αk−1) as the basis is as follows: a q = a 0 + ∑ i = 1 k - 1   a i  β   q - 1 k  α i ( 60 )
The eighth embodiment of the invention will be described with reference to FIGS. 47 and 48.
xk−β(βεGF(q)) (61)
and, under the condition that k−1(q−1) (k exactly divides q−1), calculates
aq=a0+a′1α+a′2α2+ . . . +a′jαj+ . . . +a′k−1αk−1
where a′jεGF(q) and 0 j<k, as processing equivalent to aq=a0+a1αq+a2α2q+ . . . +ak−1α(k−1)q which is the q-th power of
a=a0+a1α+a2α2 . . . +ak−1αk−1
where aεGF*(qk), aiεGF(q) and 0≦i≦k−1. Here, a′i is given by the following equation:
a′i=a iβi[(q−1)/k], (0<i<k) (62)
as expressed in the aforementioned Equation (59).
The Frobenius map calculation apparatus is made up of a memory 48A, a multiplier 48B and a multiplication-addition means 48C. The memory 48A stores the following values pre-computed using preset q, β and k: β 0 = 1 , β q - 1 k , β 2  q - 1 k , β 3  q - 1 k , …  , β ( k - 1 )  q  q - 1 k ( 63 )
The multiplier 48B inputs thereinto (α0, a1, . . . ai, . . . , ak−1) from an external circuit and (1, β[(q−1)/k], β2[(q−1)/k], . . . , β2[(q−1)/k], . . . , β(k−1)[(q−1)/k]) from the memory 48A and multiplies them by the corresponding coefficients to generate
(a′0, a′1, . . . , a′i, . . . , a′k−1)=(a01, a1β[(q−1)/k], . . . , aiβi[(q−1)/k], . . . , ak−1β(k−1)[(q−1)/k])
The multiplication-addition means 48C inputs thereinto the output (a′0, a′1, . . . , a′i, . . . , a′k−1) from the multiplier 48B and (α=1, α, . . . αi, . . . αk−1) from an external circuit, then multiplies them by the coefficients corresponding thereto, then, adds together the multiplied results, and the added result as aq.
β[(q−1)/k], β2[(q−1)/k], . . . , βi[(q−1)/k], . . . , β(k−1)[(q−1)/k]
from the memory 48A and generates
(a0, a1β[(q−1)/k], a2β2[(q−1)/k], . . . , aiβi[(q−1)/k], . . . , ak−1β(k−1)[(q−1)/k])=(a′0, a′1, a′2, . . . , a′i, . . . , a′k−1) (64)
Step S3: Then, the output (a′0, a′1, a′2, . . . , a′i, . . . , a′k−1) from the multiplier 48B and the polynomial bases (1, α, α2, . . . , αk−1) are subjected to multiplication-addition by the multiplication-addition means 48C, and the calculated result is output therefrom as a polynomial of aq.
Next, the control program controls the computer to calculate a 0 + ∑ i = 1 k - 1   a i  β   q - 1 k  α i ( 65 )
and output the calculated result as a polynomial of aq.
The present invention can construct the reference table without any pre-computations, and hence it has a wider range of application (to the signature verification in the elliptic curve DSA signature scheme, for instance) than the conventional apparatus employing the reference table method.
Elliptic-Curve Elliptic-Curve
Addition Doubing
Max Average Max = Av
Binary Method n n/2 n
Signed Binary n/2 n/3 n
FIG. 1 n n/2 y
FIG. 23 n/2 Aprx n/3 y
FIG. 34 n/2 Aprx n/3 y/z
US6263081 * Jul 17, 1998 Jul 17, 2001 Matsushita Electric Industrial Co., Ltd. Elliptic curve calculation apparatus capable of calculating multiples at high speed
EP0807908A2 Apr 15, 1997 Nov 19, 1997 Certicom Corp. Digital signatures on a smartcard
1 Cheon, J.H., et al., "Two Efficient Algorithms for Arithmetic of Elliptic Curves Using Frobenius Map," Elec. & Telec. Res. Inst., ROK, pp. 195-202.
2 Kobayashi, Tetsutaro, et al., "Elliptic Curve Algorithm on OEF with Frobenius Map," SCIS '99, The 1999 Symposium on Cryptography and Information Security, Kobe, Japan, Jan. 26-29, 1999, the Institute of Electronics, Information and Communication Engineers.
3 Kobayashi, Tetsutaro, et al., "Elliptic-Curve Arithmetic Methods on OEF using Frobenius Map," Technical Report of IEICE, the Institute of Electronics, Information and Communication Engineers.
4 Kobayashi, Tetsutaro, et al., "Exponentiation Table Method for Complex Multiplication Method," NTT Information and Communication Systems Laboratories.
5 Kobayashi, Tetsutaro, et al., Fast Elliptic Curve Algorithm Combining Frobenius Map and Table Reference to Adapt to Higher Characteristic, NTT Laboratories, Kanagawa-ken, Japan.
6 Muller, V., "Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two," 1997, 19 pages.
7 Saito, Taiichi, et al., "Optimal Extension Field Frobenius," SCIS '99, The 1999 Symposium on Cryptography and Information Security, Kobe, Japan, Jan. 26-29, 1999, the Institute of Electronics, Information and Communication Engineers.
US7602907 Jul 1, 2005 Oct 13, 2009 Microsoft Corporation Elliptic curve point multiplication
US7742596 * Jun 21, 2005 Jun 22, 2010 General Dynamics C4 Systems, Inc. Reliable elliptic curve cryptography computation
US7995752 Apr 1, 2005 Aug 9, 2011 Certicom Corp. Method for accelerating cryptographic operations on elliptic curves
US20100232601 * Jan 15, 2010 Sep 16, 2010 Fujitsu Limited Elliptic curve arithmetic processing unit and elliptic curve arithmetic processing program and method
US20160065361 * Jun 23, 2015 Mar 3, 2016 Samsung Electronics Co., Ltd. Endecryptor preventing side channel attack, driving method thereof and control device having the same
WO2007005563A2 * Jun 29, 2006 Jan 11, 2007 Microsoft Corporation Elliptic curve point multiplication
WO2007005563A3 * Jun 29, 2006 Apr 23, 2009 Microsoft Corp Elliptic curve point multiplication
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KOBYAYASHI, TETSUTARO;MORITA, HIKARU;KOBAYASHI, KUNIO;AND OTHERS;REEL/FRAME:010233/0688