← Watch feed
Merge bitcoin-core/secp256k1#1949: ecdsa: Clarify derivation of the r check in `_sig_verify`
Public commit record
93/100 · Strong
What the developer wrote
Authored by merge-script
Merge bitcoin-core/secp256k1#1949: ecdsa: Clarify derivation of the r check in `_sig_verify`
93987567a1bf2bb5d3ea1492c286cd2b5a76f544 ecdsa: Clarify derivation of the r check in `_sig_verify` (Tim Ruffing)
Pull request description:
Introduce the `xr + n < p` condition in the step where it is needed, namely right before switching from integer equality to equality modulo p, and explain why it is required there. Write congruences as `a == b (mod m)`, because `a mod p == b` reads as if `mod p` were an operator applied to the left-hand side only.
Also reword the comment at the `p - n` check: the check is needed for correctness, not merely an optimization.
Made these improvements when trying to understand the background of #1948.
ACKs for top commit:
theStack:
re-ACK 93987567a1bf2bb5d3ea1492c286cd2b5a76f544
Tree-SHA512: 162508706fdb3c912c71de5935f276f24ed31c62620eee513896c4058327a697f3c9f9250634d65bcd1687a716f0347e8775b3382dade5ea77ede17759e70ad4
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Explains rationale or failure mode✓ Links an issue, advisory, or supporting reference
What changed, and why it matters
This commit only rewrites comments in the source code to make the mathematical explanation clearer. It does not change any actual code instructions, function behavior, or security properties. There is no vulnerability or fix here.
Recommended action
No action required. This is a non-functional comment cleanup.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The patch is a documentation-only change in src/ecdsa_impl.h within secp256k1_ecdsa_sig_verify. It rewords the derivation of why the ECDSA signature verification checks both xr and xr+n against the recomputed R x-coordinate, and clarifies that the p - n comparison is a correctness requirement, not merely an optimization. No executable logic, conditions, or arithmetic operations are modified.
Changed components
src/ecdsa_impl.hInspect captured patch +21 / −15
### src/ecdsa_impl.h
@@ -238,33 +238,39 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_scalar *sigr, const secp25
(void)range;
#endif
- /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
- * in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
- * compute the remainder modulo n, and compare it to xr. However:
+ /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n) in xr.
+ * Naively, we would extract pr's x-coordinate X(pr) (requiring an inversion modulo p), and
+ * check whether the congruence xr === X(pr) (mod n) holds. However, we can do better:
*
- * xr == X(pr) mod n
- * <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
- * [Since 2 * n > p, h can only be 0 or 1]
- * <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
- * [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
- * <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
- * [Multiplying both sides of the equations by pr.z^2 mod p]
- * <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
+ * xr === X(pr) (mod n)
+ * <=> exists h. xr + h * n == X(pr)
+ * [Since 2 * n > p, h can only be 0 or 1:]
+ * <=> xr == X(pr) || xr + n == X(pr)
+ * [Since X(pr) < p, the second equality implies xr + n < p:]
+ * <=> xr == X(pr) || (xr + n < p && xr + n == X(pr))
+ * [Both sides of each equality are in [0, p), so it is equivalent to consider the
+ * congruences modulo p instead:]
+ * <=> xr === X(pr) (mod p) || (xr + n < p && xr + n === X(pr) (mod p))
+ * [In Jacobian coordinates, X(pr) is pr.x / pr.z^2:]
+ * <=> xr === pr.x / pr.z^2 (mod p)) || (xr + n < p && xr + n === pr.x / pr.z^2 (mod p))
+ * [Multiplying both sides of the congruences by pr.z^2 (which is nonzero modulo p because
+ * the point pr is not infinity) gives:]
+ * <=> xr * pr.z^2 === pr.x (mod p) || (xr + n < p && (xr + n) * pr.z^2 === pr.x (mod p))
*
* Thus, we can avoid the inversion, but we have to check both cases separately.
- * secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
+ * secp256k1_gej_eq_x implements the (xr * pr.z^2 === pr.x (mod p)) test.
*/
if (secp256k1_gej_eq_x_var(&xr, &pr)) {
- /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */
+ /* xr * pr.z^2 === pr.x (mod p), so the signature is valid. */
return 1;
}
if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
- /* xr + n >= p, so we can skip testing the second case. */
+ /* xr + n >= p, so the second case cannot hold. */
return 0;
}
secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
if (secp256k1_gej_eq_x_var(&xr, &pr)) {
- /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
+ /* (xr + n) * pr.z^2 === pr.x (mod p), so the signature is valid. */
return 1;
}
return 0;Risk score
Our methodology →Why this scored 15/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.