Elliptic Curve and Operator Overloading

Repository

• https://github.com/machingclee/2023-09-10-Elliptic-Curve-in-Rust/tree/main/ECC/src/modules

Prefered Headers to Ignore Annoying Warnings:

1#![allow(unused)]
2#![allow(non_camel_case_types)]
3#![allow(non_snake_case)]

Utility Struct to Perform Arithmetic on $\mathbb Z/ p \mathbb Z$ for BigUint

1struct Fp<'a> {
2    p: &'a BigUint,
3}
4
5impl<'a> Fp<'a> {
6    fn power(&self, u: &BigUint, i: u32) -> BigUint {
7        u.modpow(&BigUint::from(i), &self.p)
8    }
9
10    fn add(&self, u: &BigUint, v: &BigUint) -> BigUint {
11        (u + v).modpow(&BigUint::from(1u32), self.p)
12    }
13    fn mul(&self, u: &BigUint, v: &BigUint) -> BigUint {
14        (u * v).modpow(&BigUint::from(1u32), self.p)
15    }
16    fn add_inverse(&self, u: &BigUint) -> BigUint {
17        assert!(
18            u < &self.p,
19            "{}",
20            format!("{} >= {} should not happen", u, &self.p)
21        );
22        self.p - u
23    }
24    fn mul_inverse(&self, u: &BigUint) -> BigUint {
25        if self.p < &BigUint::from(2u32) {
26            BigUint::from(1u32)
27        } else {
28            let two = BigUint::from(2u32);
29            let power = self.add(&self.p, &self.add_inverse(&two));
30            u.modpow(&power, &self.p)
31        }
32    }
33}

Definition of Addition and Double on Elliptic Curve

1use num_bigint::BigUint;
2
3#[derive(PartialEq, Clone, Debug)]
4enum Point {
5    Coor(BigUint, BigUint),
6    Identity,
7}
8
9struct EllipticCurve {
10    a: BigUint,
11    b: BigUint,
12    p: BigUint,
13}
14
15impl EllipticCurve {
16    fn double(&self, h: &Point) -> Point {
17        let fp = Fp { p: &self.p };
18        let h_on_curve = self.is_on_curve(h);
19        assert!(h_on_curve, "point h is not on the curve");
20        // s = (3*x^2 + a)/(2*y)
21        // x_ = s^2 - 2*x
22        // y_ = s*(x - x_) - y
23        match h {
24            Point::Identity => Point::Identity,
25            Point::Coor(x, y) => {
26                let three_times_xsq = fp.mul(&BigUint::from(3u32), &fp.power(x, 2));
27                let two_times_y = fp.mul(&BigUint::from(2u32), &y);
28                let inverse_two_times_y = fp.mul_inverse(&two_times_y);
29                let s = fp.mul(&fp.add(&three_times_xsq, &self.a), &inverse_two_times_y);
30                let x_ = fp.add(
31                    &fp.power(&s, 2),
32                    &fp.add_inverse(&fp.mul(&BigUint::from(2u32), x)),
33                );
34                let s_times_x_minus_x_ = fp.mul(&s, &fp.add(x, &fp.add_inverse(&x_)));
35                let y_ = fp.add(&s_times_x_minus_x_, &fp.add_inverse(y));
36                Point::Coor(x_, y_)
37            }
38        }
39    }
40
41    fn add(&self, h: &Point, k: &Point) -> Point {
42        let fp = Fp { p: &self.p };
43        let h_on_curve = self.is_on_curve(h);
44        let k_on_curve = self.is_on_curve(k);
45        assert!(*h != *k, "two points should not be the same");
46        assert!(h_on_curve, "point h is not on the curve");
47        assert!(k_on_curve, "point k is not on the curve");
48        match (h, k) {
49            (Point::Identity, _) => k.clone(),
50            (_, Point::Identity) => h.clone(),
51            (Point::Coor(x1, y1), Point::Coor(x2, y2)) => {
52                // s = (y2-y1)/(x2-x1)
53                // x3 = s^2 - x1 - x2
54                // y3 = s*(x1-x3) - y1
55
56                let y1_plus_y2 = fp.add(y1, y2);
57                if x1 == x2 && y1_plus_y2 == BigUint::from(0u32) {
58                    return Point::Identity;
59                }
60
61                let s = fp.mul(
62                    &(y2 + &fp.add_inverse(y1)),
63                    &fp.mul_inverse(&(x2 + &fp.add_inverse(x1))),
64                );
65                let x3 = fp.add(
66                    &fp.add(&fp.power(&s, 2), &fp.add_inverse(x1)),
67                    &fp.add_inverse(x2),
68                );
69
70                let y3 = fp.add(
71                    &fp.mul(&s, &(x1 + &fp.add_inverse(&x3))),
72                    &fp.add_inverse(y1),
73                );
74                Point::Coor(x3, y3)
75            }
76        }
77    }
78
79    fn scalar_mul(&self, c: &Point, d: &BigUint) -> Point {
80        let mut t = c.clone();
81        for i in (0..(d.bits() - 1)).rev() {
82            t = self.double(&t);
83            if d.bit(i) {
84                t = self.add(&t, c);
85            }
86        }
87        t
88    }
89
90    fn is_on_curve(&self, point: &Point) -> bool {
91        let fp = Fp { p: &self.p };
92        if let Point::Coor(x, y) = point {
93            let y2 = fp.power(y, 2);
94            let x3 = fp.power(x, 3);
95            let ax = fp.mul(&self.a, x);
96            y2 == fp.add(&x3, &fp.add(&ax, &self.b))
97        } else {
98            true
99        }
100    }
101}

Operator Overloading

New Struct Field

We wish to convert BigUint into our own struct Field and define all the usual operation on $\mathbb Z/p \mathbb Z$, i.e., among the Field objects.

That is, we wish to overload the operators:

1+ - * /

without the utility struct Fp.

1#[derive(PartialEq, Clone, Debug)]
2pub struct Field<'a> {
3    value: BigUint,
4    p: &'a BigUint,
5}

New Definition of Point and EllipticCurve base on Field

1pub enum Point<'a> {
2    Coor(Field<'a>, Field<'a>),
3    Identity,
4}
5
6pub struct EllipticCurve<'a> {
7    a: Field<'a>,
8    b: Field<'a>,
9}

Operator Overloadings on Field

Implementations

1pub struct Field<'a> {
2    pub value: BigUint,
3    pub p: &'a BigUint,
4}
5impl<'a> Field<'a> {
6    pub fn new(i: u32, p: &'a BigUint) -> Self {
7        Field {
8            value: BigUint::from(i),
9            p,
10        }
11    }
12}
13
14impl<'a> Add<&Field<'a>> for &Field<'a> {
15    type Output = Field<'a>;
16
17    fn add(self, rhs: &Field) -> Self::Output {
18        let value = (&self.value + &rhs.value).modpow(&BigUint::from(1u32), self.p);
19        Field { value, p: self.p }
20    }
21}
22
23impl<'a> Sub<&Field<'a>> for &Field<'a> {
24    type Output = Field<'a>;
25
26    fn sub(self, rhs: &Field) -> Self::Output {
27        let value: BigUint;
28        let a = &self.value;
29        let b = &rhs.value;
30        if a > b {
31            value = a - b;
32        } else {
33            value = (self.p + a) - b;
34        }
35        Field { value, p: &self.p }
36    }
37}
38
39impl<'a> Mul<BigUint> for &Field<'a> {
40    type Output = Field<'a>;
41    fn mul(self, rhs: BigUint) -> Self::Output {
42        let a = &self.value;
43        let value = (a * &rhs).modpow(&BigUint::from(1u32), &self.p);
44        return Field { value, p: self.p };
45    }
46}
47
48impl<'a> Mul<&Field<'a>> for &Field<'a> {
49    type Output = Field<'a>;
50
51    fn mul(self, rhs: &Field) -> Self::Output {
52        let value = (&self.value * &rhs.value).modpow(&BigUint::from(1u32), self.p);
53        Field { value, p: self.p }
54    }
55}
56
57impl<'a> Div<&Field<'a>> for &Field<'a> {
58    type Output = Field<'a>;
59
60    fn div(self, rhs: &Field) -> Self::Output {
61        let left = &self.value;
62        let right = &rhs.value;
63        let p_minus_2 = (self.p - BigUint::from(2u32)).modpow(&BigUint::from(1u32), self.p);
64
65        let multiplicative_inverse_right = right.modpow(&p_minus_2, &self.p);
66        let value = (left * &multiplicative_inverse_right).modpow(&BigUint::from(1u32), self.p);
67        Field { value, p: &self.p }
68    }
69}

Rewrite of EllipticCurve::double With Field in Place of BigUint

1impl<'a> EllipticCurve<'a> {
2		pub fn double(&self, h: &Point<'a>) -> Point {
3        let h_on_curve = self.is_on_curve(h);
4        assert!(h_on_curve, "point h is not on the curve");
5        // s = (3*x^2 + a)/(2*y)
6        // x_ = s^2 - 2*x
7        // y_ = s*(x - x_) - y
8        match h {
9            Point::Identity => Point::Identity,
10            Point::Coor(xp, yp) => {
11                if yp.value == BigUint::from(0u32) {
12                    return Point::Identity;
13                }
14                let two_times_yp = yp * BigUint::from(2u32);
15                let s = xp * xp;
16                let s = &s * BigUint::from(3u32);
17                let s = &s + &self.a;
18                let s = &s / &two_times_yp;
19
20                let two_times_x = xp * BigUint::from(2u32);
21                let new_x = &s * &s;
22                let new_x = &new_x - &two_times_x;
23
24                let new_y = xp - &new_x;
25                let new_y = &s * &new_y;
26                let new_y = &new_y - yp;
27
28                Point::Coor(new_x, new_y)
29            }
30        }
31    }
32}

Rewrite of EllipticCurve::add With Field in Place of BigUint

1impl<'a> EllipticCurve<'a> {
2		pub fn add(&self, h: &Point<'a>, k: &Point<'a>) -> Point {
3        let h_on_curve = self.is_on_curve(h);
4        let k_on_curve = self.is_on_curve(k);
5        assert!(*h != *k, "two points should not be the same");
6        assert!(h_on_curve, "point h is not on the curve");
7        assert!(k_on_curve, "point k is not on the curve");
8        match (h, k) {
9            (Point::Identity, _) => k.to_owned(),
10            (_, Point::Identity) => h.to_owned(),
11            (Point::Coor(x1p, y1p), Point::Coor(x2p, y2p)) => {
12                if x1p == x2p && (y1p + y2p).value == BigUint::from(0u32) {
13                    return Point::Identity;
14                }
15                // s = (y2-y1)/(x2-x1)
16                // x3 = s^2 - x1 - x2
17                // y3 = s*(x1-x3) - y1
18
19                let s = y2p - y1p;
20                let x2_minus_x1 = x2p - x1p;
21                let s = &s / &x2_minus_x1;
22                let s_square = &s * &s;
23
24                let x3p = &s_square - &x1p;
25                let x3p = &x3p - &x2p;
26
27                let y3p = &s * &(x1p - &x3p);
28                let y3p = &y3p - &y1p;
29
30                Point::Coor(x3p, y3p)
31            }
32        }
33    }
34}

Rewrite of EllipticCurve::is_on_curve With Field in Place of BigUint

1impl<'a> EllipticCurve<'a> {
2		fn is_on_curve(&self, point: &Point) -> bool {
3				if let Point::Coor(x, y) = point {
4						let y2 = y * y;
5						let x3 = x * x;
6						let x3 = &x3 * x;
7						let ax = x * &self.a;
8						y2 == &(&x3 + &ax) + &self.b
9				} else {
10						true
11				}
12		}
13}

EllipticCurve::scalar_mul --- the Double and Add Algorithm under Field

1impl<'a> EllipticCurve<'a> {
2    pub fn scalar_mul(&'a self, q: &Point<'a>, k: &Field<'a>) -> Point<'a> {
3        let mut t = q.clone();
4        for i in (0..(k.value.bits() - 1)).rev() {
5            t = self.double(&t);
6            if k.value.bit(i) {
7                t = self.add(&t, q);
8            }
9        }
10        t
11    }
12}

Test Cases

The following 3 cases can pass successfully:

1running 4 tests
2test test::test_ec_point_add_identity ... ok
3test test::test_ec_point_addition ... ok
4test test::test_double ... ok
5test test::test_scalar_mul ... ok

1#[cfg(test)]
2mod test {
3    use super::*;
4    #[test]
5    fn test_ec_point_addition() {
6        let p = BigUint::from(17u32);
7        let ec = EllipticCurve {
8            a: Field::new(2, &p),
9            b: Field::new(2, &p),
10        };
11
12        // (6, 3) + (5, 1) = (10, 6);
13        let p1 = Point::Coor(Field::new(6, &p), Field::new(3, &p));
14        let p2 = Point::Coor(Field::new(5, &p), Field::new(1, &p));
15        let r = Point::Coor(Field::new(10, &p), Field::new(6, &p));
16
17        let res = ec.add(&p1, &p2);
18        assert_eq!(r, res);
19    }
20    #[test]
21    fn test_ec_point_add_identity() {
22        let p = BigUint::from(17u32);
23        let ec = EllipticCurve {
24            a: Field::new(2, &p),
25            b: Field::new(2, &p),
26        };
27
28        // (6, 3) + (5, 1) = (10, 6);
29        let p1 = Point::Coor(Field::new(6, &p), Field::new(3, &p));
30        let p2 = Point::Identity;
31        let expect = Point::Coor(Field::new(6, &p), Field::new(3, &p));
32
33        let result = ec.add(&p1, &p2);
34        assert_eq!(expect, result);
35    }
36
37    #[test]
38    fn test_scalar_mul() {
39        let p = BigUint::from(17u32);
40        let ec = EllipticCurve {
41            a: Field::new(2, &p),
42            b: Field::new(2, &p),
43        };
44        let q = Point::Coor(Field::new(5, &p), Field::new(1, &p));
45        let k = BigUint::from(16u32);
46        let result = ec.scalar_mul(&q, &k);
47
48        let expected = Point::Coor(Field::new(10, &p), Field::new(11, &p));
49        assert_eq!(result, expected);
50    }
51
52    #[test]
53    fn test_double() {
54        let p = BigUint::from(17u32);
55        let ec = EllipticCurve {
56            a: Field::new(2, &p),
57            b: Field::new(2, &p),
58        };
59
60        let p = Point::Coor(Field::new(6, &p), Field::new(3, &p));
61        let double = ec.double(&p);
62        let p_on_curve = ec.is_on_curve(&double);
63        assert!(p_on_curve);
64    }
65}

Specific case: The Secp256k1

Configuration of the values: n(order), p, a, b can be found in this wiki page.

We test our algorithm by the following test case:

1fn test_secp256k1() {
2		let p = BigUint::parse_bytes(
3				b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",
4				16,
5		)
6		.expect("Parsing fail for p");
7
8		let a = BigUint::parse_bytes(
9				b"0000000000000000000000000000000000000000000000000000000000000000",
10				16,
11		)
12		.expect("Parsing fail for a");
13
14		let b = BigUint::parse_bytes(
15				b"0000000000000000000000000000000000000000000000000000000000000007",
16				16,
17		)
18		.expect("Parsing fail for b");
19
20		let n = BigUint::parse_bytes(
21				b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",
22				16,
23		)
24		.expect("Parsing fail for n");
25
26		let x = BigUint::parse_bytes(
27				b"79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
28				16,
29		)
30		.expect("Parsing fail for x");
31
32		let y = BigUint::parse_bytes(
33				b"483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8",
34				16,
35		)
36		.expect("Parsing fail for y");
37
38		let point = Point::Coor(Field { value: x, p: &p }, Field { value: y, p: &p });
39
40		let ec = EllipticCurve {
41				a: Field { value: a, p: &p },
42				b: Field { value: b, p: &p },
43		};
44
45		let result = ec.scalar_mul(&point, &n);
46
47		assert_eq!(Point::Identity, result);
48}

The Elliptic Curve Digital Signature Algorithm (ECDSA)

Statement of the Theorem and Proof

Note that the group of all points on an elliptic curve is not always cyclic. There are some necessary conditions for that group to be cyclic in this post.

Theorem. Let $G$ be a cyclic subgroup of points on an elliptic curve

$$C: y^2 = x^3+ax+b\quad\text{over }\,\mathbb Z_p$$

and $g\in \mathbb Z_p\times \mathbb Z_p$ a given generator of $G$. For a fixed $k_\text{pri}\in \mathbb Z_p$, define $K_\text{pub} = k_\text{pri} g$, then for every $k,z\in \mathbb Z_{|G|}$, there holds

$$\begin{aligned} &\qquad \,\,\,\,\begin{cases} R := \pi_x(kg), \\ S := k^{-1}\big(z +\pi_x(kg) k_\text{pri}\big ) \end{cases}\\ &\implies\pi_x\bigg(\big[S^{-1}z\big]g + \big[S^{-1}R\big]K_\text{pub}\bigg)\equiv \pi_x(kg)\pmod{|G|}. \end{aligned}$$

Where $\pi_x$ denotes the canonical projection to the first coordinate.

In other words, if $(R,S)$ defined above is given to the target receiver, then necessarily

$$\pi_x\bigg(\big[S^{-1}z\big]g + \big[S^{-1}R\big]K_\text{pub}\bigg)\equiv R \pmod{|G|}.$$

• This necessary condition is defined to be the valid condition of a message, where $z=h(m)$ for some hash $h:\texttt{&str}\to\texttt{u32}$ and string $m: \texttt{&str}$ the message.
• The tuple $(R,S)$ is called the signature of the message.

Note that here $K_\text{pub}$ is called a public key, $k_\text{pri}$ a private key and $k$ a random number.

It has to be careful that $k\cdot g$ is calculated on $\mathbb Z_p$ but the message validation above are operated on $\mathbb Z_{|G|}$.

Coding

1#![allow(unused)]
2#![allow(non_snake_case)]
3
4use core::panic;
5
6use crate::modules::elliptic_curve::{EllipticCurve, Field, Point};
7use crate::modules::field_utils::Futil;
8use num_bigint::{BigUint, RandBigInt};
9use rand::{self, Rng};
10use sha256::{digest, try_digest};
11
12#[derive(PartialEq, Clone, Debug)]
13pub struct ECDSA<'a> {
14    pub elliptic_curve: EllipticCurve<'a>,
15    pub generator: Point<'a>,
16    pub order: BigUint,
17}
18
19impl<'a> ECDSA<'a> {
20    pub fn generate_key_pair(&'a self) -> (BigUint, Point<'a>) {
21        let priv_key = self.generate_private_key();
22        let pub_key = self.generate_public_key(&priv_key);
23        return (priv_key, pub_key);
24    }
25
26    pub fn generate_private_key(&self) -> BigUint {
27        self.generate_random_positive_number_less_than(&self.order)
28    }
29
30    pub fn generate_random_positive_number_less_than(&self, max: &BigUint) -> BigUint {
31        let mut rng = rand::thread_rng();
32        rng.gen_biguint_range(&BigUint::from(1u32), &max)
33    }
34
35    pub fn generate_public_key(&'a self, priv_key: &BigUint) -> Point<'a> {
36        self.elliptic_curve.scalar_mul(&self.generator, priv_key)
37    }
38
39    pub fn sign(&'a self, hash: &BigUint, priv_key: &BigUint, k_random: &BigUint) -> (BigUint, BigUint) {
40        assert!(hash < &self.order, "Hash is bigger than the order of Elliptic Curve");
41        assert!(
42            priv_key < &self.order,
43            "Private key has value bigger than the order of Elliptic Curve"
44        );
45        assert!(k_random < &self.order, "k_random has value bigger than the order of Elliptic Curve");
46        let g = &self.generator;
47        let z = hash;
48        let k_pri = priv_key;
49        let kg = self.elliptic_curve.scalar_mul(g, &k_random);
50
51        match kg {
52            Point::Identity => panic!("Public key should not be an identity."),
53            Point::Coor(kg_x, _) => {
54                let R = kg_x.value;
55
56                let S = Futil::mul(&R, &priv_key, &self.order);
57                let S = Futil::add(&z, &S, &self.order);
58                let S = Futil::mul(&Futil::mul_inverse(k_random, &self.order), &S, &self.order);
59                (R, S)
60            }
61        }
62    }
63
64    pub fn verify(&self, hash: &BigUint, pub_key: &Point, signature: &(BigUint, BigUint)) -> bool {
65        assert!(hash < &self.order, "Hash is bigger than the order of the elliptic curve");
66        let (R, S) = signature;
67        let z = hash;
68        let P = self.elliptic_curve.add(
69            // &self.elliptic_curve.scalar_mul(&self.generator, (z / S)),
70            &self
71                .elliptic_curve
72                .scalar_mul(&self.generator, &Futil::mul(&z, &Futil::mul_inverse(S, &self.order), &self.order)),
73            &self
74                .elliptic_curve
75                .scalar_mul(pub_key, &Futil::mul(R, &Futil::mul_inverse(S, &self.order), &self.order)),
76        );
77
78        if let Point::Coor(X, Y) = &P {
79            (&X.value - R).modpow(&BigUint::from(1u32), &self.order) == BigUint::from(0u32)
80        } else {
81            false
82        }
83    }
84
85    pub fn generate_hash_less_than(&self, message: &str, max: &BigUint) -> BigUint {
86        let digested = digest(message);
87        let bytes = hex::decode(&digested).expect("Cannot convert to Vec<u8>");
88        let one = BigUint::from(1u32);
89        let hash = BigUint::from_bytes_be(&bytes).modpow(&one, &(max - &one));
90        let hash = hash + one;
91        hash
92    }
93}

Tests

1#[cfg(test)]
2mod test {
3    use crate::modules::curves::{Curve, CurveConfig};
4
5    use super::*;
6    #[test]
7    fn test_sign_verify() {
8        let p = BigUint::from(17u32);
9        let ec = EllipticCurve {
10            a: Field::new(2, &p),
11            b: Field::new(2, &p),
12        };
13        let gp_order = BigUint::from(19u32);
14        let g = Point::Coor(Field::new(5, &p), Field::new(1, &p));
15
16        let ecdsa = ECDSA {
17            elliptic_curve: ec,
18            generator: g,
19            order: gp_order,
20        };
21
22        let priv_key = BigUint::from(7u32);
23        let pub_key = ecdsa.generate_public_key(&priv_key);
24
25        let hash = Field::new(10, &p);
26        let k_random = BigUint::from(18u32);
27
28        let message = "Bob -> 1BTC -> Alice";
29        let hash_ = ecdsa.generate_hash_less_than(message, &ecdsa.order);
30        let hash = BigUint::from(hash_);
31        let signature = ecdsa.sign(&hash, &priv_key, &k_random);
32        let verify_result = ecdsa.verify(&hash, &pub_key, &signature);
33        assert!(verify_result);
34    }
35
36    #[test]
37    fn test_sign_tempered_verify() {
38        let p = BigUint::from(17u32);
39        let ec = EllipticCurve {
40            a: Field::new(2, &p),
41            b: Field::new(2, &p),
42        };
43        let gp_order = BigUint::from(19u32);
44        let g = Point::Coor(Field::new(5, &p), Field::new(1, &p));
45
46        let ecdsa = ECDSA {
47            elliptic_curve: ec,
48            generator: g,
49            order: gp_order,
50        };
51
52        let priv_key = BigUint::from(7u32);
53        let pub_key = ecdsa.generate_public_key(&priv_key);
54
55        let hash = Field::new(10, &p);
56        let k_random = BigUint::from(18u32);
57
58        let message = "Bob -> 1BTC -> Alice";
59        let hash_ = ecdsa.generate_hash_less_than(message, &ecdsa.order);
60        let hash = BigUint::from(hash_);
61        let signature = ecdsa.sign(&hash, &priv_key, &k_random);
62        let (R, S) = signature;
63        let R = R + BigUint::from(1u32);
64        let R = Futil::power(&R, 1, &ecdsa.order);
65
66        let tempered_signature = (R, S);
67        let verify_result = ecdsa.verify(&hash, &pub_key, &tempered_signature);
68        assert!(!verify_result);
69    }
70
71    #[test]
72    fn test_secp256_sign_verify_tempered<'a>() {
73        let CurveConfig { a, b, generator, order, p } = Curve::get_Secp256k1_config();
74        let (x, y) = generator;
75        let generator = Point::Coor(Field { value: x, p: &p }, Field { value: y, p: &p });
76        let ec = Curve::get_elliptic_cuve(&p, &a, &b);
77        let ecdsa = Curve::get_ecdsa(&ec, &generator, &order);
78
79        // modifiied from the order n
80        let priv_key = BigUint::parse_bytes(b"FFFFF0000FFF0F0F0F0F0F0F0F0F0F0EBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
81            .expect("Cannot parse into interger");
82        let pub_key = ecdsa.generate_public_key(&priv_key);
83
84        let hash = Field::new(10, &p);
85        let k_random = ecdsa.generate_random_positive_number_less_than(&order);
86
87        let message = "Bob -> 1BTC -> Alice";
88        let hash_ = ecdsa.generate_hash_less_than(message, &ecdsa.order);
89        let hash = BigUint::from(hash_);
90        let signature = ecdsa.sign(&hash, &priv_key, &k_random);
91
92        // let verify_result = ecdsa.verify(&hash, &pub_key, &signature);
93        // println!("hash: {}", hash);
94        // assert!(verify_result);
95
96        let (R, S) = signature;
97        let R = R + BigUint::from(1u32);
98        let R = Futil::power(&R, 1, &ecdsa.order);
99
100        let tempered_signature = (R, S);
101        let verify_result = ecdsa.verify(&hash, &pub_key, &tempered_signature);
102        assert!(!verify_result);
103    }
104}