Cryptosystems with elliptic curves chosen by users6446205Abstract Participants in a cryptosystem select their own elliptic curve and finite field, rather than using a centrally chosen elliptic curve. The curve is chosen from a predetermined set of elliptic curves expressed as Weierstra.beta. model equations. The public key is based on a participant's unique ID, which must be exchanged during communication setup for non-cryptographic reasons, and a randomly chosen bitstring having a length based on security considerations. The public key can be readily constructed from parameters and mapping functions which are known system-wide and from a small amount of participant dependent data. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
curve d
y.sup.2 = x.sup.3 + 0 x + 16 3
y.sup.2 = x.sup.3 - 270 x - 1512 8
y.sup.2 = x.sup.3 - 35 x - 98 7
y.sup.2 = x.sup.3 - 9504 x - 365904 11
y.sup.2 = x.sup.3 - 608 x + 5776 19
y.sup.2 = x.sup.3 - 13760 x + 621264 43
y.sup.2 = x.sup.3 - 117920 x + 15585808 67
y.sup.2 = x.sup.3 - 34790720 x + 78984748304 163
Since there are eight choices for the value of d, the choice of d can be specified by a three bit number. Specifically, three bits represent numbers {0, 1, . . . , 7} which correspond to the eight choices listed in Table 1. Furthermore, prime number p and elliptic curve E define a pair of intermediate integers a and b, depending on the equation satisfied by elliptic curve E, according to Table 2.
TABLE 2
curve constraints on integers a, b
y.sup.2 = x.sup.3 + 0 x + 16 p .ident. 1 mod 3
a .ident. 1 mod 3
b .ident. 0 mod 3
a.sup.2 + 3b.sup.2 = 4p
y.sup.2 = x.sup.3 - 270 x - 1512 if p .ident. 3 mod 16, then a .ident. 1
mod 4
if p .ident. 11 mod 16, then a .ident. 3 mod 4
a.sup.2 + 2b.sup.2 = p
all others a .noteq. 1
a.sup.2 + db.sup.2 = 4p
Given prime number p and intermediate integer a, the cardinality .vertline.E(F(p)).vertline. of the group of points E(F(p)) of elliptic curve E over field F(p) is a simple closed formula as given in Table 3 where j(a,d)=1 when 2a is a square modulo d and j(a,d)=-1 when 2a is not a square modulo d, with d corresponding to the curve in Table 1. Thus, the software and runtime needed by each participant to count group cardinalities is straightforward enough for the present cryptosystem to be feasible.
TABLE 3
curve group cardinality
y.sup.2 = x.sup.3 + 0 x + 16 .vertline.E(F(p)).vertline.= p + a + 1
y.sup.2 = x.sup.3 - 270 x - 1512 .vertline.E(F(p)).vertline. = p - 2a + 1
y.sup.2 = x.sup.3 - 9504 x - 365904 .vertline.E(F(p)).vertline. = p +
j(a,11)* a + 1
all others .vertline.E(F(p)).vertline. = p - j(a,d)* a
+ 1
Because of the simplicity of the formulas for the cardinality .vertline.E(F(p)).vertline. in Table 3, no complicated software or lengthy runtimes are required to generate a proper finite field and elliptic curve. When elliptic curve E satisfies any of the first three equations of the predetermined set of Weierstra.beta. model equations, then the group cardinality always has a non-trivial divisor c, as specified in Table 4.
TABLE 4
curve fixed divisor c
y.sup.2 = x.sup.3 + 0 x + 16 9
y.sup.2 = x.sup.3 - 270 x - 1512 2
y.sup.2 = x.sup.3 - 35 x - 98 8
all others 1
The prime number p and elliptic curve E are selected so that the cardinality .vertline.E(F(p)).vertline. is given by a simple closed formula, .vertline.E(F(p)).vertline./c=(f*q), with positive integer f.ltoreq.32, q prime. This selection makes the Discrete Logarithm problem in E(F(p)) sufficiently difficult to provide adequate security, when prime number p is chosen to be sufficiently large. Let x denote scalar multiplication in E(F(p)), that is, for a positive integer k and x .epsilon. E(F(p)), kxx.epsilon.E(F(p)) denotes the k-term sum x.sym.x.sym. . . . .sym.x, where .sym. denotes the group operation in E(F(p)). If k is negative, kxx.epsilon.E(F(p)) is defined as the negation -(.vertline.k.vertline.xx).epsilon.E(F(p)) of the point .vertline.k.vertline.xx. If k is equal to zero, kxx is the identity O in E(F(p)). Given prime numbers p and q and elliptic curve E, a point Q in E(F(p)) of order q can be found by looking for a random point P in E(F(p)) such that Q=(c*f)xP in E(F(p)) has order q. For d=3, Q=(3*f)xP instead of (9*f)xP because the order 9 subgroup is not cyclic. The point Q has order q in E(F(p)) if Q.noteq.O; if Q=O, then it is necessary to select a different random point P in E(F(p)) and try again. After p, E, q and Q are selected, the public and private key is determined as follows. First, randomly select a positive integer m<q, with m being the private key, also referred to as the secret key. Next, compute the point G=(mxQ).epsilon.E(F(p)). The public key consists of the five-tuple (p, E, q, Q, G), and the secret key is the integer m. An important aspect of the present invention is how to find prime numbers p, q, elliptic curve E and point Q having the desirable properties presented above. Typically, one would expect to let intermediate integers a and b be defined by prime number p, but in one embodiment of the present invention, the pair of intermediate integers a and b is used to define prime number p. As discussed in detail below, each participant randomly selects a bitstring s having a number of bits equal to security parameter B. The randomly selected bitstring s is concatenated with the participant's unique bitstring ID to form a concatenated bitstring (ID.vertline..vertline.s) which is then mapped by mapping functions to ultimately obtain intermediate integers a, b, which satisfy not only the conditions in one of the rows of Table 2, thereby determining the value of integer d, but also the security requirements set forth above. After values are obtained for (ID, s, b, d), it is straightforward to obtain a portion of the public key (p, E, q, Q), and then the entire public key. Determination of prime numbers p, q, elliptic curve E and point Q by each participant will now be discussed. Let it be assumed that each participant in the system has a unique bitstring ID that identifies that participant and that is recognized by all other participants in the system. In some embodiments, the bitstring ID includes an encoding of descriptive data for the participant, such as name, date of birth, address, social security number, bank account number, personnel number, system specific login name and so on. Let B be an integer valued security parameter. A useful value for B is in the range from 85 to 150, with lower values indicating minimally acceptable security and higher values indicating high security. The value for security parameter B is known system-wide. Let Bs and Bb be two other integer valued security parameters, for example, Bs=30 and Bb=16. The values for Bs and Bb may be independently selected by each participant. Let R1 and R2 be two different mapping functions that map strings of arbitrary length to B-bit positive integers, and let R3 be a mapping function that maps strings of arbitrary length to (2B)-bit positive integers. Mapping functions R1, R2, R3 can be defined using, for example, hash functions. Mapping functions R1, R2, R3 are known system-wide. If the devices to which mapping functions R1, R2, R3 are known are tamperproof devices, then the functions R1, R2, R3 can be considered confidential. An attacker without a cryptosystem device therefore cannot obtain (p, E, q, Q) even if given (ID, s, b1) as resulting from the participant setup procedure set forth in FIG. 5, which enhances security. An attacker with a cryptosystem device may be able to compute (p, E, q, Q), but will have difficulty extracting these values from a tamperproof device. FIG. 5 shows a flow chart for Participant Setup. FIG. 5 depicts how a participant obtains part of its public key, namely (p, E, q, Q). The remaining part, G, is obtained as above, namely, G =(m xQ) .epsilon.E E(F(p)). At step 505, the value for security parameter B and mapping functions R1, R2, R3 are obtained. At step 510, the participant's cryptosystem selects values for security parameters Bs and Bb. At step 515, the participant's cryptosystem randomly selects a bitstring s having Bs bits. At step 520, the participant's cryptosystem applies the mapping functions R1 and R2 to the concatenation of its identity ID and the bitstring s to obtain two positive B-bit integers a=R1(ID.vertline..vertline.s) and b0=R2(ID.vertline..vertline.s), and also initializes an integer b1, b1=0. Let b=b0+b1. At step 525, the participant's cryptosystem checks if conditions on a and b are satisfied, as set forth in FIG. 6. At step 530, the participant's cryptosystem determines whether the result of the check is that conditions are satisfied. If so, at step 535, the cryptosystem outputs the values s, b1, p, E, q and Q and terminates. If not, at step 545, the participant's cryptosystem increments b1, and, at step 550, checks whether the incremented b1 is too big, that is, b1.gtoreq.2.sup.Bb. If the incremented b1 is appropriately small, then the participant's cryptosystem returns to step 525 to recompute b as b0+b1 and to check conditions on a and b. If the incremented b1 is too big, then the participant's cryptosystem returns to step 515 to select a new bitstring s. Because of the Prime Number Theorem, the procedure in FIG. 5 must terminate. Practically, the procedure of FIG. 5 requires at most a few minutes runtime on readily available microprocessors such as an Intel Pentium. FIG. 6 shows a flow chart for checking conditions on the pair of intermediate integers a and b. At step 605, the participant's cryptosystem checks whether the intermediate integers a and b satisfy the condition for discriminant -3, as set forth in FIG. 7. At step 610, the result of the check in step 605 is evaluated. If the conditions for discriminant -3 are satisfied, then at step 615, the procedure terminates with a positive result. If the conditions for discriminant -3 are not satisfied, then at step 620, the participant's cryptosystem checks whether the intermediate integers a and b satisfy the condition for discriminant -8, as set forth in FIG. 8. At step 625, the result of the check in step 620 is evaluated. If the conditions for discriminant -8 are satisfied, then at step 615, the procedure terminates with a positive result. If the conditions for discriminant -8 are not satisfied, then at step 630, the participant's cryptosystem initializes the set D as {7, 11, 19, 43, 67, 163} and initializes the integer d as d=7, which is seen to be the first element in the set D. At step 635, the participant's cryptosystem checks whether the intermediate integers a and b satisfy the condition for discriminant -d, as set forth in FIG. 9. At step 640, the result of the check in step 635 is evaluated. If the conditions for discriminant -d are satisfied, then at step 615, the procedure terminates with a positive result. If the conditions for discriminant -d are not satisfied, then at step 645, the participant's cryptosystem removes d from D, and at step 650, checks whether there are any values remaining in the set D. If there are values remaining, at step 655, the cryptosystem sets d to a value remaining in the set D, and returns to step 635. If the set D is empty, then at step 660, the cryptosystem terminates with a negative result, namely, the intermediate integers a and b do not satisfy the conditions required for the present invention. FIG. 7 shows a flow chart for checking whether the intermediate integers a and b satisfy the condition for discriminant -3. At step 705, the participant's cryptosystem checks whether the conditions set forth in the first case of Table 2 are satisfied, namely, if a.ident.1 mod 3, b.ident.0 mod 3, a.sup.2 +3b.sup.2 is divisible by 4, and if the quotient p=(a.sup.2 +3b.sup.2)/4 has remainder 1 upon division by 3. If any of these conditions are not satisfied, then at step 710, the procedure returns with a negative result. If the aforementioned conditions of Table 2 are satisfied, then at step 715, the cryptosystem checks if the remainder of p upon division by 4 is 3, and if p is a prime number. If any of these conditions are not satisfied, then at step 710, the procedure returns with a negative result. The primality of p is tested using a probabilistic compositeness test wherein if p can be proved to be composite, then p is not prime, and if the proof of compositeness for p fails, then p is assumed to be prime. If the aforementioned conditions are satisfied, then at step 720, the cryptosystem checks if (p+a+1)/9=f*q, for a positive integer f.ltoreq.32 and a prime number q. If any of these conditions are not satisfied, then at step 710, the procedure returns with a negative result. If the aforementioned conditions are satisfied, then at step 725, the cryptosystem checks whether the point condition, as set forth in FIG. 10, is satisfied for ID, s, with s, e=3*f, p, q and E given by y.sup.2 =x.sup.3 +x+16, the first of the elliptic curve equations set forth above. At step 730, the cryptosystem evaluates the result of the check in step 725. If the result is negative, then at step 710, the procedure returns with a negative result. If the result is positive, then at step 735, the procedure returns the result that the conditions for discriminant -3 are satisfied, with p, E, q, Q, being as returned by the point condition procedure of FIG. 10. FIG. 8 shows a flow chart for checking whether the intermediate integers a and b satisfy the condition for discriminant -8. At step 805, the participant's cryptosystem obtains p=a.sup.2 +2b.sup.2 and checks whether the conditions set forth in the second case of Table 2 are satisfied, namely, if, when p.ident.3 mod 16, then a.ident.1 mod 4, and if, when p.ident.11 mod 16, then a.ident.3 mod 4. If any of these conditions are not satisfied, then at step 810, the procedure returns with a negative result. If the aforementioned conditions of Table 2 are satisfied, then at step 815, the cryptosystem checks if the remainder of p upon division by 4 is 3, and if p is a prime number. If any of these conditions are not satisfied, then at step 810, the procedure returns with a negative result. If the aforementioned conditions are satisfied, then at step 820, the cryptosystem checks if (p-2a+1)/2=f*q, for a positive integer f.ltoreq.32 and a prime number q. If any of these conditions are not satisfied, then at step 810, the procedure returns with a negative result. If the aforementioned conditions are satisfied, then at step 825, the cryptosystem checks whether the point condition, as set forth in FIG. 10, is satisfied for ID, s, with s, e=2*f, p, q and E given by y.sup.2 =x.sup.3 -270x-1512, the second of the elliptic curve equations set forth above. At step 830, the cryptosystem evaluates the result of the check in step 825. If the result is negative, then at step 810, the procedure returns with a negative result. If the result is positive, then at step 835, the procedure returns the result that the conditions for discriminant -8 are satisfied, with p, E, q, Q, being as returned by the point condition procedure of FIG. 10. FIG. 9 shows a flow chart for checking whether the intermediate integers a and b satisfy the condition for discriminant -d, d being one of (7, 11, 19, 43, 67, 163). At step 905, the participant's cryptosystem checks whether the conditions set forth in the third case of Table 2 are satisfied, namely, if a.noteq.1 and if a.sup.2 +db.sup.2 =4p for an integer p. If any of these conditions are not satisfied, then at step 910, the procedure returns with a negative result. If the aforementioned conditions of Table 2 are satisfied, then at step 915, the cryptosystem checks if the remainder of p upon division by 4 is 3, and if p is a prime number. If any of these conditions are not satisfied, then at step 910, the procedure returns with a negative result. If the aforementioned conditions are satisfied, then at step 920, the cryptosystem checks if (p+j(a,11)*a+1)/c=f*q if d=11 and if(p-j(a,d)*a+1)/c=f*q otherwise, where j(a, d)=1 when 2a is a square modulo d and j(a,d)=-1 when 2a is not a square modulo d, for a positive integer f.ltoreq.32 and a prime number q, with c=8 for the case of d=7, and c=1 for all other cases. If any of these conditions are not satisfied, then at step 910, the procedure returns with a negative result. If the aforementioned conditions are satisfied, then at step 925, the cryptosystem checks whether the point condition, as set forth in FIG. 10, is satisfied for ID, s, with s, e=2*f, p, q and E given by the third through eighth of the elliptic curve equations set forth above, based on the value for d. At step 930, the cryptosystem evaluates the result of the check in step 925. If the result is negative, then at step 910, the procedure returns with a negative result. If the result is positive, then at step 935, the procedure returns the result that the conditions for the appropriate one of the selected discriminants are satisfied, with p, E, q, being as returned by the point condition procedure of FIG. 10. FIG. 10 shows a flow chart for checking whether the point condition is satisfied for ID, s, e, p, q and E, where E is specified by the elliptic curve equation y.sup.2 =x.sup.3 +ux+v. At step 1005, the participant's cryptosystem tries to find a positive integer m such that two constraints are satisfied: first, that m*(ln(m*ln(p))).sup.2.ltoreq.0.02*(ln(p)).sup.2 and second, that q divides p.sup.m -1. Specifically, the cryptosystem checks if q divides p.sup.m -1 for m=1, 2, . . . in succession until m*(ln(m*ln(p))).sup.2 >0.02*(ln(p)).sup.2. If an m satisfying these two constraints is found, then the point condition is not satisfied, and the procedure returns at step 1010 with a negative result. If no such m is found, then at step 1015, the cryptosystem obtains x=R3(ID.vertline..vertline.s) mod p and checks whether r=x.sup.3 +ux+v is a square in F(p), with u and v being the parameters of the elliptic curve equations set forth above. If r, as defined, is not a square in F(p), then the point condition is not satisfied, and the procedure returns at step 1010 with a negative result. If r, as defined, is a square in F(p), then at step 1020, the cryptosystem obtains one of the square roots of r as y=r.sup.(p+1)/4 mod p in F(p), forms the point P=(x, y) in E(F(p)) and multiplies P by the scalar value e in the group E(F(p)) to produce the point Q=exP in E(F(p)). At step 1025, the cryptosystem checks whether the point Q does not have order q in E(F(p)), that is, whether Q is equal to the identity element O in E(F(p)). If the order of Q is not equal to q, then the point condition is not satisfied, and the procedure returns at step 1010 with a negative result. If the point Q has order q in E(F(p)), then the point condition is satisfied and the procedure returns at step 1030 with a positive result. An important aspect of the present invention is that, given B, R1, R2, R3, ID, s, b1 and d, any participant can reconstruct (p, E, q, Q). A public key reconstruction procedure is presented below. Since B, R1, R2, R3, are known to all participants, it is only necessary to obtain the values (ID, s, b1, d) to construct the (p, E, q, Q) portion of another participant's public key. It will be appreciated that communication with a participant requires identifying information ID even without the present cryptosystem. The remaining portion of the public key, G in E(F(p)), must be sent to any participant wishing to communicate with the participant using G. Specifying the x-coordinate of G reduces the possibilities for the y-coordinate of G down to two: a larger number and a smaller number. Thus, it will be appreciated that, to represent G, it is necessary to send only the x-coordinate of G and a single bit indicating the larger or smaller y-coordinate. Let L(x) denote the binary length of a non-negative integer x, that is, the number of bits required for a binary representation of x. Using the Weierstra.beta. model, y.sub.0 (X) and y.sub.1 (X) for any X can be found with a square root computation in F(p), such that (y.sub.i (X)).sup.2 =X.sup.3 +uX+v, for i=1, 2. When p.ident.3 mod 4, the square root of a square r in F(p) can be found quickly as r.sup.1/2 =r.sup.(p+1)/4, which allows reduction of the 2L(p) bits required to describe a point on the curve to 1+L(p) bits by specifying the X-coordinate and a single bit indicating y.sub.0 (X) or y.sub.i (X). Public key size will now be discussed. The public key for a participant consists of (p, E, q, Q, G). Reconstruction of a public key requires only (ID, s, b1, d, G). The length of ID may be any number of bits, as selected by a participant; this information is required to communicate with the participant, under any scheme, and so should not be counted in the size of the participant's public key. The bit lengths of s and b1 are Bs and Bb, respectively, as selected in step 510 of FIG. 5, and may be, for example, Bs=30 and Bb=16. There are eight choices for d, so three bits are required to represent d. The number of bits required for G is L(p)+1. The prime p obtained in the participant setup procedure described above has a length L(p) close to 2*B, with B being the integer valued security parameter introduced above. Thus, the amount of information from which a public key of a party of known ID can be derived is 30+16+3+L(p)+1=50+L(p) bits. When the present cryptosystem is used with certification, the message to be certified has a length of L(ID)+50 +L(p) bits, which is relatively short in comparison with conventional cryptosystems. As an illustration, the length of the public key (p, E, q, Q, G), if represented conventionally and as created by a conventional central authority, would be expected to be L(p)+L(E)+L(q)+L(Q)+L(G)=L(p)+(2*L(p))+(at least L(p)/2)+(L(p)+1)+(L(p)+1)=at least 5.5*L(p)+2 bits. If this conventional representation were used, the cryptographic overhead information would have a length of at least L(ID)+5.5*L(p)+2 bits. It can readily be seen that the reduction in cryptographic information length is the difference between the length in a conventional scheme and the length in the present cryptosystem, (at least L(ID)+5.5*L(p)+2)-(L(ID)+50+L(p))=at least 4.5*L(p)-48 bits. Typically, the prime p has a length of around 170 bits, although this could be another value, for a savings of 717 bits. The reduced bit length attained by the present invention is advantageous in at least transmission, that is, more efficient use of bandwidth since less bandwidth is needed for cryptographic overhead, and storage, since reconstruction is very easy, as shown below. In the conventional scheme, where a central authority creates the (p, E, q, Q) portion of a participant's public key, the length of the message to be certified is L(ID)+L(p)+1. In the present cryptosystem, the length of the message to be certified is L(ID)+L(p)+50,which is only 49 bits more, yet achieves much higher security. There can be redundancy in s and b1, to make creation of fraudulent public key and ID pairs more difficult. An embodiment of a procedure for public key reconstruction is set forth in FIGS. 11A and 11B, which are referred to collectively as FIG. 11. The procedure depicted in FIG. 11 demonstrates that, given a participant's identifying information ID and the values s, b1 and d, E corresponding to d according to Table 1, and given B, R1, R2, R3, it is very easy to construct the participant's (p, E, q, Q) values. At step 1105, the value B and the functions R1, R2, R3 are obtained. At step 1110, the value a is obtained as a=R1(ID.vertline..vertline.s) and the value b is obtained as b=R2(ID.vertline..vertline.s)+b1. At step 1115, the conditions on a and b are checked; as before, the specific conditions depend on the value of d. While checking conditions as in steps 705, 805 or 905, as described in step 1115, p is computed as in steps 705, 805 or 905, respectively. If the result of the condition check at step 1115 is negative, then at step 1120, the public key reconstruction procedure fails. If the result of the condition check at step 1115 is positive, then at step 1125 it is determined whether a thorough correctness check is required. If not, then the cryptosystem advances to step 1135. If a thorough correctness check is required, then at step 1130, the cryptosystem checks whether p is a prime number with remainder equal to 3 upon division by 4 using, for example, a probabilistic compositeness test. A thorough correctness check may be carried out by the party that creates a certificate for the public key: before certifying user dependent information (ID, s, b1, G) needed to reconstruct the public key, the certifying party performs the Public Key Reconstructions with a Thorough Correctness check. If, and only if, the public key can be reconstructed correctly and passes all thorough correctness tests, does the certifying party provide the desired certificate. Other parties that receive the certified user dependent information (ID, s, b1, G) need not test p and q for primality because of their correctness certification. If the check at step 1130 is negative, then at step 1120, the public key reconstruction procedure fails. At step 1135, depending on the value of d, values are assigned to c and t. At step 1140, the cryptosystem determines the largest positive integer f.ltoreq.32 such that c*f divides (p-t*a+1), and q is obtained as q=(p-t*a+1)/(c*f). At step 1145, it is again determined whether a thorough correctness check is required using the same criteria as in step 1125. If not, then the cryptosystem advances to step 1155. If a thorough correctness check is required, then at step 1147 it is checked that there is no integer m such that m*(ln(m*ln(p))).sup.2.ltoreq.0.02 *(ln(p)).sup.2 and such that q divides p.sup.m -1. If the test at step 1147 fails, then at step 1120, the public key reconstruction procedure fails. If the test at step 1147 is positive, then at step 1150, the primality of q is checked. If the check at step 1150 is negative, then at step 1120, the public key reconstruction procedure fails. At step 1155, the proper one of the elliptic curves E is selected based on the value for d, in accordance with Table 1. The value x is obtained as R3(ID.vertline..vertline.s) mod p, the value y is obtained as (x.sup.3 +ux+v).sup.(p+1)/4 in F(p), and P is set to (x, y). At step 1157, it is determined whether d=3, and if so, then c is replaced by 3, because the order 9 subgroup is not cyclic. At step 1158 it is determined whether a Thorough Correctness check is required, using the same criteria as in step 1125. If not, the cryptosystem advances to step 1160. If a Thorough Correctness check is required, then at step 1159, values are obtained for r=x.sup.3 +ux+v and s=y.sup.2 and it is checked if r=s. If not, then at step 1120, the public key reconstruction procedure fails. If r=s, then the cryptosystem advances to step 1160. At step 1160, the point Q is obtained as (c*f)xP in E(F(p)). At step 1165, it is checked whether Q is the identity element O in E(F(p)); if so, then at step 1120, the public key reconstruction procedure fails. If Q is not the identity element, then at step 1167 it is determined whether a Thorough Correctness check is required, using the same criteria as in step 1125. If not, then the cryptosystem advances to step 1170. If a Thorough Correctness check is required, then at step 1168 the point R in E(F(p)) is obtained as qxQ in E(F(p)) and it is checked if R is equal to the identity element O in E(F(p)). If so, then the cryptosystem advances to step 1170. If R is not the identity element, then at step 1120 the public key reconstruction procedure fails. If R is the identity element, then at step 1170, the values (p, E, q, Q) are output and the public key reconstruction procedure is terminated. The only steps in the public key reconstruction procedure which require any substantial computation are the primality checks and the check whether R is the identity element O. Exclusive of these checks, the public key reconstruction procedure takes only milliseconds to execute on a conventional, widely available processor such as an Intel Pentium. Examples of public keys generated according to the above-described method will now be discussed. FIGS. 12A-12D provide respective sets of values for public keys (p, E, q, Q). In these examples, for the participant's ID, the binary (base 2) bitstring having decimal (base 10) representation 11223344556677889900 was arbitarity used, security parameters Bs=30 and Bb=8 were used, and the following mapping functions were used: R1(x)=x.sup.8 mod2.sup.B R2(x)=(reverse(x)).sup.8 mod2.sup.B R3(x)=(reverse(x).vertline..vertline.x).sup.8 mod2.sup.2B The bitstring x is in binary (base 2), for example "11001" corresponding to a decimal (base 10) value of "25". The function "reverse (x)" reverses the order of bits in a bitstring, for example, reverse (11001)=10011. The operator ".vertline..vertline." denotes concatenation of bitstrings, for example (10011 .vertline..vertline. 11001)=1001111001. The examples in FIGS. 12A and 12B illustrate security parameter B=85, that is, a relatively low value, while the examples in FIGS. 12C and 12D illustrate security parameter B=150, that is, a relatively high value. Bitstring s is a different randomly chosen value in each example. All public keys (p, E, q, Q) were successfully reconstructed using the same mapping functions R1, R2, R3, participant's ID and the bitstring s and parameter b1 values set forth in the respective examples of FIGS. 12A-12D. Once keys have been initialized in accordance with the present invention, the keys can be used in combination with any elliptic curve cryptosystem. In most conventional elliptic curve cryptosystems, a substantial portion of the runtime is devoted to computation of kxQ for a randomly selected k. In many implementations, this computation can be made faster if, for instance, the x-coordinate of Q has some known fixed value such as zero. If c=1, this is ensured by requiring that R3 yields zero. Also, if c>1, it may be required that R3 yields zero if d is other than 3, and compute (k*c)xP=kxQ, which leads to a considerable speed improvement. Similarly, for d=3, it may be required that R3 yields 1, although the saving obtained in this case is much smaller. Although an illustrative embodiment of the present invention, and various modifications thereof, have been described in detail herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to this precise embodiment and the described modifications, and that various changes and further modifications may be effected therein by one skilled in the art without departing from the scope or spirit of the invention as defined in the appended claims.
|
Same subclass Same class Consider this |
||||||||||