Efficient modular addition resistant to side channel attacks

Abstract

A cryptographic device performs modular addition between a first integer value x and a second integer value y in a processor by: obtaining a first masked input {circumflex over (x)}, a second masked input ŷ, a first mask rand a second mask r, the first masked input {circumflex over (x)} resulting from the first integer value x masked by the first mask rand the second masked input ŷ resulting from the second integer value y masked by the second mask r; computing a first iteration masked carry value ĉ, using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r, the second mask rand a carry mask value λ; recursively updating the masked carry value ĉto obtain a final masked carry value ĉ, wherein the masked carry value is updated using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r, the second mask r, and the carry mask value λ; combining the first masked input {circumflex over (x)} and the second masked input ŷ and the final masked value ĉto obtain an intermediate value; combining the intermediate value with the carry mask value to obtain a masked result; and outputting the masked result and a combination of the first mask rand the second mask r. It is preferred that the combinations use XOR.