SYSTEM AND METHOD FOR ONE-TIME CHINESE-REMAINDER-THEOREM EXPONENTIATION FOR CRYPTOGRAPHIC ALGORYTHMS

Abstract

A system, method and computer-readable storage medium with instructions for protecting an electronic device against fault attack. The technology includes operating the electronic device to determine two half-size exponents, dp and dq, from the exponent d; to split the base m into two sub-bases mp and mq determined from the base m; and to iteratively compute a decryption result S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration I′. Other systems and methods are disclosed.

Claims

1. A method for operating a cryptography apparatus to perform a decryption operation having an exponentiation operation X, the method protecting the apparatus from revealing information in regard to the exponentiation operation X when the operation is exposed to a fault attack while being executed on the cryptography apparatus, the method comprising producing a result equivalent to the exponentiation by: receiving, on the cryptography apparatus, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=m.sup.d mod n; determining two half-size exponents from the exponent d; splitting the base m into two sub-bases mp and mq determined from the base m; iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i; returning as the value S the final value of the accumulator A; and completing the cryptographic operation using the value S obtained from the operation.

2. The method of claim 1 wherein the two half-sized exponents are dp and dq such that dp=d mod (p−1) and dq=d mod (q−1) where p and q are prime numbers such that n=pq.

3. The method of claim 1 wherein:
mp=1+q*iq*(m−1)mod n; and
mq=1+(1−q*iq)*(m−1)mod n wherein
iq=q.sup.−1 mod p.

4. The method of claim 1 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1=&& dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

5. (canceled)

6. The method of claim 2 wherein:
mp=1+q*iq*(m−1)mod n; and
mq=1+(1−q*iq)*(m−1)mod n wherein
iq=q.sup.−1 mod p.

7. The method of claim 2 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

8. The method of claim 3 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

9. The method of claim 6 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

10. An electronic device protected from fault attack and comprising: a central processing unit, memory, and an instruction storage wherein the instruction storage contains instructions to cause the central processing unit to perform: receiving, on by the central processing unit of the electronic device, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=m.sup.d mod n; determining two half-size exponents from the exponent d; splitting the base m into two sub-bases mp and mq determined from the base m; iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i; returning as the value S the final value of the accumulator A; and completing the cryptographic operation using the value S obtained from the operation.

11. The electronic device protected from fault attack of claim 10, wherein the two half-sized exponents are dp and dq such that dp=d mod (p−1) and dq=d mod (q−1) where p and q are prime numbers such that n=pq.

12. The electronic device protected from fault attack of claim 10, wherein:
mp=1+q*iq*(m−1)mod n; and
mq=1+(1−q*iq)*(m−1)mod n wherein
iq=q.sup.−1 mod p.

13. The electronic device protected from fault attack of claim 11, wherein:
mp=1+q*iq*(m−1)mod n; and
mq=1+(1−q*iq)*(m−1)mod n wherein
iq=q.sup.−1 mod p.

14. The electronic device protected from fault attack of claim 10, wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

15. The electronic device protected from fault attack of claim 11, wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

16. The electronic device protected from fault attack of claim 12, wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

17. The electronic device protected from fault attack of claim 13, wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations: A=A*A mod n IF (dp.sub.i=0 && dq.sub.i 0) A=A*1 mod n IF (dp.sub.i=1 && dq.sub.i 0) A=A*mp mod n IF (dp.sub.i=0 && dq.sub.i 1) A=A*mq mod n IF (dp.sub.i=1 && dq.sub.i 1) A=A*m mod n.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0027] FIG. 1 is a schematic illustration of a host computer with a portable security device, e.g., a smart card, connected thereto for performing cryptographic services through connection over a network to one or more servers.

[0028] FIG. 2 is a schematic illustration of a portable security device.

[0029] FIG. 3 is a schematic illustration of programs stored in a memory of the portable security device of FIG. 2.

[0030] FIG. 4 is a schematic illustration of a prior art cryptography module program listing that may be stored in the memory of a portable security device as illustrated in FIG. 3 and which performs a decryption including exponentiation operations.

[0031] FIG. 5 illustrates a prior art method for performing a decryption operation using modular exponentiation according to the square-and-multiply-always algorithm with half-size elements to perform two exponentiation operations, namely, S.sub.p=(M.sup.dp) mod p and S.sub.q=(M.sup.dq) mod q.

[0032] FIG. 6 illustrates a crypto module implementing a modified decryption algorithm using half-size elements, according to a preferred embodiment to perform the decryption using the same key material as in the algorithms of FIGS. 4 and 5 while performing only one exponentiation.

DETAILED DESCRIPTION OF THE INVENTION

[0033] In the following detailed description, reference is made to the accompanying drawings that show, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention. It is to be understood that the various embodiments of the invention, although different, are not necessarily mutually exclusive. For example, a particular feature, structure, or characteristic described herein in connection with one embodiment may be implemented within other embodiments without departing from the scope of the invention. In addition, it is to be understood that the location or arrangement of individual elements within each disclosed embodiment may be modified without departing from the spirit and scope of the invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims, appropriately interpreted, along with the full range of equivalents to which the claims are entitled. In the drawings, like numerals refer to the same or similar functionality throughout the several views.

[0034] In an embodiment of the invention, a technology is provided that enables the use of smart cards, or other portable security devices, to be used to digitally sign documents or to decrypt encrypted documents or messages using private keys stored on the smart cards in a manner that efficiently reduces the risk of differential power analysis attacks.

[0035] Smart cards are plastic cards with an embedded microprocessor and a secure storage. They are portable, secure, and tamper-resistant. Smart cards provide security services in many domains including telecommunication, banking, commerce, and citizen identity. Smart cards can take different forms, such as credit card shaped cards with electrical connectors to connect the smart card to a smart card reader, USB tokens with embedded smart cards, and SIM cards for use in mobile telephones and tablet devices. Smart cards are used herein as examples of portable security devices that may be used in implementations of the technology described herein. Other examples of portable security devices include smart memory cards, flash memory, etc. In a preferred embodiment, the portable security device has a processor, a memory for storing programs and data, and some security features to make the device relatively tamper-proof. Smart cards are used herein as examples of such devices.

[0036] While the mechanism for masking a cryptographic calculation described herein may be used advantageously in smart cards and other portable security tokens used for performing cryptographic calculations, the same mechanisms may also be used with other cryptographic processors. Thus, smart cards are used herein for illustrative purposes only.

[0037] Digital signature and other cryptography are examples of functions that smart cards provide. The smart card stores private or shared secret keys in its secure storage and performs cryptographic operations to generate a digital signature for a given input or to decrypt a given input. A smart card works with a host device, such as a personal computer (PC), cell phone, tablet device or banking terminal. A PC application, such as an email client or a web browser, typically works with a smart card to sign, encrypt, or decrypt a document. The cryptographic operation may be part of a challenge-response mechanism for user authentication. The PC application and the smart card interact through some cryptographic API called middleware, which is designed to communicate with the smart card. In this scenario, the smart card provides services locally to the PC.

[0038] FIG. 1 is a schematic illustration of a network 111 connecting a host computer 103 with a portable security device 109, e.g., a smart card, connected thereto, to one or more remote servers 113. The host computer 103 is operated by a user 101 who interacts with one of the servers 113 via a web browser window 105 of a web browser. In the example scenario illustrated in FIG. 1, the smart card 109 provides the cryptographic operations on behalf of the user 101, e.g., to cryptographically sign documents, to decrypt messages received from the relying party 113, or to perform a cryptographic operation as part of a challenge-response authentication mechanism.

[0039] While FIG. 1 provides an illustration of a scenario in which cryptography may play an important role, there are many other important uses for cryptography. Thus, the technology described herein is not limited in its application to the example of use which is illustrated in FIG. 1.

[0040] FIG. 2 is a schematic illustration of a portable security device 109, for example, a smart card. The portable security device 109 may include a processor 201 connected via a bus 202 to a random access memory (RAM) 203, a read-only memory (ROM) 204, and a non-volatile memory (NVM) 205. The portable security device 109 further includes an input/output interface 207 for connecting the processor 201, again typically via the bus 202, to a connector 211 by which the portable security device 109 may be connected to the host computer 103.

[0041] In alternative embodiments, the connection between the host computer 103 and the portable security device 109 is wireless, for example, using near-field communication (NFC) or other radio or microwave communication technologies.

[0042] The NVM 205 and/or ROM 204 may include computer programs 301 as is illustrated in FIG. 3. While it is here depicted that the computer programs 301 are all co-located in the ROM 204 or the NVM 205, in actual practice there is no such restriction as programs may be spread out over multiple memories and even temporarily installed in RAM 203. Furthermore, the portable security device 109 may include multiple ROMs or NVMs. The programs 301 include operating system programs as well as application programs loaded onto the portable security device 109. The NVM 205 or ROM 204 may also contain private data, such as a private key 209 or a shared secret key 210, stored either in its basic form or in derived quantities.

[0043] The portable security device 109 programs 301 may include a cryptography module 213, a user authentication module 215, a communications module 217, and the operating system OS 219.

[0044] Thus, the portable security device 109 may receive a document or message via the connector 211. The processor 201, by executing instructions of the cryptography module 213, may digitally sign the document/message or may decrypt the document/message using the private key 209 or shared secret key 210. Using functionality provided through the communications module 217, the processor 201 may receive and transmit communications with the host computer 103.

[0045] FIG. 4 is a schematic of a prior art possible implementation of the cryptography module 213. The cryptography module 213 would contain one or more functions, methods, or routines. One possible function could be, as is illustrated in FIG. 4, a function called CryptoFunction( ) which takes the argument M, the message to sign or decrypt. In the cryptography module 213 the signature S is computed using the standard RSA equation 401, namely, S=m.sup.D mod n.

[0046] An alternative prior art approach implements the CryptoFunction ( ) using the Chinese Remainder Theorem to perform a cryptographic operation; it includes modular exponentiation calculations 401 on half-size elements.

[0047] As a person skilled in the art would appreciate, this operation would be reduced to lower level arithmetic statements for the sake of efficiency. A common approach for efficiently calculating M.sup.dp mod p is the Square-and-MultiplyAlways algorithm. FIG. 5 is a program listing for a crypto module 213′ illustrating a traditional square-and-multiply-always procedure for calculating Sp=M.sup.dq mod p (algorithm 401a) and Sq=M.sup.dq mod q (algorithm 401b) using the quantities dp, dq, and iq (step 501) which are defined as:

dp=d mod(p−1)

dq=d mod(q−1)

iq=q.sup.−1 mod p

[0048] wherein dp and dq are written in the binary representations

dp=[dp.sub.n-1,dp.sub.n-2, . . . ,dp.sub.2,dp.sub.1,dp.sub.0]

and

dq=[dq.sub.n-1,dq.sub.n-2, . . . ,dq.sub.2,dq.sub.1,dq.sub.0]

[0049] S may then be computed using Garner's formula, step 503:

S=Sq+q*(iq*(Sp−Sq)mod p

[0050] The algorithm of FIG. 5 is much more efficient than the algorithm of FIG. 4 because it uses half-sized elements.

[0051] According to an embodiment of the invention described herein below, the crypto module 213′ (FIG. 6) uses a modification to the exponentiation algorithms in FIGS. 4 and 5 that, like the algorithm in FIG. 5, uses half-sized exponents while performing only one exponentiation. This modified approach is illustrated in FIG. 5.

[0052] FIG. 6 is a program listing illustrating a modified modular exponentiation calculation 401c to compute the result S=m.sup.D mod n used in a preferred embodiment of a crypto module 213″ incorporated, for example, into a memory, e.g., the ROM 204 or NVM 205 of a portable security device 109, using half-sized exponents while performing only one exponentiation. The exponentiation calculation 401c calculates S by an alternative use of the Chinese Remainder Theorem.

[0053] The inputs to the algorithm are:

[0054] m—the message to be decrypted

[0055] q and p—the two large prime numbers that are multiplied to compute n

[0056] The exponentiation calculation 401c begins by performing three preliminary calculations, 601:

iq=q.sup.−1 mod p

mq=1+q*iq*(m−1)mod n

mp=1+(1−q*iq)*(m−1)mod n

[0057] It may be shown through modular arithmetic that from the above calculations, the following relationships hold:

mq mod p=1

mq mod q=m mod q

mp mod q=1

mp mod p=m mod p

[0058] The calculation also uses the quantities dp and dq, which are defined from quantities p and q, respectively, as is described above, as:

dp=d mod(p−1)

dq=d mod(q−1)

[0059] An accumulator value A is initialized to 1, Step 603.

[0060] Next, with the binary representation of dp as dp=[dp.sub.o, dp.sub.1, . . . , dp.sub.k-1, dp.sub.k] and dq=[dq.sub.o, dq.sub.1, . . . , dq.sub.k-1, dq.sub.k], S is computed iteratively (loop 605) modifying the accumulator A over the bits of dp and dq and depending on the value of each bit dp.sub.i and dq.sub.i performing updates of the value A, as follows:

[0061] At the beginning of each iteration, A is set to A=A*A mod n, step 607.

[0062] The value pair dp.sub.i and dq.sub.i present four possible mutually exclusive alternatives: dp.sub.i=0 and dq.sub.i=0, dp.sub.i=1 and dq.sub.i=0, dp.sub.i=0 and dq.sub.i=1, and dp.sub.i=1 and dq.sub.i=1.

[0063] For the first of these alternatives (dp.sub.i=0 and dq.sub.i=0), A is set to A=A*1 mod n, steps 609. As this is an identity operation, in an actual implementation, the step is bypassed by doing nothing as the operation does not change the value of A. [0053] For the second alternative (dp.sub.i=1 and dq.sub.i=0), A is set to A=A*mp mod n, steps 611.

[0064] For the third alternative (dp.sub.i=0 and dq.sub.i=1), A is set to A=A*mq mod n, steps 613.

[0065] For the fourth alternative (dp.sub.i=1 and dq.sub.i=1), A is set to A=A*m mod n, steps 615.

[0066] At the conclusion, after all bits of dp.sub.i and dq.sub.i have been processed by the loop 605, the result held in A holds the value S=m.sup.D mod n and may be returned to the calling routine as the signed message S, Step 617.

[0067] At each iteration i of the exponentiation, the accumulator A is equal to S.sub.i such that:

S.sub.i mod p=m.sup.(dp0 dp1 dp2 . . . dpi)mod p

S.sub.i mod q=m.sup.(dq0 dq1 dq2 . . . dqi)mod q

[0068] These relationships are true because:

[0069] in step 615, when multiplying by m, the multiplication of the accumulator A*m is taken modulo p*q because n is defined as n=pq

[0070] in step 611, when multiplying by mp, the multiplication of accumulator A*mp is equivalent to A*m modulo p because the multiplication is 1 modulo q; consequently there is so no change in A due to q

[0071] in step 613, when multiplying by mq, the multiplication of the accumulator A*mq is equivalent to A*m modulo q because the multiplication is 1 modulo p; consequently there is no change in A due to p

[0072] in step 609, when multiplying by 1, the multiplication of A*1 the multiplication is A*1 modulo p and q; consequently there is no change due to either modulo p nor modulo q

[0073] Thus, after the final iteration—i.e., where i=k:

Sp=S.sub.k mod p=m.sup.dp mod p

Sq=S.sub.k mod q=.sup.dq mod q

[0074] In other words, because

Sp=S mod p

Sq=S mod q

it follows that

S=S.sub.k=A

[0075] From the foregoing it is evident that a mechanism is presented herein that computes the signed message S in a highly efficient manner using half-size exponent values without exposing multiple exponentiations to fault attacks thereby protecting against detection of the key material used in the encryption.

[0076] The above-described mechanism has been described in the context of the square-and-multiply-always technique. The mechanism is readily adapted to other exponentiation techniques.

[0077] Although specific embodiments of the invention have been described and illustrated, the invention is not to be limited to the specific forms or arrangements of parts so described and illustrated. The invention is limited only by the claims.