Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_crypto/src/pqc/dilithium.rs

53.6 KiB, 63 runs

created by r1870400018:236, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! # Crystals-Dilithium
2//! This is a pure rust implementation by https://github.com/quininer of the NIST post quantum
3//! cryptography digital signature finalist.
4//!
5//! I have so far collected their implementation files into a single file and added some rough
6//! speed tests to compare with Ed25519 signing, along with one or two top level api tweaks.
7//! Although performance optimisations can be expected, the disparity gave rise to the notion of
8//! using a dual signature scheme in the Ozone database, whereby hashes of items are signed using
9//! the fast Ed25519 algorithm, and a hash of these hashes is signed using Dilithium.
10//!
11
12mod ntt {
13
14 use super::params::*;
15 use super::reduce::montgomery_reduce;
16
17 use itertools::Itertools;
18
19 pub fn ntt(p: &mut [u32; N]) {
20 let mut k = 1;
21 for len in (0..8).map(|level| 1 << level).rev() {
22 for start in Itertools::step(0..N, 2 * len) {
23 let zeta = u64::from(ZETAS[k]);
24 k += 1;
25
26 for j in start..(start + len) {
27 let t = montgomery_reduce(zeta * u64::from(p[j + len]));
28 p[j + len] = p[j] + 2 * Q - t;
29 p[j] += t;
30 }
31 }
32 }
33 }
34
35 pub fn invntt_frominvmont(p: &mut [u32; N]) {
36 const F: u64 = ((MONT * MONT % (Q as u64)) * (Q as u64 - 1) % (Q as u64)) * ((Q as u64 - 1) >> 8) % (Q as u64);
37
38 let mut k = 1;
39 for len in (0..8).map(|level| 1 << level) {
40 for start in Itertools::step(0..N, 2 * len) {
41 let zeta = u64::from(ZETAS_INV[k]);
42 k += 1;
43
44 for j in start..(start + len) {
45 let t = p[j];
46 p[j] += p[j + len];
47 p[j + len] = t + 256 * Q - p[j + len];
48 p[j + len] = montgomery_reduce(zeta * u64::from(p[j + len]));
49 }
50 }
51 }
52
53 for j in 0..N {
54 p[j] = montgomery_reduce(F * u64::from(p[j]));
55 }
56 }
57}
58
59//////////////////////////////////////////////////////////////////////////// Original file packing.rs
60
61mod packing {
62
63 use super::params::*;
64 use super::poly::{
65 self,
66 Poly,
67 };
68 use super::polyvec::{
69 PolyVecL,
70 PolyVecK,
71 };
72
73 use arrayref::{
74 array_ref,
75 array_refs,
76 array_mut_ref,
77 mut_array_refs,
78 };
79
80 pub mod pk {
81 use super::*;
82
83 pub fn pack(pk: &mut [u8; PK_SIZE_PACKED], rho: &[u8; SEEDBYTES], t1: &PolyVecK) {
84 let (rho_bytes, t1s_bytes) = mut_array_refs!(pk, SEEDBYTES, POLT1_SIZE_PACKED * K);
85
86 rho_bytes.clone_from(rho);
87 for i in 0..K {
88 let t1_bytes = array_mut_ref!(t1s_bytes, i * POLT1_SIZE_PACKED, POLT1_SIZE_PACKED);
89 poly::t1_pack(t1_bytes, &t1[i]);
90 }
91 }
92
93 pub fn unpack(pk: &[u8; PK_SIZE_PACKED], rho: &mut [u8; SEEDBYTES], t1: &mut PolyVecK) {
94 let (rho_bytes, t1s_bytes) = array_refs!(pk, SEEDBYTES, POLT1_SIZE_PACKED * K);
95
96 rho.clone_from(rho_bytes);
97 for i in 0..K {
98 let t1_bytes = array_ref!(t1s_bytes, i * POLT1_SIZE_PACKED, POLT1_SIZE_PACKED);
99 poly::t1_unpack(&mut t1[i], t1_bytes);
100 }
101 }
102 }
103
104 pub mod sk {
105 use super::*;
106
107 pub fn pack(
108 sk: &mut [u8; SK_SIZE_PACKED],
109 rho: &[u8; SEEDBYTES],
110 key: &[u8; SEEDBYTES],
111 tr: &[u8; CRHBYTES],
112 s1: &PolyVecL,
113 s2: &PolyVecK,
114 t0: &PolyVecK
115 ) {
116 let (rho_bytes, key_bytes, tr_bytes, s1s_bytes, s2s_bytes, t0s_bytes) =
117 mut_array_refs!(
118 sk,
119 SEEDBYTES, SEEDBYTES, CRHBYTES,
120 POLETA_SIZE_PACKED * L,
121 POLETA_SIZE_PACKED * K,
122 POLT0_SIZE_PACKED * K
123 );
124
125 rho_bytes.clone_from(rho);
126 key_bytes.clone_from(key);
127 tr_bytes.clone_from(tr);
128
129 for i in 0..L {
130 let s1_bytes = array_mut_ref!(s1s_bytes, i * POLETA_SIZE_PACKED, POLETA_SIZE_PACKED);
131 poly::eta_pack(s1_bytes, &s1[i]);
132 }
133 for i in 0..K {
134 let s2_bytes = array_mut_ref!(s2s_bytes, i * POLETA_SIZE_PACKED, POLETA_SIZE_PACKED);
135 poly::eta_pack(s2_bytes, &s2[i]);
136 }
137 for i in 0..K {
138 let t0_bytes = array_mut_ref!(t0s_bytes, i * POLT0_SIZE_PACKED, POLT0_SIZE_PACKED);
139 poly::t0_pack(t0_bytes, &t0[i]);
140 }
141 }
142
143 pub fn unpack(
144 sk: &[u8; SK_SIZE_PACKED],
145 rho: &mut [u8; SEEDBYTES],
146 key: &mut [u8; SEEDBYTES],
147 tr: &mut [u8; CRHBYTES],
148 s1: &mut PolyVecL,
149 s2: &mut PolyVecK,
150 t0: &mut PolyVecK
151 ) {
152 let (rho_bytes, key_bytes, tr_bytes, s1s_bytes, s2s_bytes, t0s_bytes) =
153 array_refs!(
154 sk,
155 SEEDBYTES, SEEDBYTES, CRHBYTES,
156 POLETA_SIZE_PACKED * L,
157 POLETA_SIZE_PACKED * K,
158 POLT0_SIZE_PACKED * K
159 );
160
161 rho.clone_from(rho_bytes);
162 key.clone_from(key_bytes);
163 tr.clone_from(tr_bytes);
164
165 for i in 0..L {
166 let s1_bytes = array_ref!(s1s_bytes, i * POLETA_SIZE_PACKED, POLETA_SIZE_PACKED);
167 poly::eta_unpack(&mut s1[i], s1_bytes);
168 }
169 for i in 0..K {
170 let s2_bytes = array_ref!(s2s_bytes, i * POLETA_SIZE_PACKED, POLETA_SIZE_PACKED);
171 poly::eta_unpack(&mut s2[i], s2_bytes);
172 }
173 for i in 0..K {
174 let t0_bytes = array_ref!(t0s_bytes, i * POLT0_SIZE_PACKED, POLT0_SIZE_PACKED);
175 poly::t0_unpack(&mut t0[i], t0_bytes);
176 }
177 }
178 }
179
180 pub mod sign {
181 use super::*;
182
183 pub fn pack(sign: &mut [u8; SIG_SIZE_PACKED], z: &PolyVecL, h: &PolyVecK,c: &Poly) {
184 let (zs_bytes, h_bytes, c_bytes) =
185 mut_array_refs!(
186 sign,
187 POLZ_SIZE_PACKED * L,
188 OMEGA + K,
189 N / 8 + 8
190 );
191
192 for i in 0..L {
193 let z_bytes = array_mut_ref!(zs_bytes, i * POLZ_SIZE_PACKED, POLZ_SIZE_PACKED);
194 poly::z_pack(z_bytes, &z[i]);
195 }
196
197 let mut k = 0;
198 for i in 0..K {
199 for j in 0..N {
200 if h[i][j] != 0 {
201 h_bytes[k] = j as u8;
202 k += 1;
203 }
204 }
205 h_bytes[OMEGA + i] = k as u8;
206 }
207
208 let mut signs: u64 = 0;
209 let mut mask = 1;
210 for i in 0..(N / 8) {
211 for j in 0..8 {
212 if c[8 * i + j] != 0 {
213 c_bytes[i] |= 1 << j;
214 if c[8 * i + j] == Q - 1 {
215 signs |= mask;
216 }
217 mask <<= 1;
218 }
219 }
220 }
221 for i in 0..8 {
222 c_bytes[N / 8..][i] = (signs >> (8 * i)) as u8;
223 }
224 }
225
226 pub fn unpack(sign: &[u8; SIG_SIZE_PACKED], z: &mut PolyVecL, h: &mut PolyVecK, c: &mut Poly) -> bool {
227 let (zs_bytes, h_bytes, c_bytes) =
228 array_refs!(
229 sign,
230 POLZ_SIZE_PACKED * L,
231 OMEGA + K,
232 N / 8 + 8
233 );
234
235 for i in 0..L {
236 let z_bytes = array_ref!(zs_bytes, i * POLZ_SIZE_PACKED, POLZ_SIZE_PACKED);
237 poly::z_unpack(&mut z[i], z_bytes);
238 }
239
240 // Decode h
241 let mut k = 0;
242 for i in 0..K {
243 if (h_bytes[OMEGA + i] as usize) < k || (h_bytes[OMEGA + i] as usize) > OMEGA {
244 return false;
245 }
246
247 for j in k..(h_bytes[OMEGA + i] as usize) {
248 // Coefficients are ordered for strong unforgeability
249 if j > k && h_bytes[j] <= h_bytes[j - 1] {
250 return false;
251 }
252
253 h[i][h_bytes[j] as usize] = 1;
254 }
255 k = h_bytes[OMEGA + i] as usize;
256 }
257
258 // Extra indices are zero for strong unforgeability
259 if h_bytes[k..OMEGA].iter().any(|&v| v != 0) {
260 return false;
261 }
262
263 let signs = (0..8)
264 .map(|i| u64::from(c_bytes[N / 8 + i]) << (8 * i))
265 .fold(0, |sum, next| sum | next);
266
267 // Extra sign bits are zero for strong unforgeability
268 if signs >> 60 != 0 {
269 return false;
270 }
271
272 let mut mask = 1;
273 for i in 0..(N / 8) {
274 for j in 0..8 {
275 if (c_bytes[i] >> j) & 0x01 != 0 {
276 c[8 * i + j] =
277 if (signs & mask) != 0 { Q - 1 }
278 else { 1 };
279 mask <<= 1;
280 }
281 }
282 }
283
284 true
285 }
286 }
287}
288
289///////////////////////////////////////////////////////////////////////// Original file params.rs
290
291pub mod params {
292 pub const SEEDBYTES : usize = 32;
293 pub const CRHBYTES : usize = 48;
294 pub const N : usize = 256;
295 pub const Q : u32 = 8380417;
296 pub const QBITS : usize = 23;
297 pub const ROOT_OF_UNITY: usize = 1753;
298 pub const D : usize = 14;
299 pub const GAMMA1 : u32 = (Q - 1) / 16;
300 pub const GAMMA2 : u32 = GAMMA1 / 2;
301 pub const ALPHA : u32 = 2 * GAMMA2;
302
303 #[cfg(feature = "mode0")]
304 mod mode {
305 pub const K : usize = 3;
306 pub const L : usize = 2;
307 pub const ETA : u32 = 7;
308 pub const SETABITS: usize = 4;
309 pub const BETA : u32 = 375;
310 pub const OMEGA : usize = 64;
311 }
312
313 #[cfg(feature = "mode1")]
314 mod mode {
315 pub const K : usize = 4;
316 pub const L : usize = 3;
317 pub const ETA : u32 = 6;
318 pub const SETABITS: usize = 4;
319 pub const BETA : u32 = 325;
320 pub const OMEGA : usize = 80;
321 }
322
323 #[cfg(feature = "mode2")]
324 mod mode {
325 pub const K : usize = 5;
326 pub const L : usize = 4;
327 pub const ETA : u32 = 5;
328 pub const SETABITS: usize = 4;
329 pub const BETA : u32 = 275;
330 pub const OMEGA : usize = 96;
331 }
332
333 #[cfg(feature = "mode3")]
334 mod mode {
335 pub const K : usize = 6;
336 pub const L : usize = 5;
337 pub const ETA : u32 = 3;
338 pub const SETABITS: usize = 3;
339 pub const BETA : u32 = 175;
340 pub const OMEGA : usize = 120;
341 }
342
343 pub use self::mode::*;
344
345 pub const POL_SIZE_PACKED : usize = (N * QBITS) / 8;
346 pub const POLT1_SIZE_PACKED : usize = (N * (QBITS - D)) / 8;
347 pub const POLT0_SIZE_PACKED : usize = (N * D) / 8;
348 pub const POLETA_SIZE_PACKED: usize = (N * SETABITS) / 8;
349 pub const POLZ_SIZE_PACKED : usize = (N * (QBITS - 3)) / 8;
350 pub const POLW1_SIZE_PACKED : usize = (N * 4) / 8;
351
352 pub const POLVECK_SIZE_PACKED: usize = K * POL_SIZE_PACKED;
353 pub const POLVECL_SIZE_PACKED: usize = L * POL_SIZE_PACKED;
354 pub const PK_SIZE_PACKED : usize = SEEDBYTES + K * POLT1_SIZE_PACKED;
355 pub const SK_SIZE_PACKED : usize = 2 * SEEDBYTES + (L + K) * POLETA_SIZE_PACKED + CRHBYTES + K * POLT0_SIZE_PACKED;
356 pub const SIG_SIZE_PACKED : usize = L * POLZ_SIZE_PACKED + (OMEGA + K) + (N / 8 + 8);
357
358 pub const PUBLICKEYBYTES: usize = PK_SIZE_PACKED;
359 pub const SECRETKEYBYTES: usize = SK_SIZE_PACKED;
360 pub const BYTES : usize = SIG_SIZE_PACKED;
361
362 pub const MONT: u64 = 4193792;
363 pub const QINV: usize = 4236238847;
364
365 pub const ZETAS: [u32; N] = [0, 25847, 5771523, 7861508, 237124, 7602457, 7504169, 466468, 1826347, 2353451, 8021166, 6288512, 3119733, 5495562, 3111497, 2680103, 2725464, 1024112, 7300517, 3585928, 7830929, 7260833, 2619752, 6271868, 6262231, 4520680, 6980856, 5102745, 1757237, 8360995, 4010497, 280005, 2706023, 95776, 3077325, 3530437, 6718724, 4788269, 5842901, 3915439, 4519302, 5336701, 3574422, 5512770, 3539968, 8079950, 2348700, 7841118, 6681150, 6736599, 3505694, 4558682, 3507263, 6239768, 6779997, 3699596, 811944, 531354, 954230, 3881043, 3900724, 5823537, 2071892, 5582638, 4450022, 6851714, 4702672, 5339162, 6927966, 3475950, 2176455, 6795196, 7122806, 1939314, 4296819, 7380215, 5190273, 5223087, 4747489, 126922, 3412210, 7396998, 2147896, 2715295, 5412772, 4686924, 7969390, 5903370, 7709315, 7151892, 8357436, 7072248, 7998430, 1349076, 1852771, 6949987, 5037034, 264944, 508951, 3097992, 44288, 7280319, 904516, 3958618, 4656075, 8371839, 1653064, 5130689, 2389356, 8169440, 759969, 7063561, 189548, 4827145, 3159746, 6529015, 5971092, 8202977, 1315589, 1341330, 1285669, 6795489, 7567685, 6940675, 5361315, 4499357, 4751448, 3839961, 2091667, 3407706, 2316500, 3817976, 5037939, 2244091, 5933984, 4817955, 266997, 2434439, 7144689, 3513181, 4860065, 4621053, 7183191, 5187039, 900702, 1859098, 909542, 819034, 495491, 6767243, 8337157, 7857917, 7725090, 5257975, 2031748, 3207046, 4823422, 7855319, 7611795, 4784579, 342297, 286988, 5942594, 4108315, 3437287, 5038140, 1735879, 203044, 2842341, 2691481, 5790267, 1265009, 4055324, 1247620, 2486353, 1595974, 4613401, 1250494, 2635921, 4832145, 5386378, 1869119, 1903435, 7329447, 7047359, 1237275, 5062207, 6950192, 7929317, 1312455, 3306115, 6417775, 7100756, 1917081, 5834105, 7005614, 1500165, 777191, 2235880, 3406031, 7838005, 5548557, 6709241, 6533464, 5796124, 4656147, 594136, 4603424, 6366809, 2432395, 2454455, 8215696, 1957272, 3369112, 185531, 7173032, 5196991, 162844, 1616392, 3014001, 810149, 1652634, 4686184, 6581310, 5341501, 3523897, 3866901, 269760, 2213111, 7404533, 1717735, 472078, 7953734, 1723600, 6577327, 1910376, 6712985, 7276084, 8119771, 4546524, 5441381, 6144432, 7959518, 6094090, 183443, 7403526, 1612842, 4834730, 7826001, 3919660, 8332111, 7018208, 3937738, 1400424, 7534263, 1976782];
366 pub const ZETAS_INV: [u32; N] = [0, 6403635, 846154, 6979993, 4442679, 1362209, 48306, 4460757, 554416, 3545687, 6767575, 976891, 8196974, 2286327, 420899, 2235985, 2939036, 3833893, 260646, 1104333, 1667432, 6470041, 1803090, 6656817, 426683, 7908339, 6662682, 975884, 6167306, 8110657, 4513516, 4856520, 3038916, 1799107, 3694233, 6727783, 7570268, 5366416, 6764025, 8217573, 3183426, 1207385, 8194886, 5011305, 6423145, 164721, 5925962, 5948022, 2013608, 3776993, 7786281, 3724270, 2584293, 1846953, 1671176, 2831860, 542412, 4974386, 6144537, 7603226, 6880252, 1374803, 2546312, 6463336, 1279661, 1962642, 5074302, 7067962, 451100, 1430225, 3318210, 7143142, 1333058, 1050970, 6476982, 6511298, 2994039, 3548272, 5744496, 7129923, 3767016, 6784443, 5894064, 7132797, 4325093, 7115408, 2590150, 5688936, 5538076, 8177373, 6644538, 3342277, 4943130, 4272102, 2437823, 8093429, 8038120, 3595838, 768622, 525098, 3556995, 5173371, 6348669, 3122442, 655327, 522500, 43260, 1613174, 7884926, 7561383, 7470875, 6521319, 7479715, 3193378, 1197226, 3759364, 3520352, 4867236, 1235728, 5945978, 8113420, 3562462, 2446433, 6136326, 3342478, 4562441, 6063917, 4972711, 6288750, 4540456, 3628969, 3881060, 3019102, 1439742, 812732, 1584928, 7094748, 7039087, 7064828, 177440, 2409325, 1851402, 5220671, 3553272, 8190869, 1316856, 7620448, 210977, 5991061, 3249728, 6727353, 8578, 3724342, 4421799, 7475901, 1100098, 8336129, 5282425, 7871466, 8115473, 3343383, 1430430, 6527646, 7031341, 381987, 1308169, 22981, 1228525, 671102, 2477047, 411027, 3693493, 2967645, 5665122, 6232521, 983419, 4968207, 8253495, 3632928, 3157330, 3190144, 1000202, 4083598, 6441103, 1257611, 1585221, 6203962, 4904467, 1452451, 3041255, 3677745, 1528703, 3930395, 2797779, 6308525, 2556880, 4479693, 4499374, 7426187, 7849063, 7568473, 4680821, 1600420, 2140649, 4873154, 3821735, 4874723, 1643818, 1699267, 539299, 6031717, 300467, 4840449, 2867647, 4805995, 3043716, 3861115, 4464978, 2537516, 3592148, 1661693, 4849980, 5303092, 8284641, 5674394, 8100412, 4369920, 19422, 6623180, 3277672, 1399561, 3859737, 2118186, 2108549, 5760665, 1119584, 549488, 4794489, 1079900, 7356305, 5654953, 5700314, 5268920, 2884855, 5260684, 2091905, 359251, 6026966, 6554070, 7913949, 876248, 777960, 8143293, 518909, 2608894, 8354570];
367
368}
369
370//////////////////////////////////////////////////////////////////////////////////// Original file poly.rs
371
372mod poly {
373
374 use super::params::*;
375 use super::reduce::{
376 reduce32,
377 montgomery_reduce,
378 freeze as xfreeze,
379 csubq as xcsubq,
380 };
381 use super::rounding;
382 pub use super::ntt::{
383 ntt,
384 invntt_frominvmont as invntt_montgomery,
385 };
386
387 use byteorder::{ ByteOrder, LittleEndian };
388
389 pub type Poly = [u32; N];
390
391 pub fn reduce(a: &mut Poly) {
392 for i in 0..N {
393 a[i] = reduce32(a[i]);
394 }
395 }
396
397 pub fn csubq(a: &mut Poly) {
398 for i in 0..N {
399 a[i] = xcsubq(a[i]);
400 }
401 }
402
403 pub fn freeze(a: &mut Poly) {
404 for i in 0..N {
405 a[i] = xfreeze(a[i]);
406 }
407 }
408
409 pub fn add(c: &mut Poly, a: &Poly, b: &Poly) {
410 for i in 0..N {
411 c[i] = a[i] + b[i];
412 }
413 }
414
415 pub fn add_assign(c: &mut Poly, a: &Poly) {
416 for i in 0..N {
417 c[i] += a[i];
418 }
419 }
420
421 pub fn sub(c: &mut Poly, a: &Poly, b: &Poly) {
422 for i in 0..N {
423 c[i] = a[i] + 2 * Q - b[i];
424 }
425 }
426
427 pub fn shift_left(a: &mut Poly, k: u32) {
428 for i in 0..N {
429 a[i] <<= k;
430 }
431 }
432
433 pub fn pointwise_invmontgomery(c: &mut Poly, a: &Poly, b: &Poly) {
434 for i in 0..N {
435 c[i] = montgomery_reduce(u64::from(a[i]) * u64::from(b[i]));
436 }
437 }
438
439 pub fn power2round(a: &Poly, a0: &mut Poly, a1: &mut Poly) {
440 for i in 0..N {
441 let (x, y) = rounding::power2round(a[i]);
442 a0[i] = x;
443 a1[i] = y;
444 }
445 }
446
447 pub fn decompose(a: &Poly, a0: &mut Poly, a1: &mut Poly) {
448 for i in 0..N {
449 let (x, y) = rounding::decompose(a[i]);
450 a0[i] = x;
451 a1[i] = y;
452 }
453 }
454
455 pub fn make_hint(a: &Poly, b: &Poly, h: &mut Poly) -> usize {
456 let mut s = 0;
457
458 for i in 0..N {
459 h[i] = rounding::make_hint(a[i], b[i]);
460 s += h[i] as usize;
461 }
462
463 s
464 }
465
466 pub fn use_hint(a: &mut Poly, b: &Poly, h: &Poly) {
467 for i in 0..N {
468 a[i] = rounding::use_hint(b[i], h[i]);
469 }
470 }
471
472 pub fn chknorm(a: &Poly, b: u32) -> bool {
473 a.iter()
474 .map(|&a|{
475 let mut t = ((Q - 1) / 2).wrapping_sub(a) as i32;
476 t ^= t >> 31;
477 ((Q - 1) / 2) as i32 - t
478 })
479 .any(|t| t as u32 >= b)
480 }
481
482 pub fn uniform(a: &mut Poly, buf: &[u8]) {
483 let mut ctr = 0;
484 let mut pos = 0;
485
486 while ctr < N {
487 let val = LittleEndian::read_u24(&buf[pos..]) & 0x7f_ffff;
488 pos += 3;
489
490 if val < Q {
491 a[ctr] = val;
492 ctr += 1;
493 }
494 }
495 }
496
497 pub fn uniform_eta(a: &mut Poly, seed: &[u8; SEEDBYTES], nonce: u8) {
498 use digest::{ Input, ExtendableOutput, XofReader };
499 use sha3::Shake256;
500
501 const SHAKE256_RATE: usize = 136;
502
503 fn rej_eta(a: &mut [u32], buf: &[u8]) -> usize {
504 let mut ctr = 0;
505 let mut pos = 0;
506 let len = a.len();
507
508 while ctr < len && pos < buf.len() {
509 let (t0, t1) =
510 if ETA <= 3 { (u32::from(buf[pos] & 0x07), u32::from(buf[pos] >> 5)) }
511 else { (u32::from(buf[pos] & 0x0f), u32::from(buf[pos] >> 4)) };
512 pos += 1;
513
514 if t0 <= 2 * ETA {
515 a[ctr] = Q + ETA - t0;
516 ctr += 1;
517 }
518 if t1 <= 2 * ETA && ctr < len {
519 a[ctr] = Q + ETA - t1;
520 ctr += 1;
521 }
522
523 if pos >= buf.len() {
524 break
525 }
526 }
527
528 ctr
529 }
530
531 let mut outbuf = [0; 2 * SHAKE256_RATE];
532 let mut hasher = Shake256::default();
533 hasher.process(seed);
534 hasher.process(&[nonce]);
535
536 let mut xof = hasher.xof_result();
537 xof.read(&mut outbuf);
538
539 let ctr = rej_eta(a, &outbuf);
540 if ctr < N {
541 xof.read(&mut outbuf[..SHAKE256_RATE]);
542 rej_eta(&mut a[ctr..], &outbuf[..SHAKE256_RATE]);
543 }
544 }
545
546 pub fn uniform_gamma1m1(a: &mut Poly, seed: &[u8; SEEDBYTES], mu: &[u8; CRHBYTES], nonce: u16) {
547 use digest::{ Input, ExtendableOutput, XofReader };
548 use sha3::Shake256;
549
550 const SHAKE256_RATE: usize = 136;
551
552 fn rej_gemma1m1(a: &mut [u32], buf: &[u8]) -> usize {
553 let mut ctr = 0;
554 let mut pos = 0;
555
556 while ctr < a.len() && pos + 5 <= buf.len() {
557 let mut t0 = u32::from(buf[pos]);
558 t0 |= u32::from(buf[pos + 1]) << 8;
559 t0 |= u32::from(buf[pos + 2]) << 16;
560 t0 &= 0xfffff;
561
562 let mut t1 = u32::from(buf[pos + 2]) >> 4;
563 t1 |= u32::from(buf[pos + 3]) << 4;
564 t1 |= u32::from(buf[pos + 4]) << 12;
565
566 pos += 5;
567
568 if t0 <= 2 * GAMMA1 - 2 {
569 a[ctr] = Q + GAMMA1 - 1 - t0;
570 ctr += 1;
571 }
572 if t1 <= 2 * GAMMA1 - 2 && ctr < a.len() {
573 a[ctr] = Q + GAMMA1 - 1 - t1;
574 ctr += 1;
575 }
576
577 if pos > buf.len() - 5 {
578 break
579 }
580 }
581
582 ctr
583 }
584
585 let mut outbuf = [0; 5 * SHAKE256_RATE];
586 let mut nonce_bytes = [0; 2];
587 LittleEndian::write_u16(&mut nonce_bytes, nonce);
588
589 let mut hasher = Shake256::default();
590 hasher.process(seed);
591 hasher.process(mu);
592 hasher.process(&nonce_bytes);
593
594 let mut xof = hasher.xof_result();
595 xof.read(&mut outbuf);
596
597 let ctr = rej_gemma1m1(a, &outbuf);
598 if ctr < N {
599 xof.read(&mut outbuf[..SHAKE256_RATE]);
600 rej_gemma1m1(&mut a[ctr..], &outbuf[..SHAKE256_RATE]);
601 }
602 }
603
604 #[inline]
605 pub fn eta_pack(r: &mut [u8; POLETA_SIZE_PACKED], a: &Poly) {
606 if ETA <= 3 {
607 let mut t = [0; 8];
608 for i in 0..(N / 8) {
609 t[0] = (Q + ETA - a[8*i+0]) as u8;
610 t[1] = (Q + ETA - a[8*i+1]) as u8;
611 t[2] = (Q + ETA - a[8*i+2]) as u8;
612 t[3] = (Q + ETA - a[8*i+3]) as u8;
613 t[4] = (Q + ETA - a[8*i+4]) as u8;
614 t[5] = (Q + ETA - a[8*i+5]) as u8;
615 t[6] = (Q + ETA - a[8*i+6]) as u8;
616 t[7] = (Q + ETA - a[8*i+7]) as u8;
617
618 r[3*i+0] = t[0];
619 r[3*i+0] |= t[1] << 3;
620 r[3*i+0] |= t[2] << 6;
621 r[3*i+1] = t[2] >> 2;
622 r[3*i+1] |= t[3] << 1;
623 r[3*i+1] |= t[4] << 4;
624 r[3*i+1] |= t[5] << 7;
625 r[3*i+2] = t[5] >> 1;
626 r[3*i+2] |= t[6] << 2;
627 r[3*i+2] |= t[7] << 5;
628 }
629 } else {
630 let mut t = [0; 2];
631 for i in 0..(N / 2) {
632 t[0] = (Q + ETA - a[2*i+0]) as u8;
633 t[1] = (Q + ETA - a[2*i+1]) as u8;
634 r[i] = t[0] | (t[1] << 4);
635 }
636 }
637 }
638
639 #[inline]
640 pub fn eta_unpack(r: &mut Poly, a: &[u8; POLETA_SIZE_PACKED]) {
641 if ETA <= 3 {
642 for i in 0..(N / 8) {
643 r[8*i+0] = u32::from(a[3*i+0]) & 0x07;
644 r[8*i+1] = (u32::from(a[3*i+0]) >> 3) & 0x07;
645 r[8*i+2] = (u32::from(a[3*i+0]) >> 6) | ((u32::from(a[3*i+1]) & 0x01) << 2);
646 r[8*i+3] = (u32::from(a[3*i+1]) >> 1) & 0x07;
647 r[8*i+4] = (u32::from(a[3*i+1]) >> 4) & 0x07;
648 r[8*i+5] = (u32::from(a[3*i+1]) >> 7) | ((u32::from(a[3*i+2]) & 0x03) << 1);
649 r[8*i+6] = (u32::from(a[3*i+2]) >> 2) & 0x07;
650 r[8*i+7] = u32::from(a[3*i+2]) >> 5;
651
652 r[8*i+0] = Q + ETA - r[8*i+0];
653 r[8*i+1] = Q + ETA - r[8*i+1];
654 r[8*i+2] = Q + ETA - r[8*i+2];
655 r[8*i+3] = Q + ETA - r[8*i+3];
656 r[8*i+4] = Q + ETA - r[8*i+4];
657 r[8*i+5] = Q + ETA - r[8*i+5];
658 r[8*i+6] = Q + ETA - r[8*i+6];
659 r[8*i+7] = Q + ETA - r[8*i+7];
660 }
661 } else {
662 for i in 0..(N / 2) {
663 r[2*i+0] = u32::from(a[i]) & 0x0F;
664 r[2*i+1] = u32::from(a[i]) >> 4;
665 r[2*i+0] = Q + ETA - r[2*i+0];
666 r[2*i+1] = Q + ETA - r[2*i+1];
667 }
668 }
669 }
670
671 #[inline]
672 pub fn t0_pack(r: &mut [u8], a: &Poly) {
673 let mut t = [0; 4];
674 for i in 0..(N / 4) {
675 t[0] = Q + (1 << (D-1) as u32) - a[4*i+0];
676 t[1] = Q + (1 << (D-1) as u32) - a[4*i+1];
677 t[2] = Q + (1 << (D-1) as u32) - a[4*i+2];
678 t[3] = Q + (1 << (D-1) as u32) - a[4*i+3];
679
680 r[7*i+0] = t[0] as u8;
681 r[7*i+1] = (t[0] >> 8) as u8;
682 r[7*i+1] |= (t[1] << 6) as u8;
683 r[7*i+2] = (t[1] >> 2) as u8;
684 r[7*i+3] = (t[1] >> 10) as u8;
685 r[7*i+3] |= (t[2] << 4) as u8;
686 r[7*i+4] = (t[2] >> 4) as u8;
687 r[7*i+5] = (t[2] >> 12) as u8;
688 r[7*i+5] |= (t[3] << 2) as u8;
689 r[7*i+6] = (t[3] >> 6) as u8;
690 }
691 }
692
693 #[inline]
694 pub fn t0_unpack(r: &mut Poly, a: &[u8]) {
695 for i in 0..(N / 4) {
696 r[4*i+0] = u32::from(a[7*i+0]);
697 r[4*i+0] |= (u32::from(a[7*i+1]) & 0x3F) << 8;
698
699 r[4*i+1] = u32::from(a[7*i+1]) >> 6;
700 r[4*i+1] |= u32::from(a[7*i+2]) << 2;
701 r[4*i+1] |= (u32::from(a[7*i+3]) & 0x0F) << 10;
702
703 r[4*i+2] = u32::from(a[7*i+3]) >> 4;
704 r[4*i+2] |= u32::from(a[7*i+4]) << 4;
705 r[4*i+2] |= (u32::from(a[7*i+5]) & 0x03) << 12;
706
707 r[4*i+3] = u32::from(a[7*i+5]) >> 2;
708 r[4*i+3] |= u32::from(a[7*i+6]) << 6;
709
710 r[4*i+0] = Q + (1 << (D-1) as u32) - r[4*i+0];
711 r[4*i+1] = Q + (1 << (D-1) as u32) - r[4*i+1];
712 r[4*i+2] = Q + (1 << (D-1) as u32) - r[4*i+2];
713 r[4*i+3] = Q + (1 << (D-1) as u32) - r[4*i+3];
714 }
715 }
716
717 #[inline]
718 pub fn t1_pack(r: &mut [u8; POLT1_SIZE_PACKED], a: &Poly) {
719 for i in 0..(N / 8) {
720 r[9*i+0] = ( a[8*i+0] & 0xFF) as u8;
721 r[9*i+1] = ((a[8*i+0] >> 8) | ((a[8*i+1] & 0x7F) << 1)) as u8;
722 r[9*i+2] = ((a[8*i+1] >> 7) | ((a[8*i+2] & 0x3F) << 2)) as u8;
723 r[9*i+3] = ((a[8*i+2] >> 6) | ((a[8*i+3] & 0x1F) << 3)) as u8;
724 r[9*i+4] = ((a[8*i+3] >> 5) | ((a[8*i+4] & 0x0F) << 4)) as u8;
725 r[9*i+5] = ((a[8*i+4] >> 4) | ((a[8*i+5] & 0x07) << 5)) as u8;
726 r[9*i+6] = ((a[8*i+5] >> 3) | ((a[8*i+6] & 0x03) << 6)) as u8;
727 r[9*i+7] = ((a[8*i+6] >> 2) | ((a[8*i+7] & 0x01) << 7)) as u8;
728 r[9*i+8] = ( a[8*i+7] >> 1) as u8;
729 }
730 }
731
732 #[inline]
733 pub fn t1_unpack(r: &mut Poly, a: &[u8; POLT1_SIZE_PACKED]) {
734 for i in 0..(N / 8) {
735 r[8*i+0] = u32::from(a[9*i+0]) | (u32::from(a[9*i+1] & 0x01) << 8);
736 r[8*i+1] = (u32::from(a[9*i+1]) >> 1) | (u32::from(a[9*i+2] & 0x03) << 7);
737 r[8*i+2] = (u32::from(a[9*i+2]) >> 2) | (u32::from(a[9*i+3] & 0x07) << 6);
738 r[8*i+3] = (u32::from(a[9*i+3]) >> 3) | (u32::from(a[9*i+4] & 0x0F) << 5);
739 r[8*i+4] = (u32::from(a[9*i+4]) >> 4) | (u32::from(a[9*i+5] & 0x1F) << 4);
740 r[8*i+5] = (u32::from(a[9*i+5]) >> 5) | (u32::from(a[9*i+6] & 0x3F) << 3);
741 r[8*i+6] = (u32::from(a[9*i+6]) >> 6) | (u32::from(a[9*i+7] & 0x7F) << 2);
742 r[8*i+7] = (u32::from(a[9*i+7]) >> 7) | (u32::from(a[9*i+8] & 0xFF) << 1);
743 }
744 }
745
746 #[inline]
747 pub fn z_pack(r: &mut [u8; POLZ_SIZE_PACKED], a: &Poly) {
748 let mut t = [0; 2];
749 for i in 0..(N / 2) {
750 t[0] = (GAMMA1 - 1).wrapping_sub(a[2*i+0]);
751 t[0] = t[0].wrapping_add(((t[0] as i32) >> 31) as u32 & Q);
752 t[1] = (GAMMA1 - 1).wrapping_sub(a[2*i+1]);
753 t[1] = t[1].wrapping_add(((t[1] as i32) >> 31) as u32 & Q);
754
755 r[5*i+0] = t[0] as u8;
756 r[5*i+1] = (t[0] >> 8) as u8;
757 r[5*i+2] = (t[0] >> 16) as u8;
758 r[5*i+2] |= (t[1] << 4) as u8;
759 r[5*i+3] = (t[1] >> 4) as u8;
760 r[5*i+4] = (t[1] >> 12) as u8;
761 }
762 }
763
764 #[inline]
765 pub fn z_unpack(r: &mut Poly, a: &[u8; POLZ_SIZE_PACKED]) {
766 for i in 0..(N / 2) {
767 r[2*i+0] = u32::from(a[5*i+0]);
768 r[2*i+0] |= u32::from(a[5*i+1]) << 8;
769 r[2*i+0] |= u32::from(a[5*i+2] & 0x0F) << 16;
770
771 r[2*i+1] = u32::from(a[5*i+2]) >> 4;
772 r[2*i+1] |= u32::from(a[5*i+3]) << 4;
773 r[2*i+1] |= u32::from(a[5*i+4]) << 12;
774
775 r[2*i+0] = (GAMMA1 - 1).wrapping_sub(r[2*i+0]);
776 r[2*i+0] = r[2*i+0].wrapping_add(((r[2*i+0] as i32) >> 31) as u32 & Q);
777 r[2*i+1] = (GAMMA1 - 1).wrapping_sub(r[2*i+1]);
778 r[2*i+1] = r[2*i+1].wrapping_add(((r[2*i+1] as i32) >> 31) as u32 & Q);
779 }
780 }
781
782 #[inline]
783 pub fn w1_pack(r: &mut [u8; POLW1_SIZE_PACKED], a: &Poly) {
784 for i in 0..(N / 2) {
785 r[i] = (a[2 * i] | (a[2 * i + 1] << 4)) as u8;
786 }
787 }
788}
789
790///////////////////////////////////////////////////////////////////////////// Original file polyvec.rs
791
792mod polyvec {
793
794 use crate::polyvec;
795 use super::params::*;
796 use super::poly::{
797 self,
798 Poly,
799 };
800
801 polyvec!(PolyVecL, L);
802 polyvec!(PolyVecK, K);
803
804 pub fn pointwise_acc_invmontgomery(w: &mut Poly, u: &PolyVecL, v: &PolyVecL) {
805 let mut t = [0; N];
806
807 poly::pointwise_invmontgomery(w, &u[0], &v[0]);
808
809 for i in 1..L {
810 poly::pointwise_invmontgomery(&mut t, &u[i], &v[i]);
811 poly::add_assign(w, &t);
812 }
813
814 poly::reduce(w);
815 }
816
817 impl PolyVecK {
818 pub fn power2round(&self, v0: &mut Self, v1: &mut Self) {
819 for i in 0..K {
820 poly::power2round(&self[i], &mut v0[i], &mut v1[i]);
821 }
822 }
823
824 pub fn decompose(&self, v0: &mut Self, v1: &mut Self) {
825 for i in 0..K {
826 poly::decompose(&self[i], &mut v0[i], &mut v1[i]);
827 }
828 }
829 }
830
831 pub fn make_hint(h: &mut PolyVecK, u: &PolyVecK, v: &PolyVecK) -> usize {
832 let mut s = 0;
833 for i in 0..K {
834 s += poly::make_hint(&u[i], &v[i], &mut h[i]);
835 }
836 s
837 }
838
839 pub fn use_hint(w: &mut PolyVecK, u: &PolyVecK, h: &PolyVecK) {
840 for i in 0..K {
841 poly::use_hint(&mut w[i], &u[i], &h[i]);
842 }
843 }
844}
845
846///////////////////////////////////////////////////////////////////////////// Original file reduce.rs
847
848mod reduce {
849
850 use super::params::*;
851
852 pub fn montgomery_reduce(a: u64) -> u32 {
853 let mut t = a.wrapping_mul(QINV as u64);
854 t &= (1 << 32) - 1;
855 t *= u64::from(Q);
856 t += a;
857 (t >> 32) as u32
858 }
859
860 pub fn reduce32(mut a: u32) -> u32 {
861 let mut t = a & 0x7f_ffff;
862 a >>= 23;
863 t += (a << 13) - a;
864 t
865 }
866
867 pub fn csubq(mut a: u32) -> u32 {
868 a = a.wrapping_sub(Q as u32);
869 let c = ((a as i32) >> 31) & Q as i32;
870 a.wrapping_add(c as u32)
871 }
872
873 pub fn freeze(a: u32) -> u32 {
874 let a = reduce32(a);
875 let a = csubq(a);
876 a
877 }
878}
879
880//////////////////////////////////////////////////////////////////////////// Original file rounding.rs
881
882mod rounding {
883
884 use super::params::*;
885
886 pub fn power2round(a: u32) -> (u32, u32) {
887 let d = D as u32;
888
889 let mut t = (a & ((1 << d) - 1)) as i32;
890 t -= (1 << (d - 1)) + 1;
891 t += (t >> 31) & (1 << d);
892 t -= (1 << (d - 1)) - 1;
893 (Q.wrapping_add(t as u32), a.wrapping_sub(t as u32) >> d)
894 }
895
896 pub fn decompose(mut a: u32) -> (u32, u32) {
897 let alpha = ALPHA as i32;
898
899 let mut t = (a & 0x7_ffff) as i32;
900 t += ((a >> 19) << 9) as i32;
901 t -= alpha / 2 + 1;
902 t += (t >> 31) & alpha;
903 t -= alpha / 2 - 1;
904 a = a.wrapping_sub(t as u32);
905
906 let mut u = (a as i32) - 1;
907 u >>= 31;
908 a = (a >> 19) + 1;
909 a -= (u & 1) as u32;
910
911 (Q.wrapping_add(t as u32).wrapping_sub(a >> 4), a & 0xf)
912 }
913
914 pub fn make_hint(a: u32, b: u32) -> u32 {
915 let (_, x) = decompose(a);
916 let (_, y) = decompose(b);
917 if x != y { 1 } else { 0 }
918 }
919
920 pub fn use_hint(a: u32, hint: u32) -> u32 {
921 let (a0, a1) = decompose(a);
922
923 if hint == 0 {
924 a1
925 } else if a0 > Q {
926 a1.wrapping_add(1) & 0xf
927 } else {
928 a1.wrapping_sub(1) & 0xf
929 }
930 }
931}
932
933//////////////////////////////////////////////////////////////////////////// Original file sign.rs
934
935pub mod sign {
936
937 use crate::{
938 shake128,
939 shake256,
940 };
941 use super::params::*;
942 use super::polyvec::{
943 self,
944 PolyVecL,
945 PolyVecK,
946 };
947 use super::poly::{
948 self,
949 Poly,
950 };
951 use super::packing;
952
953 use arrayref::{
954 array_mut_ref,
955 array_ref,
956 };
957 use byteorder::{
958 ByteOrder,
959 LittleEndian,
960 };
961 use digest::{
962 Input,
963 ExtendableOutput,
964 XofReader,
965 };
966 use rand_core_old::{
967 RngCore,
968 CryptoRng,
969 };
970 use sha3::Shake256;
971
972 pub(crate) fn expand_mat(
973 mat: &mut [PolyVecL; K],
974 rho: &[u8; SEEDBYTES],
975 ) {
976 const SHAKE128_RATE: usize = 168;
977
978 let mut outbuf = [0; 5 * SHAKE128_RATE];
979
980 for i in 0..K {
981 for j in 0..L {
982 shake128!(&mut outbuf; rho, &[(i + (j << 4)) as u8]);
983 poly::uniform(&mut mat[i][j], &outbuf);
984 }
985 }
986 }
987
988 pub(crate) fn challenge(
989 c: &mut Poly,
990 mu: &[u8; CRHBYTES],
991 w1: &PolyVecK,
992 ) {
993 const SHAKE256_RATE: usize = 136;
994
995 let mut outbuf = [0; SHAKE256_RATE];
996 let mut w1pack = [0; K * POLW1_SIZE_PACKED];
997 for (i, pack) in w1pack.chunks_mut(POLW1_SIZE_PACKED).enumerate() {
998 let pack = array_mut_ref!(pack, 0, POLW1_SIZE_PACKED);
999 poly::w1_pack(pack, &w1[i]);
1000 }
1001
1002 let mut hasher = Shake256::default();
1003 hasher.process(mu);
1004 hasher.process(&w1pack);
1005 let mut xof = hasher.xof_result();
1006 xof.read(&mut outbuf);
1007
1008 let signs = LittleEndian::read_u64(&outbuf);
1009 let mut pos = 8;
1010 let mut mask = 1;
1011
1012 for i in 196..256 {
1013 let b = loop {
1014 if pos >= SHAKE256_RATE {
1015 xof.read(&mut outbuf);
1016 pos = 0;
1017 }
1018
1019 let b = outbuf[pos] as usize;
1020 pos += 1;
1021 if b <= i { break b }
1022 };
1023
1024 c[i] = c[b];
1025 c[b] = if signs & mask != 0 { Q - 1 } else { 1 };
1026 mask <<= 1;
1027 }
1028 }
1029
1030 pub fn keypair<R: RngCore + CryptoRng>(
1031 rng: &mut R,
1032 pk_bytes: &mut [u8; PK_SIZE_PACKED],
1033 sk_bytes: &mut [u8; SK_SIZE_PACKED],
1034 ) {
1035 let mut nonce = 0;
1036 let mut tr = [0; CRHBYTES];
1037 let mut seedbuf = [0; 3 * SEEDBYTES];
1038 let mut mat = [PolyVecL::default(); K];
1039 let mut s1 = PolyVecL::default();
1040 let (mut s2, mut t, mut t0, mut t1) = (
1041 PolyVecK::default(),
1042 PolyVecK::default(),
1043 PolyVecK::default(),
1044 PolyVecK::default(),
1045 );
1046
1047 // Expand 32 bytes of randomness into rho, rhoprime and key
1048 rng.fill_bytes(&mut seedbuf[..SEEDBYTES]);
1049 shake256!(&mut seedbuf; &seedbuf[..SEEDBYTES]);
1050 let rho = array_ref!(seedbuf, 0, SEEDBYTES);
1051 let rhoprime = array_ref!(seedbuf, SEEDBYTES, SEEDBYTES);
1052 let key = array_ref!(seedbuf, 2 * SEEDBYTES, SEEDBYTES);
1053
1054 // Expand matrix
1055 expand_mat(&mut mat, rho);
1056
1057 // Sample short vectors s1 and s2
1058 for i in 0..L {
1059 poly::uniform_eta(&mut s1[i], rhoprime, nonce);
1060 nonce += 1;
1061 }
1062 for i in 0..K {
1063 poly::uniform_eta(&mut s2[i], rhoprime, nonce);
1064 nonce += 1;
1065 }
1066
1067 // Matrix-vector multiplication
1068 let mut s1hat = s1.clone();
1069 s1hat.ntt();
1070 for i in 0..K {
1071 polyvec::pointwise_acc_invmontgomery(&mut t[i], &mat[i], &s1hat);
1072 poly::reduce(&mut t[i]);
1073 poly::invntt_montgomery(&mut t[i])
1074 }
1075
1076 // Add noise vector s2
1077 t.add_assign(&s2);
1078
1079 // Extract t1 and write public key
1080 t.freeze();
1081 t.power2round(&mut t0, &mut t1);
1082 packing::pk::pack(
1083 pk_bytes,
1084 rho,
1085 &t1,
1086 );
1087
1088 // Compute CRH(rho, t1) and write secret key
1089 shake256!(&mut tr; pk_bytes);
1090 packing::sk::pack(
1091 sk_bytes,
1092 rho,
1093 key,
1094 &tr,
1095 &s1,
1096 &s2,
1097 &t0,
1098 );
1099 }
1100
1101 pub fn sign(
1102 m: &[u8],
1103 sk: &[u8; SK_SIZE_PACKED],
1104 )
1105 -> [u8; SIG_SIZE_PACKED]
1106 {
1107 let mut sig = [0; SIG_SIZE_PACKED];
1108 sign_mut(&mut sig, &m, &sk);
1109 sig
1110 }
1111
1112 pub fn sign_mut(
1113 sig: &mut [u8; SIG_SIZE_PACKED],
1114 m: &[u8],
1115 sk: &[u8; SK_SIZE_PACKED],
1116 ) {
1117 let mut nonce = 0;
1118 let mut mat = [PolyVecL::default(); K];
1119 let (mut s1, mut y, mut z) = (
1120 PolyVecL::default(),
1121 PolyVecL::default(),
1122 PolyVecL::default(),
1123 );
1124 let (mut s2, mut t0, mut w, mut w1) = (
1125 PolyVecK::default(),
1126 PolyVecK::default(),
1127 PolyVecK::default(),
1128 PolyVecK::default(),
1129 );
1130 let (mut h, mut wcs2, mut wcs20, mut ct0, mut tmp) = (
1131 PolyVecK::default(),
1132 PolyVecK::default(),
1133 PolyVecK::default(),
1134 PolyVecK::default(),
1135 PolyVecK::default(),
1136 );
1137 let (mut rho, mut key, mut mu) = (
1138 [0; SEEDBYTES],
1139 [0; SEEDBYTES],
1140 [0; CRHBYTES],
1141 );
1142
1143 packing::sk::unpack(
1144 sk,
1145 &mut rho,
1146 &mut key,
1147 &mut mu,
1148 &mut s1,
1149 &mut s2,
1150 &mut t0,
1151 );
1152
1153 // Compute CRH(tr, msg)
1154 shake256!(&mut mu; &mu, m);
1155
1156 // Expand matrix and transform vectors
1157 expand_mat(&mut mat, &rho);
1158 s1.ntt();
1159 s2.ntt();
1160 t0.ntt();
1161
1162 loop {
1163 let mut c = [0; N];
1164
1165 // Sample intermediate vector
1166 for i in 0..L {
1167 poly::uniform_gamma1m1(&mut y[i], &key, &mu, nonce);
1168 nonce += 1;
1169 }
1170
1171 // Matrix-vector multiplicatio
1172 let mut yhat = y.clone();
1173 yhat.ntt();
1174 for i in 0..K {
1175 polyvec::pointwise_acc_invmontgomery(&mut w[i], &mat[i], &yhat);
1176 poly::invntt_montgomery(&mut w[i]);
1177 }
1178
1179 // Decompose w and call the random oracle
1180 w.csubq();
1181 w.decompose(&mut tmp, &mut w1);
1182 challenge(&mut c, &mu, &w1);
1183
1184 // Compute z, reject if it reveals secret
1185 let mut chat = c.clone();
1186 poly::ntt(&mut chat);
1187 for i in 0..L {
1188 poly::pointwise_invmontgomery(&mut z[i], &chat, &s1[i]);
1189 poly::invntt_montgomery(&mut z[i])
1190 }
1191 z.add_assign(&y);
1192 z.freeze();
1193 if z.chknorm(GAMMA1 - BETA) { continue };
1194
1195 // Compute w - cs2, reject if w1 can not be computed from it
1196 for i in 0..K {
1197 poly::pointwise_invmontgomery(&mut wcs20[i], &chat, &s2[i]);
1198 poly::invntt_montgomery(&mut wcs20[i]);
1199 }
1200 wcs2.with_sub(&w, &wcs20);
1201 wcs2.freeze();
1202 wcs2.decompose(&mut wcs20, &mut tmp);
1203 wcs20.csubq();
1204 if wcs20.chknorm(GAMMA2 - BETA) { continue };
1205
1206 if tmp != w1 { continue };
1207
1208 // Compute hints for w1
1209 for i in 0..K {
1210 poly::pointwise_invmontgomery(&mut ct0[i], &chat, &t0[i]);
1211 poly::invntt_montgomery(&mut ct0[i]);
1212 }
1213
1214 ct0.csubq();
1215 if ct0.chknorm(GAMMA2) { continue };
1216
1217 tmp.with_add(&wcs2, &ct0);
1218 tmp.csubq();
1219 let hint = polyvec::make_hint(&mut h, &wcs2, &tmp);
1220 if hint > OMEGA { continue };
1221
1222 // Write signature
1223 packing::sign::pack(sig, &z, &h, &c);
1224
1225 break
1226 }
1227 }
1228
1229 pub fn verify(
1230 m: &[u8],
1231 sig: &[u8; SIG_SIZE_PACKED],
1232 pk: &[u8; PK_SIZE_PACKED],
1233 )
1234 -> bool
1235 {
1236 let (mut rho, mut mu) = ([0; SEEDBYTES], [0; CRHBYTES]);
1237 let (mut c, mut cp) = ([0; N], [0; N]);
1238 let mut mat = [PolyVecL::default(); K];
1239 let mut z = PolyVecL::default();
1240 let (mut t1, mut w1, mut h) = Default::default();
1241 let (mut tmp1, mut tmp2) = (PolyVecK::default(), PolyVecK::default());
1242
1243 packing::pk::unpack(pk, &mut rho, &mut t1);
1244 let r = packing::sign::unpack(sig, &mut z, &mut h, &mut c);
1245
1246 if !r { return false };
1247 if z.chknorm(GAMMA1 - BETA) { return false };
1248
1249 // TODO
1250 // Compute CRH(CRH(rho, t1), msg)
1251 shake256!(&mut mu; pk);
1252 shake256!(&mut mu; &mu, m);
1253
1254 // Matrix-vector multiplication; compute Az - c2^dt1
1255 expand_mat(&mut mat, &rho);
1256 z.ntt();
1257 for i in 0..K {
1258 polyvec::pointwise_acc_invmontgomery(&mut tmp1[i], &mat[i], &z);
1259 }
1260
1261 let mut chat = c.clone();
1262 poly::ntt(&mut chat);
1263 t1.shift_left(D as u32);
1264 t1.ntt();
1265 for i in 0..K {
1266 poly::pointwise_invmontgomery(&mut tmp2[i], &chat, &t1[i]);
1267 }
1268
1269 let mut tmp = PolyVecK::default();
1270 tmp.with_sub(&tmp1, &tmp2);
1271 tmp.reduce();
1272 tmp.invntt_montgomery();
1273
1274 // Reconstruct w1
1275 tmp.csubq();
1276 polyvec::use_hint(&mut w1, &tmp, &h);
1277
1278 // Call random oracle and verify challenge
1279 challenge(&mut cp, &mu, &w1);
1280
1281 // TODO use subtle
1282 // https://github.com/isislovecruft/subtle/pull/5
1283 (0..N)
1284 .map(|i| c[i] ^ cp[i])
1285 .fold(0, |sum, next| sum | next)
1286 .eq(&0)
1287 }
1288}
1289
1290////////////////////////////////////////////////////////////////////////////// Original file test_mul.rs
1291
1292#[cfg(test)]
1293mod test_mul {
1294 use super::*;
1295 use poly::Poly;
1296 use params::{ N, Q };
1297 use rand_core_old::{
1298 OsRng as OsRng_old,
1299 RngCore,
1300 };
1301
1302 const NTESTS: usize = 10000;
1303
1304 fn poly_naivemul(c: &mut Poly, a: &Poly, b: &Poly) {
1305 let mut r = [0; 2 * N];
1306
1307 for i in 0..N {
1308 for j in 0..N {
1309 r[i + j] += ((u64::from(a[i]) * u64::from(b[j])) % u64::from(Q)) as u32;
1310 r[i + j] %= Q;
1311 }
1312 }
1313
1314 for i in N..(2 * N) {
1315 r[i - N] = r[i - N] + (Q as u32) - r[i];
1316 r[i - N] %= Q;
1317 }
1318
1319 c.copy_from_slice(&r[..N]);
1320 }
1321
1322
1323 #[test]
1324 fn test_dilithium_mul() {
1325 let mut rndbuf = [0; 840];
1326 let (mut c1, mut c2) = ([0; N], [0; N]);
1327 let (mut a, mut b) = ([0; N], [0; N]);
1328
1329 for _ in 0..NTESTS {
1330 OsRng_old.fill_bytes(&mut rndbuf);
1331 poly::uniform(&mut a, &rndbuf);
1332 OsRng_old.fill_bytes(&mut rndbuf);
1333 poly::uniform(&mut b, &rndbuf);
1334
1335 poly_naivemul(&mut c1, &a, &b);
1336
1337 poly::ntt(&mut a);
1338 poly::ntt(&mut b);
1339 poly::pointwise_invmontgomery(&mut c2, &a, &b);
1340 poly::invntt_montgomery(&mut c2);
1341 poly::csubq(&mut c2);
1342
1343 assert_eq!(&c2[..], &c1[..]);
1344 }
1345 }
1346}
1347/////////////////////////////////////////////////////////////////////////// Original file test_vectors.rs
1348#[cfg(test)]
1349mod test_vectors {
1350 use oxedyne_fe2o3_core::ok;
1351 use hex::{self, FromHexError};
1352 use byteorder::{ ByteOrder, BigEndian };
1353 use itertools::Itertools;
1354 use super::poly;
1355 use super::polyvec::{ self, PolyVecL, PolyVecK };
1356 use super::params::{
1357 N, K, L,
1358 SEEDBYTES, CRHBYTES
1359 };
1360 use super::sign;
1361
1362 const TEST_VECTORS: &str = include_str!("../../tests/testvectors.txt");
1363
1364 struct TestVector {
1365 seed: ([u8; SEEDBYTES], [u8; CRHBYTES]),
1366 mat: [PolyVecL; K],
1367 s: PolyVecL,
1368 y: PolyVecL,
1369 w1: PolyVecK,
1370 c: [u32; N]
1371 }
1372
1373 impl Default for TestVector {
1374 fn default() -> Self {
1375 TestVector {
1376 seed: ([0; SEEDBYTES], [0; CRHBYTES]),
1377 mat: [PolyVecL::default(); K],
1378 s: PolyVecL::default(),
1379 y: PolyVecL::default(),
1380 w1: PolyVecK::default(),
1381 c: [0; N]
1382 }
1383 }
1384 }
1385
1386 fn parse_testvectors() -> Result<Vec<TestVector>, FromHexError> {
1387 let mut testvectors = Vec::new();
1388
1389 for testvector in TEST_VECTORS.lines().chunks(7).into_iter() {
1390 let mut tv = TestVector::default();
1391
1392 for (key, val) in testvector
1393 .map(|line| line.split('='))
1394 .map(|mut split| (split.next(), split.last()))
1395 .filter_map(|(key, val)| key.and_then(|key| val.map(|val| (key.trim(), val.trim()))))
1396 {
1397 match key {
1398 "count" => (),
1399 "seed" => {
1400 let seed = ok!(hex::decode(val));
1401 let (rho, mu) = seed.split_at(SEEDBYTES);
1402 tv.seed.0.copy_from_slice(rho);
1403 tv.seed.1.copy_from_slice(mu);
1404 },
1405 "mat" => {
1406 let mut mat = [0; K * L * N];
1407 let mut i = 0;
1408 BigEndian::read_u32_into(&ok!(hex::decode(val)), &mut mat);
1409 for j in 0..K {
1410 for k in 0..L {
1411 for l in 0..N {
1412 tv.mat[j][k][l] = mat[i];
1413 i += 1;
1414 }
1415 }
1416 }
1417 },
1418 "s" => {
1419 let mut s = [0; L * N];
1420 let mut i = 0;
1421 BigEndian::read_u32_into(&ok!(hex::decode(val)), &mut s);
1422 for j in 0..L {
1423 for k in 0..N {
1424 tv.s[j][k] = s[i];
1425 i += 1;
1426 }
1427 }
1428 },
1429 "y" => {
1430 let mut y = [0; L * N];
1431 let mut i = 0;
1432 BigEndian::read_u32_into(&ok!(hex::decode(val)), &mut y);
1433 for j in 0..L {
1434 for k in 0..N {
1435 tv.y[j][k] = y[i];
1436 i += 1;
1437 }
1438 }
1439 },
1440 "w1" => {
1441 let mut w1 = [0; K * N];
1442 let mut i = 0;
1443 BigEndian::read_u32_into(&ok!(hex::decode(val)), &mut w1);
1444 for j in 0..K {
1445 for k in 0..N {
1446 tv.w1[j][k] = w1[i];
1447 i += 1;
1448 }
1449 }
1450 },
1451 "c" => {
1452 BigEndian::read_u32_into(&ok!(hex::decode(val)), &mut tv.c);
1453 },
1454 _ => panic!()
1455 }
1456 }
1457
1458 testvectors.push(tv);
1459 }
1460
1461 Ok(testvectors)
1462 }
1463
1464 #[test]
1465 fn test_dilithium_vectors() {
1466 for tv in parse_testvectors().unwrap() {
1467 let mut mat = [PolyVecL::default(); K];
1468 let mut s = PolyVecL::default();
1469 let mut y = PolyVecL::default();
1470 let mut w = PolyVecK::default();
1471 let mut w1 = PolyVecK::default();
1472 let mut tmp = PolyVecK::default();
1473 let mut c = [0; N];
1474
1475 sign::expand_mat(&mut mat, &tv.seed.0);
1476 assert!(&mat == &tv.mat);
1477
1478 for i in 0..L {
1479 poly::uniform_eta(&mut s[i], &tv.seed.0, i as u8);
1480 }
1481 assert!(&s == &tv.s);
1482
1483 for i in 0..L {
1484 poly::uniform_gamma1m1(&mut y[i], &tv.seed.0, &tv.seed.1, i as u16);
1485 }
1486 assert!(&y == &tv.y);
1487
1488 y.ntt();
1489 for i in 0..K {
1490 polyvec::pointwise_acc_invmontgomery(&mut w[i], &mat[i], &y);
1491 poly::invntt_montgomery(&mut w[i]);
1492 }
1493 w.csubq();
1494 w.decompose(&mut tmp, &mut w1);
1495 assert!(&w1 == &tv.w1);
1496
1497 sign::challenge(&mut c, &tv.seed.1, &w1);
1498 assert!(&c[..] == &tv.c[..]);
1499 }
1500 }
1501}
1502
1503#[cfg(test)]
1504mod test_sign {
1505 use super::*;
1506 use crate::{
1507 pqc::dilithium::{
1508 params::*,
1509 sign::{
1510 keypair,
1511 sign,
1512 verify,
1513 },
1514 },
1515 sign::SignatureScheme,
1516 };
1517
1518 use oxedyne_fe2o3_core::prelude::*;
1519 use oxedyne_fe2o3_iop_crypto::sign::Signer;
1520
1521 use std::time::Instant;
1522
1523 use ed25519_dalek::{
1524 Signer as DalekSigner,
1525 SigningKey,
1526 Verifier,
1527 };
1528 use rand_core_old::{
1529 OsRng as OsRng_old,
1530 RngCore,
1531 };
1532 use rand_core::OsRng;
1533
1534 const BATCH_SIZE: usize = 1000;
1535 const MSG_SIZE: usize = 32;
1536
1537 #[test]
1538 fn test_rough_dilithium_speed_compare_00() {
1539 msg!("Constructing {} messages of size {} bytes...", BATCH_SIZE, MSG_SIZE);
1540 let mut msgs = Vec::new();
1541 for _ in 0..BATCH_SIZE {
1542 let mut msg = [0; MSG_SIZE];
1543 OsRng_old.fill_bytes(&mut msg);
1544 msgs.push(msg);
1545 }
1546
1547 msg!("Creating Dilithium key pair...");
1548 let (mut pk, mut sk) = ([0; PUBLICKEYBYTES], [0; SECRETKEYBYTES]);
1549 keypair(&mut OsRng_old, &mut pk, &mut sk);
1550 let t0 = Instant::now();
1551 msg!("Sign and verify {} messages...", BATCH_SIZE);
1552 for i in 0..BATCH_SIZE {
1553 let sig = sign(&msgs[i], &sk);
1554 assert!(verify(&msgs[i], &sig, &pk));
1555 }
1556 let dt = t0.elapsed().as_millis();
1557 msg!("Dilithium signatures and verifications: {} [ms]/loop.",
1558 (dt as f64) / (BATCH_SIZE as f64));
1559
1560 msg!("Creating ED25519 key pair...");
1561 let signing_key = SigningKey::generate(&mut OsRng);
1562 let verifying_key = signing_key.verifying_key();
1563 let t0 = Instant::now();
1564 msg!("Sign and verify {} messages...", BATCH_SIZE);
1565 for i in 0..BATCH_SIZE {
1566 let sig = signing_key.sign(&msgs[i]);
1567 assert!(verifying_key.verify(&msgs[i], &sig).is_ok());
1568 }
1569 let dt = t0.elapsed().as_millis();
1570 msg!("ED25519 signatures and verifications: {} [ms]/loop.",
1571 (dt as f64) / (BATCH_SIZE as f64));
1572 }
1573
1574 #[test]
1575 fn test_rough_dilithium_speed_compare_01() -> Outcome<()> {
1576 msg!("Constructing {} messages of size {} bytes...", BATCH_SIZE, MSG_SIZE);
1577 let mut msgs = Vec::new();
1578 for _ in 0..BATCH_SIZE {
1579 let mut msg = [0; MSG_SIZE];
1580 OsRng_old.fill_bytes(&mut msg);
1581 msgs.push(msg);
1582 }
1583
1584 msg!("Creating Dilithium scheme...");
1585 //let scheme = res!(SignatureScheme::new_dilithium2()); // TODO Substantially faster, why?
1586 let scheme = SignatureScheme::new_dilithium2_fe2o3();
1587 let t0 = Instant::now();
1588 msg!("Sign and verify {} messages...", BATCH_SIZE);
1589 for i in 0..BATCH_SIZE {
1590 let sig = res!(scheme.sign(&msgs[i]));
1591 assert!(res!(scheme.verify(&msgs[i], &sig)));
1592 }
1593 let dt = t0.elapsed().as_millis();
1594 msg!("Dilithium signatures and verifications: {} [ms]/loop.",
1595 (dt as f64) / (BATCH_SIZE as f64));
1596
1597 msg!("Creating ED25519 key pair...");
1598 let scheme = SignatureScheme::new_ed25519();
1599 let t0 = Instant::now();
1600 msg!("Sign and verify {} messages...", BATCH_SIZE);
1601 for i in 0..BATCH_SIZE {
1602 let sig = res!(scheme.sign(&msgs[i]));
1603 assert!(res!(scheme.verify(&msgs[i], &sig)));
1604 }
1605 let dt = t0.elapsed().as_millis();
1606 msg!("ED25519 signatures and verifications: {} [ms]/loop.",
1607 (dt as f64) / (BATCH_SIZE as f64));
1608
1609 Ok(())
1610 }
1611}