Embedded SDK
Embedded SDK
Loading...
Searching...
No Matches
cx_mldsa_lowram.c
Go to the documentation of this file.
1/*****************************************************************************
2 * (c) 2026 Ledger SAS.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *****************************************************************************/
25#ifdef HAVE_MLDSA_OPTIMIZATION
26
27#include <string.h>
28#include "cx_mldsa_lowram.h"
29#include "cx_mldsa_rounding.h"
30#include "cx_mldsa_poly.h"
31#include "cx_mldsa_sample.h"
32#include "cx_mldsa_util.h"
33
37static inline int32_t mldsa_freeze(int32_t a)
38{
40 a = MLDSA_POLY_caddq(a);
41 return a;
42}
43
49static inline int32_t polyt0_unpack_idx(const uint8_t *t0, uint32_t idx)
50{
51 int32_t coeff;
52 const uint8_t *p = t0 + 13U * (idx >> 3U);
53 uint32_t r = idx & 7U;
54
55 switch (r) {
56 case 0U:
57 coeff = (int32_t) p[0];
58 coeff |= (int32_t) ((uint32_t) p[1] << 8U);
59 break;
60 case 1U:
61 coeff = (int32_t) (p[1] >> 5U);
62 coeff |= (int32_t) ((uint32_t) p[2] << 3U);
63 coeff |= (int32_t) ((uint32_t) p[3] << 11U);
64 break;
65 case 2U:
66 coeff = (int32_t) (p[3] >> 2U);
67 coeff |= (int32_t) ((uint32_t) p[4] << 6U);
68 break;
69 case 3U:
70 coeff = (int32_t) (p[4] >> 7U);
71 coeff |= (int32_t) ((uint32_t) p[5] << 1U);
72 coeff |= (int32_t) ((uint32_t) p[6] << 9U);
73 break;
74 case 4U:
75 coeff = (int32_t) (p[6] >> 4U);
76 coeff |= (int32_t) ((uint32_t) p[7] << 4U);
77 coeff |= (int32_t) ((uint32_t) p[8] << 12U);
78 break;
79 case 5U:
80 coeff = (int32_t) (p[8] >> 1U);
81 coeff |= (int32_t) ((uint32_t) p[9] << 7U);
82 break;
83 case 6U:
84 coeff = (int32_t) (p[9] >> 6U);
85 coeff |= (int32_t) ((uint32_t) p[10] << 2U);
86 coeff |= (int32_t) ((uint32_t) p[11] << 10U);
87 break;
88 default: /* case 7 */
89 coeff = (int32_t) (p[11] >> 3U);
90 coeff |= (int32_t) ((uint32_t) p[12] << 5U);
91 break;
92 }
93 coeff &= 0x1FFF;
94 return (1 << (MLDSA_D - 1)) - coeff;
95}
96
102static inline int32_t polyt1_unpack_idx(const uint8_t *t1, uint32_t idx)
103{
104 int32_t coeff;
105 const uint8_t *p = t1 + 5U * (idx >> 2U);
106 uint32_t r = idx & 3U;
107
108 switch (r) {
109 case 0U:
110 coeff = (int32_t) p[0];
111 coeff |= (int32_t) ((uint32_t) p[1] << 8U);
112 break;
113 case 1U:
114 coeff = (int32_t) (p[1] >> 2U);
115 coeff |= (int32_t) ((uint32_t) p[2] << 6U);
116 break;
117 case 2U:
118 coeff = (int32_t) (p[2] >> 4U);
119 coeff |= (int32_t) ((uint32_t) p[3] << 4U);
120 break;
121 default: /* case 3 */
122 coeff = (int32_t) (p[3] >> 6U);
123 coeff |= (int32_t) ((uint32_t) p[4] << 2U);
124 break;
125 }
126 coeff &= 0x3FF;
127 return coeff;
128}
129
130/*********************
131 * COMPRESSED W OPS
132 *********************/
133
134void MLDSA_LOWRAM_polyw_pack(uint8_t buf[MLDSA_WCOMP_BYTES], const mldsa_poly *w)
135{
136 for (uint32_t i = 0U; i < MLDSA_N; i++) {
137 int32_t c = mldsa_freeze(w->coeffs[i]);
138 buf[i * 3U + 0U] = (uint8_t) c;
139 buf[i * 3U + 1U] = (uint8_t) (c >> 8U);
140 buf[i * 3U + 2U] = (uint8_t) (c >> 16U);
141 }
142}
143
144void MLDSA_LOWRAM_polyw_unpack(mldsa_poly *w, const uint8_t buf[MLDSA_WCOMP_BYTES])
145{
146 for (uint32_t i = 0U; i < MLDSA_N; i++) {
147 w->coeffs[i] = (int32_t) buf[i * 3U + 0U];
148 w->coeffs[i] |= (int32_t) ((uint32_t) buf[i * 3U + 1U] << 8U);
149 w->coeffs[i] |= (int32_t) ((uint32_t) buf[i * 3U + 2U] << 16U);
150 }
151}
152
153void MLDSA_LOWRAM_polyw_add_idx(uint8_t buf[MLDSA_WCOMP_BYTES], int32_t a, uint32_t idx)
154{
155 int32_t coeff;
156 coeff = (int32_t) buf[idx * 3U + 0U];
157 coeff |= (int32_t) ((uint32_t) buf[idx * 3U + 1U] << 8U);
158 coeff |= (int32_t) ((uint32_t) buf[idx * 3U + 2U] << 16U);
159
160 coeff += a;
161 coeff = mldsa_freeze(coeff);
162
163 buf[idx * 3U + 0U] = (uint8_t) coeff;
164 buf[idx * 3U + 1U] = (uint8_t) (coeff >> 8U);
165 buf[idx * 3U + 2U] = (uint8_t) (coeff >> 16U);
166}
167
168void MLDSA_LOWRAM_polyw_sub(mldsa_poly *c,
169 const uint8_t buf[MLDSA_WCOMP_BYTES],
170 const mldsa_poly *a)
171{
172 for (uint32_t i = 0U; i < MLDSA_N; i++) {
173 int32_t coeff;
174 coeff = (int32_t) buf[i * 3U + 0U];
175 coeff |= (int32_t) ((uint32_t) buf[i * 3U + 1U] << 8U);
176 coeff |= (int32_t) ((uint32_t) buf[i * 3U + 2U] << 16U);
177 c->coeffs[i] = coeff - a->coeffs[i];
178 }
179}
180
181/*********************
182 * CHALLENGE COMPRESS
183 *********************/
184
185void MLDSA_LOWRAM_challenge_compress(uint8_t ccomp[MLDSA_CCOMP_BYTES],
186 const mldsa_poly *cp,
187 uint8_t tau)
188{
189 uint64_t signs = 0U;
190 uint64_t mask = 1U;
191 uint32_t pos = 0U;
192
193 memset(ccomp, 0, MLDSA_CCOMP_BYTES);
194
195 for (uint32_t i = 0U; i < MLDSA_N; i++) {
196 if (cp->coeffs[i] != 0) {
197 ccomp[pos++] = (uint8_t) i;
198 if (cp->coeffs[i] == -1) {
199 signs |= mask;
200 }
201 mask <<= 1U;
202 }
203 }
204 (void) tau; // pos should equal tau
205
206 for (uint32_t i = 0U; i < 8U; i++) {
207 ccomp[60U + i] = (uint8_t) (signs >> (8U * i));
208 }
209}
210
211void MLDSA_LOWRAM_challenge_decompress(mldsa_poly *cp,
212 const uint8_t ccomp[MLDSA_CCOMP_BYTES],
213 uint8_t tau)
214{
215 uint64_t signs = 0U;
216
217 for (uint32_t i = 0U; i < MLDSA_N; i++) {
218 cp->coeffs[i] = 0;
219 }
220 for (uint32_t i = 0U; i < 8U; i++) {
221 signs |= ((uint64_t) ccomp[60U + i]) << (8U * i);
222 }
223 for (uint32_t i = 0U; i < tau; i++) {
224 uint32_t pos = ccomp[i];
225 if (signs & 1U) {
226 cp->coeffs[pos] = -1;
227 }
228 else {
229 cp->coeffs[pos] = 1;
230 }
231 signs >>= 1U;
232 }
233}
234
235/*********************
236 * SCHOOLBOOK OPS
237 *********************/
238
239void MLDSA_LOWRAM_schoolbook_t0(mldsa_poly *c,
240 const uint8_t ccomp[MLDSA_CCOMP_BYTES],
241 const uint8_t *t0,
242 uint8_t tau)
243{
244 uint64_t signs = 0U;
245
246 for (uint32_t i = 0U; i < MLDSA_N; i++) {
247 c->coeffs[i] = 0;
248 }
249 for (uint32_t i = 0U; i < 8U; i++) {
250 signs |= ((uint64_t) ccomp[60U + i]) << (8U * i);
251 }
252
253 for (uint32_t idx = 0U; idx < tau; idx++) {
254 uint32_t pos = ccomp[idx];
255 int32_t sign = (signs & 1U) ? -1 : 1;
256
257 for (uint32_t j = 0U; pos + j < MLDSA_N; j++) {
258 c->coeffs[pos + j] += sign * polyt0_unpack_idx(t0, j);
259 }
260 for (uint32_t j = MLDSA_N - pos; j < MLDSA_N; j++) {
261 c->coeffs[pos + j - MLDSA_N] -= sign * polyt0_unpack_idx(t0, j);
262 }
263 signs >>= 1U;
264 }
265}
266
267void MLDSA_LOWRAM_schoolbook_t1(mldsa_poly *c,
268 const uint8_t ccomp[MLDSA_CCOMP_BYTES],
269 const uint8_t *t1,
270 uint8_t tau)
271{
272 uint64_t signs = 0U;
273
274 for (uint32_t i = 0U; i < MLDSA_N; i++) {
275 c->coeffs[i] = 0;
276 }
277 for (uint32_t i = 0U; i < 8U; i++) {
278 signs |= ((uint64_t) ccomp[60U + i]) << (8U * i);
279 }
280
281 for (uint32_t idx = 0U; idx < tau; idx++) {
282 uint32_t pos = ccomp[idx];
283 int32_t sign = (signs & 1U) ? -1 : 1;
284
285 for (uint32_t j = 0U; pos + j < MLDSA_N; j++) {
286 c->coeffs[pos + j] += sign * (polyt1_unpack_idx(t1, j) << MLDSA_D);
287 }
288 for (uint32_t j = MLDSA_N - pos; j < MLDSA_N; j++) {
289 c->coeffs[pos + j - MLDSA_N] -= sign * (polyt1_unpack_idx(t1, j) << MLDSA_D);
290 }
291 signs >>= 1U;
292 }
293}
294
295/*********************
296 * FUSED A EXPANSION
297 *********************/
298
305#define LOWRAM_AEXPAND_NBLOCKS 5U
306#define LOWRAM_AEXPAND_BUFSIZE (LOWRAM_AEXPAND_NBLOCKS * 168U)
307
308void MLDSA_LOWRAM_expand_aij_accum(uint8_t wcomp[MLDSA_WCOMP_BYTES],
309 const mldsa_poly *b,
310 const uint8_t rho[MLDSA_SEEDBYTES],
311 uint16_t nonce)
312{
313 uint8_t buf[LOWRAM_AEXPAND_BUFSIZE] = {0};
314 uint32_t ctr = 0U;
315
316 MLDSA_UTIL_shake128_seed_nonce(buf, sizeof(buf), rho, MLDSA_SEEDBYTES, nonce);
317
318 uint32_t pos = 0U;
319 while ((ctr < MLDSA_N) && ((pos + 3U) <= sizeof(buf))) {
320 uint32_t t;
321 t = (uint32_t) buf[pos];
322 t |= (uint32_t) buf[pos + 1U] << 8U;
323 t |= (uint32_t) buf[pos + 2U] << 16U;
324 t &= 0x7FFFFFU;
325 pos += 3U;
326
327 if (t < (uint32_t) MLDSA_Q) {
328 int32_t mont_prod
329 = MLDSA_POLY_montgomery_reduce((int64_t) t * (int64_t) b->coeffs[ctr]);
330 MLDSA_LOWRAM_polyw_add_idx(wcomp, mont_prod, ctr);
331 ctr++;
332 }
333 }
334
335 explicit_bzero(buf, sizeof(buf));
336}
337
338/*********************
339 * HIGHBITS/LOWBITS
340 *********************/
341
342void MLDSA_LOWRAM_poly_highbits(mldsa_poly *a1, const mldsa_poly *a, int32_t gamma2)
343{
344 int32_t a0_dummy;
345 for (uint32_t i = 0U; i < MLDSA_N; i++) {
346 a1->coeffs[i] = MLDSA_ROUNDING_decompose(a->coeffs[i], &a0_dummy, gamma2);
347 }
348}
349
350void MLDSA_LOWRAM_poly_lowbits(mldsa_poly *a0, const mldsa_poly *a, int32_t gamma2)
351{
352 for (uint32_t i = 0U; i < MLDSA_N; i++) {
353 MLDSA_ROUNDING_decompose(a->coeffs[i], &a0->coeffs[i], gamma2);
354 }
355}
356
360static int32_t mldsa_lowram_w1_unpack_idx(const uint8_t *w1_packed, uint32_t i, int32_t gamma2)
361{
362 int32_t w1;
363 if (gamma2 == (MLDSA_Q - 1) / 32) {
364 // 4 bits per coefficient.
365 w1 = (int32_t) ((w1_packed[i >> 1U] >> ((i & 1U) * 4U)) & 0x0FU);
366 }
367 else {
368 // 6 bits per coefficient, 4 coefficients packed in 3 bytes.
369 const uint8_t *q = &w1_packed[(i >> 2U) * 3U];
370 switch (i & 3U) {
371 case 0U:
372 w1 = (int32_t) (q[0] & 0x3FU);
373 break;
374 case 1U:
375 w1 = (int32_t) (((uint32_t) (q[0] >> 6U)) | (((uint32_t) (q[1] & 0x0FU)) << 2U));
376 break;
377 case 2U:
378 w1 = (int32_t) (((uint32_t) (q[1] >> 4U)) | (((uint32_t) (q[2] & 0x03U)) << 4U));
379 break;
380 default:
381 w1 = (int32_t) (q[2] >> 2U);
382 break;
383 }
384 }
385 return w1;
386}
387
388void MLDSA_LOWRAM_poly_r0(mldsa_poly *r0,
389 const uint8_t wcomp[MLDSA_WCOMP_BYTES],
390 const uint8_t *w1_packed,
391 int32_t gamma2)
392{
393 for (uint32_t i = 0U; i < MLDSA_N; i++) {
394 int32_t w_minus_cs2;
395 w_minus_cs2 = (int32_t) wcomp[i * 3U + 0U];
396 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 1U] << 8U);
397 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 2U] << 16U);
398
399 // r0 = LowBits(w) - c*s2 = (w - c*s2) - HighBits(w) * 2 * gamma2.
400 // The high bits are taken from the *original* w (w1_packed), so the
401 // result matches the reference even when w - c*s2 crosses a boundary.
402 int32_t w1 = mldsa_lowram_w1_unpack_idx(w1_packed, i, gamma2);
403 r0->coeffs[i] = MLDSA_POLY_reduce32(w_minus_cs2 - w1 * 2 * gamma2);
404 }
405}
406
407/*********************
408 * HINT OPERATIONS
409 *********************/
410
411uint32_t MLDSA_LOWRAM_make_hint(mldsa_poly *h,
412 const mldsa_poly *ct0,
413 const uint8_t wcomp[MLDSA_WCOMP_BYTES],
414 const uint8_t *w1_packed,
415 int32_t gamma2)
416{
417 uint32_t hints_n = 0U;
418 for (uint32_t i = 0U; i < MLDSA_N; i++) {
419 int32_t w_minus_cs2;
420 w_minus_cs2 = (int32_t) wcomp[i * 3U + 0U];
421 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 1U] << 8U);
422 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 2U] << 16U);
423
424 // w1 = HighBits(w), unpacked from the packed w1 row. The reference uses
425 // the high bits of the *original* w (not w - c*s2): subtracting c*s2 may
426 // cross a gamma2 boundary so HighBits(w - c*s2) != HighBits(w).
427 int32_t w1 = mldsa_lowram_w1_unpack_idx(w1_packed, i, gamma2);
428
429 // a0 = LowBits(w) - c*s2 + c*t0 = (w - c*s2) + c*t0 - w1 * 2 * gamma2.
430 // (w - c*s2) is stored frozen to [0, Q); reduce32 recovers the small
431 // centered representative, which equals the reference a0.
432 int32_t a0 = MLDSA_POLY_reduce32(w_minus_cs2 + ct0->coeffs[i] - w1 * 2 * gamma2);
433
434 h->coeffs[i] = (int32_t) MLDSA_ROUNDING_make_hint(a0, w1, gamma2);
435 if (h->coeffs[i] == 1) {
436 hints_n++;
437 }
438 }
439 return hints_n;
440}
441
442void MLDSA_LOWRAM_use_hint_indices(mldsa_poly *b,
443 const mldsa_poly *a,
444 const uint8_t *h_indices,
445 uint32_t num_hints,
446 int32_t gamma2)
447{
448 for (uint32_t i = 0U; i < MLDSA_N; i++) {
449 uint32_t in_list = 0U;
450 for (uint32_t hidx = 0U; hidx < num_hints; hidx++) {
451 if (i == h_indices[hidx]) {
452 in_list = 1U;
453 break;
454 }
455 }
456 b->coeffs[i] = MLDSA_ROUNDING_use_hint(a->coeffs[i], in_list, gamma2);
457 }
458}
459
460/*********************
461 * STREAMING GAMMA1
462 *********************/
463
464void MLDSA_LOWRAM_sample_gamma1(mldsa_poly *a,
465 const uint8_t seed[MLDSA_CRHBYTES],
466 uint16_t nonce,
467 int32_t gamma1)
468{
469 MLDSA_SAMPLE_gamma1(a, seed, nonce, gamma1);
470}
471
472void MLDSA_LOWRAM_sample_gamma1_add(mldsa_poly *a,
473 const mldsa_poly *b,
474 const uint8_t seed[MLDSA_CRHBYTES],
475 uint16_t nonce,
476 int32_t gamma1)
477{
478 // gamma1 = 2^17 => 18 bits/coeff => 576 bytes.
479 // gamma1 = 2^19 => 20 bits/coeff => 640 bytes.
480 uint8_t buf[640U];
481 size_t buflen = (gamma1 == (1 << 17)) ? 576U : 640U;
482
483 MLDSA_UTIL_shake256_seed_nonce(buf, buflen, seed, MLDSA_CRHBYTES, nonce);
484
485 if (gamma1 == (1 << 17)) {
486 for (uint32_t i = 0U; i < MLDSA_N / 4U; i++) {
487 uint32_t t0, t1, t2, t3;
488 t0 = (uint32_t) buf[9U * i + 0U] | ((uint32_t) buf[9U * i + 1U] << 8U)
489 | ((uint32_t) buf[9U * i + 2U] << 16U);
490 t0 &= 0x3FFFFU;
491 t1 = ((uint32_t) buf[9U * i + 2U] >> 2U) | ((uint32_t) buf[9U * i + 3U] << 6U)
492 | ((uint32_t) buf[9U * i + 4U] << 14U);
493 t1 &= 0x3FFFFU;
494 t2 = ((uint32_t) buf[9U * i + 4U] >> 4U) | ((uint32_t) buf[9U * i + 5U] << 4U)
495 | ((uint32_t) buf[9U * i + 6U] << 12U);
496 t2 &= 0x3FFFFU;
497 t3 = ((uint32_t) buf[9U * i + 6U] >> 6U) | ((uint32_t) buf[9U * i + 7U] << 2U)
498 | ((uint32_t) buf[9U * i + 8U] << 10U);
499 t3 &= 0x3FFFFU;
500
501 a->coeffs[4U * i + 0U] = b->coeffs[4U * i + 0U] + gamma1 - (int32_t) t0;
502 a->coeffs[4U * i + 1U] = b->coeffs[4U * i + 1U] + gamma1 - (int32_t) t1;
503 a->coeffs[4U * i + 2U] = b->coeffs[4U * i + 2U] + gamma1 - (int32_t) t2;
504 a->coeffs[4U * i + 3U] = b->coeffs[4U * i + 3U] + gamma1 - (int32_t) t3;
505 }
506 }
507 else {
508 for (uint32_t i = 0U; i < MLDSA_N / 2U; i++) {
509 uint32_t t0, t1;
510 t0 = (uint32_t) buf[5U * i + 0U] | ((uint32_t) buf[5U * i + 1U] << 8U)
511 | ((uint32_t) buf[5U * i + 2U] << 16U);
512 t0 &= 0xFFFFFU;
513 t1 = ((uint32_t) buf[5U * i + 2U] >> 4U) | ((uint32_t) buf[5U * i + 3U] << 4U)
514 | ((uint32_t) buf[5U * i + 4U] << 12U);
515 t1 &= 0xFFFFFU;
516
517 a->coeffs[2U * i + 0U] = b->coeffs[2U * i + 0U] + gamma1 - (int32_t) t0;
518 a->coeffs[2U * i + 1U] = b->coeffs[2U * i + 1U] + gamma1 - (int32_t) t1;
519 }
520 }
521
522 explicit_bzero(buf, sizeof(buf));
523}
524
525#endif /* HAVE_MLDSA_OPTIMIZATION */
ML-DSA low-RAM helper functions.
int32_t MLDSA_POLY_caddq(int32_t a)
Adds q if input is negative.
int32_t MLDSA_POLY_montgomery_reduce(int64_t a)
Montgomery reduction: given a 64-bit integer, compute a*q^{-1} mod 2^32.
int32_t MLDSA_POLY_reduce32(int32_t a)
Reduce coefficient to representative in about (-6283009, 6283009).
int32_t MLDSA_ROUNDING_decompose(int32_t a, int32_t *a0, int32_t gamma2)
For coefficient a, compute high and low bits a0, a1 such that a mod q = a1*ALPHA + a0,...
uint32_t MLDSA_ROUNDING_make_hint(int32_t a0, int32_t a1, int32_t gamma2)
Compute hint bit. Returns 1 if adding ct0 to w - ct0 would change the high bits (i....
int32_t MLDSA_ROUNDING_use_hint(int32_t a, uint32_t hint, int32_t gamma2)
Correct high bits using hint.
void MLDSA_SAMPLE_gamma1(mldsa_poly *a, const uint8_t seed[MLDSA_CRHBYTES], uint16_t nonce, int32_t gamma1)
Sample polynomial with coefficients in [-(gamma1-1), gamma1] from SHAKE256(seed||nonce).
void MLDSA_UTIL_shake256_seed_nonce(uint8_t *out, size_t outlen, const uint8_t *seed, size_t seedlen, uint16_t nonce)
SHAKE256 with seed || uint16_t nonce.
void MLDSA_UTIL_shake128_seed_nonce(uint8_t *out, size_t outlen, const uint8_t *seed, size_t seedlen, uint16_t nonce)
SHAKE128 with seed || uint16_t nonce.
#define MLDSA_D
Definition lcx_mldsa.h:39
#define MLDSA_N
Definition lcx_mldsa.h:37
#define MLDSA_SEEDBYTES
Definition lcx_mldsa.h:40
#define MLDSA_CRHBYTES
Definition lcx_mldsa.h:41
#define MLDSA_Q
Definition lcx_mldsa.h:38
Polynomial with MLDSA_N int32_t coefficients.
int32_t coeffs[MLDSA_N]
static nbgl_touchStatePosition_t pos
Definition ux.c:56