Springer, Lecture Notes in Computer Science, p. 864-873, 2005
DOI: 10.1007/11596042_89
Full text: Download
Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing sys- tems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy ecien t cryptosystems. Among XTR exponentiation algorithms, the most ecien t one is the Improved XTR Single Ex- ponentiation (XTR-ISE) proposed by Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is the most ecien t one suitable for ubiquitous com- puter. Even though the security of such devices against side channel attacks is very dangerous, there are few works on side channel attacks against XTR-ISE. In this paper we propose a new collision attack on XTR-ISE, derived from the structural properties of XTR-ISE. The analysis complexity of the proposed one is about 240 where the key size is 160-bit, which is 55% improvement from the previously best known analysis of Page-Stam. We also propose a novel countermeasure using a xed pattern which is secure against SPA. We deploy a variant of Euclidean al- gorithm whose one of the registers is a monotone decreasing function with odd value. From our estimation of the eciency of the proposed method, XTR expo- nentiation, computing T r(gn) with T r(g) and n, takes 11:2 log2 n multiplications in Fp2. In the sense of both eciency and security the proposed countermeasure is the best one among the previous countermeasures- it is about 30% faster.