| Elliptic Curve Cryptosystem is a kind of outstanding public-key cryptosystem. It is well known for its advantages like which has wide application in smart card, wireless network and embedded systems with limited resources. As an important part of physical security, side channel attacks menace the security of these systems. Especially, the power attack is very severe for the security of scalar multiplication on Elliptic Curve. This thesis for doctor's degree focuses on the security and efficiency of scalar multiplication on power attack and is to propose fast and secure scalar multiplications. The thesis obtains main results as follows:1. We do detailed analysis on the side channel attacks commonly used. We also propose an improved simple energy attack based on Markov Chain. This method applies the modle of Markov Chain to the anlysis of the processes of secret key from AD sequence, in which Elliptic Curve Cryptosystem scalar multiplication algorithm is used as Markov Chain. Theoretical proofs show that method is more efficient than the normal side-channel attacks.2. This thesis presentes a new SCA resistant Elliptic Curve scalar multiplication algorithm. The proposed algorithm, which builds a sequence of bit-strings representing the scalar k, is characterized by the fact that all bit-strings are different from zero. This character will ensure a uniform computation behavior for the algorithm, and thus make it secure against SPA. Combied with other randomization techniques, this algorithm can resist against other side channel attacks including differential power attack. By compare with other schemes resisting against side chanel atacks,this algorithm does not penalize the computation time and needs only one more point adding and doubling than the comb algorithm.3. A new fast and secure scalar multiplication algorithm is proposed. The algorithm is a particular addition chains based on only additions, which providing a natural protection against side channel attacks. Moreover, new addition formulae which take into account the specific structure of those chains making point multiplication very efficient are proposed. The scalar multiplication algorithm only needs 1719 multiplication for the SAC260 of 160-bit integers. From chains of length 280 to 260, our method outperforms all the previous methods with a increased efficency from 26% to 31% over the double-and-add, from 16% to 22% over NAF, from 7% to 13% over 4-NAF and from 1% to 8% over the best algorithm presently-double base chain. 4. Appling a mathematical operation"( a + b)2 ?a2?b2=2ab"on the computation between points of Jacobian coordinates, and the substitution of multiplication with squaring which is more cheaper than multiplication. Especially, these techniques can reduce the computation of doubling, addition, mixed addition and tripling. Particularly, the efficiency is improved a lot for tripling computation, providing a guarantee for fast scalar multiplication by using multi-base chains methods nowadays.5. We modify the ECC scalar multiplication to achieve a faster atomic structure when applying side channel atomicity protection. In contrast to previous atomic operations that assume squarings are indistinguishable from multiplications, our new atomic structure offers true SSCA-protection resulted from the squaring in its formulation. In the scalar multiplication using NAF, the computational efficency of our atomic blocks is increased by 30% than that of previous atomic implementations.6. Based on the improved NAFw algorithm, we present an efficient and flexible scheme resisting power attacks-the fractional windows. The fractional windows are able to resist not only SPA but also SPA /DPA combined attacks and SPA/2nd-order DPA combined attacks. The fractional windows allow us to select the appropriate window width and offer great advantages in the frame of resource-constrained devices. The fractional windows are more efficent than integral windows...
|
PDF Full Text Request