Signature protocol

Abstract

The present invention relates to data communication systems and protocols utilized in such systems.

Claims

1. A method for generating an elliptic curve cryptographic signature, comprising a first component and a second component, for a message using a long term private key, a session private key and a session public key generated from the session private key, the method comprising: generating a first signature component comprising adding an x co-ordinate of the session public key to a cryptographic hash of the message; generating a second signature component comprising multiplying the long term private key and the first signature component to provide a first result, subtracting the first result from the session private key to provide a second result, and multiplying the second result with the session private key.

2. The method of claim 1, wherein the signature may be verified by: reconstructing the session public key from the signature components, a long term public key corresponding to the long term private key, and a base point generator; recovering the x co-ordinate of the reconstructed session public key; generating an intermediate component from the first signature component and the message; and verifying the signature by comparing the intermediate component and the recovered x co-ordinate of the session public key.

3. The method of claim 2, wherein the intermediate component is generated as a subtraction of the hash of the message from the first signature component.

4. The method of claim 1, wherein the first signature component is generated as the sum of the hash of the message and the x co-ordinate of the session public key.

5. The method of claim 1, wherein combining the second result with the session private key comprises: generating a third result from the session private key; and combining the inverse of the third result with the second result.

6. The method of claim 5, wherein generating the third result comprises adding one to the value of the session private key.

7. The method of claim 1, wherein the first signature component is generated by encrypting the message with a block cipher using the x co-ordinate of the session public key as a symmetric key.

8. The method of claim 1, wherein the first signature component is generated by applying a cryptographic hash function to the concatenation of the message and the x co-ordinate of the session public key.

9. A cryptographic correspondent device comprising a processor and a memory, the memory having stored thereon a long term private key, the device further having associated therewith a cryptographic corresponding long term public key generated using the long term private key and a cryptographic generator, and an identity, the memory further having stored thereon computer instructions which when executed by the processor cause the processor to implement a elliptic curve cryptographic signature scheme comprising: generating a session private key and cryptographic corresponding session public key; generating a first signature component comprising adding an x co-ordinate of the session public key to a cryptographic hash of the message; and generating a second signature component comprising multiplying the long term private key and the first signature component to provide a first result, subtracting the first result from the session private key to provide a second result, and multiplying the second result with the session private key.

10. The device of claim 9, wherein the signature may be verified by: reconstructing the session public key from the signature components, a long term public key corresponding to the longer term private key, and a base point generator; recovering the x coordinate of the reconstructed session public key; generating an intermediate component from the first signature component and the message; and verifying the signature by comparing the intermediate component and the recovered x co-ordinate of the session public key.

11. The device of claim 10, wherein the intermediate component is generated as a subtraction of the hash of the message from the first signature component.

12. The device of claim 10, wherein the first signature component is generated by encrypting the message with a block cipher using the x co-ordinate of the session public key as a symmetric key.

13. The device of claim 9, wherein the first signature component is generated as the sum of the hash of the message and the x co-ordinate of the session public key.

14. The device of claim 9, wherein the first signature component is generated by applying a cryptographic hash function to the concatenation of the message and the x co-ordinate of the session public key.

15. The device of claim 9, wherein combining the second result with the session private key comprises generating a third result from the session private key; and combining the inverse of the third result with the second result.

16. The device of claim 15, wherein generating the third result comprises adding one to the value of the session private key.

Description

DESCRIPTION OF THE DRAWINGS

(1) An embodiment of the invention will now be described with reference to the accompanying drawings in which:

(2) FIG. 1 is a schematic representation of a data communication system;

(3) FIG. 2 is a representation of a device used in the data communication system of FIG. 1; and

(4) FIG. 3 is a flow chart showing the protocol implemented between a pair of devices shown in FIG. 1.

DETAILED DESCRIPTION

(5) The protocol is described in the context of an elliptic curve group, generated by a point P which is assumed to have prime order n.

(6) Referring therefore to FIG. 1, a data communication system 10 includes a plurality of devices 12 interconnected by communication links 14. The devices 12 may be of any known type including a computer 12a, a server 12b, a cellphone 12c, ATM 12d, and smart card 12e. The communication links 14 may be conventional fixed telephone lines, wireless connections implemented between the devices 12, near field communication connections such as Blue tooth or other conventional form of communication.

(7) The devices 12 will differ according to their intended purpose, but typically, will include a communication module 20 (FIG. 2) for communication to the links 14. A memory 22 provides a storage medium for non-transient instructions to implement protocols and to store data as required. A secure memory module 24, which may be part of memory 22 or may be a separate module, is used to store private information, such as the private keys used in the encryption protocols and withstand tampering with that data. An arithmetic logic unit (ALU) 26 is provided to perform the arithmetic operations instruction by the memory 22 using data stored in the memories 22, 24. A random or pseudo random number generator 28 is also incorporated to generate bit strings representing random numbers in a cryptographically secure manner. The memory 22 also includes an instruction set to condition the ALU 26 to perform a block cipher algorithm, such as an AES block cipher, as described more fully below.

(8) It will be appreciated that the device 12 illustrated in FIG. 2, is highly schematic and representative of a conventional device used in a data communication system.

(9) The memory 22 stores system parameters for the cryptosystem to be implemented and a set of computer readable instructions to implement the required protocol. In the case of an elliptic curve cryptosystem, elliptic curve domain parameters consist of six quantities q, a, b, P, n, and h, which are: The field size q The elliptic curve coefficients a and b The base point generator P The order n of the base point generator The cofactor h, which is the number such that hn is the number of points on the elliptic curve.

(10) The parameters will be represented as bit strings, and the representation of the base point P as a pair of bit strings, each representing an element of the underlying field. As is conventional, one of those strings may be truncated as the full representation may be recovered from the other co-ordinate and the truncated representation.

(11) The secure memory module 24 contains a bit string representing a long term private key d, and the corresponding public key Q. For an elliptic curve cryptosystem, the key Q=dP.

(12) Ephemeral values computed by the ALU may also be stored within the secure module 24 if their value is intended to be secret.

(13) A digital signature protocol is required when one of the devices 12 sends a message, m, to one or more of the other devices, and the other devices need to be able to authenticate the message. The message may, for example, be a document to be signed by all parties, or may be an instruction to the ATM 12d to transfer funds. For the description of the protocol, each device will be identified as an entity, such as Alice or Bob, as is usual in the discussion of cryptographic protocols, or as a correspondent. It will be understood however that each entity is a device 12 performing operations using the device exemplified in FIG. 2.

(14) The entity Alice composes a message m which is a bit string representative of the information to be conveyed to another entity Bob. The signature scheme takes as its input the message, m, and the signer's (Alice's) private key d, which is an integer.

(15) The verification scheme takes as input the message, m, the signer's public key, Q, which is an element of the group generated by the generating point P, and a purported signature on message by the signer. The signature comprises a pair of signature components, computed by the signer and sent to the recipients, usually with the message, m.

(16) To sign message, m, using the signer's private key d:

(17) At block 300, Alice creates a message m and hashes it with a cryptographic hash functions H, to generate e=H(m), and, at block 302, uses the RNG 28 to compute an integer k in the range [1, n−1]. The value k is the ephemeral (or, short term or session) private key of Alice. At block 304, the ALU 24 performs a point multiplication to obtain an elliptic curve point K=kP, which is used as the ephemeral public key of Alice.

(18) The ephemeral public key K is represented by a pair of bits strings, x,y, both of which are elements of the underlying field, as shown at block 304. At block 306, the bit string representing the coordinate x is used as an integer to compute an intermediate value r, r=e+x (mod n).

(19) At block 308, the ALU 24 then computes the second signature component s from the session key k, first signature component r and the private key d:
s=(k+1).sup.−1(k−dr)(mod n)

(20) As shown at block 310, the component s is an integer, and the signature on the message m is the pair of components r, s. The message m is sent by Alice, together with the signature (r,s) to Bob, using the communication module 20.

(21) The signature protocol may be summarized as: a. Compute e=H(m), where H is a cryptographic hash function. b. Compute an elliptic curve point K by randomly selecting an integer k in the range of [1,n−1], and then computing the elliptic curve point kP=K. c. Let x be the affine x-coordinate of the point kP. d. Compute the integer r=e+x (mod n) e. Compute the integer s=(k+1).sup.−1(k−dr) (mod n). If s=1, go to step (b). f. Output (r,s) as the signature of message m.

(22) Upon Bob receiving the message m, he may wish to verify the signature, and thereby confirm it has been sent by Alice, and that its contents have not been changed.

(23) At block 312 Bob hashes the message m, with a cryptographic hash function H, to generate e=H(m). At block 314, an elliptic curve point K′ is computed by the ALU 24 using the relationship
K′=s′(1−s′).sup.−1P+r′(1−s′).sup.−1Q.
where (r′,s′) is the signature received by Bob, and Q is the public key of Alice, which has been obtained from a trusted source, such as a certificate signed by a Certificate Authority (“CA”) and sent by Alice to Bob.

(24) At block 316, the x co-ordinate x′ of the point K′ is obtained and, at block 318, compared to (r′−e) (mod n), and if they are the same, the signature is verified, as shown at block 320. If not, the signature is rejected and the message may be considered invalid, as shown at block 322.

(25) In summary, the verification protocol requires: a. Check that r′ and s′ are in the interval [0,n−1], and s′≠1. If either check fails, then output ‘invalid’. b. Compute the elliptic curve point K′=s′(1−s′).sup.−1P+r′(1−s′).sup.−1 Q. If K′=∞, output ‘invalid’. c. Let x′ be the x-coordinate of the point K′. d. Compute e=H(m). e. Check that x′=(r′−e) (mod n). If the check fails, then output ‘invalid’; otherwise output ‘valid’.

(26) The first signature component r may be computed as r=(H(m)+x) (mod n). Also, the first signature component r may be computed from x and m using a one way function such as a cryptographic hash function, i.e., r=H(x∥m). An alternative computation is available, using a block cipher, such as the AES block cipher, to compute r=E.sub.x(m). In an embodiment, the coordinate x is used as the symmetric encryption key for the block cipher, E, which is performed in the ALU.