Authentication algorithms for video images

• US 5,870,471 A
• Filed: 11/27/1996
• Issued: 02/09/1999
• Est. Priority Date: 11/27/1996
• Status: Expired due to Term

• Current Assignee: ADT Security Services SA (Apollo Global Management, Inc.)
• Original Assignee: ESCO Electronics Corporation
• Inventors: Wootton, John R., Hobson, Gregory L., Waldman, Gary S.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/757,838
• Time in Patent Office: 804 Days
• Field of Search: 380/10, 380/23, 382/253, 348/232, 348/441, 348/552
• US Class Current: 713/179
• 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 2201/3205 of identification information, e.g. name or ID code H04N2201/3209 takes precedence
• CPC Class Codes: H04N 2201/3215 of a time or duration
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/3236 Details of authentication information generation
• CPC Class Codes: H04N 2201/3274 Storage or retrieval of prestored additional information
• CPC Class Codes: H04N 2201/3278 Transmission

Abstract

A method of authenticating a video image created by a camera (V) or similar video device. The image is formed into a first 2-dimensional pixel array (A1) with each pixel (p_m,n) represented by a data word of a predetermined length. This formatted array is converted into a second 2-dimensional array (A2) which may be made smaller than the first array by eliminating rows and columns from the formatted array. A first linear vector (A3) is created using the data words in the second array, and a second linear vector (A4) is created by repositioning the data words from the first linear vector in a random pattern. A checksum is created by summing the contents of all of the data words in the second linear vector beginning at a location established by a pre-established formula. A header (H) is formed using the resulting checksum, information identifying the device used to create the image, and the time the image is formed. The header is attached to the formatted image and is transmitted and stored with the formatted image to subsequently authenticate the contents of the original image.

Claims

1. A method of authenticating a video image by forming the image into a data format, encrypting a portion of the formatted image, and attaching the encrypted portion to the original image so the content of the original image can thereafter be authenticated by reference to the encrypted portion thereof, said formatted image comprising a 2-dimensional array of pixels each of which is represented by a data word of a defined length and the method includes converting the formatted image from said 2-dimensional array into a second 2-dimensional array.

2. The method of claim 1 further including detecting any modification to the content of the original image and determining where in the image the modification occured.

3. The method of claim 1 further including forming a header for the formatted image using the encrypted portion thereof, attaching the header to the formatted image, and storing or transmitting the header with the formatted image for authenticating the image.

4. The method of claim 1 wherein forming the second 2-dimensional array includes manipulating the rows and columns of the formatted array by a set of rules which incorporate the time at which the original image is formed.

5. The method of claim 4 further including converting the second 2-dimensional array into a linear vector by concatenating the data words contained in the second array.

6. The method of claim 5 further including converting the aforesaid linear vector into a second linear vector in which the position of the data words in the first linear vector are located at different positions in the second linear vector, the positioning of the data words in the second linear array being determined in accordance with a predetermined code by which the data words are randomly positioned in the second linear vector.

7. The method of claim 6 further including determining a checksum using the data words as arranged in the second linear vector, the checksum determination beginning at a location in the second linear vector which is established by a formula in which values representing elements of the time at which the image is formed are included.

8. The method of claim 7 wherein determining the checksum includes successively summing the values of each of the bits comprising a predetermined number of data words, the summation beginning with the most significant bit in each data word and proceeding through to the summation of the least significant bit thereof.

9. The method of claim 8 wherein determining the checksum further includes computing a checksum for blocks of data words each of which comprises the predetermined number of data words until a checksum is produced which includes all the data words in the second linear vector.

10. The method of claim 8 further including forming a header which is attached to the formatted array, one portion of the header including data words representing the checksum value for the data words contained in the second linear vector, the checksum value contained in the header being used to authenticate the contents of the formatted image.

11. The method of claim 10 wherein another portion of the header is formed by combining information relating to an identity and location of a device used to form the image, and the time at which the image is formed.

12. The method of claim 3 wherein the operations performed in producing the authentication are incorporated in an algorithm, portions of the algorithm including values representing elements of the time at which the image is formed, the values of the time elements periodically changing whereby an authentication for a formatted image produced at one time would be different from the authentication for the same formatted image if produced at a different time.

13. The method of claim 4 further including repositioning the rows and columns in the second array, the repositioning being determined in accordance with a predetermined code by which the rows and columns are randomly repositioned into a third 2-dimensional array.

14. The method of claim 13 further including determining a checksum for the third array by successively summing the values of the bits forming the data words for each row and column of the third array, the summation beginning by summing all of the most significant bits in the data words and proceeding through to the least significant bits thereof, the checksum determination beginning at a location in the third array established by a formula in which values representing elements of the time at which the image is formed are included.

15. The method of claim 14 further including forming a header which is attached to the formatted array, one portion of the header including data words representing the checksum value for the data word values contained in the third array, the checksum value contained in the header being used to authenticate the contents of the formatted image.

16. The method of claim 15 wherein another portion of the header is formed by combining information relating to an identity and location of a device used to form the image, and the time at which the image is formed.

17. A method of authenticating a video image comprising:

creating a video image using a video device;

formatting the image created by the device into a first 2-dimensional pixel array in which each pixel is represented by a data word of a predetermined length;

converting the first 2-dimensional array into a second 2-dimensional array by manipulating the rows and columns in the first array;

forming a linear vector using the data words in the second array with the location of data words being randomly selected;

determining a checksum from the data words in the linear vector;

forming a header using the checksum, information identifying the device used to create the image, and the time at which the image is formed; and

,

attaching the header to the formatted array representing the original contents of the image for the header to be stored or transmitted with the formatted array with the information contained in the header used to authenticate the image.

18. The method of claim 17 wherein the second array is smaller in size than the first array and is formed by eliminating selected rows and columns in the first array, the rows and columns which are eliminated being determined in accordance with a set of rules incorporating elements of the time at which the image is formed.

19. The method of claim 18 further including converting the second array into a first linear vector by concatenating the data words in the second array.

20. The method of claim 19 further including converting the first linear vector into a second linear vector in which the position of the data words in the first linear vector are located at different positions in the second linear vector, the positioning of the data words in the second linear array being determined in accordance with a predetermined code by which the data words are randomly positioned in the second linear vector.

21. The method of claim 20 wherein determining the checksum includes:

selecting a predetermined number of consecutive data words in the second linear vector;

summing the contents of the data words beginning by summing all of the most significant bits in the data words and proceeding through to the least significant bits; and

,

computing a checksum for blocks of data words each of which comprises the predetermined number of data words until a checksum is produced which includes all the data words in the second linear vector, the location in the second linear vector where the checksum determination begins being established by a formula in which values representing elements of the time at which the image is formed are included.

22. The method of claim 21 wherein the location in the second linear vector where the checksum determination begins is a function of the month, day, hour, and minute at which the image is formed.

23. The method of claim 21 wherein forming the header includes:

forming a first portion of the header by combining together information relating to an identity and location of a device used to form the image, and the time at which the image is formed; and

,

forming a second portion of the header including the checksum value for all the data words in the second linear vector.

24. A method of authenticating a video image comprising:

creating a video image using a video device;

formatting the video image into a 2-dimensional pixel array in which each pixel is represented by a data word of a predetermined length;

converting the formatted array into a second 2-dimensional array by manipulating the rows and columns forming the formatted array;

determining a checksum from the data words forming the second array;

forming a header using the checksum, information identifying the device used to create the image, and the time at which the image is formed; and

,

attaching the header to the formatted array and storing or transmitting the header with the formatted array to authenticate the content of the original image as stored in the formatted array.

25. The method of claim 24 wherein the second array is smaller in size than the formatted array and is formed by eliminating selected rows and columns in the formatted array, the rows and columns which are eliminated being determined in accordance with a set of rules incorporating elements of the time at which the image is formed.

26. The method of claim 25 further including repositioning the rows and columns of the second array into a third 2-dimensional array, the repositioning being determined in accordance with a predetermined code by which the rows and columns are randomly repositioned into the third array.

27. The method of claim 26 wherein determining the checksum for the third array includes successively summing the values of the bits forming the data words for each row and column of the third array, the summation beginning by summing all of the most significant bits in the data words and proceeding through to the least significant bits thereof, the checksum determination beginning at a location in the third array established by a formula in which values representing elements of the time at which the image is formed are included.

28. The method of claim 27 wherein forming the header includes:

forming a first portion of the header by combining together information relating to an identity and location of a device used to form the image, and the time at which the image is formed; and

,

forming a second portion of the header including the checksum value for all the data words in the third array.

29. A method of authenticating a video image comprising:

creating a video image using a video device;

formatting the image created by the device into a first 2-dimensional pixel array in which each pixel is represented by a data word of a predetermined length;

converting the first 2-dimensional into a second 2-dimensional array which is a smaller array than the first array, the conversion from the first to the second 2-dimensional array being performed by eliminating rows and columns from the first array in accordance with a set of rules incorporating elements of the time at which the image is formed;

converting the second array into a linear vector by which the position of the data words is determined in accordance with a predetermined code by which the data words are randomly positioned in the linear vector;

determining the checksum for the image by summing the contents of all of the data words in the linear vector beginning at a location established by a formula in which values representing elements of the time at which the image is formed are included;

forming a header using the resulting checksum, information identifying the device used to create the image, and the time at which the image is formed, and;

attaching the header to the formatted array representing the original contents of the image for the header to be stored or transmitted with the formatted array with the information contained in the header used to authenticate the image.

30. A method of authenticating a video image comprising:

creating a video image using a video device;

formatting the video image into a 2-dimensional pixel array in which each pixel is represented by a data word of a predetermined length;

converting the formatted array into a second 2-dimensional array by eliminating selected rows and columns in the formatted array, the rows and columns which are eliminated being determined in accordance with a set of rules incorporating elements of the time at which the image is formed;

repositioning the rows and columns of the second array into a third 2-dimensional array, the repositioning being determined in accordance with a predetermined code by which the rows and columns are randomly repositioned into the third array;

determining a checksum for the image by summing the contents of all of the data words in the third array beginning at a location established by a formula in which values representing elements of the time at which the image is formed are included;

forming a header using the checksum, information identifying the device used to create the image, and the time at which the image is formed; and

,

attaching the header to the formatted array and storing or transmitting the header with the formatted array to authenticate the content of the original image as stored in the formatted array.