Abstract:
A generator for generating ciphering sequences, including plural clocked subgenerators (Γ, ψ, Ψ) which, in turn, generate binary sequences at one or several outputs. To achieve high cryptographic security of the ciphering sequence (ω t ) generated by the generator, n+1, at least three subgenerator are used in an arrangement in which the clock of n of these subgenerators (ψ, Ψ) is controlled in each case by at least one of the outputs of the (n+1)th subgenerator (Γ) either directly or via function generators (Δf(t), Δf (t)) wherein the sequences (μf(t), μ f(t)) generated by the n sub generators are logically combined by at least one function, which function assumes both binary states with approximately the same frequency when its arguments pass through all possible values.

Description:
BACKGROUND OF THE INVENTION 
     Field of the Invention 
     This invention relates to a generator for generating binary ciphering sequences, such as is used, in particular, for coding binary-coded speech and binary messages and data. 
     DISCUSSION OF BACKGROUND 
     Binary sequences are frequently coded by mixing them with a &#34;pseudo-random&#34; ciphering sequence. By definition, these are generated by finite deterministic generators and are thus of necessity periodic. The generators themselves are designed in such a manner that some settings are freely selectable and can be used as a key. Current usage is that this key is the only secret element in such a generator. It is correspondingly desirable that different keys result in greatly differing ciphering sequences. 
     In the so-called &#34;stream ciphering&#34;, a corresponding element of a binary ciphering sequence is modulo 2  added to each element of a binary sequence. In this simple method, it must be expected that the ciphering sequence generated with a given key is accessible to anybody. For this reason, it is essential that the law of formation of the sequence cannot be easily guessed. If the statistics of the ciphering sequence are not balanced, a part of the sequence carrying the message can also be reconstructed by statistical analyses. For this reason, the statistics of the ciphering sequence must be balanced, that is to say the statistics of the ciphering sequence must not differ significantly from a sequence produced by the ideal flipping of a coin. 
     A generator of the type initially mentioned was investigated in the following publications: W. G. Chambers and S. M. Jennings, &#34;Linear equivalence of certain BRM shiftregister sequences&#34;, Electronics Letters, vol. 20, pp. 1018-1019, November 1984. K. Kjeldsen and E. Andresen, &#34;Some randomness properties of cascaded sequences&#34;, IEEE Trans. Inform. Theory, vol. IT-26, pp. 227-232, March 1980. B. Smeets, &#34;On the autocorrelation function of some sequences generated by clock controlled shift registers&#34;, Proceedings of the Second Joint Swedish-Soviet Intern. Workshop on Inform. Theory, pp, 130-136 (1985). R. Vogel, &#34;Ueber die lineare Komplexitat von kaskadenformig verbundenen Folgen&#34; (On the linear complexity of cascaded sequences), Preprint, March 1984. 
     In the text which follows, some variables are introduced which are important for the assessment of the generator characteristics. Together with the necessary conditions obtained for these variables, these are: 
     (1) Period: By period T(ω) of a sequence ω, the minimum period of this sequence is meant, that is to say the smallest number T, so that 
     
         ω.sub.t+T =ω.sub.t 
    
     
         VtεZ.sup.+. 
    
     Condition: The period of a ciphering sequence must be long. 
     (2) Linear complexity: The linear complexity L(ω) of a sequence ω is the length of the shortest linear feedback-type shift register which generates the sequence ω. 
     Comment: Knowledge of the sequence at 2L(ω) successive times allows it to be completely determined by applying the so-called Massey algorithm. 
     Condition: The linear complexity of a ciphering sequence must be long. 
     (3) Frequency of short-length configurations: (Poker Test) 
     The frequency γ l  (ω,{σ i  }) of the configuration {σ i  } o   l-1  of the length l in ω is defined: 
     
         γ.sub.l (ω,{σ.sub.i }): ={tε{0, . . . ,T(ω)-1}|ω.sub.t+i =σ.sub.i,iε{0, . . . ,l-1}} 
    
     Comment: The following holds true for a periodically contined sequence of statistically independent equally-distributed random variables: ##EQU1## 
     In general, this cannot hold true for a ciphering sequence, for example only a single configuration of length T occurs apart from cyclic interchanges. For such a sequence, however, the statement can still hold true for l≦l* where l* is of the order of magnitude of log 2  T. With this restriction, indeed, it must hold true since statistical analyses otherwise become possible. 
     Condition: For a ciphering sequence ω, the following must hold true with a &#34;sufficiently long&#34; l*(ω): ##EQU2## 
     (4) 2-point autocorrelations: 
     The 2-point autocorrelation C.sub.ω (τ) of the sequence ω are defined by: ##EQU3## 
     They supply a measure of the degree of correspondence of a sequence with its cyclic permutations. 
     Condition: If τ is restricted to 0, . . . ,T-1 the following must hold true for a ciphering sequence ω of period T for almost all τ: 
     
         |C.sub.ω (τ)-δ.sub.τo |&lt;&lt;1 
    
     (5) 2-point cross-correlations between two sequences ω.sup.(1) and ω.sup.(2), which were generated with two different keys S.sup.(1) and S.sup.(2) : 
     These variables are defined by ##EQU4## 
     They form a measure of the key-dependence of the sequences generated. 
     Condition: If ω.sup.(1) and ω.sup.(2) are two ciphering sequences which were generated by a given generator with different keysetting S.sup.(1) and S.sup.(2), the following must hold true for almost all τε{0, . . . ,T-1}: 
     
         |K.sub.ω.spsb.(1).sub.,ω.spsb.(2) (τ)|&lt;&lt;1 
    
     In the known generator, the conditions mentioned at (1) and (2) are satisfied. In addition, the variables defined at (3) and (4) can be calculated in the known generator but the associated conditions are not satisfied. 
     SUMMARY OF THE INVENTION 
     Accordingly, one object of this invention is to provide a novel generator of the type initially mentioned in which not only the variables defined at (1) to (5) can be calculated but also all of the their associated conditions are satisfied. 
     The advantages achieved by the invention can be essentially seen in that, apart from the fact that the generator according to the invention has excellent characteristics in the sense of the conditions mentioned at (1) to (5), it can also be implemented by extremely simple means. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete appreciation of the invention and many of the attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein: 
     FIG. 1 is a schematic diagram of a generator which is constructed by using three subgenerators and 
     FIG. 2 is a schematic diagram a generator which is obtained by generalizing the generator according to FIG. 1. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring now to the drawings, wherein like reference numerals designate identical or corresponding parts throughout the several views, and more particular to FIG. 1 thereof, the symbols Γ, ψ, and ψ in FIG. 1 designate three part-generators which are diagrammatically shown as dashed triangles and which generate binary sequences κ, μ and μ having a period of k, M and M. 
     The three subgenerators Γ, ψ and Ψ can be implemented for example, as shown in FIG. 1 within the dashed triangles, by linear feedback-type shift registers with a maximum period of K=2 k-1 , M=2 m-1  and M=2 m-1  and a length of k, m and m. In a linear feedback-type shift register, a part or all bits of the shift registers, added to each other, for example, modulo 2, are fed back to its input. 
     The subgenerators Γ, ψ and ψ must be clocked and for this purpose have clock inputs c in each case. The subgenerators Γ obtains its clock from an external clock generator, not shown in FIG. 1. The clocks of the two remaining subgenerators ψ and ψ are derived from outputs of the subgenerators Γ via funcction generators Δf(t) and Δf(t). At these outputs, it should be possible to pick up the sequence κ in each case, in a different time position (phase) at each output. With a length K of the period of the sequence κ, K of such different time positions κ t  . . . κ t  -(K-1) are basically possible. If the part generator Γ is implemented as a linear feedback-type shift register, these K time positions can be implemented by suitable linear combination of only k successive outputs of the shift register. Correspondingly, only k outputs of the subgenerator Γ are drawn in FIG. 1. 
     Sequences μ and μ can also be generated by the subgenerators ψ and Ψ to have different time positions. Corresponding to their period length, M and M of such time positions μ f (t), . . . , μ f (t)-(M-1) and μ f (t), . . . , μ f (t)-(MM-1) are possible. If the subgenerators ψ and Ψ are implemented as linear feedback-type shift registers, the M and M different time positions can again be implemented by suitable linear combinations of only m and m successive outputs of the shift registers. For this reason, only m and m of such outputs are drawn in FIG. 1. 
     The functions f and f are defined by ##EQU5## 
     The sequences available at the outputs of power generators ψ and Ψ are logically combined, not necessarily all of them, via at least one logical combining unit χ to form the ciphering sequence ω t  which, under certain circumstances, should be available also at different time positions ω t , . . . ,ω t  -(T-1). 
     The combination of the elements described, that is the three subgenerators Γ, ψ and Ψ the two function generators Δ f(t) and Δf(t) and the logical combining unit χ forms a generator according to the invention. 
     As shown in FIG. 1 within the rectangles representing the function generators Δf(t) and Δf(t), the sequence κ, for example, can be forwarded by the function generator Δf(t) to the clock input c of the part generator ψ only at time position t whilst, for example, the complement of sequence κ can be added by the function generator Δf(t) at time position t and modulo 2 to the product of sequence κ at all time positions, that is to say can be carried modulo 2 added to subgenerator κ t  -(K-1) . . . κ t  -1κ t  to clock input c of the subgenerator ψ. The logical combining unit χ can cause specific time positions of the sequences μ and μ generated by  the subgenerators ψ and Ψ to be modulo 2 added which is also illustrated, for example, for the μ f (t), . . . , μ f (t)-(m-1) in FIG. 1 within the rectangle forming the logical combining unit χ. 
     Having the aforementioned special embodiments of the subgenerators Γ, ψ and Ψ of the function generators Δf(t) and Δf(t) and of the logical combining unit χ, the generator according to the invention displays the characteristics, explained below, with respect to the variables and conditions initially defined at (1) to (5): 
     Let: ##EQU6## (Φ and Φ are keys which determine the phase between the part generators Γ and ψ in the one hand, and Γ and Ψ on the other hand), then ##EQU7## 
     defines the ciphering sequence for key S=(Φ, Φ). 
     In the case described above, that is to say if Γ, ψ, Ψ are linear feedback-type shift registers, the definition equations (I) and (II) for ##EQU8## will result in the value ##EQU9## which, in particular, also implies that ##EQU10## do not have a common divisor. If M and M also do not have a common divisor and furthermore M is divided by K and M is greater than K, the following holds for all keys S: 
     1. For the period 
     
         T(ω.sup.S)=K·M·M 
    
     2. For the linear complexity: 
     
         L(ω.sup.S)≧m·K 
    
     3a. For the relative frequency of &#34;1&#34;: 
     
         ω.sup.S =1/2(1-1/MM) 
    
     3b. For the relative frequency of configurations having a length l≦min (k,m,m): ##EQU11## 
     Here, as also below, 0(. . . ) is to be interpreted in such a manner that 
     X=0 (1/N) means that X N tends towards a constant in the limit N→∞ 
     4. For the 2-point autocorrelations: {ρ.sub.σ,i S  }σε{0 . . . MM-1},i ε{0,1}, so that the following holds true for all ##EQU12## 
     5. For the 2-point cross-correlations between two sequences which are generated with two different keys S.sup.(1) and S.sup.(2) : ##EQU13## With these results, which guarantee excellent characteristics within the meaning of (1) to (5) for realistic selections of the parameters (for example k=m=127, m=255), together with the extremely simple implementation, the structure described is predestined for cryptographic applications. 
     The subgenerators Γ, ψ and Ψ of FIG. 1 may not necessarily be implemented by linear feedback-type shift registers. Any other types of implementations are also possible. As a subgenerator, a generator of the type described can also be used itself in the sense of being cascaded. 
     If κ, μ, μ are sequences having periods K, M, M which are generated by 3 arbitrary subgenerators Γ, ψ, Ψ, Δf and Δf are functions of κ and t which are K-periodic in t, and the sequence generated by the composite generator is given by ##EQU14## characteristics corresponding to (1) to (5) can be proven using (M, M)=(M, F)=(M,F)=1 and specific other compatible assumptions. 
     A generalization of the generator hitherto described and shown in FIG. 1 is also obtained by logically combining, instead of three arbitrary subgenerators, n+1 arbitrary subgenerators in a corresponding manner as shown in FIG. 2. That is to say, if κ, μ.sup.(1), . . . ,μ.sup.(n) are sequences of periods K, M.sup.(1), . . . ,M.sup.(n) which are generated by n+1 arbitrary part generators Γ, ψ.sup.(1), . . . ψ.sup.(n) and if Δf.sup.(1), . . . Δf.sup.(n) are arbitrary K-periodic functions of κ and t, the sequence generated by the composite generator is given by ##EQU15## 
     Finally, the sequences ψ, Ψ or ψ.sup.(1), . . . ψ.sup.(n) generated by the subgenerators μ and μ or μ.sup.(1), . . . μ.sup.(n) can be logically combined, instead of modulo-2 as assumed above by way of example, also by another function to form the ciphering sequence ω t  in the example of FIG. 1 and in the example of FIG. 2: ##EQU16## where χ is an arbitrary function which has itself been designated by using the same symbol as that of the logical combining unit itself. 
     This function has to satisfy the following relation ##EQU17## that is to say assume both binary states with the same frequency when its arguments pass through all possible values. 
     Obviously, numerous modifications and variations of the present invention are possible in light of the above teachings. It is therefore to be understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described herein. 
     
         ______________________________________List of designations______________________________________Γ, ψ, Ψ           Part generatorsc               Clock inputsΔf(t), Δf(t)           Function generatorsκ.sub.t, . . . , κ.sub.t-(k-1)           Sequence generated by part           generator Γ at K different time           positionsμ.sub.f(t), . . . , μ.sub.f(t)-(m-1)           Sequence generated by part           generator at m different time           positionsμ.sub.t(t), . . . , μ.sub.f(t)-(m-1)           Sequence generated by part           generator at m different time           positionsχ           Logical combining unitω.sub.t, . . . , ω.sub.t-(T-1)           Ciphering sequence at T           different time positionsψ.sup.(1), . . . , ψ.sup.(n)           Part generatorsΔf.sup.(1) (t), . . . , Δf.sup.(n) (t)           Function generatorsκ.sub.t, . . . , κ.sub.t-(K-1)           Sequence generated by part           generator Γ at K different time           positions ##STR1##       Sequences generated by part  generators ψ.sup.(1) , .           . . , ψ.sup.(n) at M.sup.(1) . . . , M.sup.(n)           different time positions respectively.______________________________________