Abstract:
The invention relates to a method of determining a plaintext M on the basis of a cipher C and using a secret key d, wherein the secret key d is used in binary form, wherein the plaintext M is determined in each iteration step i for the corresponding bit d i  and a security variable M n  is determined in parallel therewith, and then a verification variable x is determined by means of a bit-compatible exponent of the secret key d.

Description:
FIELD OF THE INVENTION 
       [0001]    The invention relates to a method for determining a plaintext on the basis of a cipher. 
       BACKGROUND OF THE INVENTION 
       [0002]    Such methods are known for example by the RSA method. In the RSA method, a plaintext is encrypted by means of a public key, wherein this cipher can be decrypted again by means of an associated secret key. Since the encrypted data are usually highly confidential and nevertheless are publicly accessible, the data are more and more frequently being exposed to attacks in order to spy out the secret key so that the encrypted data can be decrypted and thus undesirably determined in order to misuse the decrypted data. 
         [0003]    Such attacks have become known as timing attacks or differential fault analysis (DFA) attacks, in which the computation time or running time of a calculation or a fault behavior during manipulations is observed in order to determine the secret key that is used during such processes. 
         [0004]    Therefore, methods have been created which, using considerable computational effort through an inverse RSA function or a second RSA calculation, attempt to ascertain such manipulations and make them ineffective. 
       OBJECT AND SUMMARY OF THE INVENTION 
       [0005]    The object of the invention is to provide a method for determining a plaintext on the basis of a cipher, which is not susceptible to timing attacks and differential fault analysis attacks and nevertheless is associated with a relatively low amount of additional effort. 
         [0006]    This is achieved according to the invention by a method of determining a plaintext M on the basis of a cipher C and using a secret key d, wherein the secret key d is used in binary form, wherein the plaintext M is determined in each iteration step i for the corresponding bit d i  of the secret key and a security variable M n  is determined in parallel therewith, and then a verification variable x is determined by means of a bit-compatible exponent of the secret key d. 
         [0007]    Advantageous further developments are described in the dependent claims. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The invention will be further described with reference to an example of embodiment shown in the drawings to which, however, the invention is not restricted. 
           [0009]      FIG. 1  shows a schematic illustration of the RSA method. 
           [0010]      FIG. 2  shows a block diagram of the RSA method. 
           [0011]      FIG. 3  shows an illustration of a timing attack. 
           [0012]      FIG. 4  shows a block diagram of the “always multiplication and squaring” method. 
           [0013]      FIG. 5  shows a block diagram of the verification method according to the invention. 
           [0014]      FIG. 6  shows a block diagram of the verification method according to the invention. 
           [0015]      FIG. 7  shows block diagram of the verification method according to the invention. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0016]    Encryption and decryption methods are very widespread today, since confidential information is used very frequently and is also transmitted in a publicly accessible manner. An implementation of such an encryption and the associated decryption according to the prior art will be described below with reference to the so-called RSA method according to Rivest, Shamir and Adleman. In the RSA method, firstly a plaintext M is encrypted using a public key g to form a cipher C, that is to say a secret text. This encrypted cipher C can then also be made public or transmitted, since the cipher C cannot be decrypted without the secret key d. The calculation of the plaintext M is carried out by a modular exponentiation (mod N) of the cipher C using the secret key d.  FIG. 1  shows a schematic diagram  1  in order to illustrate the decryption according to the RSA method of M=C d  mod N. For this,  FIG. 1  shows a block  2  which represents the RSA decryption. The input variables used are the cipher C and the secret key d, so that the plaintext M is obtained as the result. 
         [0017]    The implementation of this equation generally takes place by means of the so-called “multiplication and squaring” algorithm. Here, the key d is used in its binary form with the length L: 
         [0000]    
       
         
           
             
               
                 
                   d 
                   = 
                     
                    
                   
                     
                       d 
                       0 
                     
                     + 
                     
                       2 
                        
                       
                         d 
                         1 
                       
                     
                     + 
                     
                       4 
                        
                       
                         d 
                         2 
                       
                     
                     + 
                     
                       … 
                        
                       
                           
                       
                        
                       
                         2 
                         
                           L 
                           - 
                           1 
                         
                       
                        
                       
                         d 
                         
                           L 
                           - 
                           1 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         L 
                         - 
                         1 
                       
                     
                      
                     
                       
                         2 
                         i 
                       
                       · 
                       
                         d 
                         i 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               d 
               i 
             
             ∈ 
             
               { 
               
                 0 
                 , 
                 1 
               
               } 
             
           
         
       
     
         [0000]    If this form is used, the result is a product chain as follows: 
         [0000]    
       
         
           
             M 
             = 
             
               
                 
                   C 
                   
                     d 
                     0 
                   
                 
                 · 
                 
                   C 
                   
                     2 
                      
                     
                       d 
                       1 
                     
                   
                 
                 · 
                 
                   C 
                   
                     4 
                      
                     
                       d 
                       1 
                     
                   
                 
                 · 
                 
                   C 
                   
                     
                       8 
                        
                       
                         d 
                         1 
                       
                     
                      
                     
                         
                     
                   
                 
               
                
               
                 … 
                 · 
                 
                   C 
                   
                     
                       2 
                       
                         L 
                         - 
                         1 
                       
                     
                      
                     
                       d 
                       
                         L 
                         - 
                         1 
                       
                     
                   
                 
               
                
               mod 
                
               
                   
               
                
               N 
             
           
         
       
       
         
           
             
               M 
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     0 
                   
                   
                     L 
                     - 
                     1 
                   
                 
                  
                 
                   
                     C 
                     
                       
                         2 
                         i 
                       
                        
                       
                         d 
                         i 
                       
                     
                   
                    
                   mod 
                    
                   
                       
                   
                    
                   N 
                 
               
             
              
             
                 
             
           
         
       
     
         [0000]    If x i =C 2     i   , then in 
         [0000]    
       
         
           
             M 
             = 
               
              
             
               
                 ∏ 
                 
                   i 
                   = 
                   0 
                 
                 
                   L 
                   - 
                   1 
                 
               
                
               
                 
                   x 
                   i 
                   
                     d 
                     i 
                   
                 
                  
                 mod 
                  
                 
                     
                 
                  
                 N 
               
             
           
         
       
       
         
           
             
               where 
                
               
                   
               
                
               
                 x 
                 i 
                 
                   d 
                   i 
                 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           x 
                           i 
                         
                          
                         
                             
                         
                          
                         for 
                          
                         
                             
                         
                          
                         
                           d 
                           i 
                         
                       
                       = 
                       1 
                     
                   
                 
                 
                   
                     
                       
                         1 
                          
                         
                             
                         
                          
                         for 
                          
                         
                             
                         
                          
                         
                           d 
                           i 
                         
                       
                       = 
                       0 
                     
                   
                 
               
             
           
         
       
     
         [0000]    the variable x i  can be calculated iteratively: 
         [0000]        x   i+1   =C   2     i+1   =( C   2     i   ) 2   =x   i   2    
         [0000]    The “multiplication and squaring” algorithm is thus obtained as a pseudo-code: 
         [0000]    
       
         
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 M=1;x=C; 
               
               
                   
                 for i= 0 to L-1 
               
             
          
           
               
                   
                 if d == 1 
               
             
          
           
               
                   
                 M = M * x mod N 
               
             
          
           
               
                   
                 end if 
               
               
                   
                 x=square(x) mod N 
               
             
          
           
               
                   
                 endfor 
               
               
                   
                   
               
             
          
         
       
     
         [0018]      FIG. 2  shows the associated procedure  10  of modular exponentiation as a block diagram. 
         [0019]    The method starts in block  11 , and in block  12  the method is initialized with the values M=1, x=C and i=0. In block  13  an interrogation takes place as to whether the bit d; of the secret key d is equal to 1. If this is the case, the method continues with block  14 ; if not, the method continues with block  15 . In block  14 , M=x*M mod N is calculated. The method then also continues with block  15 , wherein x=x 2  mod N is determined. Thereafter, in block  16 , an interrogation takes place as to whether i=L−1. If this is the case, the method is terminated in block  18 ; if not, i=i+1 is set in block  17  and the method continues again with block  13 . L cycles are carried out, in which in each case one bit d; of the secret key d is processed. 
         [0020]    Timing attacks on the RSA method were introduced in 1998. In these attacks, the secret key d is derived from the different running time or computing time in the respective cycles. If d i =1, the multiplication in block  14  is carried out, i.e. there is a long running time. If d i =0, the multiplication in block  14  is not carried out and the result is therefore a short running time. Detection of the running time or of the computing times for each cycle takes place for example by evaluating the current consumption, by recording the cache activity in PC applications or by measuring the electromagnetic radiation of components. 
         [0021]    Such a current consumption of a chip card microcontroller as a function of time is shown by way of example in  FIG. 3  and illustrates the mode of operation of these timing attacks in a simple manner.  FIG. 3  shows regions of different current consumption as a function of time, wherein the regions of low current consumption have two typical widths, i.e. durations. The first region  20  represents a region of squaring, in which x=x 2  mod N is determined, while the region  21  represents a region of multiplication, in which M=x*mod N is calculated. Since the last calculation according to the method of  FIG. 2  is carried out only if the bit d i =1, then for the present case d i  must be equal to 1. This is then followed by regions  22 ,  23  and  24 , in which the multiplication is not carried out and thus d i  must be equal to 0. It is thus possible to detect in a relatively simple manner whether d i =0 or d i =1. The corresponding value of d; is shown in the bottom line of  FIG. 3 . It is thus possible to detect the respective key bit d i  based on the current curve by means of the different running times for “multiplication” and “squaring”. In order to prevent these attacks, use is made of the so-called “always multiplication and squaring” method which, for the case where d i =0, always carries out an identical but ineffective multiplication which leads to a constant cycle time for d i =1 or d i =0. The associated pseudo-code is accordingly: 
         [0000]    
       
         
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 M=1;x=C; 
               
               
                   
                 for i= 0 to L-1 
               
             
          
           
               
                   
                 if d == 1 
               
             
          
           
               
                   
                 M = M * x mod N 
               
             
          
           
               
                   
                 else 
               
             
          
           
               
                   
                 M * x mod N 
               
             
          
           
               
                   
                 end if 
               
               
                   
                 x=square(x) mod N 
               
             
          
           
               
                   
                 endfor 
               
               
                   
                   
               
             
          
         
       
     
         [0022]      FIG. 4  shows a block diagram  30  for illustrating this improved RSA method. The method starts in block  31 , and in block  32  the method is initialized with corresponding start values. In block  33  an interrogation takes place as to whether d i =1. If this is the case, the method continues with block  34 ; if not, the method continues with block  35 . In block  34 , M=x*M mod N is calculated. In block  35 , x*M mod N is carried out as a so-called ineffective multiplication. The method then continues with block  36 , in which x=x 2  mod N is determined. Thereafter, in block  37 , an interrogation takes place as to whether i= L−1. If this is the case, the method is terminated in block  39 ; if not, i=i+1 is set in block  38  and the method continues again with block  33 . L cycles are again carried out, in which in each case one bit d; of the secret key d is processed. 
         [0023]    Following the implementation of the improved RSA method, another method of attack, the so-called differential fault analysis (DFA) attack, on this algorithm became known, according to which the multiplication in the individual cycles is disrupted for example by physical influences such as light, electromagnetic pulses, power supply pulses or the like. If a disruption of the multiplication does not have any effect on the end result, the associated cycle carries out an ineffective multiplication as described above. The corresponding key bit d i  is then d i =0. However, if the disruption alters the end result, the key bit is thus d i =1. If the method is attacked in this way on a cycle-by-cycle basis, the entire secret key d can be determined. 
         [0024]    In order to prevent such an attack, the calculation of the cipher is usually verified by the inverse RSA function using the public key e through C= M e  or by a second RSA calculation. In the first case, the public key e must be known in the system. In the second case, the time taken for the calculation is doubled. 
         [0025]    The method according to the invention for protection against the above-described DFA attacks provides for verification of the calculation of the exponential equation M=C d  by means of a checksum. In this case, a method is carried out which makes use of the ineffective multiplication shown in the method of  FIG. 4 . To this end, the cipher M n  of the binary complementary exponent of d is calculated during the ineffective multiplication, see  FIG. 5 . The method according to the invention as shown in  FIG. 5  provides for verification of the “always multiplication and squaring” method by calculating M n . 
         [0026]      FIG. 5  shows a block diagram  40  for illustrating this method which has been improved with regard to DFA attacks. The method starts in block  41 , and in block  42  the method is initialized with start values. In block  43  an interrogation takes place as to whether d i =1. If this is the case, the method continues with block  44 ; if not, the method continues with block  45 . In block  44 , M=x*M mod N is calculated. In block  45 , M n =x*M mod N is calculated. The method then also continues with block  46 , in which x=x 2  mod N is determined. Thereafter, in block  47 , an interrogation takes place as to whether i= L−1. If this is the case, the method is terminated in block  49 ; if not, i=i+1 is set in block  48  and the method continues again with block  43 . In block  49 , the calculation C*M*M n  mod N=x is queried as part of the verification block  53 . If the equation is satisfied, a non-disrupted calculation is recognized in block  51  and a corresponding signal is returned. However, if the equation is not satisfied, a disrupted calculation is recognized in block  50  and a corresponding error signal is returned. The method is terminated in block  52 . L cycles are again carried out, in which in each case one bit d; of the secret key d is processed. 
         [0027]    If, according to  FIG. 5 , the calculation M n =x*M n  mod N is carried out during the ineffective multiplication, the following is obtained at the end of the last cycle: 
         [0000]      M n =C   d    mod N 
         [0000]    wherein the complement  d  of the key d has to be replaced by the equation 
         [0000]          d = 2 L −1− d.    
         [0000]    This gives: 
         [0000]        M   n   =C   2     L     −1−d  mod  N.    
         [0000]    If the product 
         [0000]        y=C·M·M   n  mod  N    
         [0000]        y=C·C   d   ·C   2     L     −1−d  mod  N    
         [0000]      y=C 2     L    mod N 
         [0000]    is calculated, the result y can be compared directly with the auxiliary variable x, which after L cycles assumes the same value x L =C 2     L    mod N. Any disruption due to a so-called DFA attack thus means that x is not equal to the product y. 
         [0028]    With just two multiplications and one comparison with a typical 1024-bit RSA (1024 multiplications+ 1024 squaring calculations), the effort for this verification is low. 
         [0029]    The calculation is even more advantageous if M n  is initialized with C. There is thus no need for the multiplication by C after the last cycle. Moreover, the memory requirement is reduced since there is no need to store C after the initialization. Such a method is shown in  FIG. 6 , wherein optimization is carried out by initializing M n =C prior to the exponentiation. 
         [0030]      FIG. 6  shows a block diagram  60  for illustrating this method which has been improved with regard to DFA attacks and optimized. The method starts in block  61 , and in block  62  the method is initialized with start values including M n =C. In block  63  an interrogation takes place as to whether d i =1. If this is the case, the method continues with block  64 ; if not, the method continues with block  65 . In block  64 , M=x*M mod N is calculated. In block  65 , M n =x*M n  mod N is calculated. The method then also continues with block  66 , in which x=x 2  mod N is determined. Thereafter, in block  67 , an interrogation takes place as to whether i=L−1. If this is the case, the method is terminated in block  69 ; if not, i=i+1 is set in block  68  and the method continues again with block  63 . In block  69 , the calculation M*M n  mod N=x is queried as part of the verification block  73 . If the equation is satisfied, a non-disrupted calculation is recognized in block  71  and a corresponding signal is returned. However, if the equation is not satisfied, a disrupted calculation is recognized in block  70  and a corresponding error signal is returned. The method is terminated in block  72 . 
         [0031]    However, according to the invention, the above-described method can also be applied to other methods or to general mathematical structures, such as to processes of the “always addition and doubling” method.  FIG. 7  shows a block diagram  80  for illustrating a corresponding “always addition and doubling” method which has been improved with regard to DFA attacks and optimized, such as an ECC or HECC method, wherein the ECC method is the method of elliptical curve cryptography and the HECC method is the method of hyperelliptical curve cryptography. The method starts in block  81 , and in block  82  the method is initialized with start values. In block  83  an interrogation takes place as to whether d i =1. If this is the case, the method continues with block  84 ; if not, the method continues with block  85 . In block  84 , M=x+M is calculated. In block  85 , M n =x+M n  is calculated. The method then also continues with block  86 , in which x=2*x is determined. Thereafter, in block  87 , an interrogation takes place as to whether i=L−1. If this is the case, the method continues in block  89 ; if not, i=i+1 is set in block  88  and the method continues again with block  83 . In block  89 , the calculation M+M n =x is queried as part of the verification block  93 . If the equation is satisfied, a non-disrupted calculation is recognized in block  91  and a corresponding signal is returned. However, if the equation is not satisfied, a disrupted calculation is recognized in block  90  and a corresponding error signal is returned. The method is terminated in block  92 . 
         [0032]    This verification method can also be used for general mathematical groups. Let (G,+,O) be a group containing elements of G, a neutral element O and a group linker “+”. The n-fold summing of a group element P is denoted n*P, in particular 0*P=O and (−n)*P=n*(−P), wherein “−P” is the inverse element of P. In order to protect the implementation of the operation d*P using an optionally also secret scalar factor d≧0 with a bit length L against timing attacks, an “always addition and doubling” algorithm can also be implemented in the same way as the “always multiplication and squaring” algorithm. The above-described protection against DFA attacks can also be transferred in an analogous manner; the auxiliary variable y is calculated at the end: 
         [0000]        y=M+M   n =( d*P )+((2 L −1− d )* P )+ P    
         [0000]        y= 2 L   *P    
         [0000]    A DFA attack has then taken place when, and only when, for the auxiliary variable x, x≠y. 
       LIST OF REFERENCES 
       [0000]    
       
           1  diagram 
           2  block of diagram  1   
           10  block diagram showing the procedure of modular exponentiation 
           11  block of block diagram  10   
           12  block of block diagram  10   
           13  block of block diagram  10   
           14  block of block diagram  10   
           15  block of block diagram  10   
           16  block of block diagram  10   
           17  block of block diagram  10   
           18  block of block diagram  10   
           20  region 
           21  region 
           22  region 
           23  region 
           24  region 
           30  block diagram 
           31  block of block diagram  30   
           32  block of block diagram  30   
           33  block of block diagram  30   
           34  block of block diagram  30   
           35  block of block diagram  30   
           36  block of block diagram  30   
           37  block of block diagram  30   
           38  block of block diagram  30   
           40  block diagram 
           41  block of block diagram  40   
           42  block of block diagram  40   
           43  block of block diagram  40   
           44  block of block diagram  40   
           45  block of block diagram  40   
           46  block of block diagram  40   
           47  block of block diagram  40   
           48  block of block diagram  40   
           49  block of block diagram  40   
           50  block of block diagram  40   
           51  block of block diagram  40   
           52  block of block diagram  40   
           53  verification block of block diagram  40   
           60  block diagram 
           61  block of block diagram  60   
           62  block of block diagram  60   
           63  block of block diagram  60   
           64  block of block diagram  60   
           65  block of block diagram  60   
           66  block of block diagram  60   
           67  block of block diagram  60   
           68  block of block diagram  60   
           69  block of block diagram  60   
           70  block of block diagram  60   
           71  block of block diagram  60   
           72  block of block diagram  60   
           73  verification block of block diagram  60   
           80  block diagram 
           81  block of block diagram  80   
           82  block of block diagram  80   
           83  block of block diagram  80   
           84  block of block diagram  80   
           85  block of block diagram  80   
           86  block of block diagram  80   
           87  block of block diagram  80   
           88  block of block diagram  80   
           89  block of block diagram  80   
           90  block of block diagram  80   
           91  block of block diagram  80   
           92  block of block diagram  80   
           93  verification block of block diagram  80