p256/arithmetic/
hash2curve.rs

1use super::FieldElement;
2use crate::{AffinePoint, FieldBytes, NistP256, ProjectivePoint, Scalar};
3use elliptic_curve::{
4    bigint::{ArrayEncoding, U256},
5    consts::U48,
6    generic_array::GenericArray,
7    hash2curve::{FromOkm, GroupDigest, MapToCurve, OsswuMap, OsswuMapParams, Sgn0},
8    point::DecompressPoint,
9    subtle::Choice,
10};
11
12impl GroupDigest for NistP256 {
13    type FieldElement = FieldElement;
14}
15
16impl FromOkm for FieldElement {
17    type Length = U48;
18
19    fn from_okm(data: &GenericArray<u8, Self::Length>) -> Self {
20        const F_2_192: FieldElement = FieldElement(U256::from_be_hex(
21            "00000000000000030000000200000000fffffffffffffffefffffffeffffffff",
22        ));
23
24        let mut d0_bytes = FieldBytes::default();
25        d0_bytes[8..].copy_from_slice(&data[..24]);
26        let d0 = FieldElement::from_uint_unchecked(U256::from_be_byte_array(d0_bytes));
27
28        let mut d1_bytes = FieldBytes::default();
29        d1_bytes[8..].copy_from_slice(&data[24..]);
30        let d1 = FieldElement::from_uint_unchecked(U256::from_be_byte_array(d1_bytes));
31
32        d0 * F_2_192 + d1
33    }
34}
35
36impl Sgn0 for FieldElement {
37    fn sgn0(&self) -> Choice {
38        self.is_odd()
39    }
40}
41
42impl OsswuMap for FieldElement {
43    const PARAMS: OsswuMapParams<Self> = OsswuMapParams {
44        c1: &[
45            0xffff_ffff_ffff_ffff,
46            0x0000_0000_3fff_ffff,
47            0x4000_0000_0000_0000,
48            0x3fff_ffff_c000_0000,
49        ],
50        c2: FieldElement(U256::from_be_hex(
51            "a3323851ba997e271ac5d59c3298bf50b2806c63966a1a6653e43951f64fdbe7",
52        )),
53        map_a: FieldElement(U256::from_be_hex(
54            "fffffffc00000004000000000000000000000003fffffffffffffffffffffffc",
55        )),
56        map_b: FieldElement(U256::from_be_hex(
57            "dc30061d04874834e5a220abf7212ed6acf005cd78843090d89cdf6229c4bddf",
58        )),
59        z: FieldElement(U256::from_be_hex(
60            "fffffff50000000b00000000000000000000000afffffffffffffffffffffff5",
61        )),
62    };
63}
64
65impl MapToCurve for FieldElement {
66    type Output = ProjectivePoint;
67
68    fn map_to_curve(&self) -> Self::Output {
69        let (qx, qy) = self.osswu();
70
71        // TODO(tarcieri): assert that `qy` is correct? less circuitous conversion?
72        AffinePoint::decompress(&qx.to_bytes(), qy.is_odd())
73            .unwrap()
74            .into()
75    }
76}
77
78impl FromOkm for Scalar {
79    type Length = U48;
80
81    fn from_okm(data: &GenericArray<u8, Self::Length>) -> Self {
82        const F_2_192: Scalar = Scalar(U256::from_be_hex(
83            "0000000000000001000000000000000000000000000000000000000000000000",
84        ));
85
86        let mut d0 = GenericArray::default();
87        d0[8..].copy_from_slice(&data[0..24]);
88        let d0 = Scalar(U256::from_be_byte_array(d0));
89
90        let mut d1 = GenericArray::default();
91        d1[8..].copy_from_slice(&data[24..]);
92        let d1 = Scalar(U256::from_be_byte_array(d1));
93
94        d0 * F_2_192 + d1
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use crate::{FieldElement, NistP256, Scalar, U256};
101    use elliptic_curve::{
102        bigint::{ArrayEncoding, NonZero, U384},
103        consts::U48,
104        generic_array::GenericArray,
105        group::cofactor::CofactorGroup,
106        hash2curve::{self, ExpandMsgXmd, FromOkm, GroupDigest, MapToCurve},
107        sec1::{self, ToEncodedPoint},
108        Curve, Field,
109    };
110    use hex_literal::hex;
111    use proptest::{num::u64::ANY, prelude::ProptestConfig, proptest};
112    use sha2::Sha256;
113
114    #[allow(dead_code)] // TODO(tarcieri): fix commented out code
115    #[test]
116    fn hash_to_curve() {
117        struct TestVector {
118            msg: &'static [u8],
119            p_x: [u8; 32],
120            p_y: [u8; 32],
121            u_0: [u8; 32],
122            u_1: [u8; 32],
123            q0_x: [u8; 32],
124            q0_y: [u8; 32],
125            q1_x: [u8; 32],
126            q1_y: [u8; 32],
127        }
128
129        const DST: &[u8] = b"QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_RO_";
130
131        const TEST_VECTORS: &[TestVector] = &[
132            TestVector {
133                msg: b"",
134                p_x: hex!("2c15230b26dbc6fc9a37051158c95b79656e17a1a920b11394ca91c44247d3e4"),
135                p_y: hex!("8a7a74985cc5c776cdfe4b1f19884970453912e9d31528c060be9ab5c43e8415"),
136                u_0: hex!("ad5342c66a6dd0ff080df1da0ea1c04b96e0330dd89406465eeba11582515009"),
137                u_1: hex!("8c0f1d43204bd6f6ea70ae8013070a1518b43873bcd850aafa0a9e220e2eea5a"),
138                q0_x: hex!("ab640a12220d3ff283510ff3f4b1953d09fad35795140b1c5d64f313967934d5"),
139                q0_y: hex!("dccb558863804a881d4fff3455716c836cef230e5209594ddd33d85c565b19b1"),
140                q1_x: hex!("51cce63c50d972a6e51c61334f0f4875c9ac1cd2d3238412f84e31da7d980ef5"),
141                q1_y: hex!("b45d1a36d00ad90e5ec7840a60a4de411917fbe7c82c3949a6e699e5a1b66aac"),
142            },
143            TestVector {
144                msg: b"abc",
145                p_x: hex!("0bb8b87485551aa43ed54f009230450b492fead5f1cc91658775dac4a3388a0f"),
146                p_y: hex!("5c41b3d0731a27a7b14bc0bf0ccded2d8751f83493404c84a88e71ffd424212e"),
147                u_0: hex!("afe47f2ea2b10465cc26ac403194dfb68b7f5ee865cda61e9f3e07a537220af1"),
148                u_1: hex!("379a27833b0bfe6f7bdca08e1e83c760bf9a338ab335542704edcd69ce9e46e0"),
149                q0_x: hex!("5219ad0ddef3cc49b714145e91b2f7de6ce0a7a7dc7406c7726c7e373c58cb48"),
150                q0_y: hex!("7950144e52d30acbec7b624c203b1996c99617d0b61c2442354301b191d93ecf"),
151                q1_x: hex!("019b7cb4efcfeaf39f738fe638e31d375ad6837f58a852d032ff60c69ee3875f"),
152                q1_y: hex!("589a62d2b22357fed5449bc38065b760095ebe6aeac84b01156ee4252715446e"),
153            },
154            TestVector {
155                msg: b"abcdef0123456789",
156                p_x: hex!("65038ac8f2b1def042a5df0b33b1f4eca6bff7cb0f9c6c1526811864e544ed80"),
157                p_y: hex!("cad44d40a656e7aff4002a8de287abc8ae0482b5ae825822bb870d6df9b56ca3"),
158                u_0: hex!("0fad9d125a9477d55cf9357105b0eb3a5c4259809bf87180aa01d651f53d312c"),
159                u_1: hex!("b68597377392cd3419d8fcc7d7660948c8403b19ea78bbca4b133c9d2196c0fb"),
160                q0_x: hex!("a17bdf2965eb88074bc01157e644ed409dac97cfcf0c61c998ed0fa45e79e4a2"),
161                q0_y: hex!("4f1bc80c70d411a3cc1d67aeae6e726f0f311639fee560c7f5a664554e3c9c2e"),
162                q1_x: hex!("7da48bb67225c1a17d452c983798113f47e438e4202219dd0715f8419b274d66"),
163                q1_y: hex!("b765696b2913e36db3016c47edb99e24b1da30e761a8a3215dc0ec4d8f96e6f9"),
164            },
165            TestVector {
166                msg: b"q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq",
167                p_x: hex!("4be61ee205094282ba8a2042bcb48d88dfbb609301c49aa8b078533dc65a0b5d"),
168                p_y: hex!("98f8df449a072c4721d241a3b1236d3caccba603f916ca680f4539d2bfb3c29e"),
169                u_0: hex!("3bbc30446f39a7befad080f4d5f32ed116b9534626993d2cc5033f6f8d805919"),
170                u_1: hex!("76bb02db019ca9d3c1e02f0c17f8baf617bbdae5c393a81d9ce11e3be1bf1d33"),
171                q0_x: hex!("c76aaa823aeadeb3f356909cb08f97eee46ecb157c1f56699b5efebddf0e6398"),
172                q0_y: hex!("776a6f45f528a0e8d289a4be12c4fab80762386ec644abf2bffb9b627e4352b1"),
173                q1_x: hex!("418ac3d85a5ccc4ea8dec14f750a3a9ec8b85176c95a7022f391826794eb5a75"),
174                q1_y: hex!("fd6604f69e9d9d2b74b072d14ea13050db72c932815523305cb9e807cc900aff"),
175            },
176            TestVector {
177                msg: b"a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
178                p_x: hex!("457ae2981f70ca85d8e24c308b14db22f3e3862c5ea0f652ca38b5e49cd64bc5"),
179                p_y: hex!("ecb9f0eadc9aeed232dabc53235368c1394c78de05dd96893eefa62b0f4757dc"),
180                u_0: hex!("4ebc95a6e839b1ae3c63b847798e85cb3c12d3817ec6ebc10af6ee51adb29fec"),
181                u_1: hex!("4e21af88e22ea80156aff790750121035b3eefaa96b425a8716e0d20b4e269ee"),
182                q0_x: hex!("d88b989ee9d1295df413d4456c5c850b8b2fb0f5402cc5c4c7e815412e926db8"),
183                q0_y: hex!("bb4a1edeff506cf16def96afff41b16fc74f6dbd55c2210e5b8f011ba32f4f40"),
184                q1_x: hex!("a281e34e628f3a4d2a53fa87ff973537d68ad4fbc28d3be5e8d9f6a2571c5a4b"),
185                q1_y: hex!("f6ed88a7aab56a488100e6f1174fa9810b47db13e86be999644922961206e184"),
186            },
187        ];
188
189        for test_vector in TEST_VECTORS {
190            // in parts
191            let mut u = [FieldElement::default(), FieldElement::default()];
192            hash2curve::hash_to_field::<ExpandMsgXmd<Sha256>, FieldElement>(
193                &[test_vector.msg],
194                &[DST],
195                &mut u,
196            )
197            .unwrap();
198
199            /// Assert that the provided projective point matches the given test vector.
200            // TODO(tarcieri): use coordinate APIs. See zkcrypto/group#30
201            macro_rules! assert_point_eq {
202                ($actual:expr, $expected_x:expr, $expected_y:expr) => {
203                    let point = $actual.to_affine().to_encoded_point(false);
204                    let (actual_x, actual_y) = match point.coordinates() {
205                        sec1::Coordinates::Uncompressed { x, y } => (x, y),
206                        _ => unreachable!(),
207                    };
208
209                    assert_eq!(&$expected_x, actual_x.as_slice());
210                    assert_eq!(&$expected_y, actual_y.as_slice());
211                };
212            }
213
214            assert_eq!(u[0].to_bytes().as_slice(), test_vector.u_0);
215            assert_eq!(u[1].to_bytes().as_slice(), test_vector.u_1);
216
217            let q0 = u[0].map_to_curve();
218            assert_point_eq!(q0, test_vector.q0_x, test_vector.q0_y);
219
220            let q1 = u[1].map_to_curve();
221            assert_point_eq!(q1, test_vector.q1_x, test_vector.q1_y);
222
223            let p = q0.clear_cofactor() + q1.clear_cofactor();
224            assert_point_eq!(p, test_vector.p_x, test_vector.p_y);
225
226            // complete run
227            let pt = NistP256::hash_from_bytes::<ExpandMsgXmd<Sha256>>(&[test_vector.msg], &[DST])
228                .unwrap();
229            assert_point_eq!(pt, test_vector.p_x, test_vector.p_y);
230        }
231    }
232
233    /// Taken from <https://www.ietf.org/archive/id/draft-irtf-cfrg-voprf-16.html#name-oprfp-256-sha-256-2>.
234    #[test]
235    fn hash_to_scalar_voprf() {
236        struct TestVector {
237            dst: &'static [u8],
238            key_info: &'static [u8],
239            seed: &'static [u8],
240            sk_sm: &'static [u8],
241        }
242
243        const TEST_VECTORS: &[TestVector] = &[
244            TestVector {
245                dst: b"DeriveKeyPairVOPRF10-\x00\x00\x03",
246                key_info: b"test key",
247                seed: &hex!("a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3"),
248                sk_sm: &hex!("274d7747cf2e26352ecea6bd768c426087da3dfcd466b6841b441ada8412fb33"),
249            },
250            TestVector {
251                dst: b"DeriveKeyPairVOPRF10-\x01\x00\x03",
252                key_info: b"test key",
253                seed: &hex!("a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3"),
254                sk_sm: &hex!("b3d12edba73e40401fdc27c0094a56337feb3646d1633345af7e7142a6b1559d"),
255            },
256            TestVector {
257                dst: b"DeriveKeyPairVOPRF10-\x02\x00\x03",
258                key_info: b"test key",
259                seed: &hex!("a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3"),
260                sk_sm: &hex!("59519f6c7da344f340ad35ad895a5b97437673cc3ac8b964b823cdb52c932f86"),
261            },
262        ];
263
264        'outer: for test_vector in TEST_VECTORS {
265            let key_info_len = u16::try_from(test_vector.key_info.len())
266                .unwrap()
267                .to_be_bytes();
268
269            for counter in 0_u8..=u8::MAX {
270                let scalar = NistP256::hash_to_scalar::<ExpandMsgXmd<Sha256>>(
271                    &[
272                        test_vector.seed,
273                        &key_info_len,
274                        test_vector.key_info,
275                        &counter.to_be_bytes(),
276                    ],
277                    &[test_vector.dst],
278                )
279                .unwrap();
280
281                if !bool::from(scalar.is_zero()) {
282                    assert_eq!(scalar.to_bytes().as_slice(), test_vector.sk_sm);
283                    continue 'outer;
284                }
285            }
286
287            panic!("deriving key failed");
288        }
289    }
290
291    #[test]
292    fn from_okm_fuzz() {
293        let mut wide_order = GenericArray::default();
294        wide_order[16..].copy_from_slice(&NistP256::ORDER.to_be_byte_array());
295        let wide_order = NonZero::new(U384::from_be_byte_array(wide_order)).unwrap();
296
297        let simple_from_okm = move |data: GenericArray<u8, U48>| -> Scalar {
298            let data = U384::from_be_slice(&data);
299
300            let scalar = data % wide_order;
301            let reduced_scalar = U256::from_be_slice(&scalar.to_be_byte_array()[16..]);
302
303            Scalar(reduced_scalar)
304        };
305
306        proptest!(ProptestConfig::with_cases(1000), |(b0 in ANY, b1 in ANY, b2 in ANY, b3 in ANY, b4 in ANY, b5 in ANY)| {
307            let mut data = GenericArray::default();
308            data[..8].copy_from_slice(&b0.to_be_bytes());
309            data[8..16].copy_from_slice(&b1.to_be_bytes());
310            data[16..24].copy_from_slice(&b2.to_be_bytes());
311            data[24..32].copy_from_slice(&b3.to_be_bytes());
312            data[32..40].copy_from_slice(&b4.to_be_bytes());
313            data[40..].copy_from_slice(&b5.to_be_bytes());
314
315            let from_okm = Scalar::from_okm(&data);
316            let simple_from_okm = simple_from_okm(data);
317            assert_eq!(from_okm, simple_from_okm);
318        });
319    }
320}
p256/arithmetic/hash2curve.rs

p256/arithmetic/
hash2curve.rs
