6
votes
Accepted
Elliptic curve and "vanity" public keys
Maxwell's vanity public key is a result of how the generator of the secp256k1 was chosen; as explained by Maxwell himself.
For some reason, the generator $G$ is the double of the point:
...
- 6,404
4
votes
Accepted
Issue implementing Pollard's Rho for discrete logarithms
First of all, Pollard Rho finds an essentially random solution $(B - b) \gamma \equiv (a - A) \pmod{N}$. This randomness implies that if $N$ has a prime factor $p$, then $B - b$ has a probability $1/...
- 145k
4
votes
Is the complexity of Pollard rho for discrete logartihm really the modulus?
The complexity of Pollard-Rho is indeed $O(\sqrt{\text{ord}(g)})$, but even though $n$ refers to the modulus, their statement might be correct depending of the context. If the modulus considered in ...
- 19.1k
4
votes
Method to break a baby Elliptic Curve analog to secp256k1
Solving discrete logarithms in $144$-bit groups is hard
Even scaling down to 144-bits is likely beyond current capability. To my knowledge the largest elliptic curve problem tackled with "black ...
- 21.9k
3
votes
Accepted
How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?
In the question you said that $a^x\equiv b\ (mod\ p)$ and $P,Q\in E(\mathbb{F}_p)$. In general case, the number of elliptic curve points $\#E(\mathbb{F}_p)$ is not equal to $p$. So these two groups ...
- 2,323
3
votes
Elliptic curve and "vanity" public keys
The birthday problem can't help to find public/private key pairs with "vanity" address (hash of public key in text form). Here, "vanity" is some arbitrary characteristic/metric, like plausibly ...
- 138k
3
votes
Accepted
On the bit security of elliptic curves
It is explained that the field $\mathbf{F}_{2^{256}}$ has a bit security of $128$
Actually, the reference was to an elliptic curve based on the field $\mathbf{F}_q$ (where $q \approx 2^{256}$)
but ...
- 145k
2
votes
Issue implementing Pollard's Rho for discrete logarithms
The problem is that Pollard Rho is not guaranteed to work, especially in very small examples where the order of the multiplicative group is 6.
With larger groups, the modular inverse will almost ...
2
votes
Williams' $p+1$ in tandem with Pollard's $p-1$?
These attacks are not relevant today because ECM, QS, and NFS are more cost-effective at modulus sizes providing serious security, which these days must be well above 1024 bits, preferably at least ...
- 47.9k
2
votes
DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus
Yes, this is totally feasible. Unless $p$ is purposely chosen as a safe prime, there's a good chance that's easy.
Computing $a$ given $B$, $p$, and $C=B^a\bmod p$ is a Discrete Logarithm Problem in ...
- 138k
2
votes
Accepted
Iterations of pollards kangaroo attack on elliptic curves
My First Attempts:
So I did some testings on the curve $E: y^2 = x^3 + x^2 + x$ with $F_{131}$ and the points $P = (42,69)$ and $Q = 42 \cdot P$. My results for different $N$:
My result for a ...
- 2,120
1
vote
Why is pollard rho's expected runtime O(sqrt(n)) not O(sqrt(n) * log(n))?
Ok, this needs a little deeper answer.
What Wikipedia gives as $\mathcal{O}(\sqrt(N))$ is the expected number of iterations to notice the repetition in $N$ element set. It is not about the actual cost ...
- 47.5k
1
vote
Pollard Rho pseudorandom function
In general a function $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ is a PRF, if you can not distinguish it from a real random function. For that you can play a game with an adversary. The ...
- 2,120
1
vote
The dth root unity in the Pollard Rho Algorithm
1) Because $r$ is a primitive root, there exists a $k$ such that $r^k = q$, so $r^{dk} = q^d$.
2) The sample code (lifted from section 3.6.3 of the Handbook of Applied Cryptography http://cacr....
- 1,411
1
vote
Pollard's Kangaroo-- What is the failure probability (assuming random functions)?
Edlyn Teske has had a look at this question in her paper, specifically in section 6.3. I restate it in your notation:
Kangaroos running in cycles During a kangaroo's travel, there is a possibility ...
- 21.2k
1
vote
How many iterations for Pollard's $p-1$ with $p = r^k + 1$ for prime $r$?
What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + 1 < q < r^{k+1}$?
...
- 145k
1
vote
Accepted
Can you help me understand Pollard's rho example?
The algorithm is clear about all your questions. The partitions of $G=\mathbb{Z}^{*}_{383}$ are the sets
$$S_1=\{x \in G: x \bmod 3=1\}$$
$$S_2=\{x \in G: x \bmod 3=0\}$$
$$S_3=\{x \in G: x \bmod 3=2\}...
- 1,015
1
vote
Accepted
Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space?
The Rho method is probabilistic, so it's possible you could find the solution within the first few iterations, or after you've generated almost the entire space.
The probability starts getting in ...
- 2,627
Only top scored, non community-wiki answers of a minimum length are eligible