Registers – Coded record sensors – Particular sensor structure
Reexamination Certificate
2001-02-26
2002-06-18
Lee, Michael G. (Department: 2876)
Registers
Coded record sensors
Particular sensor structure
C235S382000, C235S437000
Reexamination Certificate
active
06405923
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention elates to a methos for secure distribution of data and/or programs.
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.
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
−1
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.
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.
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
S=M
½
mod (
P*Q
).
The receiving unit can verify the signature by calculating
M=S
2
mod
N.
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.
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.
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):
M=
0,
N−M=
1,
M/
2=2,
M−N/
2=3 (mod 4)
i.e. the four numbers M, N−M, M/2 and N−M/2 differ in the last two bit positions.
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):
M′=M
if (
M/P
)=1, (
M/Q
)=1;
M′=−M
if (
M/P
)=−1, (
M/Q
)=−1;
M′=M/
2 if (
M/P
)=−1, (
M/Q
)=1;
M′=−M/
2 if (
M/P
)=1, (
M/Q
)=−1;
Let M′ be the value meeting both conditions. The signature for message M is then:
S=
(
M′
)
(P*Q−P−Q+5)/8
mod
N
It thus holds that:
S
2
=M′*
(
M′
)
[(P−1)/2]*[(Q−1,/2]
mod
N
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
S
2
=M′
mod
N=P*Q.
For verifying signature S terminal B first calculates the value
M′=S
2
mod
N
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′:
M=M′
if
M′=
0 mod 4;
M=N−M′
if
M′=
1 mod 4;
M=
2
M′
if
M′=
2 mod 4;
M=
2(
N−M′
) if
M′=
3 mod 4;
For verifying a signature on the smart card or terminal B a modular multiplication is necessary; i.e. the receiving unit calculates:
M′=S*S
mod
N
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.
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.
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.
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.
SUMMARY OF THE INVENTION
It is therefore the object of the invention to state a method for secure distribution of software which avoids the above disadvantages.
This problem is solved by the characterizing feature of the present invention and the advantageous embodiments thereof.
It is therefore the problem of the invention to state a method for secure distribution of software which avoids the above disadvantages.
This problem is solved by the characterizing features of claim 1 starting out from the features of the preamble of claim 1.
Advantageous embodiments of the invention are stated in the dependent claims.
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:
Z
0=
X*Y*L
−i
mod
N
L is the basis on which the long-number arithmetic is performed. Typically L=2
8
is used with an 8-bit processor, L=2
16
with a 16-bit processor, etc. The value i must be at least great enough so as to fulfill the condition
L
i
>N.
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
−i
mod N. This undesirable effect can be compensated in modular exponentiation according to the RSA method as follows.
Calculation of an RSA exponentiation A
E
mod 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).
In modular exponentiation by the Montgomery method the following is calculated:
A
0=(
A
0*(
L
2
i
mod
N
))*
L
i
mod
N
This requires one Montgomery multiplication with the fixed value L
2
i
mod N and it holds that A0=A*
Li
mod N. It obvi
Giesecke & Devrient GmbH
Lee Michael G.
Walsh Daniel
LandOfFree
Method for secure distribution of data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for secure distribution of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for secure distribution of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905684