# Tag Info

10

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

8

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

7

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

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 = ... 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 ... 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 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 There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is ... 3 Sure. Use the strong RSA assumption. The accumulator of$x_1,\dots,x_k$is$A = g^{x_1 x_2 \cdots x_k} \bmod n$, where$n$is a RSA modulus and$g$is a fixed base. To prove that the accumulator$A$contains$x$, exhibit a value$h$such that$h^x=A \pmod n$. This is secure under the strong RSA assumption, and has a discrete log "feel" to it. 3 Yes, you are correct. There are various methods for scalar multiplication on elliptic curves. Some of them are optimised for fixed base-point scalar multiplication, i.e., where you a-priori know that you will mostly/exclusively perform scalar multiplications with respect to a fixed base point on the curve. Thus, one can make (extensive) pre-computations ... 3 Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime). Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability. Then, given a value$g$and$h$, we can find$x$with$g^x = h$with nontrivial probability by: Create ... 3 If you generate group elements at random as you suggest then you can indeed invoke the "Birthday Paradox" to find logarithms in time$O(\sqrt p)$. Unfortunately your storage requirements are the same and for cryptographically interesting group orders your method is therefore far from optimal. The fastest way for groups with (apparently) no exploitable ... 2 A straightforward way to prove this when you can prove AND as well as OR statements about discrete logarithms is to take all the$K=\binom{M}{N}$subsets$A_i=\{A_{i_1},\ldots,A_{i_N}\}$with$N$elements of points from the set of your$M$points and prove the statement $$PK\{(\alpha_1,\ldots,\alpha_N): \bigvee_{j\in K} \big( \bigwedge_{A_{j_i}\in A_j} ... 2 There already exist standard primes that might be used for Finite Field Discrete Logarithm based schemes. One set is found in RFC 3526. Another set is currently in the process of being standardized as part of TLS and can be found in the current Negotiated FF DHE draft (this link will expire no later than June 15 2015). The smallest prime in the former set ... 2 There are some errors in the basic assumptions or in their descriptions. So, we start with the group \mathbb{Z}_p^*, with p prime. This is a cyclic group with order p-1. if a number is said to be a subgroup of a quadratic residue of Z∗p, can I affirm that it is a generator of a cyclic group ? First, a number (or more formally an element of the ... 2 To search for the values a^x in the range 0 < x < k, what you need to do is set m = \sqrt{k} (rounded up), and then do the Baby Step/Giant Step algorithm for 0 \le i, j < m. That is, you generate the values a^0, a^1, ..., a^{m-1} and the values B\cdot a^{-0}, B\cdot a^{-m}, B\cdot a^{-2m}, ..., B\cdot a^{-(m-1)m}; if x<k, then ... 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 Yes, it is equally as difficult; if we assign:$$g' = aga' = a^{-1}b' = b$$Then the restatement of your problem is: given$g' = ag$,$a'g' = g$and$b'g' = abg$, compute$a'b'g' = bg$, which is exactly the ECDH problem. Now, this assumes that$a$has an inverse; this is not a problem if the curve order is a prime, and is easy to work around if ... 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$

1

Actually, the algorithm is distinguishable. Let us assume that the attacker has two input, output pairs $(x, fx), (y, fy)$. Then, he can test whether $fy^x = fx^y$. If $fx = g^{sk\cdot x}$ and $fy = g^{sk\cdot y}$, this test will succeed, as $fy^x = g^{sk\cdot y \cdot x} = g^{sk\cdot x \cdot y} = fx^y$. Furthermore, given $x$ and $g^{sk \cdot x}$, the ...

1

Since attacker does not know $m$, he can't directly apply discrete logarithm methods. On the other hand, small message space allows to run discrete log algorithm on each possible $m$. There are subexponential algorithms for dlog, but I am not sure if they are directly applicable here. But the general BSGS algorithm will find $e$ in $sqrt(e)$ operations, so ...

1

As a hint, suppose we pick a random $h$, and compute $g = h^3 \bmod N$. We then find the minimal value $x$ where $g^x \equiv h \pmod{N}$ (and, yes, such an $x$ will exist, assuming $p, q > 7$). What can we deduce from such a value of $x$?

1

First there are the "generic" discrete logarithm algorithms like Shanks's "baby step, giant step" and Pollard's $\rho$, which run in $O(\sqrt{L})$ and are thus of exponential complexity (in the size of $L$). Those algorithms work in virtually any group. In the special case of the multiplicative groups of finite fields, we have subexponential algorithms ...

1

First, I think you have a typo in your question since in the original article $s = (M - x y)(r^{-1}) \mod p-1$, and not $s = (M - x^y)(r^{-1}) \mod p-1$. Knowing that, then we can construct $s_2$ from $s, r, M$ and $M_2$: $s_2 = s + (M_2 - M)r^{-1} = (M - x^y)r^{-1} + (M_2 - M)r^{-1} = (M - x^y + M_2 - M)r^{-1} = (M_2 - x y)r^{-1}$ A valid signature for ...

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