Note: Descriptions are shown in the official language in which they were submitted.
CA 02591775 2007-06-27
DIGITAL SIGNATURE PROTOCOL
The present invention relates to digital signature protocols. Public key
encryption
schemes are well known and utilize a public key and a private key that are
mathematically related. The more robust are based upon the intractability of
the discrete
log problem in a finite group.
Such public key encryption systems utilize a group element and a generator of
the
group. The generator is an element from which each other group element can be
obtained
by repeated application of the underlying group operation, ie. repeated
composition of the
generator. Conventionally, this is considered to be an exponentiation of the
generator to
an integral power and may be manifested as a k fold multiplication of the
generator or a k
fold addition of the generator depending upon the underlying group operation.
In such a
public key encryption system, an integer k is used as a private key and is
maintained
secret A corresponding public key is obtained by exponentiating the generator
a with
the integer k to provide a public key in the form ak. The value of the integer
k cannot be
derived even though the exponent ak is known.
The public and private keys may be utilized in a message exchange over a data
communication system where one of the con-espondents may encrypt the data with
the
recipient's public key ak. The recipient receives the encrypted message and
utilizes his
2 o private key k to decrypt the message and retrieve the contents.
Interception of the
message will not yield the contents as the integer k cannot be derived.
A similar technique may be utilized to verify the authenticity of a message by
utilizing a digital signature. In this technique, the transmitter of the
message signs the
message with a private key k and a recipient can verify that the message
originated from
the transmitter by decrypting the message with the transmitter's pubic key
a''. A
comparison between a function of the plain text message and of the recovered
message
confirms the authenticity of the message.
Various protocols exist for implementing a digital signature scheme and some
have been widely used. In each protocol, however, it is necessary to guard
against an
existential attack where an impostor may substitute a new message within the
transmission that leads the recipient to believe he is corresponding with a
particular
CA 02591775 2007-06-27
2
individual. Once such authentication is established, then the recipient may
disclose
information that he should not or incorrectly attribute information to the
sender.
To avoid an existential attack, it is usual for the message to include some
redundancy, e.g. by repeating part or in some cases all of the message. This
provides the
function of the message that confirms authenticity. The redundancy provides a
pattern
within the recovered message that would be expected by the recipient. Any
tampering
with the message would be unlikely to produce such a pattern when decrypted
and so
would be readily detected.
The redundancy does, however, increase the message length and therefore the
bandwidth necessary to transmit the message. Generally this is undesirable and
its effect
is seen as a reduced message transmission rate. In some applications, however,
the length
of the message is critical as the signed message may be reproduced as a
printed document
and the length of the message then influences the size of the printed
document. Such an
application is in a mail environment where a bar code may be used to indicate
destination,
postage, rate, .and_.the sender. To avoid fraud, the message is digitally
signed by an
authority and a digital bar code compiled that represents the information
contained in the
signed message. The bar code representation has particular physical
limitations for
readability and to avoid errors caused by e.g. ink bleeding. As a result, a
long message
produces a bar code that is unduly large, particularly where the redundancy
required to
avoid the existential attack is provided by repetition of the whole message.
The length of the message is particularly acute with digital signatures of
messages
that are composed of discrete blocks, as for example in such a mail
environment. In a
conventional signature protocol, a short term secret key k, (the session key),
is selected
and used to exponentiate the generator a of the underlying group to obtain a
short term
public key r = a''. A bit string, r', is derived from r and is used to encrypt
the message m
to obtain ciphertext e, that is e = Er(m) where E. signifies the application
of an encryption
algorithm with the key r' to the message (m).
A signature component, s, is generated that contains information to enable the
authenticity of the signature to be verified. The nature of the signature
component
CA 02591775 2007-06-27
3
depends upon the protocol implemented but a typical exemplary protocol
utilizes a
signature component s of the form s = ae + k mod (n) where n is the order of
the group.
The values of the signature pair s,e forwarded.
In this protocol, the recipient calculates as(aa)', where a' is the public key
of the
sender, to obtain ak which represents the short term public key r.
The ciphertext e can then be decrypted using the key r' to retrieve the
message m.
With a message composed of multiple blocks, ie. m= m,; m2; m3, the ciphertext
e
can be obtained for block m, and the corresponding pair s,e forwarded.
However,
signature component s is dependent upon the encryption of the first block
which leaves
the subsequent blocks vulnerable. It is therefore necessary to sign each block
and
forward multiple signatures, all of which increases the length of the message.
It is therefore an object of the present invention to obviate or niitigate the
above
disadvantages.
In general terms, the present invention generates an encrypted message string,
e,
with a key, r', and the ciphertext is forwarded to the recipient. The
encryptedmessage
string e is also processed by a hash function and the resulting hash e'
utilized in the
signature s. The recipient recovers the message by hashing the message string
e and
utilizes the value to recover the encryption key, r'. The message can then be
recovered
from the message string e.
If appropriate, the redundancy may be checked to ensure the accuracy of the
message but only one signature pair needs to be transferred. Since the
signature is
generated from the hash of the encrypted message string e, individual blocks
of data
cannot be altered.
As a further preference, the certificate accompanying the message may be
incorporated into the message as one of the blocks and signed. The certificate
will have
the requisite redundancy for authentication but because the hash of the string
is used in
the signature, the balance of the blocks do not need any redundancy.
Accordingly, a
shorter message can be utilized.
Embodiments of the invention will now be described by way of example only,
CA 02591775 2007-06-27
4
with reference to the accompanying drawings, in which
Figure 1 is a schematic representation of a data commtmication system;
Figure 2 is a schematic representation of a block of messages;
Figure 3 is a flow chart showing the generation of a digital signature and
recovery
of a message; and
Figure 4 is a schematic representation similar to Figure 2 of an alternative
embodiment.
Referring therefore to Figure 1, a data communication system 10 includes a
pair
of correspondents 12,14 and a communication channe116. As indicated by solid
line, the
communication channel 16 may be a continuous channel between the two
correspondents
12,14 so that digital infonnation may be transferred between the
correspondents. It will
be understood, however, that the channe116 may be interrupted as indicated in
chain dot
lines so that the sender 12 communicates with a bar code assembler 18 which
receives
digital information, converts it to a bar code and prints bar code indicia 20
on an envelope
i5 22. The indicia 20 may then be read with a bar=code reader 24 and the
recovered message
communicated to the recipient 14.
Each of the correspondents 12,14 includes an encryption unit 26,28
respectively
that may process digital information and prepare it for transmission through
the channel
16 as will be described below.
As may be seen from Figure 2, the correspondent 12 wishes to generate a
digital
message m that may be encrypted and applied through the bar code assembler to
the
envelope 22_ The digital message m consists of a plurality of discrete blocks
mj,m2,m3...,
each of which represents a particular piece of information. For example, the
message m,
may be the sender's address, the message m2 may be the recipient's address,
the message
m, may be the postal rate applied, and the message m.4 may indicate the
postage charged
and act as an electronic debit.
In order to sign digitally the message m, the correspondent 12 processes it
through
the encryption unit 26. The unit 26 includes a number generator 30 (see Figure
3) which selects
a random integer k and calculates a short term public key r at exponentiation
unit 32. The
CA 02591775 2007-06-27
unit 26 may operate under any of the established encryption schemes but a
particularly
beneficial implementation is that using eIliptic curves over a finite field.
The short term
public key r is derived from the generator of the group a that is
exponentiated to the
integer k so that r= ar. In an elliptic curve implementation, the underlying
field
5 operation is addition so that "exponentiation" is obtained by k fold
addition of a point P
so that the public key is a point kP on the curve.
A bit string r' is obtained from r by application of a predetermined
algorithm, such
as a modulo reduction or, where the implementation is over an elliptic curve,
one
coordinate of the point representing the public key and utilized as a key by
the encryption
unit to encrypt each of the blocks m,,m2, etc. at encryption module 34. The
encrypted
blocks e; e2; ... are concatenated to form a message string e where
e= e,//e~/...ek and where in general e; = Er(m;) in a register 36.
The encryption unit 26 includes a hash function h indicat.ed at 38 which
processes
the ciphertext string e to produce a shortened bit string comprising hash e'.
Suitable hash
functions are secure one-way cryptographic hash functions such as SHA.
A signature component s is then generated by an arithmetic unit 40 using the
hash
e' and the private key k from which the encryption key r is derived. A
suitable
component has the form -
s = ae' + k mod(n),
where a is the long-term private key of the correspondent 12, and k is the
short-term
private key selected by the correspondent 12.
The encryption unit assembles the message and sends as the signature pair the
message string e and the signature component s from a transmitter 42 through
the channel
16. When used as a mail system, the message may then be compiled into a
discemible
code, such as a two-dimensional bar code, applied as indicia 20 to data
carrier 22 as
indicated in Figure I and subsequently read by the recipient 14. The indicia
20 may be
visibly discernible, as in a printed bar code, may be magnetically discernible
by printing
with magnetic ink or could be optically readable by a laser according to the
particular
application.
CA 02591775 2007-06-27
6
Upon receipt by the recipient 14 at receiver 50, the encryption unit 28
initially
calculates the hash value e' * by hashing the received message string e with
the hash
function h as indicated at 52. A public key r* related to the integer k is
then calculated in
arithmetic unit 54 using operations in the underlying field to exponentiate
the generator a
with the received value of the component s and exponentiating the public key
of the
correspondent 12 with the computed hash value e' *, that is
r* = as(a') "'
An encryption key r*' is then derived from the recovered public key.
An encryption module 56 then processes the received message string e using the
encryption key r*' to recover the message m. The message m will include the
requisite
redundancy which can be checked to ascertain the authenticity of the message.
It will be understood that the procedure outlined in Figure 3 may be
implemented
as software and performed on a general purpose computer or may be implemented
in a
special purpose integrated circuit.
It will be noted that the hash value e' is a hash of all the encrypted blocks
that are
concatenated and so it is not possible to tamper with one of the blocks
without affecting
the resultant hash value. However, although multiple blocks are sent and
recovered, only
one signature is required which reduces the overall message length.
A further embodiment is shown in Figure 4 in which like reference numerals
will
indicate like parameters, with the suffix 'a' added for clarity.
In the embodiment of Figure 4, a certificate issued by a secure authority is
included as a message block msa within the message m. The certificate includes
sufficient
information to permit authentication of the public key of the correspondent 12
and the
parameters of the underlying system. The message string e is assembled as
indicated
above by encrypting each of the blocks to provide a string e,a,eZa, etc.,
including the
certificate mse.
The hash e'a is then obtained and used to generate a signature component Sa of
the
form
sa = ae', + k mod(n).
CA 02591775 2007-06-27
7
Upon recovery by the recipient 14, the recovered message will include the
certificate msa which will exhibit the requisite redundancy as part of the
underlying
system parameters. The redundancy of the certificate m5a therefore
authenticates the
message m and avoids the need for redundancy in the additional blocks.
However, as
previously, since the hash used in the signature s is a hash of all of the
blocks, it is not
possible to substitute one block within the message while retaining the
authenticity of the
signature.
It will be understood that the signature component s may be of any suitable
form
commonly used in digital signature protocols that allow the recovery of the
short term
public key and hence the encryption key from a hash of the encrypted message.
