A Fast Diffie—Hellman Protocol in Genus 2

In this paper it is shown how the multiplication by M map on the Kummer surface of a curve of genus 2 defined over can be used to construct a Diffie—Hellman protocol. We show that this map can be computed using only additions and multiplications in . In particular we do not use any divisions, polynomial arithmetic, or square root functions in , hence this may be easier to implement than multiplication by M on the Jacobian. In addition we show that using the Kummer surface does not lead to any loss in security. Received 21 November 1996 and revised 28 March 1997     

High-throughput cryptographic system using window-based modular exponentiation for secure communications

Modular exponentiation is an essential arithmetic operation for various applications, such as cryptography. The performance of this operation has a tremendous impact on the efficiency of the whole application. Therefore, many researchers devoted special interest to providing smart methods and efficient implementations for that operation. One of these methods is the sliding-window method, which pre-processes the exponent into zero and non-zero partitions. Zero partitions allow for a reduction of the number of modular multiplications required in the exponentiation process. In this paper, we devise two novel hardware designs for computing modular exponentiation using the sliding-window method: one uses the constant-length non-zero partitions strategy (CLNZ) and the other uses the variable-length non-zero partitions strategy (VLNZ). The implementations are compared to existing hardware implementations of the modular exponentiation in terms of hardware area, time and throughput requirements.     

Design of flexible GF(2/sup m/) elliptic curve cryptography processors

The design of flexible elliptic curve cryptography processors (ECP) is considered in this paper. Novel word-level algorithms and implementations for the underlying GF(2/sup m/) multiplication and squaring arithmetic which enable improved flexibility versus performance tradeoffs, are presented and employed in the design of an efficient flexible ECP architecture; corresponding field-programmable gate-array (FPGA) prototyping results for two different processor word lengths are also included for evaluation.     

Fractal circuit layout for spatial decorrelation of images

Peano-Hilbert curves can be used to destroy the spatial autocorrelation of an image. The effectiveness of the approach, which applies to cryptography and associative memories, stems from the fractal structure of such curves. The fractal topology supports pseudo-random pixel remapping, and the self-similarity of the layout strongly simplifies electronic circuit implementations     

Algorithms and architectures for a flexible elliptic curve cryptography processor

In this paper algorithms and architectures for an new versatile type of elliptic curve cryptography processor over Galois fields GF(2 ^m ) are presented. Due to its flexibility, it readily permits changes in the system security parameters. The processor has, at its core, a novel method of performing arithmetic in GF(2 ^m ). The implementation aspects and design trade-offs of such a processor in comparison with more traditional implementations are examined through prototyping on FPGA technology.     

Elliptic curve cryptosystems and their implementation

Elliptic curves have been extensively studied for many years. Recent interest has revolved around their applicability to factoring integers, primality testing, and to cryptography. In this paper we explore the feasibility of implementing in hardware an arithmetic processor for doing elliptic curve computations over finite fields. Of special interest, for practical reasons, are the curves over fields of characteristic 2. The elliptic curve analogue of the ElGamal cryptosystem is also analyzed.     

Efficient modular multiplication for programmable smart-cards

In this paper, we deal with efficient modular multiplication algorithms working with large integers on programmable smart-cards. The current smart-cards don’t contain a library supporting modular arithmetic operations, which is needed in advanced cryptography schemes. Fortunately, the smart-cards contain a crypto co-processor providing a cryptographic support that can help with the acceleration of modular multiplication. The performance of three classical methods for modular multiplication with large integers and one method using a crypto co-processor is analyzed in this paper. The results of our implementation of modular arithmetic operations with the accelerated multiplication can be useful for the construction of advanced cryptographic schemes.     

On Parallelization of High-Speed Processors for Elliptic Curve Cryptography

This paper discusses parallelization of elliptic curve cryptography hardware accelerators using elliptic curves over binary fields $BBF_{2^{m}}$. Elliptic curve point multiplication, which is the operation used in every elliptic curve cryptosystem, is hierarchical in nature, and parallelism can be utilized in different hierarchy levels as shown in many publications. However, a comprehensive analysis on the effects of parallelization has not been previously presented. This paper provides tools for evaluating the use of parallelism and shows where it should be used in order to maximize efficiency. Special attention is given for a family of curves called Koblitz curves because they offer very efficient point multiplication. A new method where the latency of point multiplication is reduced with parallel field arithmetic processors is introduced. It is shown to outperform the previously presented multiple field multiplier techniques in the cases of Koblitz curves and generic curves with fixed base points. A highly efficient general elliptic curve cryptography processor architecture is presented and analyzed. Based on this architecture and analysis on the effects of parallelization, a few designs are implemented on an Altera Stratix II field-programmable gate array (FPGA).      

Using Abelian Varieties to Improve Pairing-Based Cryptography

We show that supersingular Abelian varieties can be used to obtain higher MOV security per bit, in all characteristics, than supersingular elliptic curves. We give a point compression/decompression algorithm for primitive subgroups associated with elliptic curves that gives shorter signatures, ciphertexts, or keys for the same security while using the arithmetic on supersingular elliptic curves. We determine precisely which embedding degrees are possible for simple supersingular Abelian varieties over finite fields and define some invariants that are better measures of cryptographic security than the embedding degree. We construct examples of good supersingular Abelian varieties to use in pairing-based cryptography. Preliminary versions of parts of this paper appeared in the proceedings of Crypto 2002 38, ANTS VI 40 and the Daewoo Workshop on Cryptography 46.     

改进椭圆曲线加密算法抗边际信道攻击的研究

纯粹的加密算法的应用对于边际信道的攻击的防御是比较弱的，椭圆加密算法是近年来人们认为加密能力比较强的算法之一。本文讨论了目前存在的增强椭圆曲线算法抗边际信道攻击的方法，就其可行性提出了一些看法．并对其中几种方法的时间、空间复杂度进行比较。最后探讨了此类研究的应用前景。     

Structuring of Contourlet Transform for Pipeline-Based Implementation

Contourlet transform (CT) is a powerful image processing tool. Even though many promising applications have been proposed, no hardware implementation of CT has been reported. This paper analyzes CT to form a structure which is hardware implementable. CT consists of two main parts, Laplacian pyramid (LP) and directional filter bank (DFB). In both parts, novel algorithmic changes are proposed for realizing efficient hardware architecture. In the proposed LP structure, 50 % of the arithmetic operations have been reduced and it operates twice as fast as the existing implementations. To the best of our knowledge, DFB has not comprehensively been studied for hardware implementation so far. Thus, we first analyze DFB to figure out its hardware-oriented structure and then propose DFB architecture. Finally, analysis and simulation results demonstrate that the proposed CT architecture achieves the real-time performance (40 frame/s) operating at 76 MHz which is verified through FPGA implementation. Moreover, since all stages utilize fixed-point arithmetic operations, the comprehensive quantization analysis is performed to keep the MSE and PSNR values in an acceptable range.     

基于演化密码理论的Koblitz安全曲线选择研究及对美国NIST参数验证

Elliptic curve cryptography is one of the most important public key cryptography. The Koblitz Curve is a special kind of elliptic curve in ECC and its security mainly depends on the base field. Based on Evolutionary Cryptography theory, which becomes a principal concept for cryptography design and cryptanalysis, we propose a new algorithm for secure EC generation based on Ant Colony Optimization (ACO) to accelerate the search process of safe base field. We preliminarily deal with secure Koblitz curve selecting over the field F(2800). Experiments show that the base field and base point of secure curves generated by ant colony algorithm have gone beyond the parameter range of Koblitz curves recommended by NIST. We can present many new secure Koblitz curves, including base field and base point, which are not recommended by NIST. The maximum size of our secure Koblitz curve has gone beyond 700bit. The algorithm in this paper follows the same cryptography criteria recommended by the ANSI. So, it can resist current attacks. Theoretical analysis and experimental results prove that the new algorithm is effective and successful, and it is the first successful practice of Evolutionary Cryptography theory in public cryptography research.     

Efficient architectures for modulo 2n − 2 arithmetic units

Moduli of the 2ⁿ and 2ⁿ ± 1 forms are usually employed in designs that adopt the residue number system. However, in several cases such as in finite impulse response filters and communication components, a modulo value equal to 2ⁿ ? 2 can be used. So far, modulo 2ⁿ ? 2 arithmetic units have been based either on look-up tables or on generic modulo arithmetic units. In this work, by taking advantage of the properties of modulo 2ⁿ ? 2 arithmetic, we propose efficient modulo 2ⁿ ? 2 multi-operand adder, multiplier as well as squarer architectures. The proposed circuits are based on the corresponding ones for modulo 2^n?1 ? 1 arithmetic and some simple logic. Experimental results validate that the proposed circuits achieve significant area and delay savings compared to those previously presented.     

Hyperelliptic Curve Crypto‐Coprocessor over Affine and Projective Coordinates

This paper presents the design and implementation of a hyperelliptic curve cryptography (HECC) coprocessor over affine and projective coordinates, along with measurements of its performance, hardware complexity, and power consumption. We applied several design techniques, including parallelism, pipelining, and loop unrolling, in designing field arithmetic units, group operation units, and scalar multiplication units to improve the performance and power consumption. Our affine and projective coordinate‐based HECC processors execute in 0.436 ms and 0.531 ms, respectively, based on the underlying field GF(2⁸⁹). These results are about five times faster than those for previous hardware implementations and at least 13 times better in terms of area‐time products. Further results suggest that neither case is superior to the other when considering the hardware complexity and performance. The characteristics of our proposed HECC coprocessor show that it is applicable to high‐speed network applications as well as resource‐constrained environments, such as PDAs, smart cards, and so on.     

Customizable elliptic curve cryptosystems

This paper presents a method for producing hardware designs for elliptic curve cryptography (ECC) systems over the finite field GF(2/sup m/), using the optimal normal basis for the representation of numbers. Our field multiplier design is based on a parallel architecture containing multiple m-bit serial multipliers; by changing the number of such serial multipliers, designers can obtain implementations with different tradeoffs in speed, size and level of security. A design generator has been developed which can automatically produce a customised ECC hardware design that meets user-defined requirements. To facilitate performance characterization, we have developed a parametric model for estimating the number of cycles for our generic ECC architecture. The resulting hardware implementations are among the fastest reported: for a key size of 270 bits, a point multiplication in a Xilinx XC2V6000 FPGA at 35 MHz can run over 1000 times faster than a software implementation on a Xeon computer at 2.6 GHz.     

Elliptic Curves with Low Embedding Degree

Miyaji, Nakabayashi and Takano have recently suggested a construction of the so-called MNT elliptic curves with low embedding degree, which are also of importance for pairing-based cryptography. We give some heuristic arguments which suggest that there are only about z^{1/2+ o(1)} of MNT curves with complex multiplication discriminant up to z. We also show that there are very few finite fields over which elliptic curves with small embedding degree and small complex multiplication discriminant may exist (regardless of the way they are constructed).     

Residue-weighted number conversion using signed-digit number for moduli set {22n − 1, 22n+1 − 1, 2 n }

By introducing a signed-digit (SD) number arithmetic into a residue number system, arithmetic operations can be performed efficiently. In this paper, a new residue-to-binary conversion algorithm for three-moduli set {2²ⁿ  ? 1, 2²ⁿ⁺¹ ? 1, 2 ⁿ } using the residue SD number addition is proposed. Based on the proposed algorithm, the converter can be designed with only four high-speed SD number adders. The comparison of the proposed converter using SD number arithmetic with the converter using binary arithmetic yields more efficient both in terms of area and time.     

An accurate prediction model for computational overheads of security mechanisms in Wireless Sensor Networks

In Wireless Sensor Networks (WSNs), it is necessary to predict computational overheads of security mechanisms without final implementations to provide guidelines for system design. This paper presents an accurate and flexible model to predict overheads of these mechanisms. This model is based on overheads of basic operations frequently used in cryptography algorithms, which are essential elements of security mechanisms. Several popular cryptography algorithms and security mechanisms are evaluated using this model. According to simulation results, relative prediction errors are less than 7% for most cryptography algorithms and security mechanisms.     

Hardware operators for function evaluation using sparse-coefficient polynomials

Dedicated hardware arithmetic operators for function evaluation are presented. The proposed solution uses polynomial approximations with sparse coefficients which leads to efficient hardware implementations. Up to 2times faster and 8times smaller operators are reported compared to standard implementations     

A One Round Protocol for Tripartite Diffie–Hellman

In this paper we propose a three participants variation of the Diffie--Hellman protocol. This variation is based on the Weil and Tate pairings on elliptic curves, which were first used in cryptography as cryptanalytic tools for reducing the discrete logarithm problem on some elliptic curves to the discrete logarithm problem in a finite field.