Hot answers tagged

19

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 indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ...


10

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 distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a ...


8

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 Cryptography is based exactly on the ability to compute the point multiplication and the intractability of the inverse operation: given two points find out the ...


6

I just want to highlight: The new advancement need to be realized and validated. ECC and DH are quite similar although ECC discrete logarithm problem is harder. In other words, whatever effects the security of DH might not affect ECC with the same magnitude.


6

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ...


6

"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{F}_q$ for some $q = p^k$, $p$ being a prime. The intuitive reason why the DLP is harder to solve over (well chosen) elliptic curves is that they are our best ...


6

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$. Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $x$. In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so: Interpret $x$ as a $k$ bit number, i.e. $x = ...


5

It's not possible because if $B$ knows $b$ and $g^{ab}$, then she can compute $\left(g^{ab}\right)^{b^{-1} \bmod N} = g^a$ (where $N$ is the order of $g$, which is normally prime so that $b^{-1} \bmod N$ exists). EDIT: As noted by poncho in the comments, this assumes we are in a typical discrete logarithm setting, where the order of the group is prime to ...


5

And we know that knowing of $Q$ and $P$ is sufficient to be able to compute $d$ efficiently. I think you meant "knowing $P$ and $d$ we can compute $Q$ efficiently. That's the DLP as stated in your previous answer. I think it's more intuitive to work in $\mathbb{Z}_p^*$ and in this group you might reframe the DLP question as this: "given some generator ...


5

I will assume for simplicity that you're talking about the full multiplicative group of $F_p$ instead of a proper subgroup, thus there are no problems with $g^a+1$ (except when $g^a=p-1$ which can be trivially ruled out by comparing to $p$). The quantity $\log_g(g^a+1)$ is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for ...


5

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 return values in $\mathbb{R}$. You can have the same thing with another base. For example : $2^3 = 8$ and $\log_2 8 = 3$. The simplified idea of the discrete ...


4

In this case, the base does not matter as the $\log$ terms are wrapped in an $O$ expression. The $O$ expression lets you throw away constant factors and to convert something base $X$ to base $Y$ is simply $\log_X Z = \frac{\log_Y Z}{\log_Y X}$, well, $\log_Y X$ is a constant, so it can be thrown out in the $O$ expression. The reason the second reference ...


4

The difference is purely conceptual. That is, when Diffie-Hellman published their paper, they equated between public-key encryption and trapdoor functions. Thus, they did not think that they had constructed a public-key encryption scheme, and this invention came only a year later with RSA. In fact, Diffie and Hellman even explicitly talk about publishing one ...


4

The complexity of Pollard-Rho is indeed $O(\sqrt{\text{ord}(g)})$, but even though $n$ refers to the modulus, their statement might be correct depending of the context. If the modulus considered in your situation is a "classical" modulus in crypto (e.g. $n = (2q+1)^k$ for a prime $q$ and a small $k$, etc), as the modulus will be in general chosen so that ...


3

It can affect several classes of Elliptic curves. In particular, if this curves have pairings or any other way to translate the problem to a finite field (or extension finite field). The tricky part about ECC is that if you do not pick your Elliptic curve properly, you might end up with a weak implementation. Or, with an implementation in which the problem ...


3

In the introduction of the Logjam paper, it is stated that After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logs in that group in about a minute. So it seems that what it actually does is attack the discrete logarithm problem, so any discrete-logarithm-based system which uses a common prime should ...


3

Their statistical distance is less than $\: (q\hspace{-0.04 in}-$$\phi$$(q))\hspace{.02 in}/q\:$, $\:$ since $\:$ if $a$ is relatively prime to $q$ then $(\hspace{.02 in}g^a)^b$ and $g^c$ are $\:$ each uniformly distributed and independent of $a$ $\;\;\;\;$ and $\:$ even if $a$ isn't relatively prime to $q$, $(\hspace{.02 in}g^a)^b$ and $g^c$ each $\:$ ...


3

The answer depends on the factorization of $p-1$; for any factor $q$ of $p-1$, the attacker can derive $x \bmod q$ in $\sqrt{q}$ steps (by first computing $(g^x)^q = g^{xq}$, and then searching for the value $y$ with $(g^{xq})^y = 1$ using, say, Pollard Rho. Hence, if the attacker has a computation budget of $n$, and $p-1 = q \cdot r$, where $q$ is $n^2$ ...


3

You're right in that there's little chance you can break the logarithm in a well-chosen 512 bit group (using a home computer, in reasonable time — as pointed out by SEJPM, it is possible investing some time and a good amount of money). However, in your case, the parameters are bad: The order of $(\mathbb Z/p\mathbb Z)^\ast$, that is $p-1$, is a smooth ...


3

First of all, let us simplify the equation by replacing things that the attacker can compute with known constants. We come up with: $$a \cdot b^x = y$$ where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$. If it is sufficient for an attacker to find a ...


2

The closest that I can think of is a "symmetric bilinear group" (a.k.a. Type-I pairing group) that was popular when bilinear groups were first introduced. This is actually a pair of groups $(G, G_T)$ together with an efficient non-degenerate bilinear map $\otimes: G \times G \to G_T$. Obviously DDH is easy in $G$, since one can on input $(g, U, V, W) \in ...


2

It is equally difficult (within a factor of 2) for any irreducible polynomial. Suppose $g$ was your 'cheap' irreducible polynomial, that is, one for which, given $g^n$, you can rederive $n$ quickly. Then, given an arbitrary pair $h, h^x$, you can quickly find $a, b$, such that $h = g^a$ and $h^x = g^b$, and then immediately deduce that $x = a^{-1}b$


2

Diffie-Hellman operates in a cyclic group by definition: the elements $g, g^a, g^b, g^{ab}$ are in the cyclic group generated by $g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway. In your example, you operate in the cyclic group $c\mathbf{Z}$, and as you were told in the comments, ...


2

I've read in several places that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that? Actually, both references talk about the behavior of the TLS client when negotiating a DHE-based ciphersuite. The server proposes $p$ and $g$ as a part of the exchange, and hence ...


2

For computing $Q=dP$ we have a "NAF" methods that are more faster than logarithmic methods. Fore more detail you can see "guide to elliptic curve". Also for computing $d$ from $Q=dP$, the method that commonly use is pollard-rho method. This method is based on birthday paradox attack and be-able to solve discrete logarithm in $O(\sqrt p)$ which $p$ is a ...


2

Yes, this logic works. You have shown that given the discrete log $x$ lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log $x$ and then you are done (then you have shown the equivalence).


2

For arbitrary positive integer $n$ we have: $$\gcd(n,n+1)=1$$ So $q-1$ and $q$ haven't any nontrivial common factor.


2

It should be $\;\; O\Big(\hspace{-0.07 in}\sqrt{\text{order of g}}\hspace{-0.02 in}\Big) \:$ group exponentiations $\;\;$ . When $q$ is the order of $g$, that will be $\;\; O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{q}\hspace{-0.02 in}\right) \:$ group exponentiations $\;\;$ . When $n$ is the order of $g$, that will be $\;\; O\hspace{-0.04 ...


2

I think the problem is that you are trying to recompute the result in $(p-1)(q-1)$ instead of $n$ and that is why you don't find the exact $x$. Your question is: I can compute the discrete logarithm of $y=g^x \mod n$ by computing the discrete logarithm of $y$ modulo $p$ and $q$. But then how to recompute it? As I understand, you want to find the ...


2

I am really not sure about what you are trying to do. If you simply want to prove that $Ans = e(g,h)^k \times e(g,h)^r$ is hidden given only $(g,h,e(g,h)^k)$, then this is trivial and does not require any hypothesis at all (in particular, no discrete logarithm problem is involved). Indeed, this is perfectly equivalent to the problem of finding $e(g,h)^r$ ...



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