Split fe_set_b32 into reducing and normalizing variants

sipa commented at 10:21 pm on February 5, 2023: contributor

Follow-up to #1205.

This splits the secp256k1_fe_set_b32 function into two variants:

secp256k1_fe_set_b32_mod, which returns void, reduces modulo the curve order, and only promises weakly normalized output.
secp256k1_fe_set_b32_limit, which returns int indicating success/failure, and only promises valid output in case the input is in range (but guarantees it’s strongly normalized in this case).

This removes one of the few cases in the codebase where normalization status depends on runtime values, making it fixed at compile-time instead.

sipa force-pushed on Feb 5, 2023

in src/field_10x26_impl.h:409 in 21c5b28998 outdated

383+        r->magnitude = 1;
384+        r->normalized = 1;
385+        secp256k1_fe_verify(r);
386+    } else {
387+        r->n[4] ^= 1; /* change value, hopefully triggering errors if the value is used. */
388+    }

real-or-random commented at 8:56 am on February 6, 2023:

Perhaps we should instead make sure that we call secp256k1_fe_verify on every entry of a function that reads a fe? We do it in some functions but not in all. For instance, t’s missing in secp256k1_fe_mul_int.

sipa commented at 3:49 pm on February 6, 2023:

Done. I’ve changed this to set the magnitude to -1 in this invalid path, which should be detected if the output fe is ever fed as input to another function. In an additional commit I’ve also added more secp256k1_fe_verify checks.

in src/field.h:79 in 21c5b28998 outdated

74@@ -75,10 +75,14 @@ static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b);
75 /** Compare two field elements. Requires both inputs to be normalized */
76 static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b);
77 
78-/** Set a field element equal to 32-byte big endian value.
79- *  Returns 1 if no overflow occurred, and then the output is normalized.
80- *  Returns 0 if overflow occurred, and then the output is only weakly normalized. */
81-static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a);
82+/** Set a field element equal to 32-byte big endian value, reducing modulo the curve
83+ *  order if need be. The output is weakly normalized. */

real-or-random commented at 8:57 am on February 6, 2023:

nit: s/if need be/if necessary is simpler English

sipa commented at 3:48 pm on February 6, 2023:

Fixed.

real-or-random commented at 8:58 am on February 6, 2023: contributor

Concept ACK

Not sure what’s wrong with CI. Some tasks show red (exit code 134) though all tests have passed. I restarted those.

real-or-random commented at 9:03 am on February 6, 2023: contributor

Not sure what’s wrong with CI. Some tasks show red (exit code 134) though all tests have passed. I restarted those.

Oh, these are the new -DVERIFY tests, so they fail in the benchmark (see bench.log). It’s hard to see from the CI output. We should perhabs reconsider that cat to .log thing.

sipa force-pushed on Feb 6, 2023

sipa force-pushed on May 11, 2023

sipa commented at 1:00 pm on May 11, 2023: contributor

Rebased on top of (and simplified significantly as a result of) #1066.

sipa force-pushed on May 11, 2023

real-or-random commented at 1:33 pm on May 11, 2023: contributor

A variant of the commit has been merged as part of #1205, so it should be removed.

real-or-random approved

real-or-random commented at 3:22 pm on May 11, 2023: contributor

ACK 47bfc0a934c36e9fe1446f583789de6399bdd81d

in src/field.h:204 in 47bfc0a934 outdated

204  *
205- * Note that this function is unusual in that the normalization of the output depends on the
206- * run-time value of a.
207+ * On input, r does not need to be initalized. a must be a pointer to an initialized 32-byte array.
208+ * On output, r = a if (a < p), it will be normalized with magnitude 1, and 1 is returned.
209+ * If a >= 0, 0 is returned, and r will be made invalid (and cannot be used without overwriting).

jonasnick commented at 5:39 pm on May 11, 2023:

Should be “if a >= p”?

sipa commented at 5:50 pm on May 11, 2023:

You’re ruining all the fun. This function would be so much simpler to implement otherwise.

Fixed.

jonasnick commented at 5:46 pm on May 11, 2023: contributor

Concept ACK

Split fe_set_b32 into reducing and normalizing variants 5b32602295

sipa force-pushed on May 11, 2023

real-or-random approved

real-or-random commented at 5:51 pm on May 11, 2023: contributor

ACK 5b32602295ff7ad9e1973f96b8ee8344b82f4af0

jonasnick approved

jonasnick commented at 5:51 pm on May 11, 2023: contributor

ACK 5b32602295ff7ad9e1973f96b8ee8344b82f4af0

sipa merged this on May 11, 2023

sipa closed this on May 11, 2023

sipa cross-referenced this on May 12, 2023 from issue ElligatorSwift + integrated x-only DH by sipa

sipa referenced this in commit b4eb644b6c on May 12, 2023

hebasto referenced this in commit 49c52ea2b1 on May 13, 2023

sipa cross-referenced this on May 15, 2023 from issue Make fe magnitude implied statically by real-or-random

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

sipa referenced this in commit 901336eee7 on Jun 21, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023

jonasnick cross-referenced this on Jul 24, 2023 from issue Upstream PRs 1268, 1276, 1267, 1265, 1230, 1279, 1273, 1263, 1231, 1285, 1283, 1205, 1286, 1275, 1234, 1239, 1240, 1284, 1277, 1289, 1270, 1296, 1301, 1299, 1066, 1300, 1292, 1305, 1303, 1133, 1306, 1207, 1304, 1307, 1311, 1309, 1312 by jonasnick

Split fe_set_b32 into reducing and normalizing variants #1207