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


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

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


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

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


2

It is not entirely clear what your exact security requirements are and for which purpose you require this construction. I assume that the tags can not be manipulated by an adversary, e.g., are signed, and that users do not try to change their choice of $x_i$ after having a tag. Anyways, I give it a shot (although I may be wrong due to some information I do ...


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

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

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


2

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.


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})^*$.


1

Well, your problem is that you choose a specific bad private key ("-1"), which only generates a group with two elements. However, this is a very specific weak case, and the chance to select the according private key is negligible. But in general, there are a couple of problems with choosing a generator for the whole group $\mathbb{Z}_p^*$, because it is ...



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