Finite field cryptographic arithmetic resistant to fault attacks

Abstract

Various embodiments relate to a method for integrity protected calculation of a cryptographic function including: performing an operation c=a∘b in a cryptographic function f(x 1 , x 2 , . . . , x n ) defined over a commutative ring R; choosing a′ and b′ corresponding to a and b such that a′ and b′ are elements of a commutative ring R′; computing c′=a′∘′b′; computing a″=CRT(a, a′) and b″=CRT(b, b′), where CRT is the Chinese Remainder Theorem; computing c″=a″∘″b″; mapping c″ into R′; and determining if the mapping of c″ into R′ equals c′.

We claim: 
     
       1. A method for integrity protected calculation of a cryptographic function on a cryptographic processor comprising:
 performing on a cryptographic processor an operation c=a∘b in a cryptographic function f p,q (x 1 , x 2 , . . . , x n ) defined over a commutative ring R, wherein a and b are any one of x 1 , x 2 , . . . , x n  and p and q are prime such that  p p≡1 (MOD q) and  q q≡1 (MOD p); 
 choosing a′ and b′ corresponding to a and b such that a′ and b′ are elements of a commutative ring R′, with a modulus m that is coprime with p·q, wherein a′ and b′ are a cyclic redundancy check of a and b; 
 computing c′=a′∘b′; 
 computing a″=CRT p,q (a, a′) and b″=CRT p,q (b, b′), where CRT is a Chinese Remainder Theorem defined as CRT p,q (a,b)=(a  p  p+b  q  q) MOD pq; 
 computing c″=a″∘″b″; 
 calculating a mapping of c″ into R′=c″ mod m; and 
 determining if the mapping of c″ into R′ equals c′, and then indicating that no fault is detected, 
 wherein if the mapping of c″ into R′ equals c′ then repeating the above steps to further calculate the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) for other values of a and b, otherwise indicate that the calculation of the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) is invalid. 
 
     
     
       2. The method of  claim 1 , wherein the cryptographic function is based upon a factoring problem. 
     
     
       3. The method of  claim 1 , wherein the cryptographic function is based upon a discrete logarithm problem. 
     
     
       4. The method of  claim 1 , wherein choosing a′ and b′ includes setting a′=α′ and b′=α′, where α′ is a constant in R′ and further comprising:
 computing α″=CRT(0, α′), wherein computing c″ includes computing c″=a″∘″b″−″{tilde over (α)} where {tilde over (α)}=α″ if ∘″=+″ and {tilde over (α)}=α″(α″−1) if ∘″=·″. 
 
     
     
       5. The method of  claim 4 , wherein if the mapping of c″ into R′ equals α′ then repeating the method of  claim 1  to further calculate the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) for other values of a and b, otherwise indicate that the calculation of the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) is invalid. 
     
     
       6. A non-transitory storage medium encoded with instructions for performing an integrity protected calculation of a cryptographic function comprising:
 instructions for performing on a cryptographic processor an operation c=a∘b in a cryptographic function f p,q (x 1 , x 2 , . . . , x n ) defined over a commutative ring R, wherein a and b are any one of x 1 , x 2 , . . . , x n  and p and q are prime such that  p p≡1 (MOD q) and  q q≡1 (MOD p); 
 instructions for choosing a′ and b′ corresponding to a and b such that a′ and b′ are elements of a commutative ring R′, with a modulus m that is coprime with p·q, wherein a′ and b′ are a cyclic redundancy check of a and b; 
 instructions for computing c′=a′∘′b; 
 instructions for computing a″=CRT p,q (a, a′) and b″=CRT p,q (b, b′), where CRT is a Chinese Remainder Theorem defined as CRT p,q (a,b)=(a  p  p+b  q  q) MOD pq; 
 instructions for computing c″=a″∘″b″; 
 instructions for calculating a mapping of c″ into R′=c″ mod m; and 
 instructions for determining if the mapping of c″ into R′ equals c′, and then indicating that no fault is detected, 
 wherein if the mapping of c″ into R′ equals c′ then repeating the above instructions to further calculate the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) for other values of a and b, otherwise indicate that the calculation of the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) is invalid. 
 
     
     
       7. The non-transitory storage medium of  claim 6 , wherein the cryptographic function is based upon a factoring problem. 
     
     
       8. The non-transitory storage medium of  claim 6 , wherein the cryptographic function is based upon a discrete logarithm problem. 
     
     
       9. The non-transitory storage medium of  claim 6 , wherein choosing a′ and b′ includes setting a′=α′ and b′=α′, where α′ is a constant in R′ and further comprising:
 instructions for computing α″=CRT(0, α′), wherein instructions for computing c″ includes computing c″=a″∘″b″−″{tilde over (α)} where {tilde over (α)}=α″ if ∘″=+″ and {tilde over (α)}=α″(α″−1) if ∘″=·″. 
 
     
     
       10. The non-transitory storage medium of  claim 9 , wherein if the mapping of c″ into R′ equals α′ then repeating the method of  claim 1  to further calculate the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) for other values of a and b, otherwise indicate that the calculation of the cryptographic function f p,q (x 1 , x 2 , . . . , x n ) is invalid.