To resist the side chaimel attacks of elliptic curve cryptography, a new fast and secure point multiplication algorithm is proposed. The algorithm is based on a particular kind of addition chains involving only additi...To resist the side chaimel attacks of elliptic curve cryptography, a new fast and secure point multiplication algorithm is proposed. The algorithm is based on a particular kind of addition chains involving only additions, providing a natural protection against side channel attacks. Moreover, the new addition formulae that take into account the specific structure of those chains making point multiplication very efficient are proposed. The point multiplication algorithm only needs 1 719 multiplications for the SAC260 of 160-bit integers. For chains of length from 280 to 260, the proposed method outperforms all the previous methods with a gain of 26% to 31% over double-and add, 16% to22% over NAF, 7% to 13% over4-NAF and 1% to 8% over the present best algorithm--double-base chain.展开更多
This paper gives a comprehensive method to do Elliptic Curve Scalar Multiplication with only x-coordinate. Explicit point operation formulae for all types of defining equations of the curves are derived. For each type...This paper gives a comprehensive method to do Elliptic Curve Scalar Multiplication with only x-coordinate. Explicit point operation formulae for all types of defining equations of the curves are derived. For each type of curve, the performance is analyzed. The formulae are applied in Montgomery Ladder to get scalar multiplication algorithm operated with only x-coordinate. The new scalar multiplication has the same security level and computation amount with protected binary scalar multiplication (PBSM) against side channel attack, and has the advantages of higher security and little memory needed.展开更多
The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over eve...The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding multiplier by modulo Υk-1 +…+Υ+ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over展开更多
Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding...Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that q^s can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than φ-ary method. For some elliptic curves, our algorithm is also taster than Mǖller's algorithm. In addition, an effective algorithm is provided for finding such integer s.展开更多
Scalar multiplication [n]P is the kernel and the most time-consuming operation in elliptic curve cryptosystems. In order to improve scalar multiplication, in this paper, we propose a tripling algorithm using Lopez and...Scalar multiplication [n]P is the kernel and the most time-consuming operation in elliptic curve cryptosystems. In order to improve scalar multiplication, in this paper, we propose a tripling algorithm using Lopez and Dahab projective coordinates, in which there are 3 field multiplications and 3 field squarings less than that in the Jacobian projective tripling algorithm. Furthermore, we map P to(φε^-1(P), and compute [n](φε^-1(P) on elliptic curve Eε, which is faster than computing [n]P on E, where φε is an isomorphism. Finally we calculate (φε([n]φε^-1(P)) = [n]P. Combined with our efficient point tripling formula, this method leads scalar multiplication using double bases to achieve about 23% improvement, compared with Jacobian projective coordinates.展开更多
The focal point of this paper is to present the theoretical aspects of the building blocks of the upper bounds of ISD (integer sub-decomposition) method defined by kP = k11P + k12ψ1 (P) + k21P + k22ψ2 (P) w...The focal point of this paper is to present the theoretical aspects of the building blocks of the upper bounds of ISD (integer sub-decomposition) method defined by kP = k11P + k12ψ1 (P) + k21P + k22ψ2 (P) with max {|k11|, |k12|} 〈 Ca√n and max{|k21|, |k22|}≤C√, where C=I that uses efficiently computable endomorphisms ψj for j=1,2 to compute any multiple kP of a point P of order n lying on an elliptic curve E. The upper bounds of sub-scalars in ISD method are presented and utilized to enhance the rate of successful computation of scalar multiplication kP. Important theorems that establish the upper bounds of the kernel vectors of the ISD reduction map are generalized and proved in this work. The values of C in the upper bounds, that are greater than 1, have been proven in two cases of characteristic polynomials (with degree 1 or 2) of the endomorphisms. The upper bound of ISD method with the case of the endomorphism rings over an integer ring Z results in a higher rate of successful computations kP. Compared to the case of endomorphism rings, which is embedded over an imaginary quadratic field Q = [4-D]. The determination of the upper bounds is considered as a key point in developing the ISD elliptic scalar multiplication technique.展开更多
The last decade witnessed rapid increase in multimedia and other applications that require transmitting and protecting huge amount of data streams simultaneously.For such applications,a high-performance cryptosystem i...The last decade witnessed rapid increase in multimedia and other applications that require transmitting and protecting huge amount of data streams simultaneously.For such applications,a high-performance cryptosystem is compulsory to provide necessary security services.Elliptic curve cryptosystem(ECC)has been introduced as a considerable option.However,the usual sequential implementation of ECC and the standard elliptic curve(EC)form cannot achieve required performance level.Moreover,the widely used Hardware implementation of ECC is costly option and may be not affordable.This research aims to develop a high-performance parallel software implementation for ECC.To achieve this,many experiments were performed to examine several factors affecting ECC performance including the projective coordinates,the scalar multiplication algorithm,the elliptic curve(EC)form,and the parallel implementation.The ECC performance was analyzed using the different factors to tune-up them and select the best choices to increase the speed of the cryptosystem.Experimental results illustrated that parallel Montgomery ECC implementation using homogenous projection achieves the highest performance level,since it scored the shortest time delay for ECC computations.In addition,results showed thatNAF algorithm consumes less time to perform encryption and scalar multiplication operations in comparison withMontgomery ladder and binarymethods.Java multi-threading technique was adopted to implement ECC computations in parallel.The proposed multithreaded Montgomery ECC implementation significantly improves the performance level compared to previously presented parallel and sequential implementations.展开更多
Side-channel attacks (SCA) may exploit leakage information to break cryptosystems. In this paper we present a new SCA resistant Elliptic Curve scalar multiplication algorithm. The proposed algorithm, builds a sequen...Side-channel attacks (SCA) may exploit leakage information to break cryptosystems. In this paper we present a new SCA resistant Elliptic Curve scalar multiplication algorithm. The proposed algorithm, builds a sequence of bit-strings representing the scalar k, characterized by the fact that all bit-strings are different from zero; this property will ensure a uniform computation behavior for the algorithm, and thus will make it secure against simple power analysis attacks (SPA). With other randomization techniques, the proposed countermeasures do not penalize the computation time. The proposed scheme is more efficient than MOEller's one, its cost being about 5% to 10% smaller than MOEller's one.展开更多
In this article, a parallel hardware processor is presented to compute elliptic curve scalar multiplication in polynomial basis representation. The processor is applicable to the operations of scalar multiplication by...In this article, a parallel hardware processor is presented to compute elliptic curve scalar multiplication in polynomial basis representation. The processor is applicable to the operations of scalar multiplication by using a modular arithmetic logic unit (MALU). The MALU consists of two multiplications, one addition, and one squaring. The two multiplications and the addition or squaring can be computed in parallel. The whole computations of scalar multiplication over GF(2^163) can be performed in 3 064 cycles. The simulation results based on Xilinx Virtex2 XC2V6000 FPGAs show that the proposed design can compute random GF(2^163) elliptic curve scalar multiplication operations in 31.17 μs, and the resource occupies 3 994 registers and 15 527 LUTs, which indicates that the crypto-processor is suitable for high-performance application.展开更多
Hybrid signcryption is an important technique signcrypting bulk data using symmetric encryption. In this paper, we apply the technique of certificateless hybrid signcryption to an elliptic-curve cryptosystem, and cons...Hybrid signcryption is an important technique signcrypting bulk data using symmetric encryption. In this paper, we apply the technique of certificateless hybrid signcryption to an elliptic-curve cryptosystem, and construct a low-computation certificateless hybrid signcryption scheme. In the random oracle model, this scheme is proven to have indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) under the elliptic-curve computation Diffie-Hellman assumption. Also, it has a strong existential unforgeability against adaptive chosen-message attacks (sUF-CMA) under the elliptic-curve discrete logarithm assumption. Analysis shows that the cryptographic algorithm does not rely on pairing operations and is much more etticient than other algorithms. In addition, it suits well to applications in environments where resources are constrained, such as wireless sensor networks and ad hoc networks.展开更多
In this paper,we present the generalized Huff curves that contain Huff's model as a special case.First,it is proved that every elliptic curve with three points of order 2 is isomorphic to a generalized Huff curve.The...In this paper,we present the generalized Huff curves that contain Huff's model as a special case.First,it is proved that every elliptic curve with three points of order 2 is isomorphic to a generalized Huff curve.Then,the fast and explicit formulae are derived for generalized Huff curves in projective coordinates.This paper also enumerates the number of isomorphism classes of generalized Huff curves over finite fields.Finally,the explicit formulae are presented for the doubling step and addition step in Miller's algorithm to compute the Tate pairing on generalized Huff elliptic curves.展开更多
We propose a novel high-performance hardware architecture of processor for elliptic curve scalar multiplication based on the Lopez-Dahab algorithm over GF(2^163) in polynomial basis representation. The processor can...We propose a novel high-performance hardware architecture of processor for elliptic curve scalar multiplication based on the Lopez-Dahab algorithm over GF(2^163) in polynomial basis representation. The processor can do all the operations using an efficient modular arithmetic logic unit, which includes an addition unit, a square and a carefully designed multiplication unit. In the proposed architecture, multiplication, addition, and square can be performed in parallel by the decomposition of computation. The point addition and point doubling iteration operations can be performed in six multiplications by optimization and solution of data dependency. The implementation results based on Xilinx VirtexⅡ XC2V6000 FPGA show that the proposed design can do random elliptic curve scalar multiplication GF(2^163) in 34.11 μs, occupying 2821 registers and 13 376 LUTs.展开更多
基金The National Natural Science Foundation of China (No.60473029,60673072).
文摘To resist the side chaimel attacks of elliptic curve cryptography, a new fast and secure point multiplication algorithm is proposed. The algorithm is based on a particular kind of addition chains involving only additions, providing a natural protection against side channel attacks. Moreover, the new addition formulae that take into account the specific structure of those chains making point multiplication very efficient are proposed. The point multiplication algorithm only needs 1 719 multiplications for the SAC260 of 160-bit integers. For chains of length from 280 to 260, the proposed method outperforms all the previous methods with a gain of 26% to 31% over double-and add, 16% to22% over NAF, 7% to 13% over4-NAF and 1% to 8% over the present best algorithm--double-base chain.
基金Supported by Natural Science Basic Research Plan in Shaanxi Province of China(2005F28)
文摘This paper gives a comprehensive method to do Elliptic Curve Scalar Multiplication with only x-coordinate. Explicit point operation formulae for all types of defining equations of the curves are derived. For each type of curve, the performance is analyzed. The formulae are applied in Montgomery Ladder to get scalar multiplication algorithm operated with only x-coordinate. The new scalar multiplication has the same security level and computation amount with protected binary scalar multiplication (PBSM) against side channel attack, and has the advantages of higher security and little memory needed.
基金Supported by the National Natural Science Foundation of China(No.90104004) the National 973 High Technology Projects(No.G1998030420)
文摘The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding multiplier by modulo Υk-1 +…+Υ+ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over
基金Supported by the National 973 High Technology Projects (No. G1998030420)
文摘Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that q^s can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than φ-ary method. For some elliptic curves, our algorithm is also taster than Mǖller's algorithm. In addition, an effective algorithm is provided for finding such integer s.
基金Supported by the National Natural Science Foundation of China (60573031)
文摘Scalar multiplication [n]P is the kernel and the most time-consuming operation in elliptic curve cryptosystems. In order to improve scalar multiplication, in this paper, we propose a tripling algorithm using Lopez and Dahab projective coordinates, in which there are 3 field multiplications and 3 field squarings less than that in the Jacobian projective tripling algorithm. Furthermore, we map P to(φε^-1(P), and compute [n](φε^-1(P) on elliptic curve Eε, which is faster than computing [n]P on E, where φε is an isomorphism. Finally we calculate (φε([n]φε^-1(P)) = [n]P. Combined with our efficient point tripling formula, this method leads scalar multiplication using double bases to achieve about 23% improvement, compared with Jacobian projective coordinates.
文摘The focal point of this paper is to present the theoretical aspects of the building blocks of the upper bounds of ISD (integer sub-decomposition) method defined by kP = k11P + k12ψ1 (P) + k21P + k22ψ2 (P) with max {|k11|, |k12|} 〈 Ca√n and max{|k21|, |k22|}≤C√, where C=I that uses efficiently computable endomorphisms ψj for j=1,2 to compute any multiple kP of a point P of order n lying on an elliptic curve E. The upper bounds of sub-scalars in ISD method are presented and utilized to enhance the rate of successful computation of scalar multiplication kP. Important theorems that establish the upper bounds of the kernel vectors of the ISD reduction map are generalized and proved in this work. The values of C in the upper bounds, that are greater than 1, have been proven in two cases of characteristic polynomials (with degree 1 or 2) of the endomorphisms. The upper bound of ISD method with the case of the endomorphism rings over an integer ring Z results in a higher rate of successful computations kP. Compared to the case of endomorphism rings, which is embedded over an imaginary quadratic field Q = [4-D]. The determination of the upper bounds is considered as a key point in developing the ISD elliptic scalar multiplication technique.
基金Authors extend their appreciation to the Deanship of Scientific Research at Imam Mohammad Ibn Saud Islamic University for funding and supporting this work through Graduate Student Research Support Program.
文摘The last decade witnessed rapid increase in multimedia and other applications that require transmitting and protecting huge amount of data streams simultaneously.For such applications,a high-performance cryptosystem is compulsory to provide necessary security services.Elliptic curve cryptosystem(ECC)has been introduced as a considerable option.However,the usual sequential implementation of ECC and the standard elliptic curve(EC)form cannot achieve required performance level.Moreover,the widely used Hardware implementation of ECC is costly option and may be not affordable.This research aims to develop a high-performance parallel software implementation for ECC.To achieve this,many experiments were performed to examine several factors affecting ECC performance including the projective coordinates,the scalar multiplication algorithm,the elliptic curve(EC)form,and the parallel implementation.The ECC performance was analyzed using the different factors to tune-up them and select the best choices to increase the speed of the cryptosystem.Experimental results illustrated that parallel Montgomery ECC implementation using homogenous projection achieves the highest performance level,since it scored the shortest time delay for ECC computations.In addition,results showed thatNAF algorithm consumes less time to perform encryption and scalar multiplication operations in comparison withMontgomery ladder and binarymethods.Java multi-threading technique was adopted to implement ECC computations in parallel.The proposed multithreaded Montgomery ECC implementation significantly improves the performance level compared to previously presented parallel and sequential implementations.
基金Supported by the National Natural ScienceFoundation of China (60473029)
文摘Side-channel attacks (SCA) may exploit leakage information to break cryptosystems. In this paper we present a new SCA resistant Elliptic Curve scalar multiplication algorithm. The proposed algorithm, builds a sequence of bit-strings representing the scalar k, characterized by the fact that all bit-strings are different from zero; this property will ensure a uniform computation behavior for the algorithm, and thus will make it secure against simple power analysis attacks (SPA). With other randomization techniques, the proposed countermeasures do not penalize the computation time. The proposed scheme is more efficient than MOEller's one, its cost being about 5% to 10% smaller than MOEller's one.
基金supported by the Hi-Tech Research and Development Program of China(2006AA01Z226)the Research Foundation of Huazhong University of Science and Technology(2006Z001B)
文摘In this article, a parallel hardware processor is presented to compute elliptic curve scalar multiplication in polynomial basis representation. The processor is applicable to the operations of scalar multiplication by using a modular arithmetic logic unit (MALU). The MALU consists of two multiplications, one addition, and one squaring. The two multiplications and the addition or squaring can be computed in parallel. The whole computations of scalar multiplication over GF(2^163) can be performed in 3 064 cycles. The simulation results based on Xilinx Virtex2 XC2V6000 FPGAs show that the proposed design can compute random GF(2^163) elliptic curve scalar multiplication operations in 31.17 μs, and the resource occupies 3 994 registers and 15 527 LUTs, which indicates that the crypto-processor is suitable for high-performance application.
基金the National Natural Science Foundation of China (Nos. 61572303, 61363080, and 61272436), the Foundation of State Key Laboratory of Information Security (No. 2015-MS-10), and the Foundation of Basic Research of Qinghai Province, China (No. 2016-ZJ-776)
文摘Hybrid signcryption is an important technique signcrypting bulk data using symmetric encryption. In this paper, we apply the technique of certificateless hybrid signcryption to an elliptic-curve cryptosystem, and construct a low-computation certificateless hybrid signcryption scheme. In the random oracle model, this scheme is proven to have indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) under the elliptic-curve computation Diffie-Hellman assumption. Also, it has a strong existential unforgeability against adaptive chosen-message attacks (sUF-CMA) under the elliptic-curve discrete logarithm assumption. Analysis shows that the cryptographic algorithm does not rely on pairing operations and is much more etticient than other algorithms. In addition, it suits well to applications in environments where resources are constrained, such as wireless sensor networks and ad hoc networks.
基金Supported by the National Natural Science Foundation of China (11101002,10990011)
文摘In this paper,we present the generalized Huff curves that contain Huff's model as a special case.First,it is proved that every elliptic curve with three points of order 2 is isomorphic to a generalized Huff curve.Then,the fast and explicit formulae are derived for generalized Huff curves in projective coordinates.This paper also enumerates the number of isomorphism classes of generalized Huff curves over finite fields.Finally,the explicit formulae are presented for the doubling step and addition step in Miller's algorithm to compute the Tate pairing on generalized Huff elliptic curves.
基金supported by the Hi-Tech Research and Development Program (863) of China (No. 2006AA01Z226)the Research Foun dation of Huazhong University of Science and Technology, China (No. 2006Z001B)
文摘We propose a novel high-performance hardware architecture of processor for elliptic curve scalar multiplication based on the Lopez-Dahab algorithm over GF(2^163) in polynomial basis representation. The processor can do all the operations using an efficient modular arithmetic logic unit, which includes an addition unit, a square and a carefully designed multiplication unit. In the proposed architecture, multiplication, addition, and square can be performed in parallel by the decomposition of computation. The point addition and point doubling iteration operations can be performed in six multiplications by optimization and solution of data dependency. The implementation results based on Xilinx VirtexⅡ XC2V6000 FPGA show that the proposed design can do random elliptic curve scalar multiplication GF(2^163) in 34.11 μs, occupying 2821 registers and 13 376 LUTs.