Solving Discrete Logarithms from Partial Knowledge of the Key
For elliptic curve based cryptosystems, the discrete logarithm problem must be hard to solve. But even when this is true from a mathematical point of view, side-channel attacks could be used to reveal information about the key if proper countermeasures ar
- PDF / 427,206 Bytes
- 14 Pages / 430 x 660 pts Page_size
- 8 Downloads / 197 Views
Department of Computer Science, East Carolina University, Greenville, NC 27858 Instituto de Matem´ atica y F´ısica, Universidad de Talca, Casilla 747, Talca, Chile 3 Department of Mathematics, University of California - Riverside, CA 92521
Abstract. For elliptic curve based cryptosystems, the discrete logarithm problem must be hard to solve. But even when this is true from a mathematical point of view, side-channel attacks could be used to reveal information about the key if proper countermeasures are not used. In this paper, we study the difficulty of the discrete logarithm problem when partial information about the key is revealed by side channel attacks. We provide algorithms to solve the discrete logarithm problem for generic groups with partial knowledge of the key which are considerably better than using a square-root attack on the whole key or doing an exhaustive search using the extra information, under two different scenarios. In the first scenario, we assume that a sequence of contiguous bits of the key is revealed. In the second scenario, we assume that partial information on the “Square and Multiply Chain” is revealed. Keywords: Discrete Logarithm Problem, Generic Groups, Side Channel Attacks.
1
Introduction
The discrete logarithm problem (DLP) is an important problem in modern cryptography. The security of various cryptosystems and protocols (such as Diffie-Hellman key exchange protocol, ElGamal cryptosystem, ElGamal signature scheme, DSA, cryptosystems and signature schemes based on elliptic and hyperelliptic curves) relies on the presumed computational difficulty of solving the discrete logarithm problem. For a survey of the discrete logarithm problem, the reader is referred to [13]. However, even if the DLP is indeed difficult to solve, one has to take other aspects into account in practical implementations. If proper countermeasures are not used, side-channel attacks could be used to reveal partial information about the key. In this paper, we address the problem of how to utilize the partial information effectively when solving the DLP.
This work was done in parts while the author was at the Institute of Pure and Applied Mathematics, UCLA. This work was done in parts while the author was at the Fields Institute, Toronto, Canada.
K. Srinathan, C. Pandu Rangan, M. Yung (Eds.): Indocrypt 2007, LNCS 4859, pp. 224–237, 2007. c Springer-Verlag Berlin Heidelberg 2007
Solving Discrete Logarithms from Partial Knowledge of the Key
225
When one wants to break a system based on DLP, one can of course, ignore the partial information revealed by side channel attacks and simply use a generic algorithm. Alternatively, one can use an exhaustive search using the partial information made available to us. The primary question that we address in this paper is whether we can do something in between? i.e., can we use the partial information revealed by side channel attacks in an intelligent way to break the system? In some cases, side channel attacks could reveal a string of contiguous bits of the secret key. In th
Data Loading...
