Cryptography Stack Exchange
Cryptography Stack Exchange

Questions tagged [pollard-rho]

Algorithms for integer factorization and discrete logarithm invented by John Pollard (1975). It is often used in cryptanalysis because it only requires a small amount of space and remains polynomial in time.

If the pseudorandom number $x=g(x)$ occurring in the Pollard-$\rho$ algorithm were an actual random number, it would follow that success would be achieved half the time, by the Birthday paradox in $O(n^{1/2})O({\sqrt p})\leq O(n^{1/4})$ iterations. It is believed that the same analysis applies as well to the actual rho algorithm, but this is a heuristic claim, and rigorous analysis of the algorithm remains open.

21 questions
6
votes
1 answer

Iterations of pollards kangaroo attack on elliptic curves

I want to understand the Pollard kangaroo attack on elliptic curves. I found this Pollard's kangaroo attack on Elliptic Curve Groups Q/A pretty helpful, but not complete. The posts provides a pretty good algorithm for the attack: def…
Titanlord
  • 1,890
  • 8
  • 25
6
votes
2 answers

Elliptic curve and "vanity" public keys

I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes). In the secp256k1 case (the Bitcoin curve), G. Maxwell has found a public key with…
arulbero
  • 89
  • 6
6
votes
0 answers

Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve $E$ over a finite field $\mathbb{F}_q$ with…
Luca
  • 201
  • 1
  • 4
5
votes
0 answers

Variant of Pollard rho using small factors of p - 1

Given an integer $N$ to factor which is divisible by some prime $p$, suppose you know (or guess) that $p - 1$ has a few small factors, e.g. $3, 2^2, 5$. Define $B$ as a product of small prime powers so that $q \vert p - 1$ and $q \vert B$ where…
Seawaves32
  • 91
  • 2
4
votes
2 answers

Issue implementing Pollard's Rho for discrete logarithms

I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to Wikipedia and implemented the code from Pollard's rho…
cheater
  • 143
  • 6
3
votes
0 answers

Pollard Rho Optimization

One of the most important attacks on Elliptic Curve cryptography is Pollard's Rho method. The effect on security can be seen on SafeCurves. This attack is pretty old and there has been a bunch of optimizations. Some of them are listed here on page…
Titanlord
  • 1,890
  • 8
  • 25
3
votes
1 answer

Small complex multiplication field discriminant for solving ECDLP

I've seen from the SafeCurve criteria that one should try to avoid small complex multiplication field discriminant as it can speedup the discret log computation via the Polard Rho method. However, I cannot find any information about how this…
Binou
  • 398
  • 3
  • 14
3
votes
1 answer

Pollard's Lambda algorithm ecdlp with Pohlig Hellman

I'm trying to solve the ECDLP problem given an elliptic curve defined over a prime field. This prime is large (about 256 bits). I managed to factor the order of the curve, and most of the prime factors were smooth, but two of the factors weren't,…
user45694
  • 31
  • 2
2
votes
0 answers

Pollard's Kangaroo: How random does $f$ have to be?

I'm implementing Pollard's kangaroo algorithm as described here. Wikipedia's description of the protocol says that you should have "a pseudorandom map $f:G\rightarrow S$." Does anyone know what happens if you weaken the properties of the map? I'm…
Daniel-耶稣活着
  • 389
  • 2
  • 10
2
votes
1 answer

Pollard's Kangaroo-- What is the failure probability (assuming random functions)?

I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group. He has a Kangaroo Algorithm (page 4) which allows you, if you know that $x$ is in a range of size $w$, to find…
Daniel-耶稣活着
  • 389
  • 2
  • 10
2
votes
2 answers

How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?

I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete logarithm problem and find private key $x$. In…
Gleb Ignatev
  • 23
  • 3
2
votes
1 answer

Why is pollard rho's expected runtime O(sqrt(n)) not O(sqrt(n) * log(n))?

I understand by the birthday problem, the algorithm will expect to take $\mathcal{O}(\sqrt{N})$ times to find a cycle. However, one of the steps involves computing the $\gcd(\mid x-y \mid, N)$, which, I assume, uses the euclidean algorithm, which…
Thomas Bao
  • 21
  • 1
1
vote
1 answer

DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus

$g^{ab} \pmod{p} = B^a \pmod{p}$ where all variables are known except $a$. In this case, I have an equivalent value for $a'*b'$, but this is not the same as the real values of $a*b$ due to the modulus. Everything else including the generator, the…
Tom Smith
  • 11
  • 1
1
vote
1 answer

The dth root unity in the Pollard Rho Algorithm

In the original paper of Pollard's Monte Carlo Methods for Index Computation (mod p): When the epact is reached, i.e. $$x_i = x_{2i}.$$ then the following equation is formed $$q^m \equiv r^n \pmod p,$$ where where $m=a_e- a_{2e} \pmod{p - 1}$ and…
kelalaka
  • 45,607
  • 9
  • 104
  • 179
1
vote
1 answer

Williams' $p+1$ in tandem with Pollard's $p-1$?

Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint for $p + 1$, it seems to me that it would be…
Dave Schulman
  • 51
  • 5
1
2