Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm working with the affine representations of points of the Secp256k1 elliptic curve (from Bitcoin).

I've read many papers that show that computing some functions, like $f(P)=3P$ can be computed faster than the standard way. Other papers say that with some pre-computation, the field inversion can be amortized if $F^1(P) ... F^k(P)$ must be computed.

I need the fastest function $F(P)$ that, when applied to the last result iteratively, generates a sequences of points whose average period is large (I don't need any proof, it can be just large in practice). To be fast I suppose it should be computed without field inversions. I don't mind to pre-compute some values.

For example, it could be $F(P) = 1.5P+4Q$ for a fixed $Q$. It doesn't matter which function it is, because I need it to generate random points in the curve. The probability distribution doesn't matter either. (notation: $1.5$ is the point halving of $3P$)

Motivation: Solutions to this problem may be helpful for generating vanity addresses.

share|improve this question
    
The standard way to generate random points is to select a random value for X, check to see if there's a solution for the elliptic curve equation with that value, and if these is, pick one of the two possible values for Y. Or, do you need random values with known relationships, or for which you can compute output number N+1 given output number N? –  poncho May 23 '13 at 16:03
    
Yes, I need a way to track a point back to source points P1, P2, Pn (with a known relation) and that's why I had though about a linear function F on the previous points. –  Richard May 23 '13 at 18:07
1  
I bet this is a Bitcoin-related question, in which case although people say it uses a Koblitz curve it is in fact not one. I think I have a good candidate solution for your problem but it works for a composite modulus and only if the group order is kept secret. If that's useful then let me know. If you're working in affine coordinates and you want to generate new points without inversions then you're probably limited to the Frobenius endomorphism. –  Barack Obama May 24 '13 at 0:04
1  
Can you describe what problem you actually want to solve? –  CodesInChaos May 24 '13 at 5:47
1  
I have some experience with Bitcoin's curve and I'm very confident that you will be unable to avoid an inversion for your problem as stated. I'm also quite confident that the restrictions you have specified above are more restrictive than are really necessary. Perhaps you can let us know whether you are a) trying to break the curve, b) generate vanity addresses, c) implementing some deterministic wallet scheme or d) implementing transactions which third parties can't link to an address. –  Barack Obama May 24 '13 at 23:20
show 6 more comments

2 Answers

With your curve, you can use the Gallant-Lambert-Vanstone (GLV) method to answer your question. Indeed, the equation of your curve is: $$y^2=x^3+7.$$ Since $p$ is congruent to $1$ modulo $3$, there are cube roots of unity modulo $p$. Let: $$j=55594575648329892869085402983802832744385952214688224221778511981742606582254 \pmod{p}.$$ You can check that $j^3\equiv 1\pmod{p}$. The complex multiplication by $j$ sends $P=(X_P,Y_P)$ to $P'=(jX_P,Y_P)$.

Moreover, $P'=J\cdot P,$ where $$J=37718080363155996902926221483475020450927657555482586988616620542887997980018.$$

Finally, multiplication by $J-1$ can be performed efficiently (one application of complex multiplication and one addition) and has high order. Don't use $J+1$: it has order $6$.

EDIT $J^3$ is $1$ modulo the order of the curve, while $j^3$ is $1$ mod $p$.

This endomorphism of the curve is the projection of the complex multiplication of the curve $y^2=x^3+7$ over the rationals to the curve reduced mod $p$. This is why is is usually called the complex multiplication.

All in all, this gives a reasonably fast way to generate random looking multiples of $P$.

The full GLV method is much more than that since it speeds up multiplication by an arbitrary constant compared to regular double and add, but its basic idea relies on having an endomorphism that can be computed quickly.

share|improve this answer
    
This is not the GLV method - it's just using an efficiently computable endomorphism which is well known. Also, the solution described does not avoid the inversion required to produce an affine point. Finally, I'm not sure what's so "complex" about the multiplication by j! –  Barack Obama Jul 11 '13 at 0:00
add comment

Depending on what you actually want to do, it might be possible to speed this up using a batch inversion, instead of inverting each denominator individually.

  1. Use some form of extended coordinates
  2. Compute a few hundred new points in extended coordinates, with known relation to the original point.
  3. Multiply all denominators together and invert it.
  4. Use multiplications of the combined denominator with the existing denominators to compute the individual denominators.

AFAIK Step 3+4 have a cost of 3 field multiplications per-point. Which is much cheaper that 200ish multiplications required for an inversion.

One way to implement steps 2 and 3 is:

Given the denominators $z_1 ... z_n$:

  • Define $r_i = \Pi_{j=i+1}^n z_j$ compute iteratively as $r_n=1$, $r_i=r_{i+1} \cdot z_{i+1}$ for $i=n ... 0$ and store it in an array.

  • Compute $r_0^{-1}$ using a field inversion.

  • Define $l_1 = r_0^{-1} \cdot \Pi_{j=1}^{i-1} z_j$ and compute it iteratively as $l_0= r_0^{-1}$ and then $l_i = l_{i-1}\cdot z_{i-1}$

  • $z_i^{-1}=l_i \cdot r_i$. Given $z_i^{-1}$ the affine coordinate can be obtained by multiplying it with the nominator.

Why does this work?

$z_i^{-1} =\\ = (\Pi_{j=1}^n z_j) \cdot (\Pi_{j=1}^n z_j)^{-1} \cdot z_i^{-1} \\ = (\Pi_{j=1}^{i-1} z_j \cdot z_i \cdot \Pi_{j=i+1}^n z_j)\cdot (\Pi_{j=1}^n z_j)^{-1} \cdot z_i^{-1}\\ = ((\Pi_{j=1}^n z_j)^{-1}\cdot\Pi_{j=1}^{i-1} z_j) \cdot \Pi_{j=i+1}^n z_j\\ = l_i \cdot r_i$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.