Certicom Corporation et al v. Sony Corporation et al

Filing 52

Defendants' Second Amended ANSWER to 1 Complaint,, COUNTERCLAIM against Certicom Corporation, Certicom Patent Holding Corporation by Sony Computer Entertainment Inc., Sony Computer Entertainment America Inc., Sony Pictures Entertainment Inc., Sony Electronics Inc., Sony DADC US Inc., Sony Corporation. (Attachments: # 1 Exhibit A (Unreadable), # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D)(Wilcox, Melvin) Modified on 7/15/2008 (mpv, ).

EXHIBIT "A"

Memorandum
To: From: Sub ject: Date: P1363 working group Alfred Menezes IEEE P1363, Part 6: El liptic Curve Systems October 30, 1994.

Enclosed is a copy of IEEE P1363, Part 6, October 30, 1994, for your review. I reveived comments from Roger Schla y and Burt Kaliski. The following is a list of ma jor changes made to the August 19, 1994 draft. 1. Extended the glossary. 2. The signature scheme with appendix was modi ed. 3. A signature scheme with message recovery was added. 4. Added the section on key lengths. 5. Extended the section of key generation considerations. 6. Added a brief introduction to normal bases. 7. Added a subsection on selecting appropriate curves. 8. Added a subsection on computing the order of a point. 9. Added a list of references. The following items will be addressed in future drafts of this standard. 1. Complete a detailed described of the ECSSA and ECSSM signature schemes. 2. Use ASN.1 to describe the key syntax. 3. Specify a hash function for use with the ECSSA signature scheme. I would very much appreciate any editorial suggestions or technical comments.

WORKING DRAFT
IEEE P1363 STANDARD STANDARD FOR RSA, DIFFIE-HELLMAN AND RELATED PUBLIC-KEY CRYPTOGRAPHY PART 6: ELLIPTIC CURVE SYSTEMS (Draft 2)

Notice Warning to readers of this document
This document is in the working document stage. It has not yet been processed through the consensus procedures of the IEEE. Many changes which may greatly a ect the contents can occur before this document becomes an IEEE Standard. The developmental committee may not be held responsible for the contents of this document as it currently exists. Implementation or design based on this working paper is at the risk of the user. No advertisement implying compliance with this \Standard" should appear as it is erroneous and misleading to so state.

Dr. Alfred J. Menezes Dr. Minghua Qu Dr. Scott A. Vanstone
Mobius Encryption Technologies 200 Matheson Boulevard, West Mississauga, Ontario, Canada, L5R 3L7

October 30, 1994

Outline
6 Elliptic Curve Systems
6.1 Basic Algorithms : : : : : : : : : : : : : : : : : : : : : : : : : : 6.1.1 Elliptic Curve Encryption Scheme (ECES) : : : : : : : 6.1.2 Elliptic Curve Signature Schemes (ECSSA and ECSSM) 6.2 Services Provided : : : : : : : : : : : : : : : : : : : : : : : : : : 6.3 Encryption : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.3.1 Encryption-block formatting : : : : : : : : : : : : : : : 6.3.2 Elliptic curve computations : : : : : : : : : : : : : : : : 6.3.3 Message inclusion : : : : : : : : : : : : : : : : : : : : : : 6.3.4 Point-to-octet-string conversion : : : : : : : : : : : : : : 6.4 Decryption : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.1 Octet-string-to-point conversion : : : : : : : : : : : : : : 6.4.2 Elliptic curve computations : : : : : : : : : : : : : : : : 6.4.3 Message extraction : : : : : : : : : : : : : : : : : : : : : 6.4.4 Encryption-block parsing : : : : : : : : : : : : : : : : : 6.5 Signature : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5.1 ECSSA : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5.2 ECSSM : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.6 Signature Veri cation : : : : : : : : : : : : : : : : : : : : : : : 6.6.1 ECSSA : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.6.2 ECSSM : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.7 Key Length Considerations : : : : : : : : : : : : : : : : : : : : 6.8 Key Generation Considerations : : : : : : : : : : : : : : : : : : 6.8.1 System Setup : : : : : : : : : : : : : : : : : : : : : : : : 6.8.2 Key Generation : : : : : : : : : : : : : : : : : : : : : : : 6.9 Key Syntax : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.9.1 Public-Key Syntax : : : : : : : : : : : : : : : : : : : : : 6.9.2 Private-Key Syntax : : : : : : : : : : : : : : : : : : : : 6.10 Applications (not part of standard) : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : :

5 6 7 9 9 9 10 10 11 11 12 12 12 12 13 13 13 13 13 13 13 13 13 14 14 14 14 14

3

2 C Mathematical Background
C.1 C.2 C.3 C.4 C.5 C.6 C.7 The Finite Field F p : : : : : : : : : : : : : : : : : : The Finite Field F 2m : : : : : : : : : : : : : : : : : Elliptic Curves over F p : : : : : : : : : : : : : : : : Elliptic Curves over F 2m : : : : : : : : : : : : : : : Computing the Multiple of a Point : : : : : : : : : Normal Bases in F 2m : : : : : : : : : : : : : : : : : Selecting an Appropriate Curve : : : : : : : : : : : C.7.1 Method 1 Selecting the curve at random : C.7.2 Method 2 Selecting the order of the curve C.7.3 Method 3 Using the Weil Theorem : : : : C.8 Computing the Order of a Point : : : : : : : : : : C.9 Representing an Elliptic Curve Point : : : : : : : : C.9.1 Elliptic curves over F p : : : : : : : : : : : : C.9.2 Elliptic curves over F 2m : : : : : : : : : : :

OUTLINE
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

15

rst

: : : : :

15 16 17 18 19 20 21 21 21 22 22 22 23 23

E Validation Suite (Test Vectors) F Known State of Attacks References

25 27 29

Part 6

Elliptic Curve Systems
Abstract. This standard describes a method for data encryption and for digital signatures
using the el liptic curve analogue of the ElGamal public-key cryptosystem. El liptic curve systems are public-key (asymmetric) cryptographic algorithms, typical ly used in conjunction with a hash algorithm to create digital signatures, and for the secure distribution of secret keys for use in symmetric cryptosystems. El liptic curve systems may also be used to transmit con dential information.

Introduction
The algebraic system de ned on the points of an elliptic curve provides an alternate means to implement the ElGamal and ElGamal-like public key encryption and signature protocols. These protocols are typically described in the literature in the algebraic system Z , the p integers modulo p, where p is a prime. For example, the NIST DSS is an ElGamal-like signature scheme de ned over Z . Precisely the same protocol for signing could be de ned p over the points on an elliptic curve. Elliptic curve systems as applied to ElGamal protocols were rst proposed in 1985 independently by Neil Koblitz from the University of Washington, and Victor Miller, who was then at IBM, Yorktown Heights. Elliptic curves as algebraic/geometric entities have been studied extensively for the past 150 years, and from these studies has emerged a rich and deep theory. The security of the cryptosystems using elliptic curves hinges on the intractability of the discrete logarithm problem in the algebraic system. It appears to be much more di cult to compute logarithms in an elliptic curve system than to compute logarithms in Z . Over the past nine years this problem has received considerable attention p from leading mathematicians around the world. No substantial improvements in the ability to nd logarithms in an elliptic curve system have been found. Implementations of elliptic curve cryptosystems o er substantial improvements over existing public key systems including much higher speed, lower power consumption and a smaller key size relative to cryptographic strength. The shorter key size has unique advantages for signing short messages such as those used in electronic funds transfers, cellular and broadcast systems. Elliptic curves systems have been implemented by various groups around the world including Siemens (Germany), Matsushita (Japan), Thompson (France) and Mobius En-

4

Elliptic Curve Systems

cryption Technologies (Canada). An ISO/IEC SC27 standard for elliptic curve systems is currently being drafted.

Symbols and Notation dxe The smallest integer x. For example, d5e = 5 and d5:3e = 6. bxc The largest integer x. For example, b5c = 5 and b5:3c = 5.

binary string A binary string is a sequence of 0's and 1's. The leftmost bit is the most signi cant bit of the string. The rightmost bit is the least signi cant bit of the string. XY Bitwise exclusive or of two binary strings X and Y . octet An octet is a binary string of length 8. An octet is represented by a hexadecimal string of length 2. The rst hexadecimal digit represents the four most signi cant bits of the octet. The second hexadecimal digit represents the four least signi cant bits of the octet. For example, 9d represents the binary string 10011101. octet string An octet string is a sequence of octets. X kY Concatenation of two strings X and Y . X and Y are either both binary strings, or both octet strings. kX k Length in octets of the octet string X . PS Padding string. log2 x The logarithmic function to the base 2. a mod n The unique remainder r, 0 r n ; 1, when integer a is divided by n. For example, 23 mod 7 = 2. Z or F p The integers modulo p, where p is a prime number. p F 2m The nite eld containing 2m elements. Fq The nite eld containing q elements. For this standard, q will either be a prime number (p) or a power of 2 (2m). t A eld element of F q will be represented as a binary string of length t = dlog2 qe. In particular, if q = 2m, then a eld element in F 2m can be represented as a binary string of length t = m. E An el liptic curve E is speci ed by 2 parameters a and b, which are elements of a eld F q . The elliptic curve is said to be de ned over F q , and F q is sometimes called the underlying eld. If q is a prime (so the eld is F p ), then the equation de ning the curve is of the form y 2 = x3 + ax + b, where 4a3 + 27b2 6= 0. If q is a power of 2 (so the eld is F 2m ), then the equation de ning the curve is of the form y 2 + xy = x3 + ax2 + b, where b 6= 0. O A special point on an elliptic curve, called the point at in nity.

6.1 Basic Algorithms
P

5
P is a point (xP yP ) on an elliptic curve de ned over a eld F q , where xP and yP are elements of F q . The values x = xP and y = yP must satisfy the equation de ning E . xP is called the x-coordinate of P and yP is called the y-coordinate of P .

There is an addition rule which allows the addition of two elliptic curve points P1 and P2 to produce a third elliptic curve point P3 . If k is a positive integer, then kP denotes the point obtained by adding together k copies of the point P . f yP Let P be a point (xP yP ) on an elliptic curve E de ned over a eld F q . f If q is a prime, then yP is equal to the least signi cant bit of yP . f f If q is a power of 2, then yP is 0 if xP = 0. If xP 6= 0, then yP is equal to the least signi cant bit of the eld element yP xP ;1 . #E (F q ) If E is de ned over F q , then #E (F q ) denotes the number of points on the curve. #E (F q ) is called the order of E . supersingular An elliptic curve de ned over F p is supersingular if #E (F p ) = p + 1. An elliptic curve de ned over F 2m is supersingular if #E (F 2m ) is odd. non-supersingular If the curve is not supersingular, it is called non-supersingular. n, h The order of the point P is n this is the smallest positive integer such that nP = O. The integers in the range 0 n ; 1] are represented by binary strings of length h = dlog2 ne. ECES Elliptic Curve Encryption Scheme. ECSSA Elliptic Curve Signature Scheme with Appendix. ECSSM Elliptic Curve Signature Scheme with Message Recovery. ECSS This refers to either ECSSA or ECSSM. SHA The Secure Hash Algorithm. When a message of length less than 264 bits is input, the SHA produces a 160-bit representation of the message called the message digest or hash value. Any change of the message will, with very high probability, result in a di erent message digest. ISO International Organization for Standardization. IEC International Electrotechnical Commission. ANSI American National Standards Institute. ASN.1 Abstract Syntax Notation One. A notation for describing abstract types and values, that is described in standard ISO/IEC 8824. BER Basic Encoding Rules. A set of rules for representing or encoding the values of each ASN.1 type as a string of octets. There is usually more than one way to encode a given value using BER encoding rules. BER is de ned in standard ISO/IEC 8825. DER Distinguished Encoding Rules. A subset of BER, which gives a unique way to represent any ASN.1 value as an octet string. DER is de ned in standard ISO/IEC 8825.

6.1 Basic Algorithms
This section gives a high-level overview of the elliptic curve encryption scheme (ECES) and two elliptic curve signature schemes (ECSSA and ECSSM).

6

Elliptic Curve Systems

The cryptosystems are described using an arbitrary elliptic curve E over an arbitrary nite eld F q . Complete details and re nements are provided in Sections 6.2 6.6.

6.1.1 Elliptic Curve Encryption Scheme (ECES)
System Setup
An underlying nite eld F q is chosen. An elliptic curve E de ned over F q , and a point P on E are chosen. The order of the point P is denoted by n. The eld F q , curve E , point P , and order n, comprise the system parameters, and are public information.

Key Generation
Each entity shall perform the following operations. 1. 2. 3. 4. Select a random integer d in the range 1 n ; 1]. Compute the point Q := dP . The entity's public key consists of the point Q. The entity's private key is the integer d.

Encryption Process
(Entity B sends a message M to entity A) Entity B performs the following steps: Look up A's public key: Q. Represent the message M as a pair of eld elements (m1, m2 ), m1 2 F q , m2 2 F q . Select a random integer k in the range 1 n ; 1]. Compute the point (x1 y1) := kP . Compute the point (x2 y2) := kQ. Combine the eld elements m1, m2 , x2 and y2 in a predetermined manner to obtain two eld elements c1 and c2. 7. Transmit the data c := (x1 y1 c1 c2) to A. 1. 2. 3. 4. 5. 6.

Decryption Process
(Entity A decrypts ciphertext c = (x1 y1 c1 c2) received from B) Entity A performs the following steps: 1. Compute the point (x2 y2) := d(x1 y1), using its private key d. 2. Recover the message m1 and m2 from c1 , c2 , x2 and y2 .

6.1 Basic Algorithms Notes

7

(a) A technique for representing a message M as a pair of eld elements is speci ed in Section 6.3. (b) A simple technique for combining m1 , m2, x2 and y2 to obtain c1 and c2 is speci ed in Section 6.3. (c) An option available is that all entities use the same underlying eld F q , but each entity selects its own elliptic curve E and point P . In this case a description of E and the point P must be included as part of the public key, and hence the public key is longer. f (d) An elliptic curve point P can be speci ed by its x-coordinate and the bit yP . The full y -coordinate can then be recovered from this information. Representing a point in this way reduces the length of the public key. For more details of this technique, see Section C.9.

6.1.2 Elliptic Curve Signature Schemes (ECSSA and ECSSM)
Two signature schemes are described in this standard. The rst scheme ECSSA is used in text hashing mode, and is an example of a signature scheme with appendix. In this scheme the message is hashed to a message digest of xed length, and then this digest is signed. Veri cation of the signature requires both the signature and the original message. The second scheme ECSSM is a signature scheme with message recovery. In this scheme the message is signed directly, and then the original message can be reconstructed from the signature itself. To guard against forgeries it is important that the message include some pre-speci ed redundancy. The advantages of a signature scheme with message recovery is that it permits applications without a hash function, and furthermore results in smaller bandwidth for signatures of small messages.

System Setup
This is the same as in Section 6.1.1.

Key Generation
This is the same as in Section 6.1.1.

Signature Generation for ECSSA
(Entity A signs a message M for entity B) A performs the following steps: 1. Represent the message M as a binary string.

8
2. 3. 4. 5. 6. 7. 8.

Elliptic Curve Systems
Use a hash algorithm to compute the hash value m := H (M ). Select a random integer k in the range 1 n ; 1]. Compute the point (x1 y1) := kP . Compute r := x1 mod n. Use the private key d to compute s := k;1 (m + rd) mod n. Compute s;1 mod n. A sends to B the message M and the signature (r s;1).

Signature Veri cation for ECSSA
(Entity B veri es A's signature (r s;1) for a message M .) B performs the following steps: 1. Look up A's public key Q. 2. Compute the hash value m := H (M ). 3. Compute u := s;1 m mod n and v := s;1 r mod n. 4. Compute the point (x2 y2) := uP + v Q. 5. Compute r0 := x2 mod n. 6. Accepts A's signature for message M if and only if r = r0.

Signature Generation for ECSSM
(Entity A signs a message M for entity B) A performs the following steps: 1. Represent the message M as a pair of eld elements m1 and m2, which include some pre-speci ed redundancy. 2. Select a random integer k in the range 1 n ; 1]. 3. Compute the point (x1 y1) := kP . 4. Compute the eld elements r1 := m1x1 and r2 := m2 y1 . 5. Use the private key d to compute s := k ; d(r1 + r2 ) mod n. 6. A sends to B the signature (r1 r2 s).

Signature Veri cation for ECSSM
(Entity B recovers the message and veri es A's signature from (r1 r2 s).) B performs the following steps: 1. Look up A's public key Q. 2. Compute the point (x2 y2) := sP + (r1 + r2)Q. ; 3. Compute m01 := r1 x;1 and m02 := r2y2 1 and 2 0 4. Accept the signature for the message (m1 m02) if and only if (m01 m02) contains the pre-speci ed redundancy.

6.2 Services Provided Notes
(a) A good example of a redundancy generating function is in ISO/IEC 9796.

9

6.2 Services Provided
The cryptographic algorithms described in this standard can be used to provide the following services.

Privacy (secrecy) Entity authentication Information authentication Digital signatures (non-repudiation) Authenticated key exchange

6.3 Encryption
This section describes the ECES encryption process. The encryption process consists of four steps: encryption-block formatting, elliptic curve computations, message inclusion, and point-to-octet-string conversion. The input to the encryption process is:

An octet string M , the message. The length of the message M shall not be more that 2l ; 3 octets l is the length of the eld size (q ) in octets, that is, Two eld elements a and b which describe the elliptic curve equation. A eld element is represented by a binary string of length t. f A eld element xP and the bit yP , which together describe the point P = (xP yP ) of order n. f A eld element xQ and the bit yQ, which together describe the public-key point Q = (xQ yQ). The output from the encryption process shall be an octet string EM of length 3l + 1,
l= 8
t w

here t = dlog2 q e:

the encrypted message.

6.3.1 Encryption-block formatting
1. Pad the message M on the left with a padding string PS of 2l ; 3 ; kM k octets, followed by the 00 octet, to form the octet string M 0 : M 0 = PS k 00 k M :

10

Elliptic Curve Systems
The octets of the padding string PS should be pseudorandomly generated and nonzero. 2. The string consisting of the rst l ; 1 octets of M 0 is called M1 and the string consisting of the last l ; 1 octets of M is called M2 : M1 = left half of M 0 M2 = right half of M 0.

Notes
(a) Since t is recommended to be at least 155, the value of l is at least 20, and so the length of the message M can always be up to 37 octets. (b) Since the padding string PS contains no 00 octets, and the padding string is separated from the message M by a 00 octet, the encryption block can be parsed unambiguously. (c) The standard may be extended to handle messages of length greater than 2l ; 3 octets.

6.3.2 Elliptic curve computations
1. 2. 3. 4. 5. Select a random integer k in the range 1 n ; 1]. f Recover the y -coordinate yP of the point P from xP and the bit yP . Compute the elliptic curve point (x1 y1) := kP , where P is the point (xP yP ). f Recover the y -coordinate yQ of the point Q from xQ and the bit yQ . Compute the elliptic curve point (x2 y2) := kQ, where Q is the point (xQ yQ).

Notes
(a) For reasons of e ciency, the integer k may be chosen by setting j randomly chosen positions of its binary representation to 1, and the remaining positions to 0. For security, the value of j should be at least 30.

6.3.3 Message inclusion
1. Convert M1 to a binary string, and then append a zero binary string of length 8 ; 8l + t to the left of this binary string to form a eld element m1. 2. Convert M2 to a binary string, and then append a zero binary string of length 8 ; 8l + t to the left of this binary string to form a eld element m2. 3. Form the eld element x3 by setting to 0 the rst 8 ; 8l + t most signi cant bits of x2. 4. Form the eld element y3 by setting to 0 the rst 8 ; 8l + t most signi cant bits of y2 . t 5. Form the eld element x4 by concatenating the d 2 e most signi cant bits of x3 followed t c least signi cant bits of y3 . by the b 2 t 6. Form the eld element y4 by concatenating the d 2 e most signi cant bits of y3 followed t c least signi cant bits of x3 . by the b 2 7. Compute z1 := m1 y3 and then perform a eld multiplication to obtain c1 := x4 z1. 8. Compute z2 := m2 x3 and then perform a eld multiplication to obtain c2 := y4 z2.

6.4 Decryption Notes
(a) The value of 8 ; 8l + t is either 1, 2, 3, 4, 5, 6, 7, or 8.

11

(b) The most signi cant bit of the eld elements m1 , m2 , x3 and y3 is 0. The reason for doing this is to ensure, in the case where q is equal to a prime p, that the integers represented by x4 , y4 , z1 and z2 are less than the modulus p. (c) The reason for combining the eld elements m1 , m2 , x2 and y2 in the manner speci ed, is to ensure that an eavesdropper who knows c1, c2 and also half the message, say m1, cannot recover the second half of the message m2, nor can he substitute m1 by another message m01 of his choice.

6.3.4 Point-to-octet-string conversion
1. Append a zero binary string of length 8l ; t to the left of the eld element x1, and convert the resulting 8l-bit binary string to an octet string X1 of length l. 2. Compute the bit f. Assign the single octet Y1 the value 00 if f is 0, or the value 01 y1 y1 f if y1 is 1. 3. Append a zero binary string of length 8l ; t to the left of the eld element c1, and convert the resulting 8l-bit binary string to an octet string C1 of length l. 4. Append a zero binary string of length 8l ; t to the left of the eld element c2, and convert the resulting 8l-bit binary string to an octet string C2 of length l. 5. Finally, obtain the ciphertext EM by concatenating the four octet strings X1, Y1 , C1 and C2: EM = X1 k Y1 k C1 k C2: EM is 3l + 1 octets in length.

6.4 Decryption
This section describes the ECES decryption process. The decryption process consists of four steps: octet-string-to-point conversion, elliptic curve computations, message extraction, and encryption-block parsing. The input to the decryption process is:

An octet string EM of length 3l + 1, the encrypted message. Two eld elements a and b which describe the elliptic curve equation. An integer d, the private key.
The output from the encryption process shall be an octet string M of length at most 2l ; 3, the plaintext message.

12

Elliptic Curve Systems
1. Parse the encrypted message EM to obtain octet strings X1, Y1 , C1 and C2, of length l, 1, l and l, respectively: EM = X1 k Y1 k C1 k C2: 2. Convert X1 to a binary string, and then discard the 8l ; t most signi cant bits to obtain a eld element x1 . 3. Set the bit f to be 0 if the octet Y1 is 00, or 1 if the octet Y1 is 01. y1 4. Convert C1 to a binary string, and then discard the 8l ; t most signi cant bits to obtain a eld element c1 . 5. Convert C2 to a binary string, and then discard the 8l ; t most signi cant bits to obtain a eld element c2 .

6.4.1 Octet-string-to-point conversion

6.4.2 Elliptic curve computations
1. Use x1 and f to obtain the elliptic curve point (x1 y1). y1 2. Compute the elliptic curve point (x2 y2) := d(x1 y1 ).

6.4.3 Message extraction
1. Form the eld element x3 by setting to 0 the rst 8 ; 8l + t most signi cant bits of x2. 2. Form the eld element y3 by setting to 0 the rst 8 ; 8l + t most signi cant bits of y2 . t 3. Form the eld element x4 by concatenating the d 2 e most signi cant bits of x3 followed t by the b 2 c least signi cant bits of y3 . t 4. Form the eld element y4 by concatenating the d 2 e most signi cant bits of y3 followed t c least signi cant bits of x3 . by the b 2 5. Compute z1 := c1 x;1 and then m1 := z1 y3 . 4 ; 6. Compute z2 := c2 y4 1 and then m2 := z2 x3 . 7. Discard the 8 ; 8l + t most signi cant bits of m1 , and convert the resulting binary string to an octet string M1 of length l ; 1. 8. Discard the 8 ; 8l + t most signi cant bits of m2 , and convert the resulting binary string to an octet string M2 of length l ; 1.

6.4.4 Encryption-block parsing
1. Concatenate M1 and M2 to obtain an octet string M 0:

M 0 = M1 k M2:
2. Parse M 0 to obtain the message M :

M 0 = PS k 00 k M :

6.5 Signature

13

6.5 Signature
6.5.1 ECSSA 6.5.2 ECSSM 6.6.1 ECSSA 6.6.2 ECSSM

6.6 Signature Veri cation 6.7 Key Length Considerations
The security of the elliptic curve schemes described in this standard hinges on the apparent di culty of the discrete logarithm problem in elliptic curves. To avoid the best known attacks on the discrete logarithm problem, (see Appendix F) the underlying eld F q , the curve E , and the point P should be selected so that the order n of P is divisible by a prime number r which is at least 1044 (and hence, q should also be at least 1044). One simple way to ensure that this condition is met is to select a curve whose order is prime.

6.8 Key Generation Considerations
This section describes ECES and ECSS key generation.

6.8.1 System Setup
The system parameters, namely the eld F q , the eld elements a and b, the point P , and the order n, are selected by the system administrator. The system parameters are public information. 1. An underlying nite eld F q is chosen. The eld is either F p (so q = p, an odd prime) or F 2m (so q = 2m ). Field elements are represented by binary strings of length t = dlog2 qe. 2. If q = p, then two elements a b 2 F p are selected so that 4a3 + 27b2 6= 0 in F p . The elements a and b de ne an elliptic curve E : y 2 = x3 + ax + b. If q = 2m , then two elements a b 2 F 2m are selected so that b 6= 0. The elements a and b de ne an elliptic curve E : y 2 + xy = x3 + ax2 + b. In either case, #E (F q ) should be divisible by a large prime number. Preferably, #E (F q ) should be a prime itself. 3. A point P = (xP yP ) on the elliptic curve E is selected so that the order of P , denoted f n, is a prime number. The bit yP is computed. The point P is represented by xP and f yP .

14 Notes

Elliptic Curve Systems

(a) See Section 6.7 for a discussion of conditions imposed on the sizes of q and n due to security constraints. (b) See Section C.7 for a discussion on how to select a curve of appropriate order. (c) See Section C.8 for a method of computing the order of a point. (d) See Section C.9 for a method of representing a point by the x-coordinate and only one bit of the y -coordinate.

6.8.2 Key Generation
After system setup, each entity performs the following operations. 1. Select a random integer d in the range 1 n ; 1]. 2. Compute the point Q := dP . f 3. Let Q = (xQ yQ ), and compute yQ . The entity's public key consists of the point Q, f which is represented by xQ and yQ . 4. The entity's private key is the integer d.

6.9 Key Syntax
The section describes the syntax for ECES and ECSS public and private keys.

6.9.1 Public-Key Syntax
An ECES or ECSS public key is a binary string
f ECPublicKey := xQ k yQ f where xQ is the x-coordinate of the public-key point Q, and yQ is the bit which can be used to recover the y -coordinate yQ of Q. Note that ECPublicKey is a binary string of length t + 1.

6.9.2 Private-Key Syntax
An ECES or ECSS private key is an integer d in the range 1 n ; 1].

6.10 Applications (not part of standard)

Appendix C

Mathematical Background
C.1 The Finite Field F p
Let p be a prime number. The nite eld F p is comprised of the set of integers f0 1 2 : : : p; 1g with the following arithmetic operations:

Addition: If a b 2 F p, then a + b = r where r is the remainder when a + b is divided by p, 0 r p ; 1. Multiplication: If a b 2 F p, then ab = s where s is the remainder when ab is divided by p, 0 s p ; 1.
Let F p denote all the non-zero elements in F p . In F p , there exists at least one element g such that any non-zero element of F p can be expressed as a power of g . Such an element g is called a generator (or primitive element) of F p. That is
F p = fg i : 0

i p ; 2g:

Example (The nite eld F 2) F 2 =f0,1g. The addition and multiplication tables for F 2 are +01 01
001 110 000 101

Example (The nite eld F 23) F 23 = f0 1 2 : : : 22g. Examples of the arithmetic operations in F 23 are 12 + 20 = 32 = 9, 8 9 = 72 = 3. The element 5 is a generator of F 23. The powers of 5 are:
50 = 1 56 = 8 512 = 18 518 = 6 51 = 5 57 = 17 513 = 21 519 = 7 52 = 2 58 = 16 514 = 13 520 = 12 53 = 10 59 = 11 515 = 19 521 = 14 54 = 4 510 = 9 516 = 3 522 = 1. 55 = 20 511 = 22 517 = 15

16

Mathematical Background

C.2 The Finite Field F 2m
Let f (x) = xm + fm;1 xm;1 + + f2 x2 + f1 x + f0 , fi 2 F 2, be an irreducible polynomial of degree m over F 2 , i.e., f (x) cannot be factored into two polynomials over F 2 each of degree less than m. The nite eld F 2m is comprised of all polynomials over F 2 of degree less than m: F 2m = fam;1 xm;1 + am;2 xm;2 + + a1 x + a0 : ai 2 f0 1gg: The eld element (am;1 xm;1 + + a1 x + a0 ) is usually denoted by the binary string (am;1 a1 a0 ) of length m, so that F 2m = f(am;1 a1 a0 ) : ai 2 f0 1gg: Thus the elements of F 2m can be represented by the set of all binary strings of length m. Field elements are added and multiplied as follows: Field addition: (am;1 a1a0) + (bm;1 b1b0) = (cm;1 c1c0), where ci = ai + bi in the eld F 2 . That is, eld addition is performed componentwise. Field multiplication: (am;1 a1a0) (bm;1 b1b0) = (rm;1 r1r0), where the polynomial (rm;1xm;1 + +r1x + r0) is the remainder when the polynomial (am;1 xm;1 + + a1x + a0) (bm;1xm;1 + + b1x + b0) is divided by f (x) over F 2. Note that F 2m contains exactly 2m elements. Let F 2m denote the set of all non-zero elements in F 2m . There exists at least one element g in F 2m such that any non-zero element of F 2m can be expressed as a power of g . Such an element g is called a generator (or primitive element) of F 2m . That is F 2m = fg i : 0 i 2m ; 2g Take f (x) = x4 + x + 1 over F 2 it can be veri ed that f (x) is irreducible over F 2. Then the elements of F 24 are: (0000) (0001) (0010) (0011) (0100) (0101) (0110) (0111) (1000) (1001) (1010) (1011) (1100) (1101) (1110) (1111). As examples of eld arithmetic, we have (1011) + (1001) = (0010) and (1101) (1001) = (x3 + x2 + 1)(x3 + 1) = x6 + x5 + x2 + 1 = (x4 + x + 1)(x2 + x) + (x3 + x2 + x + 1) = x3 + x2 + x + 1 mod f (x) i = (1111) .e., the remainder when (x3 + x2 + 1)(x3 + 1) is divided by f (x) is x3 + x2 + x + 1. F 24 can be generated by one element = x. The powers of are: 0 = (0001) 1 = (0010) 2 = (0100) 3 = (1000) 4 = (0011) 5 = (0110) 6 = (1100) 7 = (1011) 8 = (0101) 9 = (1010) 10 = (0111) 11 = (1110) 12 = (1111) 13 = (1101) 14 = (1001) 15 = 0 = (0001).

Example (The nite eld F 24 )

C.3 Elliptic Curves over F p

17

C.3 Elliptic Curves over F p
Let p > 3 be a prime number. Let a b 2 F p be such that 4a3 + 27b2 6= 0 in F p . An el liptic curve E (F p ) over F p de ned by the parameters a and b is the set of solutions (x y) in F p F p to the equation t y 2 = x3 + ax + b ogether with an extra point O , the point at in nity. The number of points in E (F p ) is denoted by #E (F p ). The Hasse Theorem tells us that

p + 1 ; 2pp #E(Fp ) p + 1 + 2pp:

The set of points E (F p) form a group with respect to the following addition rules: (i) O + O = O. (ii) (x y) + O = (x y) for all (x y) 2 E (F p ). (iii) (x y) + (x ;y) = O for all (x y) 2 E (F p ) (i.e., the inverse of the point (x y) is the point (x ;y)). (iv) (Rule for adding two distinct points that are not inverses of each other) Let (x1 y1) 2 E (F p ) and (x2 y2) 2 E (F p ) be two points. If x1 6= x2 , then (x1 y1) + (x2 y2) = (x3 y3), where

x3 = 2 ; x1 ; x2 y3 = (x1 ; x3) ; y1 and

y ;y = x2 ; x1 :
2 1

(v) (Rule for doubling a point) Let (x1 y1 ) 2 E (F p ) be a point with y1 6= 0. Then 2(x1 y1) = (x3 y3), where

x3 = 2 ; 2x1 y3 = (x1 ; x3) ; y1 and

1 = 3x2y+ a : 2 1

supersingular.

The group E (F p ) is abelian, which means that P + Q = Q + P for all points P and Q in E (F p ). The curve is said to be supersingular if E (F p) = p + 1 otherwise it is non-

Example (An elliptic curve over F 23) Let y 2 = x3 + x + 1 be an equation over F 23 (i.e., a = 1 and b = 1). Then the solutions over F 23 to the equation of the elliptic curve are:
(0, 1) (0,22) (1,7) (1, 16) (6, 4) (6,19) (7,11) (7,12) (12,19) (13,7) (13,16) (17,3) (3, 10) (3,13) (4, 0) (5, 4) (5,19) (9, 7) (9,16) (11,3) (11,20) (12,4) (17,20) (18,3) (18,20) (19,5) (19,18).

The group E (F 23 ) has 28 points (including the point at in nity O). The following are examples of the group operation.

18

Mathematical Background
1. Let P1 = (3 10), P2 = (9 7) P1 + P2 = (x3 y3): Compute x = 79; 130 = ;3 = ;1 = 11 2 F 23 ; 6 2 = 112 ; 3 ; 9 = 6 ; 3 ; 9 = ;6 = 17 3 = 11(3 ; 17) ; 10 = 11(9) ; 10 = 89 = 20: Therefore P1 + P2 = (17 20):

y

3

2. Let P1 = (3 10), 2P1 = (x3 y3): Compute

= x3(3 2)0+ 1 = 250 = 1 = 6 4
2

y

Therefore 2P1 = (7 12):

= 62 ; 6 = 30 = 7 3 = 6(3 ; 7) ; 10 = ;24 ; 10 = ;11 = 12:
3

C.4 Elliptic Curves over F 2m
A non-supersingular el liptic curve E (F 2m ) over F 2m de ned by the parameters a b 2 F 2m , b 6= 0, is the set of solutions (x y) in F 2m F 2m to the equation

y 2 + xy = x3 + ax2 + b
together with an extra point O , the point at in nity. The number of points in E (F 2m ) is denoted by #E (F 2m ). The Hasse Theorem tells us that

w

q + 1 ; 2pq #E(F2m ) q + 1 + 2pq

here q = 2m . Furthermore, #E (F 2m ) is even. The set of points E (F 2m ) is a group with respect to the following addition rules: (i) O + O = O. (ii) (x y) + O = (x y) for all (x y) 2 E (F 2m ). (iii) (x y) + (x x + y ) = O for all (x y) 2 E (F 2m ) (i.e., the inverse of the point (x y) is the point (x x + y )). (iv) (Rule for adding two distinct points that are not inverses of each other) Let (x1 y1 ) 2 E (F 2m ) and (x2 y2) 2 E (F 2m ) be two points. If x1 6= x2, then (x1 y1) + (x2 y2) = (x3 y3), where y x3 = 2 + + x1 + x2 + a y3 = (x1 + x3) + x3 + y1 and = x1 + y2 : 1 + x2

C.5 Computing the Multiple of a Point
(v) (Rule for doubling a point) Let (x1 y1 ) 2 E (F 2m ) be a point with x1 6= 0. Then 2(x1 y1) = (x3 y3), where

19

x3 = x + xb2 and y3 = x2 + 1 1
2 1

x

y1 1+ x1

x

3

+ x3:

The group E (F 2m ) is abelian, which means that P + Q = Q + P for all points P and Q in E (F 2m ).

Example (An elliptic curve over F 24 .) Consider the eld F 24 generated by the root = x of the irreducible polynomial f (x) = x4 + x + 1: Consider the non-supersingular elliptic curve over F 24 with de ning equation
y2 + xy = x3 + 4x2 + 1
(so a = 4, b = 1). Then the solutions over F 24 to the equation of the elliptic curve are: (0,1) (1 6) (1 13) ( 3 8) ( 3 13) ( 5 3) ( 5 11) ( 6 8) ( 6 14) ( 9 10) ( 9 13) ( 10 1) ( 10 8) ( 12 0) ( 12 12): The group E (F 23) has 16 points (including the point at in nity O). The following are examples of the group operation. 1. Let P1 = ( 6 8) P2 = ( 3 13), and let P1 + P2 = (x3 y3). Then
3 y6 + 13 +

x3 =

8

!2 8

3 + 86 + 13 + 6 + 3 + 4 = +

3 !2

2
3!

+ 3 + 2+ 4=1 2

3

=

+ 13 ( 6 + 1) + 1 + 8 = 6+ 3

!

2

13 + 2 = 13:

2. If 2P1 = (x3 y3), then

y
3 2

x3 = ( 6)2 + ( 1 2 = 12 + 3 = 10 6)
= ( 6) +
6

+8 6

!

10 + 10 = 3 + ( 6 + 2)

10

= 8:

C.5 Computing the Multiple of a Point
If k is a positive integer and P is an elliptic curve point, then kP is the point obtained by adding together k copies of P . This computation can be performed e ciently by the \repeated double-and-add" method outlined below. Input: A positive integer k, and an elliptic curve point P . Output: The elliptic curve point kP .

20

Mathematical Background
1. Let k = kr kr;1 : : : k1k0 be the binary representation of k, where the most signi cant bit kr of k is 1. 2. Set Q ; P . 3. For i from r ; 1 downto 0 do 3.1 Set Q ; Q + Q. 3.2 If ki = 1 then set Q ; Q + P . 4. Output Q.

There are several variations of this method which can be used to speed up the computations. One such method which requires some precomputations is described in 5].

C.6 Normal Bases in F 2m
Arithmetic in the nite eld F 2m can be performed e ciently both in hardware and in software when the eld elements are represented with respect to a normal basis. The eld F 2m can be viewed as a vector space of dimension m over F 2 . That is, there exists a set of m elements 0, 1 : : : m;1 in F 2m such that each 2 F 2m can be written uniquely in the form

=

m;1 X i=0

ai i where ai 2 f0 1g:

We can then represent as the 0-1 vector (a0 a1 : : : am;1). Addition of eld elements is performed by bitwise XOR-ing the vector representations. In general, there are many di erent bases of F 2m over F 2. A normal basis of F 2m over F 2 is a basis of the form

w

f

2 22 : : : 2m;1 g

here 2 F 2m it is a well-knoPn fact thiat such a basis always exists. Given any element w m , we can write 2 F2 = m;1 ai 2 , where ai 2 f0 1g. Since squaring is a linear i=0 operator in F 2m , we have

w

2=

m;1 X i=0

ai 2i+1 =

m;1 X i=0

ai;1 2i = (am;1 a0 : : : am;2 )

ith indices reduced modulo m. Hence a normal basis representation of F 2m is advantageous because squaring a eld element can then be accomplished by a simple rotation of the vector representation, an operation that is easily implemented in hardware. Another important property of normal bases to note is that the multiplicative identity element is represented by the all-ones vector of length m. Multiplying eld elements and computing inverses can be done e ciently but is more complicated to describe. For some pointers to the literature, consult the references on page 29.

C.7 Selecting an Appropriate Curve

21

C.7 Selecting an Appropriate Curve
There are three approaches to selecting an elliptic curve over F q suitable for cryptographic purposes.

C.7.1 Method 1 Selecting the curve at random
1. Randomly select parameters a b 2 F q to de ne the elliptic curve equation. In the case that q is a prime, verify that 4a3 + 27b2 6= 0. The curve equation is E : y2 = x3 + ax + b. In the case that q = 2m , verify that b 6= 0. The curve equation is E : y 2 + xy = x3 + ax2 + b. 2. Compute u = #E (F q ). (See notes below.) 3. Factor u if this order is not divisible by a large prime number r, then go to step 1. 4. Verify that the large prime divisor r of u does not divide q v ; 1, for v = 1 2 3 : : : 10. If this test fails, then go to step 1. 5. Output the curve selected.

Notes
The order #E (F q ) can be computed by using Schoof 's algorithm 23]. Although the basic algorithm is quite ine cient, several dramatic improvements and extensions of this method have been discovered during the last three years. Currently it is feasible to compute #E (F p ) where p is as large as 10430 13]. Also, it is possible to compute #E (F 2m ) where m is as big as 300 in a few hours on a workstation 18].

C.7.2 Method 2 Selecting the order of the curve rst
1. Select an order u such that (a) q + 1 ; 2pq u q + 1 + 2pq. (b) u is divisible by a large prime r. (c) r does not divide q v ; 1 for v = 1 2 3 : : : 10.

If q = 2m then u should also be even. 2. Use the algorithm described in 12] to nd parameters a b 2 F q such that the elliptic curve E de ned by them has order #E (F q ) = u. 3. Output the curve E .

Notes
The algorithm of 12] requires some precomputations for each particular eld F q . Once this is done, then the algorithm takes a few minutes on a workstation, even when q is as large as 2300.

22

Mathematical Background

C.7.3 Method 3 Using the Weil Theorem
This technique can be used for picking curves over F 2m , where m is divisible by a small number, say l. 1. Select a random curve E : y 2 + xy = x3 + ax2 + b, b 6= 0, where a b 2 F 2l . Note that since F 2l is contained in F 2m , it is also true that a b 2 F 2m , and so E is also a curve over F 2m . 2. Compute w = #E (F 2l ). This can be done exhaustively since l is small. 3. Let t = q l + 1 ; w, and let c = m=l. Then u = #E (F 2m ) = 2m + 1 ; c ; c where and are complex numbers determined from the factorization of 1 ; tz + q l z 2 = (1 ; z)(1 ; z): 4. Factor u if this order is not divisible by a large prime number r, then go to step 1. 5. Verify that the large prime divisor r of u does not divide q v ; 1, for v = 1 2 3 : : : 10. If this test fails, then go to step 1. 6. Output the curve selected.

C.8 Computing the Order of a Point
The following algorithm is an e cient method for computing the order of an elliptic curve point, given the prime factorization of the elliptic curve order. Input: An elliptic curve E de ned over F q , where the prime factorization of #E (Fq ) is #E (F q ) = pe1 pe2 pek ei 1: 12 k A point P on E . Output: The order n of P . 1. Set n ; #E (F q ). 2. For i from 1 to k do 2.1 Set n ; n=pei . i 2.2 Compute P1 ; nP . 2.3 While P1 6= O, compute P1 ; pi P1 and set n ; npi . 3. Output n.

C.9 Representing an Elliptic Curve Point
An elliptic curve point P (which is not the point at in nity O ) is represented by two eld elements, the x-coordinate of P and the y -coordinate of P : P = (xP yP ). The point can f be represented more compactly by storing only the x-coordinate xP and a certain bit yP . The next two subsections show how the full y -coordinate yP can be recovered from xP and f yP .

C.9 Representing an Elliptic Curve Point

23

C.9.1 Elliptic curves over F p
We impose the condition that p 3 (mod 4), that is p = 4u + 3 for some positive integer u. (The case where p 1 (mod 4) is more complicated, and is not discussed here.) Let P = (xP yP ) be a point on the elliptic curve E : y 2 = x3 + ax + b de ned over a f prime eld F p . Recall that yP is equal to the least signi cant bit of yP . f Suppose that we are given the x-coordinate xP of P and the bit yP . Then yP can be recovered as follows. 1. Compute the eld element = xP 3 + axP + b mod p. 2. Compute the eld element = u+1 mod p. f 3. If the least signi cant bit of is equal to yP then set yP

yP ; p ; .

; . Otherwise, set

C.9.2 Elliptic curves over F 2m
The technique described in this subsection works only if the elements of the eld F 2m are represented with respect to a normal basis representation (see Section C.6). Let P = (xP yP ) be a point on the elliptic curve E : y 2 + xy = x3 + ax2 + b de ned f f over a eld F 2m . Recall that yP is equal to 0 if xP = 0 if xP 6= 0 then yP is equal to the ;1 . least signi cant bit of the eld element yP xP f Suppose that we are given the x-coordinate xP of P and the bit yP . Then yP can be recovered as follows. 1. If xP = 0 then yP is obtained by cyclically shifting the binary representation of the eld element b one position to the left. That is, if b = bm;1 bm;2 : : : b1b0, then yP ; bm;2 : : : b1b0bm;1. 2. If xP 6= 0 then do the following: 2.1 Compute the eld element = xP + a + bxP ;2 in F 2m . 2.2 Let the binary representation of be = m;1 m;2 : : : 1 0 . 2.3 Construct a eld element z = zm;1 zm;2 : : : z1 z0 by setting
f z0 = yP : z1 = 0 z0: z2 = 1 z1:

. . . zm;2 = zm;1 = 2.4 Finally, compute yP ; xP z.

m;3 zm;3 : m;2 zm;2 :

24

Mathematical Background

Appendix E

Validation Suite (Test Vectors)

26

Validation Suite (Test Vectors)

Appendix F

Known State of Attacks
The security of the elliptic curve systems described in this standard hinges on the apparent di culty of the discrete logarithm problem in the elliptic curve. Namely, given an elliptic curve E de ned over a nite eld F q , and given points P and Q(= kP ), nd the integer k. Unlikely the case of the discrete logarithm problem in nite elds, there is no subexponential time algorithm known for the elliptic curve discrete logarithm problem (in the case that the curve is non-singular). The best algorithm known to date is the Pollard- method p 22] which takes about r=2 steps, where r is largest prime divisor of the order n of P . Recently, van Oorschot and Wiener 21] discovered a technique for parallelizing the Pollard- method so that if m processors are used, then tpe expected number of steps by h each processor before a discrete logarithm is obtained is r=2=m. Hence, to avoid this attack, it is necessary to select a curve and a point P of order divisible by a prime r so that p r=2=m is su ciently large. As a concrete example, van Oorschot and Wiener estimated that if r is about 1036, then a machine with 325,000 processors can be built for about $10 million which would compute logarithms in about 35 days. If r is chosen to be at least 1044, then the discrete logarithm problem would be well out of reach of the van Oorschot and Wiener attack. The special classes of supersingular curves have been avoided in this standard since there is a method for reducing the discrete logarithm problem in these curves to the discrete logarithm problem in a nite eld. However, it should be pointed out that there are some particular supersingular curves whose use may have some advantages over non-supersingular curves.

28

Known State of Attacks

References
Elliptic curve cryptosystems were rst proposed in 1985 independently by Neil Koblitz 11] and Victor Miller 17]. Since then a lot of research has been done towards improving the e ciency of these systems, and evaluating their security. For a summary of this work, consult 16]. A description of a hardware implementation of an elliptic curve cryptosystem can be found in 2]. Two good references on the theory of nite elds are the books by McEliece 15] and Lidl and Niederreiter 14]. The article 1] explains how to e ciently perform arithmetic operations in nite elds of characteristic 2. A hardware implementation of arithmetic in such elds which exploits the properties of so-called optimal normal bases is described in 3]. The ElGamal public-key encryption and signature schemes were introduced in 6]. The NIST Digital Signature Standard (DSS) is described in 20]. The Secure Hash Algorithm (SHA) is described in 4] and 19]. Abstract Syntax Notation One (ASN.1), Basic Encoding Rules (BER) and Distinguished Encoding Rules (DER) are described in 8], 9] and 10] respectively.
1] G. Agnew, T. Beth, R. Mullin and S. Vanstone, \Arithmetic operations in GF (2m )", Journal of Cryptology, 6 ( 1993), 3-13. 2] G. Agnew, R. Mullin and S. Vanstone, \An implementation of elliptic curve cryptosystems over F2155 ", IEEE Journal on Selected Areas in Communications, 11 (1993), 804-813. 3] G. Agnew, R. Mullin, I. Onyszchuk and S. Vanstone, \An implementation for a fast public-key cryptosystem", Journal of Cryptology, 3 (1991), 63-79. 4] American National Standards Institute, \Public key cryptography using irreversible algorithms for the nancial services industry: part 2: the secure hash algorithm (SHA)", ANSI X9.30-1993. 5] E. Brickell, D. Gordon, K. McCurley and D. Wilson, \Fast exponentiation with precomputation", Advances in Cryptology EUROCRYPT '92, Lecture Notes in Computer Science, 658 (1993), Springer Verlag, 200-207. 6] T. ElGamal, \A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, 31 (1985), 469-472. 7] ISO/IEC 9796 \Information Technology Security Techniques Digital signature schemes giving message recovery". 8] ISO/IEC 8824, \Information Technology Open Systems Interconnection Abstract syntax notation one (ASN.1)".

30

REFERENCES

9] ISO/IEC 8825-1, \Information Technology Open Systems Interconnection Speci cation of ASN.1 encoding rules Part 1: Basic Encoding Rules (BER)". 10] ISO/IEC 8825-3, \Information Technology Open Systems Interconnection Speci cation of ASN.1 encoding rules Part 3: Distinguished canonical encoding rules". 11] N. Koblitz, \Elliptic curve cryptosystems", Mathematics of Computation, 48 (1987), 203-209. 12] G. Lay and H. Zimmer, \Constructing elliptic curves with given group order over large nite elds", presented at the First Algorithmic Number Theory Symposium, Ithaca, May 1994. 13] F. Lehmann, M. Maurer, V. Muller and V. Shoup, \Counting the number of points on elliptic curves over nite elds of characteristic greater than three", presented at the First Algorithmic Number Theory Symposium, Ithaca, May 1994. 14] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, 1987. 15] R.J. McEliece, Finite Fields for Computer Scientists and Engineers, Kluwer Academic Publishers, 1987. 16] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993. 17] V. Miller, \Uses of elliptic curves in cryptography", Advances in Cryptology CRYPTO '85, Lecture Notes in Computer Science, 218 (1986), Springer-Verlag, 417-426. 18] F. Morain, private communication, October 4, 1994. 19] National Institute of Standards and Technology, \Secure Hash Standard (SHS)", FIPS Publication 180, May 1993. 20] National Institute of Standards and Technology, \Digital signature standard", FIPS Publication 186, 1993. 21] P. van Oorschot and M. Wiener, \Parallel collision search with application to hash functions and discrete logarithms", to be presented at the 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, November 4, 1994. 22] J. Pollard, \Monte Carlo methods for index computation mod p", Mathematics of Computation, 32 (1978), 918-924. 23] R. Schoof, \Elliptic curves over nite elds and the computation of square roots mod p", Mathematics of Computation, 44 (1985), 483-494.