Abstract:
This invention discloses a method and an apparatus for processing stream encryption/decryption and more particularly to a diffusion operation of a matrix of at least one dimension including a displacement and an exclusion or (XOR), so that a plurality of diffused starting positions is converted into a diffused function operation for quickly and continuously performing an XOR operation with a plaintext (or ciphertext) stream to generate a ciphertext (or plaintext) stream.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to a method and an apparatus for processing stream encryption/decryption by a diffusion mechanism, and more particularly to a diffusion operation for a matrix of at least one dimension including a displacement and an exclusion or (XOR), so that a plurality of diffused starting positions is converted into a diffused function operation for quickly and continuously performing an XOR operation with a plaintext (or ciphertext) stream to generate a ciphertext (or plaintext) stream.  
         [0003]     2. Description of the Related Art  
         [0004]     Prior art stream encryption/decryption method and apparatus use a random code generator to output a numeric value to a register, and the bits in the register are taken out constantly to perform an XOR with a plaintext stream to generate a ciphertext stream by the operations of linear or non-linear combination function and the shifts of register. Similar process is applied to the ciphertext to obtain the plaintext stream. The key point of safety of the prior art emphasizes on the linear complexity of a combination function so as to produce a large non-correlation with the bitstream taken out from the register and reduce the risk of breaking the combination function.  
       SUMMARY OF THE INVENTION  
       [0005]     To overcome the issue of stream correlation produced by the prior art, the present invention uses an operation of a diffusion mechanism to represent a position by a linear function, and all position combinations are represented by a diffusion function, so that the maximum recurring period and linear complexity are reflected in the diffusion function to replace the prior art non-linear combination function and random code generator.  
         [0006]     The technical measures taken to overcome the foregoing problem by the present invention are described as follows:  
         [0007]     A diffusion mechanism that needs to repeat the diffused operations of a plurality of diffused starting positions has a fast operating speed in that the hardware design of the diffusion function can simultaneously complete the operations at a time. The diffusing mechanism also has a maximum recurring period and linear complexity for controlling the plurality of diffused starting positions, and the diffusion mechanism comprises the following steps:  
         [0008]     (a) Select a diffused area of at least one dimension.  
         [0009]     (b) The diffused area includes a plurality of diffused starting positions and at least one output position.  
         [0010]     (c) The diffused starting position includes a starting position and an ending position.  
         [0011]     (d) Output a trigger signal, and the trigger signal ∈ {0,1}.  
         [0012]     (e) Execute a diffused operation of at least one dimension sequentially from the starting position to the ending position, and this step is carried out for at least one time; and  
         [0013]     (f) The output position outputs a bit.  
         [0014]     The effects of the present invention are compared with those of the prior art as follows. In prior art stream encryption/decryption method and apparatus, the internal random code generator controls the random codes to produce a maximum recurring period, and the internal non-linear combination function controls each segment of the output streams to produce a minimum correlation. However, if the non-linear combination function is broken, the stream cipher/decipher will become useless.  
         [0015]     In the stream encryption/decryption method and apparatus of the present invention, the diffusion function determines the correlation between the maximum recurring period and the output stream. Unlike the non-linear combination function, the diffusion function is opened to the public, and thus even if the content of the internal register is broken, the present invention can be used again by resetting the content of the register.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]      FIG. 1  is a schematic view of the hardware layer of a diffusion mechanism according to the present invention; and  
         [0017]      FIG. 2  is a schematic view of the hardware layer of a diffusion module according to the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0018]     The stream encryption/decryption method and apparatus of the present invention uses a diffused operation to form a diffusion mechanism, and at least one combination of the diffusion mechanism forms a diffusion module that comprises:  
         [0019]     A diffused operation, for returning the value of the diffused area to the original value for every period of diffusions, as to the recurring period of diffusion. Therefore, there are two types of diffusion operations: a diffusion operation at a state after diffusion from the start to the end of a cycle, or a diffused operation at a state before diffusion from the end to the start of the diffusion.  
         [0020]     The state after diffusion includes a diffused area, and the diffused area includes a diffused starting position, and an XOR operation is performed for the new value of the diffused starting position with a trigger signal, and the starting position is used as the diffusion center, and the diffusion direction is from the inside to the outside sequentially. The new value produced in the diffused area is an original value performing an XOR operation with the new value at an internal adjacent position until the entire diffused area is completed.  
         [0021]     The state before diffusion includes a diffused area, and the diffused area includes a diffused starting position, and the starting position is used as the diffusion center, and the diffusion direction is from the outside to the inside sequentially. The new value produced in the diffused area is an original value performing an XOR operation with the original value at the internal adjacent position until the entire diffused area is completed, and the new value of the diffused starting position is obtained by performing an XOR operation for the original value with the trigger signal.  
         [0022]     Symbols and Definition of Diffusion:  
         [0023]     S is a diffused area with a m-dimensional matrix comprising a combination of n positions, m&gt;0; n&gt;0, and the position label is shown below:  
         [0024]     For example, (a) one-dimensional S  
                                                       1   2   3   . . .   n-1   n                  
 
         [0025]     (b) Two-dimensional S  
                                               1   5   .   n-3       2   6   .   n-2       3   7   .   n-1       4   8       n                  
 
         [0026]     S(i): S uses the position i as the diffused starting position to execute the diffused operation.  
           S   ⁡     (       i   1     ,     i   2     ,   Λ   ,     i   k       )         i   →   j       ⁢     :     ⁢   S       
 
 S uses {i 1 ,i 2 ,Λ,i k |1≦i k ≦n} sequentially as the diffused starting positions, and the set uses the position i as the starting position and the position j as the ending position to sequentially execute the diffused operation. 
 
         [0027]     For example,  
             S   ⁢       (     1   ⁢     :     ⁢   n     )       i   →     i   -   1         ⁢     :     ⁢   S           (   a   )             
 
 S uses the positions 1 to n sequentially as the diffused starting positions, and the position i is the starting position, and the position i−1 is the ending position to sequentially execute the diffused operation.  
                 S   ⁡     (     1   ⁢     :     ⁢   n     )         i   →   i       =       [       S   ⁡     (     1   ⁢     :     ⁢   n     )         i   →     i   -   1         ]     ⁢     (   i   )               (   b   )             
 
         [0028]     S t  is a diffusion mechanism for executing the operation of  
         S   ⁡     (       i   1     ,     i   2     ,   Λ   ,     i   k       )         i   →   j         
 
 for t times. 
 
         [0029]     For example, (a) S t =[S t−1 ] 1  (b) S 2 =[S 1 ] 1  (c) S 0 =S  
         [0030]     S t     1     xt     2    executes the operation of S t     2    for t 1  times.  
         [0031]     For example, (a) S t     1     xt     2   =[S (t     1     −1)xt     2   ] t     2    (b) S 2×2 =[S 1×2 ] 2 =S 4  (c) S 0×2 =S 0 =S  
         [0032]     F is a m+1 dimensional matrix f representing n positions of S.  
         [0033]     F t  is a diffusion function for executing the operation of S 1  for t times and the linear function combination of n positions.  
         [0034]     For example, (a) F t =[F t−1 ] 1  (b) F 2 =[F 1 ] 1  (c) F 0 =F  
         [0035]     S t     1   (F t     2   ) is an operation of S t     1    by F t     2   , and n positions produce a new value.  
         [0036]     For example, (a) S 2 =S 1 (F 1 ), (b) S 1 =S(F 1 ), (c) S=S(F), (d) S t =S t     1     xt     2   =S (t     i     −1)xt     2   (F t     2   )  
         [0037]     T is a m-dimensional zero matrix, indicating that the values of n positions have no inverse phase.  
         [0038]     T t  is a trigger area having a trigger signal of 1 for executing the operation of S 1  for t times, and the new value produces a position of a reverse phase.  
         [0039]     For example, (a) T t =T t−1 (F 1 )⊕T 1  (b) T 2 =T 1 (F 1 ) ⊕T 1  (c) T 0 =T (d) T t =T t     1     xt     2   =T (t     i     −1)xt     2   (F t     2   )⊕T t     2      
         [0040]     The embodiments of a diffusion module are described below.  
         [0041]     To make it easier for our examiner to understand the content of the present invention, the diffused operation, diffusion mechanism, diffusion function, trigger area, software design, and hardware design are described in details as follows:  
         [0042]     Set a one-dimensional diffused area S comprised of 4 positions labeled as 1, 2 , 3 and 4, and  
         S   1     =         S   ⁡     (     1   ⁢     :     ⁢   4     )         1   →   4       .         
 
         [0043]     The diffused operation uses 1 as the diffused starting position for the operation as shown in Table 1.  
                                             TABLE 1                       Diffused Stream               S   State After Diffusion   State Before Diffusion                                1   i.   1 = 1 ⊕ Tr   i.   4 = 4 ⊕ 3       2   ii.   2 = 2 ⊕ 1   ii.   3 = 3 ⊕ 2       3   iii.   3 = 3 ⊕ 2   iii.   2 = 2 ⊕ 1       4   iv.   4 = 4 ⊕ 3   iv.   1 = 1 ⊕ Tr                 Tr: trigger signal            ⊕: XOR             
 
         [0044]     Diffusion mechanism:  
           S   1     =       S   ⁡     (     1   ⁢     :     ⁢   4     )         1   →   4         ,       
 
         [0045]     and executes the diffused operation at the state before diffusion S 1 . The relation of an operation of a diffused starting position corresponding to a new value produced for each position is shown in Table 2.  
                               TABLE 2                       S   S = S(1)   S = S(2)   S = S(3)   S = S(4)                   1   1   2   1   1 ⊕ 2 ⊕ 3       2   1 ⊕ 2   1 ⊕ 2   2 ⊕ 3   1 ⊕ 2       3   2 ⊕ 3   1 ⊕ 3   1 ⊕ 3   2 ⊕ 4       4   3 ⊕ 4   2 ⊕ 4   1 ⊕ 2 ⊕ 3 ⊕ 4   1 ⊕ 2 ⊕ 3 ⊕ 4                 ⊕: XOR             
 
         [0046]     Diffusion Function: Take F 7 =F for example, the diffused operation at a state before diffusion is used. The diffusion function for six consecutive times is shown in Table 3.  
                                       TABLE 3                       S   F 1     F 2     F 3     F 4     F 5     F 6                     1   1 ⊕ 2 ⊕ 3   2 ⊕ 3 ⊕ 4   2 ⊕ 3   1 ⊕ 4   1   1 ⊕ 2 ⊕ 3 ⊕ 4       2   1 ⊕ 2   3   2 ⊕ 4   3 ⊕ 4   1 ⊕ 3   1 ⊕ 3 ⊕ 4       3   2 ⊕ 4   3 ⊕ 4   1 ⊕ 3   1 ⊕ 3 ⊕ 4   2   1 ⊕ 2       4   1 ⊕ 2 ⊕ 3 ⊕ 4   1   1 ⊕ 2 ⊕ 3   2 ⊕ 3 ⊕ 4   2 ⊕ 3   1 ⊕ 4                 ⊕: XOR             
 
         [0047]     Trigger Area: The trigger signal is 0, and the new value of each position as shown by the diffusion function. The trigger signal is 1, and  
         T   1     =       T   ⁡     (     1   ⁢     :     ⁢   4     )         1   →   4           
 
         [0048]     repeats executing the diffused operation at the state before diffusion. The new value has a reverse phase as shown in the position labeled as 1 in Table 4.  
                                           TABLE 4                       S   T 1     T 2     T 3     T 4     T 5     T 6     T 7                     1   1   1   1   0   0   1   0       2   0   1   0   1   1   1   0       3   1   0   0   0   1   1   0       4   1   0   1   1   1   0   0                  
 
         [0049]     Software Design of Diffusion Module:  
         [0050]     Embodiment I: 16×1 diffusion module of S 1×1 .  
         [0051]     A plaintext is one-dimensional zero matrix.  
         [0052]     A password is a 16-bit one-dimensional zero matrix.  
         [0053]     Initialization:  
         [0054]     1. The trigger signal is 1.  
         [0055]     2. The passwords are entered sequentially into the diffused area.  
         [0056]     3. The output position is the last bit of the diffused area.  
         [0057]     4. S 1×1 =S 1  outputs once for each operation.  
         5.   ⁢           ⁢     S             ⁢   1         =         S   ⁢     (     1   ⁢           :           ⁢   16     )         13   ⁢           →           ⁢   13       .         
 
         [0058]     Encryption Flow:  
         [0059]     1. Sequentially obtain a bit from the plaintext stream.  
         [0060]     2. The diffused area executes the operation of S 1 , and the diffused area produces a new value.  
         [0061]     3. Perform an XOR for the last bit in the diffused area with a bit of the plaintext stream.  
         [0062]     4. Repeat the foregoing steps until the plaintext is finished.  
         [0063]     Description: 
        S 0  [0000000000000000]    S 1  [1011001101100011]→Perform XOR for the last bit with a bit of the plaintext stream.     S 2  [0110100110110010]→Perform XOR for the last bit with a bit of the plaintext stream.     S 2     16     −1  [0000000000000000]→Equal to S 0 .     Results: (Take S 1  to S 64 )     1011011100111011 (S 1  to S 16 )     0000100100010111 (S 17  to S 32 )     0100000011010100 (S 33  to S 48 )     1011011111111110 (S 49  to S 64 )        
 
         [0073]     Embodiment II: 16×1 diffusion module of S 1×2 .  
         [0074]     A plaintext is a one-dimensional zero matrix.  
         [0075]     A password is a 16-bit one-dimensional matrix.  
         [0076]     Initialization:  
         [0077]     1. The trigger signal is 1.  
         [0078]     2. Enter the passwords sequentially into the diffused area.  
         [0079]     3. The output position is the last bit of the diffused area.  
         [0080]     4. S 1×2 =S 2 =[S 1 ] 1 , and output once for every two operations.  
         5.   ⁢           ⁢     S             ⁢   1         =         S   ⁢     (     1   ⁢           :           ⁢   16     )         13   ⁢           →           ⁢   13       .         
 
         [0081]     Encryption Flow:  
         [0082]     1. Take a bit sequentially from the plaintext stream.  
         [0083]     2. The diffused area executes the operation of S 2 , and the diffused area produces a new value.  
         [0084]     3. Perform XOR for the last bit of the diffused area with a bit of the plaintext stream.  
         [0085]     4. Repeat the foregoing steps until the plaintext is finished.  
         [0086]     Description: 
        S 0  [0000000000000000]    S 1×2  [0110100110110010]→Perform XOR for the last bit with a bit of the plaintext stream.     S 2×2  [1001111000110101]→Perform XOR for the last bit with a bit of the plaintext stream.     S (2     16     −1 )× 2  [0000000000000000]→Equal to S 0       Results: (Take S 1×2  to S 64×2 )     0111010100010111 (S 1×2 to S 16×2 )     1000111001111110 (S 17×2  to S 32×2 )     1000010100011110 (S 33×2  to S 48×2 )     1101011100000100 (S 49×2  to S 64×2 )        
 
         [0096]     Embodiment III is a 4×4 diffusion module of S 1×1 .  
         [0097]     A plaintext is a one-dimensional zero matrix.  
         [0098]     A password is a 16-bit two-dimensional zero matrix.  
         [0099]     The initialization and encryption flow are the same as those described in Embodiment I, but the diffusion mechanism is changed to  
         S   1     =         S   ⁡     (     1   ⁢     :     ⁢   16     )         8   →   8       .         
 
         [0100]     Description: 
        S 0  [0000000000000000]    S 1  [1010001000100100]→Perform XOR for the last bit with a bit of the plaintext stream.     S 2  [1100000110010011 ]→Perform XOR for the last bit with a bit of the plaintext stream.     S 2     16     −2  [0000000000000000]→Equal to S 0 .        
 
         [0105]     Results: (Take S 1  to S 64 ) 
        0111000100100111 (S 1  to S 16 )     0000001100101011 (S 17  to S 32 )     1110101001111110 (S 33  to S 48 )     0011000001101100 (S 49  to S 64 )        
 
         [0110]     Hardware Design of Diffusion Module:  
         [0111]     The operations of the S t     1     xt     2    diffusion mechanism used for a software design are the operations of the F t     2    diffusion function and the reverse phase of the T t     2   , which are converted into a hardware design, and the synchronous operation of the hardware design obviously can reduce the time of forming streams as shown in  FIG. 1 .  
         [0112]     Embodiment I: a 16×1 diffusion module of S 1×2 .  
         S     1   ×   2       =       S   2     =       [       S   ⁡     (     1   ⁢     :     ⁢   16     )         13   →   13       ]     1           
 
         [0113]     is converted into F t     2   =F 2  and the linear function at each position is shown in Table 5.  
                   TABLE 5                            f(1)   1 ⊕ 3 ⊕ 5 ⊕ 7 ⊕ 9 ⊕ 13        f(2)   1 ⊕ 2 ⊕ 4 ⊕ 6 ⊕ 7 ⊕ 8 ⊕ 9 ⊕ 10 ⊕ 11 ⊕ 13 ⊕ 14 ⊕ 15        f(3)   1 ⊕ 9        f(4)   1 ⊕ 2 ⊕ 10 ⊕ 13        f(5)   3 ⊕ 5 ⊕ 11 ⊕ 14 ⊕ 15        f(6)   1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 9 ⊕ 12 ⊕ 14        f(7)   9 ⊕ 13        f(8)   1 ⊕ 2 ⊕ 5 ⊕ 10 ⊕ 15        f(9)   2 ⊕ 9 ⊕ 11 ⊕ 13       f(10)   1 ⊕ 2 ⊕ 7 ⊕ 10 ⊕ 12 ⊕ 14       f(11)   1 ⊕ 2 ⊕ 5 ⊕ 9 ⊕ 13 ⊕ 15       f(12)   1 ⊕ 3 ⊕ 5 ⊕ 6 ⊕ 9 ⊕ 10 ⊕ 13 ⊕ 14 ⊕ 15 ⊕ 16       f(13)   3 ⊕ 7 ⊕ 9 ⊕ 11 ⊕ 13 ⊕ 14 ⊕ 15 ⊕ 16       f(14)   1 ⊕ 3 ⊕ 5 ⊕ 7 ⊕ 8 ⊕ 9 ⊕ 10 ⊕ 11 ⊕ 12 ⊕ 15 ⊕ 16       f(15)   3 ⊕ 4 ⊕ 7 ⊕ 8 ⊕ 9 ⊕ 10 ⊕ 11 ⊕ 12       f(16)   2 ⊕ 5 ⊕ 6 ⊕ 8 ⊕ 9 ⊕ 10 ⊕ 11 ⊕ 12 ⊕ 13 ⊕ 15 ⊕ 16                  
        T t     2   =T 2 : 0110100110110010        
 
         [0115]     Operation Flow:
 
in=1 T   t     1     ×2   =T   (t     1     −1)×2 ( F   2 )⊕T 2   , S   t     1     ×2   =S   (t     1−1)×2   ( F   2 ) ⊕T   t     1     ×2 
 
in=0 : S   t     1     ×2   =S   (t     1     −1)×2 ( F   2 )
 
         [0116]     Embodiment II: a 16×1 diffusion module of S 1×1 .  
         S     1   ×   1       =       S   1     =       S   ⁡     (     1   ⁢     :     ⁢   16     )         13   →   13             
 
         [0117]     is converted into F t     2   =F 1 , and the linear function of each position is shown in Table 6.  
                   TABLE 6                            f(1)   1 ⊕ 7 ⊕ 9 ⊕ 11        f(2)   1 ⊕ 2 ⊕ 5 ⊕ 8 ⊕ 10 ⊕ 12        f(3)   5 ⊕ 7 ⊕ 9 ⊕ 11        f(4)   1 ⊕ 3 ⊕ 6 ⊕ 7 ⊕ 8 ⊕ 10 ⊕ 12 ⊕ 13        f(5)   1 ⊕ 3 ⊕ 5 ⊕ 9 ⊕ 11 ⊕ 13        f(6)   2 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 10 ⊕ 12 ⊕ 13        f(7)   1 ⊕ 3 ⊕ 9 ⊕ 11        f(8)   1 ⊕ 2 ⊕ 4 ⊕ 7 ⊕ 9 ⊕ 10 ⊕ 12 ⊕ 13 ⊕ 14        f(9)   3 ⊕ 7 ⊕ 11 ⊕ 13 ⊕ 14       f(10)   1 ⊕ 4 ⊕ 5 ⊕ 8 ⊕ 9 ⊕ 12 ⊕ 14       f(11)   1 ⊕ 3 ⊕ 5 ⊕ 7 ⊕ 9 ⊕ 11 ⊕ 14       f(12)   2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 7 ⊕ 8 ⊕ 9 ⊕ 10 ⊕ 11 ⊕           12 ⊕ 13 ⊕ 14 ⊕ 15       f(13)   1 ⊕ 14 ⊕ 15       f(14)   1 ⊕ 2 ⊕ 13 ⊕ 15       f(15)   2 ⊕ 3 ⊕ 14 ⊕ 16       f(16)   3 ⊕ 4 ⊕ 13 ⊕ 15                  
        T t     2   =T 1 : 1011001101100011        
 
         [0119]     Operation Flow:
 
in=1 : T   t     −1     =T   t     −1   (F 1 ) ⊕T   1   , S   t   =S   t−1 ( F   1 ) ⊕T   t 
 
in=0 : S   t   =S   t−1 ( F   1 )
 
         [0120]     Embodiment III: a diffusion module of S 1×t     2    combination is shown in  FIG. 2 .  
         A   ⁢           ⁢   4   ×   4     ,         S     1   ×   1       ⁢     :     ⁢           ⁢     S   1       =           S   ⁡     (   8   )         8   →   8       .     
     ⁢   A     ⁢           ⁢   16   ×   1       ,         S     1   ×   1       ⁢     :     ⁢           ⁢     S   1       =           S   ⁡     (   13   )         13   →   13       .     
     ⁢   A     ⁢           ⁢   16   ×   1       ,         S     1   ×   2       ⁢     :     ⁢           ⁢     S   2       =         [       S   ⁡     (   13   )         13   →   13       ]     1     .           
 
         [0121]     Operation Flow:  
         [0122]     A pulse controller controls the execution of three diffusion mechanisms by the pulse, and outputs a result of performing an XOR operation for a bit with a bit of the plaintext (or ciphertext) for the completed execution of every three diffusion mechanisms, and the diffusion module is executed repeatedly to produce a ciphertext (or plaintext) stream.  
         [0123]     In the embodiments, the diffusion function can be used independently or expanded simply to one or more combinations, and the operation of the diffusion function is used to output the number of executions at the first bit, which can hardly compute the correlation. Furthermore, the value of a trigger area in each diffusion function for different combinations of the diffusion function cannot be known. Thus, the output value of the next bit cannot be found. In  FIG. 2 , a password is inputted from the “in end-point” into an internal register indirectly by the trigger signal method. Even if the content of the register can be guessed, the original password cannot be found, and the cipher still cannot be used. If a force breaking method is used, it is necessary to take 2 n+1  trials for an n-bit password.  
         [0124]     While the invention has been described by means of specific embodiments, numerous modifications and variations could be made thereto by those skilled in the art without departing from the scope and spirit of the invention set forth in the claims.