Method and apparatus incorporating a one-way sequence for transaction and identity verification

• US 4,393,269 A
• Filed: 01/29/1981
• Issued: 07/12/1983
• Est. Priority Date: 01/29/1981
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Matyas, Stephen M., Meyer, Carl H., Konheim, Alan G.
• Primary Examiner(s): Cangialosi, Sal
• Application Number:
  US06/229,494
• Time in Patent Office: 894 Days
• Field of Search: 178/22.05, 178/22.08, 178/22.09, 178/22.10
• US Class Current: 705/75
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A method and apparatus for verifying both the content of a transaction and the identity of the parties thereto. The system includes a plurality of terminals connected together over a common communication channel wherein a given pair of users located at different terminals on the system have exchanged a contract comprising a plurality of reference signatures each of which constitutes the final member of a one-way keyed signature sequence and each of which is a one-way function of each user'"'"'s secret encryption key (K_x) and a number (NUM) known to both parties. Each terminal connected to the system includes means for generating a multidigit ranking vector which is a cryptographic function of the entire message (DATA) tobe transmitted. Further means are provided for forming as many signature elements as there are digits in said ranking vector, the particular signature element being an intermediate member of a predetermined one-way keyed signature sequence specified by an associated digit of the ranking vector. Additional means are provided for initiating the generation of a separate keyed signature sequence to derive each signature element beginning with a starting element which requires that user'"'"'s secret encryption key (K_x) and the number (NUM) and continuing the generation of successive members of the one-way keyed signature sequence until the particular signature sequence element (KSS.sub.ρ) which was specified by the associated ranking vector digit (ρ) is obtained. When the appropriate sequence of one-way keyed signature sequence elements has been generated as specified by the ranking vector, this sequence of signature elements is appended onto the original message (DATA) and transmitted to a receiver. Means are provided in each terminal which are activated upon receipt of an appropriately signed message for another terminal for deriving a ranking vector from the received message which again is the same function of the message (DATA) received and a cryptographic function known to both parties. Circuitry is provided, upon the determination of the ranking vector for generating successor one-way keyed signature sequence reference elements from each received signature element based solely upon the knowledge of said element as received and the ranking vector. This process is continued until all reference elements have been derived from the received signature at which point the reference elements so derived are compared with the reference elements previously exchanged between the parties and designated for use for this particular transaction. If the elements match, the identity of the user is unequivocally verified and the contents of the message are guaranteed.

Claims

1. A transaction and identity verification system including a plurality of terminals connected together over a common communication channel wherein any given pair of users located at different terminals on this system have exchanged a contract comprising a plurality of reference signatures, each of which constitutes the final member of a one-way keyed signature sequence and each of which is a one-way function of each users secret encryption key (K_X) and a number (NUM) known to both parties and wherein each terminal connected to said system includes:

means for generating a multi-digit ranking vector which is a cryptographic function of the entire message (DATA) to be transmitted,

means for forming as many signature elements as there are digits in said ranking vector, the particular signature element being an intermediate member of a predetermined keyed signature sequence specified by an associated digit of the ranking vector,

said means for forming including means for initiating the generation of a separate keyed signature sequence to derive each signature element,

means for continuing that keyed signature sequence generation until the particular keyed signature sequence element (KSS.sub.ρ

) specified by the associated ranking vector digit (ρ

) has been generated,

means for transmitting said message (DATA) together with all of said signature elements to another predetermined terminal connected to said system,

means operable upon the receipt of a signed message from another terminal for deriving a ranking vector for said received message which is a function of the message (DATA) received,

means for deriving a successor one-way keyed signature sequence reference element from each received signature element,

means for comparing the derived keyed signature sequence reference elements with the associated keyed signature sequence reference elements in the contract of reference signatures previously exchanged between the users.

2. A transaction and identity verification system as set forth in claim 1 wherein the means for deriving the keyed signature sequence reference elements for received messages includes means for utilizing the associated digit of the ranking vector and for accessing and utilizing an associated number (NUM) from the exchanged contract table to derive each said keyed signature sequence reference element.

3. A transaction and identity verification system as set forth in claim 2 wherein the means for generating both the original one-way keyed signature sequence reference elements and individual signatures include means for utilizing a particular user (X'"'"'s) secret encryption key (K_X) as the initial key input to a key controlled block cypher cryptographic module and utilizing a predetermined number (NUM) previously agreed upon between the parties as at least a part of the data input to said key controlled block cypher cryptographic module to produce the first member (KSS₀) of each keyed signature sequence and means for producing subsequent members of each sequence by key chaining the output of the cryptographic module whereby said output becomes at least a portion of the key input for the next subsequent cryptographic operation in accordance with the formula:

space="preserve" listing-type="equation">KSS.sub.i =DES(KSS.sub.i-1, NUM⊕

KSS.sub.i-1).

4. A transaction and identity verification system as set forth in claim 3 including means for combining NUM with the data used as the key to form the input to the DATA input of said cryptographic module as each element of the keyed signature sequence is generated.

5. A transaction and identity verification system as set forth in claim 3 wherein said means for deriving a one-way keyed signature sequence reference element from the signature element appended to the received message comprises means for utilizing the received signature element as an initial key input to a key controlled block cypher cryptographic module and said predetermined associated number (NUM) from the previously exchanged signature contract as at least a portion of the data input to said cryptographic module,

means for initiating the cryptographic routine and for utilizing the output of one cryptographic routine as the key input for the next operation, and

means for iteratively continuing the one-way keyed signature sequence generation operation as a function of the value of the derived ranking vector digit to produce the required reference signature element.

6. A transaction and identity verification system as set forth in claim 5 wherein the means for generating the ranking vector for both a received message and for a message to be transmitted, includes performing a compressed encoding operation upon said entire message (DATA) whereby any given segment of said compressed encoding is a mathematical function of all of the preceding data input to said encryption operation as defined by:

space="preserve" listing-type="equation">y.sub.n =f(DES(KEY,x.sub.1,x.sub.2, . . . xn))

wherein y_n is the n^th output block from the cryptographic module and wherein x₁ . . . x_n represent the first n input blocks to the cryptographic module.

7. A transaction and identity verification system as set forth in claim 6, including means for using different values of NUM from the contract table for different transactions, whereby a different value of NUM will be used in generating both the individual signatures in a given transaction and in all subsequent transactions.

8. A transaction and identity verification system as set forth in claim 2, including means operative, on a successful validation of an original message and its appended signatures, to form a return message (ACK) for sending to the originating user, including means for repeating at least a part of the original message (DATA) acknowledging receipt of the properly signed original message from which the original sender may ascertain that said original message was accurately received.

9. A transaction and identity verification system as set forth in claim 8, including means for generating a set of signatures for said return message (ACK) utilizing exactly the same procedure as for generating an original message (DATA).

10. A transaction and identity verification system as set forth in claim 9, including means for retaining all messages, including the appended signatures both sent and received by the system together with a indication of the identity of the user to whom and from whom a particular message was transmitted and also an indication of the particular transaction number of said message.

11. A transaction and identity verification system as set forth in claim 10, including means for sending an error message to the sender a received message, when the signatures appended to said message do not match the reference signatures in the contract table, and means responsive to the receipt of such an error message to retrieve the original message from said retaining means to retrieve the original message, regenerate the required signatures in accordance with the content of such message, and retransmit the same to the sender of the error message.

12. A method for verifying the content of a message and the identity of the sender, said method comprising two participants (USER A and USER B) first exchanging a contract containing two finite sequences of keyed-reference-signatures:

space="preserve" listing-type="equation">KSS.sub.r (k.sub.A,1)KSS.sub.r (k.sub.A,2), . . .

space="preserve" listing-type="equation">KSS.sub.r (k.sub.B,1)KSS.sub.r (k.sub.B,2), . . .

wherein the j^th reference signature KSS_r (k_X,j) of USER X is the r^th or final term in the j^th keyed-signature-sequence

space="preserve" listing-type="equation">KSS.sub.0 (k.sub.X,j)KSS.sub.1 (k.sub.Xi ,j), . . . , KSS.sub.r (k.sub.X,j)

whose terms are defined and related as follows;

the initial element

space="preserve" listing-type="equation">KSS.sub.0 (k.sub.X,j)

of the j^th sequence is derived from USER X'"'"'s (secret) key k_X and the index j specifying the keyed-signature-sequence by means of the rule

space="preserve" listing-type="equation">KSS.sub.0 (k.sub.X,j)=DES}k.sub.X,j+k.sub.X }

where DES denotes the Data Encryption Standard and wherein each succeeding element KSS_i (k_X,j) with i=1, 2, . . . , r of the j^th keyed-signature-sequence is derived from the immediately preceding element KSS_i-1 (k_X,j) by a known algorithm f according to the rule

space="preserve" listing-type="equation">KSS.sub.i (k.sub.A,j)=f(KSS.sub.i-1 (k.sub.A,j)

to transmit signed data to USER B, USER A, appending to DATA a number s of signatures

space="preserve" listing-type="equation">DATA,SIG.sub.0,SIG.sub.1, . . . ,SIG.sub.s-1

the t^th signature SIG_t where t=0, 1, . . . , s-1 being the element in position ρ

_t

space="preserve" listing-type="equation">KSS.sub.ρ

.sbsb.t (k.sub.A,NUM.sub.t)

in USER A'"'"'s NUM_t^th keyed-signature-sequence

space="preserve" listing-type="equation">KSS.sub.0 (k.sub.A,NUM.sub.t),KSS.sub.1 (k.sub.A,NUM.sub.t), . . . ,KSS.sub.r (k.sub.A,NUM.sub.t)

the position ρ

_t of the t^th signature SIG_t being determined by the rank of the data

space="preserve" listing-type="equation">ρ

.sub.0,ρ

.sub.1, . . . ,ρ

.sub.s-1

USER A determining the rank of data to produce a sequence of s numbers

space="preserve" listing-type="equation">ρ

.sub.0,ρ

.sub.1, . . . ,ρ

.sub.s-1

each term being an integer having one of the values 0, 1, . . . , r-1. The value of the t^th term ρ

_t depends on DATA through a predetermined cryptographic protocol,

USER B, upon receipt of the signed message

space="preserve" listing-type="equation">DATA,SIG.sub.0,SIG.sub.1, . . . ,SIG.sub.s-1

independently determining the rank of DATA,

space="preserve" listing-type="equation">ρ

.sub.0,ρ

.sub.1, . . . ,ρ

.sub.s-1

USER B then deriving presumptive values for the s reference elements by computing the appropriate successor reference signatures for each of the s appended signatures;

as defined by;

r-ρ

₀^th successor of SIG₀

r-ρ

₁^th successor of SIG₁

. .

. .

. .

r-ρ

_s-1^th successor of SIG_s-1

USER B comparing the computed successor reference elements to the corresponding reference signatures in the previously exchanged contract, and

USER B accepting the transaction if and only if there is complete agreement.

13. A method for verifying as set forth in claim 12, including both users keeping accurate records of the transactions occurring between themselves wherein a transaction comprises a complete message exchange protocol, and accessing a particular set of numbers (NUM'"'"'s) from the exchanged contract table for use in generating the respective keyed signature sequences dependent upon which transaction is currently being performed, and ensuring that new values of NUM are selected from the contract table for successive transactions.

14. A method as set forth in claim 13 including the steps of both users keeping detailed archival records of all messages including appended signatures, both sent and received, together with a copy of the contract to which they apply, and clearly identifying the parties to each such message as well as clearly identifying the particular transaction number.

15. A method as set forth in claim 14, further including USER B, upon a successful determination that a received message (DATA), SIG₀, SIG₁, . . . SIG_s-1 received from USER A is correct and validly signed, preparing a return message (ACK) including as much of the original message (DATA) as necessary for USER A to determine that USER B has received the correct message,

deriving a ranking vector for this new message (ACK),

generating a set of s signatures for this message utilizing his own secret keyed K_B the just generated ranking vector, and the values of NUM utilized by USER A in sending the original message, and

appending these signatures to the message ACK and sending same back to USER A,

USER A upon receipt of the message (ACK), deriving the ranking vector from the message (ACK), generating the appropriate keyed signature sequence reference elements therefrom and

comparing the received reference signatures with those contained in the appropriate portions of the previous exchanged contract table and give identical considering the transaction as terminated.

16. A communication method whereby users of a public data network may upon receipt of a message over the network, verify both the content of the message (DATA) and the identity of the sender wherein said network comprises a plurality of terminals connected together over a common communication channel, and wherein each terminal has the ability to perform a key controlled block cypher cryptographic operation, said method comprising:

any given pair of users located at different terminals on the system first exchanging a contract comprising a plurality of reference signatures, each of which constitutes the final member of a one-way keyed signature sequence and each of which is a one-way function of each user'"'"'s secret encryption key (K_X) and a number (NUM) known to both parties, and included specifically in the contract,

subsequently when a sending user (sender) wishes to send a message (DATA) to a receiving user, performing the steps of generating a multi-digit ranking vector (ρ

₀ . . . ρ

_s-1) which is a predetermined cryptographic function of the entire message (DATA) to be transmitted,

forming as many signature elements (SIG₀ . . . SIG_s-1) as there are digits in said ranking vector, the particular signature element formed being an intermediate member of a predetermined one-way keyed signature sequence specified by an associated digit of the ranking vector,

transmitting said message (DATA) together with all s signature elements to another predetermined terminal connected to said system,

the receiving user, upon the receipt of a signed message from another terminal, deriving a ranking vector ρ

₀ . . . ρ

_s-1 for said received message (DATA) which is also a predetermined cryptographic function of the message (DATA) received, and then,

deriving a successor one-way keyed signature sequence reference element from each received signature element,

comparing the derived keyed signature sequence reference elements with the associated keyed signature sequence reference elements contained in the contract of reference signatures previously exchanged between the users, and

accepting the message (DATA) as validly signed if said comparison is successful.

17. A communication method as set forth in claim 16, the step of a sending user forming the signature elements including the steps of generating the initial member of a one-way keyed signature sequence utilizing USER A'"'"'s own secret encryption key and a predetermined number (NUM) previously agreed on between the users,

continuing the generation of successive elements of each one-way keyed signature sequence utilizing key chaining until the element of said one-way keyed signature sequence is generated which is specified by the associated digit of said ranking vector.

18. A communication method as set forth in claim 17 wherein the receiving user deriving a successor one-way keyed signature sequence reference element includes the steps of utilizing each received signature element as an initial key input to the key controlled block cypher cryptographic operation and said predetermined associated number (NUM) extracted from the previously exchanged signature contract as at least a portion of the data input to said cryptographic operation, performing said cryptographic operation and utilizing the output thereof as the input to the next generation sequence and continuing this operation iteratively until the desired one-way keyed signature sequence reference element is generated.

19. A communication method as set forth in claim 17, including the receiving user'"'"'s determining the number of iterations to be performed in forming said one-way signature sequence reference elements as a function of the associated digit of said previously generated ranking vector.

20. A communication method as set forth in claim 16, including the receiving user, subsequent to the receipt of a properly signed message DATA, forming a return message (ACK) for transmission to the original sending user, containing as much of the original received message (DATA as necessary in order for the original sending user to ascertain that the original message was accurately received,

acknowledging receipt of said properly signed message said receiving user preparing a set of signatures for said return message (ACK) in exactly the same manner the original sending user generated the signatures and appending said newly generated signatures to the message (ACK) and then transmitting same to the sending user.

21. A communication method as set forth in claim 20, including the original sending receiver, after receiving the message (ACK) with its appended signatures, generating a ranking vector for the message (ACK) and deriving the required one-way keyed signature sequence reference elements from these received signatures and comparing them against the previously exchanged contract table.

22. A communication method as set forth in claim 21 including each user retaining all messages received and transmitted together with the appended signatures in an archival file for possible future reference.

23. A communication method as set forth in claim 22 further including a protocol for resolving disputes between USER A and USER B relative to the validity of a signature comprising providing a trusted arbiter who is capable of performing a key controlled block cipher cryptographic operation identical to that utilized by USERS A and B with the precise method utilized for generating both the ranking vector and the one-way keyed signature sequences (KSS) and also providing said arbiter with the original signature contract and the exact message whose signature is disputed together with the signatures to be verified, said arbiter independently generating a set of KSS reference elements from the disputed signatures and the value of NUM taken from the previously obtained signature contract and determining if the reference elements which the arbiter has generated match the reference elements in the signature contract and resolving the dispute in favor of the party, claiming that the signature is correct, if the generated reference elements do, in fact, match those in the contract.

24. A communication as set forth in claim 23 further including a protocol for resolving a conflict wherein USER A disputes the content of a particular message DATA'"'"' comprising said arbiter obtaining the message DATA together with its appended signatures from USER B, which USER B claims he received and then obtaining the message DATA which USER A claims he sent independently generating the ranking vectors for each of the messages DATA and DATA'"'"' and comparing them digit by digit and determining if the following relationship exists:

space="preserve" listing-type="equation">ρ

(DATA'"'"',t)≦

ρ

(DATA,t)0=23t<

s

said relationship exists finding that the message DATA'"'"' is valid and the message DATA is invalid.