Design And Implementation Of High Performance Coprocessors For Public Key Cryptographic Algorithms

Public key cryptographic algorithms play a very important role in the area of information security. Public key cryptography technology is the primary method to implement identification, authentication and key agreement now. There are three kinds of public key cryptography which is widely used. They are the RSA algorithm which is based on integer factoring problem, the discrete logarithmic problem based DH algorithm, DSA algorithm and ElGamal algorithm, the ECC algorithm which is based on elliptic curve discrete logarithmic problem. In these public key cryptographic algorithms, the kernel operations are modular exponentiation of multi-precision integer and elliptic curve scalar multiplication, which both are computing intensive. In order to improve their computing performance and security, public key cryptographic algorithms are usually implemented by coprocessors.According to the different requirement of performance and hardware complexity for different applications, public key cryptography's application in the area of information security can be split into two categories. One is for advanced applications, such as Certificate Authority of Public Key Infrastructure and TPM of Trusted Computing Platform. The other is for simple applications which aim at embedded systems. According to the different application characters, the research of the design and implementation of public key cryptographic coprocessors can be divided into three primary categories. The first is the high performance ASIC implementation for advanced application. The second is the design and implementation that aims at embedded application. The third is unified and scalable design to satisfy different requirements for different applications.Based on the research and analysis of public key cryptography's implementation technologies and algorithms it selves' characteristics, this paper proposes a coprocessor architecture supporting high performance and cost efficient modular multi-precision integer exponentiation computing for advanced applications. In order to support different public key cryptographic algorithms and satisfy the requirements of different applications, a scalable architecture of public key cryptography coprocessor has been proposed, which not only can be extended to the one with very high performance, but also can be simplified to the one with extreme low complexity.This paper has following contributions:1. The modular multi-precision integer exponentiation coprocessor IP core is a calculating unit of modular multi-precision integer multiplication. Based on the High Radix Carry Save Montgomery Modular Multiplication algorithm, this paper proposes efficient modular multiplication architecture. The key component is a multi-precision integer MAU (Multiplier Accumulator Unit). This architecture can execute two parallel modular multiplications of same size, that is to say, this architecture supports Chinese Remainder Theorem directly.2. Public key cryptographic arithmetic consists of many modular reduction operations. This paper presents a multi-precision integer division algorithm based on Signed Digit representation. Based on this algorithm, modular reduction operations can be implemented efficiently. This can prevent these operations to be the bottleneck of public key cryptographic calculations.3. According to the requirement of reducing the hardware complexity, power dissipation, and improving hardware security, this paper proposes reasonable software and hardwarepartition for the scalable public key cryptography coprocessor. The coprocessor supports public key cryptographic calculating basic operations directly, such as modular multiplication, modular addition and subtraction, and Montgomery pre-processing. Those more complex operations such as modular exponentiation and elliptic curve scalar multiplication are implemented using the software and hardware co-pipelined method.4. In public key cryptography, all operations are defined over the ring Z#, or the finite field GF(P) and GF(2m). The implementations of these operations such as modular multiplication and modular addition or subtraction defined over different field are almost the same. In the scalable public key cryptographic coprocessor, a unified architecture has been proposed to support these operations defined over different fields.5. In the implementation of elliptic curve scalar multiplication, a considerable portion of the whole computing is modular addition or subtraction. In order to accelerate the elliptic curve scalar multiplication, special optimization methods are employed for the modular addition or subtraction operation in the design of scalable public key cryptographic coprocessor. By this means, unneeded compare and reduction is avoided.