Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
  • H04L9/065—Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
  • H04L9/0656—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
  • H04L9/0662—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher with particular pseudorandom sequence generator

Definitions

• the invention relates to the field of encryption / decryption and relates to a system and method for generating a pseudo-random data sequence.
• the invention finds a very advantageous application in that it makes it possible to create sequences of bits for symmetric encryption, for which encryption and decryption use the same secret key.
• the invention is part of a flow encryption method which consists in adding bit by bit a message with a pseudo-random data sequence of the same length.
• it is part of a process in which the encryption operation and the decryption operation are identical.
• symmetric encryption is widely used in all types of communications, such as mobile communications (GSM, UMTS ...), internet (SSL %), smart cards (bank cards), etc.
• the most basic symmetric ciphering technique is stream ciphering, which consists in adding the clear message bitwise with a random sequence of the same length. This technique poses the essential and difficult problem of generating long pseudo-random sequences.
• linear feedback shift registers The most common method of stream encryption is to use a pseudorandom sequence generated independently of the message to be encrypted by using, for the sake of economy, linear feedback shift registers.
• the major disadvantage of linear feedback shift registers is their linearity. Indeed, the knowledge of a number of output bits of the register equal to the length of the register as well as the feedback polynomial associated with the register makes it possible to know the output bits as well as all the subsequent states of the register.
• FIG. 5 shows such a generator 121 called "shrinking generator” described in the European patent application EP 0 619 659 comprising a first linear feedback shift register 123a, a second linear feedback shift register 123b, and a means 125 for select the output of the generator 121.
• the two registers 123a and 123b are shifted simultaneously, and the output of the device 121 is equal to the output of the second register 123b if the output of the first register 123a is "1", otherwise none bit is out.
• the shrinking generator makes it possible to combine not only the outputs of two linear feedback shift registers but also, more generally, any pair of bit sequences.
• the shrinking generator is part of a class of stream ciphering methods in which a linear feedback shift register controls another. The idea is to vary the number of offsets, on the one hand, between the different registers used and, on the other hand, between two consecutive bits, in order to break the linearity of the registers.
• a variant of the shrinking generator is based on the same principle, but starting from a single register.
• the output bits of the register are read in pairs, and Ie first bit controls the output of the second so that the output of the system is the second bit if the first is "1", and no bit is output otherwise.
• the use of complete prefix codes allows a unique decomposition of the initial data stream and can be easily performed by a finite state machine.
• this method is simple to implement, and it uses a function to desynchronize the initial data stream to generate a pseudo-random data sequence.
• the use of a complete prefix code and a "desynchronization component" makes it possible to prevent or render the algebraic attacks practically ineffective while producing a guaranteed minimum number of bits.
• a shrinking generator is used as a desynchronization component in a pseudorandom sequence generator, the minimum assured bit rate is practically nil.
• said desynchronization function is a parameterized function dependent on a predetermined parameter whose value is modifiable during the generation of the pseudo-random data sequence.
• said desynchronization depends on an editable initialization parameter makes it possible to improve the complexity of the relationship between the initial data flow and the pseudo-random data sequence, increasing the difficulty of predicting the pseudo-random data sequence.
• said set of output words comprises for each output word a complementary output word. This makes it possible to balance, for a given output word length, for example the number of "0" and "1" in the set of output words.
• the code words of said complete prefix code have a length limited by an upper bound h, and said code is such that if any output word x is of the same length as another output word y, then the number of antecedents by said function of desynchronization of the output word x is the same as the number of antecedents by said desynchronization function of the output word y.
• the words of said complete prefix code have a length limited by a lower bound m, and there exists a greater length / of words of said complete prefix code such that for any length k less than or equal to the greater length f, the complete prefix code contains 2 '" TM 1 words of length k.
• the method is characterized in that:
• the complete prefix code is defined by a set C 1 of code words having the following form;
• f u U n for 0 ⁇ n ⁇ h-2
• f u (l (Tl) Un® 1 for 0 ⁇ n ⁇ h -2
• C 2 ⁇ associates with any word of the form W 1 W 2 :
• This other embodiment can be advantageously used for software-type encryption.
• the ratio between the number of bytes output and the number of input bytes is strictly greater than 1/3 and the guaranteed minimum number of bytes output on an input of length h bytes is 1.
• the invention also relates to a generator of a pseudo-random data sequence from an initial data stream, characterized in that it comprises a memory and a processing unit, said memory storing a set of code words forming a complete prefix code and a set of output words, said processing unit being able to read and to decompose the initial data stream into a sequence of words coded according to said complete prefix code and to associate the words of said sequence of coded words corresponding output words in accordance with a desynchronization function for generating said pseudo-random data sequence.
• this generator makes it possible to generate a pseudo-random data sequence having a minimum bit rate that does not depend on the particular properties of the initial data stream.
• this generator is easy to implement while being efficient and inexpensive.
• the generator further comprises a parameterization means intended to make said desynchronization function dependent on a predetermined parameter and to modify the value of said predetermined parameter during the generation of the pseudo-random data sequence.
• the invention also provides an encryption / decryption device comprising an "exclusive-or" logic gate and a generator according to the above characteristics.
• This device makes it possible to easily combine each bit of the pseudo-random data sequence with a corresponding bit of a data sequence of a message to be encrypted by a modulo 2 addition to form an encrypted data sequence having a great linear complexity. .
• the invention also relates to a secure system comprising at least two entities connected via a network, each of said at least two entities comprises an encryption / decryption device according to the above characteristics.
• the secure system has a simple structure to achieve while having an intrinsically complex mechanism.
• FIG. 1 very schematically illustrates a method of generating a pseudo-random data sequence, according to the invention
• FIGS. 2A and 2B schematically show two examples of finite automata for decomposing an initial data stream into a sequence of words coded according to the invention
• FIGS. 3A and 3B illustrate schematic examples of a generator of a pseudo-random data sequence, according to the invention
• FIG. 4 shows a secure system comprising generators according to FIG. 3A or 3B;
• FIG 5 is a schematic view of a generator according to the prior art.
• FIG. 1 illustrates a schematic example of a method for generating a pseudo-random data sequence 1 from an initial data stream 3.
• a "word” (or a pattern) / any finite sequence of letters of any alphabet, for example the alphabet of the binary set consisting only of 0 and 1.
• Each word then has a given length. For example, 0, 11, 000, 1010, 00111 are words of respective lengths 1, 2, 3, 4 and 5.
• an "empty" word denoted by ⁇ is a word of zero length (ie ie, containing no letter).
• the initial data stream 3 corresponds to a data sequence having a high "linear complexity".
• the initial data stream 3 can be generated by an initial production means 23
• any periodic sequence can be generated by an infinity of linear feedback shift registers.
• these registers there is one which is shorter than all the others.
• the length of this shorter register is called the "linear complexity" of the stream. If the linear complexity of the initial data sequence is L 1 then it is possible by a Berlekamp-Massey algorithm to reconstruct the initial state of the register (and in fact the whole sequence) from a subset of the initial data sequence of length 2L
• the initial data stream 3 has a high linear complexity. Indeed, currently, the best known algorithm, can reconstruct the initial data stream 3 in less than 2 80 operations if the linear complexity L of this initial data stream is less than 160. Therefore, it is advantageous to take a flow initial data 3 having a linear complexity L greater than or equal to 160.
• a set of codewords 5a forming a "complete prefix code” 5 is defined.
• code refers to any set of words on a given alphabet. The properties of this code are then considered relative to the alphabet in question.
• the code C is complete if, and only if, for every word w, there exists a word w 'and a code word u belonging to Ctel that / y is prefix of the word ww', that is to say say that there exists a word w ⁇ a code word u belonging to this a word u 'such that ww' is equal to uu '.
• C is a complete prefix code if C is both a prefix code and a complete code.
• a set 7 of output words 7a denoted by £ is defined, such that £ is contained in the union of ⁇ 0, l ⁇ k and ⁇ , and a desynchronization function / associating with any codeword.
• 5a of the complete prefix code 5 an output word 7a of the set 7 of output words.
• the desynchronization function / is a basic operation (for example a bit-to-bit modulo 2 addition) whose evaluation is inexpensive to perform.
• the method of the present invention takes as input a complete prefix C code 5, a set E of output words 7, and a desynchronization function /.
• the method according to the invention comprises a decomposition operation decomposing the initial data stream 3 into a sequence of words coded as 11 according to said complete prefix code 5.
• a complete prefix code allows to decompose the initial data stream 3 in a unique manner.
• the complete prefix code 5 is recognizable by a finite automaton which, given a word W 1, determines whether w is or is not in the complete prefix code 5.
• FIGS. 2A and 2B schematically show two examples of finite automata 13a and 13b for decomposing an initial data stream 3 into a sequence of words coded 11.
• a finite automaton comprises a set of nodes or states 15 connected by paths or arrows 17 so that any word of a complete prefix code 5 can be defined by a set of paths 17 between an initial state noted / and a final state noted F.
• a bit is read, we follow the path 17 corresponding to the value of the bit and when we arrive in the final state F 1 we know that we have just finished reading a word of the prefix code complete 5 and we can reposition in the initial state / to read the next word.
• the method according to the invention comprises an association operation 20 associating the words of the coded word sequence 11 with the corresponding output words 7a according to the desynchronization function / in order to form the pseudo-random data sequence 1.
• the application of the mechanism of the present invention relates to the decomposition of an input sequence (i.e., the initial data stream 3) on the fly into a sequence 11 of code words. complete prefix 5. Whenever a word of the complete prefix code 5 is recognized, the image of this word by the desynchronization function / produces a word out. This mechanism is repeated until the last bit of the input stream of the initial data stream 3 is reached or when a user-determined stop condition is satisfied.
• the desynchronization function / is a parameterized function dependent on a predetermined parameter whose value can be modified during the generation of the pseudo-random data sequence 1.
• This parameterized function is then of the form v, x ⁇ > / v (x) which associates with any binary vector v of length m, that is to say, any element v of ⁇ , l ⁇ "', and any word x of the complete prefix C code 5 an element of l set of output words 7.
• the method according to the invention takes as input the initial data stream 3 and a binary vector v.
• the choice of this vector v may result from an operation (non-linear
• the vector v can take a predetermined value (for example, v is the null vector).
• vector v can be modified during the course of the process and thus depend on the generation of the pseudo-random data sequence 1.
• this parameter makes it possible to improve the complexity of the relationship between the initial data stream 3 and the pseudo-random data sequence 1, increasing the difficulty of predicting this pseudo-random data sequence 1.
• the code words of the complete prefix code 5 have a length limited by an upper bound h and such that if a any output word If is of the same length as another output word s 2 / then the number of antecedents by the desynchronization function / output word S 1 is the same as the number of antecedents by the same function / of the output word s ,? .
• the complete prefix code 5 includes the following advantageous properties:
• the words of the complete prefix code 5 have a length limited by a lower bound m and there exists a greater length / of words of said complete prefix code such that for any length k less than or equal to this upper length /, the complete prefix code contains 2 flM words of length k.
• the association function f v satisfies the following property: there is an integer
• the average rate is of the order V,.
• the probability that the code word that generated this bit is of length k and inversely proportional to k, and that regardless of the given bit (0 or 1). This choice of probability distribution is optimal with regard to the statistical properties that the pseudo-random data sequence 1 must satisfy.
• w ( « 0 , ..., w A _,) whose components belong to the set ⁇ 0,1 ⁇ .
• the initial data stream 3 bit by bit is read and for every word x of the code Q 1 the value f u (x) is calculated with the knowledge of the first bit of the word x and the value n ( for words of the form bb "b) or the fixed value h-1 (for words of the form
• f u (b, n) f u ⁇ b
• b b®u n with 0 ⁇ n ⁇ h ⁇ 2
• f ⁇ ag which is initialized with the value 0 and takes the value 1 only after the recognition of a word of the code Q. The flag value is reset after each word recognition, for each word recognition, the first bit of the current word is stored temporarily in the variable c and the word length is updated in the variable "lengtH" ⁇ The value of the output bit is stored in the s variable.
• this first embodiment comprises the repetition of the following mechanism:
• This embodiment is inexpensive to produce and can be advantageously used to implement encryption with hardware type electronic circuits.
• the average flow that is, say the ratio between the number of bits output (the number of bits of the pseudo-random data sequence 1) and the number of input bits (the number of bits of the initial data stream 3) is strictly greater than 1/3 .
• the guaranteed minimum number of bits output on an input of length h is 1.
• v (v o , ..., v 8 , v 9 ) whose components belong to the set ⁇ , l ⁇ , the values of the first eight components v o , ..., v 8 being invariant and the value of the last component v 9 being variable.
• the parameterized function f v C 2 ⁇ ⁇ u ⁇ , lf associates with any word of the form WiW 2 :
• this second embodiment comprises the repetition of the following mechanism:
• This second embodiment can be advantageously used for software-type encryption.
• the average bit rate that is the ratio between the number of bytes outputted and the number of bytes input is strictly greater than 1/3 and the guaranteed minimum number of bytes output on an input of length h bytes is 1.
• FIG. 3A illustrates a very schematic example of a generator 21 of a pseudo-random data sequence 1.
• the generator 21 comprises an initial production means 23 comprising at least one linear feedback shift register of maximum period generating the flow of data. initial data 3.
• T ⁇ - I
• a linear feedback shift register is a finite length bitmap (the register) with a linear combination represented by a polynomial called a feedback polynomial. At each offset, the highest index bit is output, all other bits are shifted by one index, and the lowest index bit takes the value of the linear combination before shifting.
• the generator 21 comprises a memory 25 and a processing unit 27.
• the memory 25 is intended to store a set of codewords forming a complete prefix code 5 and a set of output words 7.
• the processing unit 27 is intended to read and to decompose the initial data stream 3 into a sequence of words coded 11 according to the complete prefix code 5 and to associate the words of this sequence of words coded with the corresponding output words in accordance with to a desynchronization function / to generate the pseudo-random data sequence.
• the desynchronization function associates with any code word of the complete prefix code an output word of the set of output words 7. It should be noted that the decomposition and association operations 20 can be performed simultaneously by the processing unit 27.
• the processing unit 27 reads the initial data stream 3 bit by bit and whenever a word of the complete prefix code 5 is found, it calculates the image of this word by the desynchronization function 9.
• this generator is easy to implement and comprises decomposition means (memory 25 and processing unit 27) which break down the initial data input stream 3 in a unique manner and desynchronization means (memory 25 and storage unit). processing 27) for generating a pseudo-random data sequence having a minimum rate that does not depend on the particular properties of the initial data stream 3.
• FIG. 3B illustrates another example of a generator 21 of a pseudo-random data sequence 1 which differs from that of FIG. 3A in that it furthermore comprises a parameterization means 29.
• This parameterization means 29 is intended to make the desynchronization function f dependent on a predetermined parameter and to modify the value of this parameter during the generation of the pseudo-random data sequence 1.
• FIG. 4 shows a secure system 30 comprising at least two entities connected together via a communication network 35 of the Internet type, GSM, UMTS, WiFi, UltraWideBand, etc.
• the example of this figure shows a first entity 33a connected via the communication network 35 to a second entity 33b.
• the first entity 33a (respectively the second entity 33b) comprises a first terminal 37a (respectively a second terminal
• the modems 41a and 41b can be any device for interfacing with the communication network 35.
• Each of the first and second encryption / decryption devices 39a, 39b comprises a generator 21 of a pseudo-random data sequence 1 as previously described and an "exclusive-or" logic gate 43.
• Each encryption / decryption device 39a, 39b is intended to perform encryption or decryption afloat which consists of encrypting or decrypting a message bit by bit.
• the first encryption / decryption device 39a performs an encryption operation.
• the pseudo-random data sequence 1 called the ciphering sequence is combined by the exclusive-or-gate 43 with each corresponding position bit of a plaintext message 45 sent by the first terminal 37a to obtain a ciphertext 47 which is then sent by the first modem 41a to the second entity 33b.
• the encryption operation consists in adding bit by bit an encrypting sequence 1 to the clear text of the message
• the second encryption / decryption device 39b performs a decryption operation which consists in adding bit by bit this same encrypting sequence 1 to the encrypted text 47 sent by the first entity 33a to reform the message to the plaintext 45.
• a decryption operation which consists in adding bit by bit this same encrypting sequence 1 to the encrypted text 47 sent by the first entity 33a to reform the message to the plaintext 45.

Landscapes

• Engineering & Computer Science (AREA)
• Computer Security & Cryptography (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Compression, Expansion, Code Conversion, And Decoders (AREA)
• Mobile Radio Communication Systems (AREA)
• Communication Control (AREA)
• Data Exchanges In Wide-Area Networks (AREA)

Applications Claiming Priority (2)

Publications (1)

Family

ID=35241190

Family Applications (1)

Country Status (6)

Families Citing this family (2)

Family Cites Families (2)

• 2006
  • 2006-05-23 CN CN 200680023071 patent/CN101208902A/zh active Pending
  • 2006-05-23 EP EP06794454A patent/EP1886436A2/fr not_active Withdrawn
  • 2006-05-23 BR BRPI0610323A patent/BRPI0610323A2/pt not_active IP Right Cessation
  • 2006-05-23 WO PCT/FR2006/050472 patent/WO2007000549A2/fr not_active Ceased
  • 2006-05-23 KR KR1020077029543A patent/KR20080019631A/ko not_active Withdrawn
  • 2006-05-23 JP JP2008512889A patent/JP2008542805A/ja active Pending

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events