3
$\begingroup$

If you have a secp256k1 keypair and you increment the private key by 1, then a faster way to compute the new public key is to perform an addition on the previous public key. But by how much?

Some software like Profanity on Ethereum used this.

$\endgroup$

1 Answer 1

7
$\begingroup$

If you have a secp256k1 keypair and you increment the private key by 1, what's a fast way to compute the new public key?

Using notation close to sec1 and the parameters of secp256k1, if the private key is the integer $d$ and the public key is the point $Q$, then $Q=d\,G$ where $G$ is a well-known point on the curve. If follows that for $d'=d+1$ (and except for $d=n-1$), the public key is $$\begin{align}Q'&=d'\,G\\&=(d+1)\,G\\&=d\,G+1\,G\\&=Q+G\end{align}$$

That is, we need to add $G$ to the original public key to get the new one. That addition should be per the rules of point addition for Elliptic Curves over $\mathbb F_p$. Except if $d=1$, that will be case 4 (add two points with different x-coordinates).

If the public key is compressed (33 bytes with the first 02h or 03h), we'll first need to decompress the public key. In detail: we convert the last 32 bytes of the public key to $x$ (per big endian convention), compute $t=(x^3+b)\bmod p$ then tentative $y=t^{((p+1)/4)}\bmod p$, check that $y^2\bmod p=t$ (otherwise $x$ was incorrect), and then if the parity of $y$ and the first byte (02h or 03h) of the public key differ change $y$ to $p-y$.


Update per comment: The performance gain is huge (likely at least one, perhaps more than two decimal orders of magnitude), because point multiplication is much more costly than point addition. Depending on algorithm, there are in the order of 300 point additions or doublings during a point multiplication by a random 256-bit $d$; and while for some methods of point multiplication the internal additions or doublings are much faster than for standard point addition, the performance gain is still huge.

Notice that if the goal is generating public/private key pairs with a public key of a certain form (e.g. a vanity key), it's slightly better to go from $d$ to $d+(n+1)/2\bmod n$ rather than to $d+1$. This is because we can now add $((n+1)/2)\ G$ instead of $G$ to go from one public key to the next, and that operation is slightly faster than adding $G$, because the $x$ coordinate of $((n+1)/2)\ G$ is only 166-bit (see this), instead of 256-bit for $G$, which allows a small speedup in point addition.

$\endgroup$
4
  • $\begingroup$ But in the way you describe (point addition over elliptic curve) this isn’t faster in term of clocks than computing the multiplication directly ? $\endgroup$ Apr 16 at 13:19
  • $\begingroup$ @user2284570: It's MUCH faster; see update $\endgroup$
    – fgrieu
    Apr 16 at 13:53
  • $\begingroup$ ‎then what would be the fastest algorithm for an ꜰᴘɢᴀ on Koblitz’s curve (secp256k1) ? Considering more operations takes more physical space and thus there’re have to be a tradeoff between space and sequential speed ? (because otherwise less space means less brute force units) crypto.stackexchange.com/q/111457 $\endgroup$ Apr 16 at 21:18
  • $\begingroup$ @user2284570: in FPGA, I'd consider the algorithm outlined (with the variation in the last paragraph for vanity keys, but not for key search with partial private key). For modular reduction, the special form of $p$ leads to a standard optimisation. Most of the computational effort will be in the inversion modulo $p$ of the denominator $x_2−x_1$ for $\lambda$, and for this I'd consider this method. You'd want some degree of pipelinization, I guess. But I've never done anything remotely similar in FPGA. $\endgroup$
    – fgrieu
    Apr 17 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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