11#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
12 #include "verification/cbmc/model_small_field_constants.h"
13 PURIFY_CBMC_MODEL_FIELD_PRIME_INIT
15 UINT64_C(0xBFD25E8CD0364141),
16 UINT64_C(0xBAAEDCE6AF48A03B),
17 UINT64_C(0xFFFFFFFFFFFFFFFE),
18 UINT64_C(0xFFFFFFFFFFFFFFFF),
23#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
24 PURIFY_CBMC_MODEL_CURVE_ORDER_N1_INIT
26 UINT64_C(0x8A5A2A2C58E547E9),
27 UINT64_C(0xA328F24405347212),
28 UINT64_C(0xFFFFFFFFFFFFFFFF),
29 UINT64_C(0xFFFFFFFFFFFFFFFF),
34#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
35 PURIFY_CBMC_MODEL_CURVE_ORDER_N2_INIT
37 UINT64_C(0xF54A92ED47873A9B),
38 UINT64_C(0xD234C789595CCE64),
39 UINT64_C(0xFFFFFFFFFFFFFFFD),
40 UINT64_C(0xFFFFFFFFFFFFFFFF),
45#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
46 PURIFY_CBMC_MODEL_CURVE_HALF_N1_INIT
48 UINT64_C(0x452D15162C72A3F4),
49 UINT64_C(0xD1947922029A3909),
50 UINT64_C(0xFFFFFFFFFFFFFFFF),
51 UINT64_C(0x7FFFFFFFFFFFFFFF),
56#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
57 PURIFY_CBMC_MODEL_CURVE_HALF_N2_INIT
59 UINT64_C(0x7AA54976A3C39D4D),
60 UINT64_C(0xE91A63C4ACAE6732),
61 UINT64_C(0xFFFFFFFFFFFFFFFE),
62 UINT64_C(0x7FFFFFFFFFFFFFFF),
67#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
68 PURIFY_CBMC_MODEL_FIELD_DI_INIT
70 UINT64_C(0x4CBA8C385348E6E7),
71 UINT64_C(0xE445F1F5DFB6A67E),
72 UINT64_C(0x6666666666666665),
73 UINT64_C(0x6666666666666666),
80 volatile unsigned char* out = (
volatile unsigned char*)data;
89 memcpy(out, value, 4u *
sizeof(uint64_t));
93 memcpy(out, value, 4u *
sizeof(uint64_t));
100 for (i = 0; i < 4u; ++i) {
101 uint64_t sum = value[i] + carry;
102 carry = (uint64_t)(sum < value[i]);
110 for (i = 0; i < 8; ++i) {
111 out[7u - i] = (
unsigned char)(value & 0xffu);
121 const unsigned char* data,
123 const uint64_t range[5],
124 unsigned char info_byte) {
125 unsigned char tag_hash[32];
126 unsigned char derived[40];
127 unsigned char digest[32];
128 size_t bits = purify_u320_bit_length(range);
129 size_t bytes_needed = (bits + 7u) / 8u;
130 unsigned int attempt;
133 for (attempt = 0; attempt < 256u; ++attempt) {
134 size_t derived_len = 0;
137 while (derived_len < bytes_needed) {
138 unsigned char attempt_bytes[8];
139 unsigned char block_bytes[8];
140 const unsigned char* items[6];
148 item_lens[0] =
sizeof(tag_hash);
150 item_lens[1] =
sizeof(tag_hash);
152 item_lens[2] = data_len;
153 items[3] = &info_byte;
155 items[4] = attempt_bytes;
156 item_lens[4] =
sizeof(attempt_bytes);
157 items[5] = block_bytes;
158 item_lens[5] =
sizeof(block_bytes);
164 copy_len =
sizeof(digest);
165 if (copy_len > bytes_needed - derived_len) {
166 copy_len = bytes_needed - derived_len;
168 memcpy(derived + derived_len, digest, copy_len);
169 derived_len += copy_len;
173 purify_u320_from_bytes_be(out, derived, bytes_needed);
174 purify_u320_mask_bits(out, bits);
175 if (purify_u320_compare(out, range) < 0) {
183#if PURIFY_USE_LEGACY_FIELD_HASHES
184static int purify_curve_hash_to_int_hkdf_u320(uint64_t out[5],
185 const unsigned char* data,
187 const uint64_t range[5],
188 unsigned char info_byte) {
189 unsigned char derived[40];
190 unsigned char prk[32];
192 size_t bits = purify_u320_bit_length(range);
193 size_t bytes_needed = (bits + 7u) / 8u;
194 unsigned int salt_counter;
196 for (salt_counter = 0; salt_counter < 256u; ++salt_counter) {
197 unsigned char salt_byte = (
unsigned char)salt_counter;
199 unsigned int block_index = 0;
201 memset(prk, 0,
sizeof(prk));
202 memset(t, 0,
sizeof(t));
205 while (offset < bytes_needed) {
206 const size_t prev_len = block_index == 0 ? 0u :
sizeof(t);
207 const size_t input_len = prev_len + 2u;
208 unsigned char input[34];
211 if (prev_len != 0u) {
212 memcpy(input, t, prev_len);
214 input[prev_len] = info_byte;
215 input[prev_len + 1u] = (
unsigned char)(block_index + 1u);
217 copy_len =
sizeof(t);
218 if (copy_len > bytes_needed - offset) {
219 copy_len = bytes_needed - offset;
221 memcpy(derived + offset, t, copy_len);
226 purify_u320_from_bytes_be(out, derived, bytes_needed);
227 purify_u320_mask_bits(out, bits);
228 if (purify_u320_compare(out, range) < 0) {
260 out.
x = normalized.
x;
261 out.
y = normalized.
y;
450 purify_u320_try_mul_small(out, 2);
674 rhs_affine.
x = rhs->
x;
675 rhs_affine.
y = rhs->
y;
682 lhs_affine.
x = lhs->
x;
683 lhs_affine.
y = lhs->
y;
728 size_t bits = purify_u256_bit_length(scalar);
732 for (i = bits; i != 0; --i) {
735 if (purify_u256_bit(scalar, idx) != 0) {
750 unsigned int prev_bit = 0;
751 unsigned int bit = 0;
752 size_t bits = purify_u256_bit_length(curve->
n);
755 for (i = bits; i != 0; --i) {
757 bit = purify_u256_bit(scalar, idx) != 0 ? 1u : 0u;
775#if defined(PURIFY_VALGRIND_TESTING) || defined(PURIFY_CBMC_TESTING)
823 const unsigned char* data,
size_t data_len) {
827 if (out == NULL || curve == NULL || (data_len != 0u && data == NULL)) {
833 for (info_counter = 0; info_counter < 256; ++info_counter) {
835 uint64_t x_candidate[5];
840#if PURIFY_USE_LEGACY_FIELD_HASHES
841 ok = purify_curve_hash_to_int_hkdf_u320(value, data, data_len, range, (
unsigned char)info_counter);
849 purify_u320_shifted_right(x_candidate, value, 1u);
866 if (purify_u320_bit(value, 0u) != 0) {
876 uint64_t upper_bound[8];
878 return purify_u512_compare(value, upper_bound) < 0;
882 uint64_t upper_bound[8];
884 return purify_u512_compare(value, upper_bound) < 0;
888 uint64_t denominator[8];
889 uint64_t quotient[8];
890 uint64_t remainder[8];
897 purify_u256_set_zero(first);
898 purify_u256_set_zero(second);
921#if defined(PURIFY_VALGRIND_TESTING) || defined(PURIFY_CBMC_TESTING)
922void purify_curve_unpack_secret_unchecked(uint64_t first[4], uint64_t second[4],
const uint64_t value[8]) {
928 uint64_t denominator[8];
929 uint64_t quotient[8];
930 uint64_t remainder[8];
950 purify_u512_try_add(out, wide_x1);
991 if ((out_len != 0 && out_bits == NULL) || purify_u256_is_zero(value) != 0 || purify_u256_compare(value, max_value) > 0) {
995 bits = purify_u256_bit_length(max_value);
996 if (out_len < bits) {
1001 purify_u256_try_sub(copy, (
const uint64_t[4]){UINT64_C(1), UINT64_C(0), UINT64_C(0), UINT64_C(0)});
1002 for (i = 0; i < bits; ++i) {
1003 out_bits[i] = purify_u256_bit(copy, i) != 0 ? 1 : 0;
1005 for (i = 3; i < bits; i += 3) {
1006 int flip = 1 - out_bits[i];
1007 out_bits[i - 1] ^= flip;
1008 out_bits[i - 2] ^= flip;
static void purify_curve_complete_swap(purify_complete_projective_point *lhs, purify_complete_projective_point *rhs, int flag)
static const uint64_t kPurifyFieldDi[4]
void purify_curve_half_n1(uint64_t out[4])
int purify_curve_is_x_coord(const purify_curve *curve, const purify_fe *x)
void purify_curve_jacobian_infinity(purify_jacobian_point *out)
void purify_curve_pack_public(uint64_t out[8], const uint64_t x1[4], const uint64_t x2[4])
int purify_curve_is_valid_public_key(const uint64_t value[8])
static const char kPurifyHashToCurveTag[]
void purify_curve_order_n2(uint64_t out[4])
static purify_complete_projective_point purify_curve_complete_add(const purify_curve *curve, const purify_complete_projective_point *lhs, const purify_complete_projective_point *rhs)
static const uint64_t kPurifyOrderN1[4]
void purify_curve_packed_public_key_space_size(uint64_t out[8])
static void purify_curve_tag_hash(unsigned char out[32])
static void purify_curve_unpack_secret_from_valid(uint64_t first[4], uint64_t second[4], const uint64_t value[8])
static purify_complete_projective_point purify_curve_complete_double(const purify_curve *curve, const purify_complete_projective_point *point)
void purify_curve_order_n1(uint64_t out[4])
void purify_curve_packed_secret_key_space_size(uint64_t out[8])
int purify_curve_unpack_public(uint64_t first[4], uint64_t second[4], const uint64_t value[8])
void purify_curve_double(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *point)
int purify_curve_key_to_bits(int *out_bits, size_t out_len, const uint64_t value[4], const uint64_t max_value[4])
static void purify_curve_complete_assign(purify_complete_projective_point *dst, const purify_complete_projective_point *src, int flag)
void purify_curve_field_a(purify_fe *out)
void purify_curve_two_p(uint64_t out[5])
void purify_curve_negate(purify_jacobian_point *out, const purify_jacobian_point *point)
void purify_curve_half_n2(uint64_t out[4])
int purify_curve_lift_x(purify_jacobian_point *out, const purify_curve *curve, const purify_fe *x)
int purify_curve_is_valid_secret_key(const uint64_t value[8])
void purify_curve_combine(purify_fe *out, const purify_fe *x1, const purify_fe *x2)
void purify_curve_field_di(purify_fe *out)
void purify_curve_field_d(purify_fe *out)
int purify_curve_hash_to_curve(purify_jacobian_point *out, const purify_curve *curve, const unsigned char *data, size_t data_len)
void purify_curve_field_b(purify_fe *out)
static const uint64_t kPurifyHalfN1[4]
int purify_curve_mul_secret_affine(purify_affine_point *out, const purify_curve *curve, const purify_jacobian_point *point, const uint64_t scalar[4])
void purify_curve_mul(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *point, const uint64_t scalar[4])
static const uint64_t kPurifyOrderN2[4]
void purify_curve_add(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *lhs, const purify_jacobian_point *rhs)
static void purify_curve_mul_secret_ladder_core(purify_complete_projective_point *out, const purify_curve *curve, const purify_jacobian_point *point, const uint64_t scalar[4])
static purify_complete_projective_point purify_curve_complete_identity(void)
static const uint64_t kPurifyHalfN2[4]
static purify_complete_projective_point purify_curve_secret_input_point(const purify_curve *curve, const purify_jacobian_point *point)
static void purify_curve_u256_narrow_u512_unchecked(uint64_t out[4], const uint64_t value[8])
void purify_curve_add_mixed(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *lhs, const purify_affine_point *rhs)
static void purify_curve_secure_clear(void *data, size_t size)
void purify_curve_affine(purify_affine_point *out, const purify_curve *curve, const purify_jacobian_point *point)
static void purify_curve_u256_add_one_unchecked(uint64_t value[4])
void purify_curve_prime_p(uint64_t out[4])
static const uint64_t kPurifyPrimeP[4]
int purify_curve_unpack_secret(uint64_t first[4], uint64_t second[4], const uint64_t value[8])
static int purify_curve_hash_to_int_tagged_u320(uint64_t out[5], const unsigned char *data, size_t data_len, const uint64_t range[5], unsigned char info_byte)
static void purify_curve_u64_to_be(unsigned char out[8], uint64_t value)
static void purify_curve_copy_u256(uint64_t out[4], const uint64_t value[4])
int purify_fe_legendre_symbol(const purify_fe *value)
void purify_fe_set_zero(purify_fe *out)
int purify_fe_set_u256(purify_fe *out, const uint64_t value[4])
void purify_fe_inverse(purify_fe *out, const purify_fe *value)
int purify_fe_sqrt(purify_fe *out, const purify_fe *value)
int purify_fe_is_zero(const purify_fe *value)
int purify_fe_is_one(const purify_fe *value)
void purify_fe_inverse_var(purify_fe *out, const purify_fe *value)
void purify_fe_mul(purify_fe *out, const purify_fe *lhs, const purify_fe *rhs)
void purify_fe_add(purify_fe *out, const purify_fe *lhs, const purify_fe *rhs)
void purify_fe_sub(purify_fe *out, const purify_fe *lhs, const purify_fe *rhs)
void purify_fe_cmov(purify_fe *dst, const purify_fe *src, int flag)
int purify_fe_eq(const purify_fe *lhs, const purify_fe *rhs)
void purify_fe_set_u64(purify_fe *out, uint64_t value)
void purify_fe_negate(purify_fe *out, const purify_fe *value)
int purify_sha256_many(unsigned char output32[32], const unsigned char *const *items, const size_t *item_lens, size_t items_count)
Computes SHA-256 over a set of byte strings.
void purify_sha256(unsigned char output32[32], const unsigned char *data, size_t data_len)
Computes SHA-256 over a byte string.
void purify_hmac_sha256(unsigned char output32[32], const unsigned char *key, size_t key_len, const unsigned char *data, size_t data_len)
Computes HMAC-SHA256 over a byte string.
int purify_u256_try_narrow_u512(uint64_t out[4], const uint64_t value[8])
void purify_u512_widen_u256(uint64_t out[8], const uint64_t value[4])
void purify_u320_widen_u256(uint64_t out[5], const uint64_t value[4])
void purify_u512_multiply_u256(uint64_t out[8], const uint64_t lhs[4], const uint64_t rhs[4])
int purify_u512_try_divmod_same(uint64_t quotient[8], uint64_t remainder[8], const uint64_t numerator[8], const uint64_t denominator[8])
int purify_u256_try_narrow_u320(uint64_t out[4], const uint64_t value[5])
int purify_u512_try_divmod_same_consttime(uint64_t quotient[8], uint64_t remainder[8], const uint64_t numerator[8], const uint64_t denominator[8])
int PURIFY_UINT_FN bit(const uint64_t value[PURIFY_UINT_WORDS], size_t index)