COLLISION-RESISTANT ELLIPTIC CURVE HASH FUNCTIONS

• US 20100111296A1
• Filed: 10/30/2009
• Published: 05/06/2010
• Est. Priority Date: 10/30/2008
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Struik, Marius, Brown, Daniel R.L., Campagna, Matthew J.
• Granted Patent: US 8,891,756 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

Elliptic curve hash functions are provided which do not require a pre-existing hash function, such as that required by the MuHash. The elliptic curve hash functions can be built from scratch and are collision free and can be incremental. In one embodiment, rather than a pre-existing hash function, the identity function with padding is used; and in another embodiment, rather than a pre-existing hash function, a block cipher with a fixed non-secret key is used.

Claims

1. A computer-implemented method for generating a cryptographic hash H of a message M, said method comprising:

a cryptographic unit obtaining said message M;

said cryptographic unit dividing said message M into a plurality of blocks;

said cryptographic unit indexing each block;

said cryptographic unit mapping each block into a group to provide a plurality of group elements; and

said cryptographic unit combining said group elements to provide an output for representing said hash H of said message M.

2. The method according to claim 1, further comprising said cryptographic unit padding said message M prior to said dividing, and wherein said blocks are mapped to said group using an identity function.

3. The method according to claim 2, wherein said indexing comprises adding a bit representation of an index to each block, said index being incremented for each block.

4. The method according to claim 2, wherein said group elements are points on an elliptic curve, and each group element is generated by:

said cryptographic unit generating a valid x-coordinate for a respective indexed block by searching a series of candidate values and incrementing a counter until said valid x-coordinate is found, and said cryptographic unit generating a respective point on said elliptic curve using said valid x-coordinate.

5. The method according to claim 4, further comprising said cryptographic unit computing a total point by summing said respective points on said elliptic curve, and deriving said hash H from said total point.

6. The method according to claim 5, wherein said hash H is derived from said total point according to the following equation:

└

x(Q+└

x(Q)/2┘

G)/2┘

mod 2ⁿ, where Q is said total point, G is a generator point, and n is a length of said hash H in bits.

7. The method according to claim 1, wherein said plurality of group elements are computed using a block cipher.

8. The method according to claim 7 wherein said block cipher uses a non-secret key k.

9. The method according to claim 8 wherein said plurality of group elements are summed by said cryptographic unit to generate a prehash, said prehash being said output and enabling further processing to generate said hash H therefrom.

10. The method according to claim 9, further comprising:

said cryptographic unit obtaining an updated message M′

comprising at least one modified block; and

for each said at least one modified block;

said cryptographic unit applying said block cipher to said modified block;

said cryptographic unit determining a difference imparted by said modified block; and

said cryptographic unit applying said difference to said prehash to generate an updated prehash.

11. The method according to claim 1, wherein said obtaining comprises said cryptographic unit receiving said message M and a digital signature on said message M, and said method further comprises using said hash H in verifying said digital signature.

12. The method according to claim 11, wherein said cryptographic unit resides in a mobile communications device.

13. A computer readable medium comprising computer executable instructions for generating a cryptographic hash H of a message M, said computer readable medium comprising instructions for:

obtaining said message M;

dividing said message M into a plurality of blocks;

indexing each block;

mapping each block into a group to provide a plurality of group elements; and

combining said group elements to provide an output for representing said hash H of said message M.

14. The computer readable medium according to claim 13, further comprising instructions for padding said message M prior to said dividing, wherein said blocks are mapped to said group using an identity function.

15. The computer readable medium according to claim 14, wherein said indexing comprises adding a bit representation of an index to each block, said index being incremented for each block.

16. The computer readable medium according to claim 14, wherein said group elements are points on an elliptic curve, and each group element is generated using instructions for:

generating a valid x-coordinate for a respective indexed block by searching a series of candidate values and incrementing a counter until said valid x-coordinate is found, and generating a respective point on said elliptic curve using said valid x-coordinate.

17. The computer readable medium according to claim 16, further comprising instructions for computing a total point by summing said respective points on said elliptic curve, and deriving said hash H from said total point.

18. The computer readable medium according to claim 17, wherein said hash H is derived from said total point according to the following equation:

└

x(Q+└

x(Q)/2┘

G)/2┘

mod 2ⁿ, where Q is said total point, G is a generator point, and n is a length of said hash H in bits.

19. The computer readable medium according to claim 13, wherein said plurality of group elements are computed using a block cipher.

20. The computer readable medium according to claim 19 wherein said block cipher uses a non-secret key k.

21. The computer readable medium according to claim 20 wherein said plurality of group elements are summed to generate a prehash, said prehash being said output and enabling further processing to generate said hash H therefrom.

22. The computer readable medium according to claim 21, further comprising instructions for:

obtaining an updated message M′

comprising at least one modified block; and

for each said at least one modified block;

applying said block cipher to said modified block;

determining a difference imparted by said modified block; and

applying said difference to said prehash to generate an updated prehash.

23. The computer readable medium according to claim 13, wherein said obtaining comprises receiving said message M and a digital signature on said message M, and further comprising instructions for using said hash H in verifying said digital signature.

24. The computer readable medium according to claim 23, wherein said computer readable medium resides in a mobile communication device and is accessible to a cryptographic unit in said mobile communications device.

25. A cryptographic unit for generating a cryptographic hash H of a message M, said cryptographic unit being configured for:

obtaining said message M;

dividing said message M into a plurality of blocks;

indexing each block;

mapping each block into a group to provide a plurality of group elements; and

combining said group elements to provide an output for representing said hash H of said message M.