26 votes
Accepted

Why was the term "discrete" used in discrete logarithm?

The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group. The standard logarithmic problem is over the infinite group $\...
user avatar
  • 132k
21 votes

What is the key size currently used by RSA and Diffie-Hellman for secure communication over Internet?

A good overview on that matter can always be found on https://keylength.com, which summarises many publications with recommendations for key lengths. Especially NIST SP-800-38 yields good data for ...
user avatar
  • 2,458
21 votes
Accepted

What is the key size currently used by RSA and Diffie-Hellman for secure communication over Internet?

Currently (as of 2017-05-11) 2048-bit keys are most popular for use with RSA, and 2048 bit keys should also be used with classic Diffie-Hellman. These offer about the same security as a symmetric ...
user avatar
  • 2,217
20 votes
Accepted

RSA & DH at risk due to math advances, will this eventually affect elliptic curves too?

A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little ...
user avatar
  • 4,548
18 votes

How can there be insecure elliptic curves if the discrete logarithm problem is hard?

Discrete Logarithm on elliptic curves is hard in the following sense: on an $n$-bit curve, solving DL has cost $2^{n/2}$. Thus, this is infeasible only as long as $n$ is large enough to make that cost ...
user avatar
17 votes
Accepted

Security of Schnorr signature versus DSA and DLP

Your post was a bit confusing to me, I think you're thinking of this from the wrong perspective. Is there a scheme with security arguably equivalent to DSA (or better, the DLP or related), but with ...
user avatar
15 votes
Accepted

Why is the discrete logarithm problem hard?

Now, I wonder if there are any better arguments. Ultimately, no, not really. We don't have any proof that computing discrete logs is hard. For that matter, we don't have any proof that any problem ...
user avatar
  • 132k
14 votes

Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?

The main point is that the entire apparatus of calculus applies to exponentiation over the real numbers. For instance, if $a$ and $b$ are close, then $g^a$ and $g^b$ are close as well. The exponential ...
user avatar
  • 4,402
13 votes

Why was the term "discrete" used in discrete logarithm?

While I agree completely with poncho's answer, this other viewpoint might be useful. Specifically, I think a better comparison isn't between $\mathbb{Z}_p^*$ and $\mathbb{R}^*$, but with $\mathbb{Z}_p^...
user avatar
  • 8,637
12 votes

In a group, is it hard to calculate the base $g$ given $g^a$ and $a$?

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod ...
user avatar
  • 11.1k
12 votes
Accepted

Logjam on Elliptic Curves?

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a ...
user avatar
  • 11.7k
12 votes
Accepted

How to solve this ECDLP?

We begin with the singular curve $$ y^2 = x^3 + 17230x + 22699\,. $$ This curve is singular, as can be immediately determined by its $0$ discriminant. Furthermore, it has a singular point $(23796, 0)$,...
user avatar
  • 11.7k
12 votes
Accepted

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most ...
user avatar
12 votes
Accepted

Small exponents and the RSA problem

Can you please give me some direction for such proof? You're looking for a proof that the RSA problem is hard? No such proof is known (even in the specific case of $e=3$). Furthermore, there is no ...
user avatar
  • 132k
11 votes
Accepted

Is it possible to generate backdoored DH parameters?

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[...
user avatar
11 votes
Accepted

What is the difference between discrete logarithm and natural logarithm?

I will assume you understand modulo operation and the exponentiation. First let's consider logarithm in $\mathbb{R}$. You know that if we have $e^x = y$ then $x = \ln y$. The Napierian logarithm ...
user avatar
  • 9,789
11 votes
Accepted

Is the additive discrete Logarithm problem always easy in Fields?

I will call the field elements "points" (as an analogy with elliptic curves). We can thus add points together and multiply points together. We can also multiply a point with an integer with a double-...
user avatar
10 votes

Discrete logarithm modulo a smooth number

Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for ...
user avatar
  • 132k
10 votes

Using Shor's algorithm to solve the discrete logarithm problem

Shor's method relies on a period finding routine on a quantum computer. A function $f: (x_1, \dots, x_n) \mapsto f(x_1, \dots, x_n)$ is periodic, of period $(\omega_1, \dots, \omega_n)$, if $f(x_1 + \...
user avatar
  • 1,699
10 votes

What does "export grade" cryptography mean? And how is this related to the Logjam attack?

"Export grade" cryptography is a result of The Crypto Wars. Laws were passed in the United States that resulted in the crippling of encryption software that was distributed outside of the United ...
user avatar
  • 19.2k
10 votes
Accepted

Extracting $ x $ given $ g^x, g^{x + y}, y $

Ok, I gave the answer in my comment; however so that you can accept an answer (and so close this question out), I'll repeat my answer here. Yes, it is still hard to find the discrete log, given $g, g^...
user avatar
  • 132k
10 votes
Accepted

Why do the discriminant and primality of the group order of an elliptic curve affect security?

$y^2 = x^3 + ax + b\bmod p$ is the Short Weierstrass equation. The theory behind it is here Using Bezout’s Theorem, it can be shown that every irreducible cubic has a flex (a point where the tangent ...
user avatar
  • 43.4k
9 votes
Accepted

Do I understand (below) why Q = dP is easy while finding d is hard

Computing $d$ given $P$ and $Q$, with $Q = dP$ is known as the "elliptic curve discrete logarithm problem" and is considered to be infeasible under some hypothesis. The security of Elliptic Curves ...
user avatar
  • 3,225
9 votes
Accepted

Is the one-more discrete log problem hard in the Generic Group Model?

More recent work by Bauer et al. [BFP] claims that the proof in a previous answer is flawed (and that Coretti et al. confirmed this). However, Bauer et al. prove hardness of OMDL in the GGM. They show ...
user avatar
  • 206
9 votes
Accepted

Small error in security proof on the paper On the Multi-User Security of Short Schnorr Signatures with Preprocessing

Yes, you've raised a flaw, you can contact the authors, they will probably update their proof in the paper. But as you've noticed, it's not a big deal because $2q$ is much smaller than $\frac{3q^2}{2}$...
user avatar
  • 2,181
8 votes
Accepted

Why do the subexponential algoriths for the DLP not work for the ECDLP?

"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{...
user avatar
8 votes

Hardness assumption: Extracting $g^y$ from $g^x, g^{x+y}$?

No, this is (nearly) never hard. To recover $g^y$ from $g^x,g^{x+y}$ all you need is a fast (ie polynomial-time) group operation (which is a given, because otherwise you'd have a hard time to come up ...
user avatar
  • 44.6k
8 votes

Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms?

For any discrete log problem where the order of the generator is even and known, then the lsbit is easy to recover. Notation I'll use: I'll be writing things in additive notation (the notation we ...
user avatar
  • 132k
8 votes

Why is calculating the discrete logarithm harder than calculating the public key?

There are actually much more efficient algorithms to calculate the public key, such as the double-and-add method which calculates the public key in at most $2 \times \log_2(n)$ steps. For example, if $...
user avatar
  • 855

Only top scored, non community-wiki answers of a minimum length are eligible