Process for generating a check word for a bit sequence for verifying the integrity and authenticity of the bit sequence

• US 6,044,488 A
• Filed: 12/16/1997
• Issued: 03/28/2000
• Est. Priority Date: 02/29/1996
• Status: Expired due to Fees

• Current Assignee: GMD-Forschungszentrum Informationstechnik GmbH, International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liedtke, Jochen
• Primary Examiner(s): Nguyen, Hoa T.
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US08/945,592
• Time in Patent Office: 833 Days
• Field of Search: 714/807, 714/799, 714/808, 714/757, 380/23, 380/25, 380/42, 380/43
• US Class Current: 714/807
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

The method is intended for the generation of a check word for a bit string to check the integrity and authenticity of the bit string, the bit string comprising at least one data set consisting of a plurality of data words, each having the same word length defined by a number of bits. Here, a random number is generated for each data word, the number having the same number of bits as the data words. Further, first and second operand pairs are generated, each consisting of a data word and a random number. The data word and the random number of each first operand pair are subjected to a first linking operation, while the data word and the random number of each second operand pair is subjected to a second linking operation. The results of all operations applied to the first and second operand pairs are linked, the result of this linking being the check word of this data set.

Claims

1. A method for generating a check word for a bit string to check the integrity and authenticity of the bit string, the bit string comprising at least one set of data comprising a plurality of data words, each having the same word length defined by a number of bits, the method comprising:

generating a random number for each data word, the number having the same number of bits as the data words,

generating first and second operand pairs, each comprising a data word and a random number,

combining the data word and the random number of each first operand pair by a first function,

combining the data word and the random number of each second operand pair by a second function, and

combining the results of all operations applied to the first and second operand pairs, the result of this combination being the check word of the set of data.

2. The method of claim 1, characterized in that the first function is a modulo-2^word length -addition.

3. The method of claim 1, characterized in that the second function is a bit-by-bit exclusive-OR operation.

4. The method of one of claim 1, characterized in that the results of all operations applied to the first and second operands are alternately combined by a first function and a second function.

5. The method of claim 4, characterized in that the first function is a modulo-2^word length -addition.

6. The method of claim 4, characterized in that the second function is a bit-by-bit exclusive-OR operation.

7. The method of claim 1, characterized in that the bit string comprises a plurality of data sets, each with the same number of data words, and that the random numbers with which the data words of the first and second operand pairs of as data set are combined, are the same for each data set.

8. The method of claim 7, characterized in that the sequence of the random numbers, in which they are combined with the data words of the first and second operand pairs, may be changed per data set.

9. The method of claim 1, characterized in that the check words obtained for the individual data sets are combined with each other.

10. The method of claim 9, characterized in that the combining of the check words may be altered from check word to check word.

11. The method of claim 10, characterized in that the first combining operation is a modulo-2^word length -multiplication.

12. The method of claim 10, characterized in that the second combining operation is a modulo-2^word length -addition.

13. The method of claim 9, characterized in that the combining is a modulo-2^wordlength -addition, a modulo-2^wordlength -multiplication and/or a bit-by-bit exclusive-OR operation.

14. The method of claim 9, characterized in that the combining is selected such that, according to a first combining operation, the check word of a data set of the bit string is combined with a first combination word of the same length as the check word and that, according to a second combining operation, the result of the first combining operation is combined with a second combination word of the same length as the result of the first combining operation and that the result of the second combining operation is combined with the check word of the next data set of the bit string.

15. A method of sending bit strings with secured integrity and/or authenticity from a sender to a receiver, the bit string comprising at least one data set comprising a plurality of data words, each having the same word length defined by a predeterminable number of bits, the method comprising:

generating a check word by means of a key known to the sender and to the receiver,

generating a random number for each data word, having the same number of bits as the data words,

forming first and second operand pairs, each comprising a data word and a random number,

subjecting the data word and the random number of each first operand pair to a first function,

subjecting the data word and the random number of each second operand pair to a second function, and

combining the results of all operations applied to the first and second operand pairs, the result of this combining being the check word of the data set, and

sending the bit string, together with the check word, from the sender to the receiver, wherein it is possible for the receiver to check the integrity and/or authenticity of the bit string by determining the check word from the received bit string and the key known to the receiver and by comparing the obtained check word to the check word received from the sender.

16. The method of claim 15, characterized in that the first function is a modulo-2^word length -addition.

17. The method of claim 15, characterized in that the second function is a bit-by-bit exclusive-OR operation.

18. The method of claim 15, characterized in that the results of all operations applied to the first and second operands are alternately linked by a first function and a second function.

19. The method of claim 18, characterized in that the second function is a bit-by-bit exclusive-OR operation.

20. The method of claim 18, characterized in that the first function is a modulo-2^word length -addition.

21. The method of claim 15, characterized in that the bit string comprises a plurality of data sets, each with the same number of data words, and that the random numbers with which the data words of the first and second operand pairs of as data set are combined, are the same for each data set.

22. The method of claim 21, characterized in that the sequence of the random numbers, in which they are combined with the data words of the first and second operand pairs, may be changed per data set.

23. The method of claim 15, characterized in that the check words obtained for the individual data sets are combined with each other.

24. The method of claim 23, characterized in that the combining of the check words may be altered from check word to check word.

25. The method of claim 24, characterized in that the first combining operation is a modulo-2^word length -multiplication.

26. The method of claim 24, characterized in that the second combining operation is a modulo-2^word length -addition.

27. The method of claim 23, characterized in that the combining is a modulo-2^wordlength -addition, a modulo-2^wordlength -multiplication and/or a bit-by-bit exclusive-OR operation.

28. The method of claim 23, characterized in that the combining is selected such that, according to a first combining operation, the check word of a data set of the bit string is combined with a first combination word of the same length as the check word and that, according to a second combining operation, the result of the first combining operation is combined with a second combination word of the same length as the result of the first combining operation and that the result of the second combining operation is combined with the check word of the next data set of the bit string.