ec_generic/
elliptic_curve.rs

1/*!
2This crate is a minimal and easy-to-use elliptic curve library. This library
3allows to perform the following operations over an elliptic curve finite cyclic
4group:
5
6- Point Addition: `R = P + Q`
7- Point Doubling: `R = P + P = 2 * P`
8- Scalar Multiplication: `R = d * P`
9
10A generic elliptic curve is defined as `y^2 = x^3 + ax + b mod p`, and in this
11particular library the constrains are:
12
13 - `p` should be **a prime number** bigger than 3
14 - `4 a^3 + 27 b^2 != 0`
15
16The library could be use in any cryptographic algorithm that requires elliptic
17curve groups, for example:
18
19- Digital Signature Algorithm (DSA)
20- Zero-Knowledge Proofs (ZKP)
21
22# Usage
23
24This crate is [on crates.io](https://crates.io/crates/regex) and can be
25used by adding `regex` to your dependencies in your project's `Cargo.toml`.
26
27```toml
28[dependencies]
29ec_generic = "0.1.14"
30```
31
32## Example: `y^2 = x^3 + 2x + 2 mod 17`
33
34```rust
35use ec_generic::{EllipticCurve, Point};
36use num_bigint::BigUint;
37
38let ec = EllipticCurve {
39    a: BigUint::from(2u32),
40    b: BigUint::from(2u32),
41    p: BigUint::from(17u32),
42};
43
44// (6,3) + (5,1) = (10,6)
45let p1 = Point::Coor(BigUint::from(6u32), BigUint::from(3u32));
46let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
47let pr = Ok(Point::Coor(BigUint::from(10u32), BigUint::from(6u32)));
48
49let res = ec.add(&p1, &p2);
50assert_eq!(res, pr);
51
52let res = ec.add(&p2, &p1);
53assert_eq!(res, pr);
54```
55
56## Example: `secp256k1`: `y^2 = x^3 + 7 mod p (large)`
57
58```rust
59use ec_generic::{EllipticCurve, Point};
60use num_bigint::BigUint;
61
62let p = BigUint::parse_bytes(
63    b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",
64    16,
65)
66.expect("could not convert p");
67
68let n = BigUint::parse_bytes(
69    b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",
70    16,
71)
72.expect("could not convert n");
73
74let gx = BigUint::parse_bytes(
75    b"79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
76    16,
77)
78.expect("could not convert gx");
79
80let gy = BigUint::parse_bytes(
81    b"483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8",
82    16,
83)
84.expect("could not convert gy");
85
86let ec = EllipticCurve {
87    a: BigUint::from(0u32),
88    b: BigUint::from(7u32),
89    p,
90};
91
92let g = Point::Coor(gx, gy);
93
94// n * G = I (Identity)
95let res = ec.scalar_mul(&g, &n);
96
97assert_eq!(res, Ok(Point::Identity));
98```
99
100*/
101
102use crate::finite_fields::FiniteField;
103use num_bigint::BigUint;
104
105///
106/// This represents a point in the elliptic curve. The identity element is such
107/// that:
108///
109///  - `A - A = I`
110///  - `A + I = A`
111///  - `I + I = 2 * I = I`
112///
113#[derive(PartialEq, Clone, Debug)]
114pub enum Point {
115    Coor(BigUint, BigUint),
116    Identity,
117}
118
119#[derive(PartialEq, Debug)]
120pub enum EllipticCurveError {
121    InvalidPoint(Point),
122    InvalidScalar(BigUint),
123}
124
125///
126/// This represents an elliptic curve of the form
127/// y^2 = x^3 + ax + b mod p
128///
129#[derive(PartialEq, Clone, Debug)]
130pub struct EllipticCurve {
131    pub a: BigUint,
132    pub b: BigUint,
133    pub p: BigUint,
134}
135
136impl EllipticCurve {
137    ///
138    /// Perform a point addition: `C = A + B` where `A` and `B` are points which
139    /// belong to the curve. Geometrically speaking, the point `C` is the
140    /// x-reflection of the intersection of the lines that passes through `A`
141    /// and `B` and intersects the curve.
142    ///
143    pub fn add(&self, a: &Point, b: &Point) -> Result<Point, EllipticCurveError> {
144        if !self.is_on_curve(a) {
145            return Err(EllipticCurveError::InvalidPoint(a.clone()));
146        }
147
148        if !self.is_on_curve(b) {
149            return Err(EllipticCurveError::InvalidPoint(b.clone()));
150        }
151
152        if *a == *b {
153            return self.double(a);
154        }
155
156        match (a, b) {
157            (Point::Identity, _) => Ok(b.clone()),
158            (_, Point::Identity) => Ok(a.clone()),
159            (Point::Coor(x1, y1), Point::Coor(x2, y2)) => {
160                // Check that they are not additive inverses
161                let y1plusy2 = FiniteField::add(y1, y2, &self.p).unwrap();
162
163                if x1 == x2 && y1plusy2 == BigUint::from(0u32) {
164                    return Ok(Point::Identity);
165                }
166
167                // s = (y2 - y1) / (x2 - x1) mod p
168                let numerator = FiniteField::subtract(y2, y1, &self.p).unwrap();
169                let denominator = FiniteField::subtract(x2, x1, &self.p).unwrap();
170
171                let s = FiniteField::divide(&numerator, &denominator, &self.p).unwrap();
172
173                let (x3, y3) = self.compute_x3_y3(x1, y1, x2, &s);
174
175                Ok(Point::Coor(x3, y3))
176            }
177        }
178    }
179
180    ///
181    /// Perform a point doubling: `B = A + A = 2 * A` where `A` is a point in
182    /// the curve. Geometrically speaking, the point `B` is the intersection of
183    /// the tangent line over A that intersects the curve.
184    ///
185    pub fn double(&self, a: &Point) -> Result<Point, EllipticCurveError> {
186        if !self.is_on_curve(a) {
187            return Err(EllipticCurveError::InvalidPoint(a.clone()));
188        }
189
190        match a {
191            Point::Identity => Ok(Point::Identity),
192            Point::Coor(x1, y1) => {
193                if *y1 == BigUint::from(0u32) {
194                    return Ok(Point::Identity);
195                }
196
197                // s = (3 * x1^2 + a) / (2 * y1) mod p
198                let numerator = x1.modpow(&BigUint::from(2u32), &self.p);
199                let numerator =
200                    FiniteField::mult(&BigUint::from(3u32), &numerator, &self.p).unwrap();
201                let numerator = FiniteField::add(&self.a, &numerator, &self.p).unwrap();
202
203                let denominator = FiniteField::mult(&BigUint::from(2u32), y1, &self.p).unwrap();
204                let s = FiniteField::divide(&numerator, &denominator, &self.p).unwrap();
205
206                let (x3, y3) = self.compute_x3_y3(x1, y1, x1, &s);
207
208                Ok(Point::Coor(x3, y3))
209            }
210        }
211    }
212
213    ///
214    /// computes the resulting point of the addition:
215    ///  `C(x3,y3) = A(x1,y1) + B(x2,y2)`:
216    ///
217    /// `s` is given as input and should be computed differently depending on it
218    /// is point doubling or point addition:
219    ///
220    /// - `B != A => s = (y2 - y1) / (x2 - x1) mod p`
221    /// - `B == A => s = (3 * x1^2 + a) / (2 * y1) mod p`
222    ///
223    /// Result:
224    ///
225    /// - `x3 = s^2 - x1 - x2 mod p`
226    /// - `y3 = s(x1 - x3) - y1 mod p`
227    ///
228    fn compute_x3_y3(
229        &self,
230        x1: &BigUint,
231        y1: &BigUint,
232        x2: &BigUint,
233        s: &BigUint,
234    ) -> (BigUint, BigUint) {
235        let s2 = s.modpow(&BigUint::from(2u32), &self.p);
236        let x3 = FiniteField::subtract(&s2, x1, &self.p).unwrap();
237        let x3 = FiniteField::subtract(&x3, x2, &self.p).unwrap();
238
239        let y3 = FiniteField::subtract(x1, &x3, &self.p).unwrap();
240        let y3 = FiniteField::mult(s, &y3, &self.p).unwrap();
241        let y3 = FiniteField::subtract(&y3, y1, &self.p).unwrap();
242
243        (x3, y3)
244    }
245
246    ///
247    /// Perform a scalar multiplication of a point: `B = d * A` where `A` is a
248    /// point in the curve and `d > 0` is a positive scalar of any value.
249    ///
250    /// It uses the addition/doubling algorithm
251    ///
252    /// ```text
253    ///  T = A
254    ///  for i in [(bits of d)-1), 0]
255    ///       T = 2 * T
256    ///       if bit i of d == 1
257    ///           T = T + A
258    /// ```
259    ///
260    pub fn scalar_mul(&self, a: &Point, d: &BigUint) -> Result<Point, EllipticCurveError> {
261        if *d == BigUint::from(0u32) {
262            return Err(EllipticCurveError::InvalidScalar(d.clone()));
263        }
264
265        let mut t = a.clone();
266        for i in (0..(d.bits() - 1)).rev() {
267            t = self.double(&t)?;
268            if d.bit(i) {
269                t = self.add(&t, a)?;
270            }
271        }
272        Ok(t)
273    }
274
275    ///
276    /// Checks if a point A = (x,y) belongs to the elliptic curve:
277    ///
278    /// if `y^2 = x^3 + a * x + b mod p` then returns `true`, if not, returns
279    /// `false`.
280    ///
281    pub fn is_on_curve(&self, a: &Point) -> bool {
282        match a {
283            Point::Coor(x, y) => {
284                let y2 = y.modpow(&BigUint::from(2u32), &self.p);
285                let x3 = x.modpow(&BigUint::from(3u32), &self.p);
286                let ax = FiniteField::mult(&self.a, x, &self.p).unwrap();
287                let x3plusax = FiniteField::add(&x3, &ax, &self.p).unwrap();
288
289                y2 == FiniteField::add(&x3plusax, &self.b, &self.p).unwrap()
290            }
291            Point::Identity => true,
292        }
293    }
294}
295
296#[cfg(test)]
297mod test {
298
299    use super::*;
300
301    #[test]
302    fn test_point_in_curve() {
303        // y^2 = x^3 + 2x + 2 mod 17
304        let ec = EllipticCurve {
305            a: BigUint::from(2u32),
306            b: BigUint::from(2u32),
307            p: BigUint::from(17u32),
308        };
309
310        // (6,3) + (5,1) = (10,6)
311        let p1 = Point::Coor(BigUint::from(6u32), BigUint::from(3u32));
312        let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
313        let p3 = Point::Coor(BigUint::from(10u32), BigUint::from(6u32));
314
315        assert!(ec.is_on_curve(&p1));
316        assert!(ec.is_on_curve(&p2));
317        assert!(ec.is_on_curve(&p3));
318
319        let p4 = Point::Coor(BigUint::from(4u32), BigUint::from(1u32));
320        let p5 = Point::Coor(BigUint::from(1u32), BigUint::from(1u32));
321        let p6 = Point::Coor(BigUint::from(0u32), BigUint::from(1u32));
322
323        assert!(!ec.is_on_curve(&p4));
324        assert!(!ec.is_on_curve(&p5));
325        assert!(!ec.is_on_curve(&p6));
326    }
327
328    #[test]
329    fn test_point_addition() {
330        // y^2 = x^3 + 2x + 2 mod 17
331        let ec = EllipticCurve {
332            a: BigUint::from(2u32),
333            b: BigUint::from(2u32),
334            p: BigUint::from(17u32),
335        };
336
337        // (6,3) + (5,1) = (10,6)
338        let p1 = Point::Coor(BigUint::from(6u32), BigUint::from(3u32));
339        let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
340        let pr = Ok(Point::Coor(BigUint::from(10u32), BigUint::from(6u32)));
341
342        let res = ec.add(&p1, &p2);
343        assert_eq!(res, pr);
344
345        let res = ec.add(&p2, &p1);
346        assert_eq!(res, pr);
347
348        // (5,1) + (5,1) = (6,3)
349        let p1 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
350        let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
351        let pr = Ok(Point::Coor(BigUint::from(6u32), BigUint::from(3u32)));
352
353        let res = ec.add(&p1, &p2);
354        assert_eq!(res, pr);
355
356        // (10, 6) + (5, 1) = (3,1)
357        let p1 = Point::Coor(BigUint::from(10u32), BigUint::from(6u32));
358        let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
359        let pr = Ok(Point::Coor(BigUint::from(3u32), BigUint::from(1u32)));
360
361        let res = ec.add(&p1, &p2);
362        assert_eq!(res, pr);
363
364        // (16, 13) + (5, 1) = (0, 6)
365        let p1 = Point::Coor(BigUint::from(16u32), BigUint::from(13u32));
366        let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
367        let pr = Ok(Point::Coor(BigUint::from(0u32), BigUint::from(6u32)));
368
369        let res = ec.add(&p1, &p2);
370        assert_eq!(res, pr);
371
372        // (6,3) + I = (6,3)
373        let p1 = Point::Coor(BigUint::from(6u32), BigUint::from(3u32));
374
375        let res = ec.add(&p1, &Point::Identity);
376        assert_eq!(res, Ok(p1.clone()));
377
378        let res = ec.add(&Point::Identity, &p1);
379        assert_eq!(res, Ok(p1.clone()));
380
381        // I + I = 2 * I = I
382        let res = ec.add(&Point::Identity, &Point::Identity);
383        assert_eq!(res, Ok(Point::Identity));
384
385        // (5,16) + (5,1) = I
386        let p1 = Point::Coor(BigUint::from(5u32), BigUint::from(16u32));
387        let p2 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
388
389        let res = ec.add(&p1, &p2);
390        assert_eq!(res, Ok(Point::Identity));
391
392        let res = ec.add(&p2, &p1);
393        assert_eq!(res, Ok(Point::Identity));
394    }
395
396    #[test]
397    fn test_point_doubling() {
398        // y^2 = x^3 + 2x + 2 mod 17
399        let ec = EllipticCurve {
400            a: BigUint::from(2u32),
401            b: BigUint::from(2u32),
402            p: BigUint::from(17u32),
403        };
404
405        // (5,1) + (5,1) = 2 (5, 1) = (6,3)
406        let p1 = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
407        let pr = Ok(Point::Coor(BigUint::from(6u32), BigUint::from(3u32)));
408
409        let res = ec.double(&p1);
410        assert_eq!(res, pr);
411
412        // I + I = 2 * I = I
413        let res = ec.double(&Point::Identity);
414        assert_eq!(res, Ok(Point::Identity));
415    }
416
417    #[test]
418    fn test_scalar_multiplication() {
419        // y^2 = x^3 + 2x + 2 mod 17   |G| = 19  19 * A = I
420        let ec = EllipticCurve {
421            a: BigUint::from(2u32),
422            b: BigUint::from(2u32),
423            p: BigUint::from(17u32),
424        };
425
426        let a = Point::Coor(BigUint::from(5u32), BigUint::from(1u32));
427
428        // 2 * (5, 1) = (6,3)
429        let pr = Ok(Point::Coor(BigUint::from(6u32), BigUint::from(3u32)));
430        let res = ec.scalar_mul(&a, &BigUint::from(2u32));
431        assert_eq!(res, pr);
432
433        // 10 * (5, 1) = (7,11)
434        let pr = Ok(Point::Coor(BigUint::from(7u32), BigUint::from(11u32)));
435        let res = ec.scalar_mul(&a, &BigUint::from(10u32));
436        assert_eq!(res, pr);
437
438        // 15 * (5, 1) = (3,16)
439        let pr = Ok(Point::Coor(BigUint::from(3u32), BigUint::from(16u32)));
440        let res = ec.scalar_mul(&a, &BigUint::from(15u32));
441        assert_eq!(res, pr);
442
443        // 16 * (5, 1) = (10,11)
444        let pr = Ok(Point::Coor(BigUint::from(10u32), BigUint::from(11u32)));
445        let res = ec.scalar_mul(&a, &BigUint::from(16u32));
446        assert_eq!(res, pr);
447
448        // 17 * (5, 1) = (6,14)
449        let pr = Ok(Point::Coor(BigUint::from(6u32), BigUint::from(14u32)));
450        let res = ec.scalar_mul(&a, &BigUint::from(17u32));
451        assert_eq!(res, pr);
452
453        // 18 * (5, 1) = (5,16)
454        let pr = Ok(Point::Coor(BigUint::from(5u32), BigUint::from(16u32)));
455        let res = ec.scalar_mul(&a, &BigUint::from(18u32));
456        assert_eq!(res, pr);
457
458        // 19 * (5, 1) = I
459        let pr = Ok(Point::Identity);
460        let res = ec.scalar_mul(&a, &BigUint::from(19u32));
461        assert_eq!(res, pr);
462
463        // 2 * (10, 6) = (16,13)
464        let p1 = Point::Coor(BigUint::from(10u32), BigUint::from(6u32));
465        let pr = Ok(Point::Coor(BigUint::from(16u32), BigUint::from(13u32)));
466
467        let res = ec.double(&p1);
468        assert_eq!(res, pr);
469    }
470
471    #[test]
472    fn test_ec_secp256k1() {
473        /*
474          y^2 = x^3 + 7 mod p (large)
475
476          p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
477          n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
478        G = (
479            x = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798,
480            y = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
481        )
482        a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
483        b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
484        */
485
486        // n * G = I
487        let p = BigUint::parse_bytes(
488            b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",
489            16,
490        )
491        .expect("could not convert p");
492
493        let n = BigUint::parse_bytes(
494            b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",
495            16,
496        )
497        .expect("could not convert n");
498
499        let gx = BigUint::parse_bytes(
500            b"79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
501            16,
502        )
503        .expect("could not convert gx");
504
505        let gy = BigUint::parse_bytes(
506            b"483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8",
507            16,
508        )
509        .expect("could not convert gy");
510
511        let ec = EllipticCurve {
512            a: BigUint::from(0u32),
513            b: BigUint::from(7u32),
514            p,
515        };
516
517        let g = Point::Coor(gx, gy);
518
519        let res = ec.scalar_mul(&g, &n); // n * G
520        assert_eq!(res, Ok(Point::Identity));
521
522        // p = 1201 * G -> it is also a generator
523        let p = ec.scalar_mul(&g, &BigUint::from(1201u32)).unwrap();
524
525        let res = ec.scalar_mul(&p, &n); // n * p
526        assert_eq!(res, Ok(Point::Identity));
527    }
528}
ec_generic/elliptic_curve.rs

ec_generic/
elliptic_curve.rs
