Title of Invention

METHOD FOR DETERMINING, IN A WAY THAT IS PROTECTED AGAINST SPYING, THE MODULE INVERSE b OF A VALUE a WITH A MODULE n FOR A CRYPTOGRAPHIC APPLICATION

Abstract

The invention relates to methods for αn espionage-protected determination of the modular inverse b of a value a to the modulus n for a cryptographic application. According to said method, αn auxilliary value β and αn auxiliary modulus δ are determined at least in accordance with the value α , the modulus n and also at least one masking parameter r, αn auxiliary inverse β' is determined as the modular inverse of the auxiliary value β to the auxiliary modulus δ and the modular inverse b is determined at least in accordance with the auxiliary inverse β', the masking parameter(s) r and the auxiliary value β and/or the auxiliary modulus δ. The invention also relates to a corresponding computer program product and a portable data carrier. The invention provides a modular inversion method that is protected against espionage, which is suitable for security-critical applications, e.g. Cryptographic calculations in a portable data carrier.

Full Text

METHOD FOR DETERMINING, IN A WAY THAT IS PROTECTED AGAINST SPYING, THE MODULE INVERSE B OF A VALUE A WITH A MODULE TV FOR A CRYPTOGRAPHIC APPLICATION The present invention relates to a method for determining, in a way that is protected against spying, the module inverse b of a value a with a module n for a cryptographic application. And, generality relates to the technical doimain of cryptography and more particularly to a technique for modular inversion provided for cryptographic purposes. The invention is provided in particular for use in portable data carriers, which czan be configured e.g. as smart cards in various constructional forms or as chip modules. In the domain of cryptography methods for modular inversion are employed, for example, in generating a pair of keys for the RSA encoding or signature method described in U.S. patent 4,405,829. The RSA method uses a public key (e, m) and a secret private key d, wherein the value m is the product of two large prime numbers β and q. To calculate the key pair, firstly the values β, q and e are established. The private key d is then calculated as the modular inverse of e in relation to the module (p - l)(q -1). This means that the number d fulfils the equation 1 = ed mod (p - l)(q -1). In the calculation the private key d and the module (p - l)(q -1) must remain secret. In general for two given whole numbers a and n the modular inverse of a in relation to the module n is defined as the number b to which 0 1 = ab mod n applies. A number b of this kind exists if a and n are relatively prime. Algorithms for calculating the modular inverse of a given value a in relation to a given module n are known per se. For example, the extended Euclidian algorithm is described on pages 325 to 327 of the book by Donald E. Knuth, "The Art of Computer Programming", Vol. 2, second edition, Addison-Wesley, 1981. A modification of the extended Euclidian algorithm particularly advantageous in connection with binary numbers is Stein's method, described on pages 321 to 324 of said book in connection with exercise 35 on page 339 and the solution to it on page 606. In the two methods mentioned there is the problem, however, that in direct implementation of the algorithm as a program the processed program code and therefore also physical parameters such as running time or power consumption depend to a large extent on the input data. Therefore, by analysis of the power consumption curve, the program running time or other measured values conclusions can be drawn as to the input values a and n. Examples of these and other opportunities for attack in connection with portable data carriers are described in section δ.2.4.1 (pages 482 to 499) of the book "Handbuch der Chipkarten" by W. Rankl and W. Effing, third edition, Hanser, 1999. Presumably corresponding opportunities for attack are also possible in other methods for modular inversion than those described above as examples. If at least one of the input values a or n has to be kept secret, opportunities for attack like those mentioned above pose a security risk. For instance, in the already described example of generating key pairs for the RSA method there is a danger that during calculation of the modular inversion of e in relation to the module (p - l)(q -1) αn attacker will spy out either the module (p - 1){q -1) to be kept secret or directly the result of the calculation, namely the private key d. Said security problems are particularly critical if the method for modular inversion is executed by a processor of a portable data carrier, a smart card, for example, or a chip module. A first reason for this is that portable data carriers of this kind are often used for applications where security is critical, e.g. in connection with financial transactions, access control or the signature of legally binding documents. Secondly, portable data carriers are typically in the possession of the attacker while the method is being executed, so the attacker has all the access and analysis opportunities for spying out the values to be kept secret. The object of the invention is therefore to provide a method for modular inversion which is secured against spying and is suitable for applications where security is critical, such as, e.g. cryptographic calculations on a portable data carrier. In particular, the method should have as low a susceptibility to attacks by running time analysis or power consumption analysis as possible. Accordingly, the present invention provides a method for determining, in a way that is protected against spying, the modular inverse b of a value a with a module n for a cryptographic application, comprising the steps of: (a) determining αn auxiliary value β and αn auxiliary module δ , which are relatively prime to each other, at least depending on the value a, the module n and at least one masking parameter r in such a way that the auxiliary value β differs from the value a and/or the auxiliary module δ differs from the module n, (b) determining αn auxiliary inverse β' as the modular inverse of the auxiliary value β in relation to the auxiliary module 5, and (c) determining the modular inverse b at least depending on the following values: the auxiliary inverse β', the at least one masking parameter r , and the auxiliary value β and/or the auxiliary module δ. Preferably, the at least one masking parameter r is randomly chosen, and/or the at least one masking parameter r has the same order of magnitude as the module n. The value a or the module n is multiplied by the masking parameter r, and the thereby obtained product has some influence on the calculation of the auxiliary value β and/or the auxiliary module δ. In step (a) determining the auxiliary value β and the auxiliary module δ further preferably takes place depending on at least one auxiliary parameter s, which in step (c) has at the most αn indirect influence on determining the inverse b. The at least one auxiliary parameter s is preferably randomly chosen, and/or at least one auxiliary parameter s has the same order of magnitude as the value a. In step (a) the auxiliary value β and the auxiliary module δ are determined in such a way that the equations ra = αn + β and sn = γa + δ are fulfilled for predetermined values α and γ or values α and γ calculated in step (a). The inverse b is determined by evaluating the equation b = β'r + δ'γ mod n with δ' = (ββ' - 1) / δ . In step a) the auxiliary value β and the auxiliary module δ are determined in such a way that the equations ra = αn + δ and sn = γa + β are fulfilled for predetermined values α and γ or values α and γ calculated in step a). The inverse b is determined by evaluating the equation b = -(δ'r + β' γ) mod n with δ' = (ββ' - 1) / δ. The auxiliary value β and/ or the auxiliary module δ is/are determined by one division with remainder in each case, so that at least one of the inequations 0 cryptographic application is the key pair determination in αn RSA encoding method or αn RSA signature method. The invention starts from the basic idea of not feeding the input data (namely the value a and the module n) directly to a method for modular inversion, but first transforming them in a suitable way into αn auxiliary value β and αn auxiliary module δ. Here, at least one masking parameter r influencing the transformation is chosen, e.g. randomly or quasi-randomly or in some other suitable manner, in such a way that no sufficient information on the input data to be kept secret or the part of the input data to be kept secret can be derived even with knowledge of the auxiliary value β and/or the auxiliary module δ. From the auxiliary value β and the auxiliary module δ αn auxiliary inverse β' is then determined according to a method for modular inversion known per se. Even if this inversion method is possibly accessible to one of the initially mentioned opportunities for attack, spying out the auxiliary value β and/or the auxiliary module δ and/or the auxiliary inverse β' is of no advantage to the attacker, because they contain the initial data at least partially in masked form, namely depending on at least one masking parameter r. Finally, the initial transformation is effectively reversed by calculating the modular inverse b depending on the auxiliary inverse β'. The at least one masking parameter r and at least one of the values β and δ and also, where appropriate, further values also have some influence on this reverse transformation. By means of the forward and reverse transformation provided according to the invention the values to be kept secret are therefore disguised or masked before the critical calculation section. This disguising or masking is reversed again after the calculation of the modular inverse which is at risk from spying, in order to obtain the desired result. The calculations serving for masking and unmasking are secured against the opportunities for attack to be taken into account in this case. The entire method is in this way secured against spying and also suitable for critical applications. A certain extra outlay is required for the calculations serving for masking and unmasking, though overall this is not of any particular significance.. In preferred configurations both the auxiliary value β and the auxiliary module δ are masked in the sense that they differ from the basic value a and the module n, respectively. In other embodiment forms of the invention, on the other hand, it is provided to perform the masking only in respect of one of these values. Then either the auxiliary value β is identical to the value a or the auxiliary module δ is identical to the module n. These configurations can be employed in particular if one of the values a and n does not need to be kept secret. In preferred configurations the masking parameter r is chosen again at random for each individual execution of the method, in that, for example, a suitable random number algorithm is called. In embodiment alternatives, on the other hand, the masking parameter r may remain constant for several calculations or be stepped by a simple algorithm which does not fulfil any strict requirements with regard to random distribution. This too may be sufficient to produce adequate security against spying. The masking parameter r has preferably approximately the same order of magnitude as the module n. This may mean, e.g. that the values r and n differ in length as binary or decimal numbers at the most by 20 per cent or at the most by half. It is preferably provided to distort the value a and/or the module n by multiplying it by the masking parameter r, wherein the auxiliary value β and/or the auxiliary module δ are calculated depending on the product. In preferred configurations, as well as the masking parameter r, at least one other auxiliary parameter s is provided, which is likewise used for calculating the masked values β and/or δ, but which is no longer directly utilised in later determining of the modular inverse. The auxiliary parameter s does, however, have αn indirect influence on this calculation, because it usually influences at least one of the values β, β' and δ. The above-mentioned preferred characteristics of the masking parameter r also apply correspondingly to the auxiliary parameter s in preferred configurations. The auxiliary value β and the auxiliary module δ result in each case as the difference between a multiple of the value a and a multiple of the module n. It can in particular be provided to determine the auxiliary value β and the auxiliary module δ according to the equations ra = αn + β and sn = γa + δ or according to the equations ra = αn + δ and sn = γa + p. If, in addition, the inequation 0 0 remainder in each case. The computer program product according to the invention has program commands to implement the method according to the invention. A computer program product of this kind may be, for example, a semiconductor memory or a diskette or a CD-ROM on which a calculation program according to the invention is stored. A computer program product of this kind can be provided in particular for use in the production of smart cards. In preferred configurations the computer program product and/ or the portable data carrier are further developed with features corresponding to the above-described features and/or those mentioned in the dependent method claims. Further features, advantages and objects of the invention are apparent from the following precise description of αn embodiment example and several embodiment alternatives. Reference is made to the schematic drawings in which the (single) Fig. 1 shows a flow chart of the execution of the method in an embodiment example of the invention. The method schematically illustrated in Fig. 1 is provided to be executed by a processor of a portable data carrier, in particular a smart card or a chip module. The method is for this purpose implemented in the form of program commands for this processor, stored in a ROM or EEPROM of the data carrier. In the present embodiment example the method is used in the key pair determination for αn RSA encoding method or αn RSA signature method. In embodiment variants of the invention, on the other hand, the method is used for other cryptographic purposes. The method starts from a preset value a and a module n and calculates from these the modular inverse b, in other words the value 0 1 = ab mod n applies. In a first step 10 the value a and the module n are transformed for this, in order to determine αn auxiliary value β and an auxiliary module δ. In the present embodiment example step 10 has four partial steps 12,14,16,18 which can also be executed in embodiment alternatives in a different order or completely or partially interleaved. In the first partial step 12 a random masking parameter r is determined which has approximately the same order of magnitude as the value n. A random number generator known per se and implemented by software is employed for this. The product of the masking parameter r and the value a is divided in partial step 14 by the module n into whole numbers with remainder. The whole-number quotient a is not further required, whereas the remainder β serves as auxiliary value for the further method. Partial steps 16 and 18 correspond to partial steps 12 and 14 just described. In partial step 16 a random auxiliary parameter s is determined and in partial step 18 the product of the auxiliary parameter s with the module n is divided by the value a. Both the whole-number quotient γ and the remainder δ are required in the following steps; the remainder δ is here also designated as auxiliary module δ. In step 20, according to a method for modular inversion known per se, for example according to the extended Euclidian algorithm or Stein's method, an auxiliary inverse β' of the auxiliary value β is calculated in relation to the auxiliary module δ. In other words the value β' has the property 1 = ββ' mod δ. It can occur that the calculation of the auxiliary inverse β' fails, because the values β and δ are not relatively prime and therefore no inverse β' of β exists. If this case occurs in step 20, a return 22 to the beginning of step 10 is triggered. New random values r and s are then chosen. The probability of a return of this kind taking place is approximately 40%, if a and n are relatively prime. It is therefore improbable that αn excessive number of returns 22 will have to be executed. The probability of more than four new pairs of random numbers r and s having to be calculated is only approximately one per cent, for example. If a and n are not relatively prime, the return 22 is always executed, so the method shown in Fig. 1 would not terminate. If this method were therefore to be employed in a context in which it is not certain from the start whether a and n are relatively prime, the use of a return counter is provided. The return counter monitors the number of returns 22 which occur during αn execution of the method. If a preset maximum number of returns 22 is exceeded, the method of Fig. 1 is terminated. A further condition for the correct execution of the method is the exclusion of the trivial cases a = 1 and n = 1 (which are of no interest in practice), as in these cases the method always fails. After determination of the auxiliary inverse β' in step 20, in step 24 the inverse b is calculated, in that firstly a calculation of αn intermediate value δ' = (ββ' -1)/δ and then the final calculation b = β'r + δ'y mod n are performed. The value b is the inverse sought, which is now available to the cryptographic application. Steps 10 and 24 can easily be secured against the initially described attacks by running time analysis and power consumption analysis, because algorithms are available for the calculations performed there which offer few opportunities for attack. Though the inverse calculation in step 20 is at risk from spying, by analysing this step αn attacker could at the most obtain knowledge about the auxiliary value β and/or the auxiliary module δ. These values were masked in step 10 in respect of the input values a and n to be kept secret, as the random masking parameter r and the random auxiliary parameter s had some influence on the calculation of β and δ. Possible knowledge of the values β and δ therefore does not allow αn attacker to draw any security-damaging conclusions as to the input values a and n. In alternative configurations of the method of Fig. 1, in partial steps 14 and 18 the roles of the values β and δ are reversed. In this case in step 24 instead of the equation b = β'r + δ'y mod n, the equation b = -(δ'r + β'y) mod n is used. In further embodiment alternatives, in partial step 14 and/or partial step 16 instead of performing a division with remainder, the values α and/or γ are chosen at random or according to some other suitable method. In this case in partial step 14 the auxiliary value β results from β = ra - αn and, respectively, in partial step 18 the auxiliary module δ results from δ = sn- ya. Finally, configurations of the invention are also provided in which either in partial step 12 the masking parameter r = 1 and in partial step 14 the value a = 0 are set (β = a then applies) or in which in partial step 16 the auxiliary parameter s = 1 and in partial step 18 the value γ = 0 are set δ = n then applies). Further embodiment alternatives can be obtained in particular by combining the previously described possibilities. WE CLAIM: 1. Method for determining, in a way that is protected against spying, the modular inverse b of a value a with a module n in a cryptographic application, wherein the cryptographic application is a key pair determination in αn RSA encoding method or αn RSA signature method, wherein the method is executed by a processor and comprises the following steps: a) determining (10) αn auxiliary value β and αn auxiliary module δ, which are relatively prime to each other, at least depending on the value a, the module n and at least one masking parameter r and at least one auxiliary parameter s in such a way that the auxiliary value β differs from the value a and/or the auxiliary module δ differs from the module n, wherein the at least one masking parameter r is randomly chosen and/or has the same order of magnitude as the module n , and wherein the at least one auxiliary parameter s is randomly chosen and/or has the same order of magnitude as the value a, b) determining (20) αn auxiliary inverse β' as the modular inverse of the auxiliary value β in relation to the auxiliary module δ, and c) determining (24) the modular inverse b at least depending on ' the following values: the auxiliary inverse β', the at least one masking parameter r, and the auxiliary value β and/or the auxiliary module δ, wherein the auxiliary parameter s does not directly influence the determination of the modular inverse b, wherein in step a) the auxiliary value β and the auxiliary module δ are determined according to the equations ra = αn + β and sn = γa + δ with 0 determined by evaluating the equation b = β'r + δ'γ mod n with δ' = (ββ' -1)/ δ, or wherein in step a) the auxiliary value β and the auxiliary module δ are determined according to the equations ra = αn + δ and sn = γa + β with 0 determined by evaluating the equation b = -(δ'r + β'y) mod n with δ' = (ββ' - 1)/δ . 2. Portable data carrier, in particular smart card or chip module, which is equipped for executing a method with the features as claimed in claim 1. ABSTRACT METHOD FOR DETERMINING, IN A WAY THAT IS PROTECTED AGAINST SPYING, THE MODULE INVERSE B OF A VALUE A WITH A MODULE N FOR A CRYPTOGRAPHIC APPLICATION The invention relates to methods for αn espionage-protected determination of the modular inverse b of a value a to the modulus n for a cryptographic application. According to said method, αn auxilliary value β and αn auxiliary modulus δ are determined at least in accordance with the value α , the modulus n and also at least one masking parameter r, αn auxiliary inverse β' is determined as the modular inverse of the auxiliary value β to the auxiliary modulus δ and the modular inverse b is determined at least in accordance with the auxiliary inverse β', the masking parameter(s) r and the auxiliary value β and/or the auxiliary modulus δ. The invention also relates to a corresponding computer program product and a portable data carrier. The invention provides a modular inversion method that is protected against espionage, which is suitable for security-critical applications, e.g. Cryptographic calculations in a portable data carrier.

Documents:

1531-KOLNP-2004-(03-09-2012)-AMANDED CLAIMS.pdf

1531-KOLNP-2004-(03-09-2012)-CORRESPONDENCE.pdf

1531-KOLNP-2004-(03-09-2012)-OTHERS.pdf

1531-kolnp-2004-abstract.pdf

1531-kolnp-2004-assignment.pdf

1531-kolnp-2004-claims.pdf

1531-KOLNP-2004-CORRESPONDENCE 1.3.pdf

1531-KOLNP-2004-CORRESPONDENCE-1.1.pdf

1531-KOLNP-2004-CORRESPONDENCE-1.2.pdf

1531-kolnp-2004-correspondence.pdf

1531-kolnp-2004-description (complete).pdf

1531-kolnp-2004-drawings.pdf

1531-kolnp-2004-examination report.pdf

1531-kolnp-2004-form 1.pdf

1531-kolnp-2004-form 18.pdf

1531-KOLNP-2004-FORM 3 1.1.pdf

1531-kolnp-2004-form 3.pdf

1531-kolnp-2004-form 5.pdf

1531-kolnp-2004-gpa.pdf

1531-KOLNP-2004-GRANTED-ABSTRACT.pdf

1531-KOLNP-2004-GRANTED-CLAIMS.pdf

1531-KOLNP-2004-GRANTED-DESCRIPTION (COMPLETE).pdf

1531-KOLNP-2004-GRANTED-DRAWINGS.pdf

1531-KOLNP-2004-GRANTED-FORM 1.pdf

1531-KOLNP-2004-GRANTED-FORM 2.pdf

1531-KOLNP-2004-GRANTED-SPECIFICATION.pdf

1531-KOLNP-2004-INTERNATIONAL PUBLICATION.pdf

1531-KOLNP-2004-OTHERS.pdf

1531-KOLNP-2004-REPLY TO EXAMINATION REPORT 1.1.pdf

1531-kolnp-2004-reply to examination report.pdf

1531-kolnp-2004-specification.pdf

1531-KOLNP-2004-TRANSLATED COPY OF PRIORITY DOCUMENT.pdf