Cryptography system and elliptic curve operation method

Abstract

A cryptographic system is disclosed, implementing an Elliptic Curve operation method. A memory stores a program and data. A central processor unit (CPU) dispatches requests to the program. The program is converted into an equivalent substitution sequence comprising only arithmetic addition, subtraction and shift operations. A register pool stores data associated with the substitution sequence. An arithmetic logic unit (ALU) is controlled by the ASIC flow controller to execute the substitution sequence to output an execution result.

1 . A cryptographic system, comprising: 
 a memory for storage of a program;    a central processor unit (CPU), dispatching requests to an ASIC flow controller according to the program;    the ASIC flow controller, coupled to the CPU, generating a substitution sequence and performing flow control of the substitution sequence;    a register pool, coupled to the ASIC flow controller for storage of data associated with the substitution sequence; and    an arithmetic logic unit (ALU), controlled by the ASIC flow controller to execute the substitution sequence and output an execution result; 
 wherein the substitution sequence comprises only arithmetic addition, subtraction and shift operations.  
   
   
   
       2 . The cryptography system as claimed in  claim 1 , wherein the substitution sequence is converted by the CPU.  
   
   
       3 . The cryptography system as claimed in  claim 1 , wherein the substitution sequence is converted by the ASIC flow controller.  
   
   
       4 . The cryptography system as claimed in  claim 1 , wherein the ALU comprises: 
 an adder, adding or subtracting two input numbers based on an adder trigger signal to generate the execution result;    two selectors, coupled to the register pool, controlled by a selection signal to pass values from the register pool to the adder as the input numbers; wherein:    the adder trigger signal and selection signal are delivered from the ASIC flow controller or the CPU based on the substitution sequence.    
   
   
       5 . The cryptography system as claimed in  claim 4 , wherein the register pool comprises: 
 a plurality of registers for storage of data associated with the substitution sequence;and    a dispatcher, selectively storing the execution result or data to one of the registers based on a storage signal; wherein:    the storage signal is delivered from the ASIC flow controller or the CPU based on the substitution sequence.    
   
   
       6 . The cryptography system as claimed in  claim 5 , wherein: 
 the shift operation is performed by the ALU;    the ASIC flow controller delivers a shift signal to ALU when a shift operation is requested; and    the ALU shifts data stored in the register pool leftwards or rightwards according to the shift signal.    
   
   
       7 . The cryptography system as claimed in  claim 5 , wherein each selector is coupled to outputs of the registers, selecting one of them to pass an input number to the ALU.  
   
   
       8 . The cryptography system as claimed in  claim 5 , wherein: 
 the registers are 160 bit; and    the adder is a 32 bit full adder; and    the input numbers are 32 bit individually obtained from the registers based on the selection signal.    
   
   
       9 . The cryptography system as claimed in  claim 1 , wherein the program is an Elliptic Curve (EC) related application comprising: 
 EC point multiplication and addition operations,    prime field multiplication and inversion, and    arithmetic addition, and subtraction operations.    
   
   
       10 . The cryptography system as claimed in  claim 9 , wherein the ASIC flow controller converts the EC point multiplication operations to a first sequence of only EC point add operations and arithmetic operations.  
   
   
       11 . The cryptography system as claimed in  claim 10 , wherein the ASIC flow controller converts the first sequence to a second sequence comprising only prime field operations and shift operations.  
   
   
       12 . The cryptography system as claimed in  claim 11 , wherein the ASIC flow controller further converts prime field multiplication and inversion operations to an equivalent sequence comprising only arithmetic addition, subtraction and shift operations.  
   
   
       13 . An Elliptic Curve operation method, for use in an apparatus only capable of performing arithmetic addition, subtraction and shift operations, comprising: 
 providing a program to be executed;    converting the program into an equivalent substitution sequence comprising only arithmetic addition, subtraction and shift operations;    executing the substitution sequence, and outputting an execution result.    
   
   
       14 . The Elliptic Curve operation method as claimed in  claim 13 , wherein the program is an Elliptic Curve(EC) related application comprising: 
 point multiplication and addition operations,    prime field multiplication and inversion, and    arithmetic addition, and subtraction operations.    
   
   
       15 . The Elliptic Curve operation method as claimed in  claim 14 , wherein the conversion comprises converting the point multiplication operations to an arithmetic sequence of only prime field operations and shift operations.  
   
   
       16 . The Elliptic Curve operation method as claimed in  claim 15 , wherein the conversion further comprises, converting prime field multiplication and inversion operations to an equivalent sequence comprising only arithmetic addition, subtraction and shift operations, such that the substitution sequence equivalent to the program is generated.  
   
   
       17 . The Elliptic Curve operation method as claimed in  claim 16 , wherein the conversion of the multiplication and inversion in the prime field operations comprises transferring the prime field multiplication and inversion operations to Montgomery domain.  
   
   
       18 . The Elliptic Curve operation method as claimed in  claim 13 , further comprising providing flow control of the substitution sequence.