Elliptic curve transformation device, utilization device and utilization system
Abstract
This record has no abstract on file.
Term
Term ended
Expired 5 March 2019, 7.6 years ago.
- Priority
- Filed
- Granted
- Expired
- Today
12 claims: 6 independent, 6 dependent
- 1An encryption/decryption apparatus utilising an elliptic curve E which is expressed as y ^2 = x ^3 + α × x + β and defined over a finite field GF(p) , p being a prime number, α being a parameter of the elliptic curve E, and β being a parameter of the elliptic curve E , characterised in that the apparatus includes an elliptic curve transformation device for transforming the elliptic curve E into an elliptic curve Et, the device comprising:receiving means for receiving an element G as a base point, the prime number p , the parameter α, and the parameter β from an external device, the element G existing on the elliptic curve E and being expressed as G=(x0,y0) ;transformation coefficient acquiring means for acquiring a transformation coefficient t that is present on the finite field GF(p) , where t≠0 and a number of digits of t ^4 × α (mod p) is smaller than a number of digits of the prime number p ;elliptic curve calculating means for calculating a parameter α' and a parameter β' of the elliptic curve Et and an element Gt that is a new base point and is expressed as Gt=(xt0,yt0) , using the transformation coefficient t according to α' = α×t ^4 β' = β x t ^6 xt0 = t ^2×x0 yt0 = t ^3×y0 where the elliptic curve Et is expressed as y' ^2 = x' ^3 + α'×x' + β' and defined over the finite field GF(p) ;and outputting means for outputting the parameter α', the parameter β', and the element Gt to the external device.
- 5An encryption/decryption arrangement utilising an elliptic curve E which is expressed as y ^2 = x ^3 + α×x + β and defined over a finite field GF(p) , p being a prime number, α being a parameter of the elliptic curve E, and β being a parameter of the elliptic curve E , characterised in that the arrangement includes an elliptic curve transformation device for transforming the elliptic curve E into an elliptic curve Et and a cryptographic device using the elliptic curve Et generated by the elliptic curve transformation device, the cryptographic device comprising first outputting means, first receiving means and utilizing means, while the elliptic curve transformation device includes second receiving means, transformation coefficient acquiring means, elliptic curve calculating means and second outputting means, wherein the first outputting means outputs an element G as a base point, the prime number p, the parameter α, and the parameter β to the elliptic curve transformation device, the element G existing on the elliptic curve E and being expressed as G = (x0,y0) wherein the second receiving means receives the prime number p, the parameter α, the parameter β and the element G from the cryptographic device, wherein the transformation coefficient acquiring means acquires a transformation coefficient t that is present on the finite field GF(p) , where t≠0 and a number of digits of t^4 × α(mod p) is smaller than a number of digits of the prime number p , wherein the elliptic curve calculating means calculates a parameter α' and a parameter β' of the elliptic curve Et and an element Gt that is a new base point and is expressed as Gt=(xt0,yt0) , using the transformation coefficient t according to α'=α× t^4 β'=β× t^6 xt0 = t^2×x0 yt0 = t^3×y0 where the elliptic curve Et is expressed as y' ^2 = x' ^3 + α'×x' + β' and defined over the finite field GF(p) , wherein the second outputting means outputs the parameter α', the parameter β' and the element Gt to the cryptographic device, wherein the first receiving means receives the parameter α', the parameter β', and the element Gt from the elliptic curve transformation device, and wherein the utilizing means performs one of encryption, decryption, digital signature, digital signature verification, and key agreement using a discrete logarithm problem as a basis for security, by performing calculations on the elliptic curve Et using the prime number p, the elliptic curve Et defined by the parameter α', and the parameter β' over the finite field GF(p) , and the element Gt as the base point.
- 9A cryptographic device for receiving, from an elliptic curve transformation device that includes second receiving means, transformation coefficient acquiring means, elliptic curve calculating means and second outputting means and transforms an elliptic curve E into an elliptic curve Et, the elliptic curve Et and using the received elliptic curve Et, the elliptic curve E being expressed as y ^2 = x ^3 + α×x + β and defined over a finite field GF(p) , p being a prime number, α being a parameter of the elliptic curve E , and β being a parameter of the elliptic curve E , the cryptographic device comprising first outputting means, first receiving means, and utilizing means, wherein the first outputting means outputs an element G as a base point, the prime number p , the parameter α and the parameter β to the elliptic curve transformation device, the element G existing on the elliptic curve E and being expressed as G=(x0,y0) , wherein the second receiving means receives the prime number p , the parameter α, the parameter β and the element G from the cryptographic device, wherein the transformation coefficient acquiring means acquires a transformation coefficient t that is present on the finite field GF(p) , where t≠0 and a number of digits of t^4 × α(mod p) is smaller than a number of digits of the prime number p , wherein the elliptic curve calculating means calculates a parameter α' and a parameter β' of the elliptic curve Et and an element Gt that is a new base point and is expressed as Gt=(xt0,yt0), using the transformation coefficient t according to α'=α× t^4 β' = β×t^6 xt0 = t^2×x0 yt0 = t^3×y0 where the elliptic curve Et is expressed as y' ^2 = x' ^3 + α'×x' + β' and defined over the finite field GF(p) , wherein the second outputting means outputs the parameter α', the parameter β', and the element Gt to the cryptographic device, wherein the first receiving means receives the parameter α', the parameter β' and the element Gt from the elliptic curve transformation device, and wherein the utilizing means performs one of encryption, decryption, digital signature, digital signature verification, and key agreement using a discrete logarithm problem as a basis for security, by performing calculations on the elliptic curve Et using the prime number p, the elliptic curve Et defined by the parameter α' and the parameter β' over the finite field GF(p) , and the element Gt as the base point.
- 10A cryptographic device for using an elliptic curve Et which is generated as a result of transformation of an elliptic curve E , wherein the elliptic curve E is expressed as y ^2 = x ^3 + α×x + β and defined over the finite field GF(p) , while G as a base point is an element on the elliptic curve E and is expressed as G=(x0,y0) , characterised in that the device comprises:storing means for storing an element Gt as a base point, a parameter α' of the elliptic curve Et , and a parameter β' of the elliptic curve Et ;and utilizing means for performing one of encryption, decryption, digital signature, digital signature verification, and key agreement using a discrete logarithm problem as a basis for security, by performing calculations on the elliptic curve Et using a prime number p, the elliptic curve Et defined by the parameter α' and the parameter β' over a finite field GF(p) , and the element Gt as the base point, wherein the parameter α', the parameter β' and the element Gt are generated by an elliptic curve transformation device that includes transformation coefficient acquiring means and elliptic curve calculating means, wherein the transformation coefficient acquiring means acquires a transformation coefficient t that is present on the finite field GF(p) , where t≠0 and a number of digits of t^4 × α(mod p) is smaller than a number of digits of the prime number p , and wherein the elliptic curve calculating means calculates the parameter α', the parameter β' and the element Gt which is present on the elliptic curve Et and is expressed. as Gt=(xt0,yt0) , using the transformation coefficient t according to α' = α×t^4 β' = β×t^6 xt0 = t^2×x0 yt0 = t^3×y0 where the elliptic curve Et is expressed as y' ^2 = x' ^3 + α'×x' + β' and defined over the finite field GF(p) .
- 11A cryptographic method utilizing an elliptic curve E which is expressed as y ^2 = x ^3 + α×x + β and defined over a finite field GF(p) , p being a prime number, α being a parameter of the elliptic curve E, and β being a parameter of the elliptic curve E, characterised in that the method includes an elliptic curve transformation method for transforming the elliptic curve E into an elliptic curve Et comprising:a receiving step for receiving an element G as a base point, the prime number p, the parameter α, and the parameter β from an external device, the element G existing on the elliptic curve E and being expressed as G=(x0,y0) ;a transformation coefficient acquiring step for acquiring a transformation coefficient t that is present on the finite field GF(p) , where t≠0 and a number of digits of t^4 × α(mod p) is smaller than a number of digits of the prime number p ;an elliptic curve calculating step for calculating a parameter α' and a parameter β' of the elliptic curve Et and an element Gt that is a new base point and is expressed as Gt=(xt0,yt0) , using the transformation coefficient t according to α' = α×t^4 β' = β×t^6 xt0 = t^2×x0 yt0 = t^3 ×y0 where the elliptic curve Et is expressed as y' ^2 = x' ^3 + α'4×x' + β' and defined over the finite field GF(p) ;and an outputting step for outputting the parameter α', the parameter β' and the element Gt to the external device.
- 12A computer-readable storage medium storing a program for encrypting/decrypting information utilizing an elliptic curve E which is expressed as y ^2 = x ^3 + α×x + β and defined over a finite field GF(p) , p being a prime number, α being a parameter of the elliptic curve E, and β being a parameter of the elliptic curve E, characterised in that the program for encrypting/decrypting information utilizes an elliptic curve transformation program for transforming the elliptic curve E into an elliptic curve Et, the elliptic curve transformation program comprising:a receiving step for receiving an element G as a base point, the prime number p, the parameter α, and the parameter β from an external device, the element G existing on the elliptic curve E and being expressed as G=(x0,y0) ;a transformation coefficient acquiring step for acquiring a transformation coefficient t that is present on the finite field GF(p) , where t≠0 and a number of digits of t^4 × α(mod p) is smaller than a number of digits of the prime number p ;an elliptic curve calculating step for calculating a parameter α' and a parameter β' of the elliptic curve Et and an element Gt that is a new base point and is expressed as Gt=(xt0,yt0) , using the transformation coefficient t according to α' = α×t^4 β' = β×t^6 xt0 = t^2×x0 yt0 = t^3×y0 where the elliptic curve Et is expressed as y' ^2 = x'^3 + α'×x' + β' and defined over the finite field GF(p) ;and an outputting step for outputting the parameter α', the parameter β' and the element Gt to the external device.
Independent claims6
191 paragraphs in 5 sections, as filed
BACKGROUND OF THE INVENTION
Field of the Invention
0001The present invention relates to an encryption method of apparatus for maintaining the security of information, and in particular relates to an encryption/decryption technique, a digital signature/verification technique, and a key agreement technique which use an elliptic curve.
Description of the Related Art
<Public-Key Encryption>
0002Data communication that uses computer and communication techniques has become pervasive in recent years. Secret communication or digital signature techniques are used in such data communication. Secret communication techniques allow communication to be performed without the communicated content being revealed to third parties. Digital signature techniques, meanwhile, enable a receiver to verify whether the communicated content is valid or whether the information is from the stated sender.
0003Such secret communication or digital signature techniques use a cryptosystem called public-key encryption. Public-key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users. In secret communication based on public-key encryption, different keys are used for encryption and decryption, with the decryption key being kept secret and the encryption key being made public.
0004Here, one of the founding principles for the security of public-key encryption is the so-called "discrete logarithm problem". Representative examples of the discrete logarithm problem are problems defined over finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz, <i>A Course in Number Theory and Cryptography</i> (Springer-Verlag, 1987).
<Discrete Logarithm Problem based on Elliptic Curve>
0005A discrete logarithm problem based on an elliptic curve is as follows.
0006<i>E(GF(p))</i> is the elliptic curve <i>E</i> defined over the finite field <i>GF(p)</i>, with an element <i>G,</i> given when the order of <i>E</i> is exactly divided by a large prime number, being set as a base point. This being so, the problem is to calculate an integer <i>x</i> that satisfies<maths id="math0001" num="(Formula 1)"><math display="block"><mrow><mtext mathvariant="italic">Y=x*G</mtext></mrow></math><img file="EP0940944B1_D0001.tif" /></maths> where <i>Y</i> is a given element on the elliptic curve <i>E</i> and such an integer <i>x</i> actually exists.
0007Here, <i>p</i> is a prime number and <i>GF(p)</i> is a finite field that includes p elements. Note that in this specification the sign <i>*</i> represents exponentiation of an element included in an elliptic curve, so that <i>x*G=G+G+ ··· +G</i> where the element <i>G</i> is cumulated x times.
0008The reason a discrete logarithm problem assists in the security of public-key encryption is that the above calculation of <i>x</i> is extremely difficult for a large finite field <i>GF(p).</i>
<ElGamal Signature Scheme Which Uses Discrete Logarithm Problem Based on Elliptic Curve>
0009The following is a description of the ElGamal signature scheme which uses a discrete logarithm problem based on an elliptic curve.
0010Fig. 1 is a sequence diagram showing the digital signature procedure by the ElGamal signature scheme.
0011A user A 110, a management center 120 and a user B 130 are connected together via a network.
0012First, a prime number is set as <i>p</i>, an elliptic curve over a finite field <i>GF(p)</i> is set as <i>E</i>, a base point of <i>E</i> is set as <i>G,</i> and the order of <i>E</i> is set as <i>q</i>. Which is to say, <i>q</i> is the smallest positive integer that satisfies<maths id="math0002" num="(Formula 2)"><math display="block"><mrow><mtext mathvariant="italic">q*G=0</mtext></mrow></math><img file="EP0940944B1_D0002.tif" /></maths>
0013Note that a point (∞,∞) whose x and y coordinates are both ∞ is called "point at infinity" and expressed as <i>0</i>. When an elliptic curve is regarded as a group, <i>0</i> acts as "zero-element" in addition operations.
(1) Generation of Public Key by Management Center 120
0014Using a secret key <i>xA</i> given by the user A 110 beforehand, the management center 120 generates a public key <i>YA</i> for the user A 110 according to Formula 3 (steps S141-S142).<maths id="math0003" num="(Formula 3)"><math display="block"><mrow><mtext mathvariant="italic">YA=xA*G</mtext></mrow></math><img file="EP0940944B1_D0003.tif" /></maths>
0015The management center 120 then announces the prime number <i>p</i>, the elliptic curve <i>E</i> and the base point <i>G</i> as system parameters, and reveals the public key <i>YA</i> of the user A 110 to the user B 130 (steps S143-S144).
(2) Generation of Signature by User A 110
0016The user A 110 generates a random number <i>k</i> (step S145).
0017The user A 110 then calculates<maths id="math0004" num="(Formula 4)"><math display="block"><mrow><mtext mathvariant="italic">R1=(rx,ry)=k*G</mtext></mrow></math><img file="EP0940944B1_D0004.tif" /></maths> (step S146), and finds <i>s</i> that satisfies<maths id="math0005" num="(Formula 5)"><math display="block"><mrow><mtext mathvariant="italic">s×k=m+rx×xA (mod q)</mtext></mrow></math><img file="EP0940944B1_D0005.tif" /></maths> (step 147), where <i>m</i> denotes a message to be sent from the user A 110 to the user B 130.
0018The user A 110 sends (R1,s) as a signature to the user B 130 together with the message <i>m</i> (step S148).
(3) Verification of Signature by User B 130
0019The user B 130 verifies the validity of the user A110 that is the sender of the message <i>m</i>, by judging whether Formula 6 is satisfied (step S149).<maths id="math0006" num="(Formula 6)"><math display="block"><mrow><mtext mathvariant="italic">S*R1=m*G+rx*YA</mtext></mrow></math><img file="EP0940944B1_D0006.tif" /></maths>
0020Here, Formula 6 derives from<maths id="math0007" num="(Formula 7)"><math display="block"><mrow><mtext mathvariant="italic">S*Ri</mtext><mtext>=</mtext><mtext mathvariant="italic">{((m</mtext><mtext>+</mtext><mtext mathvariant="italic">rx × xA)</mtext><mtext>/</mtext><mtext mathvariant="italic">k) × k}*G</mtext><mspace linebreak="newline" /><mtext> = </mtext><mtext mathvariant="italic">(m</mtext><mtext>+</mtext><mtext mathvariant="italic">rx × xA)*G</mtext><mspace linebreak="newline" /><mtext> = </mtext><mtext mathvariant="italic">m*G</mtext><mtext>+</mtext><mtext mathvariant="italic">(rx × xA)*G</mtext><mspace linebreak="newline" /><mtext> = </mtext><mtext mathvariant="italic">m*G</mtext><mtext>+</mtext><mtext mathvariant="italic">rx*YA</mtext></mrow></math><img file="EP0940944B1_D0007.tif" /></maths>
<Computational Complexity of Addition and Doubling in Elliptic Curve Exponentiation>
0021In the above ElGamal digital signature scheme which uses a discrete logarithm problem based on an elliptical curve, elliptic curve exponentiation is repeatedly performed to generate the public key and the signature and to verify the signature. For example, <i>xA*G</i> in Formula 3, <i>k*G</i> in Formula 4, <i>s*R1</i>, <i>m*G</i> and <i>rx*YA</i> in Formula 6 are such elliptic curve exponentiation. For details on elliptic curve exponentiation, see "Efficient Elliptic Curve Exponentiation" in Miyaji, Ono & Cohen, <i>Advances in Cryptology - Proceedings of ICICS'97, Lecture Notes in Computer Science,</i> pp.282-290 (Springer-Verlag, 1997). This document describes an elliptic curve with a small coefficient α (0,-3). Its use has been described in cryptography to reduce the number of multiplications on a finite field.
0022Formulas used in elliptic curve exponentiation will be explained below.
0023Let<maths id="math0008"><math display="block"><mrow><mtext mathvariant="italic">y ^ 2=x ^ 3+α×x+</mtext><mtext>β</mtext></mrow></math><img file="EP0940944B1_D0008.tif" /></maths> be the equation of an elliptic curve. In this specification, the sign <i>^</i> represents a repeated multiplication, so that <i>2 ^ 3=2×2×2.</i>
0024Let <i>P=(x1,y1)</i> and <i>Q=(x2,y2)</i> be two arbitrary points on the elliptic curve and <i>R=(x3,y3)</i> be a point defined by <i>R=P+Q.</i>
0025When <i>P≠Q, R=P+Q</i> is an addition operation using addition formulas that are<maths id="math0009"><math display="block"><mrow><mtext mathvariant="italic">x3={(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)} ^ 2-x1-x2</mtext></mrow></math><img file="EP0940944B1_D0009.tif" /></maths><maths id="math0010"><math display="block"><mrow><mtext mathvariant="italic">y3={(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)}(x1-x3)-y1</mtext></mrow></math><img file="EP0940944B1_D0010.tif" /></maths>
0026When <i>P=Q,</i> on the other hand, <i>R=P+Q=P+P=2×P,</i> so that <i>R=P+Q</i> is a doubling operation using doubling formulas that are<maths id="math0011"><math display="block"><mrow><mtext mathvariant="italic">x3={(3x1 ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">2y1} ^ 2-2x1</mtext></mrow></math><img file="EP0940944B1_D0011.tif" /></maths><maths id="math0012"><math display="block"><mrow><mtext mathvariant="italic">y3={(3x1 ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">2y1}(x1-x3)-y1</mtext></mrow></math><img file="EP0940944B1_D0012.tif" /></maths>
0027Note that the above operations are performed on a finite field where the elliptic curve is defined.
0028As shown in the addition formulas, when performing the addition operation over the elliptic curve in the 2-tuple coordinates called affine coordinates, it is necessary to perform one division over the finite field. One division over a finite field requires an average of 10 times as much computational complexity as one multiplication over the finite field.
0029To reduce this computational complexity, 3-tuple coordinates called projective coordinates are used instead.
0030Projective coordinates are 3-tuple coordinates made up of <i>X</i>, <i>Y,</i> and <i>Z,</i> wherein if a number <i>n</i> and two points <i>(X,Y,Z)</i> and <i>(X',Y',Z')</i> satisfy the relationship<maths id="math0013"><math display="block"><mrow><mtext mathvariant="italic">X'=nX, Y'=nY, Z'=nZ</mtext></mrow></math><img file="EP0940944B1_D0013.tif" /></maths> then<maths id="math0014"><math display="block"><mrow><mtext mathvariant="italic">(X,Y,Z)=(X',Y',Z')</mtext></mrow></math><img file="EP0940944B1_D0014.tif" /></maths>
0031Projective coordinates <i>(X,Y,Z)</i> correspond to affine coordinates <i>(x,y)</i> as follows:<maths id="math0015"><math display="block"><mrow><mtext mathvariant="italic">(x,y) → (x,y,1)</mtext></mrow></math><img file="EP0940944B1_D0015.tif" /></maths><maths id="math0016"><math display="block"><mrow><mtext mathvariant="italic">(X,Y,Z) → (X</mtext><mtext>/</mtext><mtext mathvariant="italic">Y,Y</mtext><mtext>/</mtext><mtext mathvariant="italic">Z)</mtext><mtext> (where </mtext><mtext mathvariant="italic">Z≠0</mtext><mtext>)</mtext></mrow></math><img file="EP0940944B1_D0016.tif" /></maths>
0032Here, the sign → is used in such a way that <i>S1→S2</i> when an element in a set <i>S1</i> corresponds to an element in a set <i>S2</i>.
0033Hence the following description will be made on the premise that all computations over elliptic curves are performed in projective coordinates.
0034Addition and doubling formulas used for an elliptic curve in projective coordinates will be explained below. These formulas are consistent with the addition and doubling formulas in affine coordinates given above.
0035Elliptic curve exponentiation is achieved by repeating additions and doublings. Here, while computational complexity of an addition is unchanged regardless of parameters in an elliptic curve, computational complexity of a doubling is dependent on the parameters in the elliptic curve.
0036Let <i>p</i> be a 160-bit prime number and <i>E</i>: <i>y ^ 2=x ^ 3+α×x+β</i> be an elliptic curve over a finite field <i>GF(p)</i>.
0037When elements <i>P</i> and <i>Q</i> on the elliptic curve <i>E</i> are set respectively as <i>P=(X1,Y1,Z1)</i> and <i>Q=(X2,Y2,Z2), R=(X3,Y3,Z3)=P+Q</i> is calculated as follows.
(1) Addition (where
P≠Q)
(1-1) Calculation of Intermediate Values
0038The following is calculated.<maths id="math0017" num="(Formula 8)"><math display="block"><mrow><mtext mathvariant="italic">U1=X1×Z2 ^ 2</mtext></mrow></math><img file="EP0940944B1_D0017.tif" /></maths><maths id="math0018" num="(Formula 9)"><math display="block"><mrow><mtext mathvariant="italic">U2=X2×Z1 ^ 2</mtext></mrow></math><img file="EP0940944B1_D0018.tif" /></maths><maths id="math0019" num="(Formula 10)"><math display="block"><mrow><mtext mathvariant="italic">S1=Y1×Z2 ^ 3</mtext></mrow></math><img file="EP0940944B1_D0019.tif" /></maths><maths id="math0020" num="(Formula 11)"><math display="block"><mrow><mtext mathvariant="italic">S2=Y2×Z1 ^ 3</mtext></mrow></math><img file="EP0940944B1_D0020.tif" /></maths><maths id="math0021" num="(Formula 12)"><math display="block"><mrow><mtext mathvariant="italic">H=U2-U1</mtext></mrow></math><img file="EP0940944B1_D0021.tif" /></maths><maths id="math0022" num="(Formula 13)"><math display="block"><mrow><mtext mathvariant="italic">r=S2-S1</mtext></mrow></math><img file="EP0940944B1_D0022.tif" /></maths>
(1-2) Calculation of
R=(X3, Y3, Z3)
0039The following is calculated.<maths id="math0023" num="(Formula 14)"><math display="block"><mrow><mtext mathvariant="italic">X3=-H ^ 3-2×U1×H ^ 2+r ^ 2</mtext></mrow></math><img file="EP0940944B1_D0023.tif" /></maths><maths id="math0024" num="(Formula 15)"><math display="block"><mrow><mtext mathvariant="italic">Y3=-S1×H ^ 3+r×(U</mtext><mtext>1</mtext><mtext mathvariant="italic">×H ^</mtext><mtext> 2-X3)</mtext></mrow></math><img file="EP0940944B1_D0024.tif" /></maths><maths id="math0025" num="(Formula 16)"><math display="block"><mrow><mtext mathvariant="italic">Z3=Z1×Z2×H</mtext></mrow></math><img file="EP0940944B1_D0025.tif" /></maths>
(2) Doubling (where
P=Q
(
R=2P
))
(2-1) Calculation of Intermediate Values
0040The following is calculated.<maths id="math0026" num="(Formula 17)"><math display="block"><mrow><mtext mathvariant="italic">S=4×X1×Y1 ^ 2</mtext></mrow></math><img file="EP0940944B1_D0026.tif" /></maths><maths id="math0027" num="(Formula 18)"><math display="block"><mrow><mtext mathvariant="italic">M=3×X1 ^ 2+α×Z1 ^ 4</mtext></mrow></math><img file="EP0940944B1_D0027.tif" /></maths><maths id="math0028" num="(Formula 19)"><math display="block"><mrow><mtext mathvariant="italic">T=-2×S+M ^ 2</mtext></mrow></math><img file="EP0940944B1_D0028.tif" /></maths>
(2-2) Calculation of
R=(X3,Y3,Z3)
0041The following is calculated.<maths id="math0029" num="(Formula 20)"><math display="block"><mrow><mtext mathvariant="italic">X3=T</mtext></mrow></math><img file="EP0940944B1_D0029.tif" /></maths><maths id="math0030" num="(Formula 21)"><math display="block"><mrow><mtext mathvariant="italic">Y3=-8×Y1 ^ 4+M×(S-T)</mtext></mrow></math><img file="EP0940944B1_D0030.tif" /></maths><maths id="math0031" num="(Formula 22)"><math display="block"><mrow><mtext mathvariant="italic">Z3=2×Y1×Z1</mtext></mrow></math><img file="EP0940944B1_D0031.tif" /></maths>
0042Computational complexity when performing the above addition and doubling over the elliptic curve <i>E</i> can be estimated as follows. Here, computational complexity of one multiplication over the finite field <i>GF(p)</i> is measured as 1Mul, while computational complexity of one squaring over the finite field <i>GF(p)</i> is measured as 1Sq (1Sq≒0.8Mul in general-purpose microprocessors).
0043Computational complexity of the addition over the elliptic curve <i>E</i> (where <i>P</i>≠<i>Q</i>) is obtained by counting the number of multiplications and the number of squarings performed in Formulas 8-16. Since 1Mul+1Sq, 1Mul+1Sq, 2Mul, 2Mul, 2Mul+2Sq, 2Mul, and 2Mul are performed respectively in Formulas 8, 9, 10, 11, 14, 15, and 16, the computational complexity of the addition is 12Mul+4Sq.
0044Similarly, computational complexity of the doubling over the elliptic curve <i>E</i> (where <i>P</i>=<i>Q</i>) is obtained by counting the number of multiplications and the number of squarings performed in Formulas 17-22. Since 1Mul+1Sq, 1Mul+3Sq, 1Sq, 1Mul+1Sq, and 1Mul are performed respectively in Formulas 17, 18, 19, 21, and 22, the computational complexity of the doubling is 4Mul+6Sq.
0045It should be noted that there are certain rules in counting the number of multiplications and the number of squarings. For instance, <i>H ^ 3</i> in Formula 14 can be expanded as <i>H ^ 3=H ^ 2×H,</i> so that computational complexity of <i>H ^ 3</i> is 1Mul+1Sq. In the same way, <i>Z1 ^ 4</i> in Formula 18 can be expanded as <i>Z1 ^ 4=(Z1 ^ 2) ^ 2,</i> so that computational complexity of <i>Z1 ^ 4</i> is 2Sq.
0046Also, <i>H ^ 2</i> in Formula 14 is not included in the number of squarings, since <i>H ^ 2</i> has already been calculated in the calculation of <i>H ^ 3</i> in the same formula.
0047Also, a multiplication of a given value by a small value is not included in the number of multiplications due to the following reason.
0048Small values noted here are small fixed values, such as <i>2</i>, <i>3, 4,</i> and <i>8,</i> that are used for multiplications in Formulas 8-22. Such values can each be expressed in binary with 4 bits at the maximum, while the other parameters in the formulas are mostly 160 bits long.
0049In microprocessors, a multiplication of a multiplicand by a multiplier is normally achieved by repeatedly shifting the multiplicand and calculating the sum. More specifically, when a bit of a multiplier expressed in binary shows "1", a multiplicand expressed in binary is shifted to justify the least significant bit of the multiplicand to the position of the bit of the multiplier, thereby generating one bit string. After repeating the above shift for every bit of the multiplier, one or more bit strings are generated and totaled.
0050When a multiplier and a multiplicand are both 160 bits long, the 160-bit multiplicand is shifted 160 times, and as a result 160 bit strings are obtained and totaled. On the other hand, when a multiplier is 4 bits long and a multiplicand is 160 bits long, the 160-bit multiplicand is shifted 4 times, and as a result 4 bit strings are obtained and totaled.
0051Thus, in a multiplication of a given value by a small value, shift does not have to be repeated many times, so that computational complexity of the multiplication can be neglected. Accordingly, such a multiplication is not counted in the number of multiplications.
0052This rule can be applied to the following case. If a small value is assigned to the parameter α of the elliptic curve <i>E</i> in Formula 18 in the doubling operation, the computational complexity of the doubling can be reduced by 1Mul to be 3Mul+6Sq. Meanwhile, the computational complexity of the addition operation is unchanged even if parameters of the elliptic curve are changed.
<Selection of Elliptic Curve Suitable for Encryption>
0053A method of selecting an elliptic curve suitable for use in encryption will be explained below. For details on the method, see <i>IEEE P1363 Working Draft</i> (IEEE, February 6, 1997).
0054An elliptic curve suitable for encryption can be obtained by repeating the following steps.
(1) Selection of Arbitrary Elliptic Curve
0055First, two parameters on a finite field <i>GF(p)</i> are arbitrarily selected and set as α and β. Here, α and β satisfy<maths id="math0032" num="(Formula 23)"><math display="block"><mrow><mtext mathvariant="italic">4×α ^ 3+27×β ^ 2≠0 (mod p)</mtext></mrow></math><img file="EP0940944B1_D0032.tif" /></maths> and <i>p</i> denotes a prime number.
0056Next, α and β are used to set an elliptic curve <i>E</i> that is<maths id="math0033"><math display="block"><mrow><mtext mathvariant="italic">E: y ^ 2=x ^ 3+α×x+β</mtext></mrow></math><img file="EP0940944B1_D0033.tif" /></maths>
(2) Judgement on Whether Elliptic Curve
E
is Suitable for Encryption
0057The number of elements <i>#E(GF(p))</i> in the elliptic curve <i>E</i> obtained in (1) is calculated, and the elliptic curve <i>E</i> is adopted when Conditions 1 and 2 are met. <ul id="ul0001" list-style="none" compact="compact"><li>(Condition 1) <i>#E(GF(p))</i> is exactly divisible by a large prime number</li><li>(Condition 2) <i>#E(GF(p))-(p+1)≠0</i>, <i>-1</i></li></ul>
0058When any of Conditions 1 and 2 is not met, the elliptic curve <i>E</i> is rejected and (1) and (2) are performed again where a new elliptic curve is arbitrarily selected and its suitability is judged.
<Problems of Conventional Techniques>
0059As described above, when a fixed small value is assigned to the parameter α of the elliptic curve, computational complexity of elliptic curve exponentiation can be reduced. However, it is difficult to select a secure elliptic curve that is suitable for use in encryption, since the value of the parameter α is fixed beforehand.
0060On the other hand, when the above selection method is used, a secure elliptic curve suitable for use in encryption can be selected. However, it is difficult to reduce computational complexity, since a small value may not necessarily assigned to the parameter α of the elliptic curve.
0061Thus, with the conventional techniques, it is impossible to select a secure elliptic curve suitable for encryption and at the same time reduce computational complexity for the elliptic curve, due to the above mutually contradictory problems.
SUMMARY OF THE INVENTION
0062The first object of the present invention is to provide an elliptic curve transformation device, an elliptic curve transformation method, and a storage medium storing an elliptic curve transformation program that solve the stated problems by converting an elliptic curve, arbitrarily selected as a secure elliptic curve suitable for use in encryption, into an elliptic curve which enables reduction in computational complexity while maintaining the same level of security.
0063The second object of the present invention is to provide utilization devices, such as an encryption device, a decryption device, a digital signature device, a digital signature verification device and a key agreement device, that can perform computations safely at high speed as a result of elliptic curve transformation, and a utilization system composed of the elliptic curve transformation device and any of the utilization devices.
0064The above objects can be fulfilled by an elliptic curve transformation device for transforming an elliptic curve <i>E</i> into an elliptic curve <i>Et,</i> the elliptic curve <i>E</i> being expressed as<maths id="math0034"><math display="block"><mrow><mtext mathvariant="italic">y ^ 2=x ^ 3+α×x+</mtext><mtext>β</mtext></mrow></math><img file="EP0940944B1_D0034.tif" /></maths> and defined over a finite field <i>GF(p), p</i> being a prime number, α being a parameter of the elliptic curve <i>E,</i> and β being a parameter of the elliptic curve <i>E</i>, the elliptic curve transformation device including: a receiving unit for receiving an element <i>G</i> as a base point, the prime number <i>p</i>, the parameter α, and the parameter β from an external device, the element <i>G</i> existing on the elliptic curve <i>E</i> and being expressed as <i>G=(x0,y0);</i> a transformation coefficient acquiring unit for acquiring a transformation coefficient <i>t</i> that is present on the finite field <i>GF(p)</i>, where <i>t≠0</i> and a number of digits of <i>t ^ 4</i>× <i>α(mod p)</i> is smaller than a number of digits of the prime number <i>p</i>; an elliptic curve calculating unit for calculating a parameter α' and a parameter β' of the elliptic curve <i>Et</i> and an element <i>Gt</i> that is a new base point and is expressed as <i>Gt=(xt0,yt0)</i>, using the transformation coefficient <i>t</i> according to<maths id="math0035"><math display="block"><mrow><mtext>α'=α×</mtext><mtext mathvariant="italic">t^ 4</mtext></mrow></math><img file="EP0940944B1_D0035.tif" /></maths><maths id="math0036"><math display="block"><mrow><mtext mathvariant="italic">β'=β×t ^ 6</mtext></mrow></math><img file="EP0940944B1_D0036.tif" /></maths><maths id="math0037"><math display="block"><mrow><mtext mathvariant="italic">xt0=t ^ 2×x0</mtext></mrow></math><img file="EP0940944B1_D0037.tif" /></maths><maths id="math0038"><math display="block"><mrow><mtext mathvariant="italic">yt0=t ^ 3×y0</mtext></mrow></math><img file="EP0940944B1_D0038.tif" /></maths> where the elliptic curve <i>Et</i> is expressed as<maths id="math0039"><math display="block"><mrow><mtext mathvariant="italic">y' ^ 2=x' ^ 3+α'×x'+β'</mtext></mrow></math><img file="EP0940944B1_D0039.tif" /></maths> and defined over the finite field <i>GF(p)</i>; and an outputting unit for outputting the parameter α', the parameter β' and the element <i>Gt</i> to the external device.
0065With this construction, it is possible to obtain a highly effective elliptic curve that has the same level of security as an arbitrarily formed elliptic curve and at the same time enables an elliptic curve utilization device to perform computations at high speed.
0066Here, the prime number <i>p</i> may be 160 bits long, wherein the transformation coefficient acquiring unit acquires the transformation coefficient <i>t</i> which satisfies a condition that <i>t ^ 4×α(mod p)</i> is no longer than 32 bits.
0067With this construction, when an elliptic curve generated by the elliptic curve transformation device is used by a utilization device, computational complexity of a doubling on the elliptic curve can be reduced by 1Mul compared to a pre-transformed elliptic curve whose parameter α is nearly 160 bits long.
0068Here, the transformation coefficient acquiring unit may acquire the transformation coefficient <i>t</i> which satisfies <i>t ^ 4</i>× <i>α(mod p)=-3</i>.
0069With this construction, when an elliptic curve generated by the elliptic curve transformation device is used by a utilization device, computational complexity of a doubling on the elliptic curve can be reduced by 2Sq compared to conventional techniques.
0070The above objects can also be fulfilled by an elliptic curve utilization system whereby an elliptic curve transformation device transforms an elliptic curve <i>E</i> into an elliptic curve <i>Et</i> and a utilization device uses the elliptic curve <i>Et</i> generated by the elliptic curve transformation device, the elliptic curve <i>E</i> being expressed as<maths id="math0040"><math display="block"><mrow><mtext mathvariant="italic">y ^ 2=x ^ 3+α×x+</mtext><mtext>β</mtext></mrow></math><img file="EP0940944B1_D0040.tif" /></maths> and defined over a finite field <i>GF(p)</i>, <i>p</i> being a prime number, α being a parameter of the elliptic curve <i>E,</i> and β being a parameter of the elliptic curve <i>E,</i> wherein the utilization device includes a first outputting unit, a first receiving unit and a utilizing unit, while the elliptic curve transformation device includes a second receiving unit, a transformation coefficient acquiring unit, an elliptic curve calculating unit and a second outputting unit, wherein the first outputting unit outputs an element <i>G</i> as a base point, the prime number <i>p</i>, the parameter α and the parameter β to the elliptic curve transformation device, the element <i>G</i> existing on the elliptic curve <i>E</i> and being expressed as <i>G=(x0,y0)</i>, wherein the second receiving unit receives the prime number <i>p</i>, the parameter α, the parameter β and the element <i>G</i> from the utilization device, wherein the transformation coefficient acquiring unit acquires a transformation coefficient <i>t</i> that is present on the finite field <i>GF(p)</i>, where <i>t≠0</i> and a number of digits of <i>t ^ 4×α(mod p)</i> is smaller than a number of digits of the prime number <i>p</i>, wherein the elliptic curve calculating unit calculates a parameter α' and a parameter β' of the elliptic curve <i>Et</i> and an element <i>Gt</i> that is a new base point and is expressed as <i>Gt=(xt0,yt0)</i>, using the transformation coefficient <i>t</i> according to<maths id="math0041"><math display="block"><mrow><mtext>α'=α×</mtext><mtext mathvariant="italic">t 4</mtext></mrow></math><img file="EP0940944B1_D0041.tif" /></maths><maths id="math0042"><math display="block"><mrow><mtext mathvariant="italic">β'=β×t 6</mtext></mrow></math><img file="EP0940944B1_D0042.tif" /></maths><maths id="math0043"><math display="block"><mrow><mtext mathvariant="italic">xt0=t ^ 2×x0</mtext></mrow></math><img file="EP0940944B1_D0043.tif" /></maths><maths id="math0044"><math display="block"><mrow><mtext mathvariant="italic">yt0=t ^ 3×y0</mtext></mrow></math><img file="EP0940944B1_D0044.tif" /></maths> where the elliptic curve <i>Et</i> is expressed as<maths id="math0045"><math display="block"><mrow><mtext mathvariant="italic">y' ^ 2=x' ^ 3+α'×x'+β'</mtext></mrow></math><img file="EP0940944B1_D0045.tif" /></maths> and defined over the finite field <i>GF(p)</i>, wherein the second outputting unit outputs the parameter α', the parameter β' and the element <i>Gt</i> to the utilization device, wherein the first receiving unit receives the parameter α', the parameter β' and the element <i>Gt</i> from the elliptic curve transformation device, and wherein the utilizing unit performs one of encryption, decryption, digital signature, digital signature verification, and key agreement using a discrete logarithm problem as a basis for security, by performing calculations on the elliptic curve <i>Et</i> using the prime number <i>p</i>, the elliptic curve <i>Et</i> defined by the parameter α' and the parameter β' over the finite field <i>GF(p)</i>, and the element <i>Gt</i> as the base point.
0071With this construction, it is possible to use a highly effective elliptic curve that has the same level of security as an arbitrarily formed elliptic curve and at the same time enables high-speed computations.
0072Here, the prime number <i>p</i> may be 160 bits long, wherein the transformation coefficient acquiring unit acquires the transformation coefficient <i>t</i> which satisfies a condition that <i>t ^ 4×α(mod p)</i> is no longer than 32 bits.
0073With this construction, the utilization device uses a transformed elliptic curve, so that computational complexity of a doubling can be reduced by 1Mul compared to a pre-transformed elliptic curve whose parameter α is nearly 160 bits long.
0074Here, the transformation coefficient acquiring unit may acquire the transformation coefficient <i>t</i> which satisfies <i>t ^ 4× α(mod p)=-3</i>.
0075With this construction, the utilization device uses a transformed elliptic curve, so that computational complexity of a doubling can be reduced by 2Sq compared to conventional techniques.
BRIEF DESCRIPTION OF THE DRAWINGS
0076These and other objects, advantages and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings that illustrate a specific embodiment of the invention. In the drawings: <ul id="ul0002" list-style="none" compact="compact"><li>Fig. 1 is a sequence diagram showing the digital signature procedure by the ElGamal signature scheme;</li><li>Fig. 2 is a block diagram showing an elliptic curve transformation device of an embodiment of the present invention;</li><li>Fig. 3 shows a table showing a function <i>T(i)</i> used in the elliptic curve transformation device;</li><li>Fig. 4 is a flowchart showing the operation of the elliptic curve transformation device;</li><li>Fig. 5 is a flowchart showing the operation of a transformation coefficient acquiring unit of the elliptic curve transformation device;</li><li>Fig. 6 is a flowchart showing the operation of a transformed elliptic curve calculating unit of the elliptic curve transformation device; and</li><li>Fig. 7 is a sequence diagram showing the procedure of a key agreement system that uses the elliptic curve transformation device.</li></ul>
DESCRIPTION OF THE PREFERRED EMBODIMENT(S)
0077The following is a description of an elliptic curve transformation device of an embodiment of the present invention with reference to figures.
1. Construction of Elliptic Curve Transformation Device 200
0078As shown in Fig. 2, an elliptic curve transformation device 200 includes a parameter receiving unit 210, a transformation coefficient acquiring unit 220, a transformed elliptic curve calculating unit 230 and a parameter sending unit 240.
<Parameter Receiving Unit 210>
0079The parameter receiving unit 210 receives parameters α and β of an elliptic curve <i>E,</i> an element <i>G</i> on the elliptic curve <i>E,</i> and a prime number <i>p</i> from an external device. In this embodiment, <i>p</i> is 160 bits long.
0080The external device noted here may be one of an encryption device, a decryption device, a digital signature device, a digital signature verification device, and a key agreement device that use public-key encryption, and uses a discrete logarithm problem based on an elliptic curve as one of the founding principles for the security of public-key encryption. The elliptic curve <i>E</i> is stored in this external device.
0081The elliptic curve <i>E</i> is arbitrarily formed over a finite field <i>GF(p)</i> and expressed as<maths id="math0046"><math display="block"><mrow><mtext mathvariant="italic">E: y ^ 2=x ^ 3+α×x+β</mtext></mrow></math><img file="EP0940944B1_D0046.tif" /></maths> while the element <i>G</i> on the elliptic curve <i>E</i> is arbitrarily set and expressed as<maths id="math0047"><math display="block"><mrow><mtext mathvariant="italic">G=(x0,y0)</mtext></mrow></math><img file="EP0940944B1_D0047.tif" /></maths>
<Transformation Coefficient Acquiring Unit 220>
0082The transformation coefficient acquiring unit 220 possesses a function <i>T(i)</i> shown in Fig. 3. When <i>i=0, 1, 2, 3, 4</i>, the function <i>T(i)</i> holds the values <i>-3</i>, <i>1,-1, 2, -2</i>, respectively. When <i>i=5, 6, 7, 8, 9, 10,</i> ... , the function <i>T(i)</i> holds the values <i>4, -4, 5, -5, 6, -6,</i> ... , respectively.
0083Starting from <i>i=0</i> and incrementing <i>i</i> by 1, the transformation coefficient acquiring unit 220 judges whether <i>T(i)</i> satisfies<maths id="math0048" num="(Formula 24)"><math display="block"><mrow><mtext mathvariant="italic">-2 ^ 31+1≦T(i) ≦2 ^ 31-1</mtext></mrow></math><img file="EP0940944B1_D0048.tif" /></maths>
0084If <i>T(i)</i> satisfies Formula 24, the transformation coefficient acquiring unit 220 finds a transformation coefficient <i>t</i> that satisfies<maths id="math0049" num="(Formula 25)"><math display="block"><mrow><mtext mathvariant="italic">T(i)=t ^ 4×α(mod p)</mtext></mrow></math><img file="EP0940944B1_D0049.tif" /></maths> where <i>t</i> is an element on the finite field <i>GF(p)</i>.
0085Note here that Formula 24 is used to limit the length of <i>T(i)</i> within 32 bits.
0086Since <i>T(i)=-3</i> when <i>i=0</i>, the transformation coefficient acquiring unit 220 first refers to <i>-3</i> as <i>T(i).</i> After <i>i=0</i>, the transformation coefficient acquiring unit 220 refers to values with increasing absolute values as <i>T(i)</i>, since the absolute value of <i>T(i)</i> increases with increase of the value of <i>i</i> except for <i>i=0</i>.
<Transformed Elliptic Curve Calculating Unit 230>
0087The transformed elliptic curve calculating unit 230 calculates parameters α' and β' of a transformed elliptic curve <i>Et</i> which is formed over the finite field <i>GF(p)</i> and expressed as<maths id="math0050"><math display="block"><mrow><mtext mathvariant="italic">Et: y' ^ 2=x' ^ 3+α'×x'+β'</mtext></mrow></math><img file="EP0940944B1_D0050.tif" /></maths> according to Formulas 26 and 27, respectively.<maths id="math0051" num="(Formula 26)"><math display="block"><mrow><mtext>α'=α×</mtext><mtext mathvariant="italic">t ^ 4</mtext></mrow></math><img file="EP0940944B1_D0051.tif" /></maths><maths id="math0052" num="(Formula 27)"><math display="block"><mrow><mtext mathvariant="italic">β'=β×t ^ 6</mtext></mrow></math><img file="EP0940944B1_D0052.tif" /></maths>
0088The transformed elliptic curve calculating unit 230 also calculates an element <i>Gt=(xt0,yt0)</i> on the transformed elliptic curve <i>Et</i> according to<maths id="math0053" num="(Formula 28)"><math display="block"><mrow><mtext mathvariant="italic">xt0=t ^ 2×x0</mtext></mrow></math><img file="EP0940944B1_D0053.tif" /></maths><maths id="math0054" num="(Formula 29)"><math display="block"><mrow><mtext mathvariant="italic">yt0=t ^ 3×y0</mtext></mrow></math><img file="EP0940944B1_D0054.tif" /></maths> where the element <i>Gt</i> corresponds to the element <i>G</i>.
0089Consequently, a given point on the elliptic curve <i>E</i> is transformed into a point on the transformed elliptic curve <i>Et</i> which is defined by the parameters α' and β' generated above.
<Parameter Sending Unit 240>
0090The parameter sending unit 240 sends the parameters α' and β' of the transformed elliptic curve <i>Et</i> and the element <i>Gt=(xt0,yt0)</i> to the external device.
2. Operation of Elliptic Curve Transformation Device 200
<General Operation of Elliptic Curve Transformation Device 200>
0091The general operation of the elliptic curve transformation device 200 will be explained below with reference to Fig. 4.
0092The parameter receiving unit 210 receives a prime number <i>p,</i> parameters α and β of an elliptic curve <i>E,</i> and an element <i>G=(x0,y0)</i> on the elliptic curve <i>E,</i> from an external device (steps S301 and S302). The transformation coefficient acquiring unit 220 acquires a transformation coefficient <i>t</i> (step S303). The transformed elliptic curve calculating unit 230 calculates parameters α' and β' of a transformed elliptic curve <i>Et</i> formed over a finite field <i>GF(p)</i>, and an element <i>Gt=(xt0,yt0)</i> which exists on the transformed elliptic curve <i>Et</i> and corresponds to the element <i>G</i> (step S304). The parameter sending unit 240 sends the obtained parameters α' and β' and element <i>Gt=(xt0,yt0)</i> to the external device (step S305).
<Operation of Transformation Coefficient Acquiring Unit 220>
0093The operation of the transformation coefficient acquiring unit 220 will be explained below with reference to Fig. 5.
0094The transformation coefficient acquiring unit 220 assigns <i>0</i> to <i>i</i> (step S311) and judges whether the function <i>T(i)</i> satisfies<maths id="math0055"><math display="block"><mrow><mtext mathvariant="italic">-2 ^ 31+1≦T(i)≦2 ^ 31-1</mtext></mrow></math><img file="EP0940944B1_D0055.tif" /></maths> (step S312). If <i>T(i)</i> does not satisfy the above formula, the operation is complete. If <i>T(i)</i> satisfies the formula, the transformation coefficient acquiring unit 220 calculates a transformation coefficient <i>t</i> that satisfies<maths id="math0056"><math display="block"><mrow><mtext mathvariant="italic">T(i)=t ^ 4×α(mod p)</mtext></mrow></math><img file="EP0940944B1_D0056.tif" /></maths> (step S313), and judges whether the obtained transformation coefficient <i>t</i> is an element on the finite field <i>GF(p)</i> (step S314). If <i>t</i> is an element on the finite field <i>GF(p)</i>, the operation is complete. If, on the other hand, <i>t</i> is not an element on the finite field <i>GF(p)</i>, the transformation coefficient acquiring unit 220 increments <i>i</i> by 1 (step S315) and returns to step S312.
<Operation of Transformed Elliptic Curve Calculating Unit 230>
0095The operation of the transformed elliptic curve calculating unit 230 will be explained below with reference to Fig. 6.
0096The transformed elliptic curve calculating unit 230 calculates a parameter α'=α<i>×t ^ 4</i> of a transformed elliptic curve <i>Et</i> formed over the finite field <i>GF(p)</i> (step S321) and calculates a parameter <i>β'= β×t ^ 6</i> of the transformed elliptic curve <i>Et</i> (step S322).
0097The transformed elliptic curve calculating unit 230 also calculates an element <i>Gt=(xt0,yt0)</i> that is present on the transformed elliptic curve <i>Et</i> and corresponds to the element <i>G,</i> using the formulas <i>xt0=t ^ 2×x</i>0 and <i>yt0=t ^ 3×y0</i> (steps S323 and S324).
3. Proof that Transformed Elliptic Curve <i>Et</i> is Isomorphic to Elliptic Curve <i>E</i>
0098A proof that the transformed elliptic curve <i>Et: y' ^ 2=x' ^ 3+αxt ^ 4×x'+β×t ^</i> 6 is isomorphic to the elliptic curve <i>E</i>: <i>y ^ 2=x</i> ^3+α×x+β will be given below. In this proof, elliptic curve computations are performed in affine coordinates.
0099Let <i>P=(x0,y0)</i> be an arbitrary point on the elliptic curve <i>E</i>. Here, <i>P</i> satisfies<maths id="math0057" num="(Formula 30)"><math display="block"><mrow><mtext mathvariant="italic">y0 ^ 2=x0 ^ 3+α×x0+</mtext><mtext>β</mtext></mrow></math><img file="EP0940944B1_D0057.tif" /></maths>
0100As a result of transforming the elliptic curve <i>E</i> into the elliptic curve <i>Et, P</i> is converted into a point <i>P'=(x0', y0')=(t ^ 2×x0,t ^ 3×y0).</i>
0101When the both sides of Formula 30 are multiplied by <i>t ^6,</i> the result will be<maths id="math0058"><math display="block"><mrow><mtext mathvariant="italic">t ^ 6×y0 ^ 2=t ^ 6×x0 ^ 3+t ^ 6×α×x0+t ^ 6×</mtext><mtext>β</mtext></mrow></math><img file="EP0940944B1_D0058.tif" /></maths> which can be transformed into<maths id="math0059"><math display="block"><mrow><mtext mathvariant="italic">(t ^ 3×y0) ^ 2=(t ^ 2×x0) ^ 3</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">+α×t ^ 4×(t ^ 2×x0)+β×t ^ 6</mtext></mrow></math><img file="EP0940944B1_D0059.tif" /></maths> and into<maths id="math0060"><math display="block"><mrow><mtext mathvariant="italic">y0' ^ 2=x0' ^ 3+α×t ^ 4×x0'+β×t ^ 6</mtext></mrow></math><img file="EP0940944B1_D0060.tif" /></maths> which shows that the point <i>P'</i> is on the transformed elliptic curve <i>Et</i>.
0102Meanwhile, transformation of a point on the elliptic curve <i>E</i> into a point on the transformed elliptic curve <i>Et</i> is expressed as<maths id="math0061"><math display="block"><mrow><mtext mathvariant="italic">(x,y)→(x',y')=(t ^ 2×x,t ^ 3×y)</mtext></mrow></math><img file="EP0940944B1_D0061.tif" /></maths>
0103Since <i>t≠0</i>, transformation of the point on the transformed elliptic curve <i>Et</i> into the point on the elliptic curve <i>E</i> which is expressed as<maths id="math0062"><math display="block"><mrow><mtext mathvariant="italic">(x',y')→(x,y)=(x</mtext><mtext>'/</mtext><mtext mathvariant="italic">(t ^ 2),y'</mtext><mtext>/</mtext><mtext mathvariant="italic">(t ^ 3))</mtext></mrow></math><img file="EP0940944B1_D0062.tif" /></maths> is obviously the inverse transformation of <i>E</i> into <i>Et.</i>
0104As is evident from the above formulas, a point on the elliptic curve <i>E</i> corresponds to a point on the transformed elliptic curve <i>Et.</i>
0105Next, let <i>P=(x1,y1)</i> and <i>Q=(x2,y2)</i> be two arbitrary points on the elliptic curve <i>E</i> where <i>P≠Q</i>, and <i>R=(x3,y3)</i> be a point defined as <i>R=P+Q</i>. This being so, <i>R</i> can be calculated as follows:<maths id="math0063"><math display="block"><mrow><mtext mathvariant="italic">x3={(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)} ^ 2-x1-x2</mtext></mrow></math><img file="EP0940944B1_D0063.tif" /></maths><maths id="math0064"><math display="block"><mrow><mtext mathvariant="italic">y3={(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)}(x1-x3)-y1</mtext></mrow></math><img file="EP0940944B1_D0064.tif" /></maths> as described above.
0106Suppose <i>P, Q,</i> and <i>R</i> on the elliptic curve <i>E</i> are converted into points <i>P'=(x1', y1'), Q'=(x2', y2')</i>, and <i>R'=(x3', y3')</i> on the transformed elliptic curve <i>Et</i> as a result of transformation of <i>E</i> into <i>Et</i>. Here,<maths id="math0065"><math display="block"><mrow><mtext mathvariant="italic">x1'=t ^ 2×x1</mtext></mrow></math><img file="EP0940944B1_D0065.tif" /></maths><maths id="math0066"><math display="block"><mrow><mtext mathvariant="italic">y1'=t ^ 3×y1</mtext></mrow></math><img file="EP0940944B1_D0066.tif" /></maths><maths id="math0067"><math display="block"><mrow><mtext mathvariant="italic">x2'=t ^ 2×x2</mtext></mrow></math><img file="EP0940944B1_D0067.tif" /></maths><maths id="math0068"><math display="block"><mrow><mtext mathvariant="italic">y2'=t ^ 3×y2</mtext></mrow></math><img file="EP0940944B1_D0068.tif" /></maths><maths id="math0069"><math display="block"><mrow><mtext mathvariant="italic">x3'=t ^ 2×x3</mtext></mrow></math><img file="EP0940944B1_D0069.tif" /></maths><maths id="math0070"><math display="block"><mrow><mtext mathvariant="italic">y3'=t ^ 3×y3</mtext></mrow></math><img file="EP0940944B1_D0070.tif" /></maths> are established.
0107Let <i>R''=(x3'',y3'')</i> be a point defined as <i>R"=P'+Q'</i> that is an addition operation performed on the transformed elliptic curve <i>Et.</i> The point <i>R"</i> can be calculated as follows:<maths id="math0071"><math display="block"><mrow><mtext mathvariant="italic">x3"={(y2'-y1')</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2'-x1')} ^ 2-x1'-x2'</mtext></mrow></math><img file="EP0940944B1_D0071.tif" /></maths><maths id="math0072"><math display="block"><mrow><mtext mathvariant="italic">y3"={(y2'-y1')</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2'-x1')}(x1'-x3')-y1'</mtext></mrow></math><img file="EP0940944B1_D0072.tif" /></maths>
0108When <i>x1', y1', x2'</i> and <i>y2'</i> in these formulas are expressed using <i>x1, y1, x2</i> and <i>y2,</i><maths id="math0073"><math display="block"><mrow><mtext mathvariant="italic">x3''={(t ^ 3×y2-t ^ 3×y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(t ^ 2×x2</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">-t ^ 2 X×1)} ^ 2-t ^ 2 X×1-t ^ 2 X×2</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">={t(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)} ^ 2-t ^ 2×x1-t ^ 2×x2</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2×{{(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)} ^ 2-x1-x2}</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2×x3</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=x3'</mtext></mrow></math><img file="EP0940944B1_D0073.tif" /></maths> while<maths id="math0074"><math display="block"><mrow><mtext mathvariant="italic">y3"={(t ^ 3×y2-t ^ 3×y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(t ^ 2×x2</mtext><mspace linebreak="newline" /><mtext></mtext><mtext mathvariant="italic">-t ^ 2×x1)×(t ^ 2×x1-t ^ 2×x3)-t ^ 3×y1</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">={t(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)}×t ^ 2(x1-x3)-t ^ 3×y1</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 3×{{(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)}×(x1-x3)-y1}</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 3×y3</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=y3'</mtext></mrow></math><img file="EP0940944B1_D0074.tif" /></maths>
0109Accordingly, <i>R'</i> and <i>R"</i> are equivalent.
0110The validity of the addition formulas for the transformed elliptic curve is thereby verified.
0111Also, the validity of the doubling formulas for the transformed elliptic curve where <i>Q=P</i> can be checked as follows.
0112Let <i>P=(x1,y1)</i> be an arbitrary point on the elliptic curve <i>E</i> and <i>R=(x3,y3)</i> be a point defined as <i>R=P+P</i>. When <i>P</i> and <i>R</i> are converted respectively into points <i>P'=(x1',y1')</i> and <i>R'=(x3',y3')</i> on the transformed elliptic curve <i>Et</i> as a result of elliptic curve transformation,<maths id="math0075"><math display="block"><mrow><mtext mathvariant="italic">x1'=t ^ 2×x1</mtext></mrow></math><img file="EP0940944B1_D0075.tif" /></maths><maths id="math0076"><math display="block"><mrow><mtext mathvariant="italic">y1'=t ^ 3×y1</mtext></mrow></math><img file="EP0940944B1_D0076.tif" /></maths><maths id="math0077"><math display="block"><mrow><mtext mathvariant="italic">x3'=t ^ 2×x3</mtext></mrow></math><img file="EP0940944B1_D0077.tif" /></maths><maths id="math0078"><math display="block"><mrow><mtext mathvariant="italic">y3'=t ^ 3×y3</mtext></mrow></math><img file="EP0940944B1_D0078.tif" /></maths> are established.
0113Let <i>R"=(x3",y3")</i> be a point defined as <i>R"=P'+P'</i> that is a doubling operation performed on the transformed elliptic curve <i>Et.</i> Here, <i>R"</i> can be calculated as follows:<maths id="math0079"><math display="block"><mrow><mtext mathvariant="italic">x3"={(3x1' ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">2y1'} ^ 2-2x1'</mtext></mrow></math><img file="EP0940944B1_D0079.tif" /></maths><maths id="math0080"><math display="block"><mrow><mtext mathvariant="italic">y3"={(3x1' ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">2y1'}(x1'-x3')-y1'</mtext></mrow></math><img file="EP0940944B1_D0080.tif" /></maths>
0114When <i>x1'</i> and <i>y1'</i> in these formulas are expressed using <i>x1</i> and <i>y1,</i><maths id="math0081"><math display="block"><mrow><mtext mathvariant="italic">x3"={{(t ^ 2×3x1) ^ 2+α}</mtext><mtext>/</mtext><mtext mathvariant="italic">(2×t ^ 3×y1)} ^ 2</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">-2×t ^ 2×x1</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2{(3x1 ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">y1} ^2-t ^ 2×2x1</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2{{(3x1 ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">y1} ^ 2-2x1}</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2×x3</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">={t(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)} ^ 2-t ^ 2×x1-t ^ 2×x2</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2{{(y2-y1)</mtext><mtext>/</mtext><mtext mathvariant="italic">(x2-x1)} ^ 2-x1-x2}</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 2×x3</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=x3'</mtext></mrow></math><img file="EP0940944B1_D0081.tif" /></maths> while<maths id="math0082"><math display="block"><mrow><mtext mathvariant="italic">y3"={{(t ^ 2×3x1) ^ 2+α}</mtext><mtext>/</mtext><mtext mathvariant="italic">(2×t ^ 3×y1)}</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">×(t ^ 2×x1-t ^ 2×x3)-t ^ 3×y1</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 3{(3x1 ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">2y1}(x1-x3)-t ^ 3×y1</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^3{{(3x1 ^ 2+α)</mtext><mtext>/</mtext><mtext mathvariant="italic">2y1}(x1-x3)-y1}</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=t ^ 3×y3</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=y3'</mtext></mrow></math><img file="EP0940944B1_D0082.tif" /></maths>
0115Accordingly, R' and R" are equivalent.
0116The validity of the doubling formulas for the transformed elliptic curve is thereby verified.
0117Hence it is proved that the transformed elliptic curve <i>Et</i> is isomorphic to the elliptic curve <i>E.</i>
4. Evaluation of Computational Complexity for Transformed Elliptic Curve <i>Et</i>
0118With the above embodiment, the parameter α' of the transformed elliptic curve <i>Et</i> is set at 32 bits or less, so that computational complexity of Formula 18 is reduced to 3Sq. As a result, computational complexity of an addition operation over the transformed elliptic curve <i>Et</i> becomes 12Mul+4Sq and computational complexity of a doubling operation over the transformed elliptic curve <i>Et</i> becomes 3Mul+6Sq. When compared with the elliptic curve <i>E</i> whose parameter α is approximately 160 bits long, the computational complexity of the doubling is reduced by 1Mul.
0119Such reduction in computational complexity is achieved due to the following reason. Since the absolute value of <i>T(i)</i> increases with increase of the value of <i>i</i> except when <i>i=0</i>, values with smaller absolute values are first referred to as <i>T(i)</i>. Accordingly, it is possible to select an appropriate elliptic curve with less computational complexity.
0120Also, when the parameter α' of the transformed elliptic curve Et is -3, Formula 18 can be transformed as<maths id="math0083"><math display="block"><mrow><mtext mathvariant="italic">M=3×X1 ^ 2+α'×Z1 ^4</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=3×X1 ^ 2-3×Z1 ^4</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">=3×(X1+Z1 ^ 2)×(X1-Z1 ^ 2)</mtext></mrow></math><img file="EP0940944B1_D0083.tif" /></maths>
0121As a result, computational complexity of Formula 18 becomes 1Mul+1Sq, so that computational complexity of addition and doubling operations is estimated respectively as 12Mul+4Sq and 4Mul+4Sq. Thus, the computational complexity of the doubling can be reduced by 2Sq when compared with conventional techniques.
0122In the present embodiment, the transformation coefficient acquiring unit 220 refers to <i>T(i)</i> starting from <i>i=0</i> and incrementing <i>i</i> by 1, so that <i>-3</i> is initially referred to as <i>T(i)</i>. Accordingly, an elliptic curve which reduces computational complexity of the doubling by 2Sq compared to the conventional techniques is checked first, with it being possible to raise the possibility of selecting an optimal transformed elliptic curve by a single operation.
0123Consequently, through use of the transformed elliptic curve obtained by the elliptic curve transformation device 200, it is possible to speed up elliptic curve computations.
5. Variants
0124The transformation coefficient acquiring unit 220 may determine a transformation coefficient <i>t</i> as follows.
0125The transformation coefficient acquiring unit 220 includes a random number generating unit which randomly generates an element <i>u(u≠0)</i> on the finite field <i>GF(p)</i>. The transformation coefficient acquiring unit 220 then judges whether the element <i>u</i> satisfies<maths id="math0084" num="(Formula 31)"><math display="block"><mrow><mtext mathvariant="italic">-2 ^ 31+1≦u ^ 4×α(mod p)≦2 ^ 31-1</mtext></mrow></math><img file="EP0940944B1_D0084.tif" /></maths>
0126If <i>u</i> satisfies Formula 31, <i>u</i> is adopted as the transformation coefficient <i>t</i>. If, on the other hand, <i>u</i> does not satisfy Formula 31, the random number generating unit randomly generates an element <i>u</i> again and the transformation coefficient acquiring unit 220 judges whether the newly generated element <i>u</i> satisfies Formula 31.
0127The transformation coefficient acquiring unit 220 repeats the above element generation and judgement until an element <i>u</i> that satisfies Formula 31 is found.
0128Here, the transformation coefficient acquiring unit 220 may use<maths id="math0085" num="(formula 32)"><math display="block"><mrow><mtext mathvariant="italic">u ^ 4×α(mod p) =-3</mtext></mrow></math><img file="EP0940944B1_D0085.tif" /></maths> instead of Formula 31.
6. Applications of Elliptic Curve Transformation Device 200
0129A key agreement system that uses the above elliptic curve transformation device 200 will be described below with reference to Fig. 7.
0130In the figure, a user A 450, a management center 460 and a user B 470 are connected together via a network.
(1) Selection of Elliptic Curve by Management Center 460
0131The management center 460 selects a prime number <i>p</i>, selects an elliptic curve <i>E</i> on a finite field <i>GF(p)</i>, sets <i>G</i> as a base point of <i>E</i>, and sets <i>q</i> as the order of <i>E</i> (step S411). Here, <i>q</i> is the smallest positive integer that satisfies Formula 2<maths id="math0086"><math display="block"><mrow><mtext mathvariant="italic">q*G=0</mtext></mrow></math><img file="EP0940944B1_D0086.tif" /></maths> while <i>E</i> and <i>G</i> are expressed respectively as<maths id="math0087"><math display="block"><mrow><mtext mathvariant="italic">E: y ^ 2=x ^ 3+α×x+β</mtext></mrow></math><img file="EP0940944B1_D0087.tif" /></maths><maths id="math0088"><math display="block"><mrow><mtext mathvariant="italic">G=(x0,y0)</mtext></mrow></math><img file="EP0940944B1_D0088.tif" /></maths>
0132The management center 460 sends <i>p, E</i> and <i>G</i> to the elliptic curve transformation device 200 (step S412).
(2) Generation of Transformed Elliptic Curve by Elliptic Curve Transformation Device 200
0133The elliptic curve transformation device 200 calculates a transformed elliptic curve <i>Et</i> and an element <i>Gt</i> as follows:<maths id="math0089"><math display="block"><mrow><mtext mathvariant="italic">Et: y' ^ 2=x' ^ 3+α'×x'+β'</mtext></mrow></math><img file="EP0940944B1_D0089.tif" /></maths><maths id="math0090"><math display="block"><mrow><mtext mathvariant="italic">α'=α×t ^ 4</mtext></mrow></math><img file="EP0940944B1_D0090.tif" /></maths><maths id="math0091"><math display="block"><mrow><mtext>β'=β×</mtext><mtext mathvariant="italic">t ^ 6</mtext></mrow></math><img file="EP0940944B1_D0091.tif" /></maths><maths id="math0092"><math display="block"><mrow><mtext mathvariant="italic">Gt=(xt0,yt0)</mtext></mrow></math><img file="EP0940944B1_D0092.tif" /></maths><maths id="math0093"><math display="block"><mrow><mtext mathvariant="italic">xt0=t ^ 2×x0</mtext></mrow></math><img file="EP0940944B1_D0093.tif" /></maths><maths id="math0094"><math display="block"><mrow><mtext mathvariant="italic">yt0=t ^ 3×y0</mtext></mrow></math><img file="EP0940944B1_D0094.tif" /></maths> (step 421).
0134The elliptic curve transformation device 200 then sends <i>Et</i> and <i>Gt</i> to the management center 460 (step S422).
(3) Setting of Secret keys and Generation of Public Keys by Users
0135The management center 460 reveals the prime number <i>p</i>, the elliptic curve <i>Et</i> and the element <i>Gt</i> to the user A 450 and the user B 470 (step S413).
0136The user A 450 sets a secret key <i>xA</i> (step S401), and the user B 470 sets a secret key <i>xB</i> (step S431).
0137The user A 450 calculates a public key <i>YA</i> according to<maths id="math0095"><math display="block"><mrow><mtext mathvariant="italic">YA=xA*Gt</mtext></mrow></math><img file="EP0940944B1_D0095.tif" /></maths> (step S402) and sends the public key <i>YA</i> to the user B 470 (step S403).
0138Similarly, the user B 470 calculates a public key <i>YB</i> according to<maths id="math0096"><math display="block"><mrow><mtext mathvariant="italic">YB=xB*Gt</mtext></mrow></math><img file="EP0940944B1_D0096.tif" /></maths> (step S432) and sends the public key <i>YB</i> to the user A 450 (step S433).
(4) Generation of Shared Keys by Users
0139The user A 450 calculates a shared key <i>xA*YB</i> (step S404), and the user B 470 calculates a shared key <i>xB*YA</i> (step S434).
0140The shared key <i>xA*YB</i> generated by the user A 450 can be transformed as<maths id="math0097"><math display="block"><mrow><mtext mathvariant="italic">xA*YB=(xA×xB) *Gt</mtext></mrow></math><img file="EP0940944B1_D0097.tif" /></maths> while the shared key <i>xB*YA</i> generated by the user B 470 can be transformed as<maths id="math0098"><math display="block"><mrow><mtext mathvariant="italic">xB*YA=(xB×xA) *Gt</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">= (xA×xB) *Gt</mtext></mrow></math><img file="EP0940944B1_D0098.tif" /></maths>
0141As is evident from the above formulas, the shared key <i>xA*YB</i> generated by the user A 450 and the shared key <i>xB*YA</i> generated by by the user B 470 are the same.
7. Other Variants
0142Other embodiments of the present invention include an elliptic curve transformation method that achieves the elliptic curve transformation described above, and a computer-readable storage medium storing an elliptic curve transformation program for implementing the elliptic curve transformation method on a computer. The elliptic curve transformation program may also be transmitted to the computer via a communication line.
0143Also, the elliptic curve transformation device can be applied to an encryption system that includes at least one of an encryption device and a decryption device.
0144The elliptic curve transformation device can also be applied to a digital signature system that includes at least one of a digital signature device and a digital signature verification device.
0145Also, an encryption device, a decryption device, a digital signature device, a digital signature verification device or a key agreement device may store parameters α' and β' and an element <i>Gt</i> of an elliptic curve generated by the elliptic curve transformation device beforehand, so that encryption, decryption, digital signature, digital signature verification or key agreement can be performed using the parameters α' and β' and the element <i>Gt.</i>
0146Various combinations of the embodiments and variants stated above are possible.
Contents5
222 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34 Sheet 35 Sheet 36 Sheet 37 Sheet 38 Sheet 39 Sheet 40 Sheet 41 Sheet 42 Sheet 43 Sheet 44 Sheet 45 Sheet 46 Sheet 47 Sheet 48 Sheet 49 Sheet 50 Sheet 51 Sheet 52 Sheet 53 Sheet 54 Sheet 55 Sheet 56 Sheet 57 Sheet 58 Sheet 59 Sheet 60 Sheet 61 Sheet 62 Sheet 63 Sheet 64 Sheet 65 Sheet 66 Sheet 67 Sheet 68 Sheet 69 Sheet 70 Sheet 71 Sheet 72 Sheet 73 Sheet 74 Sheet 75 Sheet 76 Sheet 77 Sheet 78 Sheet 79 Sheet 80 Sheet 81 Sheet 82 Sheet 83 Sheet 84 Sheet 85 Sheet 86 Sheet 87 Sheet 88 Sheet 89 Sheet 90 Sheet 91 Sheet 92 Sheet 93 Sheet 94 Sheet 95 Sheet 96 Sheet 97 Sheet 98 Sheet 99 Sheet 100 Sheet 101 Sheet 102 Sheet 103 Sheet 104 Sheet 105 Sheet 106 Sheet 107 Sheet 108 Sheet 109 Sheet 110 Sheet 111 Sheet 112 Sheet 113 Sheet 114 Sheet 115 Sheet 116 Sheet 117 Sheet 118 Sheet 119 Sheet 120 Sheet 121 Sheet 122 Sheet 123 Sheet 124 Sheet 125 Sheet 126 Sheet 127 Sheet 128 Sheet 129 Sheet 130 Sheet 131 Sheet 132 Sheet 133 Sheet 134 Sheet 135 Sheet 136 Sheet 137 Sheet 138 Sheet 139 Sheet 140 Sheet 141 Sheet 142 Sheet 143 Sheet 144 Sheet 145 Sheet 146 Sheet 147 Sheet 148 Sheet 149 Sheet 150 Sheet 151 Sheet 152 Sheet 153 Sheet 154 Sheet 155 Sheet 156 Sheet 157 Sheet 158 Sheet 159 Sheet 160 Sheet 161 Sheet 162 Sheet 163 Sheet 164 Sheet 165 Sheet 166 Sheet 167 Sheet 168 Sheet 169 Sheet 170 Sheet 171 Sheet 172 Sheet 173 Sheet 174 Sheet 175 Sheet 176 Sheet 177 Sheet 178 Sheet 179 Sheet 180 Sheet 181 Sheet 182 Sheet 183 Sheet 184 Sheet 185 Sheet 186 Sheet 187 Sheet 188 Sheet 189 Sheet 190 Sheet 191 Sheet 192 Sheet 193 Sheet 194 Sheet 195 Sheet 196 Sheet 197 Sheet 198 Sheet 199 Sheet 200 Sheet 201 Sheet 202 Sheet 203 Sheet 204 Sheet 205 Sheet 206 Sheet 207 Sheet 208 Sheet 209 Sheet 210 Sheet 211 Sheet 212 Sheet 213 Sheet 214 Sheet 215 Sheet 216 Sheet 217 Sheet 218 Sheet 219 Sheet 220 Sheet 221 Sheet 222
Every citation, both ways
| Reference | Relation |
|---|---|
| MIYAJI A ET AL: "Efficient elliptic curve exponentiation" INFORMATION AND COMMUNICATIONS SECURITY. FIRST INTERNATIONAL CONFERENCE, ICIS '97. PROCEEDINGS, INFORMATION AND COMMUNICATIONS SECURITY. FIRST INTERNATIONAL CONFERENCE, ICICS '97, BEIJING, CHINA, 11-14 NOV. 1997, pages 282-290, XP000856526 1997, Berlin, Germany, Springer-Verlag, Germany ISBN: 3-540-63696-X | Non-patent |
| MENEZES A J ET AL: "Elliptic curve cryptosystems and their implementation" JOURNAL OF CRYPTOLOGY, AUTUMN 1993, USA, vol. 6, no. 4, pages 209-224, XP002069135 ISSN: 0933-2790 | Non-patent |
12 members in 7 offices; this record represents the family
Priority claims2
| Document | Office | Kind | Date |
|---|---|---|---|
| 5320498 | Japan | – | |
| 5320498 | Japan | A |
Members12
| Document | Office | Kind | |
|---|---|---|---|
| EP0940944A2 | European Patent Office (EPO) | A2 | |
| KR19990077606A | Republic of Korea | A | |
| JPH11316542A | Japan | A | |
| CN1235446A | China | A | |
| EP0940944A3 | European Patent Office (EPO) | A3 | |
| JP3050313B2 | Japan | B2 | |
| TW425803B | Taiwan Province of China | B | |
| US6212277B1 | United States of America | B1 | |
| EP0940944B1This record | European Patent Office (EPO) | B1 | |
| DE69903366D1 | Germany | D1 | |
| DE69903366T2 | Germany | T2 | |
| KR100513127B1 | Republic of Korea | B1 |
31 legal events, as 4 offices reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | Office | |
|---|---|---|---|
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Patent expired after termination of 20 yearsExpiredPE20 | PE20 | GB | |
| Expiry of rightR071 | R071 | DE | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Fee paymentPLFP | PLFP | FR | |
| Fee paymentPLFP | PLFP | FR | |
| Fee paymentPLFP | PLFP | FR | |
| No opposition filedOpposition26N | 26N | EP | |
| No opposition filed within time limitOppositionORIGINAL CODE: 0009261PLBE | PLBE | EP | |
| Information on the status of an ep patent application or granted ep patentGrantedSTATUS: NO OPPOSITION FILED WITHIN TIME LIMITSTAA | STAA | EP | |
| Fr: translation filedET | ET | EP | |
| Corresponds to:REF | REF | EP | |
| Designated contracting statesAK | AK | EP | |
| European patent grantedGrantedFG4D | FG4D | GB | |
| (expected) grantORIGINAL CODE: 0009210GRAA | GRAA | EP | |
| Despatch of communication of intention to grant a patentORIGINAL CODE: EPIDOS IGRAGRAH | GRAH | EP | |
| Despatch of communication of intention to grantORIGINAL CODE: EPIDOS AGRAGRAG | GRAG | EP | |
| Despatch of communication of intention to grant a patentORIGINAL CODE: EPIDOS IGRAGRAH | GRAH | EP | |
| Despatch of communication of intention to grantORIGINAL CODE: EPIDOS AGRAGRAG | GRAG | EP | |
| Designation fees paidDE FR GB ITAKX | AKX | EP | |
| First examination report despatched17Q | 17Q | EP | |
| Request for examination filed17P | 17P | EP | |
| Designated contracting statesAK | AK | EP | |
| Request for extension of the european patentAL;LT;LV;MK;RO;SIAX | AX | EP | |
| Search report despatchedORIGINAL CODE: 0009013PUAL | PUAL | EP | |
| Designated contracting statesAK | AK | EP | |
| Request for extension of the european patentAL;LT;LV;MK;RO;SIAX | AX | EP | |
| Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI | PUAI | EP |
Numbers
- Publication
- 0940944
- Application
- 993016708
Titles3
- German
- Vorrichtung zur Umwandlung einer elliptischen Kurve und Vorrichtung zu deren Verwendung
- English
- Elliptic curve transformation device, utilization device and utilization system
- French
- Dispositif de transformation d'une courbe elliptique et dispositif d'application de cette transformation
Classification
- CPC, 2
- H04L9/3066
- G06F7/725
- IPC, 2
- G06F7 72
- H04L9 30
Designated states4
- Contracting states, 4
- Germany
- France
- United Kingdom
- Italy