Method for secure distribution of data

[0002] This invention elates to a methos for secure distribution of data and/or programs.

[0003] Methods for distribution of software SW by an issuing unit to a large number of like terminals or smart cards are being increasingly used in particular through the possibilities of telecommunication. The issuing unit generates an electronic signature of software SW using a public-key method in order to ensure the authenticity of software SW.

[0004] The issuing unit uses a commonly known method to calculate for software SW to be signed certificate M containing, along with other data, mainly hash value H(SW) dependent on the software. H(SW) is a publicly known hashing method. The issuing unit encrypts certificate M with its private key D. The result of said encryption is electronic signature S. The issuing unit sends software SW together with signature S to the terminal or smart card. There, value M of the generated certificate is calculated from signature S using public key E=D⁻¹of the issuing unit. Further, the terminal or smart card, i.e. the receiving unit, calculates hash value H(SW) of software SW and tests whether H(SW) is correctly entered in certificate M. If this is the case, the receiving unit accepts software SW, otherwise it rejects software SW.

[0005] The best known public-key method for generating electronic signatures is the RSA method. A variant of the RSA method is the Rabin method or a variant of the Rabin method according to Williams.

[0006] The issuing unit randomly selects two primes P=3 mod 8 and Q=7 mod 8. These constitute the private key of the issuing unit. The public key is the value N=P*Q. For signing message M the issuing unit calculates the signature

[0007] S=M^½ mod (P*Q).

[0008] The receiving unit can verify the signature by calculating

[0009] M=S²mod N.

[0010] The security of the Rabin method is based on the fact that it is easy to extract the square root of a number modulo a prime (if one exists), while extracting the square root of a randomly selected number modulo a composite number is at least as difficult as factorizing that composite number.

[0011] Not every number is a quadratic residue modulo prime P or Q; furthermore, quadratic residues mod P and Q normally have four square roots. Due to the special choice of P and Q, for any number M exactly one of the four numbers M, N−M, N/2 and N−M/2 is a quadratic residue mod P and mod Q (when M is odd N/2 is replaced by (M+N)/2 mod P*Q). This statement follows from the additional theorems for the quadratic reciprocity law.

[0012] If one requires for message M the additional condition M=4 mod 8, the following holds because of the relation N=P*Q=3*7=5 (mod 8):

[0013] M=0, N−M=1, M/2=2, M−N/2=3 (mod 4)

[0014] i.e. the four numbers M, N−M, M/2 and N−M/2 differ in the last two bit positions.

[0015] For signing message M the issuing unit first tests which of the four values M, N−M, N/2 or N−N/2 is a quadratic residue mod P and mod Q. This can be done effectively by calculating the Jacobian symbols (N/P) and (M/Q):

[0016] M′=Mif (M/P)=1, (M/Q)=1;

[0017] M′=−Mif (M/P)=−1, (M/Q)=−1;

[0018] M′=M/2 if (M/P)=−1, (M/Q)=1;

[0019] M′=−M/2 if (M/P)=1, (M/Q)=−1;

[0020] Let M′ be the value meeting both conditions. The signature for message M is then:

[0021] S=(M′)^{(P*Q−P−Q+5)/8}mod N

[0022] It thus holds that:

[0023] S²=M′*(M′)^{[(P−1)/2]*[(Q−1,/2]} mod N

[0024] Since M′ is a quadratic residue mod P it follows by Fermat's small theorem that (M′)^[(P−1)/2]=1 mod P. Analogously it holds that (M′)^[(Q−1)/2]=1 mod Q. By the Chinese remainder theorem it further follows that (M′)^{[(P−1)/2]*[(Q−1)/2]}=1 mod P*Q. It thus holds that

[0025] S²=M′mod N=P*Q.

[0026] For verifying signature S terminal B first calculates the value

[0027] M′=S²mod N

[0028] Since when M=4 mod 8 is given the four possible values for M′ differ in the last two bit positions, M can be easily calculated from M′:

[0029] M=M′if M′=0 mod 4;

[0030] M=N−M′if M′=1 mod 4;

[0031] M=2M′if M′=2 mod 4;

[0032] M=2(N−M′) if M′=3 mod 4;

[0033] For verifying a signature on the smart card or terminal B a modular multiplication is necessary; i.e. the receiving unit calculates:

[0034] M′=S*Smod N

[0035] This necessitates a multiplication and a division. The division is considerably more elaborate than the multiplication. The disadvantage of the known procedure for verifying a signature is thus that the software receiving unit, which usually has less computing capacity than the issuing unit, must perform a comparatively elaborate calculating operation.

[0036] It is known from Menezes, “Handbook of Applied Cryptography”, 1997, CRC Press, New York, XP002112400, to verify an electronic signature using the Montgomery multiplication method.

[0037] European patent specification EP-A-0 566 498 discloses a method for secure distribution of data and/or programs wherein the data to be transmitted are provided with an electronic signature which is checked by the receiver. To check the signature the receiver implements modular multiplication according to the Montgomery method.

[0038] The disadvantage of known methods is that when software is distributed to units having low computer power, the verification of the signature reaches the limits of computer power.

[0039] It is therefore the object of the invention to state a method for secure distribution of software which avoids the above disadvantages.

[0040] This problem is solved by the characterizing feature of the present invention and the advantageous embodiments thereof.

[0041] It is therefore the problem of the invention to state a method for secure distribution of software which avoids the above disadvantages.

[0042] This problem is solved by the characterizing features of claim 1 starting out from the features of the preamble of claim 1.

[0043] Advantageous embodiments of the invention are stated in the dependent claims.

[0044] According to the invention one verifies the electronic signature using a method for implementing modular multiplication according to the Montgomery method instead of the usual standard methods for long-number arithmetic (trial division). The Montgomery method describes a faster method for modular multiplication calculating instead of the product Z=X*Y modulo N the following value:

[0045] Z0=X*Y*L⁻ⁱmod N

[0046] L is the basis on which the long-number arithmetic is performed. Typically L=2⁸is used with an 8-bit processor, L=2¹⁶with a 16-bit processor, etc. The value i must be at least great enough so as to fulfill the condition

[0047] Lⁱ>N.

[0048] The advantage of the Montgomery method is that the trial division step in modular multiplication is omitted. On the other hand, multiplication is additionally done by the undesirable factor L⁻ⁱmod N. This undesirable effect can be compensated in modular exponentiation according to the RSA method as follows.

[0049] Calculation of an RSA exponentiation A^Emod N is usually performed by repeated application of the laws of exponents A^2x=A^x*A^x(mod N) and A^2x+1=(A^x*A^x)*A (mod N). In the first step X=(E/2) is set, and in the following steps X is replaced by (X/2) until X=1 holds, (X) being here the greatest integer <=X. Modular exponentiation thus in fact amounts to a sequence of squarings and multiplications based on A (mod N).

[0050] In modular exponentiation by the Montgomery method the following is calculated:

[0051] A0=(A0*(L²mod N))*Lⁱmod N

[0052] This requires one Montgomery multiplication with the fixed value L²mod N and it holds that A0=A*^Limod N. It obviously holds that:

[0053] A^x*A^y*Lⁱ=(A^x*Lⁱ)*(A^y*Lⁱ)*Lⁱ=A^x+y*Limod N.

[0054] Using (A^x*Lⁱ) and (A^y*Lⁱ) the value A^x*A^y*Lⁱcan thus be calculated by a single Montgomery multiplication. Beginning with the value A0=A¹*Lⁱthe value A^E*Lⁱcan be easily calculated by repeated squaring and multiplying by A0. A further Montgomery multiplication of the intermediate result A^E*Lⁱby 1 provides the desired final result A^E.

[0055] In modular exponentiation with an exponent selected randomly in the range 1, . . . , N a necessary compensation involves relatively low additional computing effort.

[0056] When software is downloaded to a terminal or smart card, the signature test must be performed there. Since the terminal normally has little computing power, the signature test must be realized as simply as possible.

[0057] In the conventional combination of Rabin's signature test with Montgomery multiplication, signature S is transferred to terminal B.

[0058] Terminal B calculates:

[0059] M0=(S*S)*L⁻ⁱmod N

[0060] M′=(M0*(L²ⁱmod N))L⁻ⁱmod N

[0061] Obviously M′=S²mod N then holds. This method requires two Montgomery multiplications mod N and the value (L²ⁱmod N) must also be stored in the receiving unit.

[0062] According to an advantageous embodiment of the invention, one performs the following modification which does not require a Montgomery multiplication or storage of the value (L²ⁱmod N) unlike the conventional method. One transfers to the receiving unit instead of signature S the modified signature

[0063] S′=S*L^i/2mod N

[0064] Since with commercial processors L is a straight power of two, L^i/2can be easily calculated. The receiving unit now calculates by the Montgomery modular method the value

[0065] (S′*S′)* L⁻ⁱmod N=(S*L^i/2*S*L^i/2)L⁻ⁱmod N=S²mod N=M′mod N.

[0066] According to an advantageous embodiment of the invention one therefore performs the following modification which does not require a Montgomery multiplication or storage of the value (L²ⁱmod N) unlike the conventional method. One transfers to the receiving unit instead of signature S the modified signature

[0067] S′=S*L^i/2mod N

[0068] Since with commercial processors L is a straight power of two, L^i/2can be easily calculated. The receiving unit now calculates by the Montgomery method the value

[0069] (S′*S′)*L⁻ⁱmod N=(S*L^i/2*S*L^i/2)L⁻ⁱmod N=S²mod N=M′mod N.

[0070] Thus the signature test requires only one Montgomery modular multiplication on the terminal.

[0071] According to the invention, secure distribution of data and/or programs is performed by first transmitting the data with an electronic signature generated by a public-key method to a unit. The electronic signature is then checked by performing a first modular multiplication, thereby necessitating a multiplication and a division thereof. Lastly, the electronic signature is checked by the unit by performing modular multiplication according to the Montgomery method, as described above.

[0072] When performing modular multiplication according to the Montgomery method, a factor selected having a base 2 and even exponents is derived. The unit issues the data and/or programs by multiplying the digital signature by the factor derived from the Montgomery modular multiplication resulting in the additional multiplication factor being canceled out at the unit receiving the data and/or programs.