Method of preventing power analysis attacks on microelectronic assemblies

Abstract

Apparatus in form of a microelectronic assembly including an integrated circuit (IC) for execution of an embedded modular exponentiation program utilizing a square-and-multiply algorithm, wherein in the modular exponentiation program a secret exponent having a plurality of bits characterizes a private key, a method of providing a digital signature to prevent the detection of the secret exponent when monitoring power variations during the IC execution, the method comprising the steps of for a first operation in the modular exponentiation, selecting at least one predetermined bit, wherein the at least one predetermined bit is a bit other than a least significant bit (LSB) and the most significant bit (MSB); using the square-and-multiply algorithm, sequentially selecting bits to the left of the at least one predetermined bit for exponentiation until the MSB is selected; subsequent to selecting the MSB, sequentially selecting bits to the right of the at least one predetermined bit for exponentiation until the LSB is selected.

We claim:  
     
       1. In a microelectronic assembly including an integrated circuit (IC) for execution of an embedded modular exponentiation program, wherein in the modular exponentiation program a secret exponent having a plurality of bits characterizes a private key, a method of providing a digital signature to prevent the detection of the secret exponent when monitoring power variations during IC execution, the method comprising the steps of: 
       selecting at least one predetermined bit in the secret exponent, wherein the at least one predetermined bit is a bit other than a least significant bit (LSB) and a most significant bit (MSB);  
       using a first algorithm, sequentially selecting bits to the left of the at least one predetermined bit for exponentiation until the MSB is selected; and  
       using a second algorithm, subsequent to selecting the MSB, sequentially selecting bits to the right of the at least one predetermined bit for exponentiation until the LSB is selected,  
       wherein the first algorithm is different from the second algorithm.  
     
     
       2. The method of claim  1 , wherein the microelectronic assembly is a smartcard and the IC is a microcontroller. 
     
     
       3. The method of claim  2 , wherein the microcontroller is an HC05-based microcontroller. 
     
     
       4. The method of claim  1 , wherein the modular exponentiation program is executed in hardware. 
     
     
       5. In a microelectronic assembly including an integrated circuit (IC) for execution of an embedded modular exponentiation program, wherein in the modular exponentiation program a secret exponent (E) having a plurality of bits characterizes a private key, a method of providing a digital signature to prevent the detection of the secret exponent when monitoring power variations during the IC execution, the method comprising the steps of: 
       selecting at least one predetermined bit in the secret exponent, wherein the at least one predetermined bit is a bit other than a least significant bit (LSB) and a most significant bit (MSB);  
       using a first algorithm, sequentially selecting bits to the right of the at least one predetermined bit for exponentiation until the LSB is selected; and  
       using a second algorithm, subsequent to selecting the LSB, sequentially selecting bits to the left of the at least one predetermined bit for exponentiation until the MSB is selected,  
       wherein the first algorithm is different from the second algorithm.  
     
     
       6. The method of claim  5 , wherein the microelectronic assembly is a smartcard and the IC is a microcontroller. 
     
     
       7. The method of claim  6 , wherein the microcontroller is an ARM-based microcontroller. 
     
     
       8. The method of claim  5 , wherein the modular exponentiation program is executed in hardware. 
     
     
       9. In a microelectronic assembly including an integrated circuit (IC) for execution of an embedded elliptic-curve scalar multiplication program, wherein in the elliptic-curve scalar multiplication program a secret scalar having a plurality of bits characterizes a private key, a method of providing a digital signature to prevent the detection of the secret scalar when monitoring power variations during the IC execution, the method comprising the steps of: 
       selecting at least one predetermined bit in the secret scalar, wherein the at least one predetermined bit is a bit other than a least significant bit (LSB) and a most significant bit (MSB);  
       using a first algorithm, sequentially selecting bits to the left of the at least one predetermined bit for scalar multiplication until the MSB is selected; and  
       using a second algorithm, subsequent to selecting the MSB, sequentially selecting bits to the right of the at least one predetermined bit for scalar multiplication until the LSB is selected,  
       wherein the first algorithm is different from the second algorithm.  
     
     
       10. The method of claim  9 , wherein the microelectronic assembly is a smartcard and the IC is a microcontroller. 
     
     
       11. The method of claim  10 , wherein the microcontroller is an HC05-based microcontroller. 
     
     
       12. The method of claim  9 , wherein the elliptic-curve scalar multiplication program is executed in hardware. 
     
     
       13. In a microelectronic assembly including an integrated circuit (IC) for execution of an embedded elliptic-curve scalar multiplication program, wherein in the elliptic-curve scalar multiplication program a secret scalar having a plurality of bits characterizes a private key, a method of providing a digital signature to prevent the detection of the secret scalar when monitoring power variations during the IC execution, the method comprising the steps of: 
       selecting at least one predetermined bit in the secret scalar, wherein the at least one predetermined bit is a bit other than a least significant bit (LSB) and a most significant bit (MSB);  
       using a first algorithm, sequentially selecting bits to the right of the at least one predetermined bit for scalar multiplication until the LSB is selected; and  
       using a second algorithm, subsequent to selecting the LSB, sequentially selecting bits to the left of the at least one predetermined bit for scalar multiplication until the MSB is selected,  
       wherein the first algorithm is different from the second algorithm.  
     
     
       14. The method of claim  13 , wherein the microelectronic assembly is a smartcard and the IC is a microcontroller. 
     
     
       15. The method of claim  14 , wherein the microcontroller is an ARM-based microcontroller. 
     
     
       16. The method of claim  13 , wherein the elliptic-curve scalar multiplication program is executed in hardware. 
     
     
       17. The method of claim  1 , wherein at least one of the first and second algorithms is a square-and-multiply algorithm. 
     
     
       18. The method of claim  5 , wherein at least one of the first and second algorithms is a square-and-multiply algorithm. 
     
     
       19. The method of claim  9 , wherein at least one of the first and second algorithms is a double-and-add algorithm. 
     
     
       20. The method of claim  13 , wherein at least one of the first and second algorithms is a double-and-add algorithm.