Imbalanced montgomery ladder
The invention relates to a method for securing an electronic device (SC) against attacks via covert channels when the electronic device (SC) implements a Montgomery ladder for calculating the element A ⊥ A ⊥ . . . ⊥ A where A appears k times. A designates an element of an Abelian group with a law ⊥ , and k is a natural number. The method comprises a modified implementation of the Montgomery ladder. The invention also relates to a device (SC), a computer program and a storage medium arranged so as to implement such a method.
1. A method for encrypting data for securing an electronic device (SC) against side-channel attacks when the electronic device (SC) implements a Montgomery ladder to calculate element A ⊥ A ⊥ . . . ⊥ A where A appears k times, A being an element of an Abelian group with a law ⊥ and k being a positive integer, the method comprising a modified encryption implementation of the Montgomery ladder comprising:
determining (DET_r 1 ), by a determination circuit of the electronic device (SC), a first positive integer r 1 ;
calculating (CALC_R 1 ), by a calculation circuit of the electronic device (SC), a first parameter R 1 =A ⊥ A ⊥ . . . ⊥ A where A appears r 1 times;
determining (DET_r 2 ), by a determination circuit of the electronic device (SC), a second positive integer r 2 ;
calculating (CALC_R 2 ), by a calculation circuit of the electronic device (SC), a second parameter R 2 =A ⊥ A ⊥ . . . ⊥ A where A appears r 2 times;
calculating (CALC_k), by a calculation circuit of the electronic device (SC), a positive integer k′ from the positive integer k, from the first positive integer r 1 , and from the second positive integer r 2 ;
implementing (M_ML), by a calculation circuit of the electronic device (SC), the Montgomery ladder modified to use positive integer k′ in place of positive integer k, first parameter R 1 =A ⊥ A ⊥ . . . ⊥ A where A appears r 1 times in place of a parameter R 1 =1, and second parameter R 2 =A ⊥ A ⊥ . . . ⊥ A where A appears r 2 times in place of a parameter R 2 =A.
2. The method of claim 1 , wherein:
the calculation circuit of the electronic device implementing the calculation (CALC_R 1 ) of the first parameter, and
the calculation circuit of the electronic device implementing the calculation (CALC_R 2 ) of the second parameter
are implementing the two respective calculations with the Montgomery ladder.
3. The method according to claim 1 , further comprising:
calculating, by the electronic device (SC), a corrective term; and
using, by a correction circuit of the electronic device (SC), the corrective term so as to correct the result of the modified implementation of the Montgomery ladder and thus obtaining the value of element A ⊥ A ⊥ . . . ⊥ A where A appears k times.
4. An electronic device (SC) configured to protect against side-channel attacks using encryption based on a Montgomery ladder to calculate element A ⊥ A ⊥ . . . ⊥ A where A appears k times, A being an element of an Abelian group with a law ⊥ and k being a positive integer, the electronic device (SC) comprising:
a circuit (MCONT) configured to determine a first positive integer r 1 ;
a circuit (MCONT) configured to calculate a first parameter R 1 =A ⊥ A ⊥ . . . ⊥ A where A appears r 1 times;
a circuit (MCONT) configured to determine a second positive integer r 2 ;
a circuit (MCONT) configured to calculate a second parameter R 2 =A ⊥ A ⊥ . . . ⊥ A where A appears r 2 times;
a circuit (MCONT) configured to calculate a positive integer k′ from the positive integer k, from the first positive integer r 1 , and from the second positive integer r 2 ; and
a circuit (MCONT) configured to calculate the Montgomery ladder, modified to use positive integer k′ in place of positive integer k, first parameter R 1 =A ⊥ A ⊥ . . . ⊥ A where A appears r 1 times in place of a parameter R 1 =1, and second parameter R 2 =A ⊥ A ⊥ . . . ⊥ A where A appears r 2 times in place of a parameter R 2 =A.
5. The electronic device (SC) of claim 4 , wherein the circuit configured to calculate the first parameter, and the circuit configured to calculate the second parameter are arranged to respectively implement these two calculations with the Montgomery ladder.
6. The electronic device (SC) of claim 4 , further comprising:
a calculation circuit (MCONT) configured to calculate a corrective term; and
a correction circuit (MCONT) arranged to use the corrective term to correct the result of the circuit calculating the modified Montgomery ladder and to thus obtain the value of element A ⊥ A ⊥ . . . ⊥ A where A appears k times.
7. A non-transitory computer readable storage medium whose contents cause a computer to execute a series of instructions for encrypting data according to the method of claim 1 .