Page Menu
Home
Phabricator
Search
Configure Global Search
Log In
Files
F12910267
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Flag For Later
Size
87 KB
Subscribers
None
View Options
diff --git a/src/secp256k1/src/field_10x26.h b/src/secp256k1/src/field_10x26.h
index 727c5267fb..5ff03c8abc 100644
--- a/src/secp256k1/src/field_10x26.h
+++ b/src/secp256k1/src/field_10x26.h
@@ -1,48 +1,50 @@
/**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
#ifndef SECP256K1_FIELD_REPR_H
#define SECP256K1_FIELD_REPR_H
#include <stdint.h>
typedef struct {
- /* X = sum(i=0..9, elem[i]*2^26) mod n */
+ /* X = sum(i=0..9, n[i]*2^(i*26)) mod p
+ * where p = 2^256 - 0x1000003D1
+ */
uint32_t n[10];
#ifdef VERIFY
int magnitude;
int normalized;
#endif
} secp256k1_fe;
/* Unpacks a constant into a overlapping multi-limbed FE element. */
#define SECP256K1_FE_CONST_INNER(d7, d6, d5, d4, d3, d2, d1, d0) { \
(d0) & 0x3FFFFFFUL, \
(((uint32_t)d0) >> 26) | (((uint32_t)(d1) & 0xFFFFFUL) << 6), \
(((uint32_t)d1) >> 20) | (((uint32_t)(d2) & 0x3FFFUL) << 12), \
(((uint32_t)d2) >> 14) | (((uint32_t)(d3) & 0xFFUL) << 18), \
(((uint32_t)d3) >> 8) | (((uint32_t)(d4) & 0x3UL) << 24), \
(((uint32_t)d4) >> 2) & 0x3FFFFFFUL, \
(((uint32_t)d4) >> 28) | (((uint32_t)(d5) & 0x3FFFFFUL) << 4), \
(((uint32_t)d5) >> 22) | (((uint32_t)(d6) & 0xFFFFUL) << 10), \
(((uint32_t)d6) >> 16) | (((uint32_t)(d7) & 0x3FFUL) << 16), \
(((uint32_t)d7) >> 10) \
}
#ifdef VERIFY
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)), 1, 1}
#else
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0))}
#endif
typedef struct {
uint32_t n[8];
} secp256k1_fe_storage;
#define SECP256K1_FE_STORAGE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {{ (d0), (d1), (d2), (d3), (d4), (d5), (d6), (d7) }}
#define SECP256K1_FE_STORAGE_CONST_GET(d) d.n[7], d.n[6], d.n[5], d.n[4],d.n[3], d.n[2], d.n[1], d.n[0]
#endif /* SECP256K1_FIELD_REPR_H */
diff --git a/src/secp256k1/src/field_10x26_impl.h b/src/secp256k1/src/field_10x26_impl.h
index 94f8132fc8..4ae4fdcec8 100644
--- a/src/secp256k1/src/field_10x26_impl.h
+++ b/src/secp256k1/src/field_10x26_impl.h
@@ -1,1161 +1,1162 @@
/**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
#ifndef SECP256K1_FIELD_REPR_IMPL_H
#define SECP256K1_FIELD_REPR_IMPL_H
#include "util.h"
-#include "num.h"
#include "field.h"
#ifdef VERIFY
static void secp256k1_fe_verify(const secp256k1_fe *a) {
const uint32_t *d = a->n;
int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
r &= (d[0] <= 0x3FFFFFFUL * m);
r &= (d[1] <= 0x3FFFFFFUL * m);
r &= (d[2] <= 0x3FFFFFFUL * m);
r &= (d[3] <= 0x3FFFFFFUL * m);
r &= (d[4] <= 0x3FFFFFFUL * m);
r &= (d[5] <= 0x3FFFFFFUL * m);
r &= (d[6] <= 0x3FFFFFFUL * m);
r &= (d[7] <= 0x3FFFFFFUL * m);
r &= (d[8] <= 0x3FFFFFFUL * m);
r &= (d[9] <= 0x03FFFFFUL * m);
r &= (a->magnitude >= 0);
r &= (a->magnitude <= 32);
if (a->normalized) {
r &= (a->magnitude <= 1);
if (r && (d[9] == 0x03FFFFFUL)) {
uint32_t mid = d[8] & d[7] & d[6] & d[5] & d[4] & d[3] & d[2];
if (mid == 0x3FFFFFFUL) {
r &= ((d[1] + 0x40UL + ((d[0] + 0x3D1UL) >> 26)) <= 0x3FFFFFFUL);
}
}
}
VERIFY_CHECK(r == 1);
}
#endif
static void secp256k1_fe_normalize(secp256k1_fe *r) {
uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
/* Reduce t9 at the start so there will be at most a single carry from the first pass */
uint32_t m;
uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x3D1UL; t1 += (x << 6);
t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; m = t2;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; m &= t3;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; m &= t4;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; m &= t5;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; m &= t6;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; m &= t7;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; m &= t8;
/* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t9 >> 23 == 0);
/* At most a single final reduction is needed; check if the value is >= the field characteristic */
x = (t9 >> 22) | ((t9 == 0x03FFFFFUL) & (m == 0x3FFFFFFUL)
& ((t1 + 0x40UL + ((t0 + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
/* Apply the final reduction (for constant-time behaviour, we do it always) */
t0 += x * 0x3D1UL; t1 += (x << 6);
t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
/* If t9 didn't carry to bit 22 already, then it should have after any final reduction */
VERIFY_CHECK(t9 >> 22 == x);
/* Mask off the possible multiple of 2^256 from the final reduction */
t9 &= 0x03FFFFFUL;
r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_normalize_weak(secp256k1_fe *r) {
uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
/* Reduce t9 at the start so there will be at most a single carry from the first pass */
uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x3D1UL; t1 += (x << 6);
t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
/* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t9 >> 23 == 0);
r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
#ifdef VERIFY
r->magnitude = 1;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_normalize_var(secp256k1_fe *r) {
uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
/* Reduce t9 at the start so there will be at most a single carry from the first pass */
uint32_t m;
uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x3D1UL; t1 += (x << 6);
t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; m = t2;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; m &= t3;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; m &= t4;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; m &= t5;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; m &= t6;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; m &= t7;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; m &= t8;
/* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t9 >> 23 == 0);
/* At most a single final reduction is needed; check if the value is >= the field characteristic */
x = (t9 >> 22) | ((t9 == 0x03FFFFFUL) & (m == 0x3FFFFFFUL)
& ((t1 + 0x40UL + ((t0 + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
if (x) {
t0 += 0x3D1UL; t1 += (x << 6);
t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
/* If t9 didn't carry to bit 22 already, then it should have after any final reduction */
VERIFY_CHECK(t9 >> 22 == x);
/* Mask off the possible multiple of 2^256 from the final reduction */
t9 &= 0x03FFFFFUL;
}
r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
}
static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r) {
uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
/* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
uint32_t z0, z1;
/* Reduce t9 at the start so there will be at most a single carry from the first pass */
uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x3D1UL; t1 += (x << 6);
t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL; z0 = t0; z1 = t0 ^ 0x3D0UL;
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL; z0 |= t1; z1 &= t1 ^ 0x40UL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; z0 |= t2; z1 &= t2;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; z0 |= t3; z1 &= t3;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; z0 |= t4; z1 &= t4;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; z0 |= t5; z1 &= t5;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; z0 |= t6; z1 &= t6;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; z0 |= t7; z1 &= t7;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; z0 |= t8; z1 &= t8;
z0 |= t9; z1 &= t9 ^ 0x3C00000UL;
/* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t9 >> 23 == 0);
return (z0 == 0) | (z1 == 0x3FFFFFFUL);
}
static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r) {
uint32_t t0, t1, t2, t3, t4, t5, t6, t7, t8, t9;
uint32_t z0, z1;
uint32_t x;
t0 = r->n[0];
t9 = r->n[9];
/* Reduce t9 at the start so there will be at most a single carry from the first pass */
x = t9 >> 22;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x3D1UL;
/* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
z0 = t0 & 0x3FFFFFFUL;
z1 = z0 ^ 0x3D0UL;
/* Fast return path should catch the majority of cases */
if ((z0 != 0UL) & (z1 != 0x3FFFFFFUL)) {
return 0;
}
t1 = r->n[1];
t2 = r->n[2];
t3 = r->n[3];
t4 = r->n[4];
t5 = r->n[5];
t6 = r->n[6];
t7 = r->n[7];
t8 = r->n[8];
t9 &= 0x03FFFFFUL;
t1 += (x << 6);
t1 += (t0 >> 26);
t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL; z0 |= t1; z1 &= t1 ^ 0x40UL;
t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; z0 |= t2; z1 &= t2;
t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; z0 |= t3; z1 &= t3;
t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; z0 |= t4; z1 &= t4;
t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; z0 |= t5; z1 &= t5;
t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; z0 |= t6; z1 &= t6;
t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; z0 |= t7; z1 &= t7;
t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; z0 |= t8; z1 &= t8;
z0 |= t9; z1 &= t9 ^ 0x3C00000UL;
/* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t9 >> 23 == 0);
return (z0 == 0) | (z1 == 0x3FFFFFFUL);
}
SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe *r, int a) {
r->n[0] = a;
r->n[1] = r->n[2] = r->n[3] = r->n[4] = r->n[5] = r->n[6] = r->n[7] = r->n[8] = r->n[9] = 0;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
}
SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe *a) {
const uint32_t *t = a->n;
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
secp256k1_fe_verify(a);
#endif
return (t[0] | t[1] | t[2] | t[3] | t[4] | t[5] | t[6] | t[7] | t[8] | t[9]) == 0;
}
SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
secp256k1_fe_verify(a);
#endif
return a->n[0] & 1;
}
SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe *a) {
int i;
#ifdef VERIFY
a->magnitude = 0;
a->normalized = 1;
#endif
for (i=0; i<10; i++) {
a->n[i] = 0;
}
}
static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) {
int i;
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
VERIFY_CHECK(b->normalized);
secp256k1_fe_verify(a);
secp256k1_fe_verify(b);
#endif
for (i = 9; i >= 0; i--) {
if (a->n[i] > b->n[i]) {
return 1;
}
if (a->n[i] < b->n[i]) {
return -1;
}
}
return 0;
}
static int secp256k1_fe_set_b32(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);
if (r->n[9] == 0x3FFFFFUL && (r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL && (r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL) {
return 0;
}
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
return 1;
}
/** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
secp256k1_fe_verify(a);
#endif
r[0] = (a->n[9] >> 14) & 0xff;
r[1] = (a->n[9] >> 6) & 0xff;
r[2] = ((a->n[9] & 0x3F) << 2) | ((a->n[8] >> 24) & 0x3);
r[3] = (a->n[8] >> 16) & 0xff;
r[4] = (a->n[8] >> 8) & 0xff;
r[5] = a->n[8] & 0xff;
r[6] = (a->n[7] >> 18) & 0xff;
r[7] = (a->n[7] >> 10) & 0xff;
r[8] = (a->n[7] >> 2) & 0xff;
r[9] = ((a->n[7] & 0x3) << 6) | ((a->n[6] >> 20) & 0x3f);
r[10] = (a->n[6] >> 12) & 0xff;
r[11] = (a->n[6] >> 4) & 0xff;
r[12] = ((a->n[6] & 0xf) << 4) | ((a->n[5] >> 22) & 0xf);
r[13] = (a->n[5] >> 14) & 0xff;
r[14] = (a->n[5] >> 6) & 0xff;
r[15] = ((a->n[5] & 0x3f) << 2) | ((a->n[4] >> 24) & 0x3);
r[16] = (a->n[4] >> 16) & 0xff;
r[17] = (a->n[4] >> 8) & 0xff;
r[18] = a->n[4] & 0xff;
r[19] = (a->n[3] >> 18) & 0xff;
r[20] = (a->n[3] >> 10) & 0xff;
r[21] = (a->n[3] >> 2) & 0xff;
r[22] = ((a->n[3] & 0x3) << 6) | ((a->n[2] >> 20) & 0x3f);
r[23] = (a->n[2] >> 12) & 0xff;
r[24] = (a->n[2] >> 4) & 0xff;
r[25] = ((a->n[2] & 0xf) << 4) | ((a->n[1] >> 22) & 0xf);
r[26] = (a->n[1] >> 14) & 0xff;
r[27] = (a->n[1] >> 6) & 0xff;
r[28] = ((a->n[1] & 0x3f) << 2) | ((a->n[0] >> 24) & 0x3);
r[29] = (a->n[0] >> 16) & 0xff;
r[30] = (a->n[0] >> 8) & 0xff;
r[31] = a->n[0] & 0xff;
}
SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
#ifdef VERIFY
VERIFY_CHECK(a->magnitude <= m);
secp256k1_fe_verify(a);
#endif
r->n[0] = 0x3FFFC2FUL * 2 * (m + 1) - a->n[0];
r->n[1] = 0x3FFFFBFUL * 2 * (m + 1) - a->n[1];
r->n[2] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[2];
r->n[3] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[3];
r->n[4] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[4];
r->n[5] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[5];
r->n[6] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[6];
r->n[7] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[7];
r->n[8] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[8];
r->n[9] = 0x03FFFFFUL * 2 * (m + 1) - a->n[9];
#ifdef VERIFY
r->magnitude = m + 1;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe *r, int a) {
r->n[0] *= a;
r->n[1] *= a;
r->n[2] *= a;
r->n[3] *= a;
r->n[4] *= a;
r->n[5] *= a;
r->n[6] *= a;
r->n[7] *= a;
r->n[8] *= a;
r->n[9] *= a;
#ifdef VERIFY
r->magnitude *= a;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a) {
#ifdef VERIFY
secp256k1_fe_verify(a);
#endif
r->n[0] += a->n[0];
r->n[1] += a->n[1];
r->n[2] += a->n[2];
r->n[3] += a->n[3];
r->n[4] += a->n[4];
r->n[5] += a->n[5];
r->n[6] += a->n[6];
r->n[7] += a->n[7];
r->n[8] += a->n[8];
r->n[9] += a->n[9];
#ifdef VERIFY
r->magnitude += a->magnitude;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
#if defined(USE_EXTERNAL_ASM)
/* External assembler implementation */
void secp256k1_fe_mul_inner(uint32_t *r, const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b);
void secp256k1_fe_sqr_inner(uint32_t *r, const uint32_t *a);
#else
#ifdef VERIFY
#define VERIFY_BITS(x, n) VERIFY_CHECK(((x) >> (n)) == 0)
#else
#define VERIFY_BITS(x, n) do { } while(0)
#endif
SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint32_t *r, const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b) {
uint64_t c, d;
uint64_t u0, u1, u2, u3, u4, u5, u6, u7, u8;
uint32_t t9, t1, t0, t2, t3, t4, t5, t6, t7;
const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
VERIFY_BITS(a[0], 30);
VERIFY_BITS(a[1], 30);
VERIFY_BITS(a[2], 30);
VERIFY_BITS(a[3], 30);
VERIFY_BITS(a[4], 30);
VERIFY_BITS(a[5], 30);
VERIFY_BITS(a[6], 30);
VERIFY_BITS(a[7], 30);
VERIFY_BITS(a[8], 30);
VERIFY_BITS(a[9], 26);
VERIFY_BITS(b[0], 30);
VERIFY_BITS(b[1], 30);
VERIFY_BITS(b[2], 30);
VERIFY_BITS(b[3], 30);
VERIFY_BITS(b[4], 30);
VERIFY_BITS(b[5], 30);
VERIFY_BITS(b[6], 30);
VERIFY_BITS(b[7], 30);
VERIFY_BITS(b[8], 30);
VERIFY_BITS(b[9], 26);
/** [... a b c] is a shorthand for ... + a<<52 + b<<26 + c<<0 mod n.
- * px is a shorthand for sum(a[i]*b[x-i], i=0..x).
+ * for 0 <= x <= 9, px is a shorthand for sum(a[i]*b[x-i], i=0..x).
+ * for 9 <= x <= 18, px is a shorthand for sum(a[i]*b[x-i], i=(x-9)..9)
* Note that [x 0 0 0 0 0 0 0 0 0 0] = [x*R1 x*R0].
*/
d = (uint64_t)a[0] * b[9]
+ (uint64_t)a[1] * b[8]
+ (uint64_t)a[2] * b[7]
+ (uint64_t)a[3] * b[6]
+ (uint64_t)a[4] * b[5]
+ (uint64_t)a[5] * b[4]
+ (uint64_t)a[6] * b[3]
+ (uint64_t)a[7] * b[2]
+ (uint64_t)a[8] * b[1]
+ (uint64_t)a[9] * b[0];
/* VERIFY_BITS(d, 64); */
/* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
t9 = d & M; d >>= 26;
VERIFY_BITS(t9, 26);
VERIFY_BITS(d, 38);
/* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
c = (uint64_t)a[0] * b[0];
VERIFY_BITS(c, 60);
/* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
d += (uint64_t)a[1] * b[9]
+ (uint64_t)a[2] * b[8]
+ (uint64_t)a[3] * b[7]
+ (uint64_t)a[4] * b[6]
+ (uint64_t)a[5] * b[5]
+ (uint64_t)a[6] * b[4]
+ (uint64_t)a[7] * b[3]
+ (uint64_t)a[8] * b[2]
+ (uint64_t)a[9] * b[1];
VERIFY_BITS(d, 63);
/* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
u0 = d & M; d >>= 26; c += u0 * R0;
VERIFY_BITS(u0, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 61);
/* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
t0 = c & M; c >>= 26; c += u0 * R1;
VERIFY_BITS(t0, 26);
VERIFY_BITS(c, 37);
/* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
c += (uint64_t)a[0] * b[1]
+ (uint64_t)a[1] * b[0];
VERIFY_BITS(c, 62);
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
d += (uint64_t)a[2] * b[9]
+ (uint64_t)a[3] * b[8]
+ (uint64_t)a[4] * b[7]
+ (uint64_t)a[5] * b[6]
+ (uint64_t)a[6] * b[5]
+ (uint64_t)a[7] * b[4]
+ (uint64_t)a[8] * b[3]
+ (uint64_t)a[9] * b[2];
VERIFY_BITS(d, 63);
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
u1 = d & M; d >>= 26; c += u1 * R0;
VERIFY_BITS(u1, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 63);
/* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
t1 = c & M; c >>= 26; c += u1 * R1;
VERIFY_BITS(t1, 26);
VERIFY_BITS(c, 38);
/* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
c += (uint64_t)a[0] * b[2]
+ (uint64_t)a[1] * b[1]
+ (uint64_t)a[2] * b[0];
VERIFY_BITS(c, 62);
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
d += (uint64_t)a[3] * b[9]
+ (uint64_t)a[4] * b[8]
+ (uint64_t)a[5] * b[7]
+ (uint64_t)a[6] * b[6]
+ (uint64_t)a[7] * b[5]
+ (uint64_t)a[8] * b[4]
+ (uint64_t)a[9] * b[3];
VERIFY_BITS(d, 63);
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
u2 = d & M; d >>= 26; c += u2 * R0;
VERIFY_BITS(u2, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 63);
/* [d u2 0 0 t9 0 0 0 0 0 0 c-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
t2 = c & M; c >>= 26; c += u2 * R1;
VERIFY_BITS(t2, 26);
VERIFY_BITS(c, 38);
/* [d u2 0 0 t9 0 0 0 0 0 c-u2*R1 t2-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
/* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
c += (uint64_t)a[0] * b[3]
+ (uint64_t)a[1] * b[2]
+ (uint64_t)a[2] * b[1]
+ (uint64_t)a[3] * b[0];
VERIFY_BITS(c, 63);
/* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
d += (uint64_t)a[4] * b[9]
+ (uint64_t)a[5] * b[8]
+ (uint64_t)a[6] * b[7]
+ (uint64_t)a[7] * b[6]
+ (uint64_t)a[8] * b[5]
+ (uint64_t)a[9] * b[4];
VERIFY_BITS(d, 63);
/* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
u3 = d & M; d >>= 26; c += u3 * R0;
VERIFY_BITS(u3, 26);
VERIFY_BITS(d, 37);
/* VERIFY_BITS(c, 64); */
/* [d u3 0 0 0 t9 0 0 0 0 0 c-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
t3 = c & M; c >>= 26; c += u3 * R1;
VERIFY_BITS(t3, 26);
VERIFY_BITS(c, 39);
/* [d u3 0 0 0 t9 0 0 0 0 c-u3*R1 t3-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
/* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
c += (uint64_t)a[0] * b[4]
+ (uint64_t)a[1] * b[3]
+ (uint64_t)a[2] * b[2]
+ (uint64_t)a[3] * b[1]
+ (uint64_t)a[4] * b[0];
VERIFY_BITS(c, 63);
/* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
d += (uint64_t)a[5] * b[9]
+ (uint64_t)a[6] * b[8]
+ (uint64_t)a[7] * b[7]
+ (uint64_t)a[8] * b[6]
+ (uint64_t)a[9] * b[5];
VERIFY_BITS(d, 62);
/* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
u4 = d & M; d >>= 26; c += u4 * R0;
VERIFY_BITS(u4, 26);
VERIFY_BITS(d, 36);
/* VERIFY_BITS(c, 64); */
/* [d u4 0 0 0 0 t9 0 0 0 0 c-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
t4 = c & M; c >>= 26; c += u4 * R1;
VERIFY_BITS(t4, 26);
VERIFY_BITS(c, 39);
/* [d u4 0 0 0 0 t9 0 0 0 c-u4*R1 t4-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
c += (uint64_t)a[0] * b[5]
+ (uint64_t)a[1] * b[4]
+ (uint64_t)a[2] * b[3]
+ (uint64_t)a[3] * b[2]
+ (uint64_t)a[4] * b[1]
+ (uint64_t)a[5] * b[0];
VERIFY_BITS(c, 63);
/* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)a[6] * b[9]
+ (uint64_t)a[7] * b[8]
+ (uint64_t)a[8] * b[7]
+ (uint64_t)a[9] * b[6];
VERIFY_BITS(d, 62);
/* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
u5 = d & M; d >>= 26; c += u5 * R0;
VERIFY_BITS(u5, 26);
VERIFY_BITS(d, 36);
/* VERIFY_BITS(c, 64); */
/* [d u5 0 0 0 0 0 t9 0 0 0 c-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
t5 = c & M; c >>= 26; c += u5 * R1;
VERIFY_BITS(t5, 26);
VERIFY_BITS(c, 39);
/* [d u5 0 0 0 0 0 t9 0 0 c-u5*R1 t5-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
c += (uint64_t)a[0] * b[6]
+ (uint64_t)a[1] * b[5]
+ (uint64_t)a[2] * b[4]
+ (uint64_t)a[3] * b[3]
+ (uint64_t)a[4] * b[2]
+ (uint64_t)a[5] * b[1]
+ (uint64_t)a[6] * b[0];
VERIFY_BITS(c, 63);
/* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)a[7] * b[9]
+ (uint64_t)a[8] * b[8]
+ (uint64_t)a[9] * b[7];
VERIFY_BITS(d, 61);
/* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
u6 = d & M; d >>= 26; c += u6 * R0;
VERIFY_BITS(u6, 26);
VERIFY_BITS(d, 35);
/* VERIFY_BITS(c, 64); */
/* [d u6 0 0 0 0 0 0 t9 0 0 c-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
t6 = c & M; c >>= 26; c += u6 * R1;
VERIFY_BITS(t6, 26);
VERIFY_BITS(c, 39);
/* [d u6 0 0 0 0 0 0 t9 0 c-u6*R1 t6-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
c += (uint64_t)a[0] * b[7]
+ (uint64_t)a[1] * b[6]
+ (uint64_t)a[2] * b[5]
+ (uint64_t)a[3] * b[4]
+ (uint64_t)a[4] * b[3]
+ (uint64_t)a[5] * b[2]
+ (uint64_t)a[6] * b[1]
+ (uint64_t)a[7] * b[0];
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x8000007C00000007ULL);
/* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)a[8] * b[9]
+ (uint64_t)a[9] * b[8];
VERIFY_BITS(d, 58);
/* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
u7 = d & M; d >>= 26; c += u7 * R0;
VERIFY_BITS(u7, 26);
VERIFY_BITS(d, 32);
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x800001703FFFC2F7ULL);
/* [d u7 0 0 0 0 0 0 0 t9 0 c-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
t7 = c & M; c >>= 26; c += u7 * R1;
VERIFY_BITS(t7, 26);
VERIFY_BITS(c, 38);
/* [d u7 0 0 0 0 0 0 0 t9 c-u7*R1 t7-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
c += (uint64_t)a[0] * b[8]
+ (uint64_t)a[1] * b[7]
+ (uint64_t)a[2] * b[6]
+ (uint64_t)a[3] * b[5]
+ (uint64_t)a[4] * b[4]
+ (uint64_t)a[5] * b[3]
+ (uint64_t)a[6] * b[2]
+ (uint64_t)a[7] * b[1]
+ (uint64_t)a[8] * b[0];
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x9000007B80000008ULL);
/* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)a[9] * b[9];
VERIFY_BITS(d, 57);
/* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
u8 = d & M; d >>= 26; c += u8 * R0;
VERIFY_BITS(u8, 26);
VERIFY_BITS(d, 31);
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x9000016FBFFFC2F8ULL);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[3] = t3;
VERIFY_BITS(r[3], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[4] = t4;
VERIFY_BITS(r[4], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[5] = t5;
VERIFY_BITS(r[5], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[6] = t6;
VERIFY_BITS(r[6], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[7] = t7;
VERIFY_BITS(r[7], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[8] = c & M; c >>= 26; c += u8 * R1;
VERIFY_BITS(r[8], 26);
VERIFY_BITS(c, 39);
/* [d u8 0 0 0 0 0 0 0 0 t9+c-u8*R1 r8-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 0 0 t9+c r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += d * R0 + t9;
VERIFY_BITS(c, 45);
/* [d 0 0 0 0 0 0 0 0 0 c-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[9] = c & (M >> 4); c >>= 22; c += d * (R1 << 4);
VERIFY_BITS(r[9], 22);
VERIFY_BITS(c, 46);
/* [d 0 0 0 0 0 0 0 0 r9+((c-d*R1<<4)<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 -d*R1 r9+(c<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d = c * (R0 >> 4) + t0;
VERIFY_BITS(d, 56);
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 d-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[0] = d & M; d >>= 26;
VERIFY_BITS(r[0], 26);
VERIFY_BITS(d, 30);
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1+d r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d += c * (R1 >> 4) + t1;
VERIFY_BITS(d, 53);
VERIFY_CHECK(d <= 0x10000003FFFFBFULL);
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 d-c*R1>>4 r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [r9 r8 r7 r6 r5 r4 r3 t2 d r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[1] = d & M; d >>= 26;
VERIFY_BITS(r[1], 26);
VERIFY_BITS(d, 27);
VERIFY_CHECK(d <= 0x4000000ULL);
/* [r9 r8 r7 r6 r5 r4 r3 t2+d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d += t2;
VERIFY_BITS(d, 27);
/* [r9 r8 r7 r6 r5 r4 r3 d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[2] = d;
VERIFY_BITS(r[2], 27);
/* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
}
SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint32_t *r, const uint32_t *a) {
uint64_t c, d;
uint64_t u0, u1, u2, u3, u4, u5, u6, u7, u8;
uint32_t t9, t0, t1, t2, t3, t4, t5, t6, t7;
const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
VERIFY_BITS(a[0], 30);
VERIFY_BITS(a[1], 30);
VERIFY_BITS(a[2], 30);
VERIFY_BITS(a[3], 30);
VERIFY_BITS(a[4], 30);
VERIFY_BITS(a[5], 30);
VERIFY_BITS(a[6], 30);
VERIFY_BITS(a[7], 30);
VERIFY_BITS(a[8], 30);
VERIFY_BITS(a[9], 26);
/** [... a b c] is a shorthand for ... + a<<52 + b<<26 + c<<0 mod n.
* px is a shorthand for sum(a[i]*a[x-i], i=0..x).
* Note that [x 0 0 0 0 0 0 0 0 0 0] = [x*R1 x*R0].
*/
d = (uint64_t)(a[0]*2) * a[9]
+ (uint64_t)(a[1]*2) * a[8]
+ (uint64_t)(a[2]*2) * a[7]
+ (uint64_t)(a[3]*2) * a[6]
+ (uint64_t)(a[4]*2) * a[5];
/* VERIFY_BITS(d, 64); */
/* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
t9 = d & M; d >>= 26;
VERIFY_BITS(t9, 26);
VERIFY_BITS(d, 38);
/* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
c = (uint64_t)a[0] * a[0];
VERIFY_BITS(c, 60);
/* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
d += (uint64_t)(a[1]*2) * a[9]
+ (uint64_t)(a[2]*2) * a[8]
+ (uint64_t)(a[3]*2) * a[7]
+ (uint64_t)(a[4]*2) * a[6]
+ (uint64_t)a[5] * a[5];
VERIFY_BITS(d, 63);
/* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
u0 = d & M; d >>= 26; c += u0 * R0;
VERIFY_BITS(u0, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 61);
/* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
t0 = c & M; c >>= 26; c += u0 * R1;
VERIFY_BITS(t0, 26);
VERIFY_BITS(c, 37);
/* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
c += (uint64_t)(a[0]*2) * a[1];
VERIFY_BITS(c, 62);
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
d += (uint64_t)(a[2]*2) * a[9]
+ (uint64_t)(a[3]*2) * a[8]
+ (uint64_t)(a[4]*2) * a[7]
+ (uint64_t)(a[5]*2) * a[6];
VERIFY_BITS(d, 63);
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
u1 = d & M; d >>= 26; c += u1 * R0;
VERIFY_BITS(u1, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 63);
/* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
t1 = c & M; c >>= 26; c += u1 * R1;
VERIFY_BITS(t1, 26);
VERIFY_BITS(c, 38);
/* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
c += (uint64_t)(a[0]*2) * a[2]
+ (uint64_t)a[1] * a[1];
VERIFY_BITS(c, 62);
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
d += (uint64_t)(a[3]*2) * a[9]
+ (uint64_t)(a[4]*2) * a[8]
+ (uint64_t)(a[5]*2) * a[7]
+ (uint64_t)a[6] * a[6];
VERIFY_BITS(d, 63);
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
u2 = d & M; d >>= 26; c += u2 * R0;
VERIFY_BITS(u2, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 63);
/* [d u2 0 0 t9 0 0 0 0 0 0 c-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
t2 = c & M; c >>= 26; c += u2 * R1;
VERIFY_BITS(t2, 26);
VERIFY_BITS(c, 38);
/* [d u2 0 0 t9 0 0 0 0 0 c-u2*R1 t2-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
/* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
c += (uint64_t)(a[0]*2) * a[3]
+ (uint64_t)(a[1]*2) * a[2];
VERIFY_BITS(c, 63);
/* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
d += (uint64_t)(a[4]*2) * a[9]
+ (uint64_t)(a[5]*2) * a[8]
+ (uint64_t)(a[6]*2) * a[7];
VERIFY_BITS(d, 63);
/* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
u3 = d & M; d >>= 26; c += u3 * R0;
VERIFY_BITS(u3, 26);
VERIFY_BITS(d, 37);
/* VERIFY_BITS(c, 64); */
/* [d u3 0 0 0 t9 0 0 0 0 0 c-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
t3 = c & M; c >>= 26; c += u3 * R1;
VERIFY_BITS(t3, 26);
VERIFY_BITS(c, 39);
/* [d u3 0 0 0 t9 0 0 0 0 c-u3*R1 t3-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
/* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
c += (uint64_t)(a[0]*2) * a[4]
+ (uint64_t)(a[1]*2) * a[3]
+ (uint64_t)a[2] * a[2];
VERIFY_BITS(c, 63);
/* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
d += (uint64_t)(a[5]*2) * a[9]
+ (uint64_t)(a[6]*2) * a[8]
+ (uint64_t)a[7] * a[7];
VERIFY_BITS(d, 62);
/* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
u4 = d & M; d >>= 26; c += u4 * R0;
VERIFY_BITS(u4, 26);
VERIFY_BITS(d, 36);
/* VERIFY_BITS(c, 64); */
/* [d u4 0 0 0 0 t9 0 0 0 0 c-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
t4 = c & M; c >>= 26; c += u4 * R1;
VERIFY_BITS(t4, 26);
VERIFY_BITS(c, 39);
/* [d u4 0 0 0 0 t9 0 0 0 c-u4*R1 t4-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
c += (uint64_t)(a[0]*2) * a[5]
+ (uint64_t)(a[1]*2) * a[4]
+ (uint64_t)(a[2]*2) * a[3];
VERIFY_BITS(c, 63);
/* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)(a[6]*2) * a[9]
+ (uint64_t)(a[7]*2) * a[8];
VERIFY_BITS(d, 62);
/* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
u5 = d & M; d >>= 26; c += u5 * R0;
VERIFY_BITS(u5, 26);
VERIFY_BITS(d, 36);
/* VERIFY_BITS(c, 64); */
/* [d u5 0 0 0 0 0 t9 0 0 0 c-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
t5 = c & M; c >>= 26; c += u5 * R1;
VERIFY_BITS(t5, 26);
VERIFY_BITS(c, 39);
/* [d u5 0 0 0 0 0 t9 0 0 c-u5*R1 t5-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
c += (uint64_t)(a[0]*2) * a[6]
+ (uint64_t)(a[1]*2) * a[5]
+ (uint64_t)(a[2]*2) * a[4]
+ (uint64_t)a[3] * a[3];
VERIFY_BITS(c, 63);
/* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)(a[7]*2) * a[9]
+ (uint64_t)a[8] * a[8];
VERIFY_BITS(d, 61);
/* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
u6 = d & M; d >>= 26; c += u6 * R0;
VERIFY_BITS(u6, 26);
VERIFY_BITS(d, 35);
/* VERIFY_BITS(c, 64); */
/* [d u6 0 0 0 0 0 0 t9 0 0 c-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
t6 = c & M; c >>= 26; c += u6 * R1;
VERIFY_BITS(t6, 26);
VERIFY_BITS(c, 39);
/* [d u6 0 0 0 0 0 0 t9 0 c-u6*R1 t6-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
c += (uint64_t)(a[0]*2) * a[7]
+ (uint64_t)(a[1]*2) * a[6]
+ (uint64_t)(a[2]*2) * a[5]
+ (uint64_t)(a[3]*2) * a[4];
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x8000007C00000007ULL);
/* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)(a[8]*2) * a[9];
VERIFY_BITS(d, 58);
/* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
u7 = d & M; d >>= 26; c += u7 * R0;
VERIFY_BITS(u7, 26);
VERIFY_BITS(d, 32);
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x800001703FFFC2F7ULL);
/* [d u7 0 0 0 0 0 0 0 t9 0 c-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
t7 = c & M; c >>= 26; c += u7 * R1;
VERIFY_BITS(t7, 26);
VERIFY_BITS(c, 38);
/* [d u7 0 0 0 0 0 0 0 t9 c-u7*R1 t7-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
c += (uint64_t)(a[0]*2) * a[8]
+ (uint64_t)(a[1]*2) * a[7]
+ (uint64_t)(a[2]*2) * a[6]
+ (uint64_t)(a[3]*2) * a[5]
+ (uint64_t)a[4] * a[4];
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x9000007B80000008ULL);
/* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d += (uint64_t)a[9] * a[9];
VERIFY_BITS(d, 57);
/* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
u8 = d & M; d >>= 26; c += u8 * R0;
VERIFY_BITS(u8, 26);
VERIFY_BITS(d, 31);
/* VERIFY_BITS(c, 64); */
VERIFY_CHECK(c <= 0x9000016FBFFFC2F8ULL);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[3] = t3;
VERIFY_BITS(r[3], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[4] = t4;
VERIFY_BITS(r[4], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[5] = t5;
VERIFY_BITS(r[5], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[6] = t6;
VERIFY_BITS(r[6], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[7] = t7;
VERIFY_BITS(r[7], 26);
/* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[8] = c & M; c >>= 26; c += u8 * R1;
VERIFY_BITS(r[8], 26);
VERIFY_BITS(c, 39);
/* [d u8 0 0 0 0 0 0 0 0 t9+c-u8*R1 r8-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 0 0 t9+c r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += d * R0 + t9;
VERIFY_BITS(c, 45);
/* [d 0 0 0 0 0 0 0 0 0 c-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[9] = c & (M >> 4); c >>= 22; c += d * (R1 << 4);
VERIFY_BITS(r[9], 22);
VERIFY_BITS(c, 46);
/* [d 0 0 0 0 0 0 0 0 r9+((c-d*R1<<4)<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 0 0 0 0 -d*R1 r9+(c<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d = c * (R0 >> 4) + t0;
VERIFY_BITS(d, 56);
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 d-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[0] = d & M; d >>= 26;
VERIFY_BITS(r[0], 26);
VERIFY_BITS(d, 30);
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1+d r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d += c * (R1 >> 4) + t1;
VERIFY_BITS(d, 53);
VERIFY_CHECK(d <= 0x10000003FFFFBFULL);
/* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 d-c*R1>>4 r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [r9 r8 r7 r6 r5 r4 r3 t2 d r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[1] = d & M; d >>= 26;
VERIFY_BITS(r[1], 26);
VERIFY_BITS(d, 27);
VERIFY_CHECK(d <= 0x4000000ULL);
/* [r9 r8 r7 r6 r5 r4 r3 t2+d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
d += t2;
VERIFY_BITS(d, 27);
/* [r9 r8 r7 r6 r5 r4 r3 d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[2] = d;
VERIFY_BITS(r[2], 27);
/* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
}
#endif
static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b) {
#ifdef VERIFY
VERIFY_CHECK(a->magnitude <= 8);
VERIFY_CHECK(b->magnitude <= 8);
secp256k1_fe_verify(a);
secp256k1_fe_verify(b);
VERIFY_CHECK(r != b);
+ VERIFY_CHECK(a != b);
#endif
secp256k1_fe_mul_inner(r->n, a->n, b->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->magnitude <= 8);
secp256k1_fe_verify(a);
#endif
secp256k1_fe_sqr_inner(r->n, a->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) {
uint32_t mask0, mask1;
mask0 = flag + ~((uint32_t)0);
mask1 = ~mask0;
r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
r->n[5] = (r->n[5] & mask0) | (a->n[5] & mask1);
r->n[6] = (r->n[6] & mask0) | (a->n[6] & mask1);
r->n[7] = (r->n[7] & mask0) | (a->n[7] & mask1);
r->n[8] = (r->n[8] & mask0) | (a->n[8] & mask1);
r->n[9] = (r->n[9] & mask0) | (a->n[9] & mask1);
#ifdef VERIFY
if (a->magnitude > r->magnitude) {
r->magnitude = a->magnitude;
}
r->normalized &= a->normalized;
#endif
}
static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) {
uint32_t mask0, mask1;
mask0 = flag + ~((uint32_t)0);
mask1 = ~mask0;
r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
r->n[5] = (r->n[5] & mask0) | (a->n[5] & mask1);
r->n[6] = (r->n[6] & mask0) | (a->n[6] & mask1);
r->n[7] = (r->n[7] & mask0) | (a->n[7] & mask1);
}
static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
#endif
r->n[0] = a->n[0] | a->n[1] << 26;
r->n[1] = a->n[1] >> 6 | a->n[2] << 20;
r->n[2] = a->n[2] >> 12 | a->n[3] << 14;
r->n[3] = a->n[3] >> 18 | a->n[4] << 8;
r->n[4] = a->n[4] >> 24 | a->n[5] << 2 | a->n[6] << 28;
r->n[5] = a->n[6] >> 4 | a->n[7] << 22;
r->n[6] = a->n[7] >> 10 | a->n[8] << 16;
r->n[7] = a->n[8] >> 16 | a->n[9] << 10;
}
static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a) {
r->n[0] = a->n[0] & 0x3FFFFFFUL;
r->n[1] = a->n[0] >> 26 | ((a->n[1] << 6) & 0x3FFFFFFUL);
r->n[2] = a->n[1] >> 20 | ((a->n[2] << 12) & 0x3FFFFFFUL);
r->n[3] = a->n[2] >> 14 | ((a->n[3] << 18) & 0x3FFFFFFUL);
r->n[4] = a->n[3] >> 8 | ((a->n[4] << 24) & 0x3FFFFFFUL);
r->n[5] = (a->n[4] >> 2) & 0x3FFFFFFUL;
r->n[6] = a->n[4] >> 28 | ((a->n[5] << 4) & 0x3FFFFFFUL);
r->n[7] = a->n[5] >> 22 | ((a->n[6] << 10) & 0x3FFFFFFUL);
r->n[8] = a->n[6] >> 16 | ((a->n[7] << 16) & 0x3FFFFFFUL);
r->n[9] = a->n[7] >> 10;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
#endif
}
#endif /* SECP256K1_FIELD_REPR_IMPL_H */
diff --git a/src/secp256k1/src/field_5x52.h b/src/secp256k1/src/field_5x52.h
index bccd8feb4d..fc5bfe357e 100644
--- a/src/secp256k1/src/field_5x52.h
+++ b/src/secp256k1/src/field_5x52.h
@@ -1,47 +1,49 @@
/**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
#ifndef SECP256K1_FIELD_REPR_H
#define SECP256K1_FIELD_REPR_H
#include <stdint.h>
typedef struct {
- /* X = sum(i=0..4, elem[i]*2^52) mod n */
+ /* X = sum(i=0..4, n[i]*2^(i*52)) mod p
+ * where p = 2^256 - 0x1000003D1
+ */
uint64_t n[5];
#ifdef VERIFY
int magnitude;
int normalized;
#endif
} secp256k1_fe;
/* Unpacks a constant into a overlapping multi-limbed FE element. */
#define SECP256K1_FE_CONST_INNER(d7, d6, d5, d4, d3, d2, d1, d0) { \
(d0) | (((uint64_t)(d1) & 0xFFFFFUL) << 32), \
((uint64_t)(d1) >> 20) | (((uint64_t)(d2)) << 12) | (((uint64_t)(d3) & 0xFFUL) << 44), \
((uint64_t)(d3) >> 8) | (((uint64_t)(d4) & 0xFFFFFFFUL) << 24), \
((uint64_t)(d4) >> 28) | (((uint64_t)(d5)) << 4) | (((uint64_t)(d6) & 0xFFFFUL) << 36), \
((uint64_t)(d6) >> 16) | (((uint64_t)(d7)) << 16) \
}
#ifdef VERIFY
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)), 1, 1}
#else
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0))}
#endif
typedef struct {
uint64_t n[4];
} secp256k1_fe_storage;
#define SECP256K1_FE_STORAGE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {{ \
(d0) | (((uint64_t)(d1)) << 32), \
(d2) | (((uint64_t)(d3)) << 32), \
(d4) | (((uint64_t)(d5)) << 32), \
(d6) | (((uint64_t)(d7)) << 32) \
}}
#endif /* SECP256K1_FIELD_REPR_H */
diff --git a/src/secp256k1/src/field_5x52_impl.h b/src/secp256k1/src/field_5x52_impl.h
index 957c61b014..f4263320d5 100644
--- a/src/secp256k1/src/field_5x52_impl.h
+++ b/src/secp256k1/src/field_5x52_impl.h
@@ -1,496 +1,496 @@
/**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
#ifndef SECP256K1_FIELD_REPR_IMPL_H
#define SECP256K1_FIELD_REPR_IMPL_H
#if defined HAVE_CONFIG_H
#include "libsecp256k1-config.h"
#endif
#include "util.h"
-#include "num.h"
#include "field.h"
#if defined(USE_ASM_X86_64)
#include "field_5x52_asm_impl.h"
#else
#include "field_5x52_int128_impl.h"
#endif
/** Implements arithmetic modulo FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F,
* represented as 5 uint64_t's in base 2^52. The values are allowed to contain >52 each. In particular,
* each FieldElem has a 'magnitude' associated with it. Internally, a magnitude M means each element
* is at most M*(2^53-1), except the most significant one, which is limited to M*(2^49-1). All operations
* accept any input with magnitude at most M, and have different rules for propagating magnitude to their
* output.
*/
#ifdef VERIFY
static void secp256k1_fe_verify(const secp256k1_fe *a) {
const uint64_t *d = a->n;
int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
/* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
r &= (d[0] <= 0xFFFFFFFFFFFFFULL * m);
r &= (d[1] <= 0xFFFFFFFFFFFFFULL * m);
r &= (d[2] <= 0xFFFFFFFFFFFFFULL * m);
r &= (d[3] <= 0xFFFFFFFFFFFFFULL * m);
r &= (d[4] <= 0x0FFFFFFFFFFFFULL * m);
r &= (a->magnitude >= 0);
r &= (a->magnitude <= 2048);
if (a->normalized) {
r &= (a->magnitude <= 1);
if (r && (d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
r &= (d[0] < 0xFFFFEFFFFFC2FULL);
}
}
VERIFY_CHECK(r == 1);
}
#endif
static void secp256k1_fe_normalize(secp256k1_fe *r) {
uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
/* Reduce t4 at the start so there will be at most a single carry from the first pass */
uint64_t m;
uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x1000003D1ULL;
t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t4 >> 49 == 0);
/* At most a single final reduction is needed; check if the value is >= the field characteristic */
x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
& (t0 >= 0xFFFFEFFFFFC2FULL));
/* Apply the final reduction (for constant-time behaviour, we do it always) */
t0 += x * 0x1000003D1ULL;
t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
/* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
VERIFY_CHECK(t4 >> 48 == x);
/* Mask off the possible multiple of 2^256 from the final reduction */
t4 &= 0x0FFFFFFFFFFFFULL;
r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_normalize_weak(secp256k1_fe *r) {
uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
/* Reduce t4 at the start so there will be at most a single carry from the first pass */
uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x1000003D1ULL;
t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t4 >> 49 == 0);
r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
#ifdef VERIFY
r->magnitude = 1;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_normalize_var(secp256k1_fe *r) {
uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
/* Reduce t4 at the start so there will be at most a single carry from the first pass */
uint64_t m;
uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x1000003D1ULL;
t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t4 >> 49 == 0);
/* At most a single final reduction is needed; check if the value is >= the field characteristic */
x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
& (t0 >= 0xFFFFEFFFFFC2FULL));
if (x) {
t0 += 0x1000003D1ULL;
t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
/* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
VERIFY_CHECK(t4 >> 48 == x);
/* Mask off the possible multiple of 2^256 from the final reduction */
t4 &= 0x0FFFFFFFFFFFFULL;
}
r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
}
static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r) {
uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
/* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
uint64_t z0, z1;
/* Reduce t4 at the start so there will be at most a single carry from the first pass */
uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x1000003D1ULL;
t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL; z0 = t0; z1 = t0 ^ 0x1000003D0ULL;
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;
/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t4 >> 49 == 0);
return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
}
static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r) {
uint64_t t0, t1, t2, t3, t4;
uint64_t z0, z1;
uint64_t x;
t0 = r->n[0];
t4 = r->n[4];
/* Reduce t4 at the start so there will be at most a single carry from the first pass */
x = t4 >> 48;
/* The first pass ensures the magnitude is 1, ... */
t0 += x * 0x1000003D1ULL;
/* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
z0 = t0 & 0xFFFFFFFFFFFFFULL;
z1 = z0 ^ 0x1000003D0ULL;
/* Fast return path should catch the majority of cases */
if ((z0 != 0ULL) & (z1 != 0xFFFFFFFFFFFFFULL)) {
return 0;
}
t1 = r->n[1];
t2 = r->n[2];
t3 = r->n[3];
t4 &= 0x0FFFFFFFFFFFFULL;
t1 += (t0 >> 52);
t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;
/* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
VERIFY_CHECK(t4 >> 49 == 0);
return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
}
SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe *r, int a) {
r->n[0] = a;
r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
}
SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe *a) {
const uint64_t *t = a->n;
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
secp256k1_fe_verify(a);
#endif
return (t[0] | t[1] | t[2] | t[3] | t[4]) == 0;
}
SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
secp256k1_fe_verify(a);
#endif
return a->n[0] & 1;
}
SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe *a) {
int i;
#ifdef VERIFY
a->magnitude = 0;
a->normalized = 1;
#endif
for (i=0; i<5; i++) {
a->n[i] = 0;
}
}
static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) {
int i;
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
VERIFY_CHECK(b->normalized);
secp256k1_fe_verify(a);
secp256k1_fe_verify(b);
#endif
for (i = 4; i >= 0; i--) {
if (a->n[i] > b->n[i]) {
return 1;
}
if (a->n[i] < b->n[i]) {
return -1;
}
}
return 0;
}
static int secp256k1_fe_set_b32(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);
if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) {
return 0;
}
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
secp256k1_fe_verify(r);
#endif
return 1;
}
/** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
secp256k1_fe_verify(a);
#endif
r[0] = (a->n[4] >> 40) & 0xFF;
r[1] = (a->n[4] >> 32) & 0xFF;
r[2] = (a->n[4] >> 24) & 0xFF;
r[3] = (a->n[4] >> 16) & 0xFF;
r[4] = (a->n[4] >> 8) & 0xFF;
r[5] = a->n[4] & 0xFF;
r[6] = (a->n[3] >> 44) & 0xFF;
r[7] = (a->n[3] >> 36) & 0xFF;
r[8] = (a->n[3] >> 28) & 0xFF;
r[9] = (a->n[3] >> 20) & 0xFF;
r[10] = (a->n[3] >> 12) & 0xFF;
r[11] = (a->n[3] >> 4) & 0xFF;
r[12] = ((a->n[2] >> 48) & 0xF) | ((a->n[3] & 0xF) << 4);
r[13] = (a->n[2] >> 40) & 0xFF;
r[14] = (a->n[2] >> 32) & 0xFF;
r[15] = (a->n[2] >> 24) & 0xFF;
r[16] = (a->n[2] >> 16) & 0xFF;
r[17] = (a->n[2] >> 8) & 0xFF;
r[18] = a->n[2] & 0xFF;
r[19] = (a->n[1] >> 44) & 0xFF;
r[20] = (a->n[1] >> 36) & 0xFF;
r[21] = (a->n[1] >> 28) & 0xFF;
r[22] = (a->n[1] >> 20) & 0xFF;
r[23] = (a->n[1] >> 12) & 0xFF;
r[24] = (a->n[1] >> 4) & 0xFF;
r[25] = ((a->n[0] >> 48) & 0xF) | ((a->n[1] & 0xF) << 4);
r[26] = (a->n[0] >> 40) & 0xFF;
r[27] = (a->n[0] >> 32) & 0xFF;
r[28] = (a->n[0] >> 24) & 0xFF;
r[29] = (a->n[0] >> 16) & 0xFF;
r[30] = (a->n[0] >> 8) & 0xFF;
r[31] = a->n[0] & 0xFF;
}
SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
#ifdef VERIFY
VERIFY_CHECK(a->magnitude <= m);
secp256k1_fe_verify(a);
#endif
r->n[0] = 0xFFFFEFFFFFC2FULL * 2 * (m + 1) - a->n[0];
r->n[1] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[1];
r->n[2] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[2];
r->n[3] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[3];
r->n[4] = 0x0FFFFFFFFFFFFULL * 2 * (m + 1) - a->n[4];
#ifdef VERIFY
r->magnitude = m + 1;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe *r, int a) {
r->n[0] *= a;
r->n[1] *= a;
r->n[2] *= a;
r->n[3] *= a;
r->n[4] *= a;
#ifdef VERIFY
r->magnitude *= a;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a) {
#ifdef VERIFY
secp256k1_fe_verify(a);
#endif
r->n[0] += a->n[0];
r->n[1] += a->n[1];
r->n[2] += a->n[2];
r->n[3] += a->n[3];
r->n[4] += a->n[4];
#ifdef VERIFY
r->magnitude += a->magnitude;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b) {
#ifdef VERIFY
VERIFY_CHECK(a->magnitude <= 8);
VERIFY_CHECK(b->magnitude <= 8);
secp256k1_fe_verify(a);
secp256k1_fe_verify(b);
VERIFY_CHECK(r != b);
+ VERIFY_CHECK(a != b);
#endif
secp256k1_fe_mul_inner(r->n, a->n, b->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->magnitude <= 8);
secp256k1_fe_verify(a);
#endif
secp256k1_fe_sqr_inner(r->n, a->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
secp256k1_fe_verify(r);
#endif
}
static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) {
uint64_t mask0, mask1;
mask0 = flag + ~((uint64_t)0);
mask1 = ~mask0;
r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
#ifdef VERIFY
if (a->magnitude > r->magnitude) {
r->magnitude = a->magnitude;
}
r->normalized &= a->normalized;
#endif
}
static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) {
uint64_t mask0, mask1;
mask0 = flag + ~((uint64_t)0);
mask1 = ~mask0;
r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
}
static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
#endif
r->n[0] = a->n[0] | a->n[1] << 52;
r->n[1] = a->n[1] >> 12 | a->n[2] << 40;
r->n[2] = a->n[2] >> 24 | a->n[3] << 28;
r->n[3] = a->n[3] >> 36 | a->n[4] << 16;
}
static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a) {
r->n[0] = a->n[0] & 0xFFFFFFFFFFFFFULL;
r->n[1] = a->n[0] >> 52 | ((a->n[1] << 12) & 0xFFFFFFFFFFFFFULL);
r->n[2] = a->n[1] >> 40 | ((a->n[2] << 24) & 0xFFFFFFFFFFFFFULL);
r->n[3] = a->n[2] >> 28 | ((a->n[3] << 36) & 0xFFFFFFFFFFFFFULL);
r->n[4] = a->n[3] >> 16;
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 1;
#endif
}
#endif /* SECP256K1_FIELD_REPR_IMPL_H */
diff --git a/src/secp256k1/src/field_5x52_int128_impl.h b/src/secp256k1/src/field_5x52_int128_impl.h
index 95a0d1791c..bcbfb92ac2 100644
--- a/src/secp256k1/src/field_5x52_int128_impl.h
+++ b/src/secp256k1/src/field_5x52_int128_impl.h
@@ -1,277 +1,279 @@
/**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
#ifndef SECP256K1_FIELD_INNER5X52_IMPL_H
#define SECP256K1_FIELD_INNER5X52_IMPL_H
#include <stdint.h>
#ifdef VERIFY
#define VERIFY_BITS(x, n) VERIFY_CHECK(((x) >> (n)) == 0)
#else
#define VERIFY_BITS(x, n) do { } while(0)
#endif
SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint64_t *r, const uint64_t *a, const uint64_t * SECP256K1_RESTRICT b) {
uint128_t c, d;
uint64_t t3, t4, tx, u0;
uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
VERIFY_BITS(a[0], 56);
VERIFY_BITS(a[1], 56);
VERIFY_BITS(a[2], 56);
VERIFY_BITS(a[3], 56);
VERIFY_BITS(a[4], 52);
VERIFY_BITS(b[0], 56);
VERIFY_BITS(b[1], 56);
VERIFY_BITS(b[2], 56);
VERIFY_BITS(b[3], 56);
VERIFY_BITS(b[4], 52);
VERIFY_CHECK(r != b);
+ VERIFY_CHECK(a != b);
/* [... a b c] is a shorthand for ... + a<<104 + b<<52 + c<<0 mod n.
- * px is a shorthand for sum(a[i]*b[x-i], i=0..x).
+ * for 0 <= x <= 4, px is a shorthand for sum(a[i]*b[x-i], i=0..x).
+ * for 4 <= x <= 8, px is a shorthand for sum(a[i]*b[x-i], i=(x-4)..4)
* Note that [x 0 0 0 0 0] = [x*R].
*/
d = (uint128_t)a0 * b[3]
+ (uint128_t)a1 * b[2]
+ (uint128_t)a2 * b[1]
+ (uint128_t)a3 * b[0];
VERIFY_BITS(d, 114);
/* [d 0 0 0] = [p3 0 0 0] */
c = (uint128_t)a4 * b[4];
VERIFY_BITS(c, 112);
/* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
d += (c & M) * R; c >>= 52;
VERIFY_BITS(d, 115);
VERIFY_BITS(c, 60);
/* [c 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
t3 = d & M; d >>= 52;
VERIFY_BITS(t3, 52);
VERIFY_BITS(d, 63);
/* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
d += (uint128_t)a0 * b[4]
+ (uint128_t)a1 * b[3]
+ (uint128_t)a2 * b[2]
+ (uint128_t)a3 * b[1]
+ (uint128_t)a4 * b[0];
VERIFY_BITS(d, 115);
/* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
d += c * R;
VERIFY_BITS(d, 116);
/* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
t4 = d & M; d >>= 52;
VERIFY_BITS(t4, 52);
VERIFY_BITS(d, 64);
/* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
tx = (t4 >> 48); t4 &= (M >> 4);
VERIFY_BITS(tx, 4);
VERIFY_BITS(t4, 48);
/* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
c = (uint128_t)a0 * b[0];
VERIFY_BITS(c, 112);
/* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
d += (uint128_t)a1 * b[4]
+ (uint128_t)a2 * b[3]
+ (uint128_t)a3 * b[2]
+ (uint128_t)a4 * b[1];
VERIFY_BITS(d, 115);
/* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
u0 = d & M; d >>= 52;
VERIFY_BITS(u0, 52);
VERIFY_BITS(d, 63);
/* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
/* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
u0 = (u0 << 4) | tx;
VERIFY_BITS(u0, 56);
/* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
c += (uint128_t)u0 * (R >> 4);
VERIFY_BITS(c, 115);
/* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
r[0] = c & M; c >>= 52;
VERIFY_BITS(r[0], 52);
VERIFY_BITS(c, 61);
/* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
c += (uint128_t)a0 * b[1]
+ (uint128_t)a1 * b[0];
VERIFY_BITS(c, 114);
/* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
d += (uint128_t)a2 * b[4]
+ (uint128_t)a3 * b[3]
+ (uint128_t)a4 * b[2];
VERIFY_BITS(d, 114);
/* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
c += (d & M) * R; d >>= 52;
VERIFY_BITS(c, 115);
VERIFY_BITS(d, 62);
/* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
r[1] = c & M; c >>= 52;
VERIFY_BITS(r[1], 52);
VERIFY_BITS(c, 63);
/* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
c += (uint128_t)a0 * b[2]
+ (uint128_t)a1 * b[1]
+ (uint128_t)a2 * b[0];
VERIFY_BITS(c, 114);
/* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
d += (uint128_t)a3 * b[4]
+ (uint128_t)a4 * b[3];
VERIFY_BITS(d, 114);
/* [d 0 0 t4 t3 c t1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += (d & M) * R; d >>= 52;
VERIFY_BITS(c, 115);
VERIFY_BITS(d, 62);
/* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
/* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[2] = c & M; c >>= 52;
VERIFY_BITS(r[2], 52);
VERIFY_BITS(c, 63);
/* [d 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += d * R + t3;
VERIFY_BITS(c, 100);
/* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[3] = c & M; c >>= 52;
VERIFY_BITS(r[3], 52);
VERIFY_BITS(c, 48);
/* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += t4;
VERIFY_BITS(c, 49);
/* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[4] = c;
VERIFY_BITS(r[4], 49);
/* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
}
SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a) {
uint128_t c, d;
uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
int64_t t3, t4, tx, u0;
const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
VERIFY_BITS(a[0], 56);
VERIFY_BITS(a[1], 56);
VERIFY_BITS(a[2], 56);
VERIFY_BITS(a[3], 56);
VERIFY_BITS(a[4], 52);
/** [... a b c] is a shorthand for ... + a<<104 + b<<52 + c<<0 mod n.
* px is a shorthand for sum(a[i]*a[x-i], i=0..x).
* Note that [x 0 0 0 0 0] = [x*R].
*/
d = (uint128_t)(a0*2) * a3
+ (uint128_t)(a1*2) * a2;
VERIFY_BITS(d, 114);
/* [d 0 0 0] = [p3 0 0 0] */
c = (uint128_t)a4 * a4;
VERIFY_BITS(c, 112);
/* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
d += (c & M) * R; c >>= 52;
VERIFY_BITS(d, 115);
VERIFY_BITS(c, 60);
/* [c 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
t3 = d & M; d >>= 52;
VERIFY_BITS(t3, 52);
VERIFY_BITS(d, 63);
/* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
a4 *= 2;
d += (uint128_t)a0 * a4
+ (uint128_t)(a1*2) * a3
+ (uint128_t)a2 * a2;
VERIFY_BITS(d, 115);
/* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
d += c * R;
VERIFY_BITS(d, 116);
/* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
t4 = d & M; d >>= 52;
VERIFY_BITS(t4, 52);
VERIFY_BITS(d, 64);
/* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
tx = (t4 >> 48); t4 &= (M >> 4);
VERIFY_BITS(tx, 4);
VERIFY_BITS(t4, 48);
/* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
c = (uint128_t)a0 * a0;
VERIFY_BITS(c, 112);
/* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
d += (uint128_t)a1 * a4
+ (uint128_t)(a2*2) * a3;
VERIFY_BITS(d, 114);
/* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
u0 = d & M; d >>= 52;
VERIFY_BITS(u0, 52);
VERIFY_BITS(d, 62);
/* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
/* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
u0 = (u0 << 4) | tx;
VERIFY_BITS(u0, 56);
/* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
c += (uint128_t)u0 * (R >> 4);
VERIFY_BITS(c, 113);
/* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
r[0] = c & M; c >>= 52;
VERIFY_BITS(r[0], 52);
VERIFY_BITS(c, 61);
/* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
a0 *= 2;
c += (uint128_t)a0 * a1;
VERIFY_BITS(c, 114);
/* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
d += (uint128_t)a2 * a4
+ (uint128_t)a3 * a3;
VERIFY_BITS(d, 114);
/* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
c += (d & M) * R; d >>= 52;
VERIFY_BITS(c, 115);
VERIFY_BITS(d, 62);
/* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
r[1] = c & M; c >>= 52;
VERIFY_BITS(r[1], 52);
VERIFY_BITS(c, 63);
/* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
c += (uint128_t)a0 * a2
+ (uint128_t)a1 * a1;
VERIFY_BITS(c, 114);
/* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
d += (uint128_t)a3 * a4;
VERIFY_BITS(d, 114);
/* [d 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += (d & M) * R; d >>= 52;
VERIFY_BITS(c, 115);
VERIFY_BITS(d, 62);
/* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[2] = c & M; c >>= 52;
VERIFY_BITS(r[2], 52);
VERIFY_BITS(c, 63);
/* [d 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += d * R + t3;
VERIFY_BITS(c, 100);
/* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[3] = c & M; c >>= 52;
VERIFY_BITS(r[3], 52);
VERIFY_BITS(c, 48);
/* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
c += t4;
VERIFY_BITS(c, 49);
/* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
r[4] = c;
VERIFY_BITS(r[4], 49);
/* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
}
#endif /* SECP256K1_FIELD_INNER5X52_IMPL_H */
diff --git a/src/secp256k1/src/field_impl.h b/src/secp256k1/src/field_impl.h
index 1445653018..6070caccfe 100644
--- a/src/secp256k1/src/field_impl.h
+++ b/src/secp256k1/src/field_impl.h
@@ -1,317 +1,318 @@
/**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
#ifndef SECP256K1_FIELD_IMPL_H
#define SECP256K1_FIELD_IMPL_H
#if defined HAVE_CONFIG_H
#include "libsecp256k1-config.h"
#endif
#include "util.h"
+#include "num.h"
#if defined(USE_FIELD_10X26)
#include "field_10x26_impl.h"
#elif defined(USE_FIELD_5X52)
#include "field_5x52_impl.h"
#else
#error "Please select field implementation"
#endif
SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
secp256k1_fe na;
secp256k1_fe_negate(&na, a, 1);
secp256k1_fe_add(&na, b);
return secp256k1_fe_normalizes_to_zero(&na);
}
SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b) {
secp256k1_fe na;
secp256k1_fe_negate(&na, a, 1);
secp256k1_fe_add(&na, b);
return secp256k1_fe_normalizes_to_zero_var(&na);
}
static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
/** Given that p is congruent to 3 mod 4, we can compute the square root of
* a mod p as the (p+1)/4'th power of a.
*
* As (p+1)/4 is an even number, it will have the same result for a and for
* (-a). Only one of these two numbers actually has a square root however,
* so we test at the end by squaring and comparing to the input.
* Also because (p+1)/4 is an even number, the computed square root is
* itself always a square (a ** ((p+1)/4) is the square of a ** ((p+1)/8)).
*/
secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
int j;
VERIFY_CHECK(r != a);
/** The binary representation of (p + 1)/4 has 3 blocks of 1s, with lengths in
* { 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block:
* 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223]
*/
secp256k1_fe_sqr(&x2, a);
secp256k1_fe_mul(&x2, &x2, a);
secp256k1_fe_sqr(&x3, &x2);
secp256k1_fe_mul(&x3, &x3, a);
x6 = x3;
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&x6, &x6);
}
secp256k1_fe_mul(&x6, &x6, &x3);
x9 = x6;
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&x9, &x9);
}
secp256k1_fe_mul(&x9, &x9, &x3);
x11 = x9;
for (j=0; j<2; j++) {
secp256k1_fe_sqr(&x11, &x11);
}
secp256k1_fe_mul(&x11, &x11, &x2);
x22 = x11;
for (j=0; j<11; j++) {
secp256k1_fe_sqr(&x22, &x22);
}
secp256k1_fe_mul(&x22, &x22, &x11);
x44 = x22;
for (j=0; j<22; j++) {
secp256k1_fe_sqr(&x44, &x44);
}
secp256k1_fe_mul(&x44, &x44, &x22);
x88 = x44;
for (j=0; j<44; j++) {
secp256k1_fe_sqr(&x88, &x88);
}
secp256k1_fe_mul(&x88, &x88, &x44);
x176 = x88;
for (j=0; j<88; j++) {
secp256k1_fe_sqr(&x176, &x176);
}
secp256k1_fe_mul(&x176, &x176, &x88);
x220 = x176;
for (j=0; j<44; j++) {
secp256k1_fe_sqr(&x220, &x220);
}
secp256k1_fe_mul(&x220, &x220, &x44);
x223 = x220;
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&x223, &x223);
}
secp256k1_fe_mul(&x223, &x223, &x3);
/* The final result is then assembled using a sliding window over the blocks. */
t1 = x223;
for (j=0; j<23; j++) {
secp256k1_fe_sqr(&t1, &t1);
}
secp256k1_fe_mul(&t1, &t1, &x22);
for (j=0; j<6; j++) {
secp256k1_fe_sqr(&t1, &t1);
}
secp256k1_fe_mul(&t1, &t1, &x2);
secp256k1_fe_sqr(&t1, &t1);
secp256k1_fe_sqr(r, &t1);
/* Check that a square root was actually calculated */
secp256k1_fe_sqr(&t1, r);
return secp256k1_fe_equal(&t1, a);
}
static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a) {
secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
int j;
/** The binary representation of (p - 2) has 5 blocks of 1s, with lengths in
* { 1, 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block:
* [1], [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223]
*/
secp256k1_fe_sqr(&x2, a);
secp256k1_fe_mul(&x2, &x2, a);
secp256k1_fe_sqr(&x3, &x2);
secp256k1_fe_mul(&x3, &x3, a);
x6 = x3;
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&x6, &x6);
}
secp256k1_fe_mul(&x6, &x6, &x3);
x9 = x6;
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&x9, &x9);
}
secp256k1_fe_mul(&x9, &x9, &x3);
x11 = x9;
for (j=0; j<2; j++) {
secp256k1_fe_sqr(&x11, &x11);
}
secp256k1_fe_mul(&x11, &x11, &x2);
x22 = x11;
for (j=0; j<11; j++) {
secp256k1_fe_sqr(&x22, &x22);
}
secp256k1_fe_mul(&x22, &x22, &x11);
x44 = x22;
for (j=0; j<22; j++) {
secp256k1_fe_sqr(&x44, &x44);
}
secp256k1_fe_mul(&x44, &x44, &x22);
x88 = x44;
for (j=0; j<44; j++) {
secp256k1_fe_sqr(&x88, &x88);
}
secp256k1_fe_mul(&x88, &x88, &x44);
x176 = x88;
for (j=0; j<88; j++) {
secp256k1_fe_sqr(&x176, &x176);
}
secp256k1_fe_mul(&x176, &x176, &x88);
x220 = x176;
for (j=0; j<44; j++) {
secp256k1_fe_sqr(&x220, &x220);
}
secp256k1_fe_mul(&x220, &x220, &x44);
x223 = x220;
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&x223, &x223);
}
secp256k1_fe_mul(&x223, &x223, &x3);
/* The final result is then assembled using a sliding window over the blocks. */
t1 = x223;
for (j=0; j<23; j++) {
secp256k1_fe_sqr(&t1, &t1);
}
secp256k1_fe_mul(&t1, &t1, &x22);
for (j=0; j<5; j++) {
secp256k1_fe_sqr(&t1, &t1);
}
secp256k1_fe_mul(&t1, &t1, a);
for (j=0; j<3; j++) {
secp256k1_fe_sqr(&t1, &t1);
}
secp256k1_fe_mul(&t1, &t1, &x2);
for (j=0; j<2; j++) {
secp256k1_fe_sqr(&t1, &t1);
}
secp256k1_fe_mul(r, a, &t1);
}
static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a) {
#if defined(USE_FIELD_INV_BUILTIN)
secp256k1_fe_inv(r, a);
#elif defined(USE_FIELD_INV_NUM)
secp256k1_num n, m;
static const secp256k1_fe negone = SECP256K1_FE_CONST(
0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL,
0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 0xFFFFFC2EUL
);
/* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
static const unsigned char prime[32] = {
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
};
unsigned char b[32];
int res;
secp256k1_fe c = *a;
secp256k1_fe_normalize_var(&c);
secp256k1_fe_get_b32(b, &c);
secp256k1_num_set_bin(&n, b, 32);
secp256k1_num_set_bin(&m, prime, 32);
secp256k1_num_mod_inverse(&n, &n, &m);
secp256k1_num_get_bin(b, 32, &n);
res = secp256k1_fe_set_b32(r, b);
(void)res;
VERIFY_CHECK(res);
/* Verify the result is the (unique) valid inverse using non-GMP code. */
secp256k1_fe_mul(&c, &c, r);
secp256k1_fe_add(&c, &negone);
CHECK(secp256k1_fe_normalizes_to_zero_var(&c));
#else
#error "Please select field inverse implementation"
#endif
}
static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len) {
secp256k1_fe u;
size_t i;
if (len < 1) {
return;
}
VERIFY_CHECK((r + len <= a) || (a + len <= r));
r[0] = a[0];
i = 0;
while (++i < len) {
secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
}
secp256k1_fe_inv_var(&u, &r[--i]);
while (i > 0) {
size_t j = i--;
secp256k1_fe_mul(&r[j], &r[i], &u);
secp256k1_fe_mul(&u, &u, &a[j]);
}
r[0] = u;
}
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) {
#ifndef USE_NUM_NONE
unsigned char b[32];
secp256k1_num n;
secp256k1_num m;
/* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
static const unsigned char prime[32] = {
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
};
secp256k1_fe c = *a;
secp256k1_fe_normalize_var(&c);
secp256k1_fe_get_b32(b, &c);
secp256k1_num_set_bin(&n, b, 32);
secp256k1_num_set_bin(&m, prime, 32);
return secp256k1_num_jacobi(&n, &m) >= 0;
#else
secp256k1_fe r;
return secp256k1_fe_sqrt(&r, a);
#endif
}
#endif /* SECP256K1_FIELD_IMPL_H */
File Metadata
Details
Attached
Mime Type
text/x-diff
Expires
Wed, Jan 29, 17:03 (11 h, 50 s)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5053359
Default Alt Text
(87 KB)
Attached To
rSTAGING Bitcoin ABC staging
Event Timeline
Log In to Comment