METHOD FOR CALCULATING ELLIPTIC CURVE SCALAR MULTIPLICATION

Abstract

An elliptic curve scalar multiplication apparatus stores a prime number p and information of a first point, the prime number p defining a field of definition F.sub.p, which defines a first curve, which is a Weierstrass form elliptic curve, and expressed as p=p.sub.0+p.sub.1c+ . . . +p.sub.1c.sup.n1, (where c equals 2.sup.f and f is an integer equal to or larger than 1 that is units of breaking data into pieces in multiple-precision integer arithmetic executed by the elliptic curve scalar multiplication apparatus), calculates a Montgomery constant k.sub.0, work, and h.sub.1, executes doubling of a second point, which is calculated from the first point, by Montgomery multiplication that uses k.sub.0, work, and h.sub.1, adds a third point and fourth point, which are calculated from the first point, by Montgomery multiplication that uses k.sub.0, work, and h.sub.1; and calculates a scalar multiple of the first point, based on a result of the doubling and the addition.

Claims

1. An elliptic curve scalar multiplication method by which an elliptic curve scalar multiplication apparatus is configured to execute scalar multiplication of a first point on a first curve, which is a Weierstrass form elliptic curve, the elliptic curve scalar multiplication apparatus being configured to store a prime number p and information of the first point, the prime number p defining a field of definition F.sub.p, which defines the first curve, and being expressed as p=p.sub.0+p.sub.1c+ . . . +p.sub.nc.sup.n1, (where c equals 2.sup.f and f is an integer equal to or larger than 1 that is units of breaking data into pieces in multiple-precision integer arithmetic executed by the elliptic curve scalar multiplication apparatus), the elliptic curve scalar multiplication method comprising: a first step of calculating, by the elliptic curve scalar multiplication apparatus, a Montgomery constant k.sub.0, which is used for Montgomery multiplication of data x and data y, which are multiple-precision integers in units of f bits and expressed as x=x.sub.0+x.sub.1c+ . . . +x.sub.nc.sup.n1 and y=y.sub.0+y.sub.1c+ . . . +y.sub.nc.sup.n1 (c=2.sup.f, f1, x<p, y<p, 1n), by the following processing (a1) through processing (a8): (a1) determining whether or not p.sub.0=2.sup.f1 is true, and proceeding to the processing (a2) when it is determined that p.sub.0=2.sup.f1 is true, and to the processing (a3) when it is determined that p.sub.0=2.sup.f1 is not true; (a2) putting k.sub.01, and proceeding to the processing (a8); (a3) determining, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g1 is true, and proceeding to the processing (a4) when it is determined that p.sub.0=2.sup.g1 is true, and to the processing (a5) when it is determined that p.sub.0=2.sup.g1 is not true; (a4) putting k.sub.02.sup.g+1, and proceeding to the processing (a8); (a5) determining, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g+1 is true, and proceeding to the processing (a6) when it is determined that p.sub.0=2.sup.g+1 is true, and to the processing (a7) when it is determined that p.sub.0=2.sup.g+1 is not true; (a6) putting k.sub.02.sup.g1, and proceeding to the processing (a8); (a7) calculating k.sub.0p.sup.1 mod 2.sup.f, and proceeding to the processing (a8); and (a8) using the k.sub.0 as a calculation result; a second step of calculating, by the elliptic curve scalar multiplication apparatus, work and h.sub.1 by the following processing (b1) through processing (b11): (b1) determining whether or not k.sub.0=1 is true, and proceeding to the processing (b2) when it is determined that k.sub.0=1 is true, and to the processing (b4) when it is determined that k.sub.0=1 is not true; (b2) putting workl.sub.0 (where l.sub.0 is a least significant f bits value of x.sub.0y.sub.0; (b3) putting h.sub.1work, and proceeding to the processing (b11); (b4) calculating workl.sub.0k.sub.0 mod c; (b5) determining whether or not k.sub.0=2.sup.g+1 is true, and proceeding to the processing (b6) when it is determined that k.sub.0=2.sup.g+1 is true, and to the processing (b7) when it is determined that k.sub.0=2.sup.g+1 is not true; (b6) calculating h.sub.1(work+(l.sub.0>>g))>>(fg); (b7) determining whether or not k.sub.0=2.sup.g1 is true, and proceeding to the processing (b8) when it is determined that k.sub.0=2.sup.g1 is true, and to the processing (b10) when it is determined that k.sub.0=2.sup.g1 is not true; (b8) calculating h.sub.1(work+(l.sub.0>>g))>>(fg); (b9) determining whether or not h.sub.10 is true, calculating h.sub.1h.sub.1+1 and proceeding to the processing (b11) when it is determined that h.sub.10 is true, and proceeding to the processing (b11) without making the calculation when it is determined that h.sub.1=0 is true; (b10) calculating l.sub.0+p.sub.0work, putting most significant f bits of the calculated l.sub.0+p.sub.0work as h.sub.1, and proceeding to the processing (b11); and (b11) using the work and the h.sub.1 as a calculation result; a third step of executing, by the elliptic curve scalar multiplication apparatus, doubling of a second point, which is calculated from the first point, by Montgomery multiplication that uses the calculated Montgomery constant k.sub.0, the calculated work, and the calculated h.sub.1; a fourth step of adding, by the elliptic curve scalar multiplication apparatus, a third point and a fourth point, which are calculated from the first point, by Montgomery multiplication that uses the calculated Montgomery constant k.sub.0, the calculated work, and the calculated h.sub.1; and a fifth step of calculating, by the elliptic curve scalar multiplication apparatus, a scalar multiple of the first point, based on a result of the doubling of the second point and on a result of the addition of the third point and the fourth point.

2. The elliptic curve scalar multiplication method according to claim 1, wherein, in the Montgomery multiplication in the second step and the third step, the elliptic curve scalar multiplication apparatus is configured to execute Montgomery multiplication of the data x and the data y by the following processing (c1) through processing (c18): (c1) putting z0 and i0; (c2) determining whether or not in is true, and proceeding to the processing (c3) when it is determined that in is true, and to the processing (c12) when it is determined that in is not true; (c3) calculating z.sub.0+x.sub.0y.sub.i, putting least significant f bits as l.sub.0, and putting most significant f bits as h.sub.0; (c4) calculating work and h.sub.1 by the processing (b1) through the processing (b11); (c5) putting j1; (c6) determining whether or not jn is true, and proceeding to the processing (c7) when it is determined that jn is true, and to the processing (c11) when it is determined that jn is not true; (c7) calculating z.sub.j+x.sub.jy.sub.i+h.sub.0, putting least significant f bits as l.sub.0, and putting most significant f bits as h.sub.0; (c8) calculating l.sub.0+p.sub.jwork+h.sub.1, putting least significant f bits as l.sub.1, and putting most significant f bits as h.sub.1; (c9) putting z.sub.j1l.sub.1; (c10) putting jj+1, and returning to the processing (c6); (c11) putting ii+1, and returning to the processing (c2); (c12) calculating z.sub.n+1+h.sub.0+h.sub.1, putting least significant f bits as l, and putting most significant f bits as h; (c13) putting z.sub.nl; (c14) calculating z.sub.n+1z.sub.n+2+h; (c15) putting z.sub.n+20; (c16) putting z=z.sub.0+z.sub.1c+ . . . +z.sub.nc.sup.n1+z.sub.n+1c.sup.n; (c17) determining whether or not zp is true, calculating zzp when it is determined that zp is true, and skipping the calculation when it is determined that zp is not true; and (c18) using the z as a calculation result.

3. The elliptic curve scalar multiplication method according to claim 2, wherein the elliptic curve scalar multiplication apparatus is further configured to store a parameter a of the first curve, y.sup.2=x.sup.3+ax+b(4a.sup.227b.sup.30, a,b Fp), wherein, in the third step, the elliptic curve scalar multiplication apparatus is configured to execute doubling of the second point, Q.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m), by the following processing (d1) through processing (d8): (d1) calculating S4X.sub.1mY.sub.1m.sup.2; (d2) determining whether or not a=3 is true, and proceeding to the processing (d3) when it is determined that a=3 is true, and to the processing (d4) when it is determined that a=3 is not true; (d3) calculating HZ.sub.1m.sup.2 and M3(X.sub.1m+H)(X.sub.1mH), and proceeding to the processing (d5); (d4) calculating M3X.sub.1m.sup.2+aZ.sub.1m.sup.2, and proceeding to the processing (d5); (d5) calculating X.sub.3mM.sup.22S; (d6) calculating Y.sub.3mM(SX.sub.3m)8Y.sub.1m.sup.4; (d7) calculating Z.sub.3m2Y.sub.1mZ.sub.1m; and (d8) using Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as a calculation result, and wherein Montgomery multiplication in the processing (d1) and the processing (d3) through the processing (d7) is executed by using the processing (c1) through the processing (c18).

4. The elliptic curve scalar multiplication method according to claim 2, wherein, in the fourth step, the elliptic curve scalar multiplication apparatus is configured to add the third point, P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m), and the fourth point, Q.sub.Jm=(X.sub.2m:Y.sub.2m:Z.sub.2m), by the following processing (e1) through processing (e7): (e1) calculating U.sub.1X.sub.1mZ.sub.2m.sup.2 and U.sub.2X.sub.2mZ.sub.1m.sup.2; (e2) calculating S.sub.1Y.sub.1mZ.sub.2m.sup.3 and S.sub.2Y.sub.2mZ.sub.1m.sup.3; (e3) calculating HU.sub.2U.sub.1 and VS.sub.2S.sub.1; (e4) calculating X.sub.3mV.sup.2H.sup.32U.sub.1H.sup.2; (e5) calculating Y.sub.3mV(U.sub.1H.sup.2X.sub.3m)S.sub.1H.sup.3; (e6) calculating Z.sub.3mHZ.sub.1mZ.sub.2m; and (e7) using Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as a calculation result, and wherein Montgomery multiplication in the processing (e1) through the processing (e7) is executed by using the processing (c1) through the processing (c18).

5. The elliptic curve scalar multiplication method according to claim 3, wherein the elliptic curve scalar multiplication apparatus is further configured to store R=2.sup.fk defined by a minimum integer k that satisfies p<2.sup.fk, the elliptic curve scalar multiplication method further comprising calculating, by the elliptic curve scalar multiplication apparatus, a scalar multiple of the first point P=(x.sub.1,y.sub.1) by the following processing (f1) through processing (f9): (f1) calculating the Montgomery constant k.sub.0 by the processing (a1) through the processing (a8); (f2) calculating a point P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m)(x.sub.1R mod p:y.sub.1R mod p:R mod p) by conversion from the first point P=(x.sub.1,y.sub.1), and calculating a.sub.maR mod p for the parameter a of the first curve y.sup.2=x.sup.3+ax+b; (f3) putting it2 and Q.sub.JmP.sub.Jm; (f4) calculating Q.sub.Jm2Q.sub.Jm by the processing (d1) through the processing (d8); (f5) determining whether or not l.sub.i=1 is true, and proceeding to the processing (f6) when it is determined that l.sub.i=1 is true, and to the processing (f7) when it is determined that l.sub.i=1 is not true; (f6) calculating Q.sub.JmQ.sub.Jm+P.sub.Jm; (f7) calculating ii1; (f8) determining whether or not i0 is true, returning to the processing (f4) when i0 is true, and proceeding to the processing (f9) when i0 is not true; (f9) converting Q.sub.Jm into Q.sub.J by calculating Q.sub.J=(X.sub.3:Y.sub.3:Z.sub.3)(X.sub.3mR.sup.1 mod p:Y.sub.3mR.sup.1 mod p:Z.sub.3mR.sup.1 mod p); and (f10) calculating Q=(x.sub.3, y.sub.3)(X.sub.3/Z.sub.3.sup.2,Y.sub.3/Z.sub.3.sup.3) from the scalar multiplication result Q.sub.J=(X.sub.3:Y.sub.3:Z.sub.3), and using the Q as a calculation result, wherein, in the processing (f6), the third point, P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m), and the fourth point, Q.sub.Jm=(X.sub.2m:Y.sub.2m:Z.sub.2m), are added by the following processing (e1) through processing (e7): (e1) calculating U.sub.1X.sub.1mZ.sub.2m.sup.2 and U.sub.2X.sub.2mZ.sub.1m.sup.2; (e2) calculating S.sub.1Y.sub.1mZ.sub.2m.sup.3 and S.sub.2Y.sub.2mZ.sub.1m.sup.3; (e3) calculating HU.sub.2U.sub.1 and VS.sub.2S.sub.1; (e4) calculating X.sub.3mV.sup.2H.sup.32U.sub.1H.sup.2; (e5) calculating Y.sub.3mV(U.sub.1H.sup.2X.sub.3m)S.sub.1H.sup.3; (e6) calculating Z.sub.3mHZ.sub.1mZ.sub.2m; and (e7) using Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as a calculation result, and wherein Montgomery multiplication in the processing (e1) through the processing (e7) is executed by using the processing (c1) through the processing (c18).

6. An ECDSA key pair generating method, which is executed by an ECDSA key pair generating apparatus comprising the elliptic curve scalar multiplication apparatus using the elliptic curve scalar multiplication method of claim 5, the ECDSA key pair generating apparatus being configured to store a base point G on the first curve and an order q of the base point G, the ECDSA key pair generating method comprising generating, by the ECDSA key pair generating apparatus, an ECDSA key pair by the following processing (g1) through processing (g3): (g1) generating at random an integer d.sub.pri that satisfies 0<d.sub.pri<q, and using the integer d.sub.pri as a private key; (g2) in the processing (f1) through the processing (f10), putting the base point G as the first point, using a scalar multiple Q.sub.pubd.sub.priG=(x,y) of the base point G in calculation, and using a result Q.sub.pub of the calculation as a public key; and (g3) using (d.sub.pri,Q.sub.pub) as an ECDSA key pair.

7. An ECDSA signature generating method, which is executed by an ECDSA signature generating apparatus comprising the elliptic curve scalar multiplication apparatus using a private key generated by the ECDSA key pair generating method of claim 6, the ECDSA signature generating apparatus being configured to store the base point G, the order q, the generated private key d.sub.pri, and a plain text M to be signed, the ECDSA signature generating method comprising generating, by the ECDSA signature generating apparatus, an ECDSA signature by the following processing (h1) through processing (h6): (h1) generating at random an integer a.sub.r that satisfies 0<a.sub.r<q; (h2) in the processing (f1) through the processing (f10), putting the base point G as the first point and calculating a scalar multiple Q.sub.Ra.sub.rG=(x.sub.r,y.sub.r) of the base point G; (h3) calculating rx.sub.r mod q; (h4) calculating a hash function eH(M) of the plain text M to be signed; (h5) calculating sa.sub.r.sup.1(e+rd.sub.pri) mod q; and (h6) using (r,s) as a signature.

8. A method of verifying an ECDSA signature that is generated by the ECDSA signature generating method of claim 7, which is executed by an ECDSA signature verifying apparatus comprising the elliptic curve scalar multiplication apparatus, the ECDSA signature verifying apparatus being configured to store the base point G, the order q, the public key Q.sub.pub=(x.sub.Q,Y.sub.Q), a signature verification target plain text M, and the signature (r, s), the method comprising executing, by the ECDSA signature verifying apparatus, verification of the ECDSA signature by the following processing (i1) through processing (i7): (i1) calculating a hash value eH(M) of the signature verification target plain text M; (i2) calculating es.sup.1e mod q; (i3) calculating rs.sup.1r mod q; (i4) in the processing (f1) through the processing (f10), putting the base point G as the first point and calculating a scalar multiple G(x.sub.g,y.sub.g)=eG of the base point G; (i5) in the processing (f1) through the processing (f10), putting the public key Q.sub.pub as the first point and calculating a scalar multiple Q(x.sub.q,y.sub.q)=rQ.sub.pub of the public key Q.sub.pub; (i6) calculating (x.sub.2,y.sub.2)=G+Q; and (i7) determining whether or not x.sub.2 mod q=r is established, using true as a verification result when it is determined that x.sub.2 mod q=r is established, and using false as a verification result when it is determined that x.sub.2 mod q=r is not established.

9. A computer-readable non-transitory recording medium having stored thereon a program for causing an elliptic curve scalar multiplication apparatus to execute scalar multiplication of a first point on a first curve, which is a Weierstrass form elliptic curve, the elliptic curve scalar multiplication apparatus being configured to store a prime number p and information of the first point, the prime number p defining a field of definition F.sub.p, which defines the first curve, and being expressed as p=p.sub.0+p.sub.1c+ . . . +p.sub.nc.sup.n1, (where c equals 2.sup.f and f is an integer equal to or larger than 1 that is units of breaking data into pieces in multiple-precision integer arithmetic executed by the elliptic curve scalar multiplication apparatus), the program causing the elliptic curve scalar multiplication apparatus to execute: a first procedure of calculating a Montgomery constant k.sub.0, which is used for Montgomery multiplication of data x and data y, which are multiple-precision integers in units of f bits and expressed as x=x.sub.0+x.sub.1c+ . . . +x.sub.nc.sup.n1 and y=y.sub.0+y.sub.1c+ . . . +y.sub.nc.sup.n1 (c=2.sup.f, x<p, y<p, 1n), by the following processing (a1) through processing (a8): (a1) determining whether or not p.sub.0=2.sup.f1 is true, and proceeding to the processing (a2) when it is determined that p.sub.0=2.sup.f1 is true, and to the processing (a3) when it is determined that p.sub.0=2.sup.f1 is not true; (a2) putting k.sub.01, and proceeding to the processing (a8); (a3) determining, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g1 is true, and proceeding to the processing (a4) when it is determined that p.sub.0=2.sup.g1 is true, and to the processing (a5) when it is determined that p.sub.0=2.sup.g1 is not true; (a4) putting k.sub.02.sup.g+1, and proceeding to the processing (a8); (a5) determining, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g+1 is true, and proceeding to the processing (a6) when it is determined that p.sub.0=2.sup.g+1 is true, and to the processing (a7) when it is determined that p.sub.0=2.sup.g+1 is not true; (a6) putting k.sub.02.sup.g1, and proceeding to the processing (a8); (a7) calculating k.sub.0p.sup.1 mod 2.sup.f, and proceeding to the processing (a8); and (a8) using the k.sub.0 as a calculation result; a second procedure of calculating work and h.sub.1 by the following processing (b1) through processing (b11): (b1) determining whether or not k.sub.0=1 is true, and proceeding to the processing (b2) when it is determined that k.sub.0=1 is true, and to the processing (b4) when it is determined that k.sub.0=1 is not true; (b2) putting workl.sub.0 (where l.sub.0 is a least significant f bits value of x.sub.0y.sub.0); (b3) putting h.sub.1work, and proceeding to the processing (b11); (b4) calculating workl.sub.0k.sub.0 mod c; (b5) determining whether or not k.sub.0=2.sup.g+1 is true, and proceeding to the processing (b6) when it is determined that k.sub.0=2.sup.g+1 is true, and to the processing (b7) when it is determined that k.sub.0=2.sup.g+1 is not true; (b6) calculating h.sub.1(work+(l.sub.0>>g))>>(fg); (b7) determining whether or not k.sub.0=2.sup.g1 is true, and proceeding to the processing (b8) when it is determined that k.sub.0=2.sup.g1 is true, and to the processing (b10) when it is determined that k.sub.0=2.sup.g1 is not true; (b8) calculating h.sub.1(work+(l.sub.0>>g))>>(fg); (b9) determining whether or not h.sub.10 is true, calculating h.sub.1h.sub.1+1 and proceeding to the processing (b11) when it is determined that h.sub.10 is true, and proceeding to the processing (b11) without making the calculation when it is determined that h.sub.1=0 is true; (b10) calculating l.sub.0+p.sub.0work, putting most significant f bits of the calculated l.sub.0+p.sub.0work as h.sub.1, and proceeding to the processing (b11); and (b11) using the work and the h.sub.1 as a calculation result; a third procedure of executing doubling of a second point, which is calculated from the first point, by Montgomery multiplication that uses the calculated Montgomery constant k.sub.0, the calculated work, and the calculated h.sub.1; a fourth procedure of adding a third point and a fourth point, which are calculated from the first point, by Montgomery multiplication that uses the calculated Montgomery constant k.sub.0, the calculated work, and the calculated h.sub.1; and a fifth procedure of calculating a scalar multiple of the first point, based on a result of the doubling of the second point and on a result of the addition of the third point and the fourth point.

10. The computer-readable non-transitory recording medium according to claim 9, wherein, in the Montgomery multiplication in the second procedure and the third procedure, the program causes the elliptic curve scalar multiplication apparatus to execute Montgomery multiplication of the data x and the data y by the following processing (c1) through processing (c18): (c1) putting z0 and i0; (c2) determining whether or not in is true, and proceeding to the processing (c3) when it is determined that in is true, and to the processing (c12) when it is determined that in is not true; (c3) calculating z.sub.0+x.sub.0y.sub.i, putting least significant f bits as l.sub.0, and putting most significant f bits as h.sub.0; (c4) calculating work and h.sub.1 by the processing (b1) through the processing (b11); (c5) putting j1; (c6) determining whether or not jn is true, and proceeding to the processing (c7) when it is determined that jn is true, and to the processing (c11) when it is determined that jn is not true; (c7) calculating z.sub.j+x.sub.jy.sub.i+h.sub.0, putting least significant f bits as l.sub.0, and putting most significant f bits as h.sub.0; (c8) calculating l.sub.0+p.sub.jwork+h.sub.1, putting least significant f bits as l.sub.1, and putting most significant f bits as h.sub.1; (c9) putting z.sub.j1l.sub.1; (c10) putting jj+1, and returning to the processing (c6); (c11) putting ii+1, and returning to the processing (c2); (c12) calculating z.sub.n+1+h.sub.0+h.sub.1, putting least significant f bits as l, and putting most significant f bits as h; (c13) putting z.sub.nl; (c14) calculating z.sub.n+1z.sub.n+2+h; (c15) putting z.sub.n+20; (c16) putting z=z.sub.0+z.sub.1c+ . . . +z.sub.nc.sup.n1+z.sub.n+1c.sup.n; (c17) determining whether or not zp is true, calculating zzp when it is determined that zp is true, and skipping the calculation when it is determined that zp is not true; and (c18) using the z as a calculation result.

11. The computer-readable non-transitory recording medium according to claim 10, wherein the elliptic curve scalar multiplication apparatus is further configured to store a parameter a of the first curve, y.sup.2=x.sup.3+ax+b(4a.sup.227b.sup.30, a,b Fp), wherein, in the third procedure, the program causes the elliptic curve scalar multiplication apparatus to execute doubling of the second point, Q.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m), by the following processing (d1) through processing (d8): (d1) calculating S4X.sub.1mY.sub.1m.sup.2; (d2) determining whether or not a=3 is true, and proceeding to the processing (d3) when it is determined that a=3 is true, and to the processing (d4) when it is determined that a=3 is not true; (d3) calculating HZ.sub.1m.sup.2 and M3(X.sub.1m+H)(X.sub.1mH), and proceeding to the processing (d5); (d4) calculating M3X.sub.1m.sup.2+aZ.sub.1m.sup.2, and proceeding to the processing (d5); (d5) calculating X.sub.3mM.sup.22S; (d6) calculating Y.sub.3mM(SX.sub.3m)8Y.sub.1m.sup.4; (d7) calculating Z.sub.3m2Y.sub.1mZ.sub.1m; and (d8) using Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as a calculation result, and wherein the program causes the elliptic curve scalar multiplication apparatus to execute Montgomery multiplication in the processing (d1) and the processing (d3) through the processing (d7) by using the processing (c1) through the processing (c18).

12. The computer-readable non-transitory recording medium according to claim 10, wherein, in the fourth procedure, the program causes the elliptic curve scalar multiplication apparatus to execute addition of the third point, P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m), and the fourth point, Q.sub.Jm=(X.sub.2m:Y.sub.2m:Z.sub.2m), by the following processing (e1) through processing (e7): (e1) calculating U.sub.1X.sub.1mZ.sub.2m.sup.2 and U.sub.2X.sub.2mZ.sub.1m.sup.2; (e2) calculating S.sub.1Y.sub.1mZ.sub.2m.sup.3 and S.sub.2Y.sub.2mZ.sub.1m.sup.3; (e3) calculating HU.sub.2U.sub.1 and VS.sub.2S.sub.1; (e4) calculating X.sub.3mV.sup.2H.sup.32U.sub.1H.sup.2; (e5) calculating Y.sub.3mV(U .sub.1 H.sup.2X.sub.3m)S.sub.1H.sup.3; (e6) calculating Z.sub.3mHZ.sub.1mZ.sub.2m; and (e7) using Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as a calculation result, and wherein the program causes the elliptic curve scalar multiplication apparatus to execute Montgomery multiplication in the processing (e1) through the processing (e7) by using the processing (c1) through the processing (c18).

13. The computer-readable non-transitory recording medium according to claim 11, wherein the elliptic curve scalar multiplication apparatus is configured to further store R=2.sup.fk defined by a minimum integer k that satisfies p<2.sup.fk, wherein the program causes the elliptic curve scalar multiplication apparatus to calculate a scalar multiple of the first point by the following processing (f1) through processing (f9): (f1) calculating the Montgomery constant k.sub.0 by the processing (a1) through the processing (a8); (f2) calculating a point P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m)(x.sub.1R mod p:y.sub.1R mod p:R mod p) by conversion from the first point, P=(x.sub.1,y.sub.1), and calculating a.sub.maR mod p for the parameter a of the first curve y.sup.2=x.sup.3+ax+b; (f3) putting it2 and Q.sub.JmP.sub.Jm; (f4) calculating Q.sub.Jm2Q.sub.Jm by the processing (d1) through the processing (d8); (f5) determining whether or not l.sub.i=1 is true, and proceeding to the processing (f6) when it is determined that l.sub.i=1 is true, and to the processing (f7) when it is determined that l.sub.i=1 is not true; (f6) calculating Q.sub.JmQ.sub.Jm+P.sub.Jm; (f7) calculating ii1; (f8) determining whether or not i0 is true, returning to the processing (f4) when i0 is true, and proceeding to the processing (f9) when i0 is not true; (f9) converting Q.sub.Jm into Q.sub.J by calculating Q.sub.J=(X.sub.3:Y.sub.3:Z.sub.3)(X.sub.3mR.sup.1 mod p:Y.sub.3mR.sup.1 mod p:Z.sub.3mR.sup.1 mod p); and (f10) calculating Q=(x.sub.3, y.sub.3)(X.sub.3/Z.sub.3.sup.2,Y.sub.3/Z.sub.3.sup.3) from the scalar multiplication result Q.sub.J=(X.sub.3:Y.sub.3:Z.sub.3), and using the Q as a calculation result, wherein, in the processing (f6), the program causes the elliptic curve scalar multiplication apparatus to execute addition of the third point, P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m), and the fourth point, Q.sub.Jm=(X.sub.2m:Y.sub.2m:Z.sub.2m), by the following processing (e1) through processing (e7): (e1) calculating U.sub.1X.sub.1mZ.sub.2m.sup.2 and U.sub.2X.sub.2mZ.sub.1m.sup.2; (e2) calculating S.sub.1Y.sub.1mZ.sub.2m.sup.3 and S.sub.2Y.sub.2mZ.sub.1m.sup.3; (e3) calculating HU.sub.2U.sub.1 and VS.sub.2S.sub.1; (e4) calculating X.sub.3mV.sup.2H.sup.32U.sub.1H.sup.2; (e5) calculating Y.sub.3mV(U.sub.1H.sup.2X.sub.3m)S.sub.1H.sup.3; (e6) calculating Z.sub.3mHZ.sub.1mZ.sub.2m; and (e7) using Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as a calculation result, and wherein the program causes the elliptic curve scalar multiplication apparatus to execute Montgomery multiplication in the processing (e1) through the processing (e7) by using the processing (c1) through the processing (c18).

14. The computer-readable non-transitory recording medium according to claim 13, wherein the program causes an ECDSA key pair generating apparatus comprising the elliptic curve scalar multiplication apparatus to generate an ECDSA key pair, wherein the ECDSA key pair generating apparatus is configured to store a base point G on the first curve and an order q of the base point G, and wherein the program causes the ECDSA key pair generating apparatus to generate an ECDSA key pair by the following processing (g1) through processing (g3): (g1) generating at random an integer d.sub.pri that satisfies 0<d.sub.pri<q, and using the integer d.sub.pri as a private key; (g2) in the processing (f1) through the processing (f10), putting the base point G as the first point, using a scalar multiple Q.sub.pubd.sub.priG=(x,y) of the base point G in calculation, and using a result Q.sub.pub of the calculation as a public key; and (g3) using (d.sub.pri,Q.sub.pub) as an ECDSA key pair.

15. An elliptic curve scalar multiplication apparatus for calculating a scalar multiple of a first point on a first curve, which is a Weierstrass form elliptic curve, the elliptic curve scalar multiplication apparatus comprising: an elliptic curve addition unit configured to add points on the first curve; an elliptic curve doubling unit configured to execute doubling of a point on the first curve; and a basic arithmetic unit configured to execute arithmetic on a field of definition of the first curve, four arithmetic operations that use modulo operation, and Montgomery arithmetic, wherein the elliptic curve scalar multiplication apparatus is configured to store a prime number p and information of the first point, the prime number p defining a field of definition F.sub.p, which defines the first curve, and being expressed as p=p.sub.0+p.sub.1c+ . . . +p.sub.nc.sup.n1, (where c equals 2.sup.f and f is an integer equal to or larger than 1 that is units of breaking data into pieces in multiple-precision integer arithmetic executed by the elliptic curve scalar multiplication apparatus), wherein the basic arithmetic unit is configured to: calculate a Montgomery constant k.sub.0, which is used for Montgomery multiplication of data x and data y, which are multiple-precision integers in units of f bits and expressed as x=x.sub.0+x.sub.1c+ . . . +x.sub.nc.sup.n1 and y=y.sub.0+y.sub.1c+ . . . +y.sub.nc.sup.n1 (c=2.sup.f, f1, x<p, y<p, 1n), by the following processing (a1) through processing (a8): (a1) determining whether or not p.sub.0=2.sup.f1 is true, and proceeding to the processing (a2) when it is determined that p.sub.0=2.sup.f1 is true, and to the processing (a3) when it is determined that p.sub.0=2.sup.f1 is not true; (a2) putting k.sub.01, and proceeding to the processing (a8); (a3) determining, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g1 is true, and proceeding to the processing (a4) when it is determined that p.sub.0=2.sup.g1 is true, and to the processing (a5) when it is determined that p.sub.0=2.sup.g1 is not true; (a4) putting k.sub.02.sup.g+1, and proceeding to the processing (a8); (a5) determining, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g+1 is true, and proceeding to the processing (a6) when it is determined that p.sub.0=2.sup.g+1 is true, and to the processing (a7) when it is determined that p.sub.0=2.sup.g+1 is not true; (a6) putting k.sub.02.sup.g1, and proceeding to the processing (a8); (a7) calculating k.sub.0p.sup.1 mod 2.sup.f, and proceeding to the processing (a8); and (a8) using the k.sub.0 as a calculation result; and calculate work and h.sub.1 by the following processing (b1) through processing (b11): (b1) determining whether or not k.sub.0=1 is true, and proceeding to the processing (b2) when it is determined that k.sub.0=1 is true, and to the processing (b4) when it is determined that k.sub.0=1 is not true; (b2) putting workl.sub.0 (where l.sub.o is a least significant f bits value of x.sub.0y.sub.0); (b3) putting h.sub.1work, and proceeding to the processing (b11); (b4) calculating workl.sub.0k.sub.0 mod c; (b5) determining whether or not k.sub.0=2.sup.g+1 is true, and proceeding to the processing (b6) when it is determined that k.sub.0=2.sup.g+1 is true, and to the processing (b7) when it is determined that k.sub.0=2.sup.g+1 is not true; (b6) calculating h.sub.1(work+(l.sub.0>>g))>>(fg); (b7) determining whether or not k.sub.0=2.sup.g1 is true, and proceeding to the processing (b8) when it is determined that k.sub.0=2.sup.g1 is true, and to the processing (b10) when it is determined that k.sub.0=2.sup.g1 is not true; (b8) calculating h.sub.1(work+(l.sub.0>>g))>>(fg); (b9) determining whether or not h.sub.10 is true, calculating h.sub.1h.sub.1+1 and proceeding to the processing (b11) when it is determined that h.sub.10 is true, and proceeding to the processing (b11) without making the calculation when it is determined that h.sub.1=0 is true; (b10) calculating l.sub.0+p.sub.0work, putting most significant f bits of the calculated l.sub.0+p.sub.0work as h.sub.1, and proceeding to the processing (b11); and (b11) using the work and the h.sub.1 as a calculation result, wherein the elliptic curve doubling unit is configured to execute doubling of a second point, which is calculated from the first point, by Montgomery multiplication that uses the calculated Montgomery constant k.sub.0, the calculated work, and the calculated h.sub.1, wherein the elliptic curve addition unit is configured to add a third point and a fourth point, which are calculated from the first point, by Montgomery multiplication that uses the calculated Montgomery constant k.sub.0, the calculated work, and the calculated h.sub.1, and wherein the basic arithmetic unit is configured to calculate a scalar multiple of the first point, based on a result of the doubling of the second point and on a result of the addition of the third point and the fourth point.

Description

BRIEF DESCRIPTIONS OF DRAWINGS

[0221] The present invention can be appreciated by the description which follows in conjunction with the following figures, wherein:

[0222] FIG. 1A is a diagram for illustrating a configuration example of an elliptic curve scalar multiplication apparatus according to an embodiment mode;

[0223] FIG. 1B is a diagram for illustrating a hardware configuration example of an information processing apparatus;

[0224] FIG. 2 is a diagram for illustrating a configuration example of an elliptic curve scalar multiplication unit;

[0225] FIG. 3 is a flow chart for illustrating an example of scalar multiplication processing on an elliptic curve according to the embodiment mode;

[0226] FIG. 4 is a flow chart for illustrating an example of processing of calculating a Montgomery constant according to the embodiment mode;

[0227] FIG. 5 is a flow chart for illustrating an example of doubling processing on an elliptic curve according to the embodiment mode;

[0228] FIG. 6 is a flow chart for illustrating an example of addition processing on the elliptic curve according to the embodiment mode;

[0229] FIG. 7 is a flow chart for illustrating an example of addition processing on a field F.sub.p according to the embodiment mode;

[0230] FIG. 8 is a flow chart for illustrating an example of subtraction processing on the field F.sub.p according to the embodiment mode;

[0231] FIG. 9 is a flow chart for illustrating an example of subtraction processing according to the embodiment mode;

[0232] FIG. 10 is a flow chart for illustrating an example of Montgomery multiplication processing according to the embodiment mode;

[0233] FIG. 11 is a flow chart for illustrating an example of processing of calculating work and others in the Montgomery multiplication processing according to the embodiment mode;

[0234] FIG. 12 is a diagram for illustrating a configuration example of an ECDSA key pair generating apparatus according to Second Embodiment;

[0235] FIG. 13 is a flow chart for illustrating an example of ECDSA key pair generating processing according to Second Embodiment;

[0236] FIG. 14 is a diagram for illustrating a configuration example of an ECDSA signature generating apparatus according to Second Embodiment;

[0237] FIG. 15 is a flow chart for illustrating an example of ECDSA signature generating processing according to Second Embodiment;

[0238] FIG. 16 is a diagram for illustrating a configuration example of an ECDSA signature verifying apparatus according to Second Embodiment;

[0239] FIG. 17 is a flow chart for illustrating an example of ECDSA signature verifying processing according to Second Embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0240] Embodiment modes of the present invention are described below with reference to the accompanying drawings. However, it should be noted that the embodiment modes described below are merely examples for achieving the present invention and do not limit a technical scope of the present invention. Components common across the respective drawings are denoted by the same reference symbols. In the embodiment modes of the present invention, elliptic curve refers to an Weierstrass form elliptic curve unless otherwise noted.

First Embodiment

[0241] FIG. 1A is a diagram for illustrating a configuration example of an elliptic curve scalar multiplication apparatus according to an embodiment mode of the present invention. An elliptic curve scalar multiplication apparatus 101 includes a control calculating unit 102 and a storage unit 103. The control calculating unit 102 includes an input/output unit 104 configured to input data to be calculated and output a calculation result, a control unit 105 configured to handle overall control of the elliptic curve scalar multiplication apparatus 101, and an elliptic curve scalar multiplication unit 106 configured to actually calculate a scalar multiple on an elliptic curve.

[0242] The storage unit 103 includes an intermediate data storing unit 107 configured to store intermediate data, which is generated during processing as the need arises, and a data storing unit 108 configured to store a parameter of an elliptic curve and other types of data. The data storing unit 108 stores, for example, an elliptic curve y.sup.2=x.sup.3+ax+b (4a.sup.227b.sup.30, a,b F.sub.p) input via the input/output unit 104, a point P that is a prime order on the elliptic curve, P=(x.sub.1,y.sub.1), an order q of the point P, an integer l, and others.

[0243] The elliptic curve scalar multiplication unit 106 uses information stored in the data storing unit 108 to execute scalar multiplication processing, and obtains a calculation result Q=lP=(x.sub.3,y.sub.3) expressed with Jacobian coordinates. The scalar multiplication processing follows a flow chart that is illustrated in FIG. 3 and described later.

[0244] FIG. 1B is a diagram for illustrating a hardware configuration example of an information processing apparatus. An information processing apparatus 110 includes a CPU 111, a memory 112, an external storage apparatus 113 including a hard disk apparatus, an input apparatus 115, which is a keyboard or the like, an output apparatus 116, such as a display, and an interface 114 to the external storage apparatus 113, the input apparatus, and the output apparatus. The elliptic curve scalar multiplication apparatus 101 is built on, for example, the information processing apparatus 110 of FIG. 1B.

[0245] The processing units of the control calculating unit 102 are implemented as, for example, processes manifested on the information processing apparatus 110 by executing, with the CPU 111, programs (also called code modules) that are loaded onto the memory 112. The memory 112 and the external storage apparatus 113 are used as the storing units of the storage unit 103 in the elliptic curve scalar multiplication apparatus 101.

[0246] The programs described above are stored in the external storage apparatus 113 in advance, and are loaded onto the memory 112 as the need arises to be executed by the CPU 111. The programs may instead be loaded onto the memory 112 as the need arises from a computer-readable, portable, non-transitory, storage medium, such as a CD-ROM, via an external storage apparatus that handles this type of storage medium. Alternatively, the programs may be installed from the storage medium into the external storage apparatus 113 to be loaded onto the memory 112 from the external storage apparatus 113 as the need arises.

[0247] The programs may be loaded onto the memory after being downloaded to the external storage apparatus 113 via, for example, a network connection apparatus (not shown) with the use of a transmission signal that is a type of media readable to information processing apparatus on a network. The programs may instead be loaded onto the memory 112 directly from a network. The same applies to other apparatus described later in the embodiment mode of the present invention.

[0248] FIG. 2 is a diagram for illustrating a configuration example of the elliptic curve scalar multiplication unit 106. The elliptic curve scalar multiplication unit 106 includes an input/output unit 201, an elliptic curve addition unit 202, an elliptic curve doubling unit 203, and a basic calculating unit 204. The input/output unit 201 is configured to input and output data. The elliptic curve addition unit 202 is configured to add two points on an elliptic curve. The elliptic curve doubling unit 203 is configured to perform the doubling of a point on an elliptic curve. The basic calculating unit 204 is called up by the elliptic curve addition unit 202 and the elliptic curve doubling unit 203 as the need arises to perform, for example, an arithmetic operation on the field of definition of an elliptic curve, four arithmetic operations that use modulo operation (mod), and Montgomery arithmetic.

[0249] FIG. 3 is a flow chart for illustrating an example of scalar multiplication processing. A method of calculating Q=lP when an integer that satisfies 0<l<q is expressed in binary as l=l.sub.0+l.sub.12+ . . . +l.sub.t12.sup.t1 (l.sub.t1=1) is described. A symbol R in steps described below represents a value defined as R=2.sup.fk with the use of a minimum integer k that satisfies p<2.sup.fk in relation to f bits (f is an integer equal to or larger than 1), which are the unit of breaking data into pieces in multiple-precision integer arithmetic performed by the elliptic curve scalar multiplication unit 106. The notation ab in the following description indicates that a is substituted with b.

[0250] <Step S301> The basic calculating unit 204 calculates a Montgomery constant k.sub.0. The Montgomery constant k.sub.0 is calculated by processing that is described later with reference to FIG. 4.

[0251] <Step S302> The basic calculating unit 204 calculates P.sub.Jm=(X.sub.1m:Y.sub.1m:Z.sub.1m)(x.sub.1R mod p:y.sub.1R mod p:R mod p) and calculates a.sub.maR mod p for a parameter a of the elliptic curve y.sup.2=x.sup.3+ax+b.

[0252] <Step S303> The basic calculating unit 204 puts it2 and Q.sub.JmP.sub.Jm.

[0253] <Step S304> The elliptic curve doubling unit 203 calculates Q.sub.Jm2Q.sub.Jm. The calculation of 2Q.sub.Jm is made by processing that is described later with reference to FIG. 5.

[0254] <Step S305> The basic calculating unit 204 determines whether or not l.sub.i=1 is true, and proceeds to Step S306 when determining that l.sub.i=1 is true, and to Step S307 when determining that l.sub.i=1 is not true.

[0255] <Step S306> The elliptic curve addition unit 202 calculates Q.sub.JmQ.sub.Jm+P.sub.Jm. The calculation of Q.sub.Jm+P.sub.Jm is made by processing that is described later with reference to FIG. 6.

[0256] <Step S307> The basic calculating unit 204 calculates ii1.

[0257] <Step S308> The basic calculating unit 204 determines whether or not i0 is true, returns to Step S304 when determining that i0 is true, and proceeds to Step S309 when determining that i0 is not true.

[0258] <Step S309> The basic calculating unit 204 converts Q.sub.Jm into Q.sub.J by calculating Q.sub.J=(X.sub.3:Y.sub.3:Z.sub.3)(X.sub.3mR.sup.1 mod p:Y.sub.3mR.sup.1 mod p:Z.sub.3mR.sup.1 mod p).

[0259] <Step S310> The basic calculating unit 204 calculates Q=(x.sub.3,y.sub.3)(X.sub.3/Z.sub.3.sup.2,Y.sub.3/Z.sub.3.sup.3) from the scalar multiplication result Q.sub.J=(X.sub.3:Y.sub.3:Z.sub.3), and determines Q as the calculation result.

[0260] FIG. 4 is a flow chart for illustrating an example of the processing of calculating the Montgomery constant k.sub.0 in Step S301. Input values are the least significant f bits p.sub.0 of the prime number p, which is used to define the prime field F.sub.p and expressed as p=p.sub.0+p.sub.1c+ . . . +p.sub.nc.sup.n1, where c equals 2.sup.f and f is an integer equal to or larger than 1.

[0261] <Step S401> The basic calculating unit 204 determines whether or not p.sub.0=2.sup.f1 is true, and proceeds to Step S402 when determining that p.sub.0=2.sup.f1 is true, and to Step S403 when determining that p.sub.0=2.sup.f1 is not true.

[0262] <Step S402> The basic calculating unit 204 puts k.sub.01, and proceeds to Step S408.

[0263] <Step S403> The basic calculating unit 204 determines, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g1 is true, and proceeds to Step S404 when determining that p.sub.0=2.sup.g1 is true, and to Step S405 when determining that p.sub.0=2.sup.g1 is not true.

[0264] <Step S404> The basic calculating unit 204 puts k.sub.02.sup.g+1, and proceeds to Step S408.

[0265] <Step S405> The basic calculating unit 204 determines, for an integer that satisfies f/2g<f, whether or not p.sub.0=2.sup.g+1 is true, and proceeds to Step S406 when determining that p.sub.0=2.sup.g+1 is true, and to Step S407 when determining that p.sub.0=2.sup.g+1 is not true.

[0266] <Step S406> The basic calculating unit 204 puts k.sub.02.sup.g1, and proceeds to Step S408.

[0267] <Step S407> The basic calculating unit 204 calculates k.sub.0p.sup.1 mod 2.sup.f, and proceeds to Step S408.

[0268] <Step S408> The input/output unit 201 outputs k.sub.0.

[0269] The basic calculating unit 204, depending on the value of p.sub.0, thus changes the method of calculating the Montgomery constant k.sub.0, thereby finishing the calculation of the Montgomery constant k.sub.0 quickly. Specifically, when p.sub.0 is 2.sup.f1, 2.sup.g1, or 2.sup.g+1, in particular, the basic calculating unit 204 does not need to calculate p.sup.1 mod 2.sup.f, and can quickly determine the Montgomery constant k.sub.0 by simple substitution.

[0270] FIG. 5 is a flow chart for illustrating an example of the doubling processing Q.sub.Jm2Q.sub.Jm that is executed by the elliptic curve doubling unit 203 in Step S304. The coordinates of Q.sub.Jm when input are (X.sub.1m:Y.sub.1m:Z.sub.1m).

[0271] <Step S501> The elliptic curve doubling unit 203 calculates S4X.sub.1mY.sub.1m.sup.2.

[0272] <Step S502> The basic calculating unit 204 determines whether or not a=3 is true, and proceeds to Step S503 when determining that a=3 is true, and to Step S504 when determining that a=3 is not true.

[0273] <Step S503> The elliptic curve doubling unit 203 calculates HZ.sub.1m.sup.2 and M3(X1m+H)(X1mH), and proceeds to Step S505.

[0274] <Step S504> The elliptic curve doubling unit 203 calculates M3X.sub.1m.sup.2+a.sub.mZ.sub.1m.sup.2, and proceeds to Step S505.

[0275] <Step S505> The elliptic curve doubling unit 203 calculates X.sub.3mM.sup.22S.

[0276] <Step S506> The elliptic curve doubling unit 203 calculates Y.sub.3mM(SX.sub.3m)8Y.sub.1m.sup.4.

[0277] <Step S507> The elliptic curve doubling unit 203 calculates Z.sub.3m2Y.sub.1mZ.sub.1m.

[0278] <Step S508> The input/output unit 201 outputs Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as the calculation result.

[0279] FIG. 6 is a flow chart for illustrating an example of the addition processing Q.sub.JmQ.sub.Jm+P.sub.Jm that is executed by the elliptic curve addition unit 202 in Step S306. The coordinates of P.sub.Jm and Q.sub.Jm when input are (X.sub.1:Y.sub.1:Z.sub.1) and (X.sub.2:Y.sub.2:Z.sub.2), respectively.

[0280] <Step S601> The elliptic curve addition unit 202 calculates U.sub.1X.sub.1mZ.sub.2m.sup.2 and U.sub.2X.sub.2mZ.sub.1m.sup.2.

[0281] <Step S602> The elliptic curve addition unit 202 calculates S.sub.1Y.sub.1mZ.sub.2m.sup.3 and S.sub.2Y.sub.2mZ.sub.1m.sup.3.

[0282] <Step S603> The elliptic curve addition unit 202 calculates HU.sub.2U.sub.1 and VS.sub.2S.sub.1.

[0283] <Step S604> The elliptic curve addition unit 202 calculates X.sub.3mV.sup.2H.sup.32U.sub.1H.sup.2.

[0284] <Step S605> The elliptic curve addition unit 202 calculates Y.sub.3mV(U.sub.1H.sup.2X.sub.3m)S.sub.1H.sup.3.

[0285] <Step S606> The elliptic curve addition unit 202 calculates Z.sub.3mHZ.sub.1mZ.sub.2m.

[0286] <Step S607> The input/output unit 201 outputs Q.sub.Jm(X.sub.3m:Y.sub.3m:Z.sub.3m) as the calculation result.

[0287] FIG. 7 is a flow chart for illustrating an example of multiple-precision integer addition processing zx+y mod p that is used in, for example, Step S304, Step S306 and other similar types of processing when inputs are x (x<p), y (y<p), and the prime number p.

[0288] <Step S701> The basic calculating unit 204 re-designates larger data of the input values as x and smaller data as y. The data x and the data y are expressed as data broken into the units of f bits, x=x.sub.0+x.sub.1c+ . . . +x.sub.nc.sup.n1 and y=y.sub.0+y.sub.1c+ . . . +y.sub.tc.sup.t1 (c=2.sup.f, f1, 1tn).

[0289] <Step S702> The basic calculating unit 204 puts c.sub.a0 and i0.

[0290] <Step S703> The basic calculating unit 204 determines whether or not it is true, and proceeds to Step S704 when it is true, and to Step S707 otherwise.

[0291] <Step S704> The basic calculating unit 204 calculates z.sub.ix.sub.i+y.sub.i+c.sub.a mod c.

[0292] <Step S705> The basic calculating unit 204 determines whether or not z.sub.i<b is true, and puts c.sub.a0 when z.sub.i<b is true, and puts c.sub.a1 otherwise.

[0293] <Step S706> The basic calculating unit 204 puts ii+1, and proceeds to Step S703.

[0294] <Step S707> The basic calculating unit 204 determines whether or not in is true, and proceeds to Step S708 when in is true, and to Step S711 otherwise.

[0295] <Step S708> The basic calculating unit 204 calculates z.sub.ix.sub.i+c.sub.a mod c.

[0296] <Step S709> The basic calculating unit 204 determines whether or not z.sub.i<c is true, and puts c.sub.a0 when z.sub.i<c true, and as c.sub.a1 otherwise.

[0297] <Step S710> The basic calculating unit 204 puts ii+1, and returns to Step S707.

[0298] <Step S711> The basic calculating unit 204 puts z.sub.n+1c.sub.a.

[0299] <Step S712> The basic calculating unit 204 puts z=z.sub.0+z.sub.1c+ . . . +z.sub.nc.sup.n1+z.sub.n+1c.sup.n.

[0300] <Step S713> The basic calculating unit 204 determines whether or not zp is true, and calculates zzp when zp is true. The basic calculating unit 204 calculates zp by a calculation method that is illustrated in a flow chart of FIG. 8.

[0301] <Step S714> The input/output unit 201 outputs z.

[0302] Subtraction processing that is used in, for example, Step S304, Step S306, and Step S713 is described next. FIG. 8 is a flow chart for illustrating an example of subtraction processing zxy on the prime field F.sub.p when inputs are x, y, and the prime number is p.

[0303] <Step S801> The basic calculating unit 204 determines whether or not x=y is true, and proceeds to Step S802 when determining that x=y is true, and to Step S803 when determining that x=y is not true.

[0304] <Step S802> The basic calculating unit 204 puts z0, and proceeds to Step S807.

[0305] <Step S803> The basic calculating unit 204 determines whether or not x>y is true, and proceeds to Step S804 when determining that x>y is true, and to Step S805 when determining that x>y is not true.

[0306] <Step S804> The basic calculating unit 204 calculates zxy, and proceeds to Step S807. The basic calculating unit 204 calculates xy by a calculation method that is described later with reference to FIG. 9.

[0307] <Step S805> The basic calculating unit 204 calculates zyx. The basic calculating unit 204 calculates yx by the calculation method that is illustrated in the flow chart of FIG. 8.

[0308] <Step S806> The basic calculating unit 204 calculates zpz, and proceeds to Step S807. The basic calculating unit 204 calculates pz by the calculation method that is described later with reference to FIG. 9.

[0309] <Step S807> The input/output unit 201 outputs z.

[0310] The multiple-precision integer subtraction processing in Step S804, Step S805, and other steps is described next. FIG. 9 is a flow chart for illustrating an example of subtraction processing zxy when inputs are x and y (x>y,x=x.sub.0+x.sub.1c+ . . . +x.sub.nc.sup.n1,y=y.sub.0+y.sub.1c+ . . . +y.sub.tc.sup.t1 (c=2.sup.f, f1, 1tn)).

[0311] <Step S901> The basic calculating unit 204 puts c.sub.a0 and i0.

[0312] <Step S902> The basic calculating unit 204 determines whether or not it is true, and proceeds to Step S903 when determining that it is true, and to Step S906 when determining that it is not true.

[0313] <Step S903> The basic calculating unit 204 calculates z.sub.ix.sub.iy.sub.i+c.sub.a mod c.

[0314] <Step S904> The basic calculating unit 204 determines whether or not z.sub.i<b is true, and puts c.sub.a0 when determining that z.sub.i<b is true, and as c.sub.a1 when determining that z.sub.i<b is not true.

[0315] <Step S905> The basic calculating unit 204 puts ii+1, and returns to Step S902.

[0316] <Step S906> The basic calculating unit 204 determines whether or not in is true, and proceeds to Step S907 when determining that in is true, and to Step S910 when determining that in is not true.

[0317] <Step S907> The basic calculating unit 204 calculates z.sub.ix.sub.i+c.sub.a mod c.

[0318] <Step S908> The basic calculating unit 204 determines whether or not z.sub.i<c is true, and puts c.sub.a0 when determining that z.sub.i<c true, and puts c.sub.a1 when determining that z.sub.i<c is not true.

[0319] <Step S909> The basic calculating unit 204 puts ii+1, and returns to Step S906.

[0320] <Step S910> The basic calculating unit 204 puts z.sub.n+1c.sub.a.

[0321] <Step S911> The basic calculating unit 204 puts z=z.sub.0+z.sub.1c+ . . . +z.sub.nc.sup.n1+z.sub.n+1c.sup.n.

[0322] <Step S912> The input/output unit 201 outputs z.

[0323] Montgomery multiplication processing in Step S304, Step S306, and other steps is described next. FIG. 10 is a flow chart for illustrating an example of Montgomery multiplication processing zxyR.sup.1 mod p when inputs are x and y. In a calculation method described below, x, y, and p are defined as x=x.sub.0+x.sub.1c+ . . . +x.sub.nc.sup.n1, y=y.sub.0+y.sub.1c+ . . . +y.sub.nc.sup.n1, and p=p.sub.0+p.sub.1c+ . . . +p.sub.nc.sup.n1 (c=2.sup.f, f1, y<p, x<p, 1n).

[0324] <Step S1001> The basic calculating unit 204 puts z0 and i0.

[0325] <Step S1002> The basic calculating unit 204 determines whether or not in is true, and proceeds to Step S1003 when determining that in is true, and to Step S1012 when determining that in is not true.

[0326] <Step S1003> The basic calculating unit 204 calculates z.sub.0+x.sub.0y.sub.i, puts the least significant f bits as l.sub.0, and puts the most significant f bits as h.sub.0.

[0327] <Step S1004> The basic calculating unit 204 calculates work and others by a calculation method that is illustrated in FIG. 11.

[0328] <Step S1005> The basic calculating unit 204 puts j1.

[0329] <Step S1006> The basic calculating unit 204 determines whether or not jn is true, and proceeds to Step S1007 when determining that jn is true, and to Step S1011 when determining that jn is not true.

[0330] <Step S1007> The basic calculating unit 204 calculates z.sub.j+x.sub.jy.sub.i+h.sub.0, puts the least significant f bits as l.sub.0, and puts the most significant f bits as h.sub.0.

[0331] <Step S1008> The basic calculating unit 204 calculates l.sub.0+p.sub.jwork+h.sub.1, puts the least significant f bits as l.sub.1, and puts the most significant f bits as h.sub.1.

[0332] <Step S1009> The basic calculating unit 204 puts z.sub.j1l.sub.1.

[0333] <Step S1010> The basic calculating unit 204 puts jj+1, and returns to Step S1006.

[0334] <Step S1011> The basic calculating unit 204 puts ii+1, and returns to Step S1006.

[0335] <Step S1012> The basic calculating unit 204 calculates z.sub.n+1+h.sub.0+h.sub.1, puts the least significant f bits as l, and puts the most significant f bits as h.

[0336] <Step S1013> The basic calculating unit 204 puts z.sub.nl.

[0337] <Step S1014> The basic calculating unit 204 calculates z.sub.n+1z.sub.n+2+h.

[0338] <Step S1015> The basic calculating unit 204 puts z.sub.n+20.

[0339] <Step S1016> The basic calculating unit 204 puts z=z.sub.0+z.sub.1c+ . . . +z.sub.nc.sup.n1 +z.sub.n+1c.sup.n.

[0340] <Step S1017> The basic calculating unit 204 determines whether or not zp is true, calculates zzp when determining that zp is true, and does not execute the processing when determining that zp is not true. The basic calculating unit 204 calculates zp by the calculation method of FIG. 8.

[0341] <Step S1018> The input/output unit 201 outputs z.

[0342] The calculation of work and others in Step S1004 is described next. FIG. 11 is a flow chart for illustrating an example of processing of calculating work and others when inputs are k.sub.0, l.sub.0, and c.

[0343] <Step S1101> The basic calculating unit 204 determines whether or not k.sub.0=1 is true, and proceeds to Step S1102 when determining that k.sub.0=1 is true, and to Step S1104 when determining that k.sub.0=1 is not true.

[0344] <Step S1102> The basic calculating unit 204 puts workl.sub.0.

[0345] <Step S1103> The basic calculating unit 204 puts h.sub.1work, and proceeds to Step S1111.

[0346] <Step S1104> The basic calculating unit 204 calculates workl.sub.0k.sub.0 mod c.

[0347] <Step S1105> The basic calculating unit 204 determines whether or not k.sub.0=2.sup.g+1 is true, and proceeds to Step S1106 when determining that k.sub.0=2.sup.g+1 is true, and to Step S1107 when determining that k.sub.0=2.sup.g+1 is not true.

[0348] <Step S1106> The basic calculating unit 204 calculates h.sub.1(work+(l.sub.0>>g))>>(fg), and proceeds to Step S1111.

[0349] <Step S1107> The basic calculating unit 204 determines whether or not k.sub.0=2.sup.g1 is true, and proceeds to Step S1108 when determining that k.sub.0=2.sup.g1 is true, and to Step S1110 when determining that k.sub.0=2.sup.g1 is not true.

[0350] <Step S1108> The basic calculating unit 204 calculates h.sub.1(work+(l.sub.0>>g))>>(fg).

[0351] <Step S1109> The basic calculating unit 204 determines whether or not h.sub.10 is true, and calculates h.sub.1h.sub.1+1 and proceeds to Step S1111 when determining that h.sub.10 is true. When determining that h.sub.1=0 is true, the basic calculating unit 204 proceeds to Step S1111 without executing the processing.

[0352] <Step S1110> The basic calculating unit 204 calculates l.sub.0+p.sub.0work, puts the most significant f bits as h.sub.1, and proceeds to Step S1111.

[0353] <Step S1111> The input/output unit 201 outputs work and h.sub.1.

[0354] In the manner described above, the basic calculating unit 204 can finish Montgomery multiplication quickly by optimizing calculation and replacing one session of f-bit multiplication per loop with addition and shift operation, which are lighter in processing load, when k.sub.0 is 2.sup.g1 or 2.sup.g+1, in other words, when p.sub.0 is 2.sup.g+1 or 2.sup.g1(f/2g<f). The basic calculating unit 204 can thus reduce the number of times f-bit multiplication is executed from 2n.sup.2+n to 2n.sup.2 by n times, and is therefore capable of fast multiplication processing.

Second Embodiment

[0355] An elliptic curve encryption and signature method to which the elliptic curve scalar multiplication apparatus 101 of the first embodiment is applied is described in this embodiment. FIG. 12 is a diagram for illustrating a configuration example of an ECDSA key pair generating apparatus 1201. The ECDSA key pair generating apparatus 1201 includes a control calculating unit 1202 and a storage unit 1203. The control calculating unit 1202 includes an input/output unit 1204, a control unit 1205, an elliptic curve scalar multiplication unit 1206, and a random number generating unit 1207. The ECDSA key pair generating apparatus 1201 is built on, for example, the information processing apparatus 110 illustrated in FIG. 1B.

[0356] The input/output unit 1204 is configured to receive an input of, for example, a parameter of an elliptic curve, field-of-definition information, the base point G, and the order of G. The input/output unit 1204 is also configured to output a generated key pair. The control unit 1205 is configured to control the ECDSA key pair generating apparatus 1201. The elliptic curve scalar multiplication unit 1206 is configured to calculate an integral multiple of the base point G.

[0357] The elliptic curve scalar multiplication unit 1206 can be built from, for example, the elliptic curve scalar multiplication apparatus 101 of the first embodiment. The elliptic curve scalar multiplication unit 1206 in this case can perform basic arithmetics such as calculation on a field of definition, modulo operation (mod), and comparison by calling up the basic calculating unit 205 through the input/output unit 104. The same applies to elliptic curve scalar multiplication units that are included in other apparatus described later. The random number generating unit 1207 is configured to generate a random number.

[0358] The storage unit 1203 includes an intermediate data storing unit 1208, a data storing unit 1209, and a key pair storing unit 1210. The intermediate data storing unit 1208 is configured to store intermediate data generated during calculation that is made by the control calculating unit 1202. The data storing unit 1209 is configured to store a parameter of an elliptic curve, a base point, the order of the base point, field-of-definition information, and the like that are input via the input/output unit 1204. The key pair storing unit 1210 is configured to store key pair information generated by the control calculating unit 1202.

[0359] The flow of operation of the key pair storing unit 1210 is described next on the assumption that the operation of the ECDSA key pair generating apparatus 1201 is controlled by the control unit 1205. The data storing unit 1209 stores, for example, the elliptic curve y.sup.2=x.sup.3+ax+b(4a.sup.227b.sup.30, a,b F.sub.p), the field of definition F.sub.p, the base point G of the elliptic curve, G=(x.sub.g,y.sub.g), and the order q (a prime number) of the base point G input via the input/output unit 1204. The control calculating unit 1202 uses information stored in the data storing unit 1209 to execute key pair generating processing, which is, for example, processing that is described later with reference to FIG. 13. The key pair storing unit 1210 stores the key pair generated by the control calculating unit 1202, the input/output unit 1204 outputs the key pair, and the operation is then ended.

[0360] FIG. 13 is a flow chart for illustrating an example of the key pair generating processing that is executed by the control calculating unit 1202.

[0361] <Step S1301> The random number generating unit 1207 generates at random an integer d.sub.pri that satisfies 0<d.sub.pri<q, and uses d.sub.pri as a private key.

[0362] <Step S1302> The elliptic curve scalar multiplication unit 1206 calculates a scalar multiple Q.sub.pubd.sub.priG=(x.sub.Q,y.sub.Q), and uses Q.sub.pub as a public key.

[0363] <Step S1304> The input/output unit 1204 outputs (d.sub.pri,Q.sub.pub) as a key pair.

[0364] FIG. 14 is a diagram for illustrating a configuration example of an ECDSA signature generating apparatus 1401. The ECDSA signature generating apparatus 1401 includes a control calculating unit 1402 and a storage unit 1403. The control calculating unit 1402 includes an input/output unit 1404, a control unit 1405, an elliptic curve scalar multiplication unit 1406, a random number generating unit 1407, and a hash function calculating unit 1408. The ECDSA signature generating apparatus 1401 is built on, for example, the information processing apparatus 110 illustrated in FIG. 1B.

[0365] The input/output unit 1404 is configured to receive an input of, for example, a parameter of an elliptic curve, a field of definition, a base point and the order of the base point, a private key of a signer, and a plain text to be signed. The input/output unit 1404 is also configured to output a generated ECDSA signature. The control unit 1405 is configured to control the ECDSA signature generating apparatus 1401. The elliptic curve scalar multiplication unit 1406 is configured to calculate a scalar multiple of a base point. The random number generating unit 1407 is configured to generate a random number. The hash function calculating unit 1408 is configured to generate a hash value.

[0366] The storage unit 1403 includes an intermediate data storing unit 1409, a data storing unit 1410, and a private key storing unit 1411. The intermediate data storing unit 1409 is configured to store intermediate data generated during calculation that is made by the control calculating unit 1402. The data storing unit 1410 is configured to store, for example, a parameter of an elliptic curve, field-of-definition information, a base point, the order of the base point, and a plain text to be signed that are input via the input/output unit 1404, and a generated ECDSA signature. The private key storing unit 1411 is configured to store a private key of a signer that is input via the input/output unit 1404.

[0367] The flow of operation of the ECDSA signature generating apparatus 1401 is described next on the assumption that the operation of the ECDSA signature generating apparatus 1401 is controlled by the control unit 1405. The data storing unit 1410 stores, for example, the elliptic curve y.sup.2=x.sup.3+ax+b(4a.sup.227b.sup.30, a,b F.sub.p), the field of definition F.sub.p, the base point G of the elliptic curve, G=(x.sub.g,y.sub.g), the order q (a prime number) of the base point G, and a plain text M to be signed that are input via the input/output unit 1404.

[0368] The private key storing unit 1411 stores the private key d.sub.pri of the signer that is input via the input/output unit 1404. The control calculating unit 1402 uses information stored in the data storing unit 1410 and information stored in the private key storing unit 1411 to execute ECDSA signature generating processing and generate an ECDSA signature. The control calculating unit 1402 executes ECDSA signature processing by following, for example, a procedure that is described later with reference to FIG. 15. The data storing unit 1410 stores signature data generated by the control calculating unit 1402, the input/output unit 1404 outputs the signature data, and the processing is then ended.

[0369] FIG. 15 is a flow chart for illustrating an example of the ECDSA signature generating processing.

[0370] <Step S1501> The random number generating unit 1407 generates at random an integer a.sub.r that satisfies 0<a.sub.r<q.

[0371] <Step S1502> The elliptic curve scalar multiplication unit 1406 calculates Q.sub.Ra.sub.rG=(x.sub.r,y.sub.r).

[0372] <Step S1503> A basic arithmetic function of the elliptic curve scalar multiplication unit 1406 calculates rx.sub.r mod q.

[0373] <Step S1504> The hash function calculating unit 1408 uses the hash function H to calculate eH(M).

[0374] <Step S1505> The basic arithmetic function of the elliptic curve scalar multiplication unit 1406 calculates sa.sub.r.sup.1(e+rd.sub.pri) mod q.

[0375] <Step S1506> The input/output unit 1404 outputs (r,s) as a signature.

[0376] FIG. 16 is a diagram for illustrating a configuration example of an ECDSA signature verifying apparatus 1601. The ECDSA signature verifying apparatus 1601 includes a control calculating unit 1602 and a storage unit 1603. The control calculating unit 1602 includes an input/output unit 1604, a control unit 1605, an elliptic curve scalar multiplication unit 1606, and a hash function calculating unit 1607. The ECDSA signature verifying apparatus 1601 is built on, for example, the information processing apparatus 110 illustrated in FIG. 1B.

[0377] The input/output unit 1604 is configured to receive an input of, for example, a parameter of an elliptic curve, a field of definition, a base point, a public key of a signer, the order of the base point, a plain text to be signed, and a signature. The input/output unit 1604 is also configured to output a signature verification result. The control unit 1605 is configured to control the ECDSA signature verifying apparatus 1601. The elliptic curve scalar multiplication unit 1606 is configured to calculate scalar multiples of a base point and of a public key. The hash function calculating unit 1607 is configured to generate a hash value.

[0378] The storage unit 1603 includes an intermediate data storing unit 1608 and a data storing unit 1609. The intermediate data storing unit 1608 is configured to store intermediate data generated during calculation that is made by the control calculating unit 1602. The data storing unit 1609 is configured to store, for example, a parameter of an elliptic curve, field-of-definition information, a base point, a public key of a signer, the order of the base point and the public key, a signature verification target plain text, and a signature that are input via the input/output unit 1604, and a signature verification result.

[0379] The flow of operation of the ECDSA signature verifying apparatus 1601 is described next on the assumption that the operation of the ECDSA signature verifying apparatus 1601 is controlled by the control unit 1605. The data storing unit 1609 stores, for example, the elliptic curve y.sup.2=x.sup.3+ax+b(4a.sup.227b.sup.30, a,b F.sub.p), the field of definition F.sub.p, the base point G of the elliptic curve, G=(x.sub.g,y.sub.g), the public key Q.sub.pub=(x.sub.q,y.sub.q), the order q (a prime number) of the base point G and the public key Q.sub.pub, a plain text M, and a signature (r, s) of the plain text M that are input via the input/output unit 1604.

[0380] The control calculating unit 1602 uses information stored in the data storing unit 1609 to execute ECDSA signature verifying processing. The control calculating unit 1602 executes the ECDSA signature verifying processing by following, for example, a procedure that is described later with reference to FIG. 17. The data storing unit 1609 stores a signature verification result generated by the control calculating unit 1602, the input/output unit 1604 outputs the signature verification result, and the processing is then ended.

[0381] FIG. 17 is a flow chart for illustrating an example of the ECDSA signature verifying processing.

[0382] <Step S1701> The hash function calculating unit 1607 uses the hash function H to calculate eH(M).

[0383] <Step S1702> A basic arithmetic function of the elliptic curve scalar multiplication unit 1606 calculates es.sup.1e mod q.

[0384] <Step S1703> The basic arithmetic function of the elliptic curve scalar multiplication unit 1606 calculates rs.sup.1r mod q.

[0385] <Step S1704> The elliptic curve scalar multiplication unit 1606 calculates G(x.sub.g,y.sub.g)=eG.

[0386] <Step S1705> The elliptic curve scalar multiplication unit 1606 calculates Q(x.sub.q,y.sub.q)=rQ.sub.pub.

[0387] <Step S1706> The basic arithmetic function of the elliptic curve scalar multiplication unit 1606 calculates (x.sub.2,y.sub.2)=G+Q.

[0388] <Step S1707> The basic arithmetic function of the elliptic curve scalar multiplication unit 1606 determines whether or not x.sub.2 mod q=r is established. True is output as the verification result when it is determined that x.sub.2 mod q=r is established, and false is output as the verification result when it is determined that x.sub.2 mod q=r is not established.

[0389] This invention is not limited to the above-described embodiments but includes various modifications. The above-described embodiments are explained in details for better understanding of this invention and are not limited to those including all the configurations described above. A part of the configuration of one embodiment may be replaced with that of another embodiment; the configuration of one embodiment may be incorporated to the configuration of another embodiment. A part of the configuration of each embodiment may be added, deleted, or replaced by that of a different configuration.

[0390] The above-described configurations, functions, and processors, for all or a part of them, may be implemented by hardware: for example, by designing an integrated circuit. The above-described configurations and functions may be implemented by software, which means that a processor interprets and executes programs providing the functions. The information of programs, tables, and files to implement the functions may be stored in a storage device such as a memory, a hard disk drive, or an SSD (Solid State Drive), or a storage medium such as an IC card, or an SD card.

[0391] The control lines and information lines given above are ones that are deemed necessary for description, and not all of control lines and information lines that are included in a product are listed. It can be considered that almost all components are actually coupled to one another.