资源受限环境下的适应性窗口多点乘计算方法 2.docVIP

 Adaptive window method for multi-scalar multiplication under resource-constrained environments# 5 10 15 Da-Zhi Sun* (School of Computer Science and Technology, Tianjin University, Tianjin 300072) Abstract: A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-scalar multiplication in a certain finite additive group defined by an elliptic curve. In this paper, we propose an adaptive window method for the multi-scalar multiplication, which can balance the computation cost and the memory cost under the resource-constrained environments. By modeling the scanning process as a Markov chain, we analyze the computational efficiency of this adaptive window method using the non-adjacent form (NAF) representation. When there are 2–4 extra registers, the adaptive window method using the NAF representation on average requires 11%–19% fewer additions than the Shamir trick using the joint sparse form (JSF) representation. In order to reduce the number of required registers, our strategy in the adaptive window method is not to store all values of the possible block pairs in the certain representations of two integers, but only to store those values with high probabilities. Key words: Public-key cryptosystem; Multi-scalar multiplication; Adaptive window method; Non-adjacent form (NAF) representation; Markov chain; Resource-constrained environment 20 0 Introduction A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-exponentiation in a certain finite multiplication group Z *p or the multi-scalar multiplication in a certain finite additive group defined by an 25 30 35 elliptic curve. The representative examples include DSA [1], ECDSA [2], and Schnorr signature scheme [3]. To make it easy for readers to understand, we adopt the symbol system of the multi-scalar multiplication herein. Without loss of generality, all techniques discu