Skip to content

secp256k1_fe_set_b32_mod doesn't actually reduce anything #1453

New issue
New issue
Closed
Closed
secp256k1_fe_set_b32_mod doesn't actually reduce anything#1453
Labels
tweak/refactor
@Coding-Enthusiast

Description

@Coding-Enthusiast
Coding-Enthusiast
opened on Dec 6, 2023

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    tweak/refactor

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions