halo2curves/secp256k1/
curve.rs

Help
1use core::{
2    cmp,
3    fmt::Debug,
4    iter::Sum,
5    ops::{Add, Mul, Neg, Sub},
6};
7
8use rand::RngCore;
9use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
10
11use crate::{
12    ff::{Field, PrimeField, WithSmallOrderMulGroup},
13    group::{prime::PrimeCurveAffine, Curve, Group as _, GroupEncoding},
14    impl_binops_additive, impl_binops_additive_specify_output, impl_binops_multiplicative,
15    impl_binops_multiplicative_mixed, new_curve_impl,
16    secp256k1::{Fp, Fq},
17    Coordinates, CurveAffine, CurveExt,
18};
19
20impl group::cofactor::CofactorGroup for Secp256k1 {
21    type Subgroup = Secp256k1;
22
23    fn clear_cofactor(&self) -> Self {
24        *self
25    }
26
27    fn into_subgroup(self) -> CtOption<Self::Subgroup> {
28        CtOption::new(self, 1.into())
29    }
30
31    fn is_torsion_free(&self) -> Choice {
32        1.into()
33    }
34}
35
36// Reference: https://neuromancer.sk/std/secg/secp256k1
37const SECP_GENERATOR_X: Fp = Fp::from_raw([
38    0x59F2815B16F81798,
39    0x029BFCDB2DCE28D9,
40    0x55A06295CE870B07,
41    0x79BE667EF9DCBBAC,
42]);
43const SECP_GENERATOR_Y: Fp = Fp::from_raw([
44    0x9C47D08FFB10D4B8,
45    0xFD17B448A6855419,
46    0x5DA4FBFC0E1108A8,
47    0x483ADA7726A3C465,
48]);
49
50const SECP_A: Fp = Fp::from_raw([0, 0, 0, 0]);
51const SECP_B: Fp = Fp::from_raw([7, 0, 0, 0]);
52
53new_curve_impl!(
54    (pub),
55    Secp256k1,
56    Secp256k1Affine,
57    Fp,
58    Fq,
59    (SECP_GENERATOR_X,SECP_GENERATOR_Y),
60    SECP_A,
61    SECP_B,
62    "secp256k1",
63    |domain_prefix| hash_to_curve(domain_prefix, hash_to_curve_suite(b"secp256k1_XMD:SHA-256_SSWU_RO_")),
64    crate::serde::CompressedFlagConfig::Extra,
65    standard_sign
66);
67
68fn hash_to_curve_suite(domain: &[u8]) -> crate::hash_to_curve::Suite<Secp256k1, sha2::Sha256, 48> {
69    // Z = -11 (reference: <https://www.rfc-editor.org/rfc/rfc9380.html#name-suites-for-secp256k1>)
70    // 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc24
71    const SSWU_Z: Fp = Fp::from_raw([
72        0xfffffffefffffc24,
73        0xffffffffffffffff,
74        0xffffffffffffffff,
75        0xffffffffffffffff,
76    ]);
77
78    // E': y'^2 = x'^3 + A' * x' + B', where
79    // A': 0x3f8731abdd661adca08a5558f0f5d272e953d363cb6f0e5d405447c01a444533
80    // B': 1771
81    // (reference: <https://www.rfc-editor.org/rfc/rfc9380.html#name-suites-for-secp256k1>)
82    pub const ISO_SECP_A: Fp = Fp::from_raw([
83        0x405447c01a444533,
84        0xe953d363cb6f0e5d,
85        0xa08a5558f0f5d272,
86        0x3f8731abdd661adc,
87    ]);
88
89    pub const ISO_SECP_B: Fp = Fp::from_raw([1771, 0, 0, 0]);
90
91    let iso_map = crate::hash_to_curve::Iso {
92        a: ISO_SECP_A,
93        b: ISO_SECP_B,
94        map: Box::new(iso_map),
95    };
96
97    crate::hash_to_curve::Suite::new(domain, SSWU_Z, crate::hash_to_curve::Method::SSWU(iso_map))
98}
99
100#[allow(clippy::type_complexity)]
101pub(crate) fn hash_to_curve<'a>(
102    domain_prefix: &'a str,
103    suite: crate::hash_to_curve::Suite<Secp256k1, sha2::Sha256, 48>,
104) -> Box<dyn Fn(&[u8]) -> Secp256k1 + 'a> {
105    Box::new(move |message| suite.hash_to_curve(domain_prefix, message))
106}
107
108/// 3-Isogeny Map for Secp256k1
109/// Reference: <https://www.rfc-editor.org/rfc/rfc9380.html#name-3-isogeny-map-for-secp256k1>
110pub(crate) fn iso_map(x: Fp, y: Fp, z: Fp) -> Secp256k1 {
111    // constants for secp256k1 iso_map computation
112    const K: [[Fp; 4]; 5] = [
113        [Fp::ZERO; 4],
114        [
115            Fp::from_raw([
116                0x8e38e38daaaaa8c7,
117                0x38e38e38e38e38e3,
118                0xe38e38e38e38e38e,
119                0x8e38e38e38e38e38,
120            ]),
121            Fp::from_raw([
122                0xdfff1044f17c6581,
123                0xd595d2fc0bf63b92,
124                0xb9f315cea7fd44c5,
125                0x7d3d4c80bc321d5,
126            ]),
127            Fp::from_raw([
128                0x4ecbd0b53d9dd262,
129                0xe4506144037c4031,
130                0xe2a413deca25caec,
131                0x534c328d23f234e6,
132            ]),
133            Fp::from_raw([
134                0x8e38e38daaaaa88c,
135                0x38e38e38e38e38e3,
136                0xe38e38e38e38e38e,
137                0x8e38e38e38e38e38,
138            ]),
139        ],
140        [
141            Fp::from_raw([
142                0x9fe6b745781eb49b,
143                0x86cd409542f8487d,
144                0x9ca34ccbb7b640dd,
145                0xd35771193d94918a,
146            ]),
147            Fp::from_raw([
148                0xc52a56612a8c6d14,
149                0x06d36b641f5e41bb,
150                0xf7c4b2d51b542254,
151                0xedadc6f64383dc1d,
152            ]),
153            Fp::ZERO,
154            Fp::ZERO,
155        ],
156        [
157            Fp::from_raw([
158                0xa12f684b8e38e23c,
159                0x2f684bda12f684bd,
160                0x684bda12f684bda1,
161                0x4bda12f684bda12f,
162            ]),
163            Fp::from_raw([
164                0xdffc90fc201d71a3,
165                0x647ab046d686da6f,
166                0xa9d0a54b12a0a6d5,
167                0xc75e0c32d5cb7c0f,
168            ]),
169            Fp::from_raw([
170                0xa765e85a9ecee931,
171                0x722830a201be2018,
172                0x715209ef6512e576,
173                0x29a6194691f91a73,
174            ]),
175            Fp::from_raw([
176                0x84bda12f38e38d84,
177                0xbda12f684bda12f6,
178                0xa12f684bda12f684,
179                0x2f684bda12f684bd,
180            ]),
181        ],
182        [
183            Fp::from_raw([
184                0xfffffffefffff93b,
185                0xffffffffffffffff,
186                0xffffffffffffffff,
187                0xffffffffffffffff,
188            ]),
189            Fp::from_raw([
190                0xdfb425d2685c2573,
191                0x9467c1bfc8e8d978,
192                0xd5e9e6632722c298,
193                0x7a06534bb8bdb49f,
194            ]),
195            Fp::from_raw([
196                0xa7bf8192bfd2a76f,
197                0x0a3d21162f0d6299,
198                0xf3a70c3fa8fe337e,
199                0x6484aa716545ca2c,
200            ]),
201            Fp::ZERO,
202        ],
203    ];
204
205    let z2 = z.square();
206    let z3 = z2 * z;
207
208    // iso_map logic (avoid inversion) in projective coordinates
209    //   reference: <https://github.com/zcash/pasta_curves/blob/main/src/hashtocurve.rs#L80-L106>
210    let x_num = ((K[1][3] * x + K[1][2] * z) * x + K[1][1] * z2) * x + K[1][0] * z3;
211    let x_den = (z * x + K[2][1] * z2) * x + K[2][0] * z3;
212
213    let y_num = (((K[3][3] * x + K[3][2] * z) * x + K[3][1] * z2) * x + K[3][0] * z3) * y;
214    let y_den = (((x + K[4][2] * z) * x + K[4][1] * z2) * x + K[4][0] * z3) * z;
215
216    let z = x_den * y_den;
217    let x = x_num * y_den;
218    let y = y_num * x_den;
219
220    Secp256k1 { x, y, z }
221}
222
223#[cfg(test)]
224mod test {
225    use group::UncompressedEncoding;
226    use rand_core::OsRng;
227
228    use super::*;
229    use crate::{serde::SerdeObject, tests::curve::TestH2C};
230
231    crate::curve_testing_suite!(Secp256k1);
232    crate::curve_testing_suite!(Secp256k1, "endo_consistency");
233    crate::curve_testing_suite!(Secp256k1, "ecdsa_example");
234    crate::curve_testing_suite!(
235        Secp256k1,
236        "constants",
237        Fp::MODULUS,
238        SECP_A,
239        SECP_B,
240        SECP_GENERATOR_X,
241        SECP_GENERATOR_Y,
242        Fq::MODULUS
243    );
244
245    #[test]
246    fn test_hash_to_curve() {
247        // Test vectors are taken from
248        // https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#name-expand_message_xmdsha-256
249        [
250            TestH2C::<Secp256k1Affine>::new(
251                b"",
252                crate::tests::point_from_hex(
253                    "c1cae290e291aee617ebaef1be6d73861479c48b841eaba9b7b5852ddfeb1346",
254                    "64fa678e07ae116126f08b022a94af6de15985c996c3a91b64c406a960e51067",
255                ),
256            ),
257            TestH2C::<Secp256k1Affine>::new(
258                b"abc",
259                crate::tests::point_from_hex(
260                    "3377e01eab42db296b512293120c6cee72b6ecf9f9205760bd9ff11fb3cb2c4b",
261                    "7f95890f33efebd1044d382a01b1bee0900fb6116f94688d487c6c7b9c8371f6",
262                ),
263            ),
264            TestH2C::<Secp256k1Affine>::new(
265                b"abcdef0123456789",
266                crate::tests::point_from_hex(
267                    "bac54083f293f1fe08e4a70137260aa90783a5cb84d3f35848b324d0674b0e3a",
268                    "4436476085d4c3c4508b60fcf4389c40176adce756b398bdee27bca19758d828",
269                ),
270            ),
271            TestH2C::<Secp256k1Affine>::new(
272                b"q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq",
273                crate::tests::point_from_hex(
274                    "e2167bc785333a37aa562f021f1e881defb853839babf52a7f72b102e41890e9",
275                    "f2401dd95cc35867ffed4f367cd564763719fbc6a53e969fb8496a1e6685d873",
276                ),
277            ), //
278            TestH2C::<Secp256k1Affine>::new(
279                b"a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
280                crate::tests::point_from_hex(
281                    "e3c8d35aaaf0b9b647e88a0a0a7ee5d5bed5ad38238152e4e6fd8c1f8cb7c998",
282                    "8446eeb6181bf12f56a9d24e262221cc2f0c4725c7e3803024b5888ee5823aa6",
283                ),
284            ),
285        ].iter().for_each(|test| {
286            test.run("QUUX-V01-CS02-with-");
287        });
288    }
289}
halo2curves/secp256k1/curve.rs

halo2curves/secp256k1/
curve.rs
