Tag Info

New answers tagged

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


4

Collision and preimage resistance does not imply this; suppose we select a collision and preimage resistant function $H$ with a known value $I$ with $H(I) = 1$ (the group identity); this additional assertion does not contradict the assumptions of collision or preimage resistance. Then, given $a$, we can easily output the tuple $(I, a)$; as we have $H(I) ...


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


0

if you know a, you also know $\frac{1}{a}$ then $g=(g^a)^{\frac{1}{a}}$ UPDATE: answering the question for solving $X^r - a = 0$, when r | (p-1). If my analysis is correct: if r | (p-1): the square root algorithm can easily be adapted regarding the form of prime p. If p=2.r.q + 2.r -1: this deterministic case: Let Let $y_0=a^{\frac{p+1}{2 \times r}} ...


0

There are libraries allowing to do that: PBC: C library JPBC : Java library Hope it helps.


4

One way to do this, if you're working with a multiplicative group $Z^*_p$, is to pick a prime $p$ so that $p-1$ has a large prime factor $q$; once you have this, then to generate a generator of order $q$, you pick a random value $h$, compute $g = h^{(p-1)/q}$, and if that is not 1, then $g$ is a generator of your group. Obvious questions: How do you find ...


0

The simplest case for you is to consider prime number p of the form $p=2.p_1+1$. Where p1 is also prime. The structure of the multiplicative group of $\mathbb{Z}_n = \{1,2, ... ,p-1 \}$ splits into 3 subgroups of order 2, $p_1$, p-1. Only quadratic non residue residue have maximal order. elements of order 2 are 1 and p-1. The quadratic residue are those ...



Top 50 recent answers are included