Efficient Integer Representations For Public Key Cryptosystems

RSA and Elliptic Curve Cryptosystem (ECC) that made security in electronic environments are two commonly used public key cryptosystems. The basic mathematic operation in above cryptosystems is scalar multiplication which can be computed using the binary algorithm. It is well known that the representation of an integer with few nonzero digits allows the basic algebraic operations (here is scalar multiplication) to be done more quickly. Such as NAF algorithm, it can reduce about 1/3 point addition than general binary algorithm. However the scalar multiplication using low nonzero density representation is vulnerable to the so-called side channel attacks which exploit leakage information by cryptographic devices such as computational time, power traces and etc. This paper is concerned with both various representations of integers that are related to efficient implementations of basic algebraic operations in public key cryptosystems and various representations of integers that are security against side channel attacks.The topics of this paper include:1. Left-to-right minimal weight signed-digit radix-r representation. Recently, radix-r representation is used to speed up the scalar multiplication of pairing based cryptosystems with characteristic r. At ISC 2004, Takagi et al. introduced the width-w rNAF for the signed digit radix-r representation, which is obtained from right to left. We present a new signed radix-r representation with the same average weight as wrNAF, that is (r-1)/(w(r-1)+1). The new representation can be obtained using a left-to-right algorithm and has a minimal number of non-zero digits among all the representations with the same digit set as wrNAF. We compare our algorithm with previous ones and it shows that in pairing passed cryptosystems, our algorithm can reduce both the time and space complexity of scalar multiplication than previous ones.2. Security analysis of wrNAF and SPA resistant scalar multiplication. Signed digit radix-r representation is used for the efficient implementation of the scalar multiplication. However, the side-channel attack which uses the leaked information such as computational time, power traces from a cryptosystem, is a serious threat to the implementations of a cryptosystem. We utilize the simple power analysis technique to analyze the security of wNAF, and we can see that the wNAF is not a SPA resistant recoding. In order to resist against SPA, we present two integer recodings (right-to-left and left-to-right) using two special digit sets respectively. The two recodings can be used to perform the scalar multiplication with a fixed sequence of operations without inserting dummy operations. Compared to Han's fixed pattern scheme, the proposed schemes can reduce about 16.7% to 37.5% table sizes (the number of precomputed and needed to be stored points) for r=3, 5 and w=2, 3, 4, 5.3. Further cryptanalysis of a provably secure CRT-RSA algorithm. At CCS 2003, a new fault immune CRT-RSA signature algorithm namely BOS algorithm was proposed by Bldmer, Otto, and Seifert. Unfortunately, one year later Wagner presented a simple and practical attack on the BOS algorithm. We further analyze the security of the BOS algorithm and present a new fault attack which can be described as followings: The adversaries first induce a permanent fault on the secret RSA key d_p and then run the BOS algorithm to obtain four faulty RSA signatures. Lastly, the adversaries use the Greatest Common Divisor algorithm to obtain the factorization of the RSA modulus.