Data file authentication device

• US 6,167,516 A
• Filed: 11/25/1997
• Issued: 12/26/2000
• Est. Priority Date: 04/12/1996
• Status: Expired due to Fees

• Current Assignee: Compagnie Generale D'Informatique et de Tele-Communications, Inria Institut National de Recherche EN Informatique et EN Automatique
• Original Assignee: Compagnie Generale D'Informatique et de Tele-Communications, Inria Institut National de Recherche EN Informatique et EN Automatique
• Inventors: Kalfon, Pierre, Camion, Paul, Sendrier, Nicolas, Cordier, Fran.cedilla.ois
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): LATHAM, BRYAN S
• Application Number:
  US08/952,733
• Time in Patent Office: 1,127 Days
• Field of Search: 713/200, 713/105, 713/168, 713/176, 713/179, 713/170, 380/250, 380/50, 380/4
• US Class Current: 713/168
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A device receives at one input (2) data of a file to be processed, and includes a processing module (5) which at the start of receiving the file, react by three operative stages. These stages include first stage of inserting data blocks from the file into a source memory (MS), after transformation, a second continuous stage of processing each data block of the file, transformed and inserted into the source memory (MS), and a third stage of generating a signature from the transformed, inserted and processed blocks.

Claims

1. A device for authenticating a data file, comprising:

an input (2) capable of receiving the data of a file to be processed;

a buffer memory (3) arranged to store said data in the form of blocks, at predetermined addresses;

a pseudorandom module (4) provided with a working memory (MT) having at least a first segment (SS), a second segment (RI), and a third segment (AI);

a source memory (MS) of the read-write memory type, capable of storing words, each accompanied by an extraction status; and

processing means (5) arranged to cooperate with the pseudorandom module (4) and the source memory (MS) so as to authenticate the file, said processing means being arranged for performing;

a first transfrinnation on a word extracted from the source memory (MS) at an address drawn from the first segment (SS(i)), and

a second transformation on the third segment (AI), with an operand which is either one of said data blocks or, if there are no longer any, the extracted word from the source memory (MS), the extraction statis of said extracted word being then modified,

wherein the processing means includes;

an initializing module (6) to initialize the pseudorandom module,

transfer means (7) capable of placing into the second segment (RI(i+4)), the transform by said first transformation of the extracted word, and finally replacing the extracted word in the source memory, by the transform by said second transformation of the third segment (AI),

a cyclic logic (8) for actuating the pseudorandom module (4), and causing the transfer means (7) to operate until all the words of the source memory (MS) have been extracted once, and once only, and

a generator (9) of the authentication sequence, capable of actuating the pseudorandom module (4), and extracting a random bit from one of the first segment (SS) and second segment (RI) at an address drawn from the third segment (AI), repetitively until a predetermined number of random bits is obtained, and

wherein said predetermined number of random bits forms an authentication sequence for authenticating the data file.

2. A device according to claim 1, wherein the pseudorandom module (4) further comprises an increment memory (MI), forming a table for P predetermined integral increments, the increment memory being a read-only memory.

3. A device according to claim 2, wherein the pseudorandom module (4) is arranged to extract before the first transformation, an increment of the increment memory (MI), at an address drawn from the result of a first operation between at least one predetermined part of the third segment (AI) and at least one predetermined part of the content of one of the first segment (SS) and second segment (RI), and to effect a second operation between at least one predetermined part of the current content of the first segment (SS) and at least the result of the first operation, the result of this second operation replacing the current content of the first segment (SS).

4. A device according to claim 3, wherein the pseudorandom module (4) is arranged to effect a third operation between the word extracted from the source memory, and the respective current contents of at least one part of a zone (i+1) of the first segment (SS) and of at least one part of a zone (i+4) of the second segment (RI), the result of this third operation forming the transform by the first transformation, of the word extracted from the source memory and constituting the new content of the zone (i+4) of the second segment (RI).

5. A device according to claim 3, wherein the transfer means (7) is arranged to extract, after each second transformation, an increment from the increment memory (MI, either of the transform of the word extracted from the source memory, or of the transform of the block extracted from the buffer memory (3), according to the origin of the block or word having been subjected to the said second transformation, and to effect a further operation between the said increment thus extracted from the increment memory (MI) and the current content of the third segment (AI), the result of this further operation constituting the new content of the third segment (AI).

6. A device according to claim 5, wherein the transfer means (7) is arranged to take also into account during the further operation the increment extracted from the increment memory (MI) at the address drawn from the result of the first operation.

7. A device according to claim 1, wherein the processing means (5) is arranged to order the initialization module (6) to initialize the pseudorandom module (4) and the source memory (MS) on receiving information of the start of the file to be processed, and wherein the pseudorandom module (4) is arranged to designate, after the said initialization, a zone (i) from a plurality of zones which comprises at least one of the first segment (SS) and second segment (RI).

8. A device according to claim 7, wherein the pseudorandom module (4) is arranged for incrementing by one unit, modulo the total number of zones of each first segment (SS) and second segment (RI), the number (i) of a currently designated zone, after each extraction of a word from the source memory (MS), and then placing into the source memory a transform of a word or of a block that has been subjected to at least one of the first and second transformations.

9. A device according to claim 7, wherein the generator (9) of the authentication sequence, after activating the pseudorandom module (4), is arranged to then cause the transfer means (7) to operate at least partially, so that each bit is extracted from the segment (RI) concerned, after placement in the second segment (RI(i+4)) of the transform by the first transformation of the word extracted from the source memory (MS) at tie address drawn from the first segment (SS(i)).

10. A device according to claim 7, wherein the generator (9) of the authentication sequence extracts each bit from a current zone (i) of the second segment (RI).

11. A device according to claim 7, wherein the pseudorandom module (4) is arranged for incrementing by one unit, module the total number of zones of each first segment (SS) or second segment (RI), the number (i) of a currently designated zone, after each extraction of a word from source memory (MS), and then placing into the source memory a transform of a word or of a block that has been subjected to at least one of the first and second transformations.

12. A device according to claim 1, wherein the transfer module (7) is arranged to effect a circular permutation (50) operation of at least one bit, over at least a part of the bits of the third segment (AI) of the working memory after each first transformation, the result of this circular permutation operation constituting the new content of the said third segment (AI).

13. A device according to claim 1, wherein after a chosen number of placements of transforms of words or blocks into the source memory (MS), the processing means (5) is arranged to effect a circular permutation (120, 130), of at least one bit over at last a part of the bits of the first segment (SS), the result of this permutation constituting the new content of the said first segment (SS).

14. A device according to claim 1, wherein the buffer memory (3) comprises a shift register, wherein the data blocks are stacked, according to their order of arrival, beneath one another in the free spaces comprised between a first space (B1) and a last space (512) of the shift register, wherein the transfer means (7) is arranged to extract the block which is situated in the first space (B1), and wherein the said buffer memory (3) is arranged to produce after each extraction of the block stored in the first space (B1), a shift by one position of the set of blocks situated after the first space (B1), so that the block which was situated in the second space (B2) is stored in the first space (B1).

15. A device according to claim 1, wherein the first segment (SS), the second segment (RI), and the third segment (AI) of the working memory (MT) are respectively a first register (SS), a second register (RI), and an increment accumulator (AI).