Patent Publication Number: US-7907724-B2

Title: Method and apparatus for protecting an RSA calculation on an output by means of the chinese remainder theorem

Description:
BACKGROUND 
     The present invention relates to cryptography and, in particular, to a method and an apparatus for protecting an RSA calculation of an output based on input values by means of the Chinese remainder theorem (CRT). 
     Modular exponentiation is one of the core calculations for various cryptographic algorithms. One example of a widespread cryptographic algorithm is the RSA cryptosystem. 
     Let N=p·q be the product of two large input primes p and q. Let also a public exponent e be coprime to φ(N)=(p−1)(q−1), wherein φ(.) denotes Euler&#39;s totient function. Thereby the totient φ(.) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. A corresponding secret exponent to the public exponent e is d=e −1  mod φ(N). For the RSA cryptosystem the output or a signature on an input message M is given by
 
S=M′ d  mod N,  (1)
 
wherein M′=μ(M) for some deterministic padding function μ. The validity of the output S can be then publicly verified by checking whether S e =μ(M)(mod N), using the public exponent e.
 
     Most implementations of the widely-used RSA cryptosystem rely on the Chinese remainder theorem as this greatly improves the performance in both running time as well as memory requirement. In CRT mode of the RSA cryptosystem, the secret parameters are d p =d mod (p−1), d q =d mod (q−1) and q inv =q −1  mod p. The output S is then computed as
 
 S =CRT( S   p   ,S   g )= S   q   +q[q   inv ( S   p   −S   q )mod  p],   (2)
 
with
 
S P =M′ d     p    mod p,
 
S q =M′ d     q    mod q.  (3)
 
     Unfortunately, CRT-based implementations of the RSA cryptosystems are also known to be more sensitive to fault attacks. A single fault in an RSA exponentiation may reveal the two secret input prime factors p, q through a gcd-computation (gcd=greatest common divisor). Differential fault attacks against the RSA cryptosystem with CRT have emerged to one of the most important attack scenarios (not only) against RSA, since the publication of Boneh et al., “On the Importance of Checking Cryptographic Protocols for Faults(Extended Abstract), Eurocrypt 1997, pages 37 to 51. A lot of fault attacks have been described in the meantime. Countermeasures to the fault attacks are as diverse as the fault attacks themselves. The first and best known countermeasure is described in U.S. Pat. No. 5,991,415. This specialist publication suggests using a small random number r and to compute the two half exponentiations, S p  and S q  of equations (3) in a redundant way, that is
 
 S   p   *=M′   d  mod  rp  
 
 S   q   *=M′   d  mod  rq,   (4)
 
and to return the output S=CRT (S p *. S q *) mod N in case S p *=S q *(mod r) and an error or countermeasure otherwise.
 
     Most of the countermeasures of today work on the principle described in U.S. Pat. No. 5,991,415. Redundancy is introduced into the RSA computation, which is checked at the end of the computation and, based on the success of the tests, the (correct) signature is output or the wrong signature is suppressed. 
     Another alternative is to base a fault-check on a one- or zero-comparison and, in the case of an inequality, to combine the comparing number with a signature, such that the signature is changed or infected in such a way in case of an error, such that an attacker cannot draw any conclusions on the secret key. In this case, a dedicated error output can be avoided, since a double disturbed signature is output. 
     In case an attacker is able to disturb the check as well, he might be able to suppress the error output or the infection of the signature. For this reason, also the fault revealing parts of the algorithms have to be protected. This is not always an easy task, since it is not possible to know every possible fault attack (used in the future). Due to the diverse fault attacks, additional fault-checks have been added to the algorithms. Each of those fault-checks is a potential target for an attack and has to be carefully protected. For this reason, an RSA cryptosystem might become more and more complex related to a security evaluation, since it has to be secured that the fault-checks cover the whole computation seamlessly. 
     Hence, it would be desirable to secure the whole critical computation of an RSA-CRT cryptosystem by using as few fault-checks as possible. 
     BRIEF SUMMARY 
     Embodiments of the present invention provide an apparatus for protecting an RSA calculation of an output based on input values by means of the Chinese remainder theorem, the apparatus comprising a first determining device adapted to determine a first security parameter based on the input values, a computing device adapted to compute a control value based on the first security parameter and the input values, a calculating device adapted to calculate a modified input parameters based on the input values and the first security parameter, a performing device adapted to perform the RSA calculation based on the modified input values to obtain a single modified output, and a second determining device adapted to determine whether the single modified output is in a predetermined relation to the control value and applying a countermeasure in case the predetermined relation is not fulfilled. 
     Further embodiments of the present invention provide an apparatus for protecting an RSA calculation of an output message based on an input message and a first and a second input value by means of the Chinese remainder theorem, the apparatus comprising a first register for the first input value, a second register for the second input prime, a third register for the input message, a fourth register for a first security parameter, a fifth register for a control value, wherein a register content of the fourth register is determined based on register contents of the first and the second registers, wherein the fifth register content is determined based on the register contents of first, the second, the third and the fourth register, and wherein the apparatus comprises a processing sub-unit configured to compute a single modified output message based on modified register contents of the first and second register, and to determine whether the single modified output message is in a predetermined relation to the register content of the fifth register and to apply a countermeasure in case the predetermined relation is not fulfilled. 
     Further embodiments of the present invention provide a method for protecting an RSA calculation of an output based on input values by means of the Chinese remainder theorem comprising determining a first security parameter based on the input values, computing a control value based on the first security parameter and the input values, calculating modified input parameters based on the input values and the first security parameter, performing the RSA calculation based on the modified input values to obtain a single modified output and determining whether the single modified output is in a predetermined relation to the control value and applying a countermeasure in case the predetermined relation is not fulfilled. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In the following, embodiments of the present invention are explained in more detail with reference to the accompanying drawings, in which: 
         FIG. 1  shows a flow chart of a method for protecting an RSA calculation by means of the Chinese remainder theorem according to an embodiment of the present invention; 
         FIG. 2  shows a more detailed flow chart of a method for protecting an RSA calculation by means of the Chinese remainder theorem according to an embodiment of the present invention; and 
         FIG. 3  shows a block diagram of an apparatus for performing a method according to  FIG. 1  or  2 . 
     
    
    
     DETAILED DESCRIPTION 
     With regard to the following description, it should be noted that in the different embodiments, equally operating functional elements have the same reference numerals and, thus, the descriptions of those functional elements are exchangeable in the different embodiments illustrated in the following. 
       FIG. 1  shows a flow chart of a method for protecting an RSA calculation of an output S based on input values p, q, d and M by means of the Chinese remainder theorem. 
     From the input values p, q and d further values d p =d mod (p−1), d q =d mod(q−1) and q inv =q −1  mod p can be derived. 
     In a first step S 1 , a first security parameter t is determined based on the input values p and q. In a second step S 2 , a control value σ is computed based on the first security parameter t and the input values p, q and M. In a third step S 3 , modified input parameters {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)}, {tilde over (q)} inv  are calculated based on the input values p, q and the first security parameter t. In a fourth step S 4 , the RSA calculation with CRT is performed based on the modified input values {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)}, {tilde over (q)} inv  to obtain a single modified output Ŝ. In a further step S 5 , it is determined whether the single modified output Ŝ is in a predetermined relation to the control value σ. A countermeasure is applied in case the predetermined relation is not fulfilled. 
     Thereby, the countermeasure could be e.g. to suppress the calculation and output of the output or output signature S stemming from the single modified output Ŝ. Alternatively, the output signature S could be computed in any case and, as a countermeasure, in case the predetermined relation is not fulfilled, be further infected or falsified. 
     According to embodiments of the present invention the step S 5  includes a sub-step of extracting the output signature S based on the single modified output signature Ŝ and the input values p, q. 
     After an overview of the inventive method has been given schematically referring to  FIG. 1 , embodiments of the single steps S 1  to S 5  shall be explained in more detail in the following. 
     In step S 1 , the first security parameter t is chosen as a random prime having a word length of, for example, 32 bits. Thereby, the first security parameter t has to have certain properties, in particular, that the modular multiplicative inverse q inv  of the input prime q modulo the input prime p modularly reduced by the first security parameter t is not equal to 0 and that the modular reduction of a product of the modular multiplicative inverse q inv  of the input prime q and the input prime q with respect to the modulus t is not equal to 1, that is
 
q inv  mod t≠O and  (5)
 
ζ t   =q   inv   ·q  mod  t≠ 1.  (6)
 
In particular, ζ t  has to be outside the interval between 0 and 1, i.e. ζ t ∉{0,1}.
 
     According to an embodiment of the present invention, in step S 1 , a candidate for the first security parameter t is chosen to fulfill equations (5) and (6) and then the property ζ t ∉{0,1} is checked. If it is not fulfilled, then a new first security parameter t will be used. Note that the input prime q and its modular inverse q inv  are secret and nearly random parameters. An attacker cannot force them to have certain values or, if he could, one could say that such an attack would not make any sense, since this is the value he wants to extract. So, the probability that the condition ζ t ∉{0,1} is not fulfilled is about 2/t and it will practically never happen that two or more values for t will be thrown away. 
     In step S 1 , it is further important that φ(t−1) is as big as possible. This value is directly related to the error detection probability. Since (t−1) is an even integer, φ(t−1)≦(t−1)/2, and the equality holds if and only if t=2g+1, wherein g is an odd prime number. Hence, according to embodiments of the present invention the first security parameter t is determined such that the Euler&#39;s totient function of the first security parameter minus one is larger than (t−1)/3, i.e. φ(t−1)&gt;(t−1)/3. 
     During step S 1  or in a succeeding step, a second security parameter u can be generated. Thereby, the second security parameter u is greater than or equal to 0 and is smaller than the first security parameter t, i.e. uε[0,t[, such that the greatest common divisor of the second security parameter u and the product of the first security parameter t and the input prime p is equal to 1, that is gcd(u, t·p)=1. 
     After the step S 1  has been performed, the first security parameter t can be used together with the input values p, q, d p , d q , q inv  and M to compute the control value σ in the second step S 2 . Thereby, the control value σ can be computed based on the following equation:
 
σ=[σ q (1−ζ t )+σ p ζ t ] mod  t,   (7)
 
wherein σ q  denotes a modular reduction of a value depending on the input message M and the input prime q with respect to a modulus being the first security parameter t. According to an embodiment of the present invention, σ q  can be calculated according to
 
σ q =M d     q    mod t.  (8)
 
     In equation (7), σ p  denotes a modular reduction of a value depending on the input message and the input prime p with respect to a modulus being the first security parameter t. According to an embodiment of the present invention, σ p  can be calculated according to
 
σ p =M d     p    mod t.  (9)
 
     Having performed the computation of the control value σ in the second step S 2 , the modified input values {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)}, {tilde over (q)} inv  can be determined in step S 3 . 
     Here, a modified input parameter {circumflex over (p)} is calculated from a product of the input parameter p and the first security parameter t, i.e. {circumflex over (p)}=p·t. A further modified input parameter {circumflex over (q)} is calculated from a product of the input parameter q and the first security parameter t, i.e. {circumflex over (q)}=q·t. Yet a further modified input parameter {tilde over (q)} is calculated from a product of the input parameter q and the second security parameter u, which has e.g. been determined in step S 1 , i.e. {tilde over (q)}=q·u. According to an embodiment of the present invention, in step S 3  also a modified modular inverse {tilde over (q)} inv  is determined based on a modular reduction of a product of the inverse u −1  of the second security parameter u and the input parameter q with respect to the modulus being the input parameter p, i.e. {tilde over (q)} inv =u −1 ·q mod p. 
     The second security parameter u could, of course, also be computed in step S 3  instead of step S 1 . Furthermore, the order of execution of step S 2  and S 3  could be reversed according to different embodiments of the present invention. However, it is advantageous to compute the control value σ as early as possible. 
     After the execution of step S 3  leading to the modified input parameters {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)} and {tilde over (q)} inv , an RSA computation with CRT is used in step S 4  to generate a single modified output or output signature Ŝ based on
 
 Ŝ=S   q +[( S   p   −S   q )· {tilde over (q)}   inv  mod  {circumflex over (p)}]·{tilde over (q)}   (10)
 
wherein S q  denotes a value obtained by a modular reduction of a value depending on the input message M with respect to a modulus determined by the modified input parameter {circumflex over (q)}, and wherein S p  denotes a value obtained by a modular reduction of a value depending on the input message M with respect to a modulus determined by the modified input parameter {circumflex over (p)}. According to embodiments of the present invention, S p , S q  can be determined based on
 
S p =M d     p    mod {circumflex over (p)} and S q =M d     p    mod {circumflex over (q)}.  (11)
 
     Note, that it is very important not to use {circumflex over (q)} instead of {tilde over (q)} in equation (10). Since {circumflex over (q)}=q·t it would destroy any information about an error in the big bracket. 
     After having determined the single modified output Ŝ in step S 4 , the single modified output Ŝ can be used to determine whether the first security parameter t is in a predefined relation to the control value σ in step S 5 . Or, in other words, it can also be determined whether the single modified output Ŝ is in a predefined relation to the control value σ using the first security parameter t. For that, a modular reduction of the single modified output Ŝ with respect to a modulus determined by the first security parameter t is computed. Then it is checked whether the result of the modular reduction is equal to the control value σ, i.e. it is checked whether Ŝ mod t=σ. If this is the case, then the output or the output signature S can be extracted from the single modified output Ŝ based on the relation
 
 S=Ŝ  mod( p·q ).  (12)
 
     In case Ŝ mod t is not equal to σ, i.e. Ŝ mod t≠σ, an aforementioned countermeasure can be applied. 
     In step S 5 , an error detection based on a decisional test is performed. The decisional test, i.e. the comparison of (Ŝ mod t) to σ, can be protected, for example, by performing this decisional test more than once. This can be done by performing the decisional test of S 5  sequentially or in parallel. By doing so, a bypass of the error detection by inducing a random fault in a status register of the decisional test can be avoided. 
     Note, that the whole critical RSA-CRT computation of step S 4  is protected by a single fault-check in step S 5 . This means, that only the decisional test needs to be protected and no implementary security holes appear. 
     In order to protect the RSA-CRT computation even more efficiently, also against differential power analysis (DPA), more algorithmic modifications can be introduced, such that the cryptographic operations occur on data that is related to actual values by some mathematical relationship that survives the cryptographic operations. For this reason, more than the aforementioned two security parameters t, u can be used. Embodiments of the present invention may also use further, odd-valued randomization parameters r 1  to r 4 . 
     A detailed description of the method for protecting the RSA-CRT computation using the security parameters t, u and the randomization parameters r 1  to r 4  is described in detail in the following referring to  FIG. 2 . 
     According to embodiments of the present invention the security parameters t, u and the randomization parameters r 1  to r 4  are determined based on the input parameter q (and q inv ) in the first step S 1 . 
     According to embodiments the following criteria have to be fulfilled for the security parameters t, u and the randomization parameters r 1  to r 4 . 
     The first security parameter t for the whole CRT computation is generated, such that tε[2 16 , 2 64 [\F 4  prime, such that φ(t−1) is big, with q inv  mod t≠0 and ζ t =q inv ·q mod t≠1. As mentioned before, the first security parameter t has to have certain properties, in particular the fact that q inv  mod t≠0 and q inv ·q mod t≠1. The actual property is that ζt∉{0,1}, where ζ t :=q inv  ·q mod t. So, in S 1  a candidate for the first security parameter t is chosen, then the property ζ t ∉{0,1} is checked. If it is not fulfilled, then a new first security parameter t will be used. Note that q and q inv  are secret and nearly random parameters. An attacker cannot force them to have a certain value. Or, if he could, one can say that such an attack does not make any sense, since this is the value he wants to extract. So, the probability that the condition is not fulfilled is about 2/t, and it will practically never happen that two or more values for t will be thrown away. 
     Another important property for t is that φ(t−1) is as big as possible. This value is directly related to the error detection probability. Since (t−1) is an even integer, φ(t−1)≦(t−1)/2, and equality holds if and only if t=2·g+1, where g is an odd prime number. 
     The randomization parameters r 1  and r 2  for the input parameters p and q as well as r 3  and r 4  for the exponents d p  and d q  are generated, such that e.g. r 1 ε[2 16 , 2 β [∩[0, (t−1)/2[, wherein r 1  is odd, r 2 ε[2 16 , 2 β [∩[0, (t−1)/2[, wherein r 2  is odd, r 3 ε[2 16 , 2 γ [Ω[0, (t−1)/2[, wherein r 3  is odd, and r 4 ε[2 16 , 2 γ [Ω[0, (t−1)/2[, wherein r 4  is odd. According to embodiments of the present invention the numbers β, γ are chosen to be greater than 16. The fact that the randomization parameters r 1 , r 2 , r 3 , r 4  are chosen to be odd, saves a factor 2 in the error detection probability. Furthermore, gcd(r i ,t−1)=1 (i=1, 2, 3, 4). 
     Furthermore, the second security parameter u is generated in step S 1 , such that uε[0, t[with gcd(u, r 1 ·t·p)=1, e.g. u=t−r 1 . Since u should have the special property gcd(u, r 1 ·t·p)=1, the value u:=t−r 1  can be used for it. The property is fulfilled for this special value because of gcd(u,p)=1, since p is a prime larger than u, gcd(u,t)=gcd(t−r 1 ,t)=gcd(r 1 ,t)=1, since t is a prime larger than r 1 , and gcd(u,r 1 )=gcd(t−r 1 ,r 1 )=gcd(t,r 1 )=1, since t is a prime larger than r 1 . 
     According to an embodiment of the present invention, the inputs to the second step S 2  are the input values pε[0,2 2048+64 [, qε[0,2 2048+64 [, Mε[0,N[(N=pq) and the values d p ε[0,φ(p)[, d P ε[0,φ(q)[, q inv =q −1  mod p, r 1 , r 2 , r 3 , r 4 , t, which can all be derived from the input values p, q. 
     In order to compute the control value σ in step S 2 , all input data of the RSA routine have to be reduced modulo t or (t−1) (in case of exponent parameters), i.e. 
     
       
         
           
               
               
               
               
               
             
               
                   
                   
               
             
            
               
                   
                   
                 p t   
                 := p mod t 
                 (13) 
               
            
           
           
               
               
               
               
            
               
                   
                 p t−1   
                 := p mod (t−1) 
                 (14) 
               
            
           
           
               
               
               
               
               
            
               
                   
                   
                 q t   
                 := q mod t 
                 (15) 
               
            
           
           
               
               
               
               
            
               
                   
                 q t−1   
                 := q mod (t−1) 
                 (16) 
               
            
           
           
               
               
               
               
               
            
               
                   
                   
                   
                 dp t−1  := dp mod (t−1) 
                 (17) 
               
               
                   
                   
                 dq t−1   
                 := dq mod (t−1) 
                 (18) 
               
               
                   
                   
                 q inv,t   
                 := q inv  mod t 
                 (19) 
               
               
                   
                   
                 ζ t   
                 := q inv,t · q t  mod t 
                 (20) 
               
            
           
           
               
               
               
            
               
                   
                 M t := M mod t 
                 (21) 
               
               
                   
                   
               
            
           
         
       
     
     Note that after the reduction, the parameters do contain only minimal (and not useful) information about the secrets, so these computations may not need the full care for security for the implementation. 
     Further, a correction of M t  is done in step S 2 , since in the case of (M t =0) or (M t =1) or (M t =t−1) the computation of the control value σ will not yield any or much information about an error in the main computation. Since M can be chosen by an attacker, it is better to make a correction on the message M than just choosing another first security parameter t. E.g. an attacker could choose the product of all first security parameters t which are stored on the chip. Hence, M t  is modified with an iteration loop according to 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 ω := 0 
               
               
                   
                 while (M t  ∈ {0,1,t−1}   ω = 0) do 
               
            
           
           
               
               
            
               
                   
                 M t  := (M t  + (q t  · p t )) mod t 
               
               
                   
                 ω := ω + 1 
               
            
           
           
               
               
            
               
                   
                 end 
               
               
                   
                   
               
            
           
         
       
     
     During the modification of M t , a new parameter ω is evaluated. This parameter ω will be important for the step S 3  and has to be provided to it. 
     Modified exponent parameters for the modified input message M t  can be computed based on
 
δ p   :=dp   t−1   +r   3   r   1 ( p   t−1 −1)mod( t− 1)  (22)
 
δ p   :=dp   t−1   +r   4   r   2 ( p   t−1 −1)mod( t− 1)  (23)
 
     Then, the control value σ can be computed based on the “small” CRT computation according to equation (7), wherein here σ q  denotes a modular reduction of the modified input message M t  raised to the power of δ q  with respect to a modulus being the first security parameter t according to
 
σ q =M t   δ     q    mod t.  (24)
 
Further, σ p  here denotes a modular reduction of the modified input message M t  raised to the power of δ p  with respect to a modulus being the first security parameter t according to
 
σ p =M t   δ     p    mod t.  (25)
 
     Hence, as already described referring to  FIG. 1 , the control value σ for the whole RSA-CRT computation is determined in the second step S 2 . Compared to the embodiment described referring to  FIG. 1 , here the randomization parameters r 1  to r 4  are additionally involved in the determination of the control value ca. 
     Having performed the computation of the control values σ and ω in the second step S 2 , the modified input values {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)}, {tilde over (q)} inv  can be determined in step S 3  based on the inputs pε[0,2 2048+64 [, qε[0,2 2048+64 [, d p ε[0,φ(p)[, d q ε[0,φ(q)[, q inv =q −1  mod p, Mε[0,N[, r 1 , r 2 , r 3 , r 4 , t, u, ω. 
     The modification of the input values for the RSA-CRT computation of step S 4  starts first with the randomization of the most secret parameters p and q. Care has to be taken for the implementation of this sub-step of step S 3 .
 
 p′:=r   1   ·p,   (26)
 
 q′:=r   2   ·q,   (27)
 
     The next sub-step of step S 3  is the computation of the public key element N based on
 
 N:=p·q.   (28)
 
     The parameter ω, gained in step S 2 , is involved in the modification of the message M according to
 
 M′:=M+N·ω.   (29)
 
     Then, the exponents have to be randomized. This is done in the following way:
 
 {circumflex over (p)}=p′·t,   (30)
 
 {circumflex over (q)}=q′·t,   (31)
 
 {tilde over (d)}   p   :=d   p   +r   3 ( {tilde over (p)}−t·r   1 ),  (32)
 
 {tilde over (d)}   q   :=d   q   +r   3 ( {tilde over (q)}−t·r   2 ).  (33)
 
     Since q will not be used directly in the subsequent step S 4 , but randomized with u, the value q inv  is also modified in step S 3 . The related sub-step involves an inversion, but since one of the numbers (namely u) is very small, the computation based on
 
 {tilde over (q)}:=q·u,   (34)
 
 u   inv   :=u   −1  mod  {circumflex over (p)},   (35)
 
 {tilde over (q)}   inv   :=u   inv   ·q   inv  mod  {circumflex over (p)},   (36)
 
is not too time consuming.
 
     After the execution of step S 3  leading to the modified input parameters {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)} and {tilde over (q)} inv , the RSA computation with CRT is used in step S 4  to generate a single modified output or output signature Ŝε[0,N·2 β+2r [based on the modified inputs ({circumflex over (p)}, {circumflex over (q)}, {tilde over (d)} p , {tilde over (d)} q , {tilde over (q)} inv , {tilde over (q)}, M′) based on equation (10), wherein S q  denotes a value obtained by a modular reduction of a value depending on the input message M with respect to a modulus determined by the modified input parameter {circumflex over (q)}, and wherein S p  denotes a value obtained by a modular reduction of a value depending on the input message M with respect to a modulus determined by the modified input parameter {circumflex over (p)}. According to embodiments of the present invention, S p , S q  can be determined based on
 
S p =M {tilde over (d)}     p    mod {circumflex over (p)} and S q =M {tilde over (d)}     p    mod {circumflex over (q)}.  (37)
 
     The single modified output Ŝ generated in step S 4  will provide, reduced modulo N, the result and, reduced modulo t, the control value σ—given that no fault attack has taken place. 
     Step S 4  is almost a normal RSA-CRT computation with the only exception that the modulus {tilde over (q)} used in the second exponentiation is not the parameter which is used in Garners formula as the prime factor on the right hand side. Note that the single modified output Ŝ will not be reduced in step S 4 , neither with respect to N nor to N·t. There is no need to do that, since the reductions take place in step S 5 . 
     In step S 5 , error detection based on a decisional test is performed has described above. 
     Regarding security provided by embodiments of the present invention, it has to be mentioned that DPA (differential power analysis) is possible at a point where unknown (but fixed) values come together with known (or even determinable) values. Known and secret values come together in step S 4 . Since in step S 3  all the secret values are randomized, in step S 4 , all the secret values (even the intermediary ones) cannot be guessed by an attacker. So a (first order) DPA is not possible. 
     For DFA (differential fault analysis) a careful analysis and simulation was done with the result that all faults can be detected with a probability that depends on the first security parameter t:
         The overall probability that a successful error induction is not detected is ≦       

     
       
         
           
             
               2 
               t 
             
             . 
           
         
       
         
         
           
             The worst case probability that a successful error induction is not detected is 
           
         
       
    
     
       
         
           
             ≤ 
             
               
                 4 
                 t 
               
               . 
             
           
         
       
     
     The only fault induction which cannot be detected is one by a faulty N or Ŝ, i.e. only faults induced in step S 5 . But those are not fatal, since they do not include secret information any more. Note: If the computations in steps S 1  to S 4  have been done error free, then step S 5  could be a public operation. 
     SPA (simple power analysis) cannot be covered by embodiments of the present invention. Important is the implementation of (in particular) the two exponentiations in step S 4 . 
     It is crucial that the input variables have to be checked after the computation, since, e.g., a change in the input value d p  cannot be detected intrinsically. An alternative would be to compute and pass additionally the parameters p t , p t−1 , q t , q t−1 , dp t−1 , dq t−1 , q inv,t  to the function. Of course, for this, the caller has to know the security value t. 
     In order to perform embodiments of the inventive method described before, an embodiment of the present invention provides an apparatus  30  for protecting an RSA-CRT calculation of an output S based on input values p, q, M. An embodiment of the apparatus  30  is shown in  FIG. 3 . 
     The apparatus  30  comprises a first determining device  31  for determining the first security parameter t based on the input values p, q. The apparatus  30  further comprises a computing device  32  for computing the control value σ based on the first security parameter t and the input values p, q and M. Means  33  for calculating modified input parameters {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)} and {tilde over (q)} inv  based on the input values p, q and the first security parameter t is also provided. The apparatus  30  also comprises performing device  34  for performing the RSA-CRT calculation based on the modified input values {circumflex over (p)}, {circumflex over (q)}, {tilde over (q)} and {tilde over (q)} inv  to obtain the single modified output Ŝ. The single modified output Ŝ is coupled to second determining device  35  for determining whether the first security parameter t is in a predefined relation to the control value σ and for applying a countermeasure in case the predetermined relation is not fulfilled. 
     According to embodiments of the present invention, the apparatus  30  comprises a first register  36  for the input prime p, a second register  37  for the input prime q, a third register  38  for the input message M, a fourth register  39  for the first security parameter t and a fifth register  40  for the control value σ. 
     The register content of the fourth register  39  is determined by the first determining device  31 , which could be a processing sub-unit of a processing device, based on the first and the second input prime p, q. According to embodiments of the present invention the processing sub-unit  31  also produces the second security parameter u, for which a resister is provided as well. 
     The register content of the fifth register is computed by computing device  32 , which also could be a processing sub-unit of a processing device, based on the input values p, q, M and the first security parameter t. 
     Performing device  34 , which could be a processing sub-unit of a processing device, computes the single modified output message Ŝ based on modified register contents of the first and second registers  36 ,  37  and the contents of the registers related to the first and second security parameters t. Thereby the register contents of the first and second registers  36 ,  37  get modified in the processing sub-unit  33 . 
     The second determining device  35 , which could be a processing sub-unit of said processing device, has access to the single modified output message Ŝ, the first, second, fourth and fifth registers  36 ,  37 ,  39 ,  40  and has an output for the output message S computed based on the single modified output message Ŝ and the register content of the first and second registers  36 ,  37  in case of a positive control operation. An error message is output in case of a negative control operation of the single modified output message Ŝ. Thereby the control operation is based on the decisional test which has been described above referring to step S 5 . 
     It becomes evident from the embodiments described before that the calculations needed in steps S 1  to S 3  and step S 5  are simple calculations, which are, anyhow, present in a crypto-computational unit, such as a multiplication algorithm or an algorithm for performing a modular reduction. 
     According to embodiments of the present invention the apparatus  30  is hence configured as a side-channel-attack-secure hardware block and is used in cryptographic applications. The apparatus  30  is thereby adapted for generating e.g. a signature for an asymmetric cryptographic scheme. 
     Hence, the present invention, due to its flexibility, safety and performance, is suitable in particular for cryptographic algorithms and for cryptographic coprocessors on which a safe and efficient implementation of the RSA-CRT algorithm suitable for signing as well as encryption is typically implemented by means of a circuit. 
     Depending on the circumstances, the inventive method may be implemented in hardware or in software. The implementation may be done on a digital storage medium, particularly a disk, CD or DVD with electronically readable control signals, which may cooperate with a programmable computer system so that the method is executed. In general, the invention thus also consists in a computer program product with a program code stored on a machine-readable carrier for performing the inventive method when the computer program product runs on a computer. In other words, the invention may thus be realized as a computer program with a program code for performing the method when the computer program runs on a computer. 
     While this invention has been described in terms of several preferred embodiments, there are alterations, permutations, and equivalents which fall within the scope of this invention. It should also be noted that there are many alternative ways of implementing the methods and compositions of the present invention. It is therefore intended that the following appended claims be interpreted as including all such alterations, permutations, and equivalents as fall within the true spirit and scope of the present invention.