fp2 0.1.3

An efficient, flexible and constant time Rust implementation of the extension field Fp^2 with modulus x^2 + 1
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

mod dlp_tests {
    use ::sha2::Digest as _;

    static MODULUS: [u64; 4] = [
        0xFFFFFFFFFFFFFFFF,
        0xFFFFFFFFFFFFFFFF,
        0xFFFFFFFFFFFFFFFF,
        0x04FFFFFFFFFFFFFF,
    ];
    static X_STR: &str = "5f33b0e1f6bc51f2699fb8becd1774f318f43a005ae24c723bb9baab3a62ac02b56ce2daf2cc76b04bfbd2703cafc470c14531ad68793d18a764b57a3c171700";

    fp2::define_fp2_from_modulus!(typename = FpExt, base_typename = Fp, modulus = MODULUS,);

    #[test]
    fn test_element_order() {
        // ensure x is an element of order 2^248
        let (mut x, r) = FpExt::decode(&hex::decode(X_STR).unwrap());
        assert!(r == u32::MAX);

        // Compute x^(2^127) this should be equal to -1
        for _ in 0..247 {
            x.set_square();
        }
        assert!(x.equals(&FpExt::MINUS_ONE) == u32::MAX);

        // Assert x has order exactly 2^128
        x.set_square();
        assert!(x.equals(&FpExt::ONE) == u32::MAX);
    }

    // Compute x^a for a 128-bit random a
    fn compute_challenge(x: &FpExt, y: &mut FpExt) {
        // We hash the encoding of y to create a new y = x^exp
        let mut exp = [0u8; 31];
        let mut sh = ::sha2::Sha256::new();
        sh.update(y.encode());
        exp.copy_from_slice(&sh.finalize_reset()[0..31]);

        *y = x.pow(&exp, 248);
    }

    #[test]
    fn test_dlp_n() {
        // x is a precomputed element of order 2^248
        let (x, r) = FpExt::decode(&hex::decode(X_STR).unwrap());
        assert!(r == u32::MAX);

        let mut y = FpExt::ONE;

        // Run the test 100 times
        for _ in 0..25 {
            compute_challenge(&x, &mut y);

            let (exp, check) = x.solve_dlp_2e(&y, 248, None);
            let z = x.pow(&exp, 248);
            assert!(check == u32::MAX);
            assert!(z.equals(&y) == u32::MAX);
        }
    }

    #[test]
    fn test_dlp_n_with_table() {
        // x is a precomputed element of order 2^248
        let (x, r) = FpExt::decode(&hex::decode(X_STR).unwrap());
        assert!(r == u32::MAX);

        let mut y = FpExt::ONE;

        let (dlp_table, ele_table, check) = x.precompute_dlp_tables(248);
        assert!(check == u32::MAX);

        for _ in 0..25 {
            compute_challenge(&x, &mut y);

            let (exp, check) = x.solve_dlp_2e(&y, 248, Some((&dlp_table, &ele_table)));
            let z = x.pow(&exp, 248);
            assert!(check == u32::MAX);
            assert!(z.equals(&y) == u32::MAX);
        }
    }
}