Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-09-15
2002-04-02
Decady, Albert (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S285000, C380S044000, C380S030000
Reexamination Certificate
active
06366673
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to a method according to the preamble of Claim 1. Encrypting by executing a standardized modular exponentiation is used in the environment of a smart card and elsewhere, such as for supporting financial operations, through blocking opportunity for falsifying the control or contents of such operations. Encryption can be expressed as y=<x
e
>
M
, wherein x is a message, e is an encryption key, and M a modulus. Likewise, decryption is effected as D(y)=<y
d
>
M
, wherein d is the decryption key, and retrieving x from D is straightforward. For a particular device, the values of M and e are known and fixed, the content of x to be encrypted is naturally unknown and variable, and the value of d is fixed but unknown. For certain operations, such as the providing of an encoded signature, the first encoding also operates with a secret key along similar lines. For the present description, such encoding is also called “decrypting”. Now, the decrypting is effected digit-wise. For each digit of D, one or two first multiplications X*Y mod M produce a first result. The attaining of such first result is followed by an addition. After attaining a second result, the next digit of D is processed. Prior technology has kept the size of the second result down by, in operation, subtracting an appropriate multiplicity (zero, one, or more) of the quantity M, because the register width of available hardware is adapted to the digit length, that is generally much less than the size of the overall quantities used in the multiplication.
It has been found that the sequential pattern of the above multiplicity may depend on the values of X, Y, and M. Further, the use of temporal statistics on a great number of mutually unrelated decryption operations with arbitrary messages allows to derive a value for d. This renders the protection by the encryption illusory. Therefore, a need exists to mask these statistical variations by some additional affecting of the calculation procedure.
SUMMARY TO THE INVENTION
In consequence, amongst other things, it is an object of the present invention to suppress the relation between the value of the decryption key and the temporal structure of the calculating steps, through a masking mechanism that does not appreciably lengthen the calculations, nor would necessitate inordinate hardware facilities. Now therefore, according to one of its aspects, the invention is characterized by the characterizing part of Claim 1. In particular, the inventors have recognized that present day microcontrollers, even those that are used in the constraining environment of a smart card, can allow the use of longer storage registers than before, and in particular, a few bits longer than the digits used in the calculation. Such registers would provide the extra freedom that the present invention is in need of.
Advantageously, the procedure executes the exponentiation along the Quisquater or Barrett prescriptions. These are methods commonly in use, and the amending of their prosecution for adhering to the invention is minimal. The pattern of the calculation procedure no longer depends on the decryption key. This takes away any method for so deciphering the value of the decrypting key.
The invention also relates to a device arranged to implement the method of the invention. Further advantageous aspects of the invention are recited in dependent Claims.
REFERENCES:
patent: 5261001 (1993-11-01), Dariel et al.
patent: 5724279 (1998-03-01), Benaloh
patent: 6085210 (2000-07-01), Buer
patent: 6088800 (2000-07-01), Jones et al.
patent: 6151393 (2000-11-01), Jeong
patent: 6182104 (2001-01-01), Foster et al.
“Fast Implementations of RSA Cryptography” by M. Shand et al., IEEE Proc. 11th Symposium on Computer Arithmetic, pp. 252-259.
Hollmann Hendrik D. L.
Lenoir Petrus J.
Van Dijk Marten E.
Callahan Paul E.
De'cady Albert
Piotrowski Daniel J.
U.S. Philips Corporation
LandOfFree
Method and device for executing a decrypting mechanism... 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 and device for executing a decrypting mechanism..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for executing a decrypting mechanism... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2928559