Cryptography – Key management – Key distribution
Reexamination Certificate
1997-10-10
2001-04-03
Swann, Tod (Department: 2132)
Cryptography
Key management
Key distribution
C380S281000, C380S283000, C380S285000, C380S045000, C713S176000, C713S177000, C713S180000
Reexamination Certificate
active
06212281
ABSTRACT:
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 &agr; with the integer k to provide a public key in the form &agr;
k
. The value of the integer k cannot derived even though the exponent &agr;
k
is known.
The public and private keys may be utilized in a message exchange over a data communication system where one of the correspondents may encrypt the data with the recipient's public key &agr;
k
. The recipient receives the encrypted message and utilizes his 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 &agr;
k
. 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 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 &agr; of the underlying group to obtain a short term public key r=&agr;
k
. A bit string, r′, is derived from r and is used to encrypt the message m to obtain ciphertext e, that is e=E
r′
(m) where E
r′
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 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 &agr;
s
(&agr;
−a
)
e
, where &agr;
−a
is the public key of the sender, to obtain &agr;
k
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
1
; m
2
; m
3
, the ciphertext e can be obtained for block m
1
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 mitigate 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 encrypted message 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.
REFERENCES:
patent: 4641347 (1987-02-01), Clark et al.
patent: 4660221 (1987-04-01), Dlugos
patent: 4796193 (1989-01-01), Pitchenik
patent: 4881264 (1989-11-01), Merkle
patent: 4947430 (1990-08-01), Chaum
patent: 5018196 (1991-05-01), Takaragi et al.
patent: 5208858 (1993-05-01), Vollert et al.
patent: 5245657 (1993-09-01), Sakurai
patent: 5351297 (1994-09-01), Miyaji et al.
patent: 5442707 (1995-08-01), Miyaji et al.
patent: 5479515 (1995-12-01), Longacre, Jr.
patent: 5499294 (1996-03-01), Friedman
patent: 5581616 (1996-12-01), Crandall
patent: 5608801 (1997-03-01), Aiello et al.
patent: 5638446 (1997-06-01), Rubin
patent: 0639907 (1995-02-01), None
Bruce Schneier; “Applied Cryptography, Second Edition”, John Wiley & Sons, Oct. 18, 1995, pp. 37-39 and pp. 476-479.
Callahan Paul E.
Certicom Corp.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Swann Tod
LandOfFree
Digital signature protocol does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital signature protocol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital signature protocol will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2510467