Patent ID: 9077536
Filing Date: 2015-07-07
Classification: G06F,H04L

Abstract:
1. A method, performed by a server, of generating a pre-computation table and computing a discrete logarithm based on the pre-computation table, the method comprising: setting, by a controller of the server, p−1 and q−1 so that each p−1 and q−1 has at least one prime factor larger than B bits and N=pq is used as a modulus in the computing of the discrete logarithm, and both p and q are primes; generating, by the controller of the server, the pre-computation table consisting of chains of function values obtained by applying an iterating function to a predetermined number of initial values having a generator of the cyclic group as a base and having different exponents; and if a first function value obtained by applying the iterating function to a value having a target element as a base and having an exponent is identical to a second function value stored in the pre-computation table, computing the discrete logarithm of the target element by using exponent information of the first function value and the second function value, wherein the B bits are a predetermined number of bits relating to a secret key.