Patent ID: 7174016

Claim:
A method for protecting from attack a modular exponentiation algorithm that is performed in a cryptographic operation on data in a microprocessor-based system, said algorithm being defined by the following mathematical formula: R=X Y mod N; Y being an exponent having a size of k bits, N being a modulus having a size of kâ€² bits, X being a known variable having a size of kâ€³ bits, and R being the result of the modular exponentiation operation and having a size of kâ€² bits; Said method comprising the steps of establishing registers R1 and R2 and an indicator I in said system, and said cryptographic operation on the data including execution of the following steps via a microprocessor: a) initializing R 1 =1 and Z=X; b) initializing I=0; for each bit of Y(i) of the binary representation of Y, i varying from â€œ0â€ to â€œkâˆ’1â€, performing the following steps c, d, and e from the least significant bit Y(0) to the most significant bit Y(kâˆ’1): c) performing the operation Z:=Z 2 ; d) if I=0, performing the operation R 2 :=R 1 *Z; if I=1, performing the operation R 1 :=R 2 *Z; e) if Y(i)=0, then I is kept unchanged and if Y(i)=1, then I is complemented; and f) encrypting, decrypting, or signing said data using the value Y as a key.