Re-Deriving the edwards25519 Decoding Formulas

https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-re-deriving-the/ [buttondown.email]

2020-12-21 17:03

A lot of my job is implementing specifications, and sometimes in a crypto spec you’ll encounter something like this and what you do is nod, copy it into a comment, break it down into a sequence of operations, and check that the result matches a test case. However, the other day I was having a bit of an identity crisis because I could not remember basic algebra, so I went and re-derived the edwards25519 point decoding formulas as a sort of homework. It turned out to be pretty useful for understanding pieces of the implementation I had been just treating as black boxes. I’m going to try to take you along for the ride, to show that there is no dark magic involved, and that we can all get to the same result as the specification with step-by-step high-school algebra.