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: ...
Conrado's user avatar
  • 6,434
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/...
poncho's user avatar
  • 147k
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 ...
Geoffroy Couteau's user avatar
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 ...
Daniel S's user avatar
  • 23.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 ...
Meysam Ghahramani's user avatar
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 ...
fgrieu's user avatar
  • 141k
3 votes
Accepted

Example of CM field discriminant of elliptic curves

The speed up is not for all curves with small CM discriminant, but specifically for those with CM by $\sqrt{-3}$ (hence allowing us to define a cube root of unity $\beta=(1+\sqrt{-3})/2$. For a given ...
Daniel S's user avatar
  • 23.9k
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 ...
poncho's user avatar
  • 147k
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 ...
Christopher Swenson's user avatar
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 ...
Squeamish Ossifrage's user avatar
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 ...
fgrieu's user avatar
  • 141k
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 ...
Titanlord's user avatar
  • 2,264
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 ...
kelalaka's user avatar
  • 48.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 ...
Titanlord's user avatar
  • 2,264
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....
Aman Grewal's user avatar
  • 1,421
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 ...
kodlu's user avatar
  • 22.5k
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}$? ...
poncho's user avatar
  • 147k
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\}...
gammatester's user avatar
  • 1,005
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 ...
user13741's user avatar
  • 2,627

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