Method and device for inserting and authenticating a digital signature in digital data

• US 7,216,232 B1
• Filed: 04/20/1999
• Issued: 05/08/2007
• Est. Priority Date: 04/20/1999
• Status: Expired due to Fees

• Current Assignee: NEC Corporation of America (NEC Corporation)
• Original Assignee: NEC Corporation
• Inventors: Miller, Matthew L., Cox, Ingemar J., Rayner, Douglas F.
• Primary Examiner(s): Zand; Kambiz
• Application Number:
  US09/294,956
• Time in Patent Office: 2,940 Days
• Field of Search: 713/168, 713/167, 713/176, 713/201, 380/202, 380/257, 380/167, 380/267
• US Class Current: 713/176
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/608 Watermarking
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04N 1/32128 attached to the image data, e.g. file header, transmitted message header, information on the same page or in the same computer file as the image for information embedded in the image H04N1/32144
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 1/32283 Hashing
• CPC Class Codes: H04N 2101/00 Still video cameras
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/3269 of machine readable codes or marks, e.g. bar codes or glyphs

Abstract

A method for inserting a digital signature into digital data is provided. The digital data has bits and the method includes the steps of: assigning predetermined bits of the digital data for receiving the digital signature; signing the digital data excluding the predetermined bits resulting in the digital signature; and inserting the digital signature into the predetermined bits of the digital data for subsequent authentication of the digital data. Also provided is a method for authenticating digital data having the embedded digital signature in the predetermined bits of the digital data including the steps of: extracting the digital signature from the predetermined bits; decrypting the digital signature from the digital data resulting in a first hash; applying a known one-way hashing function used by an encoder of the digital data to the digital data excluding the predetermined bits resulting in a second hash; and comparing the first hash to the second hash wherein if the first hash matches the second hash the digital data is authentic. In a preferred version of the methods of the present invention, the method further includes the step of inserting associated data into the digital data prior to the signing step such that the digital signature authenticates both the associated data as well as the digital data. Preferably, the associated data is inserted into the bits of the digital data excluding the predetermined bits.

Claims

1. A method for inserting a digital signature into digital data, the digital data comprising bits, the method comprising the steps of:

assigning predetermined bits of the digital data for receiving the digital signature;

inserting associated data into the digital data;

signing the digital data, excluding the predetermined bits in the digital data, with the digital signature, the digital data including the inserted associated data;

inserting the digital signature into the predetermined bits of the digital data for subsequent authentication of the digital data and the associated data;

receiving the associated data from a Global Positioning Satellite transmission;

wherein at least a portion of the associated data comprises data identifying a public key needed to decrypt the digital signature; and

outputting the digital data with the digital signature inserted into the predetermined bits.

2. The method of claim 1, wherein the signing step comprises:

applying a one-way hashing function to the digital data excluding said predetermined bits resulting in a hash; and

encrypting the hash.

3. The method of claim 1, wherein the digital data is selected from a group consisting of image data, video data, and audio data.

4. The method of claim 1, wherein the associated data is inserted into the bits of the digital data excluding the predetermined bits.

5. The method of claim 1, wherein the digital data comprises a plurality of samples, each of the samples being defined by a plurality of the bits, from a most significant bit to a least significant bit, all of the least significant bits defining the plurality of samples comprising a least significant bit plane, wherein the predetermined bits comprise at least a portion of the least significant bit plane.

6. The method of claim 5, wherein the digital data is an image and each sample is an image pixel.

7. The method of claim 5, wherein the digital data is video and each sample is a spatial temporal sample.

8. The method of claim 5, wherein the digital data is audio and each sample is a time sample.

9. The method of claim 5, wherein the associated data is inserted into at least a portion of the remaining least significant bits in the least significant bit plane.

10. The method of claim 1, wherein the digital data comprises a plurality of samples, each of the samples being defined by a plurality of the bits, further comprising the step of transforming the plurality of bits into an alternative representation having at least first and second characteristic components, wherein the predetermined bits comprise the first characteristic component.

11. The method of claim 10, wherein the digital data is an image and each sample is an image pixel.

12. The method of claim 10, wherein the digital data is video and each sample is a spatial temporal sample.

13. The method of claim 10, wherein the digital data is audio and each sample is a time sample.

14. The method of claim 10, wherein the associated data is inserted into at least a portion of the second characteristic component.

15. The method of claim 14, wherein the alternative representation is a frequency domain representation having high and low frequency components, wherein the first characteristic component is a portion of the high frequency component and the second characteristic component is the remaining high frequency component and the low frequency component.

16. The method of claim 1, wherein the associated data comprises data identifying a source of the digital data.

17. The method of claim 1, wherein the associated data comprises data identifying the identity of an owner of the digital data.

18. The method of claim 17, wherein the digital data is an image and the associated data comprises data identifying a photographer of the image.

19. The method of claim 1, wherein a portion of the associated data is encrypted and a remaining portion of the associated data is unencrypted.

20. The method of claim 1, wherein the associated data comprises at least two fields.

21. The method of claim 20, wherein at least one other field comprises data identifying the owner of the public key.

22. The method of claim 1, wherein the digital data is compressed using a compression standard resulting in a compressed file, wherein the method further comprises the steps of:

creating a decompressed file prior to the signing step;

signing the decompressed file resulting in the digital signature; and

inserting the digital signature into a header in the compressed file instead of inserting the same into the digital data.

23. The method of claim 22, wherein the digital data is an image and the compression standard is JPEG.

24. The method of claim 22, wherein the digital data is video and the compression standard is MPEG.

25. The method of claim 1, wherein the digital data is compressed using a compression standard resulting in a compressed file, wherein the method further comprises the steps of:

creating a decompressed file prior to the signing step;

inserting the associated data into the decompressed file;

signing the decompressed file resulting in the digital signature; and

inserting the digital signature and associated data into a header in the compressed file instead of inserting the same into the digital data.

26. The method of claim 25, wherein the digital data is an image and the compression standard is JPEG.

27. The method of claim 25, wherein the digital data is video and the compression standard is MPEG.

28. The method of claim 1, wherein the digital data comprises a plurality of samples, each of the samples being defined by a plurality of the bits, from a most significant bit to a least significant bit, all of the least significant bits defining the plurality of samples comprising a least significant bit plane, wherein the method further comprises the steps of:

ignoring the least significant bit plane in the digital data;

concatenating the associated data to the digital data having the ignored least significant bit plane prior to the signing step;

performing the signing step to the digital data having concatenated associated data resulting in the digital signature;

wherein the predetermined bits comprise at least a portion of the least significant bit plane and the associated data is inserted into at least a portion of the remaining least significant bits in the least significant bit plane.

29. The method of claim 1, further comprising the steps of:

providing time data identifying the time the digital data was created;

concatenating the hash and the time data;

applying a one-way hashing function to the concatenated hash and time data resulting in a second hash; and

encrypting the second hash instead of the first hash to result in a time stamp containing the digital signature, wherein both the digital data and the time data are subsequently authenticated.

30. The method of claim 29, further comprising the steps of:

transmitting the hash and signature to a third party for performance of the providing, concatenating, and encrypting steps; and

receiving the time stamp from the third party prior to the inserting step.

31. The method of claim 30, wherein the trusted third party resides at an internet address and the transmitting and receiving steps are done through the internet.

32. The method of claim 29, wherein the time stamp is provided by a semiconductor chip having a tamper resistant clock and a tamper resistant time stamping circuit, wherein the clock outputs the time data which together with the digital signature is signed by the circuit to output the time stamp.

33. The method of claim 1, further comprising the steps of:

storing an identifier in a memory corresponding to each of at least one user of a device which creates the digital data;

recognizing a user of the device whose identifier is stored in the memory; and

outputting the identifier corresponding to the recognized user from the memory to be inserted as the associated data.

34. The method of claim 33, further comprising the steps of storing a private key for signing the digital data in the memory corresponding to each user and using the private key for signing the digital data.

35. The method of claim 33, wherein the recognizing step is accomplished by a fingerprint recognition system.

36. The method of claim 33, wherein the identifier is a name of the recognized user.

37. An encoder for inserting a digital signature into digital data, the digital data comprising bits, the encoder comprising:

means for assigning predetermined bits of the digital data for receiving the digital signature;

means for signing the digital data excluding the predetermined bits in the digital data, with the digital signature, the digital data including the inserted associated data;

means for inserting the digital signature into the predetermined bits of the digital data for subsequent authentication of the digital data;

means for inserting associated data into the digital data prior to signing the digital data such that the encoder authenticates both the associated data as well as the digital data; and

means for receiving the associated data from a Global Positioning Satellite transmission;

wherein at least a portion of the associated data comprises data identifying a public key needed to decrypt the digital signature and at least a portion of the associated data comprises data identifying the identity of an owner of the digital data.

38. The encoder of claim 37, wherein the means for signing comprises:

means for applying a one-way hashing function to the digital data excluding said predetermined bits resulting in a hash; and

encrypting the hash.

39. The encoder of claim 37, wherein the digital data is selected from a group consisting of image data, video data, and audio data.

40. The encoder of claim 37, wherein the associated data is inserted into the bits of the digital data excluding the predetermined bits.

41. The encoder of claim 37, wherein the digital data comprises a plurality of samples, each of the samples being defined by a plurality of the bits, from a most significant bit to a least significant bit, all of the least significant bits defining the plurality of samples comprising a least significant bit plane, wherein the predetermined bits comprise at least a portion of the least significant bit plane.

42. The encoder of claim 41, wherein the digital data is an image and each sample is an image pixel.

43. The encoder of claim 41, wherein the digital data is video and each sample is a spatial temporal sample.

44. The encoder of claim 41, wherein the digital data is audio and each sample is a time sample.

45. The encoder of claim 41, wherein the associated data is inserted into at least a portion of the remaining least significant bits in the least significant bit plane.

46. The encoder of claim 37, wherein the digital data is an image comprising a plurality of samples, each of the samples being defined by a plurality of the bits, further comprising means for transforming the plurality of bits into an alternative representation having at least first and second characteristic components, wherein the predetermined bits comprise the first characteristic component.

47. The encoder of claim 46, wherein the digital data is an image and each sample is an image pixel.

48. The encoder of claim 46, wherein the digital data is video and each sample is a spatial temporal sample.

49. The encoder of claim 46, wherein the digital data is audio and each sample is a time sample.

50. The encoder of claim 46, wherein the associated data is inserted into at least a portion of second characteristic component.

51. The encoder of claim 50, wherein the alternative representation is a frequency domain representation having high and low frequency components, wherein the first characteristic component is a portion of the high frequency component and the second characteristic component is the remaining high frequency component and the low frequency component.

52. The encoder of claim 37, wherein the associated data comprises data identifying a source of the digital data.

53. The encoder of claim 37, wherein the digital data is an image and the associated data comprises data identifying a photographer of the image.

54. The encoder of claim 37, wherein a portion of the associated data is encrypted and a remaining portion of the associated data is unencrypted.

55. The encoder of claim 37, wherein the associated data comprises at least two fields.

56. The encoder of claim 37, wherein at least one of the fields comprises data identifying the owner of the public key.

57. The encoder of claim 37, wherein the digital data is compressed using a compression standard resulting in a compressed file, wherein the encoder further comprises:

means for creating a decompressed file prior to signing the digital data;

means for signing the decompressed file resulting in the digital signature; and

means for inserting the digital signature into a header in the compressed file instead of inserting the same into the digital data.

58. The encoder of claim 57, wherein the digital data is an image and the compression standard is JPEG.

59. The encoder of claim 57, wherein the digital data is video and the compression standard is MPEG.

60. The encoder of claim 37, wherein the digital data is compressed using a compression standard resulting in a compressed file, wherein the encoder further comprises:

means for creating a decompressed file prior to signing the digital data;

means for inserting the associated data into the decompressed file;

means for signing the decompressed file with the associated data inserted therein resulting in the digital signature; and

means for inserting the digital signature and associated data into a header in the compressed file instead of inserting the same into the digital data.

61. The encoder of claim 60, wherein the digital data is an image and the compression standard is JPEG.

62. The encoder of claim 60, wherein the digital data is video and the compression standard is MPEG.

63. The encoder of claim 37, wherein the digital data comprises a plurality of samples, each of the samples being defined by a plurality of the bits, from a most significant bit to a least significant bit, all of the least significant bits defining the plurality of samples comprising a least significant bit plane, wherein the encoder further comprises:

means for ignoring at least a portion of the least significant bit plane in the digital data;

means for concatenating the associated data to the digital data having the ignored least significant bit plane prior to signing the digital data;

means for signing the digital data having the concatenated associated data resulting in the digital signature;

wherein the predetermined bits comprise at least a portion of the least significant bit plane and the associated data is inserted into at least a portion of the remaining least significant bits in the least significant bit plane.

64. The encoder of claim 37, further comprising:

means for providing time data identifying the time the digital data was created;

means for concatenating the hash and the time data;

means for applying a one-way hashing function to the concatenated hash and time data resulting in a second hash; and

means for encrypting the second hash instead of the first hash to result in a time stamp containing the digital signature, wherein both the digital data and the time data are subsequently authenticated.

65. The encoder of claim 64, further comprising:

means for transmitting the hash to a third party for providing the time stamp and concatenating the hash and time stamp; and

means for receiving the second hash from the third party prior to encryption.

66. The encoder of claim 65, wherein the trusted third party resides at an internet address and the means for transmitting and receiving is a computer capable of accessing the internet and receiving the transmitted second hash.

67. The encoder of claim 64, further comprising a semiconductor chip having a tamper resistant clock and a tamper resistant time stamping circuit, wherein the clock outputs the time data which together with the digital signature is signed by the circuit to output the time stamp.

68. The encoder of claim 37, further comprising:

a memory for storing an identifier corresponding to each of at least one user of a device which creates the digital data;

recognition means for recognizing a user of the device whose identifier is stored in the memory; and

output means for outputting the identifier corresponding to the recognized user from the memory to be inserted as the associated data.

69. The encoder of claim 68, wherein a private key for signing the digital data is also stored in memory corresponding to each user, wherein the identifier is inserted as associated data and the private key is used to sign the digital data.

70. The encoder of claim 69, wherein the recognition means is a fingerprint recognition system.

71. The encoder of claim 70, wherein the identifier is a name of the recognized user.