
Let \(p\) be a prime and \(g\), \(x\) integers. The computation of \(y\) such that \(y\equiv g^ x(\mod p)\), \(0\leq y\leq p-1\), is referred to as discrete exponentiation. Given \(p\), \(g\) and \(y\) the computation of \(x\) is referred to as the discrete logarithm problem. Using the best published algorithms the problem has a running time on the order of \[ \exp((1+o(1))(\log p)^{1/2}(\log \log p)^{1/2})\text{ as } p\to\infty, \] which is on the same order as the time required to factor an integer of the same magnitude. This paper describes an attack on the Sun Microsystems Inc. secure identification system which uses discrete exponentiation modulo a prime of 192 bits, giving the first experimental evidence of discrete logarithms modulo a prime. The precomputation stage that constructs a database of logarithms for small primes used the method of Gaussian integers to generate equations. For the Sun prime of interest the database required a few days of computation on moderately sized machines to compute the database of less than one megabyte and a few minutes to then compute a particular logarithm. It is noted that the more recent number field sieve for factoring integers is likely to improve the running time for discrete logarithms.
cryptography, discrete logarithm problem, integer factorization, Cryptography, attack, identification system, Algebraic coding theory; cryptography (number-theoretic aspects), Factorization; primality, discrete exponentiation
cryptography, discrete logarithm problem, integer factorization, Cryptography, attack, identification system, Algebraic coding theory; cryptography (number-theoretic aspects), Factorization; primality, discrete exponentiation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 55 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
