Elliptic Curve Digital Signature Algorithm (ECDSA)

Problem Description
The Elliptic Curve Digital Signature Algorithm (ECDSA) is a digital signature scheme based on elliptic curve cryptography. It is used to verify data integrity and the identity of the signer and is widely applied in areas such as Bitcoin and SSL/TLS certificates. The task requires understanding the signature generation and verification processes of ECDSA, including parameter definition, key generation, signature calculation, and verification logic.

1. Basic Concepts and Parameter Definitions
ECDSA relies on the mathematical structure of elliptic curves, requiring the pre-definition of the following public parameters:

• Elliptic Curve Equation: e.g., \(y^2 = x^3 + ax + b\) (operations are performed over a finite field).
• Base Point G: A generator point on the curve, publicly known.
• Order n: The order of the base point G (satisfying \(n \times G = O\), where O is the point at infinity).
• Private Key d: An integer randomly chosen by the user (\(1 \leq d \leq n-1\)).
• Public Key Q: Calculated from the private key, \(Q = d \times G\).

2. Signature Generation Process
Assume user A needs to sign a message \(m\):

1. Compute Message Hash: \(e = \text{HASH}(m)\), convert the hash value to an integer.
2. Generate Ephemeral Key: Randomly select an integer \(k\) (\(1 \leq k \leq n-1\)), which must be different for each signature.
3. Calculate Point R: Compute the curve point \(R = k \times G\), take the x-coordinate of R \(r = R_x \mod n\). If \(r=0\), choose a new k.
4. Calculate Signature s: \(s = k^{-1} (e + d \cdot r) \mod n\). Here, \(k^{-1}\) is the modular inverse of k modulo n.
5. Output Signature: Obtain the signature pair \((r, s)\).

Key Point: The ephemeral key k must be kept secret and must not be reused, otherwise the private key d could be compromised.

3. Signature Verification Process
After receiving the message \(m\) and the signature \((r, s)\), the verifier needs to confirm whether the signature was generated by the holder of the public key Q:

1. Check Range: Verify that \(r, s\) are within the interval \([1, n-1]\).
2. Compute Hash: \(e = \text{HASH}(m)\).
3. Calculate Intermediate Values:
   • \(w = s^{-1} \mod n\) (find the modular inverse of s).
   • \(u_1 = e \cdot w \mod n\)
   • \(u_2 = r \cdot w \mod n\)
4. Calculate Curve Point: \(P = u_1 \times G + u_2 \times Q\).
5. Verify Signature: If the x-coordinate of point P \(P_x \mod n = r\), then the signature is valid; otherwise, it is invalid.

Principle: During verification, if the signature is correct, point P should equal the ephemeral point R from the signing step. Because:

\[P = (e \cdot w) \times G + (r \cdot w) \times Q = w(e + r \cdot d) \times G = k \times G = R \]

4. Security Analysis

• Underlying Hard Problem: Security is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), i.e., given Q and G, it is computationally infeasible to derive the private key d.
• Important Notes: The randomness of k is crucial. If k is reused or predictable, an attacker can solve for the private key using two signatures (see "k reuse attack").

Summary
ECDSA achieves efficient and secure digital signatures through elliptic curve operations. Its core lies in the clever use of the ephemeral key k and modular inverse calculations, transforming private key verification into an equivalence check of curve points. Understanding its mathematical background and details is key to mastering this algorithm.