Tag Info

Hot answers tagged

9

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


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


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

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other). If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you ...


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

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


5

The bad news is that projective coordinates do not work with Pollard's Rho like you want it to. Rho needs an unambiguous point representation to find meaningful collisions, and in projective coordinates each point can have up to $p-1$ valid distinct representations. The good news is that, sticking to affine coordinates, you can avoid most of the cost of the ...


4

Not at all. It's very trivial: $$(g^{ab})^{b^{-1}}=g^a$$


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

The question as currently worded, and considering comments by its author, would boil down to: is it a hard problem finding $g^a\bmod p$, given large prime $p$ large integer $g$ less than $p$ that is a generator of $\mathbb Z_p$ [see note 1] prime $r$ less than $p$ knowledge that unknown $a$ is a positive integer less than $r$ positive integer $b$ less than ...


3

Solving a 256-bit discrete log is absolutely doable, and quite quickly, these days; there are public tools that can do it, though they may require some expertise to use. On that note, even a 1024-bit modulus is not particularly conservative: it is generally agreed that well-funded organizations today could break logs of that size as well, but at a very ...


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

Being able to solve the discrete logarithm in SRP-6 allows an eavesdropping attacker to dictionary attack the password. It will not directly reveal a strong password or its hash. It requires the attacker to observe a successful authentication, $B$ alone does not suffice. The attacker eavesdrops $s$, $A = g^a$, $B$ and $M_1$. The attacker solves $a$ from ...


2

"Would it be possible for an attacker to launch an offline dictionary/brute-force attack on the B public key: ..." That is possible if and only if the attacker can distinguish b's distribution from the uniform distribution on {0,1,2,3,...,N-3,N-2}. $\:$ If so, an attacker could compute verifiers v for candidate passwords, subtract kv from B mod N, and ...


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' = ag$$ $$a' = 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

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


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


1

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


1

Because $x$ is defined modulo $28$ ($2^{28} = 2^0$ in $(\mathbf{Z}/29\mathbf{Z})^*$), you can view $x$ as an element of $\mathbf{Z}/28\mathbf{Z}$, while $2$ and $3$ are elements of $(\mathbf{Z}/29\mathbf{Z})^*$.



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