An elliptic-curve point is a coordinate pair (x, y) that satisfies the curve equation. In DUAL_EC_DRBG, scalar multiplication transforms such points and makes generator points central to the attack. section 3.2.4
The implementation treats a candidate point defensively:
- Compute y from x using y² = x³ + ax + b. section 3.2.4
- Reject x values without a modular square root. section 3.2.4
- Verify y² matches the curve expression and confirm the point lies on P-256. section 3.2.4
Recovering a hidden point
An observed DUAL_EC_DRBG output contains a truncated x-coordinate. An attacker guesses the missing bytes, reconstructs possible y-coordinates, and tests each candidate through scalar multiplication until the next output matches. section 3.2.4
Equation 3.7
\[\begin{aligned} \begin{aligned} y^2 = x^3 + ax + b \\ y = \sqrt{x^3 + ax + b} \end{aligned} \label{equation:elliptic-curves-2} \end{aligned}\]Use the curve equation to connect an x-coordinate with its possible y-coordinates. section 3.2.4
