@Benjojo12 and I are building an encryption tool that will also support SSH keys as recipients, because everyone effectively already publishes their SSH public keys on GitHub.

For RSA keys, this is dangerous but straightforward: a PKCS#1 v1.5 signing key is the same as an OAEP encryption key.

Ed25519 keys, though, are specifically made to be used with EdDSA, the Edwards-Curve Digital Signature Algorithm. To encrypt to them we'll have to choose between converting them to X25519 keys to do Ephemeral-Static Diffie-Hellman, and devising our own Diffie-Hellman scheme that uses Ed25519 keys.

While the latter is a totally viable strategy—you can do Ephemeral-Static Diffie-Hellman on twisted Edwards curves—I wanted to reuse the X25519 codepath, so I opted for the former.

First, we need to understand the difference between Ed25519 and X25519. For that I recommend Montgomery curves and their arithmetic by Craig Costello and Benjamin Smith, which is where I learned most of the underlying mechanics of Montgomery curves. The high level summary is that the twisted Edwards curve used by Ed25519 and the Montgomery curve used by X25519 are birationally equivalent: you can convert points from one to the other, and they behave the same way. The main difference is that on Montgomery curves you can use the Montgomery ladder to do scalar multiplication of x coordinates, which is fast, constant time, and sufficient for Diffie-Hellman. Points on the Edwards curve are usually referred to as (x, y), while points on the Montgomery curve are usually referred to as (u, v).

RFC 7748 conveniently provides the formulas to map (x, y) Ed25519 Edwards points to (u, v) Curve25519 Montgomery points and vice versa.

(u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
(x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))

So that's what a X25519 public key is: a u coordinate on the Curve25519 Montgomery curve obtained by multiplying the basepoint by a secret scalar, which is the private key. An Ed25519 public key instead is the compressed encoding of a (x, y) point on the Ed25519 Edwards curve obtained by multiplying the basepoint by a secret scalar derived from the private key. (An Ed25519 private key is hashed to obtained two secrets, the first is the secret scalar, the other is used elsewhere in the signature scheme.)

If we use the same secret scalar to calculate both an Ed25519 and an X25519 public key, we will get two points that are birationally equivalent, so we can convert from one to the other with the maps above. There is one catch though: you might have noticed that while we have both x and y coordinates for the Ed25519 public key, we only have the u coordinate for the X25519 key. That's because u coordinates are enough to do Diffie-Hellman (which is the core insight of Curve25519).

For every valid u coordinate, there are two points on the Montgomery curve. The same is true of y coordinates and the Edwards curve. (When you use the birational map, y coordinates map to u coordinates and vice-versa.) That's why we can encode Ed25519 public keys as a y coordinate and a "sign" bit in place of the full x coordinate.

This means that for each X25519 public key, there are two possible secret scalars (k and -k) and two equivalent Ed25519 public keys (with sign bit 0 and 1, also said to be one the negative of the other).

By the way, this all works because the basepoints of the Montgomery and Edwards curves are equivalent. Interestingly enough, the spec made a mistake and picked the wrong v coordinate for the Montgomery basepoint, so that the Montgomery basepoint maps to the negative of the Edwards basepoint. It's fixed in an errata but no one cares about Montgomery v coordinates anyway.

It should be mentioned that there is precedent for converting keys between the two curves: Signal's XEd25519. They do the opposite of what we want to do though, they use an X25519 key for EdDSA. That comes with an issue: an X25519 public key does not carry a v coordinate, so it can map to two Ed25519 keys. They solve it by defining the Edwards point sign bit to be 0, and then negating the Edwards secret scalar if it would generate a point with positive sign. (It also comes with more issues due to not having the other secret that you derive from an EdDSA private key, but that's out of scope. I like the diagram in this blog post if you are curious.)

I recommend reading both section 2.3 of the XEdDSA spec and this StackExchange answer if things don't feel clear at this point.

Getting back to our use case, it turns out that it's pretty easy to use an Ed25519 public key for X25519, because an Ed25519 public key maps to a single X25519 public key, and the Ed25519 secret scalar will be one of the two valid X25519 private keys for that public key.

To encrypt, we take the y coordinate of the Ed25519 public key and we convert it to a Montgomery u coordinate, which we use as an X25519 public key for Ephemeral-Static Diffie-Hellman.

u = (1 + y) / (1 - y)

ephemeral_secret = read(/dev/urandom, 32)
ephemeral_share = X25519(ephemeral_secret, BASEPOINT)
shared_secret = X25519(ephemeral_secret, u)

To decrypt, we derive the secret scalar according to the Ed25519 spec, and simply use it as an X25519 private key in Ephemeral-Static Diffie-Hellman.

secret_scalar = SHA-512(Ed25519_key)[:32]
shared_secret = X25519(secret_scalar, ephemeral_share)

The two peers might end up with different v coordinates, if they were to calculate them, but in X25519 the shared secret is just the u coordinate, so no one will notice.

What remains open for future work is checking for cross-protocol attacks. The only one that really concerns me is if a partial decryption oracle (where you can submit files to an endpoint and it will tell you if they decrypt successfully) allows generating an Ed25519 signature that can be used to log in to an SSH server. I can't see such an attack, but if you can, let me know on Twitter.

P.S. Looks like libsodium already supports this kind of Ed25519 to Curve25519 conversion, which is great as it makes it easy for languages with libsodium bindings (most of them) to implement age, and it gets us something to test against.