| Cryptography system and elliptic curve operation method -> Monitor Keywords |
|
|
  Cryptography system and elliptic curve operation methodUSPTO Application #: 20070198824Title: 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. (end of abstract) Agent: Thomas, Kayden, Horstemeyer & Risley, LLP - Atlanta, GA, US Inventors: Chia-Ping Chen, Ying-Che Hung, Li-Lien Lin USPTO Applicaton #: 20070198824 - Class: 713150000 (USPTO) Related Patent Categories: Electrical Computers And Digital Processing Systems: Support, Multiple Computer Communication Using Cryptography The Patent Description & Claims data below is from USPTO Patent Application 20070198824. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS REFERENCE TO RELATED APPLICATIONS [0001] This application claims the benefit of U.S. Provisional Application No. 60/743,126, filed Jan. 12, 2006. BACKGROUND OF THE INVENTION [0002] 1. Field of the Invention [0003] The invention relates to Elliptic Curve Cryptography (ECC), and in particular, to arithmetic circuits for EC operations. [0004] 2. Description of the Related Art [0005] Elliptic Curve Cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985. Elliptic curves are also used in several integer factorization algorithms that have applications in cryptography, such as, for instance, Lenstra elliptic curve factorization, but this use of elliptic curves is not usually referred to as "elliptic curve cryptography." [0006] In ECC, a finite field, also referred to as a Galois field (GF), defines a field that contains only finitely many elements. The GF is typically categorized into two types, a prime field GF(p) and a binary field GF(2.sup.m). The prime field GF(p) is a finite field with p elements, usually labelled 0, 1, 2, . . . p-1, where arithmetic is performed with modulo p. Most of the ECC schemes are related to the prime field GF(p). Often seen examples are, the Elliptic Curve Diffie-Hellman (ECDH) key agreement scheme based on the Diffie-Hellman algorithm, the Elliptic Curve Digital Signature Algorithm (ECDSA) based on the Digital Signature Algorithm, and the ECMQV key agreement scheme based on the MQV key agreement scheme. [0007] Conventionally, for a software based system, the ECC schemes are executed by a CPU cooperated with memory. The memory is accessed rapidly, thus a costly wide-width bus is requested. Specifically designed circuits are proposed to accelerate the EC operations. For example, prior arts in US patents U.S. Pat. No. 6,963,644, U.S. Pat. No. 6,820,105, U.S. Pat. No. 6,691,143 are hardware implementations for various ECC calculations, in which a plurality of multipliers and adders are utilized. Circuits in the published disclosures, however, are designed for particular operations, and the components therein can not be reused or shared by other algorithms. Thus, redundant components are used with considerable costs, and an improvement is therefore desirable. BRIEF SUMMARY OF THE INVENTION [0008] An exemplary embodiment of a cryptographic system is disclosed to implement 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 program data associated with the substitution sequence. An arithmetic logic unit (ALU) is controlled by the ASIC flow controller or the CPU to execute the substitution sequence to output an execution result. [0009] In the ALU, an adder adds or subtracts two input numbers based on an adder trigger signal to generate the execution result. Two selectors controlled by a selection signal, pass values from the register pool to the adder as the input numbers. The adder trigger signal and selection signal are delivered from the ASIC flow controller based on the substitution sequence. [0010] In the register pool, a plurality of registers store the program data associated with the substitution sequence. A dispatcher selectively stores the execution result or program data to one of the registers based on a storage signal. The storage signal is delivered from the ASIC flow controller based on the substitution sequence. [0011] The shift operation may be performed by the register pool. The ASIC flow controller delivers a shift signal to one of the registers when a shift operation is requested, and the register shifts its stored data leftwards or rightwards accordingly. Each selector is coupled to outputs of the registers, selecting one of them to pass an input number to the adder. The registers may be at least 160 bit, 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. [0012] Specifically, the program is an Elliptic Curve (EC) related application comprising point multiplication and addition operations, and prime field multiplication, inversion, addition, and subtraction operations. [0013] The ASIC flow controller converts the point multiplication operations to a sequence comprising only prime field operations and shift operations. Furthermore, the ASIC flow controller converts 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. The conversion of the prime field multiplication and inversion operations is a Montgomery domain transfer. [0014] Another embodiment is an Elliptic Curve operation method, for use in an apparatus only capable of performing arithmetic addition, subtraction and shift operations. A program to be executed is firstly provided. The program is converted into an equivalent substitution sequence comprising only arithmetic addition, subtraction and shift operations. The substitution sequence is then executed and an execution result is output. A detailed description is given in the following embodiments with reference to the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS [0015] The invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: [0016] FIG. 1 shows an embodiment of a cryptographic system 100 according to the invention; [0017] FIG. 2 shows an embodiment of a state machine for Elliptic Curve (EC) operations; [0018] FIG. 3 shows an embodiment of a register pool 210 and an ALU 220 according to FIG. 1; [0019] FIG. 4 is an exemplary flowchart of a key generation procedure; [0020] FIG. 5 is an exemplary flowchart of a point addition operation; and Continue reading... Full patent description for Cryptography system and elliptic curve operation method Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Cryptography system and elliptic curve operation method patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Cryptography system and elliptic curve operation method or other areas of interest. ### Previous Patent Application: Semiconductor device Next Patent Application: Methods for conducting server-side encryption/decryption-on-demand Industry Class: Electrical computers and digital processing systems: support ### FreshPatents.com Support Thank you for viewing the Cryptography system and elliptic curve operation method patent info. IP-related news and info Results in 5.62664 seconds Other interesting Feshpatents.com categories: Software: Finance , AI , Databases , Development , Document , Navigation , Error |
||
