sp1_curves/weierstrass/
secp256k1.rs

1//! Modulo defining the Secp256k1 curve and its base field. The constants are all taken from
2//! https://en.bitcoin.it/wiki/Secp256k1.
3
4use std::str::FromStr;
5
6use elliptic_curve::{sec1::ToEncodedPoint, subtle::Choice};
7use generic_array::GenericArray;
8use k256::{elliptic_curve::point::DecompressPoint, FieldElement};
9use num::{
10    traits::{FromBytes, ToBytes},
11    BigUint, Zero,
12};
13use serde::{Deserialize, Serialize};
14use typenum::{U32, U62};
15
16use super::{SwCurve, WeierstrassParameters};
17use crate::{
18    params::{FieldParameters, NumLimbs},
19    AffinePoint, CurveType, EllipticCurve, EllipticCurveParameters,
20};
21
22#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
23/// Secp256k1 curve parameter
24pub struct Secp256k1Parameters;
25
26pub type Secp256k1 = SwCurve<Secp256k1Parameters>;
27
28#[derive(Debug, Default, Clone, Copy, PartialEq, Serialize, Deserialize)]
29/// Secp256k1 base field parameter
30pub struct Secp256k1BaseField;
31
32impl FieldParameters for Secp256k1BaseField {
33    const MODULUS: &'static [u8] = &[
34        0x2f, 0xfc, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
35        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
36        0xff, 0xff,
37    ];
38
39    /// A rough witness-offset estimate given the size of the limbs and the size of the field.
40    const WITNESS_OFFSET: usize = 1usize << 14;
41
42    fn modulus() -> BigUint {
43        BigUint::from_bytes_le(Self::MODULUS)
44    }
45}
46
47impl NumLimbs for Secp256k1BaseField {
48    type Limbs = U32;
49    type Witness = U62;
50}
51
52impl EllipticCurveParameters for Secp256k1Parameters {
53    type BaseField = Secp256k1BaseField;
54    const CURVE_TYPE: CurveType = CurveType::Secp256k1;
55}
56
57impl WeierstrassParameters for Secp256k1Parameters {
58    const A: GenericArray<u8, U32> = GenericArray::from_array([
59        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
60        0, 0,
61    ]);
62
63    const B: GenericArray<u8, U32> = GenericArray::from_array([
64        7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
65        0, 0,
66    ]);
67    fn generator() -> (BigUint, BigUint) {
68        let x = BigUint::from_str(
69            "55066263022277343669578718895168534326250603453777594175500187360389116729240",
70        )
71        .unwrap();
72        let y = BigUint::from_str(
73            "32670510020758816978083085130507043184471273380659243275938904335757337482424",
74        )
75        .unwrap();
76        (x, y)
77    }
78
79    fn prime_group_order() -> num::BigUint {
80        BigUint::from_slice(&[
81            0xD0364141, 0xBFD25E8C, 0xAF48A03B, 0xBAAEDCE6, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF,
82            0xFFFFFFFF,
83        ])
84    }
85
86    fn a_int() -> BigUint {
87        BigUint::zero()
88    }
89
90    fn b_int() -> BigUint {
91        BigUint::from(7u32)
92    }
93}
94
95pub fn secp256k1_decompress<E: EllipticCurve>(bytes_be: &[u8], sign: u32) -> AffinePoint<E> {
96    let computed_point =
97        k256::AffinePoint::decompress(bytes_be.into(), Choice::from(sign as u8)).unwrap();
98    let point = computed_point.to_encoded_point(false);
99
100    let x = BigUint::from_bytes_be(point.x().unwrap());
101    let y = BigUint::from_bytes_be(point.y().unwrap());
102    AffinePoint::<E>::new(x, y)
103}
104
105pub fn secp256k1_sqrt(n: &BigUint) -> BigUint {
106    let be_bytes = n.to_be_bytes();
107    let mut bytes = [0_u8; 32];
108    bytes[32 - be_bytes.len()..].copy_from_slice(&be_bytes);
109    let fe = FieldElement::from_bytes(&bytes.into()).unwrap();
110    let result_bytes = fe.sqrt().unwrap().normalize().to_bytes();
111    BigUint::from_be_bytes(&result_bytes as &[u8])
112}
113
114#[cfg(test)]
115mod tests {
116    #![allow(clippy::print_stdout)]
117
118    use super::*;
119    use crate::utils::biguint_from_limbs;
120    use num::bigint::RandBigInt;
121    use rand::thread_rng;
122
123    #[test]
124    fn test_weierstrass_biguint_scalar_mul() {
125        assert_eq!(biguint_from_limbs(Secp256k1BaseField::MODULUS), Secp256k1BaseField::modulus());
126    }
127
128    #[test]
129    fn test_secp256k_sqrt() {
130        let mut rng = thread_rng();
131        for _ in 0..10 {
132            // Check that sqrt(x^2)^2 == x^2
133            // We use x^2 since not all field elements have a square root
134            let x = rng.gen_biguint(256) % Secp256k1BaseField::modulus();
135            let x_2 = (&x * &x) % Secp256k1BaseField::modulus();
136            let sqrt = secp256k1_sqrt(&x_2);
137
138            println!("sqrt: {sqrt}");
139
140            let sqrt_2 = (&sqrt * &sqrt) % Secp256k1BaseField::modulus();
141
142            assert_eq!(sqrt_2, x_2);
143        }
144    }
145}
sp1_curves/weierstrass/secp256k1.rs

sp1_curves/weierstrass/
secp256k1.rs
