# Tag Info

17

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

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

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 = ... 10 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 ... 9 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} ...

8

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

8

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

8

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

8

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

7

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

7

"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 gx mod 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 of a larger ...

7

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

7

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

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

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

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

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

6

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

6

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

5

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

5

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

5

It means that if you have an oracle access to CDH, then you can solve DDH, but we do not know if there exists a reduction the other way round. Technically, suppose $\mathsf{CDH}$ is an oracle that finds $g^{xy}$, given $(g^x,g^y)$, then for a DDH instance, say $(a,b,c)$, you can feed $\mathsf{CDH}$ with $(a,b)$ and output $1$ if output of $\mathsf{CDH}$ ...

5

I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem. The first observation is that if you know the group order $n$ and a group generator ...

5

For ElGamal to be secure, the 'discrete log problem' (which is, given $g$ and $g^x$, find $x$) must be intractable. You give a generic way to attack the discrete log problem for a group with $n$ elements with something like $n$ steps (I say about because your approach isn't the simplest version of this type of attack; the simplest does take $n$ steps); ...

5

No, it is not possible to compute $\lambda$ easily. Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability. Hence, if we believe the factorization problem is hard, we must also believe that this ...

5

Göloğlu, Granger, McGuire, and Zumbrägel broke the DLP in the Galois finite field with $2^n$ elements for $n=6120$, and Antoine Joux did it for $n=6168$, with modest computing power. These recent announcements directly imply that cryptosystems (if any) based on the DLP in a field with $2^n$ elements are no longer secure, including for $n$ big enough that ...

5

Why does finding a collision mean that we have solved the problem? If we find a collision: $\alpha^{i1} \cdot \beta^{j1} = \alpha^{i2} \cdot \beta^{j2}$ then we know that: $\alpha^{i1-i2} = \beta^{j2-j1}$ And so, if we know the order of the group (which we generally do), then we can compute $({i1-i2})^{-1}$, and so, we have: $\alpha = ... 4 In addition to Jalaj's correct answer, I also want to dispute one of your statements: "From my understanding, since the Discrete Log(DL) Problem is considered hard, then so is CDH" Actually, that's not the case. Now, if you can solve the DL problem, the CDH problem is easy (and so the CDH problem is no harder than the DL problem). However, there's no ... 4 Ok, lets try again from scratch. First, some group theory definitions: A group is a set of elements and an operation$\times\$ which satisfies a specific set of properties (closure, associativity, an identity element, inverses) A subgroup is a subset of elements of a group which, along with the group operation from the main group, satisfies those same set ...

4

To complete @Samuel's answer, there are a few shortcuts that can be used when n is composite; however, they only contribute small constant factors, hence they do not change the asymptotic behavior: If n can be divided by r, then one can first solve the discrete logarithm in the subfield GF(2r). In a sieve-based algorithm, this can provide up to half the ...

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