1 /*
2 * This file is part of the openHiTLS project.
3 *
4 * openHiTLS is licensed under the Mulan PSL v2.
5 * You can use this software according to the terms and conditions of the Mulan PSL v2.
6 * You may obtain a copy of Mulan PSL v2 at:
7 *
8 * http://license.coscl.org.cn/MulanPSL2
9 *
10 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
11 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
12 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
13 * See the Mulan PSL v2 for more details.
14 */
15
16 #include "hitls_build.h"
17 #ifdef HITLS_CRYPTO_MLDSA
18 #include "ml_dsa_local.h"
19
20 // mont = 2^32 mod q = -4186625
21 // ZETAS is NIST.FIPS.204 Zetas * mont
22 static const int32_t ZETAS[MLDSA_N] = {
23 0, 25847, -2608894, -518909, 237124, -777960, -876248,
24 466468, 1826347, 2353451, -359251, -2091905, 3119733, -2884855,
25 3111497, 2680103, 2725464, 1024112, -1079900, 3585928, -549488,
26 -1119584, 2619752, -2108549, -2118186, -3859737, -1399561, -3277672,
27 1757237, -19422, 4010497, 280005, 2706023, 95776, 3077325,
28 3530437, -1661693, -3592148, -2537516, 3915439, -3861115, -3043716,
29 3574422, -2867647, 3539968, -300467, 2348700, -539299, -1699267,
30 -1643818, 3505694, -3821735, 3507263, -2140649, -1600420, 3699596,
31 811944, 531354, 954230, 3881043, 3900724, -2556880, 2071892,
32 -2797779, -3930395, -1528703, -3677745, -3041255, -1452451, 3475950,
33 2176455, -1585221, -1257611, 1939314, -4083598, -1000202, -3190144,
34 -3157330, -3632928, 126922, 3412210, -983419, 2147896, 2715295,
35 -2967645, -3693493, -411027, -2477047, -671102, -1228525, -22981,
36 -1308169, -381987, 1349076, 1852771, -1430430, -3343383, 264944,
37 508951, 3097992, 44288, -1100098, 904516, 3958618, -3724342,
38 -8578, 1653064, -3249728, 2389356, -210977, 759969, -1316856,
39 189548, -3553272, 3159746, -1851402, -2409325, -177440, 1315589,
40 1341330, 1285669, -1584928, -812732, -1439742, -3019102, -3881060,
41 -3628969, 3839961, 2091667, 3407706, 2316500, 3817976, -3342478,
42 2244091, -2446433, -3562462, 266997, 2434439, -1235728, 3513181,
43 -3520352, -3759364, -1197226, -3193378, 900702, 1859098, 909542,
44 819034, 495491, -1613174, -43260, -522500, -655327, -3122442,
45 2031748, 3207046, -3556995, -525098, -768622, -3595838, 342297,
46 286988, -2437823, 4108315, 3437287, -3342277, 1735879, 203044,
47 2842341, 2691481, -2590150, 1265009, 4055324, 1247620, 2486353,
48 1595974, -3767016, 1250494, 2635921, -3548272, -2994039, 1869119,
49 1903435, -1050970, -1333058, 1237275, -3318210, -1430225, -451100,
50 1312455, 3306115, -1962642, -1279661, 1917081, -2546312, -1374803,
51 1500165, 777191, 2235880, 3406031, -542412, -2831860, -1671176,
52 -1846953, -2584293, -3724270, 594136, -3776993, -2013608, 2432395,
53 2454455, -164721, 1957272, 3369112, 185531, -1207385, -3183426,
54 162844, 1616392, 3014001, 810149, 1652634, -3694233, -1799107,
55 -3038916, 3523897, 3866901, 269760, 2213111, -975884, 1717735,
56 472078, -426683, 1723600, -1803090, 1910376, -1667432, -1104333,
57 -260646, -3833893, -2939036, -2235985, -420899, -2286327, 183443,
58 -976891, 1612842, -3545687, -554416, 3919660, -48306, -1362209,
59 3937738, 1400424, -846154, 1976782
60 };
61
62 // Referenced from NIST.FIPS.204 Algorithm 49 MontgomeryReduce(a)
MLDSA_MontgomeryReduce(int64_t a)63 int32_t MLDSA_MontgomeryReduce(int64_t a)
64 {
65 int32_t t = (int32_t)(a * MLDSA_QINV);
66 t = (int32_t)((a - (int64_t)t * MLDSA_Q) >> 32); // (a - t * q)/2^32
67 return t;
68 }
69
70 // Algorithm 41 NTT(w)
MLDSA_ComputesNTT(int32_t w[MLDSA_N])71 void MLDSA_ComputesNTT(int32_t w[MLDSA_N])
72 {
73 uint32_t m = 0;
74 for (uint32_t len = MLDSA_N / 2; len > 0; len >>= 1) {
75 for (uint32_t start = 0; start < MLDSA_N;) {
76 m++;
77 int32_t z = ZETAS[m];
78 for (uint32_t j = start; j < start + len; ++j) {
79 int32_t t = MLDSA_MontgomeryReduce((int64_t)z * w[j + len]);
80 w[j + len] = w[j] - t;
81 w[j] = w[j] + t;
82 }
83 start = start + 2 * len;
84 }
85 }
86 }
87
88 // Algorithm 42 NTT^−1(w)
MLDSA_ComputesINVNTT(int32_t w[MLDSA_N])89 void MLDSA_ComputesINVNTT(int32_t w[MLDSA_N])
90 {
91 const int64_t f = 41978; // 41978 is mont^2/256
92 uint32_t m = MLDSA_N;
93 for (uint32_t len = 1; len < MLDSA_N; len <<= 1) {
94 for (uint32_t start = 0; start < MLDSA_N;) {
95 m--;
96 int32_t zeta = -ZETAS[m];
97 for (uint32_t j = start; j < start + len; j++) {
98 int32_t t = w[j];
99 w[j] = t + w[j + len];
100 w[j + len] = t - w[j + len];
101 w[j + len] = MLDSA_MontgomeryReduce((int64_t)zeta * w[j + len]);
102 }
103 start = start + 2 * len;
104 }
105 }
106
107 for (uint32_t j = 0; j < MLDSA_N; j++) {
108 w[j] = MLDSA_MontgomeryReduce((int64_t)f * w[j]);
109 }
110 }
111
112 #endif