Note: Descriptions are shown in the official language in which they were submitted.
CA 02892318 2015-05-26
1 SIGNATURE PROTOCOL
2 TECHNICAL FIELD
3 [0001] The present invention relates to data communication systems and
protocols utilized in
4 such systems.
BACKGROUND
6 [0002] Data communication systems are used to exchange information
between devices. The
7 information to be exchanged comprises data that is organized as strings
of digital bits
8 formatted so as to be recognizable by other devices and to permit the
information to be
9 processed and/or recovered.
[0003] The exchange of information may occur over a publically accessible
network, such as a
11 communication link between two devices, over a dedicated network within
an organization, or
12 may be between two devices within the same dedicated component, such as
within a
13 computer or point of sale device.
14 [0004] The devices may range from relatively large computer systems
through to
telecommunication devices, cellular phones, monitoring devices, sensors,
electronic wallets
16 and smart cards, and a wide variety of devices that are connected to
transfer data between
17 two or more of such devices.
18 [0005] A large number of communication protocols have been developed to
allow the
19 exchange of data between different devices. The communication protocols
permit the
exchange of data in a robust manner, often with error correction and error
detection
21 functionality, and for the data to be directed to the intended recipient
and recovered for further
22 use.
23 [0006] Because the data may be accessible to other devices, it is
vulnerable to interception
24 and observation or manipulation. The sensitive nature of the information
requires that steps
are taken to secure the information and ensure its integrity.
26 [0007] A number of techniques collectively referred to as encryption
protocols and
27 authentication protocols have been developed to provide the required
attributes and ensure
28 security and/or integrity in the exchange of information. These
techniques utilize a key that is
29 combined with the data.
1
CA 02892318 2015-05-26
1 [0008] There are two main types of cryptosystems that implement the
protocols, symmetric
2 key cryptosystems and asymmetric or public-key cryptosystems. In a
symmetric key
3 cryptosystem, the devices exchanging information share a common key that
is known only to
4 the devices intended to share the information. Symmetric key systems have
the advantage
that they are relatively fast and therefore able to process large quantities
of data in a relatively
6 short time, even with limited computing power. However, the keys must be
distributed in a
7 secure manner to the different devices, which leads to increased overhead
and vulnerability if
8 the key is compromised.
9 [0009] Public-key cryptosystems utilize a key pair, one of which is
public and the other private,
associated with each device. The public key and private key are related by a
"hard"
11 mathematical problem so that even if the public key and the underlying
problem are known, the
12 private key cannot be recovered in a feasible time. One such problem is
the factoring of the
13 product of two large primes, as utilized in RSA cryptosystems. Another
is the discrete log
14 problem in a finite cyclic group. A generator, a, of the underlying
group is identified as a
system parameter and a random integer, k, generated for use as a private key.
To obtain a
16 public key, K, a k-fold group operation is performed so that K=f(a,k).
17 [0010] Different groups may be used in discrete log cryptosystems
including the multiplicative
18 group of a finite field, the group of integers in a finite cyclic group
of order p, usually denoted
19 Zp* and consisting of the integers 0 to p-1. The group operation is
multiplication so that
K=f(ak).
21 [0011] Another group that is used for enhanced security is an elliptic
curve group. The elliptic
22 curve group consists of pairs of elements, one of which is designated x
and the other y, in a
23 field that satisfy the equation of the chosen elliptic curve. For a
group of order p, the
24 relationship would generally be defined by y2 = x3 + ax + b mod p. Other
curves are used for
different underlying fields. Each such pair of elements is a point on the
curve, and a generator
26 of the group or an appropriate subgroup is designated as a point P. The
group operation is
27 addition, so a private key k will have a corresponding public-key f(kP).
28 [0012] Public-key cryptosystems reduce the infrastructure necessary with
symmetric key
29 cryptosystems. A device generates a key pair by obtaining an integer k,
which is used as a
private key and performing a k-fold group operation to generate the
corresponding public-key.
2
CA 02892318 2015-05-26
1 In an elliptic curve group, this would be kP. The public-key is published
so it is available to
2 other devices.
3 [0013] Devices may then use the key pair in communications between them.
If one device
4 wishes to encrypt a message to be sent to another device, it uses the
public key of the
intended recipient in an encryption protocol. The message may be decrypted and
recovered by
6 the other device using the private key.
7 [0014] To assure the recipient of the integrity of a message, the device
may also use the key
8 pair in a digital signature protocol. The message is signed using the
private key k and other
9 devices can confirm the integrity of the message using the public key kP.
[0015] A digital signature is a computer readable data string (or number)
which associates a
11 message with the author of that data string. A digital signature
generation algorithm is a
12 method of producing digital signatures.
13 [0016] Digital signature schemes are designed to provide the digital
counterpart to handwritten
14 signatures (and more). A digital signature is a number dependent on some
secret known only
to the signer (the signer's private key), and, additionally, on the contents
of the message being
16 signed.
17 [0017] Signatures must be verifiable ¨ if a dispute arises as to whether
an entity signed a
18 document, an unbiased third party should be able to resolve the matter
equitably, without
19 requiring access to the signer's private key. Disputes may arise when a
signer tries to
repudiate a signature it did create, or when a forger makes a fraudulent
claim.
21 [0018] The three fundamental different types of signatures are:
22A digital signature scheme with appendix, which requires the original
message
=
23 as input into the verification process.
24= A digital signature scheme with message recovery, which does not
require the
original message as input to the verification process. Typically the original
26 message is recovered during verification.
27 = A digital signature scheme with partial message recovery, which
requires only a
28 part of the message to be recovered.
3
CA 02892318 2015-05-26
1 [0019] The present application is concerned with asymmetric digital
signatures schemes with
2 appendix. As discussed above, asymmetric means that each entity selects a
key pair
3 consisting of a private key and a related public key. The entity
maintains the secrecy of the
4 private key which it uses for signing messages, and makes authentic
copies of its public key
available to other entities which use it to verify signatures. Usually
Appendix means that a
6 cryptographic hash function is used to create a message digest of the
message, and the
7 signing transformation is applied to the message digest rather than to
the message itself.
8 [0020] A digital signature must be secure if it is to fulfill its
function of non-repudiation. Various
9 types of attack are known against digital signatures. The types of
attacks on Digital Signatures
include:
11 = Key-Only Attack: An adversary only has the public key of the
signer.
12 = Know Signature Attack: An adversary knows the public key of the
signer and
13 has message-signature pairs chosen and produced by the signer.
14 = Chosen Message Attack: The adversary chooses messages that are
signed by
the signer, in this case the signer is acting as an oracle.
16 = Attacks on digital signatures can result in the following
breakages:
17 = Total Break: An adversary is either able to compute the private
key information
18 of the signer, or finds an efficient alternate signing algorithm.
19 = Selective Forgery: An adversary is able to create a valid
signature for a
particular message.
21 = Existential Forgery: An adversary is able to forge a signature for
at least one
22 message.
23 = Universal Forgery: An adversary can forge any message without the
secret key.
24 [0021] Ideally, a digital signature scheme should be existentially
unforgeable under
chosenmessage attack. This notion of security was introduced by Goldwasser,
Micali and
26 Rivest. Informally, it asserts that an adversary who is able to obtain
the signatures of an entity
27 for any messages of its choice is unable to forge successfully a
signature of that entity on a
28 single other message.
4
CA 02892318 2015-05-26
1 [0022] Digital signature schemes can be used to provide the following
basic cryptographic
2 services: data integrity (the assurance that data has not been altered by
unauthorized or
3 unknown means), data origin authentication (the assurance that the source
of data is as
4 claimed), and non-repudiation (the assurance that an entity cannot deny
previous actions or
commitments). Digital signature schemes are commonly used as primitives in
cryptographic
6 protocols that provide other services including entity authentication,
authenticated key
7 transport, and authenticated key agreement.
8 [0023] The digital signature schemes in use today can be classified
according to the hard
9 underlying mathematical problem which provides the basis for their
security:
[0024] Integer Factorization (IF) schemes, which base their security on the
intractability of the
11 integer factorization problem. Examples of these include the RSA and
Rabin signature
12 schemes.
13 [0025] Discrete Logarithm (DL) schemes, which base their security on the
intractability of the
14 (ordinary) discrete logarithm problem in a finite field. Examples of
these include the EIGamal,
Schnorr, DSA, and Nyberg-Rueppel signature schemes.
16 [0026] Elliptic Curve (EC) schemes, which base their security on the
intractability of the elliptic
17 curve discrete logarithm problem.
18 [0027] One signature scheme in wide spread use is the elliptic curve
digital signature
19 algorithm (ECDSA). To generate the signature it is necessary to hash the
message and
generate a public session key from a random integer. One signature component
is obtained by
21 a modular reduction of one co-ordinate of the point representing the
public session key, and
22 the other signature component combines the hash and private keys of the
signer. This requires
23 inversion of the session private key, which may be relatively
computationally intensive.
24 [0028] Verification requires the hashing of the message and inversion of
the other component.
Various mathematical techniques have been developed to make the signing and
verification
26 efficient, however the hashing and modular reduction remain
computationally intensive.
27 [0029] It is an object of the present invention to provide a signature
scheme in which the
28 above disadvantages may be obviated or mitigated.
5
CA 02892318 2015-05-26
1 SUMMARY
2 [0030] In one aspect, a method for generating an elliptic curve
cryptographic signature is
3 provided comprising a first component and a second component for a
message using a long
4 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
using an x co-
6 ordinate of the session public key and the message; generating a second
signature component
7 by combining the long term private key and the first signature component
to provide a first
8 result, subtracting the first result from the session private key to
provide a second result, and
9 combining the second result with the session private key.
[0031] In another aspect, a cryptographic correspondent device is provided,
comprising a
11 processor and a memory, the memory having stored thereon a long term
private key, the
12 device further having associated therewith a cryptographic corresponding
long term public key
13 generated using the long term private key and a cryptographic generator,
and an identity, the
14 memory further having stored thereon computer instructions which when
executed by the
processor cause the processor to implement a elliptic curve cryptographic
signature scheme
16 comprising: generating a session private key and cryptographic
corresponding session public
17 key; generating a first signature component using an x co-ordinate of
the session public key
18 and the message; and generating a second signature component by
combining the long term
19 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 combining the
second result with
21 the session private key.
22 [0032] According to a further aspect, a signature may be verified by:
reconstructing the
23 session public key from the signature components, a long term public key
corresponding to the
24 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
26 signature component and the message; and verifying the signature by
comparing the
27 intermediate component and the recovered x co-ordinate of the session
public key.
28 DESCRIPTION OF THE DRAWINGS
29 [0033] An embodiment of the invention will now be described with
reference to the
accompanying drawings in which:
6
CA 02892318 2015-05-26
1 [0034] Figure 1 is a schematic representation of a data communication
system;
2 [0035] Figure 2 is a representation of a device used in the data
communication system of
3 Figure 1; and
4 [0036] Figure 3 is a flow chart showing the protocol implemented between
a pair of devices
shown in Figure 1.
6 DETAILED DESCRIPTION
7 [0037] The protocol is described in the context of an elliptic curve
group, generated by a point
8 P which is assumed to have prime order n.
9 [0038] Referring therefore to figure 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
11 type including a computer 12a, a server 12b, a cellphone 12c, ATM 12d,
and smart card 12e.
12 The communication links 14 may be conventional fixed telephone lines,
wireless connections
13 implemented between the devices 12, near field communication connections
such as Blue
14 tooth or other conventional form of communication.
[0039] The devices 12 will differ according to their intended purpose, but
typically, will include
16 a communication module 20 (figure 2) for communication to the links 14.
A memory 22
17 provides a storage medium for non-transient instructions to implement
protocols and to store
18 data as required. A secure memory module 24, which may be part of memory
22 or may be a
19 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
21 is provided to perform the arithmetic operations instruction by the
memory 22 using data stored
22 in the memories 22, 24. A random or pseudo random number generator 28 is
also
23 incorporated to generate bit strings representing random numbers in a
cryptographically
24 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.
26 [0040] It will be appreciated that the device 12 illustrated in Figure
2, is highly schematic and
27 representative of a conventional device used in a data communication
system.
28 [0041] The memory 22 stores system parameters for the cryptosystem to be
implemented and
29 a set of computer readable instructions to implement the required
protocol. In the case of an
7
CA 02892318 2015-05-26
1 elliptic curve cryptosystem, elliptic curve domain parameters consist of
six quantities q, a, b, P,
2 n, and h, which are:
3 = The field size q
4 = The elliptic curve coefficients a and b
= The base point generator P
6 = The order n of the base point generator
7 = The cofactor h, which is the number such that hn is the number of
points on the
8 elliptic curve.
9 [0042] 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
11 conventional, one of those strings inay be truncated as the full
representation may be
12 recovered from the other co-ordinate and the truncated representation.
13 [0043] The secure memory module 24 contains a bit string representing a
long term private
14 key d, and the corresponding public key Q. For an elliptic curve
cryptosystem, the key Q=dP.
[0044] Ephemeral values computed by the ALU may also be stored within the
secure module
16 24 if their value is intended to be secret.
17 [0044] A digital signature protocol is required when one of the devices
12 sends a message,
18 m, to one or more of the other devices, and the other devices need to be
able to authenticate
19 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,
21 each device will be identified as an entity, such as Alice or Bob, as is
usual in the discussion of
22 cryptographic protocols, or as a correspondent. It will be understood
however that each entity
23 is a device 12 performing operations using the device exemplified in
figure 2.
24 [0045] 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
26 message, m, and the signer's (Alice's) private key d, which is an
integer.
27 [0046] The verification scheme takes as input the message, m, the
signer's public key, Q,
28 which is an element of the group generated by the generating point P,
and a purported
8
CA 02892318 2015-05-26
1 signature on message by the signer. The signature comprises a pair of
signature components,
2 computed by the signer and sent to the recipients, usually with the
message, m.
3 [0047] To sign message, m, using the signer's private key d:
4 [0048] 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
6 k in the range [1, n-1]. The value k is the ephemeral (or, short term or
session) private key of
7 Alice. At block 304, the ALU 24 performs a point multiplication to obtain
an elliptic curve point
8 K=kP, which is used as the ephemeral public key of Alice.
9 [0049] 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
11 representing the coordinate x is used as an integer to compute an
intermediate value r, r = e+x
12 (mod n).
13 [0050] At block 308, the ALU 24 then computes the second signature
component s from the
14 session key k, first signature component r and the private key d:
s=(k+1)-1(k-dr) (mod n)
16 [0051] As shown at block 310, the component s is an integer, and the
signature on the
17 message m is the pair of components r, s. The message m is sent by
Alice, together with the
18 signature (r,$) to Bob, using the communication module 20.
19 [0052] The signature protocol may be summarized as:
a. Compute e = H(m), where H is a cryptographic hash function.
21 b. Compute an elliptic curve point K by randomly selecting an integer
k in the
22 range of [1,n-1], and then computing the elliptic curve point
kP=K.
23 c. Let x be the affine x-coordinate of the point kP.
24 d. Compute the integer r = e + x (mod n)
e. Compute the integer s=(k+1)-1(k-dr) (mod n). Ifs = 1, go to step (b).
26 f. Output (r,$) as the signature of message m.
9
CA 02892318 2015-05-26
1 [0053] Upon Bob receiving the message m, he may wish to verify the
signature, and thereby
2 confirm it has been sent by Alice, and that its contents have not been
changed.
3 [0054] At block 312 Bob hashes the message m, with a cryptographic hash
function H, to
4 generate e = H(m). At block 314, an elliptic curve point K' is computed
by the ALU 24 using the
relationship
6 K'=s'(1-sT1P+r(1-s')1 Q.
7 where (r',s') is the signature received by Bob, and Q is the public key
of Alice, which has been
8 obtained from a trusted source, such as a certificate signed by a
Certificate Authority ("CA")
9 .and sent by Alice to Bob.
[0055] At block 316, the x co-ordinate x' of the point K' is obtained and, at
block 318,
11 compared to (r' ¨ e) (mod n), and if they are the same, the signature is
verified, as shown at
12 block 320. If not, the signature is rejected and the message may be
considered invalid, as
13 shown at block 322.
14 [0056] 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,
16 then output 'invalid'.
17 b. Compute the elliptic curve point K'=s'(1-s') -11D+r(1-sT1 Q. If K'
= co, output
18 'invalid'.
19 c. Let x' be the x-coordinate of the point K'.
d. Compute e = H(m).
21 e. Check that x' = (r' ¨ e) (mod n). If the check fails, then output
'invalid'; otherwise
22 output 'valid'.
23 [0057] The first signature component r may be computed as r = (H(m) + x)
(mod n). Also, the
24 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 II m). An alternative computation
is available, using
26 a block cipher, such as the AES block cipher, to compute r = E(m). In an
embodiment, the
27 coordinate x is used as the symmetric encryption key for the block
cipher, E, which is
28 performed in the ALU.
