secp256k1_fe_set_b32_mod doesn't actually reduce anything

[Coding-Enthusiast]

secp256k1_fe_set_b32_mod method name and comment suggest that it reduces the value mod p and the result is supposed to be r ≡ a (mod p)

secp256k1/src/field.h

Lines 187 to 192 in d3e29db

	/** Set a field element equal to a provided 32-byte big endian value, reducing it.
	*
	* On input, r does not need to be initialized. a must be a pointer to an initialized 32-byte array.
	* On output, r = a (mod p). It will have magnitude 1, and not be normalized.
	*/
	static void secp256k1_fe_set_b32_mod(secp256k1_fe *r, const unsigned char *a);

However looking at the implementations they don't actually perform any reduction. It's just a simple conversion from byte[] to uint[] in radix 26 or 52.

secp256k1/src/field_impl.h

Lines 270 to 277 in d3e29db

	static void secp256k1_fe_impl_set_b32_mod(secp256k1_fe *r, const unsigned char *a);
	SECP256K1_INLINE static void secp256k1_fe_set_b32_mod(secp256k1_fe *r, const unsigned char *a) {
	secp256k1_fe_impl_set_b32_mod(r, a);
	r->magnitude = 1;
	r->normalized = 0;
	SECP256K1_FE_VERIFY(r);
	}

secp256k1/src/field_10x26_impl.h

Lines 293 to 304 in d3e29db

	static void secp256k1_fe_impl_set_b32_mod(secp256k1_fe *r, const unsigned char *a) {
	r->n[0] = (uint32_t)a[31] | ((uint32_t)a[30] << 8) | ((uint32_t)a[29] << 16) | ((uint32_t)(a[28] & 0x3) << 24);
	r->n[1] = (uint32_t)((a[28] >> 2) & 0x3f) | ((uint32_t)a[27] << 6) | ((uint32_t)a[26] << 14) | ((uint32_t)(a[25] & 0xf) << 22);
	r->n[2] = (uint32_t)((a[25] >> 4) & 0xf) | ((uint32_t)a[24] << 4) | ((uint32_t)a[23] << 12) | ((uint32_t)(a[22] & 0x3f) << 20);
	r->n[3] = (uint32_t)((a[22] >> 6) & 0x3) | ((uint32_t)a[21] << 2) | ((uint32_t)a[20] << 10) | ((uint32_t)a[19] << 18);
	r->n[4] = (uint32_t)a[18] | ((uint32_t)a[17] << 8) | ((uint32_t)a[16] << 16) | ((uint32_t)(a[15] & 0x3) << 24);
	r->n[5] = (uint32_t)((a[15] >> 2) & 0x3f) | ((uint32_t)a[14] << 6) | ((uint32_t)a[13] << 14) | ((uint32_t)(a[12] & 0xf) << 22);
	r->n[6] = (uint32_t)((a[12] >> 4) & 0xf) | ((uint32_t)a[11] << 4) | ((uint32_t)a[10] << 12) | ((uint32_t)(a[9] & 0x3f) << 20);
	r->n[7] = (uint32_t)((a[9] >> 6) & 0x3) | ((uint32_t)a[8] << 2) | ((uint32_t)a[7] << 10) | ((uint32_t)a[6] << 18);
	r->n[8] = (uint32_t)a[5] | ((uint32_t)a[4] << 8) | ((uint32_t)a[3] << 16) | ((uint32_t)(a[2] & 0x3) << 24);
	r->n[9] = (uint32_t)((a[2] >> 2) & 0x3f) | ((uint32_t)a[1] << 6) | ((uint32_t)a[0] << 14);
	}

secp256k1/src/field_5x52_impl.h

Lines 235 to 270 in d3e29db

	static void secp256k1_fe_impl_set_b32_mod(secp256k1_fe *r, const unsigned char *a) {
	r->n[0] = (uint64_t)a[31]
	| ((uint64_t)a[30] << 8)
	| ((uint64_t)a[29] << 16)
	| ((uint64_t)a[28] << 24)
	| ((uint64_t)a[27] << 32)
	| ((uint64_t)a[26] << 40)
	| ((uint64_t)(a[25] & 0xF) << 48);
	r->n[1] = (uint64_t)((a[25] >> 4) & 0xF)
	| ((uint64_t)a[24] << 4)
	| ((uint64_t)a[23] << 12)
	| ((uint64_t)a[22] << 20)
	| ((uint64_t)a[21] << 28)
	| ((uint64_t)a[20] << 36)
	| ((uint64_t)a[19] << 44);
	r->n[2] = (uint64_t)a[18]
	| ((uint64_t)a[17] << 8)
	| ((uint64_t)a[16] << 16)
	| ((uint64_t)a[15] << 24)
	| ((uint64_t)a[14] << 32)
	| ((uint64_t)a[13] << 40)
	| ((uint64_t)(a[12] & 0xF) << 48);
	r->n[3] = (uint64_t)((a[12] >> 4) & 0xF)
	| ((uint64_t)a[11] << 4)
	| ((uint64_t)a[10] << 12)
	| ((uint64_t)a[9] << 20)
	| ((uint64_t)a[8] << 28)
	| ((uint64_t)a[7] << 36)
	| ((uint64_t)a[6] << 44);
	r->n[4] = (uint64_t)a[5]
	| ((uint64_t)a[4] << 8)
	| ((uint64_t)a[3] << 16)
	| ((uint64_t)a[2] << 24)
	| ((uint64_t)a[1] << 32)
	| ((uint64_t)a[0] << 40);
	}

After this change the old method (secp256k1_fe_set_b32_limit) is still used in most places except something like this
5b32602#diff-6f71b0372be086d45b4f2740508c03a21835d87008840032fbb767f419fd988a
And it just assumes secp256k1_fe_set_b32_mod reduces the result while it doesn't.

@sipa

[sipa]

You're right that the function secp256k1_fe_set_b32_mod itself doesn't perform any modular reductions. But it doesn't need to: the secp256k1_fe type itself does: all operations on secp255k1_fe automatically perform reductions when the integer used to represent it overflows too much.

In short, secp256k1_fe can only represent elements of the finite field "integers modulo p". It encapsulates an integer, and that integer can (within certain bounds) exceed p, but the actual integer is hidden by the abstraction: none of the functions operating on the type let you observe the integer.

So the only difference between secp256k1_fe_set_b32_mod and secp256k1_fe_set_b32_limit is that the latter detects and fails if the input exceeds p, but then in return gives a stronger guarantee on how normalized (basically, how small the integers inside is guaranteed to be) the resulting field element is.

[Coding-Enthusiast]

So the only difference between secp256k1_fe_set_b32_mod and secp256k1_fe_set_b32_limit is that the latter detects and fails if the input exceeds p

Wouldn't it be better to rename the methods to something like _set_b32 and set_b32_check?

[real-or-random]

Well, bike shedding is always possible, but I think the names are okay. If anything, limit is more precise than check, and mod is more precise than the empty string.

Perhaps the docs can be marginally improved. I see that this can be misleading.

Set a field element equal to a provided 32-byte big endian value, reducing it.

It's more like this:
"Set a field element equal to the element represented by a provided 32-byte big endian value interpreted modulo p."

And the other one:

Set a field element equal to a provided 32-byte big endian value, checking for overflow.

Perhaps:
"Set a field element equal to a provided 32-byte big endian value in [0..p-1]."

[real-or-random]

@Coding-Enthusiast I'd be happy to review a PR which implements (variants of) these suggestions.