Patent ID: 8402287

Claim:
A cryptographic mechanism involving a secret D which can be represented as an n-bit number {d 0 , d 1 , . . . d n−1 } 2 , the cryptographic mechanism being arranged to calculate an output element OUT equal to X D , X being an element of a monoid {M, *}, the cryptographic mechanism comprising a first variable VAR 0 , a second variable VAR 1 , and computer program instructions to cause a processor of a cryptographic device to perform the steps of: a. generating a random element MSK_INPUT (R); b. creating a masked element MASKED_X (VAR 1 ) by using the element X and the random element MSK_INPUT and initializing a masked output element to the random element MSK_INPUT (R); c. calculating the masked output element MASKED_OUT (VAR 0 ) using the masked element MASKED_X (VAR 1 ), the calculation of the masked output element MASKED_OUT thereby accumulating the random element MSK_INPUT (R) into intermediate results for MASKED_X and MASKED_OUT, the calculation comprising: for i=n−1 down to 0: performing a step MULi: VAR 1−di →VAR 1−di *VAR di ; performing a step SQi: VAR di →VAR di * VAR di ; d. calculating an output mask MSK_OUTPUT (MSK 0 ) from the random element MSK_INPUT, MSK_OUTPUT (MSK 0 ) being an inverse of the accumulation of the random element MSK_INPUT in masked output element MASKED_OUT during the step of calculating the masked output element in step c, without involving the secret D; e. calculating the output element OUT using the masked output element MASKED_OUT and the output mask MSK_OUTPUT; and wherein the step d occurs at any time between step a and step e, and wherein the steps a, b, c and e are consecutive.