RANDOMIZED RSA-BASED CRYPTOGRAPHIC EXPONENTIATION RESISTANT TO SIDE CHANNEL AND FAULT ATTACKS

• US 20090097637A1
• Filed: 10/10/2007
• Published: 04/16/2009
• Est. Priority Date: 10/10/2007
• Status: Active Grant

• Current Assignee: Cypress Semiconductor Corporation (Infineon Technologies AG)
• Original Assignee: Spansion LLC (Infineon Technologies AG)
• Inventors: Trichina, Elena, Boscher, Arnaud, Handschuh, Helena
• Granted Patent: US 8,139,763 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/7238 Operand masking, i.e. message blinding, e.g. (A+r)**e mod n; k.(P+R)
• CPC Class Codes: G06F 2207/7271 Fault verification, e.g. comparing two values which should be the same, unless a computational fault occurred
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 9/004 for fault attacks
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Systems and/or methods that facilitate secure electronic communication of data are presented. A cryptographic component facilitates data encryption, data decryption, and/or generation of digital signatures, associated with messages. The cryptographic component includes a randomized exponentiation component that facilitates decryption of data and/or generation of digital signatures by exponentiating exponents associated with messages. A random number is generated and utilized to randomize the value of a message. After an exponentiation is performed on the randomized message value, intermediate results can be analyzed to determine if there was error in the exponentiation. If there was no error in the exponentiation, a final value of the exponentiation is determined and provided as output as decrypted data or a digital signature; if there is error, an “error” output can be provided.

Claims

1. A system that facilitates communication of data, comprising:

a cryptographic component that facilitates securing the data in accordance with a cryptographic protocol and includes a randomized exponentiation component that facilitates at least one of decryption of the data or generation of a digital signature, or a combination thereof, based on an exponentiation of the data with an exponent associated with the data, where a value of the data is randomized based on a value of a random number.

2. The system of claim 1, the data is received by the cryptographic component and the value of the data is multiplied by the value of the random number.

3. The system of claim 1, the value of the random number is different for each execution by the cryptographic component.

4. The system of claim 1, the randomized exponentiation component exponentiates the data based on the exponent in accordance with a right-to-left square-and-multiply algorithm.

5. The system of claim 4, the randomized exponentiation component performs calculations associated with the exponentiation of the data in accordance with a Chinese Remainder Theorem algorithm.

6. The system of claim 1, the randomized exponentiation component utilizes at least one of Montgomery multiplication or Montgomery exponentiation, or a combination thereof, to compute at least one of the random number or a modular inverse of the random number, or a combination thereof.

7. The system of claim 1, the randomized exponentiation component determines whether the exponentiation is performed without error and provides a final result of the exponentiation as an output if there is no error or provides an output of “

error”

if there is an error.

8. The system of claim 1, further comprising a computation component that performs parallel operations associated with exponentiation of the data based on the exponent.

9. The system of claim 1, further comprising:

a host processor that facilitates performing operations on data;

a memory that stores data, the cryptographic component receives data from at least one of the host processor or the memory, or a combination thereof.

10. The system of claim 1, the exponent is associated with one of RSA cryptography, elliptic curve cryptography, Diffie-Hellman cryptography, Digital Signature Algorithm (DSA) cryptography, or Elliptic Curve DSA cryptography.

11. An electronic device comprising the system of claim 1, the electronic device is one of a computer, a cellular phone, a digital phone, a video device, a smart card, a personal digital assistant, a television, an electronic game, a digital camera, an electronic organizer, an audio player, an audio recorder, an electronic device associated with digital rights management, Personal Computer Memory Card International Association (PCMCIA) cards, trusted platform modules (TPMs), Hardware Security Modules (HSMs), set-top boxes, secure portable tokens, Universal Serial Bus (USB) tokens, key tokens, secure memory devices with computational capabilities, or electronic devices with tamper-resistant chips.

12. A method that facilitates securing data, comprising:

exponentiating the data using an exponent, a value of the data is randomized based on a random number; and

providing an output based on the exponentiation of the data, a value of the output is based on an inverse value of the random number.

13. The method of claim 12, further comprising:

generating a random number; and

multiplying a value of the data with a value associated with the random number.

14. The method of claim 12, further comprising:

receiving the data associated with the message;

receiving the exponent;

setting initial values of variables associated with exponentiation of the data using the exponent;

scanning the bits of the exponent during exponentiation from a least significant bit to a most significant bit in accordance with a right-to-left square-and-multiply algorithm;

exponentiating the data using the exponent;

determining if the exponentiation results are without error; and

at least one of;

providing an output of a final result based on the exponentiation of the data if the exponentiation results are without error, the final result is based on the inverse value of the random number, or

providing an output of “

error”

if the exponentiation has at least one error.

15. The method of claim 14, further comprising:

exponentiating the data with an exponent in accordance with a Chinese Remainder Theorem.

16. The method of claim 14, further comprising:

calculating a variable Sp1 as at least one of Sp1=R*M̂

dp mod p or Sp1=R̂

(−

1)*M̂

dp, where R is the random number, M is the data associated with the message, p is a prime number, dp=d mod p−

1, d represents the exponent, and mod represents a modulo operation;

calculating a variable Sp2 as at least one of Sp2=R̂

(−

1)*M̂

(not (dp)) mod p or Sp2=R*M̂

(not (dp)) mod p;

calculating a variable Sp3 as Sp3=M̂

(2̂

(length (p))) mod p;

calculating a variable Sq1 as at least one of Sq1=R*M̂

dq mod q or Sq1=R*M̂

dq mod q, where q is a prime number and dq=d mod q−

1;

calculating a variable Sq2 as at least one of Sq2=R̂

(−

1)*M̂

(not (dq)) mod q or Sq2=R*M̂

(not (dq)) mod q;

calculating a variable Sq3 as Sq3=M̂

(2̂

(length (q))) mod q;

calculating a variable S1 as S1=((Sq1−

Sp1)*Apq mod q)*p+Sp1 where Apq=p̂

(−

1) mod q;

calculating a variable S2 as S2=((Sq2−

Sp2)*Apq mod q)*p+Sp2;

calculating a variable S3 as S3=((Sq3−

Sp3)*Apq mod q)*p+Sp3;

determining if the value of M*S1*S2 mod N is equivalent to the value of S3; and

at least one of;

calculating a final result as at least one of S1* R̂

(−

1) mod N or S1*R mod N if the value of M*S1*S2 mod N is equivalent to the value of S3, and

providing the final result as an output, or providing “

error”

as an output if M*S1*S2 mod N is not equivalent to the value of S3.

17. The method of claim 12, further comprising:

setting initial values for variables R0, R1, A, and i as A=g, i=0, R0 equal to at least one of R or R̂

(−

1), and R1 equal to at least one of R̂

(−

1) or R, wherein g is the data associated with the message and i is an iteration number;

scanning an exponent bit of the exponent based on the iteration number i;

at least one of;

calculating R0=R0*A when the value of the exponent bit is 1, or

calculating R1=R1*A when the value of the exponent bit is 0;

calculating A =Â

2;

determining if the value of R0*R1*g is equivalent to the value of A after each bit of the exponent is scanned;

determining if all exponent bits of the exponent are scanned;

incrementing the iteration number i if all exponents bits are not scanned; and

at least one of;

calculating a final result as at least one of R0*R̂

(−

1) if the initial value of R0=R and the initial value of R1=R1̂

(−

1) or R0*R if the initial value of R0=R̂

(−

1) and the initial value of R1=R, and

providing the final result as an output, if R0*R1*g is equivalent to the value of A after all of the exponent bits are scanned, or

providing “

error”

as an output, if R0*R1*g is not equivalent to the value of A after all of the exponent bits are scanned.

18. The method of claim 12, further comprising:

calculating at least one of a random number or an inverse of a random number using a Montgomery algorithm.

19. A system for securing information, comprising:

means for randomizing a binary value associated with the information;

means for exponentiating the information with an exponent; and

means for providing a final data value based on the exponentiation of the information.

20. The system of claim 19, further comprising:

means for generating a random number;

means for receiving the information;

means for performing computations associated with the exponentiation based on a right-to-left square-and-multiply exponentiation algorithm;

means for comparing preliminary results associated with the exponentiation; and

means for determining whether at least one error occurred in the exponentiation.