winter_crypto/hash/rescue/rp64_256/
mod.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use core::ops::Range;
7
8use math::{fields::f64::BaseElement, FieldElement, StarkField};
9
10use super::{super::mds::mds_f64_12x12::mds_multiply, exp_acc, Digest, ElementHasher, Hasher};
11
12mod digest;
13pub use digest::ElementDigest;
14
15#[cfg(test)]
16mod tests;
17
18// CONSTANTS
19// ================================================================================================
20
21/// Sponge state is set to 12 field elements or 96 bytes; 8 elements are reserved for rate and
22/// the remaining 4 elements are reserved for capacity.
23const STATE_WIDTH: usize = 12;
24
25/// The rate portion of the state is located in elements 4 through 11.
26const RATE_RANGE: Range<usize> = 4..12;
27const RATE_WIDTH: usize = RATE_RANGE.end - RATE_RANGE.start;
28
29const INPUT1_RANGE: Range<usize> = 4..8;
30const INPUT2_RANGE: Range<usize> = 8..12;
31
32/// The capacity portion of the state is located in elements 0, 1, 2, and 3.
33const CAPACITY_RANGE: Range<usize> = 0..4;
34
35/// The output of the hash function is a digest which consists of 4 field elements or 32 bytes.
36///
37/// The digest is returned from state elements 4, 5, 6, and 7 (the first four elements of the
38/// rate portion).
39const DIGEST_RANGE: Range<usize> = 4..8;
40const DIGEST_SIZE: usize = DIGEST_RANGE.end - DIGEST_RANGE.start;
41
42/// The number of rounds is set to 7 to target 128-bit security level with 40% security margin;
43/// computed using algorithm 7 from <https://eprint.iacr.org/2020/1143.pdf>
44const NUM_ROUNDS: usize = 7;
45
46/// S-Box and Inverse S-Box powers;
47/// computed using algorithm 6 from <https://eprint.iacr.org/2020/1143.pdf>
48///
49/// The constants are defined for tests only because the exponentiations in the code are unrolled
50/// for efficiency reasons.
51#[cfg(test)]
52const ALPHA: u64 = 7;
53#[cfg(test)]
54const INV_ALPHA: u64 = 10540996611094048183;
55
56// HASHER IMPLEMENTATION
57// ================================================================================================
58
59/// Implementation of [Hasher] trait for Rescue Prime hash function with 256-bit output.
60///
61/// The hash function is implemented according to the Rescue Prime
62/// [specifications](https://eprint.iacr.org/2020/1143.pdf) with the following exception:
63/// * We set the number of rounds to 7, which implies a 40% security margin instead of the 50%
64///   margin used in the specifications (a 50% margin rounds up to 8 rounds). The primary motivation
65///   for this is that having the number of rounds be one less than a power of two simplifies AIR
66///   design for computations involving the hash function.
67/// * When hashing a sequence of elements, we do not append Fp(1) followed by Fp(0) elements to the
68///   end of the sequence as padding. Instead, we initialize the first capacity element to the
69///   number of elements to be hashed, and pad the sequence with Fp(0) elements only. This ensures
70///   consistency of hash outputs between different hashing methods (see section below). However, it
71///   also means that our instantiation of Rescue Prime cannot be used in a stream mode as the
72///   number of elements to be hashed must be known upfront.
73/// * We use the first 4 elements of the state (rather than the last 4 elements of the state) for
74///   capacity and the remaining 8 elements for rate. The output of the hash function comes from the
75///   first four elements of the rate portion of the state (elements 4, 5, 6, and 7). This
76///   effectively applies a fixed bit permutation before and after XLIX permutation. We assert
77///   without proof that this does not affect security of the construction.
78/// * Instead of using Vandermonde matrices as a standard way of generating an MDS matrix as
79///   described in Rescue Prime paper, we use a methodology developed by Polygon Zero to find an MDS
80///   matrix with coefficients which are small powers of two in frequency domain. This allows us to
81///   dramatically reduce MDS matrix multiplication time. Using a different MDS matrix does not
82///   affect security of the hash function as any MDS matrix satisfies Rescue Prime construction (as
83///   described in section 4.2 of the paper).
84///
85/// The parameters used to instantiate the function are:
86/// * Field: 64-bit prime field with modulus 2^64 - 2^32 + 1.
87/// * State width: 12 field elements.
88/// * Capacity size: 4 field elements.
89/// * Number of rounds: 7.
90/// * S-Box degree: 7.
91///
92/// The above parameters target 128-bit security level. The digest consists of four field elements
93/// and it can be serialized into 32 bytes (256 bits).
94///
95/// ## Hash output consistency
96/// Functions [hash_elements()](Rp64_256::hash_elements), [merge()](Rp64_256::merge), and
97/// [merge_with_int()](Rp64_256::merge_with_int) are internally consistent. That is, computing
98/// a hash for the same set of elements using these functions will always produce the same
99/// result. For example, merging two digests using [merge()](Rp64_256::merge) will produce the
100/// same result as hashing 8 elements which make up these digests using
101/// [hash_elements()](Rp64_256::hash_elements) function.
102///
103/// However, [hash()](Rp64_256::hash) function is not consistent with functions mentioned above.
104/// For example, if we take two field elements, serialize them to bytes and hash them using
105/// [hash()](Rp64_256::hash), the result will differ from the result obtained by hashing these
106/// elements directly using [hash_elements()](Rp64_256::hash_elements) function. The reason for
107/// this difference is that [hash()](Rp64_256::hash) function needs to be able to handle
108/// arbitrary binary strings, which may or may not encode valid field elements - and thus,
109/// deserialization procedure used by this function is different from the procedure used to
110/// deserialize valid field elements.
111///
112/// Thus, if the underlying data consists of valid field elements, it might make more sense
113/// to deserialize them into field elements and then hash them using
114/// [hash_elements()](Rp64_256::hash_elements) function rather then hashing the serialized bytes
115/// using [hash()](Rp64_256::hash) function.
116pub struct Rp64_256();
117
118impl Hasher for Rp64_256 {
119    type Digest = ElementDigest;
120
121    const COLLISION_RESISTANCE: u32 = 128;
122
123    fn hash(bytes: &[u8]) -> Self::Digest {
124        // compute the number of elements required to represent the string; we will be processing
125        // the string in 7-byte chunks, thus the number of elements will be equal to the number
126        // of such chunks (including a potential partial chunk at the end).
127        let num_elements = if bytes.len() % 7 == 0 {
128            bytes.len() / 7
129        } else {
130            bytes.len() / 7 + 1
131        };
132
133        // initialize state to all zeros, except for the first element of the capacity part, which
134        // is set to the number of elements to be hashed. this is done so that adding zero elements
135        // at the end of the list always results in a different hash.
136        let mut state = [BaseElement::ZERO; STATE_WIDTH];
137        state[CAPACITY_RANGE.start] = BaseElement::new(num_elements as u64);
138
139        // break the string into 7-byte chunks, convert each chunk into a field element, and
140        // absorb the element into the rate portion of the state. we use 7-byte chunks because
141        // every 7-byte chunk is guaranteed to map to some field element.
142        let mut i = 0;
143        let mut buf = [0_u8; 8];
144        for chunk in bytes.chunks(7) {
145            if i < num_elements - 1 {
146                buf[..7].copy_from_slice(chunk);
147            } else {
148                // if we are dealing with the last chunk, it may be smaller than 7 bytes long, so
149                // we need to handle it slightly differently. we also append a byte with value 1
150                // to the end of the string; this pads the string in such a way that adding
151                // trailing zeros results in different hash
152                let chunk_len = chunk.len();
153                buf = [0_u8; 8];
154                buf[..chunk_len].copy_from_slice(chunk);
155                buf[chunk_len] = 1;
156            }
157
158            // convert the bytes into a field element and absorb it into the rate portion of the
159            // state; if the rate is filled up, apply the Rescue permutation and start absorbing
160            // again from zero index.
161            state[RATE_RANGE.start + i] += BaseElement::new(u64::from_le_bytes(buf));
162            i += 1;
163            if i % RATE_WIDTH == 0 {
164                Self::apply_permutation(&mut state);
165                i = 0;
166            }
167        }
168
169        // if we absorbed some elements but didn't apply a permutation to them (would happen when
170        // the number of elements is not a multiple of RATE_WIDTH), apply the Rescue permutation.
171        // we don't need to apply any extra padding because we injected total number of elements
172        // in the input list into the capacity portion of the state during initialization.
173        if i > 0 {
174            Self::apply_permutation(&mut state);
175        }
176
177        // return the first 4 elements of the state as hash result
178        ElementDigest::new(state[DIGEST_RANGE].try_into().unwrap())
179    }
180
181    fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
182        // initialize the state by copying the digest elements into the rate portion of the state
183        // (8 total elements), and set the first capacity element to 8 (the number of elements to
184        // be hashed).
185        let mut state = [BaseElement::ZERO; STATE_WIDTH];
186        state[RATE_RANGE].copy_from_slice(Self::Digest::digests_as_elements(values));
187        state[CAPACITY_RANGE.start] = BaseElement::new(RATE_WIDTH as u64);
188
189        // apply the Rescue permutation and return the first four elements of the state
190        Self::apply_permutation(&mut state);
191        ElementDigest::new(state[DIGEST_RANGE].try_into().unwrap())
192    }
193
194    fn merge_many(values: &[Self::Digest]) -> Self::Digest {
195        Self::hash_elements(ElementDigest::digests_as_elements(values))
196    }
197
198    fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
199        // initialize the state as follows:
200        // - seed is copied into the first 4 elements of the rate portion of the state.
201        // - if the value fits into a single field element, copy it into the fifth rate element and
202        //   set the first capacity element to 5 (the number of elements to be hashed).
203        // - if the value doesn't fit into a single field element, split it into two field elements,
204        //   copy them into rate elements 5 and 6, and set the first capacity element to 6.
205        let mut state = [BaseElement::ZERO; STATE_WIDTH];
206        state[INPUT1_RANGE].copy_from_slice(seed.as_elements());
207        state[INPUT2_RANGE.start] = BaseElement::new(value);
208        if value < BaseElement::MODULUS {
209            state[CAPACITY_RANGE.start] = BaseElement::new(DIGEST_SIZE as u64 + 1);
210        } else {
211            state[INPUT2_RANGE.start + 1] = BaseElement::new(value / BaseElement::MODULUS);
212            state[CAPACITY_RANGE.start] = BaseElement::new(DIGEST_SIZE as u64 + 2);
213        }
214
215        // apply the Rescue permutation and return the first four elements of the state
216        Self::apply_permutation(&mut state);
217        ElementDigest::new(state[DIGEST_RANGE].try_into().unwrap())
218    }
219}
220
221impl ElementHasher for Rp64_256 {
222    type BaseField = BaseElement;
223
224    fn hash_elements<E: FieldElement<BaseField = Self::BaseField>>(elements: &[E]) -> Self::Digest {
225        // convert the elements into a list of base field elements
226        let elements = E::slice_as_base_elements(elements);
227
228        // initialize state to all zeros, except for the last element of the capacity part, which
229        // is set to the number of elements to be hashed. this is done so that adding zero elements
230        // at the end of the list always results in a different hash.
231        let mut state = [BaseElement::ZERO; STATE_WIDTH];
232        state[CAPACITY_RANGE.start] = BaseElement::new(elements.len() as u64);
233
234        // absorb elements into the state one by one until the rate portion of the state is filled
235        // up; then apply the Rescue permutation and start absorbing again; repeat until all
236        // elements have been absorbed
237        let mut i = 0;
238        for &element in elements.iter() {
239            state[RATE_RANGE.start + i] += element;
240            i += 1;
241            if i % RATE_WIDTH == 0 {
242                Self::apply_permutation(&mut state);
243                i = 0;
244            }
245        }
246
247        // if we absorbed some elements but didn't apply a permutation to them (would happen when
248        // the number of elements is not a multiple of RATE_WIDTH), apply the Rescue permutation.
249        // we don't need to apply any extra padding because we injected total number of elements
250        // in the input list into the capacity portion of the state during initialization.
251        if i > 0 {
252            Self::apply_permutation(&mut state);
253        }
254
255        // return the first 4 elements of the state as hash result
256        ElementDigest::new(state[DIGEST_RANGE].try_into().unwrap())
257    }
258}
259
260// HASH FUNCTION IMPLEMENTATION
261// ================================================================================================
262
263impl Rp64_256 {
264    // CONSTANTS
265    // --------------------------------------------------------------------------------------------
266
267    /// The number of rounds is set to 7 to target 128-bit security level with 40% security margin.
268    pub const NUM_ROUNDS: usize = NUM_ROUNDS;
269
270    /// Sponge state is set to 12 field elements or 96 bytes; 8 elements are reserved for rate and
271    /// the remaining 4 elements are reserved for capacity.
272    pub const STATE_WIDTH: usize = STATE_WIDTH;
273
274    /// The rate portion of the state is located in elements 4 through 11 (inclusive).
275    pub const RATE_RANGE: Range<usize> = RATE_RANGE;
276
277    /// The capacity portion of the state is located in elements 0, 1, 2, and 3.
278    pub const CAPACITY_RANGE: Range<usize> = CAPACITY_RANGE;
279
280    /// The output of the hash function can be read from state elements 4, 5, 6, and 7.
281    pub const DIGEST_RANGE: Range<usize> = DIGEST_RANGE;
282
283    /// MDS matrix used for computing the linear layer in a Rescue Prime round.
284    pub const MDS: [[BaseElement; STATE_WIDTH]; STATE_WIDTH] = MDS;
285
286    /// Inverse of the MDS matrix.
287    pub const INV_MDS: [[BaseElement; STATE_WIDTH]; STATE_WIDTH] = INV_MDS;
288
289    /// Round constants added to the hasher state in the first half of the Rescue Prime round.
290    pub const ARK1: [[BaseElement; STATE_WIDTH]; NUM_ROUNDS] = ARK1;
291
292    /// Round constants added to the hasher state in the second half of the Rescue Prime round.
293    pub const ARK2: [[BaseElement; STATE_WIDTH]; NUM_ROUNDS] = ARK2;
294
295    // RESCUE PERMUTATION
296    // --------------------------------------------------------------------------------------------
297
298    /// Applies Rescue-XLIX permutation to the provided state.
299    pub fn apply_permutation(state: &mut [BaseElement; STATE_WIDTH]) {
300        // implementation is based on algorithm 3 from <https://eprint.iacr.org/2020/1143.pdf>
301        // apply round function 7 times; this provides 128-bit security with 40% security margin
302        for i in 0..NUM_ROUNDS {
303            Self::apply_round(state, i);
304        }
305    }
306
307    /// Rescue-XLIX round function.
308    #[inline(always)]
309    pub fn apply_round(state: &mut [BaseElement; STATE_WIDTH], round: usize) {
310        // apply first half of Rescue round
311        Self::apply_sbox(state);
312        Self::apply_mds(state);
313        Self::add_constants(state, &ARK1[round]);
314
315        // apply second half of Rescue round
316        Self::apply_inv_sbox(state);
317        Self::apply_mds(state);
318        Self::add_constants(state, &ARK2[round]);
319    }
320
321    // HELPER FUNCTIONS
322    // --------------------------------------------------------------------------------------------
323
324    #[inline(always)]
325    fn apply_mds(state: &mut [BaseElement; STATE_WIDTH]) {
326        mds_multiply(state)
327    }
328
329    #[inline(always)]
330    fn add_constants(state: &mut [BaseElement; STATE_WIDTH], ark: &[BaseElement; STATE_WIDTH]) {
331        state.iter_mut().zip(ark).for_each(|(s, &k)| *s += k);
332    }
333
334    #[inline(always)]
335    fn apply_sbox(state: &mut [BaseElement; STATE_WIDTH]) {
336        state[0] = state[0].exp7();
337        state[1] = state[1].exp7();
338        state[2] = state[2].exp7();
339        state[3] = state[3].exp7();
340        state[4] = state[4].exp7();
341        state[5] = state[5].exp7();
342        state[6] = state[6].exp7();
343        state[7] = state[7].exp7();
344        state[8] = state[8].exp7();
345        state[9] = state[9].exp7();
346        state[10] = state[10].exp7();
347        state[11] = state[11].exp7();
348    }
349
350    #[inline(always)]
351    fn apply_inv_sbox(state: &mut [BaseElement; STATE_WIDTH]) {
352        // compute base^10540996611094048183 using 72 multiplications per array element
353        // 10540996611094048183 = b1001001001001001001001001001000110110110110110110110110110110111
354
355        // compute base^10
356        let mut t1 = *state;
357        t1.iter_mut().for_each(|t| *t = t.square());
358
359        // compute base^100
360        let mut t2 = t1;
361        t2.iter_mut().for_each(|t| *t = t.square());
362
363        // compute base^100100
364        let t3 = exp_acc::<BaseElement, STATE_WIDTH, 3>(t2, t2);
365
366        // compute base^100100100100
367        let t4 = exp_acc::<BaseElement, STATE_WIDTH, 6>(t3, t3);
368
369        // compute base^100100100100100100100100
370        let t5 = exp_acc::<BaseElement, STATE_WIDTH, 12>(t4, t4);
371
372        // compute base^100100100100100100100100100100
373        let t6 = exp_acc::<BaseElement, STATE_WIDTH, 6>(t5, t3);
374
375        // compute base^1001001001001001001001001001000100100100100100100100100100100
376        let t7 = exp_acc::<BaseElement, STATE_WIDTH, 31>(t6, t6);
377
378        // compute base^1001001001001001001001001001000110110110110110110110110110110111
379        for (i, s) in state.iter_mut().enumerate() {
380            let a = (t7[i].square() * t6[i]).square().square();
381            let b = t1[i] * t2[i] * *s;
382            *s = a * b;
383        }
384    }
385}
386
387// MDS
388// ================================================================================================
389/// Rescue MDS matrix
390const MDS: [[BaseElement; STATE_WIDTH]; STATE_WIDTH] = [
391    [
392        BaseElement::new(7),
393        BaseElement::new(23),
394        BaseElement::new(8),
395        BaseElement::new(26),
396        BaseElement::new(13),
397        BaseElement::new(10),
398        BaseElement::new(9),
399        BaseElement::new(7),
400        BaseElement::new(6),
401        BaseElement::new(22),
402        BaseElement::new(21),
403        BaseElement::new(8),
404    ],
405    [
406        BaseElement::new(8),
407        BaseElement::new(7),
408        BaseElement::new(23),
409        BaseElement::new(8),
410        BaseElement::new(26),
411        BaseElement::new(13),
412        BaseElement::new(10),
413        BaseElement::new(9),
414        BaseElement::new(7),
415        BaseElement::new(6),
416        BaseElement::new(22),
417        BaseElement::new(21),
418    ],
419    [
420        BaseElement::new(21),
421        BaseElement::new(8),
422        BaseElement::new(7),
423        BaseElement::new(23),
424        BaseElement::new(8),
425        BaseElement::new(26),
426        BaseElement::new(13),
427        BaseElement::new(10),
428        BaseElement::new(9),
429        BaseElement::new(7),
430        BaseElement::new(6),
431        BaseElement::new(22),
432    ],
433    [
434        BaseElement::new(22),
435        BaseElement::new(21),
436        BaseElement::new(8),
437        BaseElement::new(7),
438        BaseElement::new(23),
439        BaseElement::new(8),
440        BaseElement::new(26),
441        BaseElement::new(13),
442        BaseElement::new(10),
443        BaseElement::new(9),
444        BaseElement::new(7),
445        BaseElement::new(6),
446    ],
447    [
448        BaseElement::new(6),
449        BaseElement::new(22),
450        BaseElement::new(21),
451        BaseElement::new(8),
452        BaseElement::new(7),
453        BaseElement::new(23),
454        BaseElement::new(8),
455        BaseElement::new(26),
456        BaseElement::new(13),
457        BaseElement::new(10),
458        BaseElement::new(9),
459        BaseElement::new(7),
460    ],
461    [
462        BaseElement::new(7),
463        BaseElement::new(6),
464        BaseElement::new(22),
465        BaseElement::new(21),
466        BaseElement::new(8),
467        BaseElement::new(7),
468        BaseElement::new(23),
469        BaseElement::new(8),
470        BaseElement::new(26),
471        BaseElement::new(13),
472        BaseElement::new(10),
473        BaseElement::new(9),
474    ],
475    [
476        BaseElement::new(9),
477        BaseElement::new(7),
478        BaseElement::new(6),
479        BaseElement::new(22),
480        BaseElement::new(21),
481        BaseElement::new(8),
482        BaseElement::new(7),
483        BaseElement::new(23),
484        BaseElement::new(8),
485        BaseElement::new(26),
486        BaseElement::new(13),
487        BaseElement::new(10),
488    ],
489    [
490        BaseElement::new(10),
491        BaseElement::new(9),
492        BaseElement::new(7),
493        BaseElement::new(6),
494        BaseElement::new(22),
495        BaseElement::new(21),
496        BaseElement::new(8),
497        BaseElement::new(7),
498        BaseElement::new(23),
499        BaseElement::new(8),
500        BaseElement::new(26),
501        BaseElement::new(13),
502    ],
503    [
504        BaseElement::new(13),
505        BaseElement::new(10),
506        BaseElement::new(9),
507        BaseElement::new(7),
508        BaseElement::new(6),
509        BaseElement::new(22),
510        BaseElement::new(21),
511        BaseElement::new(8),
512        BaseElement::new(7),
513        BaseElement::new(23),
514        BaseElement::new(8),
515        BaseElement::new(26),
516    ],
517    [
518        BaseElement::new(26),
519        BaseElement::new(13),
520        BaseElement::new(10),
521        BaseElement::new(9),
522        BaseElement::new(7),
523        BaseElement::new(6),
524        BaseElement::new(22),
525        BaseElement::new(21),
526        BaseElement::new(8),
527        BaseElement::new(7),
528        BaseElement::new(23),
529        BaseElement::new(8),
530    ],
531    [
532        BaseElement::new(8),
533        BaseElement::new(26),
534        BaseElement::new(13),
535        BaseElement::new(10),
536        BaseElement::new(9),
537        BaseElement::new(7),
538        BaseElement::new(6),
539        BaseElement::new(22),
540        BaseElement::new(21),
541        BaseElement::new(8),
542        BaseElement::new(7),
543        BaseElement::new(23),
544    ],
545    [
546        BaseElement::new(23),
547        BaseElement::new(8),
548        BaseElement::new(26),
549        BaseElement::new(13),
550        BaseElement::new(10),
551        BaseElement::new(9),
552        BaseElement::new(7),
553        BaseElement::new(6),
554        BaseElement::new(22),
555        BaseElement::new(21),
556        BaseElement::new(8),
557        BaseElement::new(7),
558    ],
559];
560
561/// Rescue Inverse MDS matrix
562const INV_MDS: [[BaseElement; STATE_WIDTH]; STATE_WIDTH] = [
563    [
564        BaseElement::new(14868391535953158196),
565        BaseElement::new(13278298489594233127),
566        BaseElement::new(389999932707070822),
567        BaseElement::new(9782021734907796003),
568        BaseElement::new(4829905704463175582),
569        BaseElement::new(7567822018949214430),
570        BaseElement::new(14205019324568680367),
571        BaseElement::new(15489674211196160593),
572        BaseElement::new(17636013826542227504),
573        BaseElement::new(16254215311946436093),
574        BaseElement::new(3641486184877122796),
575        BaseElement::new(11069068059762973582),
576    ],
577    [
578        BaseElement::new(11069068059762973582),
579        BaseElement::new(14868391535953158196),
580        BaseElement::new(13278298489594233127),
581        BaseElement::new(389999932707070822),
582        BaseElement::new(9782021734907796003),
583        BaseElement::new(4829905704463175582),
584        BaseElement::new(7567822018949214430),
585        BaseElement::new(14205019324568680367),
586        BaseElement::new(15489674211196160593),
587        BaseElement::new(17636013826542227504),
588        BaseElement::new(16254215311946436093),
589        BaseElement::new(3641486184877122796),
590    ],
591    [
592        BaseElement::new(3641486184877122796),
593        BaseElement::new(11069068059762973582),
594        BaseElement::new(14868391535953158196),
595        BaseElement::new(13278298489594233127),
596        BaseElement::new(389999932707070822),
597        BaseElement::new(9782021734907796003),
598        BaseElement::new(4829905704463175582),
599        BaseElement::new(7567822018949214430),
600        BaseElement::new(14205019324568680367),
601        BaseElement::new(15489674211196160593),
602        BaseElement::new(17636013826542227504),
603        BaseElement::new(16254215311946436093),
604    ],
605    [
606        BaseElement::new(16254215311946436093),
607        BaseElement::new(3641486184877122796),
608        BaseElement::new(11069068059762973582),
609        BaseElement::new(14868391535953158196),
610        BaseElement::new(13278298489594233127),
611        BaseElement::new(389999932707070822),
612        BaseElement::new(9782021734907796003),
613        BaseElement::new(4829905704463175582),
614        BaseElement::new(7567822018949214430),
615        BaseElement::new(14205019324568680367),
616        BaseElement::new(15489674211196160593),
617        BaseElement::new(17636013826542227504),
618    ],
619    [
620        BaseElement::new(17636013826542227504),
621        BaseElement::new(16254215311946436093),
622        BaseElement::new(3641486184877122796),
623        BaseElement::new(11069068059762973582),
624        BaseElement::new(14868391535953158196),
625        BaseElement::new(13278298489594233127),
626        BaseElement::new(389999932707070822),
627        BaseElement::new(9782021734907796003),
628        BaseElement::new(4829905704463175582),
629        BaseElement::new(7567822018949214430),
630        BaseElement::new(14205019324568680367),
631        BaseElement::new(15489674211196160593),
632    ],
633    [
634        BaseElement::new(15489674211196160593),
635        BaseElement::new(17636013826542227504),
636        BaseElement::new(16254215311946436093),
637        BaseElement::new(3641486184877122796),
638        BaseElement::new(11069068059762973582),
639        BaseElement::new(14868391535953158196),
640        BaseElement::new(13278298489594233127),
641        BaseElement::new(389999932707070822),
642        BaseElement::new(9782021734907796003),
643        BaseElement::new(4829905704463175582),
644        BaseElement::new(7567822018949214430),
645        BaseElement::new(14205019324568680367),
646    ],
647    [
648        BaseElement::new(14205019324568680367),
649        BaseElement::new(15489674211196160593),
650        BaseElement::new(17636013826542227504),
651        BaseElement::new(16254215311946436093),
652        BaseElement::new(3641486184877122796),
653        BaseElement::new(11069068059762973582),
654        BaseElement::new(14868391535953158196),
655        BaseElement::new(13278298489594233127),
656        BaseElement::new(389999932707070822),
657        BaseElement::new(9782021734907796003),
658        BaseElement::new(4829905704463175582),
659        BaseElement::new(7567822018949214430),
660    ],
661    [
662        BaseElement::new(7567822018949214430),
663        BaseElement::new(14205019324568680367),
664        BaseElement::new(15489674211196160593),
665        BaseElement::new(17636013826542227504),
666        BaseElement::new(16254215311946436093),
667        BaseElement::new(3641486184877122796),
668        BaseElement::new(11069068059762973582),
669        BaseElement::new(14868391535953158196),
670        BaseElement::new(13278298489594233127),
671        BaseElement::new(389999932707070822),
672        BaseElement::new(9782021734907796003),
673        BaseElement::new(4829905704463175582),
674    ],
675    [
676        BaseElement::new(4829905704463175582),
677        BaseElement::new(7567822018949214430),
678        BaseElement::new(14205019324568680367),
679        BaseElement::new(15489674211196160593),
680        BaseElement::new(17636013826542227504),
681        BaseElement::new(16254215311946436093),
682        BaseElement::new(3641486184877122796),
683        BaseElement::new(11069068059762973582),
684        BaseElement::new(14868391535953158196),
685        BaseElement::new(13278298489594233127),
686        BaseElement::new(389999932707070822),
687        BaseElement::new(9782021734907796003),
688    ],
689    [
690        BaseElement::new(9782021734907796003),
691        BaseElement::new(4829905704463175582),
692        BaseElement::new(7567822018949214430),
693        BaseElement::new(14205019324568680367),
694        BaseElement::new(15489674211196160593),
695        BaseElement::new(17636013826542227504),
696        BaseElement::new(16254215311946436093),
697        BaseElement::new(3641486184877122796),
698        BaseElement::new(11069068059762973582),
699        BaseElement::new(14868391535953158196),
700        BaseElement::new(13278298489594233127),
701        BaseElement::new(389999932707070822),
702    ],
703    [
704        BaseElement::new(389999932707070822),
705        BaseElement::new(9782021734907796003),
706        BaseElement::new(4829905704463175582),
707        BaseElement::new(7567822018949214430),
708        BaseElement::new(14205019324568680367),
709        BaseElement::new(15489674211196160593),
710        BaseElement::new(17636013826542227504),
711        BaseElement::new(16254215311946436093),
712        BaseElement::new(3641486184877122796),
713        BaseElement::new(11069068059762973582),
714        BaseElement::new(14868391535953158196),
715        BaseElement::new(13278298489594233127),
716    ],
717    [
718        BaseElement::new(13278298489594233127),
719        BaseElement::new(389999932707070822),
720        BaseElement::new(9782021734907796003),
721        BaseElement::new(4829905704463175582),
722        BaseElement::new(7567822018949214430),
723        BaseElement::new(14205019324568680367),
724        BaseElement::new(15489674211196160593),
725        BaseElement::new(17636013826542227504),
726        BaseElement::new(16254215311946436093),
727        BaseElement::new(3641486184877122796),
728        BaseElement::new(11069068059762973582),
729        BaseElement::new(14868391535953158196),
730    ],
731];
732
733// ROUND CONSTANTS
734// ================================================================================================
735
736/// Rescue round constants;
737/// computed using algorithm 5 from <https://eprint.iacr.org/2020/1143.pdf>
738///
739/// The constants are broken up into two arrays ARK1 and ARK2; ARK1 contains the constants for the
740/// first half of Rescue round, and ARK2 contains constants for the second half of Rescue round.
741const ARK1: [[BaseElement; STATE_WIDTH]; NUM_ROUNDS] = [
742    [
743        BaseElement::new(13917550007135091859),
744        BaseElement::new(16002276252647722320),
745        BaseElement::new(4729924423368391595),
746        BaseElement::new(10059693067827680263),
747        BaseElement::new(9804807372516189948),
748        BaseElement::new(15666751576116384237),
749        BaseElement::new(10150587679474953119),
750        BaseElement::new(13627942357577414247),
751        BaseElement::new(2323786301545403792),
752        BaseElement::new(615170742765998613),
753        BaseElement::new(8870655212817778103),
754        BaseElement::new(10534167191270683080),
755    ],
756    [
757        BaseElement::new(14572151513649018290),
758        BaseElement::new(9445470642301863087),
759        BaseElement::new(6565801926598404534),
760        BaseElement::new(12667566692985038975),
761        BaseElement::new(7193782419267459720),
762        BaseElement::new(11874811971940314298),
763        BaseElement::new(17906868010477466257),
764        BaseElement::new(1237247437760523561),
765        BaseElement::new(6829882458376718831),
766        BaseElement::new(2140011966759485221),
767        BaseElement::new(1624379354686052121),
768        BaseElement::new(50954653459374206),
769    ],
770    [
771        BaseElement::new(16288075653722020941),
772        BaseElement::new(13294924199301620952),
773        BaseElement::new(13370596140726871456),
774        BaseElement::new(611533288599636281),
775        BaseElement::new(12865221627554828747),
776        BaseElement::new(12269498015480242943),
777        BaseElement::new(8230863118714645896),
778        BaseElement::new(13466591048726906480),
779        BaseElement::new(10176988631229240256),
780        BaseElement::new(14951460136371189405),
781        BaseElement::new(5882405912332577353),
782        BaseElement::new(18125144098115032453),
783    ],
784    [
785        BaseElement::new(6076976409066920174),
786        BaseElement::new(7466617867456719866),
787        BaseElement::new(5509452692963105675),
788        BaseElement::new(14692460717212261752),
789        BaseElement::new(12980373618703329746),
790        BaseElement::new(1361187191725412610),
791        BaseElement::new(6093955025012408881),
792        BaseElement::new(5110883082899748359),
793        BaseElement::new(8578179704817414083),
794        BaseElement::new(9311749071195681469),
795        BaseElement::new(16965242536774914613),
796        BaseElement::new(5747454353875601040),
797    ],
798    [
799        BaseElement::new(13684212076160345083),
800        BaseElement::new(19445754899749561),
801        BaseElement::new(16618768069125744845),
802        BaseElement::new(278225951958825090),
803        BaseElement::new(4997246680116830377),
804        BaseElement::new(782614868534172852),
805        BaseElement::new(16423767594935000044),
806        BaseElement::new(9990984633405879434),
807        BaseElement::new(16757120847103156641),
808        BaseElement::new(2103861168279461168),
809        BaseElement::new(16018697163142305052),
810        BaseElement::new(6479823382130993799),
811    ],
812    [
813        BaseElement::new(13957683526597936825),
814        BaseElement::new(9702819874074407511),
815        BaseElement::new(18357323897135139931),
816        BaseElement::new(3029452444431245019),
817        BaseElement::new(1809322684009991117),
818        BaseElement::new(12459356450895788575),
819        BaseElement::new(11985094908667810946),
820        BaseElement::new(12868806590346066108),
821        BaseElement::new(7872185587893926881),
822        BaseElement::new(10694372443883124306),
823        BaseElement::new(8644995046789277522),
824        BaseElement::new(1422920069067375692),
825    ],
826    [
827        BaseElement::new(17619517835351328008),
828        BaseElement::new(6173683530634627901),
829        BaseElement::new(15061027706054897896),
830        BaseElement::new(4503753322633415655),
831        BaseElement::new(11538516425871008333),
832        BaseElement::new(12777459872202073891),
833        BaseElement::new(17842814708228807409),
834        BaseElement::new(13441695826912633916),
835        BaseElement::new(5950710620243434509),
836        BaseElement::new(17040450522225825296),
837        BaseElement::new(8787650312632423701),
838        BaseElement::new(7431110942091427450),
839    ],
840];
841
842const ARK2: [[BaseElement; STATE_WIDTH]; NUM_ROUNDS] = [
843    [
844        BaseElement::new(7989257206380839449),
845        BaseElement::new(8639509123020237648),
846        BaseElement::new(6488561830509603695),
847        BaseElement::new(5519169995467998761),
848        BaseElement::new(2972173318556248829),
849        BaseElement::new(14899875358187389787),
850        BaseElement::new(14160104549881494022),
851        BaseElement::new(5969738169680657501),
852        BaseElement::new(5116050734813646528),
853        BaseElement::new(12120002089437618419),
854        BaseElement::new(17404470791907152876),
855        BaseElement::new(2718166276419445724),
856    ],
857    [
858        BaseElement::new(2485377440770793394),
859        BaseElement::new(14358936485713564605),
860        BaseElement::new(3327012975585973824),
861        BaseElement::new(6001912612374303716),
862        BaseElement::new(17419159457659073951),
863        BaseElement::new(11810720562576658327),
864        BaseElement::new(14802512641816370470),
865        BaseElement::new(751963320628219432),
866        BaseElement::new(9410455736958787393),
867        BaseElement::new(16405548341306967018),
868        BaseElement::new(6867376949398252373),
869        BaseElement::new(13982182448213113532),
870    ],
871    [
872        BaseElement::new(10436926105997283389),
873        BaseElement::new(13237521312283579132),
874        BaseElement::new(668335841375552722),
875        BaseElement::new(2385521647573044240),
876        BaseElement::new(3874694023045931809),
877        BaseElement::new(12952434030222726182),
878        BaseElement::new(1972984540857058687),
879        BaseElement::new(14000313505684510403),
880        BaseElement::new(976377933822676506),
881        BaseElement::new(8407002393718726702),
882        BaseElement::new(338785660775650958),
883        BaseElement::new(4208211193539481671),
884    ],
885    [
886        BaseElement::new(2284392243703840734),
887        BaseElement::new(4500504737691218932),
888        BaseElement::new(3976085877224857941),
889        BaseElement::new(2603294837319327956),
890        BaseElement::new(5760259105023371034),
891        BaseElement::new(2911579958858769248),
892        BaseElement::new(18415938932239013434),
893        BaseElement::new(7063156700464743997),
894        BaseElement::new(16626114991069403630),
895        BaseElement::new(163485390956217960),
896        BaseElement::new(11596043559919659130),
897        BaseElement::new(2976841507452846995),
898    ],
899    [
900        BaseElement::new(15090073748392700862),
901        BaseElement::new(3496786927732034743),
902        BaseElement::new(8646735362535504000),
903        BaseElement::new(2460088694130347125),
904        BaseElement::new(3944675034557577794),
905        BaseElement::new(14781700518249159275),
906        BaseElement::new(2857749437648203959),
907        BaseElement::new(8505429584078195973),
908        BaseElement::new(18008150643764164736),
909        BaseElement::new(720176627102578275),
910        BaseElement::new(7038653538629322181),
911        BaseElement::new(8849746187975356582),
912    ],
913    [
914        BaseElement::new(17427790390280348710),
915        BaseElement::new(1159544160012040055),
916        BaseElement::new(17946663256456930598),
917        BaseElement::new(6338793524502945410),
918        BaseElement::new(17715539080731926288),
919        BaseElement::new(4208940652334891422),
920        BaseElement::new(12386490721239135719),
921        BaseElement::new(10010817080957769535),
922        BaseElement::new(5566101162185411405),
923        BaseElement::new(12520146553271266365),
924        BaseElement::new(4972547404153988943),
925        BaseElement::new(5597076522138709717),
926    ],
927    [
928        BaseElement::new(18338863478027005376),
929        BaseElement::new(115128380230345639),
930        BaseElement::new(4427489889653730058),
931        BaseElement::new(10890727269603281956),
932        BaseElement::new(7094492770210294530),
933        BaseElement::new(7345573238864544283),
934        BaseElement::new(6834103517673002336),
935        BaseElement::new(14002814950696095900),
936        BaseElement::new(15939230865809555943),
937        BaseElement::new(12717309295554119359),
938        BaseElement::new(4130723396860574906),
939        BaseElement::new(7706153020203677238),
940    ],
941];
winter_crypto/hash/rescue/rp64_256/mod.rs

winter_crypto/hash/rescue/rp64_256/
mod.rs
