Skip to content

Instantly share code, notes, and snippets.

@chjj
Last active February 1, 2023 23:40
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chjj/16ba7fa08d64e8dda269a9fe5b2a8bbc to your computer and use it in GitHub Desktop.
Save chjj/16ba7fa08d64e8dda269a9fe5b2a8bbc to your computer and use it in GitHub Desktop.

Twisted Edwards & Short Weierstrass Equivalence

Putting this here since I don't see it documented anywhere in the literature.

Note that your Short Weierstrass curve must have 2-torsion.

1. Short Weierstrass -> Twisted Edwards

s = sqrt(3 * r^2 + a)
a' = 3 * r + 2 * s
d' = 3 * r - 2 * s

where r^3 + a * r + b == 0

Rational Maps:

x' = (6 * x - a' - d') / (6 * y)
y' = (12 * x - 5 * a' + d') / (12 * x + a' - 5 * d')

Note that this map is undefined for for x = (5 * d' - a') / 12 or y = 0.

Infinity should be mapped to (0, 1).

For the exceptional cases, map the 2-torsion point ((a' + d') / 6, 0) to (0, -1), and the 4-torsion point ((5 * d' - a') / 12, (d' - a') / 4 * sqrt(d')) ends up on the twist (only occurs if d' is square).

2. Twisted Edwards -> Short Weierstrass

a' = -(a^2 + 14 * a * d + d^2) / 48
b' = (33 * (a^2 * d + a * d^2) - a^3 - d^3) / 864

Rational Maps:

x' = ((5 * d - a) * y + d - 5 * a) / (12 * (y - 1))
y' = (d - a) * (y + 1) / (4 * x * (y - 1))

Note that this map is undefined for x = 0 or y = 1.

For the exceptional cases, map (0, 1) to infinity, and map the 2-torsion point (0, -1) to ((a + d) / 6, 0).

3. Test Vectors

Ed25519 (Twisted Edwards)

a = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec
d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3
x = 0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a
y = 0x6666666666666666666666666666666666666666666666666666666666666658

Ed25519 (Short Weierstrass)

a = 0x5d4eacd3a5b9bee63197e10d617b3dd66bb8b65d0ca52af7ac71e18ef8bc172d
b = 0x1d11b29bcfd0b3e0550ddb06105780d5f54831976b9fbc329004ebc1f364b2a4
x = 0x2a78dd0fd02c0339f00b8f02f1c20618a9c13fdf0d617c9aca55c89b025aef35
y = 0x29c644a5c71da22ebe483ba563798323cf6fd061807131659b7830f3f62c1d14
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment