tailieunhanh - Low-Power Elliptic Curve Cryptography Using Scaled Modular Arithmetic

We introduce new modulus scaling techniques for transforming a class of primes into special forms which enables efficient arithmetic. The scaling technique may be used to improve multiplication and inversion in finite fields. We present an efficient inversion algorithm that utilizes the structure of scaled modulus. | Low-Power Elliptic Curve Cryptography Using Scaled Modular Arithmetic E. Oztlirk1 B. Sunar1 and E. Savas2 1 Department of Electrical Computer Engineering Worcester Polytechnic Institute Worcester MA 01609 USA erdinc sunar@ 2 Faculty of Engineering and Natural Sciences Sabanci University Istanbul Turkey TR-34956 erkays@ Abstract. We introduce new modulus scaling techniques for transforming a class of primes into special forms which enables efficient arithmetic. The scaling technique may be used to improve multiplication and inversion in finite fields. We present an efficient inversion algorithm that utilizes the structure of scaled modulus. Our inversion algorithm exhibits superior performance to the Euclidean algorithm and lends itself to efficient hardware implementation due to its simplicity. Using the scaled modulus technique and our specialized inversion algorithm we develop an elliptic curve processor architecture. The resulting architecture successfully utilizes redundant representation of elements in GF p and provides a low-power high speed and small footprint specialized elliptic curve implementation. 1 Introduction Modular arithmetic has a variety of applications in cryptography. Many publickey algorithms heavily depend on modular arithmetic. Among these RSA encryption and digital signature schemes discrete logarithm problem DLP based schemes such as the Diffie-Helman key agreement 4 and El-Gamal encryption and signature schemes 8 and elliptic curve cryptography 6 7 play an important role in authentication and encryption protocols. The implementation of RSA based schemes requires the arithmetic of integers modulo a large integer that is in the form of a product of two large primes n p q. On the other hand implementations of Diffie-Helman and El-Gamal schemes are based on the arithmetic of integers modulo a large prime p. While ECDSA is built on complex algebraic structures the underlying arithmetic operations are either modular .