Indian Patents. 200026:" A CRYPROGRAPHIC METHOD THAT SAVES COMPUTING OPERATIONS OR COMPUTATION TIME WHILE RETAINING OR INCREASING THE SECURITY AND APPARATUS THEREFOR".

Title of Invention	" A CRYPROGRAPHIC METHOD THAT SAVES COMPUTING OPERATIONS OR COMPUTATION TIME WHILE RETAINING OR INCREASING THE SECURITY AND APPARATUS THEREFOR".
Abstract	The invention relates to a cryptographic method with at least one computing step containing a modular exponentiation E according to E = xd (mod poq), with a first prime factor p, a second prime factor q, an exponent d and a number x, whereby the modular exponentiation E is calculated according to the Chinese Remainder Theorem.

Full Text	- 1 - A CRYPTOGRAPHIC METHOD THAT SAVES COMPUTING OPERATIONS OR COMPUTATION TIME WHILE RETAINING OR INCREASING THE SECURITY AND APPARATUS THEREFOR. The present invention relates to a cryptocraphic method that saves computing operations or computation time while retaining or increasing the security and apparatus therefor. Cryptographic methods in the form of encryption and signature schemes are becoming increasingly widespread in particular due to the rising importance of electronic commerce. They are normally implemented by means of electronic apparatuses which may comprise for example a programmable universal microcontroller or else a specialized electronic circuit e.g. in the form of an ASIC. An especially interesting form of cryptographic apparatus is the smart card, since if expediently designed technically it can protect secret key data against unauthorized access. There are constant efforts both to improve the execution speed of cryptographic methods and to protect them against all possible kinds of attacks. The invention is suitable in particular for use in connection with smart cards, but is in no way limited thereto. It is instead implementable in connection with all kinds of cryptographic apparatuses. In a number of known cryptographic methods it is necessary to perform a modular exponentiation according to the equation where p and q are prime numbers. An especially important cryptographic method that comprises a modular exponentiation step is the RSA method, known for example from Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, "Handbook of Applied Cryptography," Boca Raton: CRC Press, 1997, pages 285 to 291. Use of modular exponentiation is not limited to the RSA method, however, but also includes for example Rabin signatures known from Menezes et al., ibid., pages 438 to 442, and the Fiat-Shamir identification scheme known from Menezes et al., ibid., pages 408 to 410. The security of cryptographic methods that include modular exponentiation is regularly dependent on the difficulty of factorizing the number N from equation (1) into its prime factors p and q. This problem is only of sufficient complexity for large values N, SO that N should be chosen as great as possible, on the one hand. The computing effort for calculating values by means of modular exponentiation according to equation (I) increases monotonically with the magnitude of N, on the other hand, so -2- that it would be desirable from the point of view of practical applicability to be able to restrict the computation time required to acceptable values despite large values of TV. It is known to increase the computation speed by a factor of four by applying the so-called "Chinese Remainder Theorem," which permits for example larger values N at equal computation time. Instead of evaluating equation (1) directly, a transformation is performed according to (2) where (3) (4) One consequence of applying the Chinese Remainder Theorem is that the modular exponentiation is no longer done modulo N, i.e. modulo that number concealing its own prime factorization, but successively in a first partial step modulo p and a second partial step modulo q, i.e. knowledge of the prime factorization n = p.q to be kept secret is presupposed in this computing rule and leads to division of the total computing process into a first computing step (3) essentially involving the first prime factor, and a second computing step (4) essentially involving the second prime factor. The advantage is that exponent d in equation (1) must be defined modulo (p.q), whereas the exponents in equation (2) must only be defined modulo (p) or (q), where denotes the Eulerian function. Interestingly, an attack scheme on such cryptographic methods using modular exponentiation has recently become known by which the information on the prime factorization of Ncan be recovered from the faulty result of a disturbed modular exponentiation by suitable artificial intrusions in the otherwise undisturbed computing sequence, provided the concrete implementation makes use of the Chinese Remainder. Theorem according to equations (2) to (4). This attempt known as the "Bellcore attack" is described for example in Dan Boneh, Richard A. DeMillo and Richard J. Lio-ton: "On the importance of checking cryptographic protocols for faults," Advances in Cryptology - EUROCRYPT, 97. Lecture Notes in Computer Science 1233, Berlin: Sponger, 1997. An encryption device is manipulated by physical intrusions such as -3- increasing clock speed, operating voltage or irradiation so that computing errors occur in the execution of the modular exponentiation according to the Chinese Remainder Theorem with a certain, not too great probability. If a computing error occurs only in one of the two terms in equation (2), the two prime factors/p and q can be reconstructed from the erroneous exponentiation result. The consequence to be drawn from this vulnerability of modular exponentiation implemented by means of the Chinese Remainder Theorem is to first check the result of the computing operation for correctness before it is processed further, particularly before it is outputted in some form, e.g. in the form of a signature. A trivial countermeasure for the "Bellcore attack" is to effect this correctness check by repeating the computing operation at least once. In case of random computing errors it can be assumed that the result of the first computing operation deviates from that of the check computing operations. The essential disadvantage of this approach is that the computation time is already doubled by one check calculation. [ The print WO-A1 -9 8/52319 discloses in particular a method for protecting computing operations executing modular exponentiation according to the Chinese Remainder Theorem against the "Bellcore attack." A secret integer j is selected for example in the range of [0, 2k-l] with 16 vl = x(modj.q) (5) v2 =x (mod j.q) (6) d1 = d (mod jop)) (7) d2 = d (mod (joq)) (8) w1 = v1d1 (mod jop) (9) w2 = v2 d2(mod joq) (10) Then it is checked whether it holds that: w1 = w2 (modj) (11) If expression (11) can be verified, the following expressions are calculated in the known method: y1= w1 (mod p) (12) -4- y2 = w2 (mod q) (13) from which the value for E = xd (mod N) (14) can then be determined by means of the Chinese Remainder Theorem. This known method has the advantage over simple check computing operations that the additional computation time required is substantially lower. In this method, both prime numbers p and q must be multiplied by the same factor d. The print WO-A1-9 8/52319 describes a second method that permits prime numbers p and q to be multiplied by different factors r and s. However, two further exponentiations are possible for the check calculation. The problem of the invention is to provide a cryptographic method and apparatus that save computing operations or computation time while retaining or increasing the security. -4A Accordingly, the present invention provides a cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E E = xd (mod poq) with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby for carrying out the modular exponentiation two natural numbers r and s are chosen with the condition that d is relatively prime to kg V(r,s)), and whereby the following computing steps are performed: X1 = x (mod por) x2 = x (mod qos) d_2=d(mod pos)) d_2 = d (mod (qos)) Z1 =X1d-2 (mod por) z2 = x2 d-2 (mod qos) and whereby (.) is the Eulerian function and kgV(r.s) is the smallest common multiple of r and s, then a number z is calculated according to the Chinese Remainder Theorem fromz1 and z2 withz = z1 (modpor) ;z=z2(mod qos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z and thus the result E is checked for computing errors in a checking step, the checking step comprises the following computing operations: calculating the smallest possible natural number e with the property eod=1 (mod kgV(r.s))) with the aid of the Extended Euclidean Algorithm, calculating the value C=ze (mod kgV(r,s)), comparing the values x and C modulo kgV(r,s), whereby the result of the modular exponentiation E is rejected as faulty if x ? C (mod kgV(r,s)). The present invention also provides a cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E E = xu (mod poq) 4B with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby for carrying out the modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in the interval [I,...,r-1] and [1,...s-1] and relatively prime to r and s, respectively, are chosen, and whereby b1 and b2 fulfill the condition b1 = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s, the two numbers b1 and b2 are used to calculate according to the Chinese Remainder Theorem values x1 and x2 fulfilling the following conditions: X1 =x (mod p) ,x1 -b1 (mod r) x2 = x (mod q), x2 = b2 (mod s) and then the following computing steps are performed: d_1 = d (mod (p)) d_2 = d (mod (q)) z2 =x1 d-2 (mod por) Z2 = x2 d_2 (mod qos) and (.) represents the Eulerian function and kgV(r,s) the smallest common multiple of r and s, then a number z is calculated from z1 and z2 according to the Chinese Remainder Theorem with z = z1 (modpor) ;z=z2 (modqos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z (and thus automatically also the result E) is checked for computing errors in a checking step, the checking step comprises the following computing operations: calculating the numbers C1 = b1 d_1 (modor) C2 = b2 d_2 (modos) whereby d_1 and d_2 are reduced before carrying out the modular exponentiation modulo r) and (s), respectively, comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C, ? z1 mod r or C2 ? z2 mod s holds. The present invention further provides a cryptographic apparatus comprising : means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E E = xd (modpoq) with a first prime factory, a second prime factor q, an exponent d and a base x, whereby means for performing a modular exponentiation two natural numbers r and s are chosen with the condition that d is relatively prime to (kgV(r,s)), and whereby the following computing steps are performed: x1 =x (mod por) x2= x (mod qos) d_1 = d (mod d_2 = d (mod (qos)) z1 =x1 d-1 (modpor) z2 = x2 d-2 (mod qos) and (.) is the Eulerian function and kgV(r,s) is the smallest common multi-ple of r and s, means for calculating of the number z calculated from z1 and z2 according to the Chinese Remainder Theorem with z = Z1 (mod pr) z = z2 (mod qos); means for calculating the result E of the exponentiation by reduction of z modulo poq, e) means for checking the previously calculated number z (and thus automatically also the result E)for computing errors in a checking step, f) the checking step comprises the following computing operations: fl) calculating the smallest possible natural number e with the property eod=1 (mod kgV(r,s))) with the aid of the Extended Euclidean Algorithm, f2) calculating the value C = ze (mod kgV(r,s)), f3) comparing the values x and C modulo kgV(r,s), 'whereby the result of the modular exponentiation E is rejected as faulty if x ? C (mod kgV(r,s)). -4D- The present invention further provides a cryptographic apparatus that saves computing operations or computation time while retaining or increasing the security, said apparatus comprising means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E E = xd (mod poq) with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby b) means for performing a modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in the interval [i,...,r-l] and [1,,..s-1] and relatively prime to r and s, respectively, are chosen, and whereby b1 and b2 fulfill the condition bt = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s, c) means for using the two numbers b1 and b2 to calculate according to the Chinese Remainder Theorem values X1 and x2 fulfilling the following conditions: x1 = x (modp) ,x1 = b1 (mod r) x2 = x (mod q), x2 = b2 (mod s) and then the following computing steps are performed: d_1 = d (mod p)) d_2 = d (mod (q)) z1 =x1 d-1 (modpor) z2 = x2d-1 (mod qos) and whereby .) represents the Eulerian function and kgV(r,s) the smallest d) means for calculating a number z from z1 and z2 according to the Chinese Re mainder Theorem with z=Z1 (mod por) ;z=z2 (mod qos); e) means for calculating the result E of the exponentiation by reduction of z modulo poq, f) means for checking the previously calculated number z (and thus automatically also the result E)for computing errors in a checking step, g) the checking step comprises the following computing operations: gl) calculating the numbers C1 = b1d-1 (modor) C2=b2d-2 (modos) whereby d_1 and d_2. are reduced before carrying out the modular exponentiation modulo r) and s), respectively, g2) comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C1 ?Z1 mod r or C2 ? z2 mod s holds. 4E Dependent claims 3 to 12 and 15 to 24 show advantageous developments. As mentioned below, it is advantageous on certain arithmetic and logic units if a modulus in the modular exponentiation has many leading binary ones, so that different factors r and s signify a certain advantage here. Further, there are arithmetic and logic units optimized for modular exponentiation, but the mere data transfer from the central processing unit to the optimized arithmetic and logic unit for exponentiation causes considerable overhead. The present invention saves one exponentiation compared to the above-described method with different factors r and s. According to the invention, two integers r and s are selected for example in the range of [0, 2k-l] with 16 -5- Now z1 = x d (modpof) and z2 = x d (mod qos) hold. According to the Chinese Remainder Theorem a'number z can easily be calculated from z1 and z2 with z = Z1 (mod por); z = z2 (mod qos) ;z = xd (mod p-q-kgV(r,s)) (17) The numbers r and j must according to the invention be chosen so that d is relatively prime to s)). Under these circumstances the Extended Euclidean Algorithm can be used to easily find a natural number e with (18) With the aid of Z and e the number C is calculated as follows: (19) According to Euler's theorem the following holds: (20) By comparison of the two values C and x modulo kgV(r,s) an error can be ascertained with high probability. ifC^x (mod kgV(r,s)) is ascertained, the result of the modular exponentiation is to be regarded as erroneous and rejected. In RSAjnethods (as also in the Rabin signature scheme) a modular exponentiation is to be performed for generating a digital signature or for decryption, whereby the modulus^^_ajid^ip_Qiient^only_depend on the private key. Consequently the numbers d, e, r and .? can be calculated once upon integration of the private key and stored for re-use. In a variant of the invention, two integers r and s are likewise selected for example in the range of [0, 2-1] with 16 To save computation time, exponents d_1 and d_2 in (27) and (28) can be reduced before carrying out the exponentiation modulo (r) and (s), respectively. It follows from (23) and (25) that (29) It follows from (24) and (26) that (30) According to the Chinese Remainder Theorem a number z can easily be calculated from z1 and z2 with (31) Even if r and s are not relatively prime, such a number z exists because z1 = C1 = (mod ggT(r,s)). Since p and q are relatively prime, it follows from (29), (30) and (31) that: z = x d (mod poq) (32) so that the sought number z can easily be determined from the values calculated above. It follows from (21), (25) and (27) that -7- Z1 = C1 (mod r) (33) It follows from (22), (26) and (28) that z2 = C2 (mod s) (34) By checking conditions (33) and (34) an error can be ascertained with high probability. If one of conditions (33) or (34) is violated, the result of the modular exponentiation is to be regarded as erroneous and rejected. In contrast to the method of the print W0-A1-98/52319, numbers b1 and b2 are not dependent on base x in the variant of the method presented here. When applying the RS A method or Rabin signature scheme a private key is typically integrated into a cryptographic device, e.g. smart card, once and then used several times. In the modular exponentiation applied in these methods, exponent d and modulus p-q are fixed elements of the private key. Consequently, values C1 and C2 must only be calculated once upon integration of the key in the cryptographic device, and can then be stored in the device. Storing these values saves two modular exponentiations over the method presented in the print WO-A1-98/52319. According to WO-a1 -98/52319, in a method of implementing public key schemes containing the CRT form of the modular exponentiation operation x d (mod n) where n=pq, for the purpose of making them more resistant to timing and fault attacks, the improvement comprises the steps of: a. selecting two secret integers j 1 and j 2; -8- d. aborting the computation if w_3 is not equal to w_l modulo j_l, or if w_4 is not equal to w_2 modulo j_2; d. otherwise, computing y_l=w_l (mod p), y_2=w_2 (mod q), and combining them by the Chinese Remainder Theorem to obtain the result of x d (mod n). A cryptographic apparatus, for example smart card, with additional hardware for accelerating the modular arithmetic contains fast adding and/or multiplying units in usual embodiments, while the division by a long number required in modular reduction must be performed by usual standard methods, as known for example from Donald Knuth: "The Art of Computer Programming," Volume 2: Seminumerical Algorithms, 2nd Ed., Addison-Wesley, 1981. One of several known methods for simplifying the division operation is to multiply modulus p by number r before exponentiation so that the binary representation of product por contains as many ones as possible; see for example Menezes et al., ibid., pages 598 to 599. Division by a number with as many leading ones as possible is considerably simpler than division by a general number. Multiplier r is chosen according to the invention so that d is relatively prime to (p(r). In the abovementioned variant of the invention, this relative primeness is not required. For each modulus p there is optimal multiplier ropt dependent on the particular technical implementation of the division. If the chosen value of r is slightly smaller smaller than the optimum, product por still contains enough leading ones to permit the division to be done simply. With high probability, number d is relatively prime to at least one of the values (p(ropti), where i =1,..., k, where k is a small number dependent on the implementation. If this is not the case, let r be replaced by 2ior where 2' is a suitable power of two dependent on the implementation. The same substitutions are accordingly also applicable to second prime factor q. Since multipliers r (forp) and s (for q) can be chosen independently of each other, a corresponding choice is likewise possible for multiplier s. - 9 - WE CLAIM: 1. A cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E E =xd (mod poq) with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby for canying out the modular exponentiation two natural numbers r and s are chosen with the condition that d is relatively prime to (kgV(r,s)), and whereby the following computing steps are performed: and whereby (.) is the Eulerian function and kgV(r,s) is the smallest com- monmultiple of r ands, then a number z is calculated according to the Chinese Remainder Theorem from z1 and z2 with z = Z1 (mod por); z=z2 (mod qos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z and thus the result E is checked for computing errors in a checking step, the checking step comprises the following computing operations: calculating the smallest possible natural number e with the property eod =1 (mod (kgV(r,s))) with the aid of the Extended Euclidean Algorithm, calculating the value C = ze (mod kgV(r,s)), comparing the values .x and C modulo kgV(r,s), whereby the result of the modular exponentiation E is rejected as faulty if x ? C (mod kgV(r,s)). 2. A cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E E = xd(modpog) - 10- with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby for carrying out the modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in the interval [1,...,r-1] and [l,...,s-l] and relatively prime to r and s, respectively, are chosen, and whereby b1 and b2 fulfill the condition b1 = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s, the two numbers b1 and b2 are used to calculate according to the Chinese Remainder Theorem values X1 and x2 fulfilling the following conditions: and then the following computing steps are performed: and (.) represents the Eulerian function and kgV(r,s) the smallest common multiple of r and s, then a number 2 is calculated from z1 and z2 according to the Chinese Remainder Theorem with z = z1 (modpor) ;z = z2 (mod qos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z (and thus automatically also the result E) is checked for computing errors in a checking step, the checking step comprises the following computing operations: calculating the numbers whereby d_1 and d_2 are reduced before carrying out the modular exponentiation modulo (r) and (s), respectively, comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C, ? z1 mod r or C2 ? z2 mod 5 holds. 3. A cryptographic method as claimed in claim 2, wherein the numbers r and s are odd ' 4. A cryptographic method as claimed in claims 1 to 3, wherein -the num bers r and s are selected in the range of [0, 2k-1] with 16 5. A cryptographic method as claimed in claims 1 to 4, wherein at least one of the numbers r and s is chosen so that the binary representation of the product por or qos contains as many leading ones as possible. 6. A cryptographic method as claimed in any of claims 1 to 5, wherein' both numbers r and s are chosen so that the binary representation of the product p-r and the product qos contain as many leading ones as possible. 7. A cryptographic method as claimed in one of claims 5 and 6, wherein a) in a first partial step, corresponding optimal numbers ropt and sopt are first selected for at least one of the numbers r and s, respectively, without limita tion by the condition that d is relatively prime to (kgV(r,s)), and b) in a second partial step, adjacent values r = ropt-i and s - sopt-i, i = 0, 1, ..., k, are selected so that d is relatively prime to (kgV(r,s)). 8. A cryptographic method as claimed in one of claims 5 and 6,- wherein a) in a first partial step, corresponding optimal numbers ropt and sopt are se lected for each of the numbers r and s, respectively, without limitation by the condition that d is relatively prime to (kgV(r,s)), and b) in a second partial step, values r = 2loropt ands-2losopt 1 = 0, 1, ...,j, are se lected so that d is relatively prime to (kgV(r,s)). 9. A cryptographic method as claimed in one of claims 5 and 6, wherein a) in a first partial step, at least one of the numbers ropt and sopt is first selected without limitation by the condition that d is relatively prime to (kgV(r,s)), b) in a second partial step, adjacent values r = ropt-i ands = sopt-i, i= 0, 1,..., k, are selected so that d is relatively prime to kgV(r,s)) if such a value exists for i = 0, l,..., k, and - 12- c) in a third partial step, values r = 2loropt and s = 2losopt, i = 0,1,...,j, are selected so that d is relatively prime to (kgV(r,s)) if no value was selected in the second partial step. 10. A cryptographic method as claimed in any of the above claims,-wherein------ it comprises the RSA method. 11. A cryptographic method as claimed in any of the above cteims,-----wherein it comprises the Rabin signature scheme. .12. A cryptographic method as claimed in any of the above claims,-wherein it comprises the Fiat-Shamir identification scheme. 13. A cryptographic apparatus that saves computing operations or computation time while retaining or increasing the security, said apparatus comprising means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E E = xd (modpoq) with a first prime factor p, a second prime factor q, an exponent d and a base X, whereby means for performing a modular exponentiation two natural numbers r and s are chosen with the condition that d is relatively prime to (kgV(r,s))t and whereby the following computing steps are performed: and .) is the Eulerian function and kgV(r,s) is the smallest common multiple of rands, means for calculating of the number z calculated from z1 and z2 according to the Chinese Remainder Theorem withz = z1 (modpor) ;z = Z2 (modqos); means for calculating the result E of the exponentiation by reduction of z modulo poq, - 13- e) means for checking the previously calculated number z (and thus automatically also the result E)for computing errors in a checking step, f) the checking step comprises the following computing operations: fl) calculating the smallest possible natural number e with the property eod=1 (mod kgV(r,s))) with the aid of the Extended Euclidean Algorithm, f2) calculating the value C = ze (mod kgV(r,s)), G) comparing the values x and C modulo kgV(r,s), whereby the result of the modular exponentiation E is rejected as faulty if x C (mod kgV(r,s)). 14. A cryptographic apparatus that saves computing operations or computation time while retaining or increasing the security, said apparatus comprising means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E E=xd (mod poq) with a first prime factorp, a second prime factor q, an exponent d and a base x, whereby b) means for performing a modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in this interval [l,...,s-l] and [1 ,.,.s-t] and rela tively prime to r and s, respectively, are chosen, and whereby b1and b2 ful fill the condition b1 = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s, c) means for using the two numbers b1 and b2 to calculate according to the Chinese Remainder Theorem values x1 and x2 fulfilling the following conditions: and then the following computing steps are performed". > and whereby .) represents the Eulerian function and kgV(r,s) the smallest common multiple of r and s, - 14- d) means for calculating a number z from z1 and z2 according to the Chinese Remainder Theorem with z =z1 (mod por) ;z=z2 (mod qos) ; e) means for calculating the result E of the exponentiation by reduction of z modulo poq, f) means for checking the previously calculated number z (and thus automatically also the result E)for computing errors in a checking step, g) the checking step comprises the following computing operations: gl) calculating the numbers whereby d_1 and d_2 are reduced before carrying out the modular exponentiation modulo r) and (s), respectively, g2) comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C1 z1 mod r or C2 z2 mod s holds. 15. A cryptographic apparatus as claimed in. claim 14,--wherein-the num bers r and s are odd. 16. A cryptographic apparatus as claimed in claims 13 to 15,-wherein-the numbers r and s are selected in the range of [0, 2k -1] with 16 17. A cryptographic apparatus as claimed in claims 13 to 16,-wherein-at least one of the numbers r and s is chosen so that the binary representation of the product por or qos contains as many leading ones as possible. 18. A cryptographic apparatus as claimed in any of claims 13 to 17,-wherein- that both numbers r and s are chosen so that the binary representation of the product por and the product qos contain as many leading ones as possible. 19. A cryptographic apparatus as claimed in one of claims 17 and 18, -wherein- that a) in a first partial step, corresponding optimal numbers ropt and sopt are first selected for at least one of the numbers r and s, respectively, without limitation by the condition that d is relatively prime to (kgV(r,s)), and - 15- b) in a second partial step, adjacent values r= ropl-i and s =-sopt -i, i= 0, 1, ..., k, are selected so that d is relatively prime to (kgV(r,s)). 20. A cryptographic apparatus as claimed in one of claims 17 and 18,-wherein- a) in a first partial step, corresponding optimal numbers ropt and sopt are se lected for each of the numbers r and s, respectively, without limitation by the condition that d is relatively prime to (kgV(r,s)), and b) in a second partial step, values r =2l -ropt and s = 2l osopt 1 = 0, 1, ...,j, are se lected so that d is relatively prime to (kgV(r,s)). 21. A cryptographic apparatus as claimed in one of claims 17 and 18,-wherein- a) in a first partial step, at least one of the numbers ropt and sopt is first selected without limitation by the condition that d is relatively prime to kgV(r,s)), b) in a second partial step, adjacent values r = ropt-i and s = sopt-i, i = 0, 1,..., k, are selected so that d is relatively prime to (kgV(r,s)) if such a value exists for i=0, 1,..., k, and c) in a third partial step, values r = 2 1opt and s = 2lo sopt i = 0, 1,...,j, are se lected so that d is relatively prime to (kgV(r,s)) if no value was selected in the second partial step. 22. A cryptographic apparatus as claimed in any of the above claims,-wherein- it comprises the RSA method. 23. A cryptographic apparatus as claimed in any of the above claims,--wherein- it comprises the Rabin signature scheme. 24. A cryptographic apparatus as claimed in any of the above claims-wherein- it comprises the Fiat-Shamir identification scheme. The invention relates to a cryptographic method with at least one computing step containing a modular exponentiation E according to E = xd (mod poq), with a first prime factor p, a second prime factor q, an exponent d and a number x, whereby the modular exponentiation E is calculated according to the Chinese Remainder Theorem.

Full Text

- 1 -
A CRYPTOGRAPHIC METHOD THAT SAVES COMPUTING OPERATIONS
OR COMPUTATION TIME WHILE RETAINING OR INCREASING
THE SECURITY AND APPARATUS THEREFOR.
The present invention relates to a cryptocraphic method that saves computing operations or computation time while retaining or increasing the security and apparatus therefor.
Cryptographic methods in the form of encryption and signature schemes are becoming increasingly widespread in particular due to the rising importance of electronic commerce. They are normally implemented by means of electronic apparatuses which may comprise for example a programmable universal microcontroller or else a specialized electronic circuit e.g. in the form of an ASIC. An especially interesting form of cryptographic apparatus is the smart card, since if expediently designed technically it can protect secret key data against unauthorized access. There are constant efforts both to improve the execution speed of cryptographic methods and to protect them against all possible kinds of attacks. The invention is suitable in particular for use in connection with smart cards, but is in no way limited thereto. It is instead implementable in connection with all kinds of cryptographic apparatuses.
In a number of known cryptographic methods it is necessary to perform a modular exponentiation according to the equation

where p and q are prime numbers. An especially important cryptographic method that comprises a modular exponentiation step is the RSA method, known for example from Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, "Handbook of Applied Cryptography," Boca Raton: CRC Press, 1997, pages 285 to 291. Use of modular exponentiation is not limited to the RSA method, however, but also includes for example Rabin signatures known from Menezes et al., ibid., pages 438 to 442, and the Fiat-Shamir identification scheme known from Menezes et al., ibid., pages 408 to 410.
The security of cryptographic methods that include modular exponentiation is regularly dependent on the difficulty of factorizing the number N from equation (1) into its prime factors p and q. This problem is only of sufficient complexity for large values N, SO that N should be chosen as great as possible, on the one hand. The computing effort for calculating values by means of modular exponentiation according to equation (I) increases monotonically with the magnitude of N, on the other hand, so

-2-
that it would be desirable from the point of view of practical applicability to be able to restrict the computation time required to acceptable values despite large values of TV.
It is known to increase the computation speed by a factor of four by applying the so-called "Chinese Remainder Theorem," which permits for example larger values N at equal computation time. Instead of evaluating equation (1) directly, a transformation is performed according to
(2)
where
(3) (4)
One consequence of applying the Chinese Remainder Theorem is that the modular exponentiation is no longer done modulo N, i.e. modulo that number concealing its own prime factorization, but successively in a first partial step modulo p and a second partial step modulo q, i.e. knowledge of the prime factorization n = p.q to be kept secret is presupposed in this computing rule and leads to division of the total computing process into a first computing step (3) essentially involving the first prime factor, and a second computing step (4) essentially involving the second prime factor. The advantage is that exponent d in equation (1) must be defined modulo (p.q), whereas the exponents in equation (2) must only be defined modulo (p) or (q), where denotes the Eulerian function.
Interestingly, an attack scheme on such cryptographic methods using modular exponentiation has recently become known by which the information on the prime factorization of Ncan be recovered from the faulty result of a disturbed modular exponentiation by suitable artificial intrusions in the otherwise undisturbed computing sequence, provided the concrete implementation makes use of the Chinese Remainder. Theorem according to equations (2) to (4). This attempt known as the "Bellcore attack" is described for example in Dan Boneh, Richard A. DeMillo and Richard J. Lio-ton: "On the importance of checking cryptographic protocols for faults," Advances in Cryptology - EUROCRYPT, 97. Lecture Notes in Computer Science 1233, Berlin: Sponger, 1997. An encryption device is manipulated by physical intrusions such as

-3-
increasing clock speed, operating voltage or irradiation so that computing errors occur in the execution of the modular exponentiation according to the Chinese Remainder Theorem with a certain, not too great probability. If a computing error occurs only in one of the two terms in equation (2), the two prime factors/p and q can be reconstructed from the erroneous exponentiation result.
The consequence to be drawn from this vulnerability of modular exponentiation implemented by means of the Chinese Remainder Theorem is to first check the result of the computing operation for correctness before it is processed further, particularly before it is outputted in some form, e.g. in the form of a signature.
A trivial countermeasure for the "Bellcore attack" is to effect this correctness check by repeating the computing operation at least once. In case of random computing errors it can be assumed that the result of the first computing operation deviates from that of the check computing operations. The essential disadvantage of this approach is that the computation time is already doubled by one check calculation.
[ The print WO-A1 -9 8/52319 discloses in particular a method for protecting computing operations executing modular exponentiation according to the Chinese Remainder Theorem against the "Bellcore attack." A secret integer j is selected for example in the range of [0, 2k-l] with 16 vl = x(modj.q) (5)
v2 =x (mod j.q) (6)
d1 = d (mod jop)) (7)
d2 = d (mod (joq)) (8)
w1 = v1d1 (mod jop) (9)
w2 = v2 d2(mod joq) (10)
Then it is checked whether it holds that:
w1 = w2 (modj) (11)
If expression (11) can be verified, the following expressions are calculated in the known method:
y1= w1 (mod p) (12)

-4-
y2 = w2 (mod q) (13)
from which the value for
E = xd (mod N) (14)
can then be determined by means of the Chinese Remainder Theorem.
This known method has the advantage over simple check computing operations that the additional computation time required is substantially lower.
In this method, both prime numbers p and q must be multiplied by the same factor d. The print WO-A1-9 8/52319 describes a second method that permits prime numbers p and q to be multiplied by different factors r and s. However, two further exponentiations are possible for the check calculation.
The problem of the invention is to provide a cryptographic method and apparatus that save computing operations or computation time while retaining or increasing the security.

-4A
Accordingly, the present invention provides a cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E
E = xd (mod poq)
with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby
for carrying out the modular exponentiation two natural numbers r and s are chosen with the condition that d is relatively prime to kg V(r,s)), and whereby the following computing steps are performed: X1 = x (mod por) x2 = x (mod qos) d_2=d(mod pos)) d_2 = d (mod (qos)) Z1 =X1d-2 (mod por) z2 = x2 d-2 (mod qos)
and whereby (.) is the Eulerian function and kgV(r.s) is the smallest common multiple of r and s,
then a number z is calculated according to the Chinese Remainder Theorem fromz1 and z2 withz = z1 (modpor) ;z=z2(mod qos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z and thus the result E is checked for computing errors in a checking step,
the checking step comprises the following computing operations: calculating the smallest possible natural number e with the property eod=1 (mod kgV(r.s))) with the aid of the Extended Euclidean Algorithm, calculating the value C=ze (mod kgV(r,s)),
comparing the values x and C modulo kgV(r,s), whereby the result of the modular exponentiation E is rejected as faulty if x ? C (mod kgV(r,s)).
The present invention also provides a cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E
E = xu (mod poq)

4B
with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby
for carrying out the modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in the interval [I,...,r-1] and [1,...s-1] and relatively prime to r and s, respectively, are chosen, and whereby b1 and b2 fulfill the condition b1 = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s,
the two numbers b1 and b2 are used to calculate according to the Chinese Remainder Theorem values x1 and x2 fulfilling the following conditions:
X1 =x (mod p) ,x1 -b1 (mod r)
x2 = x (mod q), x2 = b2 (mod s) and then the following computing steps are performed:
d_1 = d (mod (p))
d_2 = d (mod (q))
z2 =x1 d-2 (mod por)
Z2 = x2 d_2 (mod qos)
and (.) represents the Eulerian function and kgV(r,s) the smallest common multiple of r and s,
then a number z is calculated from z1 and z2 according to the Chinese Remainder Theorem with z = z1 (modpor) ;z=z2 (modqos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z (and thus automatically also the result E) is checked for computing errors in a checking step, the checking step comprises the following computing operations: calculating the numbers
C1 = b1 d_1 (modor)
C2 = b2 d_2 (modos)
whereby d_1 and d_2 are reduced before carrying out the modular exponentiation modulo r) and (s), respectively, comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C, ? z1 mod r or C2 ? z2 mod s holds.

The present invention further provides a cryptographic apparatus comprising : means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E
E = xd (modpoq)
with a first prime factory, a second prime factor q, an exponent d and a base
x, whereby
means for performing a modular exponentiation two natural numbers r and s are
chosen with the condition that d is relatively prime to (kgV(r,s)), and
whereby the following computing steps are performed:
x1 =x (mod por)
x2= x (mod qos)
d_1 = d (mod

d_2 = d (mod (qos))
z1 =x1 d-1 (modpor)
z2 = x2 d-2 (mod qos)
and (.) is the Eulerian function and kgV(r,s) is the smallest common multi-ple of r and s,
means for calculating of the number z calculated from z1 and z2 according to the Chinese Remainder Theorem with z = Z1 (mod pr) z = z2 (mod qos); means for calculating the result E of the exponentiation by reduction of z modulo poq,
e) means for checking the previously calculated number z (and thus automatically also
the result E)for computing errors in a checking step,
f) the checking step comprises the following computing operations:
fl) calculating the smallest possible natural number e with the property eod=1 (mod kgV(r,s))) with the aid of the Extended Euclidean Algorithm,
f2) calculating the value C = ze (mod kgV(r,s)),
f3) comparing the values x and C modulo kgV(r,s), 'whereby the result of the modular exponentiation E is rejected as faulty if x ? C (mod kgV(r,s)).

-4D-
The present invention further provides a cryptographic apparatus that saves computing operations or computation time while retaining or increasing the security, said apparatus comprising means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E E = xd (mod poq)
with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby
b) means for performing a modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in the interval [i,...,r-l] and [1,,..s-1] and relatively prime to r and s, respectively, are chosen, and whereby b1 and b2 fulfill the condition bt = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s,
c) means for using the two numbers b1 and b2 to calculate according to the Chinese Remainder Theorem values X1 and x2 fulfilling the following conditions: x1 = x (modp) ,x1 = b1 (mod r) x2 = x (mod q), x2 = b2 (mod s) and then the following computing steps are performed: d_1 = d (mod p)) d_2 = d (mod (q)) z1 =x1 d-1 (modpor) z2 = x2d-1 (mod qos) and whereby .) represents the Eulerian function and kgV(r,s) the smallest
d) means for calculating a number z from z1 and z2 according to the Chinese Re
mainder Theorem with z=Z1 (mod por) ;z=z2 (mod qos);
e) means for calculating the result E of the exponentiation by reduction of z modulo poq,
f) means for checking the previously calculated number z (and thus automatically
also the result E)for computing errors in a checking step,
g) the checking step comprises the following computing operations:
gl) calculating the numbers
C1 = b1d-1 (modor)
C2=b2d-2 (modos)
whereby d_1 and d_2. are reduced before carrying out the modular exponentiation modulo r) and s), respectively,
g2) comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C1 ?Z1 mod r or C2 ? z2 mod s holds.

4E
Dependent claims 3 to 12 and 15 to 24 show advantageous developments.
As mentioned below, it is advantageous on certain arithmetic and logic units if a modulus in the modular exponentiation has many leading binary ones, so that different factors r and s signify a certain advantage here. Further, there are arithmetic and logic units optimized for modular exponentiation, but the mere data transfer from the central processing unit to the optimized arithmetic and logic unit for exponentiation causes considerable overhead. The present invention saves one exponentiation compared to the above-described method with different factors r and s.
According to the invention, two integers r and s are selected for example in the range of [0, 2k-l] with 16

-5-
Now z1 = x d (modpof) and z2 = x d (mod qos) hold. According to the Chinese Remainder Theorem a'number z can easily be calculated from z1 and z2 with
z = Z1 (mod por); z = z2 (mod qos) ;z = xd (mod p-q-kgV(r,s)) (17)
The numbers r and j must according to the invention be chosen so that d is relatively prime to

s)). Under these circumstances the Extended Euclidean Algorithm can be used to easily find a natural number e with
(18) With the aid of Z and e the number C is calculated as follows:
(19) According to Euler's theorem the following holds:
(20)
By comparison of the two values C and x modulo kgV(r,s) an error can be ascertained with high probability. ifC^x (mod kgV(r,s)) is ascertained, the result of the modular exponentiation is to be regarded as erroneous and rejected.
In RSAjnethods (as also in the Rabin signature scheme) a modular exponentiation is to be performed for generating a digital signature or for decryption, whereby the modulus^^_ajid^ip_Qiient^only_depend on the private key. Consequently the numbers d, e, r and .? can be calculated once upon integration of the private key and stored for re-use.
In a variant of the invention, two integers r and s are likewise selected for example in the range of [0, 2*-1] with 16

To save computation time, exponents d_1 and d_2 in (27) and (28) can be reduced before carrying out the exponentiation modulo (r) and (s), respectively. It follows from (23) and (25) that
(29) It follows from (24) and (26) that
(30)
According to the Chinese Remainder Theorem a number z can easily be calculated from z1 and z2 with
(31)
Even if r and s are not relatively prime, such a number z exists because z1 = C1 =
(mod ggT(r,s)). Since p and q are relatively prime, it follows from (29), (30) and (31) that:
z = x d (mod poq) (32)
so that the sought number z can easily be determined from the values calculated above.
It follows from (21), (25) and (27) that

-7-
Z1 = C1 (mod r) (33)
It follows from (22), (26) and (28) that
z2 = C2 (mod s) (34)
By checking conditions (33) and (34) an error can be ascertained with high probability. If one of conditions (33) or (34) is violated, the result of the modular exponentiation is to be regarded as erroneous and rejected.
In contrast to the method of the print W0-A1-98/52319, numbers b1
and b2 are not dependent on base x in the variant of the method presented here. When applying the RS A method or Rabin signature scheme a private key is typically integrated into a cryptographic device, e.g. smart card, once and then used several times. In the modular exponentiation applied in these methods, exponent d and modulus p-q are fixed elements of the private key. Consequently, values C1 and C2 must only be calculated once upon integration of the key in the cryptographic device, and can then be stored in the device. Storing these values saves two modular exponentiations over the method presented in the print WO-A1-98/52319.
According to WO-a1 -98/52319, in a method of implementing public key schemes containing the CRT form of the modular exponentiation operation x d (mod n) where n=p*q, for the purpose of making them more resistant to timing and fault attacks, the improvement comprises the steps of:
a. selecting two secret integers j 1 and j 2;

-8-
d. aborting the computation if w_3 is not equal to w_l modulo j_l, or if w_4 is not equal to w_2 modulo j_2; d. otherwise, computing y_l=w_l (mod p), y_2=w_2 (mod q), and combining them by the Chinese Remainder Theorem to obtain the result of x d (mod n).
A cryptographic apparatus, for example smart card, with additional hardware for accelerating the modular arithmetic contains fast adding and/or multiplying units in usual embodiments, while the division by a long number required in modular reduction must be performed by usual standard methods, as known for example from Donald Knuth: "The Art of Computer Programming," Volume 2: Seminumerical Algorithms, 2nd Ed., Addison-Wesley, 1981. One of several known methods for simplifying the division operation is to multiply modulus p by number r before exponentiation so that the binary representation of product por contains as many ones as possible; see for example Menezes et al., ibid., pages 598 to 599. Division by a number with as many leading ones as possible is considerably simpler than division by a general number.
Multiplier r is chosen according to the invention so that d is relatively prime to (p(r). In the abovementioned variant of the invention, this relative primeness is not required. For each modulus p there is optimal multiplier ropt dependent on the particular technical implementation of the division. If the chosen value of r is slightly smaller
smaller than the optimum, product por still contains enough leading ones to permit the division to be done simply. With high probability, number d is relatively prime to at least one of the values (p(ropti), where i =1,..., k, where k is a small number dependent on the implementation.
If this is not the case, let r be replaced by 2ior where 2' is a suitable power of two dependent on the implementation.
The same substitutions are accordingly also applicable to second prime factor q. Since multipliers r (forp) and s (for q) can be chosen independently of each other, a corresponding choice is likewise possible for multiplier s.

- 9 -
WE CLAIM:
1. A cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E
E =xd (mod poq)
with a first prime factor p, a second prime factor q, an exponent d and a base
x, whereby
for canying out the modular exponentiation two natural numbers r and s are
chosen with the condition that d is relatively prime to (kgV(r,s)), and
whereby the following computing steps are performed:

and whereby (.) is the Eulerian function and kgV(r,s) is the smallest com-
monmultiple of r ands,
then a number z is calculated according to the Chinese Remainder Theorem from z1 and z2 with z = Z1 (mod por); z=z2 (mod qos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z and thus the result E is checked for computing errors in a checking step,
the checking step comprises the following computing operations: calculating the smallest possible natural number e with the property eod =1 (mod (kgV(r,s))) with the aid of the Extended Euclidean Algorithm, calculating the value C = ze (mod kgV(r,s)),
comparing the values .x and C modulo kgV(r,s), whereby the result of the modular exponentiation E is rejected as faulty if x ? C (mod kgV(r,s)).
2. A cryptographic method that saves computing operations or computation time while retaining or increasing the security, said method having at least one computing step containing a modular exponentiation E E = xd(modpog)

- 10-
with a first prime factor p, a second prime factor q, an exponent d and a base x, whereby
for carrying out the modular exponentiation two natural numbers r and s, and two numbers b1 and b2 in the interval [1,...,r-1] and [l,...,s-l] and relatively prime to r and s, respectively, are chosen, and whereby b1 and b2 fulfill the condition b1 = b2 (mod ggT(r,s)), where ggT(r,s) designates the greatest common divisor of r and s,
the two numbers b1 and b2 are used to calculate according to the Chinese Remainder Theorem values X1 and x2 fulfilling the following conditions:

and then the following computing steps are performed:

and (.) represents the Eulerian function and kgV(r,s) the smallest common multiple of r and s,
then a number 2 is calculated from z1 and z2 according to the Chinese Remainder Theorem with z = z1 (modpor) ;z = z2 (mod qos) ; the result E of the exponentiation is calculated by reduction of z modulo poq, the previously calculated number z (and thus automatically also the result E) is checked for computing errors in a checking step, the checking step comprises the following computing operations: calculating the numbers

whereby d_1 and d_2 are reduced before carrying out the modular exponentiation modulo (r) and (s), respectively, comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s, whereby the result of the modular exponentiation E is rejected as faulty if C,
? z1 mod r or C2 ? z2 mod 5 holds.

3. A cryptographic method as claimed in claim 2, wherein the numbers r and s
are odd '
4. A cryptographic method as claimed in claims 1 to 3, wherein -the num
bers r and s are selected in the range of [0, 2k-1] with 16 5. A cryptographic method as claimed in claims 1 to 4, wherein at least
one of the numbers r and s is chosen so that the binary representation of the product por or qos contains as many leading ones as possible.
6. A cryptographic method as claimed in any of claims 1 to 5, wherein'
both numbers r and s are chosen so that the binary representation of the product p-r and the product qos contain as many leading ones as possible.
7. A cryptographic method as claimed in one of claims 5 and 6, wherein
a) in a first partial step, corresponding optimal numbers ropt and sopt are first
selected for at least one of the numbers r and s, respectively, without limita
tion by the condition that d is relatively prime to (kgV(r,s)), and
b) in a second partial step, adjacent values r = ropt-i and s - sopt-i, i = 0, 1, ..., k,
are selected so that d is relatively prime to (kgV(r,s)).

8. A cryptographic method as claimed in one of claims 5 and 6,- wherein
a) in a first partial step, corresponding optimal numbers ropt and sopt are se
lected for each of the numbers r and s, respectively, without limitation by
the condition that d is relatively prime to (kgV(r,s)), and
b) in a second partial step, values r = 2loropt ands-2losopt 1 = 0, 1, ...,j, are se
lected so that d is relatively prime to (kgV(r,s)).
9. A cryptographic method as claimed in one of claims 5 and 6, wherein
a) in a first partial step, at least one of the numbers ropt and sopt is first selected
without limitation by the condition that d is relatively prime to (kgV(r,s)),
b) in a second partial step, adjacent values r = ropt-i ands = sopt-i, i= 0, 1,..., k,
are selected so that d is relatively prime to kgV(r,s)) if such a value exists
for i = 0, l,..., k, and

- 12-
c) in a third partial step, values r = 2loropt and s = 2losopt, i = 0,1,...,j, are selected so that d is relatively prime to (kgV(r,s)) if no value was selected in the second partial step.
10. A cryptographic method as claimed in any of the above claims,-wherein------
it comprises the RSA method.
11. A cryptographic method as claimed in any of the above cteims,-----wherein
it comprises the Rabin signature scheme.
.12. A cryptographic method as claimed in any of the above claims,-wherein
it comprises the Fiat-Shamir identification scheme.
13. A cryptographic apparatus that saves computing operations or computation time while retaining or increasing the security, said apparatus comprising means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E
E = xd (modpoq)
with a first prime factor p, a second prime factor q, an exponent d and a base
X, whereby
means for performing a modular exponentiation two natural numbers r and s are
chosen with the condition that d is relatively prime to (kgV(r,s))t and
whereby the following computing steps are performed:

and .) is the Eulerian function and kgV(r,s) is the smallest common multiple of rands,
means for calculating of the number z calculated from z1 and z2 according to the Chinese Remainder Theorem withz = z1 (modpor) ;z = Z2 (modqos); means for calculating the result E of the exponentiation by reduction of z modulo poq,

- 13-
e) means for checking the previously calculated number z (and thus automatically also
the result E)for computing errors in a checking step,
f) the checking step comprises the following computing operations:
fl) calculating the smallest possible natural number e with the property eod=1
(mod kgV(r,s))) with the aid of the Extended Euclidean Algorithm, f2) calculating the value C = ze (mod kgV(r,s)), G) comparing the values x and C modulo kgV(r,s), whereby the result of the
modular exponentiation E is rejected as faulty if x C (mod kgV(r,s)). 14. A cryptographic apparatus that saves computing operations or computation time while retaining or increasing the security, said apparatus comprising means for executing, with at least one exponentiation device, a computing step containing a modular exponentiation E
E=xd (mod poq)
with a first prime factorp, a second prime factor q, an exponent d and a base
x, whereby
b) means for performing a modular exponentiation two natural numbers r and s,
and two numbers b1 and b2 in this interval [l,...,s-l] and [1 ,.,.s-t] and rela
tively prime to r and s, respectively, are chosen, and whereby b1and b2 ful
fill the condition b1 = b2 (mod ggT(r,s)), where ggT(r,s) designates the
greatest common divisor of r and s,
c) means for using the two numbers b1 and b2 to calculate according to the Chinese
Remainder Theorem values x1 and x2 fulfilling the following conditions:

and then the following computing steps are performed".
> and whereby .) represents the Eulerian function and kgV(r,s) the smallest
common multiple of r and s,

- 14-
d) means for calculating a number z from z1 and z2 according to the Chinese Remainder Theorem with z =z1 (mod por) ;z=z2 (mod qos) ;
e) means for calculating the result E of the exponentiation by reduction of z modulo poq,
f) means for checking the previously calculated number z (and thus automatically
also the result E)for computing errors in a checking step,
g) the checking step comprises the following computing operations:
gl) calculating the numbers

whereby d_1 and d_2 are reduced before carrying out the modular exponentiation modulo r) and (s), respectively, g2) comparing the values z1 and C1 modulo r as well as z2 and C2 modulo s,
whereby the result of the modular exponentiation E is rejected as faulty if C1 z1 mod r or C2 z2 mod s holds.
15. A cryptographic apparatus as claimed in. claim 14,--wherein-the num
bers r and s are odd.
16. A cryptographic apparatus as claimed in claims 13 to 15,-wherein-the
numbers r and s are selected in the range of [0, 2k -1] with 16 17. A cryptographic apparatus as claimed in claims 13 to 16,-wherein-at
least one of the numbers r and s is chosen so that the binary representation of the product por or qos contains as many leading ones as possible.
18. A cryptographic apparatus as claimed in any of claims 13 to 17,-wherein-
that both numbers r and s are chosen so that the binary representation of the product por and the product qos contain as many leading ones as possible.
19. A cryptographic apparatus as claimed in one of claims 17 and 18, -wherein-
that
a) in a first partial step, corresponding optimal numbers ropt and sopt are first selected for at least one of the numbers r and s, respectively, without limitation by the condition that d is relatively prime to (kgV(r,s)), and

- 15-
b) in a second partial step, adjacent values r= ropl-i and s =-sopt -i, i= 0, 1, ..., k, are selected so that d is relatively prime to (kgV(r,s)).
20. A cryptographic apparatus as claimed in one of claims 17 and 18,-wherein-
a) in a first partial step, corresponding optimal numbers ropt and sopt are se
lected for each of the numbers r and s, respectively, without limitation by
the condition that d is relatively prime to (kgV(r,s)), and
b) in a second partial step, values r =2l -ropt and s = 2l osopt 1 = 0, 1, ...,j, are se
lected so that d is relatively prime to (kgV(r,s)).
21. A cryptographic apparatus as claimed in one of claims 17 and 18,-wherein-
a) in a first partial step, at least one of the numbers ropt and sopt is first selected
without limitation by the condition that d is relatively prime to kgV(r,s)),
b) in a second partial step, adjacent values r = ropt-i and s = sopt-i, i = 0, 1,..., k,
are selected so that d is relatively prime to (kgV(r,s)) if such a value exists
for i=0, 1,..., k, and
c) in a third partial step, values r = 2 1opt and s = 2lo sopt i = 0, 1,...,j, are se
lected so that d is relatively prime to (kgV(r,s)) if no value was selected in
the second partial step.
22. A cryptographic apparatus as claimed in any of the above claims,-wherein-
it comprises the RSA method.
23. A cryptographic apparatus as claimed in any of the above claims,--wherein-
it comprises the Rabin signature scheme.
24. A cryptographic apparatus as claimed in any of the above claims-wherein-
it comprises the Fiat-Shamir identification scheme.
The invention relates to a cryptographic method with at least one computing step containing a modular exponentiation E according to E = xd (mod poq), with a first prime factor p, a second prime factor q, an exponent d and a number x, whereby the modular exponentiation E is calculated according to the Chinese Remainder Theorem.

Documents:

« Previous Patent

Next Patent »

Patent Number

200026

Indian Patent Application Number

IN/PCT/2002/01333/KOL

PG Journal Number

11/2007

Publication Date

16-Mar-2007

Grant Date

16-Mar-2007

Date of Filing

25-Oct-2002

Name of Patentee

GIESECKE & DEVRIENT GMBH,

Applicant Address

PRINZREGENTENSTRASSE 159, 81677 MUNCHEN, ( A GERMANY COMPANY )

Inventors:

#	Inventor's Name	Inventor's Address
1	SEYSEN MARTIN	SCHLEISSHEIMER STRASSE 339, 80809, MUNCHEN

PCT International Classification Number

G06F 7/72

PCT International Application Number

PCT/EP01/05532

PCT International Filing date

2001-05-15

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	10024325.8	2000-05-17	Germany