In short: I got obsessed by making it as fast as possible and read a ton of elliptic curve cryptography papers.
It was a journey that started from reading WireGuard kernel sources,
then I was thinking about deriving IPv6 address from peer key,
left a random comment on a dated gist https://gist.github.com/artizirk/c91e4f8c237dec07e3ad1b286f1...
from which I learned about vanity key concept.
I've implemented first version of https://github.com/AlexanderYastrebov/wireguard-vanity-key and then continuously profiled it to improve performance.
From profiling I saw that field inversion and multiplication are the main operations.
I realized I need to reduce unnecessary computation to make it faster and for that I need to understand the underlying math which is actually quite simple.
I read RFCs for Curve25519 and papers from D. J. Bernstein who invented it.
It also supports distributed search, e.g. you can run it in Kubernetes without exposing the secret key to the cluster, see https://github.com/AlexanderYastrebov/onion-vanity-address?t...
How did you learn the math used to speed up your implementation?
Thanks, great question!
In short: I got obsessed by making it as fast as possible and read a ton of elliptic curve cryptography papers.
It was a journey that started from reading WireGuard kernel sources, then I was thinking about deriving IPv6 address from peer key, left a random comment on a dated gist https://gist.github.com/artizirk/c91e4f8c237dec07e3ad1b286f1... from which I learned about vanity key concept.
I naturally enjoy doing performance optimization work so when I discovered incremental approach idea here https://github.com/warner/wireguard-vanity-address/pull/15 I decided to create my own tool.
I've implemented first version of https://github.com/AlexanderYastrebov/wireguard-vanity-key and then continuously profiled it to improve performance. From profiling I saw that field inversion and multiplication are the main operations.
I realized I need to reduce unnecessary computation to make it faster and for that I need to understand the underlying math which is actually quite simple.
I read RFCs for Curve25519 and papers from D. J. Bernstein who invented it.
You can see how my understanding evolved from the commit history https://github.com/AlexanderYastrebov/wireguard-vanity-key/c...
Once I have the fastest algorithm to generate vanity Curve25519 keypairs I can apply it to other things that use Curve25519 (https://ianix.com/pub/curve25519-deployment.html) or Ed25519 (https://ianix.com/pub/ed25519-deployment.html) which is an equivalent curve.
See also my other related projects: * [age-vanity-keygen](https://github.com/AlexanderYastrebov/age-vanity-keygen) — Fast vanity age X25519 identity generator. * [vanity25519](https://github.com/AlexanderYastrebov/vanity25519) — Efficient Curve25519 vanity key generator.