# Tag Info

18

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others. For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line ...

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 ... 5 Why does finding a collision mean that we have solved the problem? If we find a collision:$\alpha^{i1} \cdot \beta^{j1} = \alpha^{i2} \cdot \beta^{j2}$then we know that:$\alpha^{i1-i2} = \beta^{j2-j1}$And so, if we know the order of the group (which we generally do), then we can compute$({i1-i2})^{-1}$, and so, we have:$\alpha = ...

5

Elliptic curves have a number of nice features that make them good for cryptography. One could write a whole book on the topic (as some have), so I'll highlight a few points. The points on an elliptic curve over a finite field forms a group. The same is not true for the ideas you mentioned. Discrete log on many of these EC groups is hard. In fact, there ...

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

You are not wrong: given any variety $V$, we can form the Jacobian $J(V)$ as an abelian variety, in particular an abelian group over which we could use the Diffie-Hellman problem. However, there are several details that get in the way of doing this. First, it is necessary to compute the order of the Jacobian. We only know how to do this for elliptic curves. ...

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

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

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

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 new to cryptography is one thing, but you are supposed to do some research on your own before asking questions here (see How to Ask), and D.W. gave you the right directions already. But since you wanted names and links: The first stop should be discrete logarithm on Wikipedia, and it lists several algorithms on this topic. As a beginner, start with ...

2

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$. In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but ...

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

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

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

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

"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

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

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

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