Coverage Report

Created: 2026-11-15 06:55

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/nss/lib/freebl/verified/Hacl_Curve25519_51.c
Line
Count
Source
1
/* MIT License
2
 *
3
 * Copyright (c) 2016-2022 INRIA, CMU and Microsoft Corporation
4
 * Copyright (c) 2022-2023 HACL* Contributors
5
 *
6
 * Permission is hereby granted, free of charge, to any person obtaining a copy
7
 * of this software and associated documentation files (the "Software"), to deal
8
 * in the Software without restriction, including without limitation the rights
9
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10
 * copies of the Software, and to permit persons to whom the Software is
11
 * furnished to do so, subject to the following conditions:
12
 *
13
 * The above copyright notice and this permission notice shall be included in all
14
 * copies or substantial portions of the Software.
15
 *
16
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22
 * SOFTWARE.
23
 */
24
25
26
#include "internal/Hacl_Curve25519_51.h"
27
28
#include "internal/Hacl_Krmllib.h"
29
#include "internal/Hacl_Bignum25519_51.h"
30
31
static const uint8_t g25519[32U] = { (uint8_t)9U };
32
33
static void point_add_and_double(uint64_t *q, uint64_t *p01_tmp1, FStar_UInt128_uint128 *tmp2)
34
6.52M
{
35
6.52M
  uint64_t *nq = p01_tmp1;
36
6.52M
  uint64_t *nq_p1 = p01_tmp1 + (uint32_t)10U;
37
6.52M
  uint64_t *tmp1 = p01_tmp1 + (uint32_t)20U;
38
6.52M
  uint64_t *x1 = q;
39
6.52M
  uint64_t *x2 = nq;
40
6.52M
  uint64_t *z2 = nq + (uint32_t)5U;
41
6.52M
  uint64_t *z3 = nq_p1 + (uint32_t)5U;
42
6.52M
  uint64_t *a = tmp1;
43
6.52M
  uint64_t *b = tmp1 + (uint32_t)5U;
44
6.52M
  uint64_t *ab = tmp1;
45
6.52M
  uint64_t *dc = tmp1 + (uint32_t)10U;
46
6.52M
  Hacl_Impl_Curve25519_Field51_fadd(a, x2, z2);
47
6.52M
  Hacl_Impl_Curve25519_Field51_fsub(b, x2, z2);
48
6.52M
  uint64_t *x3 = nq_p1;
49
6.52M
  uint64_t *z31 = nq_p1 + (uint32_t)5U;
50
6.52M
  uint64_t *d0 = dc;
51
6.52M
  uint64_t *c0 = dc + (uint32_t)5U;
52
6.52M
  Hacl_Impl_Curve25519_Field51_fadd(c0, x3, z31);
53
6.52M
  Hacl_Impl_Curve25519_Field51_fsub(d0, x3, z31);
54
6.52M
  Hacl_Impl_Curve25519_Field51_fmul2(dc, dc, ab, tmp2);
55
6.52M
  Hacl_Impl_Curve25519_Field51_fadd(x3, d0, c0);
56
6.52M
  Hacl_Impl_Curve25519_Field51_fsub(z31, d0, c0);
57
6.52M
  uint64_t *a1 = tmp1;
58
6.52M
  uint64_t *b1 = tmp1 + (uint32_t)5U;
59
6.52M
  uint64_t *d = tmp1 + (uint32_t)10U;
60
6.52M
  uint64_t *c = tmp1 + (uint32_t)15U;
61
6.52M
  uint64_t *ab1 = tmp1;
62
6.52M
  uint64_t *dc1 = tmp1 + (uint32_t)10U;
63
6.52M
  Hacl_Impl_Curve25519_Field51_fsqr2(dc1, ab1, tmp2);
64
6.52M
  Hacl_Impl_Curve25519_Field51_fsqr2(nq_p1, nq_p1, tmp2);
65
6.52M
  a1[0U] = c[0U];
66
6.52M
  a1[1U] = c[1U];
67
6.52M
  a1[2U] = c[2U];
68
6.52M
  a1[3U] = c[3U];
69
6.52M
  a1[4U] = c[4U];
70
6.52M
  Hacl_Impl_Curve25519_Field51_fsub(c, d, c);
71
6.52M
  Hacl_Impl_Curve25519_Field51_fmul1(b1, c, (uint64_t)121665U);
72
6.52M
  Hacl_Impl_Curve25519_Field51_fadd(b1, b1, d);
73
6.52M
  Hacl_Impl_Curve25519_Field51_fmul2(nq, dc1, ab1, tmp2);
74
6.52M
  Hacl_Impl_Curve25519_Field51_fmul(z3, z3, x1, tmp2);
75
6.52M
}
76
77
static void point_double(uint64_t *nq, uint64_t *tmp1, FStar_UInt128_uint128 *tmp2)
78
77.6k
{
79
77.6k
  uint64_t *x2 = nq;
80
77.6k
  uint64_t *z2 = nq + (uint32_t)5U;
81
77.6k
  uint64_t *a = tmp1;
82
77.6k
  uint64_t *b = tmp1 + (uint32_t)5U;
83
77.6k
  uint64_t *d = tmp1 + (uint32_t)10U;
84
77.6k
  uint64_t *c = tmp1 + (uint32_t)15U;
85
77.6k
  uint64_t *ab = tmp1;
86
77.6k
  uint64_t *dc = tmp1 + (uint32_t)10U;
87
77.6k
  Hacl_Impl_Curve25519_Field51_fadd(a, x2, z2);
88
77.6k
  Hacl_Impl_Curve25519_Field51_fsub(b, x2, z2);
89
77.6k
  Hacl_Impl_Curve25519_Field51_fsqr2(dc, ab, tmp2);
90
77.6k
  a[0U] = c[0U];
91
77.6k
  a[1U] = c[1U];
92
77.6k
  a[2U] = c[2U];
93
77.6k
  a[3U] = c[3U];
94
77.6k
  a[4U] = c[4U];
95
77.6k
  Hacl_Impl_Curve25519_Field51_fsub(c, d, c);
96
77.6k
  Hacl_Impl_Curve25519_Field51_fmul1(b, c, (uint64_t)121665U);
97
77.6k
  Hacl_Impl_Curve25519_Field51_fadd(b, b, d);
98
77.6k
  Hacl_Impl_Curve25519_Field51_fmul2(nq, dc, ab, tmp2);
99
77.6k
}
100
101
static void montgomery_ladder(uint64_t *out, uint8_t *key, uint64_t *init)
102
25.8k
{
103
25.8k
  FStar_UInt128_uint128 tmp2[10U];
104
284k
  for (uint32_t _i = 0U; _i < (uint32_t)10U; ++_i)
105
258k
    tmp2[_i] = FStar_UInt128_uint64_to_uint128((uint64_t)0U);
106
25.8k
  uint64_t p01_tmp1_swap[41U] = { 0U };
107
25.8k
  uint64_t *p0 = p01_tmp1_swap;
108
25.8k
  uint64_t *p01 = p01_tmp1_swap;
109
25.8k
  uint64_t *p03 = p01;
110
25.8k
  uint64_t *p11 = p01 + (uint32_t)10U;
111
25.8k
  memcpy(p11, init, (uint32_t)10U * sizeof (uint64_t));
112
25.8k
  uint64_t *x0 = p03;
113
25.8k
  uint64_t *z0 = p03 + (uint32_t)5U;
114
25.8k
  x0[0U] = (uint64_t)1U;
115
25.8k
  x0[1U] = (uint64_t)0U;
116
25.8k
  x0[2U] = (uint64_t)0U;
117
25.8k
  x0[3U] = (uint64_t)0U;
118
25.8k
  x0[4U] = (uint64_t)0U;
119
25.8k
  z0[0U] = (uint64_t)0U;
120
25.8k
  z0[1U] = (uint64_t)0U;
121
25.8k
  z0[2U] = (uint64_t)0U;
122
25.8k
  z0[3U] = (uint64_t)0U;
123
25.8k
  z0[4U] = (uint64_t)0U;
124
25.8k
  uint64_t *p01_tmp1 = p01_tmp1_swap;
125
25.8k
  uint64_t *p01_tmp11 = p01_tmp1_swap;
126
25.8k
  uint64_t *nq1 = p01_tmp1_swap;
127
25.8k
  uint64_t *nq_p11 = p01_tmp1_swap + (uint32_t)10U;
128
25.8k
  uint64_t *swap = p01_tmp1_swap + (uint32_t)40U;
129
25.8k
  Hacl_Impl_Curve25519_Field51_cswap2((uint64_t)1U, nq1, nq_p11);
130
25.8k
  point_add_and_double(init, p01_tmp11, tmp2);
131
25.8k
  swap[0U] = (uint64_t)1U;
132
6.52M
  for (uint32_t i = (uint32_t)0U; i < (uint32_t)251U; i++)
133
6.49M
  {
134
6.49M
    uint64_t *p01_tmp12 = p01_tmp1_swap;
135
6.49M
    uint64_t *swap1 = p01_tmp1_swap + (uint32_t)40U;
136
6.49M
    uint64_t *nq2 = p01_tmp12;
137
6.49M
    uint64_t *nq_p12 = p01_tmp12 + (uint32_t)10U;
138
6.49M
    uint64_t
139
6.49M
    bit =
140
6.49M
      (uint64_t)(key[((uint32_t)253U - i)
141
6.49M
      / (uint32_t)8U]
142
6.49M
      >> ((uint32_t)253U - i) % (uint32_t)8U
143
6.49M
      & (uint8_t)1U);
144
6.49M
    uint64_t sw = swap1[0U] ^ bit;
145
6.49M
    Hacl_Impl_Curve25519_Field51_cswap2(sw, nq2, nq_p12);
146
6.49M
    point_add_and_double(init, p01_tmp12, tmp2);
147
6.49M
    swap1[0U] = bit;
148
6.49M
  }
149
25.8k
  uint64_t sw = swap[0U];
150
25.8k
  Hacl_Impl_Curve25519_Field51_cswap2(sw, nq1, nq_p11);
151
25.8k
  uint64_t *nq10 = p01_tmp1;
152
25.8k
  uint64_t *tmp1 = p01_tmp1 + (uint32_t)20U;
153
25.8k
  point_double(nq10, tmp1, tmp2);
154
25.8k
  point_double(nq10, tmp1, tmp2);
155
25.8k
  point_double(nq10, tmp1, tmp2);
156
25.8k
  memcpy(out, p0, (uint32_t)10U * sizeof (uint64_t));
157
25.8k
}
158
159
void
160
Hacl_Curve25519_51_fsquare_times(
161
  uint64_t *o,
162
  uint64_t *inp,
163
  FStar_UInt128_uint128 *tmp,
164
  uint32_t n
165
)
166
506k
{
167
506k
  Hacl_Impl_Curve25519_Field51_fsqr(o, inp, tmp);
168
11.5M
  for (uint32_t i = (uint32_t)0U; i < n - (uint32_t)1U; i++)
169
11.0M
  {
170
11.0M
    Hacl_Impl_Curve25519_Field51_fsqr(o, o, tmp);
171
11.0M
  }
172
506k
}
173
174
void Hacl_Curve25519_51_finv(uint64_t *o, uint64_t *i, FStar_UInt128_uint128 *tmp)
175
38.8k
{
176
38.8k
  uint64_t t1[20U] = { 0U };
177
38.8k
  uint64_t *a1 = t1;
178
38.8k
  uint64_t *b1 = t1 + (uint32_t)5U;
179
38.8k
  uint64_t *t010 = t1 + (uint32_t)15U;
180
38.8k
  FStar_UInt128_uint128 *tmp10 = tmp;
181
38.8k
  Hacl_Curve25519_51_fsquare_times(a1, i, tmp10, (uint32_t)1U);
182
38.8k
  Hacl_Curve25519_51_fsquare_times(t010, a1, tmp10, (uint32_t)2U);
183
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(b1, t010, i, tmp);
184
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(a1, b1, a1, tmp);
185
38.8k
  Hacl_Curve25519_51_fsquare_times(t010, a1, tmp10, (uint32_t)1U);
186
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(b1, t010, b1, tmp);
187
38.8k
  Hacl_Curve25519_51_fsquare_times(t010, b1, tmp10, (uint32_t)5U);
188
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(b1, t010, b1, tmp);
189
38.8k
  uint64_t *b10 = t1 + (uint32_t)5U;
190
38.8k
  uint64_t *c10 = t1 + (uint32_t)10U;
191
38.8k
  uint64_t *t011 = t1 + (uint32_t)15U;
192
38.8k
  FStar_UInt128_uint128 *tmp11 = tmp;
193
38.8k
  Hacl_Curve25519_51_fsquare_times(t011, b10, tmp11, (uint32_t)10U);
194
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(c10, t011, b10, tmp);
195
38.8k
  Hacl_Curve25519_51_fsquare_times(t011, c10, tmp11, (uint32_t)20U);
196
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(t011, t011, c10, tmp);
197
38.8k
  Hacl_Curve25519_51_fsquare_times(t011, t011, tmp11, (uint32_t)10U);
198
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(b10, t011, b10, tmp);
199
38.8k
  Hacl_Curve25519_51_fsquare_times(t011, b10, tmp11, (uint32_t)50U);
200
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(c10, t011, b10, tmp);
201
38.8k
  uint64_t *b11 = t1 + (uint32_t)5U;
202
38.8k
  uint64_t *c1 = t1 + (uint32_t)10U;
203
38.8k
  uint64_t *t01 = t1 + (uint32_t)15U;
204
38.8k
  FStar_UInt128_uint128 *tmp1 = tmp;
205
38.8k
  Hacl_Curve25519_51_fsquare_times(t01, c1, tmp1, (uint32_t)100U);
206
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(t01, t01, c1, tmp);
207
38.8k
  Hacl_Curve25519_51_fsquare_times(t01, t01, tmp1, (uint32_t)50U);
208
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(t01, t01, b11, tmp);
209
38.8k
  Hacl_Curve25519_51_fsquare_times(t01, t01, tmp1, (uint32_t)5U);
210
38.8k
  uint64_t *a = t1;
211
38.8k
  uint64_t *t0 = t1 + (uint32_t)15U;
212
38.8k
  Hacl_Impl_Curve25519_Field51_fmul(o, t0, a, tmp);
213
38.8k
}
214
215
static void encode_point(uint8_t *o, uint64_t *i)
216
25.8k
{
217
25.8k
  uint64_t *x = i;
218
25.8k
  uint64_t *z = i + (uint32_t)5U;
219
25.8k
  uint64_t tmp[5U] = { 0U };
220
25.8k
  uint64_t u64s[4U] = { 0U };
221
25.8k
  FStar_UInt128_uint128 tmp_w[10U];
222
284k
  for (uint32_t _i = 0U; _i < (uint32_t)10U; ++_i)
223
258k
    tmp_w[_i] = FStar_UInt128_uint64_to_uint128((uint64_t)0U);
224
25.8k
  Hacl_Curve25519_51_finv(tmp, z, tmp_w);
225
25.8k
  Hacl_Impl_Curve25519_Field51_fmul(tmp, tmp, x, tmp_w);
226
25.8k
  Hacl_Impl_Curve25519_Field51_store_felem(u64s, tmp);
227
25.8k
  KRML_MAYBE_FOR4(i0,
228
25.8k
    (uint32_t)0U,
229
25.8k
    (uint32_t)4U,
230
25.8k
    (uint32_t)1U,
231
25.8k
    store64_le(o + i0 * (uint32_t)8U, u64s[i0]););
232
25.8k
}
233
234
/**
235
Compute the scalar multiple of a point.
236
237
@param out Pointer to 32 bytes of memory, allocated by the caller, where the resulting point is written to.
238
@param priv Pointer to 32 bytes of memory where the secret/private key is read from.
239
@param pub Pointer to 32 bytes of memory where the public point is read from.
240
*/
241
void Hacl_Curve25519_51_scalarmult(uint8_t *out, uint8_t *priv, uint8_t *pub)
242
25.8k
{
243
25.8k
  uint64_t init[10U] = { 0U };
244
25.8k
  uint64_t tmp[4U] = { 0U };
245
25.8k
  KRML_MAYBE_FOR4(i,
246
25.8k
    (uint32_t)0U,
247
25.8k
    (uint32_t)4U,
248
25.8k
    (uint32_t)1U,
249
25.8k
    uint64_t *os = tmp;
250
25.8k
    uint8_t *bj = pub + i * (uint32_t)8U;
251
25.8k
    uint64_t u = load64_le(bj);
252
25.8k
    uint64_t r = u;
253
25.8k
    uint64_t x = r;
254
25.8k
    os[i] = x;);
255
25.8k
  uint64_t tmp3 = tmp[3U];
256
25.8k
  tmp[3U] = tmp3 & (uint64_t)0x7fffffffffffffffU;
257
25.8k
  uint64_t *x = init;
258
25.8k
  uint64_t *z = init + (uint32_t)5U;
259
25.8k
  z[0U] = (uint64_t)1U;
260
25.8k
  z[1U] = (uint64_t)0U;
261
25.8k
  z[2U] = (uint64_t)0U;
262
25.8k
  z[3U] = (uint64_t)0U;
263
25.8k
  z[4U] = (uint64_t)0U;
264
25.8k
  uint64_t f0l = tmp[0U] & (uint64_t)0x7ffffffffffffU;
265
25.8k
  uint64_t f0h = tmp[0U] >> (uint32_t)51U;
266
25.8k
  uint64_t f1l = (tmp[1U] & (uint64_t)0x3fffffffffU) << (uint32_t)13U;
267
25.8k
  uint64_t f1h = tmp[1U] >> (uint32_t)38U;
268
25.8k
  uint64_t f2l = (tmp[2U] & (uint64_t)0x1ffffffU) << (uint32_t)26U;
269
25.8k
  uint64_t f2h = tmp[2U] >> (uint32_t)25U;
270
25.8k
  uint64_t f3l = (tmp[3U] & (uint64_t)0xfffU) << (uint32_t)39U;
271
25.8k
  uint64_t f3h = tmp[3U] >> (uint32_t)12U;
272
25.8k
  x[0U] = f0l;
273
25.8k
  x[1U] = f0h | f1l;
274
25.8k
  x[2U] = f1h | f2l;
275
25.8k
  x[3U] = f2h | f3l;
276
25.8k
  x[4U] = f3h;
277
25.8k
  montgomery_ladder(init, priv, init);
278
25.8k
  encode_point(out, init);
279
25.8k
}
280
281
/**
282
Calculate a public point from a secret/private key.
283
284
This computes a scalar multiplication of the secret/private key with the curve's basepoint.
285
286
@param pub Pointer to 32 bytes of memory, allocated by the caller, where the resulting point is written to.
287
@param priv Pointer to 32 bytes of memory where the secret/private key is read from.
288
*/
289
void Hacl_Curve25519_51_secret_to_public(uint8_t *pub, uint8_t *priv)
290
0
{
291
0
  uint8_t basepoint[32U] = { 0U };
292
0
  for (uint32_t i = (uint32_t)0U; i < (uint32_t)32U; i++)
293
0
  {
294
0
    uint8_t *os = basepoint;
295
0
    uint8_t x = g25519[i];
296
0
    os[i] = x;
297
0
  }
298
0
  Hacl_Curve25519_51_scalarmult(pub, priv, basepoint);
299
0
}
300
301
/**
302
Execute the diffie-hellmann key exchange.
303
304
@param out Pointer to 32 bytes of memory, allocated by the caller, where the resulting point is written to.
305
@param priv Pointer to 32 bytes of memory where **our** secret/private key is read from.
306
@param pub Pointer to 32 bytes of memory where **their** public point is read from.
307
*/
308
bool Hacl_Curve25519_51_ecdh(uint8_t *out, uint8_t *priv, uint8_t *pub)
309
25.8k
{
310
25.8k
  uint8_t zeros[32U] = { 0U };
311
25.8k
  Hacl_Curve25519_51_scalarmult(out, priv, pub);
312
25.8k
  uint8_t res = (uint8_t)255U;
313
854k
  for (uint32_t i = (uint32_t)0U; i < (uint32_t)32U; i++)
314
828k
  {
315
828k
    uint8_t uu____0 = FStar_UInt8_eq_mask(out[i], zeros[i]);
316
828k
    res = uu____0 & res;
317
828k
  }
318
25.8k
  uint8_t z = res;
319
  bool r = z == (uint8_t)255U;
320
25.8k
  return !r;
321
25.8k
}
322