| The security of many modern cryptosystems are based on mathematical problems that are widely believed to be very difficult to solve. To break a cryptosystem of this type requires one to solve an instance of this difficult problem. Discrete Logarithm Problem (DLP) is one of the "hard" problems used. This assumption that discrete logarithms are hard to compute is the foundation for the presumed security of a variety of public key schemes, such as Diffie-Hellman key exchange algorithm, ElGamal Cryptosystem and signature scheme. Actually, the security of the first practical public key cryptosystem, the Diffie-Hellman key exchange algorithm relies on a stronger but related assumption called the Diffie-Hellman Indistinguishable assumption (DHI). DHI assumes that certain desirable properties such as uniform distribution are possessed by the Diffie-Hellman triples (Vx, Vy, Vxy), where V is an integer of multiplicative order t modulo p &ge 3 that is Vx &nequiv 1(modp), x = 1,..., t -- 1, Vt &equiv 1( modp). Most of the time the only practical way to solve DHI is to solve the related DLP. For elliptic curve based cryptosystems, the DLP 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.In this thesis, we study the difficulty of the discrete logarithm problem when partial information about the key is revealed by side channel attacks and double exponential sums S&tildea,b,c( t) = x,y=1t ep(aVx + bVy + cVxy) related to the Diffie-Hellman triples (Vx, V y, Vxy). We provided algorithms that 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 located either in the front, middle, or the end portion of the key is revealed. In the second scenario, we assume that (incomplete) information on the "square and Multiply Chain" is revealed. We also show that Diffie-Hellman triples are uniformly distributed via finding bounds on the double exponential sums. |
