# Tag Info

19

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others. For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line ...

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 ...

14

The problems: The Discrete Logarithm problem: Given $y$, find $x$ so that $g^x = y$. The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$. The Decisional Diffie-Hellman problem: Given $y_1, y_2, y_3$, decide if they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$ and $y_3 = ... 13$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$[$\hspace{.02 in}x$of them]$\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$[$\hspace{.03 in}y$of them]$\ldots \cdot g\cdot g\cdot g)= \;\;\; g\cdot g\cdot g\cdot \ldots$[$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$of them] ... 12 The generic discrete logarithm problem is this: Given a group$(G, ·)$with generator$g$and$y \in G$, find$x \in \mathbb N$such that$y = g^x$. The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e.$(\mathbb Z/p \mathbb Z)^*$: Given a ... 12 The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the$\mathbb{F}_{2^{6120}}$example: it clearly passes the field size criterion, but also the subgroup rule, as the group order$2^{6120} - 1$has one$1536$-bit prime factor. Not all binary fields are affected equally, however. Both Göloğlu et al and ... 11 I have asked a similar question to Arjen Lenstra a few years ago: I was investigating three 2048-bit primes of low Hamming weight:$p_1 = 2^{2048} - 2^{1056} + 2^{736} - 2^{320} + 2^{128} + 1p_2 = 2^{2048} - 2^{1376} + 2^{992} + 2^{896} + 2^{640} - 1p_3 = 2^{2048} - 2^{2016} + 2^{1984} - 2^{1856} - 2^{1824} + 2^{1792} - 2^{1760} + 2^{1696} + 2^{1664} ...

11

Discrete logarithms in $\mathbb{F}_{p}$ share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function ...

11

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 m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$. However, there are cases for which ...

10

Yes there are other hard problems you can base asymmetric cryptography on. Lattices. The NTRU systems is based on the shortest vector problem in ideal lattices. Lattice-based cryptography is of much interest these days for two reasons: (1) unlike factorization and discrete logarithms, there isn't an efficient algorithm for breaking these problems on a ...

10

Oh, and while you did not specifically ask about this, there is another point I believe that is important to highlight; DH and SRP are different protocols, and have different requirements on the generator they use. In particular, taking a generator that is designed to be used securely within DH can void the security properties of SRP. Here's what's going ...

10

Well, yes, that is generally good advice about DH. Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$. If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps. If we have as our ...

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 ...

9

There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as ...

9

Short answer: Yes. The discrete logarithm can be attacked in a multitude of ways: Baby-step giant-step (BSGS), Pollard's Rho, Pohlig-Hellman, and the several variants of Index Calculus, the best of which currently is the Number Field Sieve. Let $n$ be the order of the generator of our field $\mathbb{F}_p$; it is $n = p-1$. We are trying to find $x$ given ...

9

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$). Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it ...

9

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of. When someone uses the term "discrete log", they can mean two things: A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$ A discrete log in some other group; that is, given a group $G$, a ...

8

"Discrete logarithm" is a wide class. Originally, this means that we work in a finite field (e.g. integers modulo a big prime) and, given $g$, $p$ and $g^x \bmod p$, it is computationally difficult to recover $x$ (it becomes impossible with today's technology once $p$ is big enough). At some point, someone noticed that discrete logarithm was a special case ...

8

There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits. Let $n = pq$ be RSA modulus. Generate random number $a$ co-prime to $n$ and random number $x < n$ but very close to $n$. Compute $b = a^x \text{ mod } n$ but ...

8

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..." Actually, that's not true, and the information theoretically hiding" bullet point does not state that. What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value. ...

8

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 Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however ...

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 ...

7

For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$: Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$. If $x$ is a non-zero ...

7

Here's the deal. The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large). Suppose we are given $y=g^m$, and we want to find $m$. Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say. Then it turns out it is easy to recover $m$, ...

7

For all $m$, if $m$ is a positive integer then $g$ is a primitive root mod $m$ $\;$ if and only if $0\leq g< m$ $\:$ and $\:$ $\operatorname{gcd}(\hspace{.015 in}g,\hspace{-0.01 in}m) = 1$ $\:$ and $\;\;$ for all prime factors $q$ of $\phi$$(m)$, $\: g^{(\phi(m))/q} \not\equiv 1 \;\;\;$.

7

It happens that a line usually (not always) cuts three points in a elliptic curve by the Bezout theorem. This is the case for the points and the curve you are asking for. So the sum of two points are defined like the inverse of the third point intercepted by the line that cut $P$ and $Q$ (let's name it $R$). So we need to find $-R$ because $P+Q=-R$ by ...

6

256-bit discrete logarithms on a prime field are definitely not of the order of magnitude used in cryptographic applications. Secure sizes for this problem are in the thousands of bits, very much like integer factorization. To break that example discrete logarithm, you probably want to use Index Calculus, more specifically the Linear Sieve. Resorting to the ...

6

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus ...

6

Antoine Joux very kindly sent me the following on the topic: People worry that [logarithms over fields with composite exponent] might be easier, this is why they use prime exponent. For some factorization of the exponent, viewing the finite field as a tower of extensions $(p^{n_1})^{n_2}$ indeed makes things easier. See "The function field sieve ...

6

I'm not sure how to answer the question about "trust" in the assumption. I suppose that is a matter of personal belief more than science. We don't know the truthfulness about any cryptographic assumptions, although obviously some have received more scrutiny than others. I'd say that the KEA assumptions have received relatively little attention, and so should ...

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