Elliptical curve converting device and device and system for use thereof
Elliptical curve converting device and device and system for use thereof
 CN 1,235,446 A
 Filed: 03/04/1999
 Published: 11/17/1999
 Est. Priority Date: 03/05/1998
 Status: Abandoned Application
First Claim
1. elliptic curve E of a conversion and generate the elliptical curve converting device of other elliptic curves Et comprises:
 Receive the parameter a of prime number p, elliptic curve E and parameter b from the outside, as the receiving system of first G of basic point, wherein elliptic curve E is defined within on the limited body GF (p), represents with y^2=x^3+ax+b, and first G is present on the elliptic curve E, (x0 y0) represents with G=;
Obtain the conversion coefficient acquisition device that is present in the conversion coefficient t on the limited body GF (p), conversion coefficient t t ≠
0 that satisfies condition wherein, and, to compare with prime number p, the figure place of t^4 * a (modp) is few;
Calculate the parameter a '"'"', parameter b of elliptic curve Et '"'"' and elliptic curve calculating apparatus of the new Gt of basic point unit according to following formula with the described conversion coefficient t that obtains,a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first Gt;
Described parameter a '"'"', b '"'"' that calculates to outside output and the output device of first Gt.
Chinese PRB Reexamination
Abstract
A parameter receiving unit receives parameters alpha and beta of an elliptic curve E and an element G on the elliptic curve E. A transformation coefficient acquiring unit calculates a transformation coefficient t which is an element on a finite field GF(p) so that t{circumflex over ( )}4*alpha(mod p) will not exceed 32 bits. A transformed elliptic curve calculating unit calculates parameters alpha'"'"' and beta'"'"' of an elliptic curve Et that is defined over the finite field GF(p) and expressed as Et: y'"'"'{circumflex over ( )}2=x'"'"'{circumflex over ( )}3+alpha'"'"'*x'"'"'+beta'"'"', and calculates an element Gt=(xt0,yt0) that is present on the elliptic curve Et and corresponds to the element G, as follows:alpha'"'"'=alpha'"'"'t{circumflex over ( )}4, beta'"'"'=betaxt{circumflex over ( )}6, xt0=t{circumflex over ( )}2*x0, yt0=t{circumflex over ( )}3*y0A, parameter sending unit sends the parameters alpha'"'"' and beta'"'"' and the element Gt to an external device.
12 Claims

1. elliptic curve E of a conversion and generate the elliptical curve converting device of other elliptic curves Et comprises:

Receive the parameter a of prime number p, elliptic curve E and parameter b from the outside, as the receiving system of first G of basic point, wherein elliptic curve E is defined within on the limited body GF (p), represents with y^2=x^3+ax+b, and first G is present on the elliptic curve E, (x0 y0) represents with G=; Obtain the conversion coefficient acquisition device that is present in the conversion coefficient t on the limited body GF (p), conversion coefficient t t ≠
0 that satisfies condition wherein, and, to compare with prime number p, the figure place of t^4 * a (modp) is few;Calculate the parameter a '"'"', parameter b of elliptic curve Et '"'"' and elliptic curve calculating apparatus of the new Gt of basic point unit according to following formula with the described conversion coefficient t that obtains, a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first Gt; Described parameter a '"'"', b '"'"' that calculates to outside output and the output device of first Gt.


2. according to the elliptical curve converting device of claim 1, it is characterized in that p is 160 a prime number, described conversion coefficient acquisition device is obtained the conversion coefficient t that satisfies following condition, and t^4 * a (modp) is the number below 32.

3. according to the elliptical curve converting device of claim 1, it is characterized in that described conversion coefficient acquisition device obtains the conversion coefficient t that satisfies following condition, t^4 * a (modp) is3.

4. according to the elliptical curve converting device of claim 1, it is characterized in that described conversion coefficient acquisition device establishes variable T, and to establish initial value be3, by getting initial value value in addition to the order of the big value of figure place from the little value of figure place, judge the T=t^4 * a (modp) that whether satisfies condition repeatedly, obtain conversion coefficient t thus.

5. one kind is utilized system by elliptic curve E of conversion and the elliptic curve that generates the elliptical curve converting device of other elliptic curves Et and utilize the use device of the elliptic curve Et generated to constitute, it is characterized in that:

Described use device is provided with first output device, first receiving device and use device, and described elliptical curve converting device is provided with second receiving system, conversion coefficient acquisition device, elliptic curve calculating apparatus and second output device; Described first output device is to the parameter a of described elliptical curve converting device output prime number p, elliptic curve E and parameter b, as first G of basic point;
Wherein elliptic curve E is defined within on the limited body GF (p), and represents that with y^2=x^3+ax+b first G is present on the elliptic curve E, and (x0 y0) represents with G=;Described second receiving system receives the parameter a of prime number p, elliptic curve E and parameter b, first G from described use device; Described conversion coefficient acquisition device is obtained the conversion coefficient t that is present on the limited body GF (p), conversion coefficient t t ≠
0 that satisfies condition wherein, and with prime number p relatively, t^4 * a (modp) figure place is few;Described elliptic curve calculating apparatus is calculated the parameter a '"'"', parameter b of elliptic curve Et '"'"' and new first Gt as basic point according to following formula with the described conversion coefficient t that obtains, a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0=t^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first Gt; Described parameter a '"'"', b '"'"' and first Gt that described second output device is calculated to described use device output; Described first receiving device receives the described parameter a '"'"' that is output, b '"'"' and first Gt; Described use device is used by the elliptic curve of prime number p, the described parameter a '"'"' that receives and b '"'"' decision and as the first Gt of basic point and is carried out encryption, deciphering, digital sign, digital sign checking or the key of discrete logarithm problem as the basis of fail safe had according to the computing on the elliptic curve that is defined on the limited body GF (p).


6. the elliptic curve according to claim 5 utilizes system, it is characterized in that p is 160 a prime number, and described conversion coefficient acquisition device is obtained the conversion coefficient t that satisfies following condition, and t^4 * a (modp) is the number below 32.

7. the elliptic curve according to claim 5 utilizes system, it is characterized in that described conversion coefficient acquisition device obtains the conversion coefficient t that satisfies following condition, and t^4 * a (modp) is3.

8. the elliptic curve according to claim 5 utilizes system, it is characterized in that described conversion coefficient acquisition device establishes variable T, and to establish initial value be3, by getting initial value value in addition to the order of the big value of figure place from the little value of figure place, judge the T=t^4 * a (modp) that whether satisfies condition repeatedly, obtain conversion coefficient t thus.

9. one kind is provided with second receiving system, conversion coefficient acquisition device, elliptic curve calculating apparatus and second output device, receive and utilize the use device of the aforementioned elliptic curve Et that generates from elliptic curve E of conversion and the elliptical curve converting device that generates other elliptic curves Et, it is characterized in that:

Described use device is provided with first output device, first receiving device and use device; Described first output device is to the parameter a of described elliptical curve converting device output prime number p, elliptic curve E and parameter b, as first G of basic point;
Wherein elliptic curve E is defined within on the limited body GF (p), and represents that with y^2=x^3+ax+b first G is present on the elliptic curve E, and (x0 y0) represents with G=;Described second receiving system receives the parameter a of prime number p, elliptic curve E and parameter b, first G from described use device; Described conversion coefficient acquisition device is obtained the conversion coefficient t that is present on the limited body GF (p), conversion coefficient t t ≠
0 that satisfies condition wherein, and with prime number p relatively, t^4 * a (modp) figure place is few;Described elliptic curve calculating apparatus is calculated the parameter a '"'"', parameter b of elliptic curve Et '"'"' and first Gt according to following formula with the described conversion coefficient t that obtains, a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0=t^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first Gt; Described parameter a '"'"', b '"'"' and first Gt that described second output device is calculated to described use device output; Described first receiving device receives the described parameter a '"'"' that is output, b '"'"' and first Gt; Described use device is used by the elliptic curve of prime number p, the described parameter a '"'"' that receives and b '"'"' decision and as the first Gt of basic point and is carried out encryption, deciphering, digital sign, digital sign checking or the key of discrete logarithm problem as the basis of fail safe had according to the computing on the elliptic curve that is defined on the limited body GF (p).


10. use device that utilizes the elliptic curve Et that elliptic curve E of conversion generated comprises:

The parameter a '"'"' of storage elliptic curve Et, parameter b '"'"' and as the storage device of first Gt of basic point; Use device that discrete logarithm problem is had as encryption, deciphering, digital sign, digital sign checking or the key of the basis of fail safe is carried out in utilization according to the computing on the elliptic curve that is defined on the limited body GF (p) by the elliptic curve of p, the described parameter a '"'"' that receives and b '"'"' decision and as first Gt of basic point;
Wherein parameter a '"'"', parameter b '"'"' and first Gt generate by elliptical curve converting device, described elliptical curve converting device is provided with conversion coefficient acquisition device, elliptic curve calculating apparatus, p is a prime number, elliptic curve E is defined within on the limited body GF (p), and represent with y^2=x^3+ax+b, first G as basic point is present on the elliptic curve E, and (x0 y0) represents with G=;Described conversion coefficient acquisition device is obtained the conversion coefficient t that is present on the limited body GF (p), conversion coefficient t t ≠
0 that satisfies condition wherein, and with prime number p relatively, t^4 * a (modp) figure place is few;Described elliptic curve calculating apparatus is calculated the parameter a '"'"', parameter b of elliptic curve Et '"'"' and new first Gt as basic point according to following formula with the described conversion coefficient t that obtains, a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0=t^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first G=t.


11. elliptic curve E of a conversion generates the elliptic curve transform method of other elliptic curves Et, comprises following steps:

Receive the parameter a of prime number p, elliptic curve E and parameter b from the outside, as the receiving step of first G of basic point, wherein elliptic curve E is defined within on the limited body GF (p), represents with y^2=x^3+ax+b, and first G is present on the elliptic curve E, (x0 y0) represents with G=; Obtain the conversion coefficient that is present in the conversion coefficient t on the limited body GF (p) and calculate step, conversion coefficient t t ≠
0 that satisfies condition wherein, and, to compare with prime number p, the figure place of t^4 * a (modp) is few;Calculate the parameter a '"'"', parameter b of elliptic curve Et '"'"' and calculate step according to following formula with the described conversion coefficient t that obtains as the elliptic curve of first Gt of new basic point, a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0=t^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first Gt; Output step to the outside output described parameter a '"'"' that is calculated, b '"'"' and first Gt.


12. one kind is being write down the computerreadable recording medium that elliptic curve E of conversion generates the elliptic curve conversion program of other elliptic curves Et, described program comprises following steps:

Receive the parameter a of prime number p, elliptic curve E and parameter b from the outside, as the receiving step of first G of basic point, wherein elliptic curve E is defined within on the limited body GF (p), represents with y^2=x^3+ax+b, and first G is present on the elliptic curve E, (x0 y0) represents with G=; Obtain the conversion coefficient that is present in the conversion coefficient t on the limited body GF (p) and calculate step, conversion coefficient t t ≠
0 that satisfies condition wherein, and, to compare with prime number p, the figure place of t^4 * a (modp) is few;Calculate the parameter a '"'"', parameter b of elliptic curve Et '"'"' and calculate step according to following formula with the described conversion coefficient t that obtains as the elliptic curve of first Gt of new basic point, a′
=a×
t^4b′
=b×
t^6xt0=t^2×
x0yt0=t^3×
y0Wherein elliptic curve Et is defined within on the limited body GF (p), represents with y '"'"' ^2=x '"'"' ^3+a '"'"' * x '"'"'+b '"'"', and xt0, yt0 are respectively x coordinate figure, the y coordinate figures of first Gt; Output step to the outside output described parameter a '"'"' that is calculated, b '"'"' and first Gt.

Specification(s)