System and method for one-time chinese-remainder-theorem exponentiation for cryptographic algorythms
AssigneeGemalto SA
InventorDavid VIGILANT
Life of this patent
Estimating the term…
Abstract
A system, method and computer-readable storage medium with instructions for protecting an electronic device against fault attack. The technology includes operating the electronic device to determine two half-size exponents, dp and dq, from the exponent d; to split the base m into two sub-bases mp and mq determined from the base m; and to iteratively compute a decryption result S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration I′. Other systems and methods are disclosed.
Claims17
A method for operating a cryptography apparatus to perform a decryption operation having an exponentiation operation X, the method protecting the apparatus from revealing information in regard to the exponentiation operation X when the operation is exposed to a fault attack while being executed on the cryptography apparatus, the method comprising producing a result equivalent to the exponentiation by:
- receiving, on the cryptography apparatus, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=md mod n;
- determining two half-size exponents from the exponent d;
- splitting the base m into two sub-bases mp and mq determined from the base m;
- iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i;
- returning as the value S the final value of the accumulator A;
- and completing the cryptographic operation using the value S obtained from the operation.
(canceled)
An electronic device protected from fault attack and comprising:
- a central processing unit, memory, and an instruction storage wherein the instruction storage contains instructions to cause the central processing unit to perform:
- receiving, on by the central processing unit of the electronic device, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=md mod n;
- determining two half-size exponents from the exponent d;
- splitting the base m into two sub-bases mp and mq determined from the base m;
- iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i;
- returning as the value S the final value of the accumulator A;
- and completing the cryptographic operation using the value S obtained from the operation.
Dependencies are inferred from the claim text.