0001 This invention relates to a method for performing computations in cryptographic systems utilizing elliptic curves.

BACKGROUND OF THE INVENTION 0002 A public-key data communication system may be used to transfer information between a pair of correspondents. At least part of the information exchanged is enciphered by a predetermined mathematical operation by the sender and the recipient may perform a complementary mathematical operation to decipher the information. 0003 Each correspondent has a private key and a public key that is mathematically related to the private key. The relationship is such that it is not feasible to determine the private key from knowledge of the public key. The keys are used in the transfer of data, either to encrypt data that is to be transferred or to attach a signature to allow verification of the authenticity of the data. 0004 For encryption, one correspondent uses the public key of the recipient to encrypt the message and sends it to the recipient The recipient then uses her private key to decipher the message. 0005 A common key may also be generated by combining one parties public key with the other parties private key. It is usual in such cases to generate new private and corresponding public keys for each communication session, usually referred to as session keys or ephemeral keys, to avoid the long-term keys of the parties being compromised. 0006 The exchange of messages and generation of the public keys may therefore involve significant computation involving exponentiation when the cryptographic system utilizes in Z*p, the finite field of integers mod p where p is a prime or the analogous operation of point multiplication when the system utilizes an elliptic curve. In an elliptic curve system, an ephemeral key pair is obtained by generating a secret integer, k and performing a point multiplication in the seed point Q to provide the ephemeral public key kQ. Similarly, the generation of a common ephemeral session key will require multiplication of a public key kaQ, which is a point on the curve, with a secret integer kb of the other correspondent so that point multiplication is again required. 0007 A similar procedure is used to sign a message except that the sender applies his private key to the message. This permits any recipient to recover and verify the message using the senders public key. 0008 Various protocols exist for implementing such a scheme and some have been widely used. In each case, however, the sender is required to perform a computation to sign the information to be transferred and the receiver is required to perform a computation to verify the signed information. 0009 In a typical implementation a signature component s has the form: 0010 saek (mod n) 0011 where; in an elliptic curve crypto system, 0012 P is a point on the underlying curve which is a predefined parameter of the system; 0013 k is a random integer selected as a short term private or session key; 0014 RkP is the corresponding short term public key; 0015 a is the long term private key of the sender; 0016 QaP is the senders corresponding public key; 0017 e is a secure hash, such as the SHA-1 hash function, of a message m and the short term public key R; and 0018 n is the order of the curve. 0019 The sender sends to the recipient a message including m, s, and R and the signature is verified by computing the value R1(sP-eQ) which should correspond to R. If the computed values correspond then the signature is verified. 0020 In order to perform the verification it is necessary to compute the point multiplications to obtain sP and eQ, each of which is computationally complex. Where the recipient has adequate computing, power this does not present a particular problem but where the recipient has limited computing power, such as in a secure token or a Smart card application, the computations may introduce delays in the verification process. 0021 Key generation and signature protocols may therefore be computationally intensive. As cryptography becomes more widely used there is an increasing demand to implement cryptographic systems that are faster and that use limited computing power, such as may be found on a smart card or wireless device. 0022 Elliptic curve cryptography (ECC) provides a solution to the computation issue. ECC permits reductions in key and certificate size that translates to smaller memory requirements, and significant cost savings. ECC can not only significantly reduce the cost, but also accelerate the deployment of smart cards in next-generation applications. Additionally, although the ECC algorithm allows for a reduction in key size, the same level of security as other algorithms with larger keys is maintained. 0023 However, there is still a need to perform faster calculations on the keys so as to speed up the information transfer while maintaining a low cost of production of cryptographic devices. 0024 Computing multiples of a point on an elliptic curve is one of the most frequent computations performed in elliptic curve cryptography. One method of speeding up such computations is to use tables of precomputed multiples of a point. This technique is more useful when a point is known beforehand. However, there are cases when multiples of previously unknown points are required (for example, in ECDSA verification). Thus there is a need for a system and method for facilitating point multiplications.

SUMMARY OF THE INVENTION 0025 In general terms, the present invention represents the scalar k as a combination of components ki and an integer derived from an endomorphism in the underlying curve. 0026 The method is based on the observation that, given an elliptic curve (EC) having complex multiplication mapping over a finite field, there is an , which is the solution to a quadratic, for which the complex multiplication mapping is equivalent to multiplying a point Q by . It will often be less computationally expensive to compute Q via the complex multiplication map, compared to treating as a integer and performing the EC multiplication. In practice, point multiplication by other scalars (not just ) is required. It is also shown how the multiplication mapping may be used to compute other multiples of the point. 0027 In accordance with this invention there is provided a method for accelerating multiplication of an elliptic curve point Q(x,y) by a scalar k, the method comprising the steps of: selecting an elliptic curve over a finite field F such that there exists an endomorphism , where (Q)Q for all points Q(x,y) on the elliptic curve; and using smaller representation ki of the scalar k in combination with the mapping to compute the scalar multiple of the elliptic curve point Q.

BRIEF DESCRIPTION OF THE DRAWINGS 0028 These and other features of the preferred embodiments of the invention will become more apparent in the following detailed description in which reference is made to the appended drawings wherein: 0029 FIG. 1 is a schematic diagram of a communication system; 0030 FIG. 2 is a flow chart showing the steps of implementing a first embodiment of the present invention. 0031 FIG. 3 is a flow chart showing the steps of providing parameters required to implement the method of FIG. 2.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 0032 For convenience in the following description, like numerals refer to like structures in the drawings. Referring to FIG. 1, a data communication system 10 includes a pair of correspondents, designated as a sender 12, and a recipient 14, connected by a communication channel 16. Each of the correspondents 12,14 includes a cryptographic processor 18,20 respectively that may process digital information and prepare it for transmission through the channel 16 as will be described below. Each of the correspondents 12,14 also includes a computational unit 19,21 respectively to perform mathematical computations related to the cryptographic processors 18,20. The processors 18,20 may be embodied in an integrated circuit incorporated in the processor or may be implemented as instructions encoded on a data carrier to implement a predetermined protocol in conjunction with a general purpose processor. For the purpose of illustration it will be assumed that the correspondent 12 is in the form of a smart card having a dedicated processor 18 with relatively limited computing power. The processor 20 may be a central server communicating with the card by channel 16 and channel 16 may be a wireless communication channel if preferred. 0033 The cryptographic processors 18 implement an elliptic curve cryptographic system, of ECC, and one of the functions of the cryptographic processor 18 is to perform point multiplications of the form kQ, where k is an integer and Q a point on the underlying elliptic curve, so that they may be used as a key pair k, kQ in a cryptographic scheme. As noted above, cryptographic computations such as the multiplication of an elliptic curve point by a scalar value are computationally expensive. 0034 A method for accelerating scalar multiplication of an elliptic curve point Q(x,y) is shown in FIG. 2 and indicated generally by the numeral 50. The subject algorithm increases the speed at which the processors 12 can for example sign and verify messages for specific classes of elliptic curves. The method is based on the observation that given the general equation for an elliptic curve E:

y2a1xya3yx3a2x2a4xa6 (1)

0035 over a finite field, exemplified as Fq (q is a prime power) and when there exists an endomorphism , where (Q)Q for all points Q(x,y) on the elliptic curve, then multiplication of the point Q by an integer k may be accelerated by utilizing combinations of smaller representations ki of k in combination with the mapping . The mapping also allows precomputation of group elements and combinations thereof, which may be used in subsequent calculation of kQ. 0036 Referring now to FIG. 2, a flow chart of a general embodiment for accelerating point multiplication on an elliptic curve, is shown by numeral 50. The system parameters are first selected. As an initial step an underlying elliptic curve E is selected to have certain characteristics. In a first embodiment of the invention the generalized elliptic curve (1) may be expressed in the following form:

E: y2x3b mod p; where p is a prime.(2)

0037 Firstly, the modulus p can be determined such that there is a number, where Fp (Fp is the field of size p consisting of all integers mod p), and 31 mod p (a cube root of unity). If for example p7, then 2, since 23 mod 71. Such a does not necessarily exist for all p, and therefore this must be taken into consideration when choosing the value of p. Typically, the chosen p should be at least 160 bits in length for adequate cryptographic strength. 0038 After the curve E has been selected, a mapping function is determined. The mapping function : (x, y)(x, y), simply maps one set of points on the curve to another set of points on the curve. There exists an integer such that (Q)Q for all points Q(x,y) of interest on the elliptic curve, E. This integer may be found by noting that 31 mod n, where n is the number of points on the elliptic curve E over Fp i.e. the number of points on E(Fp). There may exist more than one solution for in 31 mod n, but only one of those solutions will satisfy the mapping function . It is important to note that since 3 mod p1, both Q and (Q) satisfy the equation for E. Therefore, instead of having to perform lengthy calculations to determine the results of multiplication by , it can be done very efficiently using the results of the mapping function so that multiplication by can be done very efficiently. 0039 A seed point Q is selected and the system parameters E, p, Q, , (Q), and are stored in the card 12, as indicated at 52, at manufacture time for use by the cryptographic processor 18. To implement a cryptographic procedure such as encryption, key agreement or signature it is necessary to select an integer k for use as an ephemeral private key k and generate a corresponding public key kQ. 0040 The value of k may be expressed as:

k(k0k1) mod n (3)

0041 where n is the number of points on E(Fp) and k0 and k1 are integers. The point kQ then becomes:

kQ(k0Qk1Q) mod n (4)

0042 For some cryptographic operations the value of k may be chosen at random and in these cases, rather than select k it is possible to select values for k0 and k1 at random, having a length of log2 (n)/2 not including sign bits, (i.e. the length of the k1's are chosen to be at least one half the length k) and then calculate the value for k using equation (3). Having selected the values of k0, k1 as indicated a 54 in FIG. 2, the right side of equation (4) can be calculated quickly using an algorithm analogous to the Simultaneous Multiple Exponentiation as described in the Handbook of Applied Cryptography(HAC) by Menezes et. al.(Algorithm 14.88) and indicated at 56. For convenience the algorithm is reproduced below. It may be noted that in an additive group exponentiation is analogous to addition, thus replacing the multiplication in the algorithm with addition, yields the following: 1Algorithm 1 Simultaneous Multiple AdditionINPUT: groupelements g0, g1, . . . , gl1 and non negative t-bit integers e0, e1, . . . , el1.OUTPUT: g0e0 g1e1 . . . gl1el1.step1. Precomputation. For i from 0 to (2l 1):Gi j0l1 gjijwhere i (il1 . . . i0)2step2. A 0step3. For i from 1 to t do the following:A A A, A A G1,step4. Return (A)where A g0e0 g1e1 . . . gl1el1

0043 Applying this algorithm to equation (4) it can be seen that there are two group elements, g0, g1 namely Q and Q, so that l2 and two integers e0, e1 namely k0, k1. The algorithm permits precomputation of some of the values and initially Gi is precomputed. The results of precomputation of Gi with l2 is shown in table 1. 2TABLE 1i0123Gi0g0g1g0 g1

0044 After performing a point addition to construct the point: Q(Q). It is possible to fill in table 1 with the computed elements to yield table 2. These elements may be pre-computed and stored in memory as shown at step 58 in FIG. 2. 3TABLE 2i0123Gi0Q(Q)Q (Q)

0045 Before step of the algorithm can be performed, Gi, has to be determined and accordingly I1 through It have to be found as indicated at 60. A notional matrix or combing table may be constructed using the binary representation of ki. If, for example, k030 and k110, then t has the value five since the maximum number of bits in the binary representation of ko through k1 is five and the notional matrix constructed from their binary representation is shown in Table 3. Ii is determined by the number represented in the ith column where the first row contains the least significant bit, the second row contains the next significant bit, etc. Therefore it can be seen from table 3 that I1I12(11)3, I3(01)1, I43, and I50. 4TABLE 3i12345k011110k101010Ii13130

0046 All the components needed to complete the algorithm are available and the iteration of step three is performed as shown at 62. 0047 Initially AO and i is set to 1. 0048 IiI1 which from table 3 is equal to 1. Gi, is therefore Gl1, which from table 2 is Q. The value of A from the iteration for I1 is therefore OQQ. 0049 For the next iteration where i2 the initial value of A is Q so AQQ2Q IiI23 from table 3. Gl2 therefore equates to G3 from table 2 which is Q(Q). 0050 AGl1 therefore is computed as 2QQQ3QQ. 0051 The iterations continue for each value of i set out in table 4 until after the 5th iteration the value for koqk, Q, i.e. kQ is computed. 5TABLE 4iA1Q23Q (Q)37Q 2(Q)415Q 5(Q)530Q 10(Q)

0052 Each iteration requires a point doubling (AA) and a point addition (AGl1) although in some cases the value of Gl1 may be O that will reduce the computation. 0053 Thus it may be seen that this method will require a number of point doubles equal to max log2(ki), and almost as many point additions. The number of point additions can be reduced using windowing (Alg. 14.85 HAC) and exponent recoding techniques. Since the value of i and Gi can be precomputed, the point additions are easily performed by retrieving the appropriate precomputed element Gi from table 2. Once kP has been computed, it may be used as the correspondents 12 ephemeral public key in encrypting or signing transmissions over the channel 16. 0054 To summarize, for cryptographic operations like encryption and Diffie-Hellman, signature, an integer k is required with a corresponding public key kQ, computed. The values k0 and k1 are chosen at random, each having a length one half the length of n and the term k0Qk1Q generated using a suitable algorithm. When the k's are chosen in this way, the method seems to be as secure as the random generation of k itself. Of course it is possible to choose the ki's to have fewer bits in order to improve efficiency. 0055 In the above technique, the method of writing kk0k1 in conjunction with simultaneous combing achieves a speed up of the simultaneous multiple addition algorithm. The technique of writing kk0k1 may also be used with the scalar multiplication techniques to advantage, namely with winding, combing ,etc. 0056 For some mappings , it is also possible to use more than two sub k's. It is possible for some 's to write kk0k1k22 allowing the value of k to be computed by applying the simultaneous multiple addition algorithm. 0057 In a second embodiment of the invention a different form of the generalized elliptic curve equation (1) is used, namely:

y2(x3ax) mod p(5)

0058 Once again, p will be a prime number having at least 160 bits. For this type of curve, the properties required for y are different. It is now required to find a value such that 21 mod p. A change in the property of y requires a different mapping function 1 to be used. In this embodiment the mapping takes the form 1: (x, y)(x, y). If (x,y) is on the curve, then 1(x,y) is also on the curve. In this case 41 mod n (n is still the number of points on E(Fp)), and therefore can be calculated. The mapping 1(Q)Q is performed as before and once again multiplication by can be done very efficiently for this curve. The equation for k in this embodiment is the same as in the first embodiment and is represented by:

k(k0k1)mod n(6)

0059 This equation is the same as in the previous embodiment, having only two group elements. Thus using the group elements Q and Q1(Q) in the algorithm 1, the point kQ may be calculated. This computation will require a number of point doubles equal to max log2(ki), and a similar number of point additions. As described earlier the number of point additions can be reduced using windowing and exponent recoding techniques. 0060 This method applies to other elliptic curves, so long as there exists an efficiently computable endomorphism, . 0061 The above embodiments assume that k can be chosen at random and therefore k0 and k1 can be selected instead and determine k. For cryptographic protocols, where it is not possible to choose k, it is first necessary to find k0, k1 of the desired short form from the given value of k such that k(k0k1) mod n. In some cases, more than two k's can be used to advantage. 0062 As may be seen in the embodiments described above when a point is known beforehand, tables can be built to speed multiplication. However, there are cases when multiples of previously unknown points are required (for example, this can occur in ECDSA verification) and it is then necessary to take the value of k as provided and then determine suitable representations for ki. 0063 Thus in a third embodiment, system parameters and a value k is provided, the point Q, the required multiple k, and the complex multiplication multiple are known. It is necessary to determine the short ki's from the value for k, which is predetermined. A method for doing this described as follows and illustrated in the flow chart of FIG. 3. As a pre-computation (not requiring k) we compute two relations:

a0b00 mod n

a1b10 mod n

0064 such that ai and bi are numbers smaller than n. It is preferable that ai and bi are as small as possible, however, the present method has advantages even when ai and bi are not minimal. The pair, ai and bi, where ai and bi are both small, can be viewed as a vector, ui with a small Euclidean length. Typically the method described below produces k0 and k1 having representations one half the size of the original k. 0065 In the present embodiment, kQ can be computed efficiently by utilizing precomputed, short vector representations to obtain an expression of the form:

k0Qk1 Q

0066 This is accomplished by using precomputed vectors to derive fractions f0 and f1 that do not require knowledge of k. A vector z is generated from the combination of fractions f0 and f1 and k. The vector z is used to calculate a second vector v where v(vo,v1) and the value of kQ calculated as

volQv1lQ(8)

0067 The method of achieving this solution is described below in greater detail. 0068 To produce small a1, and bi, it is possible to make use of the L3-lattice basis reduction algorithm (HAC p. 118), which would directly result in short basis vectors. However, in this preferred embodiment the simple extended Euclidean algorithm is employed on the pair (n, ). The extended Euclidean algorithm on (n, ) produces linear combinations cind1ri, where the representation of ri (e.g. bit-length) decreases and the representation of ci and di increases with i. 0069 The two smallest values of (d1, r1) resulting from using the extended Euclidean algorithm are saved. The size of these vectors are measured with the squared Euclidean norm (di, ri)di2r12. The terms in these minimal relations are denoted {circumflex over (d)}0, {circumflex over (r)}0 and {circumflex over (d)}1, {circumflex over (r)}1. And will typically occur in the middle of the algorithm. Even if the minimal relations are not retained, suboptimal relations may still give the method an advantage in the calculation of point multiples. 0070 The values of ai and bi are constructed by defining a0{circumflex over (r)}0, b0{circumflex over (d)}0 and a1{circumflex over (r)}1, b1{circumflex over (d)}0 all of which may be precomputed. The next task is to find a small representation for the multiple k. 0071 Given the computation of a0, b0 and a1, b1, it is possible to designate the vectors u0, u1, where u0(a0, b0) and u1(a1, b1). These vectors satisfy a1bi0 (mod n). The multiplication of the group elements Q by the vector v(v0, v1) is defined as (v0v1)Q. Since aibi0 (mod n), u0Ru1R0 for any group element R. Hence for any integers z0 and z1, vR(vz0u0z1u1)R for any group element R. 0072 Integers z0 and z1 may be chosen such that the vector vvz0u0z1u1 has components that are as small as possible. Again, this method will have an advantage if the components of v are small, but not necessarily minimally so. 0073 The appropriate z0 and z1 are calculated by converting the basis of v into the basis u0, u1. The conversion between basis involves matrix multiplication. To convert the vector v(v0, v1) from the u0, u1 basis to the standard orthonormal basis (1,0),(0,1), 1

v_{{(1, 0), (0, 1)}} = v_{(u_{0}, u_{1})} M = (v_{0}, v_{1}) [\begin{matrix} a_{0} & b_{0} \\ a_{1} & b_{1} \end{matrix}]

0074 To convert in the other direction, from the standard orthonormal basis (1,0),(0,1) to the (u0, u1) basis, the multiplication is simply by the inverse of M, 2

v_{(u_{0}, u_{1})} = v_{{(1, 0), (0, 1)}} inverse (M) = v_{{(1, 0), (0, 1)}} \frac{1}{a_{0} b_{1} - a_{1} b_{0}} [\begin{matrix} b_{1} & - b_{0} \\ - a_{1} & a_{0} \end{matrix}]

0075 Since the vector v(k, 0) has a zero component, the bottom row of inverse(M) is not required, and therefore to convert to the u0, u1 basis only the fractions 3

f_{0} = \frac{b_{1}}{a_{0} b_{1} - a_{1} b_{0}} and f_{1} = \frac{b_{0}}{a_{0} b_{1} - a_{1} b_{0}}

0076 are needed. 0077 The fractions f0 and f1 may be precomputed to enough precision so that this operation may be effected only with multiplication. It should be noted that the computations leading to these fractions do not depend upon k, therefore they can be computed once when the elliptic curve is chosen as a system parameter, and do not need to be recalculated for each k. Similarly the vectors v, u0 and u1 may be precomputed and stored. 0078 Once a value of k is selected or determined the value of kQ may be computed by first calculating z(z0, z1), where z is defined as (z0, z1)(round(kf0), round(kf1)). Other vectors near to z will also be useful, therefore rounding could be replaced with floor or ceiling functions or some other approximation. 0079 Once a suitable z has been determined, an efficient equivalent to v (k,0) is calculated by v(v0, v1)vz0u0z0u0z1u1. The phrase efficient equivalent implies a vector v such that vPvP and v has small coefficients. The value kQ is then calculated as v0Qv1Q. This value can be calculated using simultaneous point addition as described above, with enhanced efficiency obtained from the use of non-adjacent form (NAF) recoding as described above and as described in H. A. C. 14.7 at page 627. Thus, even where k is predetermined, values of k and ki can be computed and used with the mapping function to obtain a value of kQ and hus he key pair k, kQ. 0080 For the case where k is to be separated into 3 portions kk0k1k22, small vectors can be obtained from L3-row-reducing 4

[\begin{matrix} 1 & 0 & -^{2} \\ 0 & 1 & - \\ 0 & 0 & - n \end{matrix}] to [\begin{matrix} u_{2} \\ u_{1} \\ u_{0} \end{matrix}]

0081 A small vector equivalent (three-dimensional row) can be obtained in a similar way to the two-dimensional case. 0082 Using these methods to determine the value of kQ greatly reduces the processing power required by the cryptographic processors 12. It also increases the speed at which these repetitive calculations can be done which, in turn, reduces the time to transfer information. 0083 It will be appreciated that once the scalar multiple k has been represented in terms of shortened components kk0k1k22. . . km-1m-1, other options for efficient elliptic curve scalar multiplication may be used in place of or in conjunction with the simultaneous multiple addition algorithm. These options include windowing (fixed and sliding), combing, bit recoding and combinations of these techniques. 0084 One particularly beneficial technique permits tables built for one component of the multiplication, say k0, to be reused for other components k1, etc. This is accomplished by transforming the computed table elements by applying the mapping as required. 0085 As a further exemplification, an embodiment where k can be recast as kk0k1k22, where k has m-bits and ki have roughly m/3 bits is described below. 0086 Once the components ki have been determined, they may be recoded from the binary representation to the signed binary representation having less non-zero bits. This recoding can take the Non-Adjacent-Form (NAF), where every 1 or 1 bit in the representation if ki is non-adjacent to another non-zero in the signed binary string. This recoding is described in H.A.C. 14.7 p. 627. 0087 Once each ki has been recoded, a table can be constructed to aid in computing kiiP. 0088 A NAF windowing table precomputes certain short-bit length multiples of iP. The width of the window determines the size of the table. As ki has been recorded to have no adjacent non zeros, odd window widths are suitable. A 3-bit wide NAF window would contain 1

0089 The recoded ki values are built by concatenating these windows, and padding where necessary with zeros (H.A.C., p. 616). 0090 The required number of additions can be reduced with use of this table, since it is necessary to add or subtract an EC point only for every window encountered instead of for every non zero bit. 0091 Initially therefore this technique is applied to the computation of k0P. 0092 The table built for the k0P calculation can be applied to the kiP calculation if the table elements are mapped with the mapping using the operator . Similarly, k22P can be accelerated by using the table built for k0P, but mapping the table elements with 2. 0093 In applying the sliding window technique to the components, only one set of doublings need be performed. 0094 To illustrate this example of a preferred embodiment the following example will be used:

If k1011010110121110101011012,

0095 then recoding 5

\begin{matrix} k = [10 - 100 - 10 - 100 - 101] + [1000 - 10 - 10 - 10 - 101], \\ = k_{0}^{} + k_{1}^{} \end{matrix}

0096 A 3-bit window table on P is precomputed containing 1P, 10-1P, 101P. This requires two EC additions, and two EC doublings. 0097 After this, kP can be calculated as

kP10-100-10-100-101P 1000-10-10-10-101P

0098 by adding/subtracting elements from the table. 0099 This can be done using an accumulator A as follows: 6A0;initializeA (1 P);consuming the top bit of k0rA 2A;double AA 2AA 10 1 P;consuming the top 3 bits of k0rA 24A;A 101 P;consuming a 3 bit window of k1rA 2A;double AA 101 P;consuming 3 bits of k1rA 24AA 101 P;consuming 3 bits of k1rA 22AA 10 1 P;consuming the last of k0rA P;producing kP.

0100 In summary, the previously described technique is as follows. Given an elliptic curve E and an endomorphism , there corresponds an integer such that Q(Q) for all points QE. Select an integer m and compute an equivalent number m of short basis vectors b1, b2, . . . ,bm. Each such basis vector corresponds to an integer, and each such integer is divisible by the number of points nE(Fpm) (i.e. the number of points). Now, given an integer k, (0<k<n), we write kkii, where the ki's are chosen to be short. This is done by finding the difference between a certain vector (which represents k) and a nearby vector in the lattice generated by b1, b2, . . . ,bm. 0101 The following embodiment explicitly describes an application of the previously described technique (endomorphism and basis conversion and Shamir's trick) to elliptic curves defined over composite fields. In particular, we describe an application to curves E(Fpm) where p is an odd prime is described. The following embodiments exemplify techniques for such curves. 0102 This technique is described in the case where the map is the Frobenius map (x,y)(xp,yp) and E'A,B(Fpm) where A,BFp. 0103 In this case, it is known that the Frobenius map satisfies the 2tp0, where tp1E(Fpm). 0104 It follows that 2tp0 mod n and so 2It1ipi0 mod n. 0105 Note that the vectors; 6

(^{m - 1}^{2},^{1},^{0})

\begin{matrix} b_{1} & (0, 0, 0, & 0, 1, - t, p) \\ b_{2} & ( & 1, - t, p, 0) \\ (1, - t, p, 0, 0, & , 0) \\ (- t, p, 0, 0, & , 0, 1) \\ b_{m} & (p, 0, 0, 0, & 0, 1, - t) \end{matrix}

0106 consist of m short basis vectors of the vector space Qn. It follows that to compute kQ on such a curve we can proceed using the vectors b1,b2. . .bm and the technique described previously. 0107 In the above embodiments it will be appreciated that k,Q can be obtained from (kQ) is the mapping is more efficient than addition. 0108 Although the invention has been described with reference to certain specific embodiments, various modifications thereof will be apparent to those skilled in the art without departing from the spirit and scope of the invention as outlined in the claims appended hereto.