3 ms·

Understanding ECDSA

100 points by avidthinker 10mo ago

This article is basically an exercise in understanding ECDSA (Elliptic Curve Digital Signature Algorithm) from scratch. All I assume is some basic math and a willingness to pick up a bit of abstract math along the way. I try to explain everything as intuitively as possible, but, despite that, the article still demands some serious effort from the reader. When I analyzed the Extended Euclidean Algorithm, one thing led to another, and I ended up writing a little intro to generating functions. You can even jump to that part and ignore the rest, if you want! Other readers may instead choose to skip that section altogether, as it's self-contained.

deleted 10mo ago
[deleted]
joezydeco 10mo ago
Your definition of "basic math" greatly differs from mine...
- j16sdiz 10mo ago
  > abstract algebra is not a requirement. and talks about fields and groups
  - mrkeen 10mo ago
    They're just spooky names for simple concepts - and the article defines them on first use. If abstract algebra were a requirement, they'd skip these definitions. Paraphrasing 'Group' from the article to see if I've understood it: A set of elements G, and some operation ⊕, where (g1 ⊕ g2) is also in G. // "Type-safety" Some g0 exists such that (gn ⊕ g0) == (g0 ⊕ gn) == gn // "Zero" For every g, there's some inverse gi such that (g ⊕ gi) == (gi ⊕ g) == g0 // "Cancelling-out" a ⊕ (b ⊕ c) == (a ⊕ b) ⊕ c // "Associative" If (a ⊕ b) == (b ⊕ a) then the group is also "abelian/commutative"
    - letmetweakit 10mo ago
      They're spooky names for simple concepts, with extremely deep consequences and hard theory, don't be fooled.
    - b112 10mo ago
      Is the aspirin symbol you're using as + figure, a special kind of +, or just a different looking +? What does the circle around the + mean? I'm mentioning this, as other people in this thread are discussing "explaining symbols you use", and you're using a non-standard symbol for +. I can easily imagine a circle around + making + a different operation, and wonder if it is so? Aspirin I've bought in the past has a + on it, and its trademark is a + within a circle. That's why I've latched on what a "common person" might view the symbol as: https://www.brand.aspirin.com/sites/g/files/vrxlpx46831/files/styles/desktop_1000xauto/public/2025-08/Aspirin%20logo%20global_368x368.png https://www.brand.aspirin.com/sites/g/files/vrxlpx46831/file... Interestingly, I have University level math courses, but decades out of date, and have never run into that symbol. I see it here: https://en.wikipedia.org/wiki/Direct_sum https://en.wikipedia.org/wiki/Direct_sum
      - jeroenhd 10mo ago
        ⊕ is a standard symbol for this kind of math. The symbol itself is ancient because it's so simple, so I don't see what Bayer's aspirin logo has to do with it. It acts as a normal +, mostly. When you're dealing with modulo math, the "normal" plus becomes a bit weird as there are rules attached to a number expressed as "(a + b) mod c", so mathematicians often use symbols like ⊕ to mean something like "+, but different". The second link you posted does the same, it acts sort of like normal addition, conceptually, except it's not done on actual numbers but groups. In definitions like these, you may as well use a peace symbol or a picture of a frog; "some operation ⊕" means "there is some operation we write down like this, and it does this and that". Another place you may find ⊕ is when it's used to represent XOR in some cases; (a + b) mod 2 is a bitwise XOR when operating on single bits (again, it means "normal addition except with weird rules", namely the mod 2 that makes you throw out anything larger than the last bit).
      - mrkeen 10mo ago
NetMageSCW 10mo ago
The article would be a lot better if it was what it said on the tin, instead of being filled with lots of unnecessary (as described in the article) digressions. If you couldn’t restrain yourself to sticking to the subject, at least put the digressions behind links or footnotes or pop-ups where they don’t detract from reading about the actual claimed intended subject.
- avidthinker 10mo ago
  I think that's a little unfair, as there's only a single digression about Fibonacci numbers (a very interesting one, IMO). The section is clearly indicated as skippable and can be quickly skipped by using the tree on the right. Since my exposition is constructive in nature, the proofs and other remarks are an integral part of the article, not digressions.
mkornaukhov 10mo ago
I've recently understood how RSA works and thought it was a cool achievement. But this article with "basic" math... Not so enjoyable for just a dev =)
- avidthinker 10mo ago
  Sorry about that. I tried to introduce the necessary concepts starting from zero, or I thought I did. We devs (take back that "just" :) ) deal with much harder stuff when we build complex APIs, so the problem must be at the syntactic level. To us devs, math may look like an antipattern, with all the short names and operator overloading. But that's unavoidable, unfortunately. It's normal to spend hours or more on a single concept until it clicks. I'd say don't give up, but I understand one's time is valuable, and the return might not be high enough to justify the cost.
atoav 10mo ago
A big part of what makes maths hard for non-math-people is math notation. That is like if a well versed python programmer told you it is as simple as: result = [[{"x": x, "y": y, "v": (x+y if (x+y)%2==0 else None)} for (x, y) in row] for row in data] Now with a bit of reasoning another programmer that hasn't used python might be able to figure out what that means. But what if my audience is non-programmers? The moment they encounter the first unexplained square brackets and then an opening curly brace it will essentially feel like telling them: "Here is a riddle for you" or potentially even like "I expect you to know this, dummy". Not that this text was particular bad in that regard, but I wish more math people had a heightened awareness of the fact that for many the hard part is not understanding the concept (e.g. fourier transformation), but the foreign looking signs mathematicians have decided to use to write them down. That is as if someone explaines the way to the next train station to you in a foreign language. The hard part isn't understanding the way, it is understanding the noises that are supposed to make up the description. And as a programmer who from time to time has to translate maths into discrete programs (or the other way around) the hard part was always parsing the notation and when I figured it out I was usually like: "Ohh, this is just a simple algorithm doing that. So if you want to explain a math concept to programmers you should chose one of two routes: (A) Stay with your notation and explain every character that isn't visible on a regular keyboard in length and gently lead the reader into being able to read the notation or (B) let go of the notation and first explain what it does and how, e.g. for our FFT example: FFT slices your list of values into frequency buckets, figures out how much of each frequency is present, and returns those strengths as numbers. And then you can work backwards from that understanding towards your notation explaining which sign relates to which part of the concept (e.g. to the number of buckets). I would prefer the latter, since it explains both the concept and gives the mathematician a chance to explain how and why math notation can be useful on top, e.g. to figure out certain properties of the method that may even have practical implications.
- mac-monet 10mo ago
  Was nodding along as I was reading this. I recently was given a paper and spoke with the engineer implementing it. The paper was incredibly dense and hard to parse. But through talking with the engineer and rewriting some terms to more common names, the math turned out to be quite simple. Echoing your sentiment, I wish more mathematicians would use simple terminology. My personal theory as to why this isn't done is the same reason why overengineering happens, that the writer is trying to cover every base but makes the hottest path a jumbled mess.
some_furry 10mo ago
In addition to the malleability attack (high-S and low-S both being valid for a given value of R), ECDSA doesn't provide a property called exclusive ownership: https://soatok.blog/2023/04/03/asymmetric-cryptographic-commitments/#ecdsa-signatures https://soatok.blog/2023/04/03/asymmetric-cryptographic-comm... In contrast, EdDSA (which is based on Schorr signatures) does, by construction: the public key is included in one of the hashes, which binds the signature to a particular public key. I haven't investigated whether cryptocurrency's use of Schnorr satisfies this property or not. (Indeed, I do not care about cryptocurrency at all.) So it's an exercise to the reader if it's satisfactory or not :3
- nrhrjrjrjtntbt 10mo ago
  Excellent blog by the way. I esp. love the humility - advanced concepts about cryptogtaphy then I see an article for new people about how to get into tech. Keeping the ladder out, so to speak.
oleganza 10mo ago
ECDSA is a horrible workaround for patent on Schnorr signatures. Here's my talk from 2019 about the issue. https://www.youtube.com/live/2IpZWSWUIVE?si=-LRRbU2mJgL9LiNP&t=6456 https://www.youtube.com/live/2IpZWSWUIVE?si=-LRRbU2mJgL9LiNP...
- mac-monet 10mo ago
  Great talk. Wish the camera focused on the slides more. The ed25519 issues are absolutely insane. Anywhere I can read more about that?
- deleted 10mo ago
  [deleted]
- nrhrjrjrjtntbt 10mo ago
  Excellent. Really enjoyed that.

Understanding ECDSA

100 points by avidthinker 10mo ago

deleted 10mo ago

[deleted]

joezydeco 10mo ago

Your definition of "basic math" greatly differs from mine...

j16sdiz 10mo ago
> abstract algebra is not a requirement. and talks about fields and groups
- mrkeen 10mo ago
  They're just spooky names for simple concepts - and the article defines them on first use. If abstract algebra were a requirement, they'd skip these definitions. Paraphrasing 'Group' from the article to see if I've understood it: A set of elements G, and some operation ⊕, where (g1 ⊕ g2) is also in G. // "Type-safety" Some g0 exists such that (gn ⊕ g0) == (g0 ⊕ gn) == gn // "Zero" For every g, there's some inverse gi such that (g ⊕ gi) == (gi ⊕ g) == g0 // "Cancelling-out" a ⊕ (b ⊕ c) == (a ⊕ b) ⊕ c // "Associative" If (a ⊕ b) == (b ⊕ a) then the group is also "abelian/commutative"
  - letmetweakit 10mo ago
    They're spooky names for simple concepts, with extremely deep consequences and hard theory, don't be fooled.
  - b112 10mo ago
    Is the aspirin symbol you're using as + figure, a special kind of +, or just a different looking +? What does the circle around the + mean? I'm mentioning this, as other people in this thread are discussing "explaining symbols you use", and you're using a non-standard symbol for +. I can easily imagine a circle around + making + a different operation, and wonder if it is so? Aspirin I've bought in the past has a + on it, and its trademark is a + within a circle. That's why I've latched on what a "common person" might view the symbol as: https://www.brand.aspirin.com/sites/g/files/vrxlpx46831/files/styles/desktop_1000xauto/public/2025-08/Aspirin%20logo%20global_368x368.png https://www.brand.aspirin.com/sites/g/files/vrxlpx46831/file... Interestingly, I have University level math courses, but decades out of date, and have never run into that symbol. I see it here: https://en.wikipedia.org/wiki/Direct_sum https://en.wikipedia.org/wiki/Direct_sum
    - jeroenhd 10mo ago
      ⊕ is a standard symbol for this kind of math. The symbol itself is ancient because it's so simple, so I don't see what Bayer's aspirin logo has to do with it. It acts as a normal +, mostly. When you're dealing with modulo math, the "normal" plus becomes a bit weird as there are rules attached to a number expressed as "(a + b) mod c", so mathematicians often use symbols like ⊕ to mean something like "+, but different". The second link you posted does the same, it acts sort of like normal addition, conceptually, except it's not done on actual numbers but groups. In definitions like these, you may as well use a peace symbol or a picture of a frog; "some operation ⊕" means "there is some operation we write down like this, and it does this and that". Another place you may find ⊕ is when it's used to represent XOR in some cases; (a + b) mod 2 is a bitwise XOR when operating on single bits (again, it means "normal addition except with weird rules", namely the mod 2 that makes you throw out anything larger than the last bit).
    - mrkeen 10mo ago

NetMageSCW 10mo ago

The article would be a lot better if it was what it said on the tin, instead of being filled with lots of unnecessary (as described in the article) digressions. If you couldn’t restrain yourself to sticking to the subject, at least put the digressions behind links or footnotes or pop-ups where they don’t detract from reading about the actual claimed intended subject.

avidthinker 10mo ago
I think that's a little unfair, as there's only a single digression about Fibonacci numbers (a very interesting one, IMO). The section is clearly indicated as skippable and can be quickly skipped by using the tree on the right. Since my exposition is constructive in nature, the proofs and other remarks are an integral part of the article, not digressions.

mkornaukhov 10mo ago

I've recently understood how RSA works and thought it was a cool achievement. But this article with "basic" math... Not so enjoyable for just a dev =)

avidthinker 10mo ago
Sorry about that. I tried to introduce the necessary concepts starting from zero, or I thought I did. We devs (take back that "just" :) ) deal with much harder stuff when we build complex APIs, so the problem must be at the syntactic level. To us devs, math may look like an antipattern, with all the short names and operator overloading. But that's unavoidable, unfortunately. It's normal to spend hours or more on a single concept until it clicks. I'd say don't give up, but I understand one's time is valuable, and the return might not be high enough to justify the cost.

atoav 10mo ago

A big part of what makes maths hard for non-math-people is math notation. That is like if a well versed python programmer told you it is as simple as: result = [[{"x": x, "y": y, "v": (x+y if (x+y)%2==0 else None)} for (x, y) in row] for row in data] Now with a bit of reasoning another programmer that hasn't used python might be able to figure out what that means. But what if my audience is non-programmers? The moment they encounter the first unexplained square brackets and then an opening curly brace it will essentially feel like telling them: "Here is a riddle for you" or potentially even like "I expect you to know this, dummy". Not that this text was particular bad in that regard, but I wish more math people had a heightened awareness of the fact that for many the hard part is not understanding the concept (e.g. fourier transformation), but the foreign looking signs mathematicians have decided to use to write them down. That is as if someone explaines the way to the next train station to you in a foreign language. The hard part isn't understanding the way, it is understanding the noises that are supposed to make up the description. And as a programmer who from time to time has to translate maths into discrete programs (or the other way around) the hard part was always parsing the notation and when I figured it out I was usually like: "Ohh, this is just a simple algorithm doing that. So if you want to explain a math concept to programmers you should chose one of two routes: (A) Stay with your notation and explain every character that isn't visible on a regular keyboard in length and gently lead the reader into being able to read the notation or (B) let go of the notation and first explain what it does and how, e.g. for our FFT example: FFT slices your list of values into frequency buckets, figures out how much of each frequency is present, and returns those strengths as numbers. And then you can work backwards from that understanding towards your notation explaining which sign relates to which part of the concept (e.g. to the number of buckets). I would prefer the latter, since it explains both the concept and gives the mathematician a chance to explain how and why math notation can be useful on top, e.g. to figure out certain properties of the method that may even have practical implications.

mac-monet 10mo ago
Was nodding along as I was reading this. I recently was given a paper and spoke with the engineer implementing it. The paper was incredibly dense and hard to parse. But through talking with the engineer and rewriting some terms to more common names, the math turned out to be quite simple. Echoing your sentiment, I wish more mathematicians would use simple terminology. My personal theory as to why this isn't done is the same reason why overengineering happens, that the writer is trying to cover every base but makes the hottest path a jumbled mess.

some_furry 10mo ago

In addition to the malleability attack (high-S and low-S both being valid for a given value of R), ECDSA doesn't provide a property called exclusive ownership: https://soatok.blog/2023/04/03/asymmetric-cryptographic-commitments/#ecdsa-signatures https://soatok.blog/2023/04/03/asymmetric-cryptographic-comm... In contrast, EdDSA (which is based on Schorr signatures) does, by construction: the public key is included in one of the hashes, which binds the signature to a particular public key. I haven't investigated whether cryptocurrency's use of Schnorr satisfies this property or not. (Indeed, I do not care about cryptocurrency at all.) So it's an exercise to the reader if it's satisfactory or not :3

nrhrjrjrjtntbt 10mo ago
Excellent blog by the way. I esp. love the humility - advanced concepts about cryptogtaphy then I see an article for new people about how to get into tech. Keeping the ladder out, so to speak.

oleganza 10mo ago

ECDSA is a horrible workaround for patent on Schnorr signatures. Here's my talk from 2019 about the issue. https://www.youtube.com/live/2IpZWSWUIVE?si=-LRRbU2mJgL9LiNP&t=6456 https://www.youtube.com/live/2IpZWSWUIVE?si=-LRRbU2mJgL9LiNP...

mac-monet 10mo ago
Great talk. Wish the camera focused on the slides more. The ed25519 issues are absolutely insane. Anywhere I can read more about that?
deleted 10mo ago
[deleted]
nrhrjrjrjtntbt 10mo ago
Excellent. Really enjoyed that.