Tag Info

25

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 $\mathbb{R}^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it. The discrete logarithmic ...

12

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^*$ and $S^1$. We can view $S^1 \cong \{z\in\mathbb{C} \mid |z| = 1\}$. It's not hard to show that any $z\in S^1$ is able to be written as $z = \exp(2\pi i t)$ ...

9

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 situations. The soundness of the protocol is not based on the Diffie-Hellman problem. This is probably the most important point to address. What does it mean for ...

6

The basic baby-step-giant-step algorithm can be tweaked to make use of this information. The following algorithm takes $\Theta(\!\sqrt{k-j})$ group operations. Let $h:=c\cdot g^{-j-1}$, which equals $g^{i-j-1}$. Pick some integer $m\geq\sqrt{k-j-1}$. Initialize an empty lookup table $T$. For all $0\leq a<m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$. For ...

6

Actually, a well known result is that, for any cryptosystem that relies on the hardness of the DLog problem (including ECDlog), there is no such reduction in strength if you have $k$ keys. That is, the problem of "here are $k$ keys, break any one" is essentially as hard as the problem "here is one key, break it". The proof is straight-forward; first off, ...

5

The discrete logarithm $\log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$. If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$. Take a generator $g$ of a ...

5

No, Shamir's trick doesn't break ECDSA. Verifying an ECDSA signature involves evaluating a sum of scalar multiplications $[h s^{-1}]G + [r s^{-1}]P$. You can compute the scalar multiplications $[h s^{-1}]G$ and $[r s^{-1}]P$ separately and then add the results, but Shamir's trick does it more efficiently as a combined computation. This trick for ...

5

Well, if you have a pseudocurve [1] based on the formula: $$y^2 = x^3 + ax + b \pmod{ pq }$$ what you have is really two different curves stapled together; that is, the curves based on: $$y^2 = x^3 + ax + b \pmod{ p }$$ $$y^2 = x^3 + ax + b \pmod{ q }$$ You can look at a point in the $pq$ curve as really being a point in the $p$ curve and a point in the ...

5

Short answer: the definition you're using (and, in particular, the notation in it) is specific to multiplicative groups modulo $p$. It makes no sense for elliptic curves, or for most other kinds of groups over which the discrete logarithm problem can be defined. In particular, for elliptic curves, there is no prime modulus $p$. (Well, OK, for the elliptic ...

4

If you wanted to compute secp256k1 discrete logs, you would use Pollard's rho, except of course the cost is far beyond your budget so it won't do you any good anyway. The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields. Such elliptic curves are called pairing-friendly, and ...

4

The question deals with the finite field $\mathrm{GF}(p^n)$. It wants to study/attack a variant of DSA in (the multiplicative subgroup of) that field, rather than $\mathrm{GF}(p)$. Whatever that DSA variant is, it can be attacked by solving the Discrete Logarithm Problem in $\mathrm{GF}(p^n)$. The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-... 4 Generic algorithms for solving the DLP, like Shanks baby step-giant step or pollard rho are of complexity of order$\mathcal{O}(|G|^{0.5})$. That is, for$|G|=2^{256}$you get a complexity of$\mathcal{O}(2^{128})$. However, for the index calculus method, that is operated on the modulus, for complexity of$\mathcal{O}(2^{128})$you would need a modulus of ... 4 Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If$G \simeq H$via$\phi : G \rightarrow H$and$\phi$is computable, then indeed, DLOG is no harder in$G$than in$H$because you can transform the instance. In the case you mentioned, we have$G = \mathbb Z/(p-1) \mathbb Z$and$H = (\mathbb Z/p\mathbb Z)^\...

4

Discrete Log for arbitrary Groups: Discrete Log can be defined in arbitrary groups and some groups can have an easy solution (powers of 10) and some can have a hard solution. Let $G$ be any group and $\odot$ be the group operation. For any $k \in \mathbb{Z}_{>0}$, let $b \in G$ then we define $[k]b = \overbrace{b\odot\cdots\odot b}^{{k\hbox{ - }times}} ... 3 Of course any integer can be a discrete logarithm: in a group$G$with generator$g$, any integer$x$is a discrete logarithm of the group element$g^x$. Another convenient way to consider the set of discrete logarithms is as the ring$\mathbf Z/n\mathbf Z$, where$n$is the order of$G$, which makes sense because$g^x = g^{x \bmod n}$for all$x$. This is ... 3$\mathbb{Z}_p=\mathbb{Z}/p\mathbb{Z}$denotes a finite field that is just integers mod the prime$p$, i.e.,$\{0,1,\ldots,p-1\}$. This field (by definition of a field) has two operations: addition and multiplication, where the multiplication group (denoted by$\mathbb{Z}_p^*$) is defined only on the non-zero elements$\{1,2,\ldots,p-1\}$. Then, since$g$is ... 3 In the algorithm,$p$is the order of group,$x$is solution. We rewrite$x = i * m + k $, but why do we make$m =\lfloor\sqrt{p}\rfloor$, rather than something else like$\lfloor {p/2}\rfloor$? The time taken by Big Step-Little Step is$O( m + p/m )$(the$O(m)$term comes from the time taken iterating through the various$k$values, the$O(p/m)$term ... 3 The space$\mathbb Z/n\mathbb Z$is usually taken to consist of equivalence classes modulo$n$called residue classes—equivalence classes of integers under the equivalence relation$a \sim b$if and only if$n$divides$a - b$. For example,$\mathbb Z/3\mathbb Zconsists of the three equivalence classes \begin{align} 3\mathbb Z &= \{\dots, -3, 0, 3, ... 3 It is true that you have in the worst case\operatorname{ord}(Z^*_p)$values to test. However, the complexity of a problem is actually measured according to the size of the input of the problem in computer representation which is binary. Here the inputs to our problem are h and p. These two are integers both of size$log_2(p)$at most in computer binary ... 3 The reason the attack does not work is because you are hitting a special case—the canonical lift. This is the case where the lifted curve over$\mathbb{Q}_p$is isomorphic to the curve over$\mathbb{F}_p$, in which case no additional information can be extracted from it. The journal version of Smart's paper mentions this case. The solution is simple: if we ... 3 How is the 3072-bit modulus derived? Find the smallest$c$such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c)$$ and$q = (p - 1)/2$are prime, and$p \equiv 7 \pmod 8$. In this case,$n = 3072$and so$c = 1690314$. Use$g = 2$as the generator. (Here$\pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/...

3

As pointed out in the comments, it's not quite clear what the problem is, but here's an easy algorithm for the (arguably) most natural interpretation. Given any prime $p$ and integer $a$, the following procedure finds an integer $x\in\mathbb Z_{\geq0}$ such that $$x^x\equiv a\pmod p \,\text.$$ Pick some positive integer $e$ coprime to $p-1$. (For example,...

2

This is not true in general. Bach showed that given the factorization of $n$, computing the discrete log modulo $n$ requires computing it modulo the factors (also cf. this previous question for more details.). So, if both the factors are large then DLP is still hard.

2

Just to add to the other answers, (as mentioned in some of the comments) it is exactly the discreteness of the discrete log problem is that makes it (for some parameter choices) hard. Computing $y = \log_{a}(x)$ is the same as solving the equation $a^y = x$ for $y$. In the non-discrete case, $y \mapsto a^y$ is a monotonically increasing (if $a > 1$) ...

2

There are a couple reasons that the discrete log is weak across powers of two, the most basic reason is because it is only considered strong when the modulus is some large prime, p. This is a good link about how to find the mod inverse, and in it you will find their function for computing it. https://www.geeksforgeeks.org/multiplicative-inverse-under-...

2

No, there is no known way to recover $d$ using an Oracle that, given $m$, returns $m^d \bmod n$; there is also no proof that such a method does not exist. Such a method would imply that the RSA problem (which is, given $m^e \bmod n$, recover $m$) is equivalent to the factorization problem (which knowledge of $d, e$ would allow you to solve); it is unknown ...

2

It does work with Silver-Pohlig-Hellman algorithm As theREALyumdub pointed out in comments that Silver-Pohlig-Hellman might be an option I did some test and it did work. Thanks for that hint. In case $t=1$ we get the results $a,b,c$ right out of the algorithm. For other $t$ the results $a,b,c$ aren't correct. Some extra work need to be done there. It does ...

2

What you are asking is in some sense a tautology. In any group $G$, Abelian or not, the subgroup generated by an element $g \in G$ is Abelian. (Recall: the subgroup generated by $g$ is: $\langle g\rangle := \{g^0, g^1, g^2....\}$ ). Hence, you can probably take your favourite DLP-based encryption scheme and implement it in $G$, without dealing with the ...

2

$k = n \cdot g^a \mod P$ How can we solve this? It is trivial to find $(n, a)$ pairs that satisfy this relation; select an arbitrary $a$ and compute $n = k g^{-a} \bmod P$; that's a solution. Now, that'll give you $ord(g)$ distinct solutions; if you have a specific solution in mind, you have no way to telling which one it is. However, depending on ...

2

$G_n = G_m$ iff $n^S \equiv m^S \pmod P$ Proof: If $n^S \not\equiv m^S \pmod P$, then $\forall e \in G_n : e^S = n^S$ (as $e^S = n^S \cdot (g^a)^s = n^S$); and similarly $\forall f \in G_m : f^S = m^S$. Hence $\forall e \in G_n, f \in G_m: e \ne f$, and hence $G_n \ne G_m$ (and actually the two sets are disjoint). Other direction (needed because we're ...

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