# Tag Info

10

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

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

5

Let $\#G$ denote the number of elements in the group. In your particular case, $\#G = \varphi{}(n)$ (and even $\#G = n-1$ if $n$ is prime). Let $\xleftarrow{\$}$denote a uniformly random sampling from a finite set of elements. Furthermore,$\mathbb{Z}_m$denotes the set of non-negative integers smaller than$m$and$\stackrel{?}{=}$denotes a equality test ... 4 Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of. When someone uses the term "discrete log", they can mean two things: A discrete log in the group$Z^*_p$; that is, given$p$,$g$and$g^x \bmod p$, recover$x$A discrete log in some other group; that is, given a group$G$, a ... 4 There are two ways to solve a discrete log problem over$Z^*/p$, that is, given$g$and$h$, find$x$with$h \equiv g^x \bmod p$: If the point$g$generates a subgroup of size$q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover$x$in$O( \sqrt{q})$time. Use the Number Field Sieve algorithm to attack the discrete log problem in ... 4 While$O(n)$is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in$O(n)$but instead in$O(\log(n)) = O(|n|)$(e.g. expoentiation with square and multiply has$|n|$multiplications and at most$|n|$squaring operations). Therefore, the ... 4 Not at all. It's very trivial: $$(g^{ab})^{b^{-1}}=g^a$$ 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 ... 3 Are you limited to working with$g$and$h$being generators of the entire group$\mathbb{Z}_p^*$? In that case you have a problem with knowledge extraction in the proof of knowledge (basically, since you are not working in a field "in the exponent", but in$\mathbb{Z}_{p-1}$, the required multiplicative inverses might not exist). However, when you work ... 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 The standard solution is to generate$g$and$p$once during application development, then hardcode$g$and$p$in your code. There are standard choices for$p$and$g$, e.g., documented by NIST in their FIPS series. I suggest using one of those. There is no need to re-generate$g$or$p$each time. You can use the same$g$and$p$for everyone. See ... 2 The polynomial vs. exponential complexity notations for algorithms or problems are always expressed in the input size, i.e. the size of a convenient way to express the problem. For the discrete algorithm problem, you normally would not write the whole group (or even its multiplication table of size$n^2$) as the input, but only some key parameters which ... 2 First of all, DLP is only defined for cyclic groups. The$\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$you are talking about is not cyclic, since (say)$s$divides$t$. But you can define a "generalized" DLP by considering the cyclic subgroup generated by an element$g$. Next, DLP in any subgroup of$\mathbb{Z}_t^+$is trivial. Figuring out why is a nice exercise. ... 2 As mentioned by Thekwasti, what you want here is compute a discrete logarithm, but while it is true that in general computing discrete logarithms is "hard" (which is why they are used in cryptography), in your case the group is small enough to make even a brute force search completely feasible. So the goal of the exercise is probably to make you implement at ... 2 The original question was: Alice knows:$a,b$and$x$such that$a^{(x\cdot x)} = b$Bob knows:$a,b$and DrLecter referenced this paper (fixed the link), which covers the question. Now, the question was changed to Alice knows:$b$and$x$such that$x^x=b$; Bob knows:$b$. The given structure was: ... multiplicative group$G$... 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 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 ... 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 ... 1 Since Blum-Micali is cryptographically secure, you know that there won't be a short cycle (not one short enough to detect in polynomial time), because a short cycle would violate cryptographic security. Therefore, you don't need to worry about this. It's not worth your time worrying about it: it's very unlikely you'll run into a short cycle. That said, ... 1 Please let me know if I have something wrong here. Let g \in \mathbb{Z}_s^{+} be fixed in advance. Choose any h in <g> = \{g,2g,3g,\ldots \}, the (finite) cyclic subgroup of \mathbb{Z}_s^{+} generated by g. Then$$h = xg$$for some$x \in \{0,\ldots,s-1\}$. In fact,$x \in \{0,\ldots,\text{order}(g)-1\} \subseteq \{0,\ldots,s-1\}$. The ... 1 First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of$\mathbb{Z_q}$in which CDH is believed to be hard but DDH is apparently tractable. Let$p = 2p_1 + 1$where both ... 1 I hope you understand your question. Your question is that given generator$g$of a prime order$q$group and some element$g^y$of that group and another element$x_1 \in Z_q$you want to check if there is such an$x_2$or find$x_2\in Z_q$such that$y\equiv x_1+x_2 \pmod q\$? I assume that in this setting the discrete logarithm problem is hard, right? ...

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