isogeny_walks.h File Reference

#include "fp2.h"

Include dependency graph for isogeny_walks.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
void	fp2_mul_by_1488 (fp2_t *output, fp2_t input)
void	fp2_mul_by_2976 (fp2_t *output, fp2_t input)
void	fp2_mul_by_162000 (fp2_t *output, fp2_t input)
void	fp2_mul_by_324000 (fp2_t *output, fp2_t input)
void	fp2_mul_by_2532192 (fp2_t *output, fp2_t input)
void	fp2_mul_by_645205500 (fp2_t *output, fp2_t input)
void	fp2_mul_by_8748000000 (fp2_t *output, fp2_t input)
void	isogeny_walks_2 (fp2_t *output, fp2_t input_prev, fp2_t input, const uint8_t *input_path, size_t input_length)
void	isogeny_walks_from_montgomery_model_2 (fp2_t *output_j, fp2_t input_A)
void	isogeny_walks_get_previous_step_2 (fp2_t *output_j, fp2_t input_A)
void	isogeny_walks_sample_bit_string (uint8_t *output)
void	isogeny_walks_2_slow (fp2_t *j0, fp2_t *j1, fp2_t input_prev, fp2_t input, const uint8_t *input_path, size_t input_length)
void	isogeny_walks_3 (fp2_t *output_a1, fp2_t *output_a3, fp2_t input_a1, fp2_t input_a3, const uint8_t *input_path, size_t input_length)
void	isogeny_walks_get_points_3 (fp2_t *output, fp2_t input_A)
void	isogeny_walks_from_montgomery_model_3 (fp2_t *output_a1, fp2_t *output_a3, fp2_t input_A, fp2_t input_xP)
void	isogeny_walks_switch_from_model_3 (fp2_t *output_j, fp2_t input_a1, fp2_t input_a3)
void	isogeny_walks_sample_trit_string (uint8_t *output)
void	isogeny_walks_get_points_3_fp (fp_t *output, const fp_t *input_A)
void	isogeny_walks_to_montgomery_model_3_fp (fp_t *output_A, const fp_t *input_t)
void	isogeny_walks_3_fp (fp_t output_A, const fp_t input_A, int input_length)

Function Documentation

fp2_mul_by_1488()

void fp2_mul_by_1488	(	fp2_t *	output,
		fp2_t	input )

Definition at line 11 of file isogeny_walks_2.c.

                                                 {
    fp2_t r, s, t;
    
    fp2_add(&r, input, input); //    2 × input
    fp2_add(&s, r, input);     //    3 × input
    fp2_add(&t, r, s);         //    5 × input
    fp2_add(&t, t, t);         //   10 × input
 
    fp2_add(&t, t, t);         //   20 × input
    fp2_add(&t, t, s);         //   23 × input
    fp2_add(&t, t, t);         //   46 × input
    fp2_add(&t, t, t);         //   92 × input
 
    fp2_add(&t, t, input);     //   93 × input
    fp2_add(&t, t, t);         //  186 × input
    fp2_add(&t, t, t);         //  372 × input
    fp2_add(&t, t, t);         //  744 × input
 
    fp2_add(output, t, t);     // 1488 × input
}

References fp2_add.

Referenced by fp2_mul_by_2976().

Here is the caller graph for this function:

fp2_mul_by_162000()

void fp2_mul_by_162000	(	fp2_t *	output,
		fp2_t	input )

Definition at line 37 of file isogeny_walks_2.c.

                                                   {
    fp2_t r, s, t;
    fp2_add(&r, input, input); //      2 × input
    fp2_add(&r, r, r);         //      4 × input
    fp2_add(&r, r, r);         //      8 × input
    fp2_add(&r, r, input);     //      9 × input
 
    fp2_add(&s, r, r);         //     18 × input
    fp2_add(&s, s, s);         //     36 × input
    fp2_add(&s, s, s);         //     72 × input
    fp2_add(&t, s, r);         //     81 × input
 
    fp2_add(&s, t, s);         //    153 × input
    fp2_add(&s, s, s);         //    306 × input
    fp2_add(&s, s, s);         //    612 × input
    fp2_add(&s, s, s);         //   1224 × input
 
    fp2_add(&s, s, s);         //   2448 × input
    fp2_add(&t, s, t);         //   2529 × input
    fp2_add(&t, t, t);         //   5058 × input
    fp2_add(&t, t, t);         //  10116 × input
 
    fp2_add(&t, t, r);         //  10125 × input
    fp2_add(&t, t, t);         //  20250 × input
    fp2_add(&t, t, t);         //  40500 × input
    fp2_add(&t, t, t);         //  81000 × input
    
    fp2_add(output, t, t);     // 162000 × input
}

References fp2_add.

Referenced by fp2_mul_by_324000(), isogeny_walks_2(), and isogeny_walks_2_slow().

Here is the caller graph for this function:

fp2_mul_by_2532192()

void fp2_mul_by_2532192	(	fp2_t *	output,
		fp2_t	input )

Definition at line 72 of file isogeny_walks_2.c.

                                                    {
    fp2_t r, s, t, u, v;
 
    fp2_add(&r, input, input); //       2 × input
    fp2_add(&s, r, input);     //       3 × input
    fp2_add(&t, s, s);         //       6 × input
    fp2_add(&t, t, t);         //      12 × input
    
    fp2_add(&t, t, t);         //      24 × input
    fp2_add(&u, t, s);         //      27 × input
    fp2_add(&v, u, t);         //      51 × input
    fp2_add(&t, v, v);         //     102 × input
 
    fp2_add(&t, t, v);         //     153 × input
    fp2_add(&t, t, t);         //     306 × input
    fp2_add(&t, t, s);         //     309 × input
    fp2_add(&t, t, t);         //     618 × input
 
    fp2_add(&t, t, t);         //    1236 × input
    fp2_add(&t, t, t);         //    2472 × input
    fp2_add(&t, t, t);         //    4944 × input
    fp2_add(&t, t, t);         //    9888 × input
 
    fp2_add(&t, t, t);         //   19776 × input
    fp2_add(&t, t, t);         //   39552 × input
    fp2_add(&t, t, t);         //   79104 × input
    fp2_add(&t, t, u);         //   79131 × input
 
    fp2_add(&t, t, t);         //  158262 × input
    fp2_add(&t, t, t);         //  316524 × input
    fp2_add(&t, t, t);         //  633048 × input
    fp2_add(&t, t, t);         // 1266096 × input
    
    fp2_add(output, t, t);     // 2532192 × input
}

References fp2_add.

Referenced by isogeny_walks_2(), and isogeny_walks_2_slow().

Here is the caller graph for this function:

fp2_mul_by_2976()

void fp2_mul_by_2976	(	fp2_t *	output,
		fp2_t	input )

Definition at line 32 of file isogeny_walks_2.c.

                                                 {
    fp2_mul_by_1488(output, input);    // 1488 × input
    fp2_add(output, *output, *output); // 2976 × input
}

References fp2_add, and fp2_mul_by_1488().

Referenced by isogeny_walks_2(), and isogeny_walks_2_slow().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_mul_by_324000()

void fp2_mul_by_324000	(	fp2_t *	output,
		fp2_t	input )

Definition at line 67 of file isogeny_walks_2.c.

                                                   {
    fp2_mul_by_162000(output, input);  // 162000 × input
    fp2_add(output, *output, *output); // 324000 × input
}

References fp2_add, and fp2_mul_by_162000().

Referenced by isogeny_walks_2(), and isogeny_walks_2_slow().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_mul_by_645205500()

void fp2_mul_by_645205500	(	fp2_t *	output,
		fp2_t	input )

Definition at line 108 of file isogeny_walks_2.c.

                                                      {
 
    fp2_t r, s, t, u, v;
    fp2_add(&r, input, input); //          2 × input
    fp2_add(&r, r, r);         //          4 × input
    fp2_add(&s, r, input);     //          5 × input
    fp2_add(&t, s, s);         //         10 × input
 
    fp2_add(&t, t, t);         //         20 × input
    fp2_add(&r, t, t);         //         40 × input
    fp2_add(&t, r, r);         //         80 × input
    fp2_add(&u, t, s);         //         85 × input
 
    fp2_add(&v, t, u);         //        165 × input
    fp2_add(&v, v, r);         //        205 × input
    fp2_add(&t, v, v);         //        410 × input
    fp2_add(&t, t, t);         //        820 × input
 
    fp2_add(&t, t, t);         //       1640 × input
    fp2_add(&t, t, t);         //       3280 × input
    fp2_add(&t, t, t);         //       6560 × input
    fp2_add(&t, t, t);         //      13120 × input
 
    fp2_add(&t, t, t);         //      26240 × input
    fp2_add(&t, t, t);         //      52480 × input
    fp2_add(&t, t, t);         //     104960 × input
    fp2_add(&t, t, t);         //     209920 × input
 
    fp2_add(&t, t, t);         //     419840 × input
    fp2_add(&t, t, v);         //     420045 × input
    fp2_add(&t, t, t);         //     840090 × input
    fp2_add(&t, t, t);         //    1680180 × input
 
    fp2_add(&t, t, t);         //    3360360 × input
    fp2_add(&t, t, u);         //    3360445 × input
    fp2_add(&t, t, t);         //    6720890 × input
    fp2_add(&t, t, t);         //   13441780 × input
 
    fp2_add(&t, t, t);         //   26883560 × input
    fp2_add(&t, t, t);         //   53767120 × input
    fp2_add(&t, t, s);         //   53767125 × input
    fp2_add(&u, t, t);         //  107534250 × input
    
    fp2_add(&t, t, u);         //  161301375 × input
    fp2_add(&t, t, t);         //  322602750 × input
    fp2_add(output, t, t);     //  645205500 × input
}

References fp2_add.

Referenced by isogeny_walks_2(), and isogeny_walks_2_slow().

Here is the caller graph for this function:

fp2_mul_by_8748000000()

void fp2_mul_by_8748000000	(	fp2_t *	output,
		fp2_t	input )

Definition at line 156 of file isogeny_walks_2.c.

                                                       {
    fp2_t r, s, t, u, v;
    fp2_add(&r, input, input); //          2 × input
    fp2_add(&r, r, r);         //          4 × input
    fp2_add(&r, r, r);         //          8 × input
    fp2_add(&r, r, r);         //         16 × input
 
    fp2_add(&r, r, r);         //         32 × input
    fp2_add(&r, r, r);         //         64 × input
    fp2_add(&r, r, r);         //        128 × input
    fp2_add(&s, r, input);     //        129 × input
 
    fp2_add(&r, s, r);         //        257 × input
    fp2_add(&r, r, r);         //        514 × input
    fp2_add(&r, r, r);         //       1028 × input
    fp2_add(&t, r, r);         //       2056 × input
 
    fp2_add(&t, t, t);         //       4112 × input
    fp2_add(&t, t, t);         //       8224 × input
    fp2_add(&u, t, s);         //       8353 × input
    fp2_add(&v, t, r);         //       9252 × input
 
    fp2_add(&t, u, v);         //      17605 × input
    fp2_add(&t, t, t);         //      35210 × input
    fp2_add(&t, t, v);         //      44462 × input
    fp2_add(&t, t, t);         //      88924 × input
 
    fp2_add(&t, t, t);         //     177848 × input
    fp2_add(&t, t, t);         //     355696 × input
    fp2_add(&t, t, t);         //     711392 × input
    fp2_add(&t, t, t);         //    1422784 × input
 
    fp2_add(&t, t, t);         //    2845568 × input
    fp2_add(&t, t, t);         //    5691136 × input
    fp2_add(&t, t, t);         //   11382272 × input
    fp2_add(&t, t, u);         //   11390625 × input
 
    fp2_add(&u, t, t);         //   22781250 × input
    fp2_add(&t, t, u);         //   34171875 × input
    fp2_add(&t, t, t);         //   68343750 × input
    fp2_add(&t, t, t);         //  136687500 × input
 
    fp2_add(&t, t, t);         //  273375000 × input
    fp2_add(&t, t, t);         //  546750000 × input
    fp2_add(&t, t, t);         // 1093500000 × input
    fp2_add(&t, t, t);         // 2187000000 × input
    
    fp2_add(&t, t, t);         // 4374000000 × input
    fp2_add(output, t, t);     // 8748000000 × input
}

References fp2_add.

Referenced by isogeny_walks_2(), and isogeny_walks_2_slow().

Here is the caller graph for this function:

isogeny_walks_2()

void isogeny_walks_2	(	fp2_t *	output,
		fp2_t	input_prev,
		fp2_t	input,
		const uint8_t *	input_path,
		size_t	input_length )

Definition at line 208 of file isogeny_walks_2.c.

                                                                                                                   {
    size_t i, j;
    fp2_t t4, t3, t2, t1, t0, jk_next, jk, jk_prev, Dk, Dk_sqrt[2];
    fp2_t constant_162000, constant_2532192, constant_645205500, constant_8748000000;
    fp2_t jk_times_2976, jk_prev_times_2976, jk_prev_times_324000, jk_squared, jk_prev_squared;
 
    fp2_set_to_one(&constant_162000);
    fp2_set_to_one(&constant_2532192);
    fp2_set_to_one(&constant_645205500);
    fp2_set_to_one(&constant_8748000000);
 
    fp2_mul_by_162000(&constant_162000, constant_162000);
    fp2_mul_by_2532192(&constant_2532192, constant_2532192);
    fp2_mul_by_645205500(&constant_645205500, constant_645205500);
    fp2_mul_by_8748000000(&constant_8748000000, constant_8748000000);
 
    fp2_copy(&jk, input);
    fp2_copy(&jk_prev, input_prev);
 
    for (i = 0; i < input_length; i++) {
        uint8_t mask = 0x1;
        for (j = 0; j < 8; j++) {
            // jk⁴
            fp2_sqr(&jk_squared, jk);
            fp2_sqr(&t4, jk_squared);
            // - 2976 × (jk³) [= - (2976  ×  jk)  ×  (jk²) ]
            fp2_mul_by_2976(&jk_times_2976, jk);
            fp2_mul(&t3, jk_times_2976, jk_squared);
            // + 2 × (jk²) × jk_prev + 2532192 × (jk²) [= +  [2 × jk_prev + 2532192]  ×  (jk²)]
            fp2_add(&t2, jk_prev, jk_prev);
            fp2_add(&t2, t2, constant_2532192);
            fp2_mul(&t2, t2, jk_squared);
            // - 2976 × jk × jk_prev - 645205500 × jk      [= -(2976 × jk_prev + 645205500)  ×  jk ]
            fp2_mul_by_2976(&jk_prev_times_2976, jk_prev);
            fp2_add(&t1, jk_prev_times_2976, constant_645205500);
            fp2_mul(&t1, t1, jk);
            // - 3 × (jk_prev²) + 324000 × jk_prev [= (-3  ×  jk_prev + 324000)  ×  jk_prev]
            fp2_mul_by_324000(&jk_prev_times_324000, jk_prev);
            fp2_sqr(&jk_prev_squared, jk_prev);
            fp2_add(&t0, jk_prev_squared, jk_prev_squared);
            fp2_add(&t0, t0, jk_prev_squared);
            fp2_sub(&t0, jk_prev_times_324000, t0);
            //  - 8748000000
 
            // Dk = jk⁴ - 2976 × (jk³) + 2 × (jk²) × jk_prev + 2532192 × (jk²) - 2976 × jk × jk_prev - 645205500 × jk - 3 × (jk_prev²) + 324000 × jk_prev - 8748000000
            fp2_sub(&Dk, t4, t3);
            fp2_add(&Dk, Dk, t2);
            fp2_sub(&Dk, Dk, t1);
            fp2_add(&Dk, Dk, t0);
            fp2_sub(&Dk, Dk, constant_8748000000);
 
            fp2_sqrt_fast(&Dk_sqrt[0], Dk);   // 1st square-root (deterministic)
            fp2_neg(&Dk_sqrt[1], Dk_sqrt[0]); // 2nd square-root (negative)
            fp2_linear_pass_in(&Dk, Dk_sqrt , 2, (input_path[i] & mask) >> j);
 
            // jk_next = (jk² - 1488 × jk - jk_prev + 162000 + Dk_sqrt[path[k]]) / 2
            fp2_half(&t0, jk_times_2976); // 2976 = 2 × 1488
            fp2_sub(&t1, jk_squared, t0);
            fp2_sub(&t1, t1, jk_prev);
            fp2_add(&t1, t1, constant_162000);
            fp2_add(&t1, t1, Dk);
            fp2_half(&jk_next, t1);
 
            fp2_copy(&jk_prev, jk);
            fp2_copy(&jk, jk_next);
            
            mask <<= 1;
        }
    }
    fp2_copy(output, jk);
}

References fp2_add, fp2_copy, fp2_half(), fp2_linear_pass_in(), fp2_mul, fp2_mul_by_162000(), fp2_mul_by_2532192(), fp2_mul_by_2976(), fp2_mul_by_324000(), fp2_mul_by_645205500(), fp2_mul_by_8748000000(), fp2_neg, fp2_set_to_one(), fp2_sqr, fp2_sqrt_fast(), fp2_sub, i, and j.

Referenced by cgl_hash_digest_2().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_2_slow()

void isogeny_walks_2_slow	(	fp2_t *	j0,
		fp2_t *	j1,
		fp2_t	input_prev,
		fp2_t	input,
		const uint8_t *	input_path,
		size_t	input_length )

Definition at line 333 of file isogeny_walks_2.c.

                                                                                                                               {
    size_t i, j;
    fp2_t t4, t3, t2, t1, t0, jk_next, jk, jk_prev, Dk, Dk_sqrt[2];
    fp2_t constant_162000, constant_2532192, constant_645205500, constant_8748000000;
    fp2_t jk_times_2976, jk_prev_times_2976, jk_prev_times_324000, jk_squared, jk_prev_squared;
 
    fp2_set_to_one(&constant_162000);
    fp2_set_to_one(&constant_2532192);
    fp2_set_to_one(&constant_645205500);
    fp2_set_to_one(&constant_8748000000);
 
    fp2_mul_by_162000(&constant_162000, constant_162000);
    fp2_mul_by_2532192(&constant_2532192, constant_2532192);
    fp2_mul_by_645205500(&constant_645205500, constant_645205500);
    fp2_mul_by_8748000000(&constant_8748000000, constant_8748000000);
 
    fp2_copy(&jk, input);
    fp2_copy(&jk_prev, input_prev);
 
    for (i = 0; i < input_length; i++) {
        uint8_t mask = 0x1;
        for (j = 0; j < 8; j++) {
            // jk⁴
            fp2_sqr(&jk_squared, jk);
            fp2_sqr(&t4, jk_squared);
            // - 2976 × (jk³) [= - (2976  ×  jk)  ×  (jk²) ]
            fp2_mul_by_2976(&jk_times_2976, jk);
            fp2_mul(&t3, jk_times_2976, jk_squared);
            // + 2 × (jk²) × jk_prev + 2532192 × (jk²) [= +  [2 × jk_prev + 2532192]  ×  (jk²)]
            fp2_add(&t2, jk_prev, jk_prev);
            fp2_add(&t2, t2, constant_2532192);
            fp2_mul(&t2, t2, jk_squared);
            // - 2976 × jk × jk_prev - 645205500 × jk      [= -(2976 × jk_prev + 645205500)  ×  jk ]
            fp2_mul_by_2976(&jk_prev_times_2976, jk_prev);
            fp2_add(&t1, jk_prev_times_2976, constant_645205500);
            fp2_mul(&t1, t1, jk);
            // - 3 × (jk_prev²) + 324000 × jk_prev [= (-3  ×  jk_prev + 324000)  ×  jk_prev]
            fp2_mul_by_324000(&jk_prev_times_324000, jk_prev);
            fp2_sqr(&jk_prev_squared, jk_prev);
            fp2_add(&t0, jk_prev_squared, jk_prev_squared);
            fp2_add(&t0, t0, jk_prev_squared);
            fp2_sub(&t0, jk_prev_times_324000, t0);
            //  - 8748000000
 
            // Dk = jk⁴ - 2976 × (jk³) + 2 × (jk²) × jk_prev + 2532192 × (jk²) - 2976 × jk × jk_prev - 645205500 × jk - 3 × (jk_prev²) + 324000 × jk_prev - 8748000000
            fp2_sub(&Dk, t4, t3);
            fp2_add(&Dk, Dk, t2);
            fp2_sub(&Dk, Dk, t1);
            fp2_add(&Dk, Dk, t0);
            fp2_sub(&Dk, Dk, constant_8748000000);
 
            fp2_sqrt_slow(&Dk_sqrt[0], Dk);   // 1st square-root (deterministic)
            fp2_neg(&Dk_sqrt[1], Dk_sqrt[0]); // 2nd square-root (negative)
            fp2_linear_pass_in(&Dk, Dk_sqrt , 2, (input_path[i] & mask) >> j);
 
            // jk_next = (jk² - 1488 × jk - jk_prev + 162000 + Dk_sqrt[path[k]]) / 2
            fp2_half(&t0, jk_times_2976); // 2976 = 2 × 1488
            fp2_sub(&t1, jk_squared, t0);
            fp2_sub(&t1, t1, jk_prev);
            fp2_add(&t1, t1, constant_162000);
            fp2_add(&t1, t1, Dk);
            fp2_half(&jk_next, t1);
 
            fp2_copy(&jk_prev, jk);
            fp2_copy(&jk, jk_next);
            
            mask <<= 1;
        }
    }
    fp2_copy(j0, jk_prev);
    fp2_copy(j1, jk);
}

References fp2_add, fp2_copy, fp2_half(), fp2_linear_pass_in(), fp2_mul, fp2_mul_by_162000(), fp2_mul_by_2532192(), fp2_mul_by_2976(), fp2_mul_by_324000(), fp2_mul_by_645205500(), fp2_mul_by_8748000000(), fp2_neg, fp2_set_to_one(), fp2_sqr, fp2_sqrt_slow(), fp2_sub, i, and j.

Here is the call graph for this function:

isogeny_walks_3()

void isogeny_walks_3	(	fp2_t *	output_a1,
		fp2_t *	output_a3,
		fp2_t	input_a1,
		fp2_t	input_a3,
		const uint8_t *	input_path,
		size_t	input_length )

Definition at line 10 of file isogeny_walks_3.c.

                                                                                                                                         {
    // This function assumes the input and output determines elliptic
    // curves of form y² + a₁xy + a₃y = x³ − 5a₁a₃x − (a₁³)a₃ − 7(a₃)²
    size_t i, j;
    fp2_t a, a1, a3, cube_roots_of_unity[3], r, s, t;
 
    fp2_set_to_one(&cube_roots_of_unity[0]);
    fp2_copy(&cube_roots_of_unity[1], *((fp2_t *)&CUBE_ROOT_OF_UNITY));
    fp2_sqr(&cube_roots_of_unity[2], cube_roots_of_unity[1]);
 
    fp2_copy(&a1, input_a1);
    fp2_copy(&a3, input_a3);
 
    uint32_t trit_string[input_length];
    to_trit_string(trit_string, input_path, input_length);
 
    for (i = 0; i < input_length; i++) {
        uint32_t mask = 0x0000000F;
        for (j = 0; j < 5; j++) {
            fp2_neg(&a, a3);
            fp2_curt(&a, a);
            fp2_linear_pass_in(&t, cube_roots_of_unity, 3, (trit_string[i] & mask) >> (4*j));
            fp2_mul(&a, a, t);
 
            // radical 3-isogeny
            fp2_add(&t, a, a);   // 2α
            fp2_add(&t, t, a);   // 3α
            fp2_add(&t, t, t);   // 6α
 
            fp2_add(&r, a1, a1); // 2a₁
            fp2_add(&r, r, a1);  // 3a₁
            fp2_sqr(&s, a1);     // a₁²
 
            fp2_sub(&a1, a1, t); // a₁ <- a₁ - 6α
            
            fp2_sqr(&t, a);      // α²
            fp2_mul(&r, r, t);   // 3a₁ · α²
            fp2_mul(&s, s, a);   // a₁² · α
            fp2_add(&t, a3, a3); // 2a₃
            fp2_add(&t, t, a3);  // 3a₃
            fp2_add(&a, t, t);   // 6a₃
            fp2_add(&t, a, t);   // 9a₃
            fp2_sub(&a3, r, s);  //  a₃ <- 3a₁ · α² - a₁² · α
            fp2_add(&a3, a3, t); //  a₃ <- 3a₁ · α² - a₁² · α + 9a₃
 
            mask <<= 4;
        }
    }
    fp2_copy(output_a1, a1);
    fp2_copy(output_a3, a3);
}

References a, a1, a3, fp2_add, fp2_copy, fp2_curt(), fp2_linear_pass_in(), fp2_mul, fp2_neg, fp2_set_to_one(), fp2_sqr, fp2_sub, i, and j.

Referenced by cgl_hash_digest_3().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_3_fp()

void isogeny_walks_3_fp	(	fp_t	output_A,
		const fp_t	input_A,
		int	input_length )

Definition at line 217 of file isogeny_walks_3_fp.c.

                                                                            {
    fp_t aux[2], num_den[3];
 
    fp_copy(aux[0], input_A);
    fp_set_to_one(aux[1]);
 
    isogeny_walks_get_points_3_fp(num_den, aux);
 
    uint64_t sign = (input_length >> TOP_BIT) & 1;
    fp_cset(aux[0], num_den[0], -sign);
    fp_cset(aux[0], num_den[1], sign-1);
    fp_copy(aux[1], num_den[2]);
 
    int input_length_abs = absolute_value(input_length);
    for(int i = 0; i < input_length_abs; i++){
        fp_t t[2] = {0};
        uint64_t d = constant_time_is_lessthan_u64(i, input_length_abs);
        isogeny_walks_to_montgomery_model_3_fp(t, aux);
        fp_cset(aux[0], t[0], -d);
        fp_cset(aux[1], t[1], -d);
    }
    isogeny_to_montgomery(output_A, aux);
}

References constant_time_is_lessthan_u64(), fp_copy, fp_cset(), fp_set_to_one(), i, isogeny_to_montgomery(), isogeny_walks_get_points_3_fp(), isogeny_walks_to_montgomery_model_3_fp(), and TOP_BIT.

Referenced by action().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_from_montgomery_model_2()

void isogeny_walks_from_montgomery_model_2	(	fp2_t *	output_j,
		fp2_t	input_A )

Definition at line 280 of file isogeny_walks_2.c.

                                                                           {
    // Computes the j-invariant of a Montgomery curve E : y² = x³ + Ax² + x
    fp2_t r, s, t;
 
    fp2_set_to_one(&t);
 
    fp2_add(&r, t, t);    // 2
    fp2_add(&r, r, t);    // 3
    fp2_sqr(&s, input_A); // A²
 
    fp2_sub(&s, s, r);    // A² - 3
    fp2_sub(&r, s, t);    // A² - 4
    fp2_add(&s, s, s);    // 2(A² - 3)
    fp2_add(&s, s, s);    // 4(A² - 3)
 
    fp2_sqr(&t, s);       // 16(A² - 3)²
    fp2_mul(&s, s, t);    // 64(A² - 3)³
    fp2_add(&s, s, s);    // 128(A² - 3)³
    fp2_add(&s, s, s);    // 256(A² - 3)³
    fp2_inv(&t, r);       // 1 / (A² - 4)
    fp2_mul(output_j, s, t);
}

References fp2_add, fp2_inv, fp2_mul, fp2_set_to_one(), fp2_sqr, and fp2_sub.

Referenced by cgl_hash_init_2().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_from_montgomery_model_3()

void isogeny_walks_from_montgomery_model_3	(	fp2_t *	output_a1,
		fp2_t *	output_a3,
		fp2_t	input_A,
		fp2_t	input_xP )

Definition at line 62 of file isogeny_walks_3.c.

                                                                                                              {
    // inputs: x-coordinate of an order-3 point P on E: y² = x³ + Ax² + x, and A
    // output: isomorphic curve of form F: y² + a₁xy + a₃y = x³
    // Cost: 2M + 2S + 7A
    fp2_t r, s, xP_squared, A_times_xP;
    
    fp2_sqr(&xP_squared, input_xP);
    fp2_add(&r, xP_squared, xP_squared);
    fp2_add(&r, xP_squared, r);
    
    fp2_mul(&A_times_xP, input_A, input_xP); 
    fp2_add(&s, A_times_xP, A_times_xP);
    fp2_add(&r, r, s);
 
    fp2_set_to_one(&s);
    fp2_add(output_a1, r, s); // (3xₚ² + 2Axₚ + 1)
 
    fp2_add(output_a3, xP_squared, A_times_xP);
    fp2_add(output_a3, *output_a3, s);
    fp2_mul(output_a3, *output_a3, input_xP);
    fp2_sqr(output_a3, *output_a3);
    fp2_add(output_a3, *output_a3, *output_a3); // 2 yₚ⁴ = 2 (xₚ³ + Axₚ² + xₚ)²
}

References fp2_add, fp2_mul, fp2_set_to_one(), and fp2_sqr.

Referenced by cgl_hash_init_3().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_get_points_3()

void isogeny_walks_get_points_3	(	fp2_t *	output,
		fp2_t	input_A )

Definition at line 124 of file isogeny_walks_3.c.

                                                              {
    fp2_t A_times_one_third, A_squared, r, s, t, u, v, y, s0, i0, s1, s2;
    fp_t THREE, EIGHT;
    
    fp_set_to_one(THREE);        // 1
 
    fp_add(EIGHT, THREE, THREE); // 2
    fp_add(THREE, THREE, EIGHT); // 3
    fp_add(EIGHT, EIGHT, EIGHT); // 4
    fp_add(EIGHT, EIGHT, EIGHT); // 8
    
    fp_mul(A_times_one_third.re, input_A.re, ONE_THIRD);
    fp_mul(A_times_one_third.im, input_A.im, ONE_THIRD);
    fp2_sqr(&A_squared, input_A);
    
    // t takes the value of ⅑(3 - A²)
    fp_sub(t.re, THREE, A_squared.re);
    fp_neg(t.im, A_squared.im);
    fp_mul(t.re, t.re, ONE_NINTH);
    fp_mul(t.im, t.im, ONE_NINTH);
    
    // r takes the value of (⁸⁄₂₇)A³
    fp2_mul(&r, A_squared, input_A);
    fp_mul(r.re, r.re, ONE_BY_27);
    fp_mul(r.im, r.im, ONE_BY_27);
    fp2_add(&r, r, r); //  2r
    fp2_add(&r, r, r); //  4r
    fp2_add(&r, r, r); //  8r
    fp2_add(&r, r, r); // 16r
 
    // s takes the calue of (⁸⁄₃)A
    fp2_copy(&s, A_times_one_third);
    fp2_add(&s, s, s); // 2s
    fp2_add(&s, s, s); // 4s
    fp2_add(&s, s, s); // 8s
    fp2_sub(&u, r, s); // r - s
 
    // v takes the value of -2A² + 8
    fp2_add(&v, A_squared, A_squared);
    fp_sub(v.re, EIGHT, v.re);
    fp_neg(v.im, v.im);
    fp2_curt(&y, v); // cube-root of v
 
    // y takes the value of t + (¹⁄₃)∛v
    fp_mul(y.re, y.re, ONE_THIRD);
    fp_mul(y.im, y.im, ONE_THIRD);
    fp2_add(&y, t, y);
    fp2_add(&r, y, y); // 2y
 
    fp2_add(&s, t, t); // 2t
    fp2_add(&s, t, s); // 3t
    fp2_add(&s, s, s); // 6t
    fp2_sub(&t, r, s); // r - s
 
    // s₀ takes the value of √(r - s)
    fp2_sqrt_slow(&s0, t);
    fp2_inv(&i0, s0); // 1 / s₀
 
    fp2_add(&v, r, s);  //   r + s
    fp2_neg(&v, v);     // -(r + s)
    fp2_mul(&t, u, i0); // u / s₀
 
    // s₁ takes the value of √[v + (u / s₀)]
    fp2_add(&s, v, t);  // v + (u / s₀)
    fp2_sqrt_slow(&s1, s);
    // s₂ takes the value of √[v - (u / s₀)]
    fp2_sub(&s, v, t);  // v - (u / s₀)
    fp2_sqrt_slow(&s2, s);
 
    fp2_sub(&r, s1, s0); // -s₀ + s₁
    fp2_add(&s, s1, s0); //  s₀ + s₁
    fp2_add(&t, s0, s2); //  s₀ + s₂
    fp2_sub(&u, s0, s2); //  s₀ - s₂
 
    fp2_neg(&s, s);      // -(s₀ + s₁)
 
    fp2_half(&r, r); // (¹⁄₂)(-s₀ + s₁)
    fp2_half(&s, s); // (¹⁄₂)(-s₀ - s₁)
    fp2_half(&t, t); // (¹⁄₂)( s₀ + s₂)
    fp2_half(&u, u); // (¹⁄₂)( s₀ - s₂)
 
    fp2_sub(&output[3], u, A_times_one_third); // r - (¹⁄₃)A
    fp2_sub(&output[2], t, A_times_one_third); // s - (¹⁄₃)A
    fp2_sub(&output[1], s, A_times_one_third); // t - (¹⁄₃)A
    fp2_sub(&output[0], r, A_times_one_third); // u - (¹⁄₃)A
}

References fp2_add, fp2_copy, fp2_curt(), fp2_half(), fp2_inv, fp2_mul, fp2_neg, fp2_sqr, fp2_sqrt_slow(), fp2_sub, fp_add, fp_mul, fp_neg(), fp_set_to_one(), fp_sub, fp2_t::im, and fp2_t::re.

Referenced by cgl_hash_init_3().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_get_points_3_fp()

void isogeny_walks_get_points_3_fp	(	fp_t *	output,
		const fp_t *	input_A )

Definition at line 18 of file isogeny_walks_3_fp.c.

                                                                     {
    fp_t A_times_one_third, A_squared, C_squared;
    fp_t t, r, s, u, aux, tmp, y;
    fp_t s0, s1, s2, s0_squared, v;
 
    // input_A[0] is A
    // input_A[1] is C
    // A_times_one_third = A * one_third                    #               M𝒸
    fp_mul(A_times_one_third, ONE_THIRD, input_A[0]);
    // A_squared = A**2                                     #               S
    fp_sqr(A_squared, input_A[0]);
    // C_squared = C**2                                     #               S
    fp_sqr(C_squared, input_A[1]);
 
    // t = (3 * C_squared - A_squared) * one_ninth          #               M𝒸 + 3A
    fp_add(t, C_squared, C_squared);
    fp_add(t, t, C_squared);
    fp_sub(t, t, A_squared);
    fp_mul(t, ONE_NINTH, t);
 
    // r = 16 * (A_squared * A) * one_by_27                 #               M + M𝒸 + 4A
    fp_mul(r, A_squared, input_A[0]);
    fp_mul(r, ONE_BY_27, r);
    fp_add(r, r, r);
    fp_add(r, r, r);
    fp_add(r, r, r);
    fp_add(r, r, r);
 
    // s = 8 * A_times_one_third                            #                 3A
    fp_add(s, A_times_one_third, A_times_one_third);
    fp_add(s, s, s);
    fp_add(s, s, s);
 
    // u = r - s * C_squared                                #                M  +  A
    fp_mul(u, s, C_squared);
    fp_sub(u, r, u);
 
    // aux = 2*C_squared**2                                         #               S + A
    fp_sqr(aux, C_squared);
    fp_add(aux, aux, aux);
    // y = 4 * C_squared                                            #               2A
    fp_add(y, C_squared, C_squared);
    fp_add(y, y, y);
    // y = y - A_squared                                            #               A
    fp_sub(y, y, A_squared);
    // y = aux * y                                                  #               M
    fp_mul(y, aux, y);
 
    // y = t + one_third * setup['curt'](y)                         #            M𝒸 + A + E   (TOTAL = S + M + Mc + 5A + E)
    fp_curt(y, y);
    fp_mul(y, y, ONE_THIRD);
    fp_add(y, y, t);
 
    // r = 2 * y                                                    #                  A
    fp_add(r, y, y);
    // s = 6 * t                                                    #                 3A
    fp_add(s, t, t);
    fp_add(t, s, s);
    fp_add(s, s, t);
 
    // s0 = setup['sqrt'](r - s)                                    #                  A + E
    fp_sub(s0, r, s);
    fp_sqrt(s0, s0);
 
    // s0_squared = s0**2                                           #                 S
    fp_sqr(s0_squared, s0);
    // v = -(r + s)                                                 #                 2A
    fp_add(v, r, s);
    fp_neg(v, v);
 
    fp_mul(tmp, v, s0_squared); //               #                  M
    fp_mul(u, u, s0);           //               #                  M
    // s1 = setup['sqrt'](tmp + u)                                  #                A + E
    fp_add(t, tmp, u);
    fp_sqrt(s1, t);
    // s2 = setup['sqrt'](tmp - u)                                  #                A + E
    fp_sub(s, tmp, u);
    fp_sqrt(s2, s);
 
    // Test to know if s1 and s2 are square roots                   #                 2S
    fp_sqr(tmp, s1);
    fp_sqr(aux, s2);
    uint8_t test_s1 = fp_is_equal(tmp, t);
    uint8_t test_s2 = fp_is_equal(aux, s);
 
    // Compute z                                                    #                 4Mc + 5A
    fp_sub(t, s1, s0_squared);
    fp_mul(t, t, ONE_HALF);
    fp_neg(s1, s1);
    fp_sub(r, s1, s0_squared);
    fp_mul(r, r, ONE_HALF);
 
    fp_add(s, s2, s0_squared);
    fp_mul(s, s, ONE_HALF);
    fp_sub(u, s0_squared, s2);
    fp_mul(u, u, ONE_HALF);
 
    // Select z in constant time
    fp_cset(output[0], t, -test_s1);
    fp_cset(output[1], r, -test_s1);
    fp_cset(output[0], s, -test_s2);
    fp_cset(output[1], u, -test_s2);
 
    // Compute num and den                                          #                  2M + 2A
    fp_mul(output[2], s0, input_A[1]);
    fp_mul(aux, s0, A_times_one_third);
    fp_sub(output[0], output[0], aux);
    fp_sub(output[1], output[1], aux);
 
    //                                                              #                 2S + 7M + 2A
    fp_sqr(r, output[0]); // x**2
    fp_sqr(s, output[2]); // den**2
    fp_mul(v, input_A[1], output[0]); // C*x
    fp_mul(t, output[2], input_A[0]); // A*den
    fp_mul(u, v, s); // C*x*den**2
    fp_mul(aux, s, output[2]); // den**3
    fp_mul(aux, aux, input_A[1]); // C*den**3
    fp_add(t, t, v); // C*x + A*den
    fp_mul(t, t, r); // x**2 * (C*x + A*den)
    fp_add(t, t, u); // (x**2 * (C*x + A*den)) + C*x * den**2
    fp_mul(t, t, aux);
 
    uint64_t test_sqr = (uint64_t)!fp_is_square(t);//          #                     E
    fp_cswap(output[0], output[1], -test_sqr);
}

References fp_add, fp_cset(), fp_cswap, fp_curt(), fp_is_equal(), fp_is_square(), fp_mul, fp_neg(), fp_sqr, fp_sqrt(), and fp_sub.

Referenced by isogeny_walks_3_fp(), and isogeny_walks_3_fp().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_get_previous_step_2()

void isogeny_walks_get_previous_step_2	(	fp2_t *	output_j,
		fp2_t	input_A )

Definition at line 303 of file isogeny_walks_2.c.

                                                                       {
    // Computes the j-invariant of a Montgomery curve E : y² = x³ + (A + 6)x² + (4[2 + A])x
    fp2_t r, s, t;
 
    fp2_set_to_one(&t);
 
    fp2_add(&r, t, t);    //  2
    fp2_add(&t, r, r);    //  4
    fp2_add(&r, t, t);    //  8
    fp2_add(&r, t, r);    // 12
 
    fp2_sqr(&s, input_A); // A²
    fp2_add(&s, s, r);    // A² + 12
    fp2_sub(&r, s, t);    // A² - 4
    fp2_add(&s, s, s);    // 2(A² + 12)
 
    fp2_sqr(&r, r);       // (A² - 4)²
    fp2_sqr(&t, s);       //  4(A² + 12)²
    fp2_mul(&s, s, t);    //  8(A² + 12)³
    fp2_add(&s, s, s);    // 16(A² + 12)³
 
    fp2_inv(&t, r);       // 1 / (A² - 4)²
    fp2_mul(output_j, s, t);
}

References fp2_add, fp2_inv, fp2_mul, fp2_set_to_one(), fp2_sqr, and fp2_sub.

Referenced by cgl_hash_init_2().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_sample_bit_string()

void isogeny_walks_sample_bit_string

(

uint8_t *

output

)

Definition at line 329 of file isogeny_walks_2.c.

                                                      {
    randombytes(output, BIT_LENGTH_PATH / 8);
}

References BIT_LENGTH_PATH, and randombytes().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_sample_trit_string()

void isogeny_walks_sample_trit_string

(

uint8_t *

output

)

Definition at line 212 of file isogeny_walks_3.c.

                                                       {
    uint8_t bound = 0xF3;
    for(int i = 0; i < (TRITLENGTH_PATH / 5); i++) {
        output[i] = 0x00;
        randombytes(&output[i], 1);
        while (issmaller((int32_t)bound, (int32_t)(output[i]))) {
            randombytes(&output[i], 1);
        }
    }
}

References i, randombytes(), and TRITLENGTH_PATH.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

isogeny_walks_switch_from_model_3()

void isogeny_walks_switch_from_model_3	(	fp2_t *	output_j,
		fp2_t	input_a1,
		fp2_t	input_a3 )

Definition at line 87 of file isogeny_walks_3.c.

                                                                                        {
    // Computes the j-invariant of an elliptic curve E : y² + a₁xy + a₃y = x³ − 5a₁a₃x − (a₁³)a₃ − 7(a₃)²
    fp2_t aux, tmp, num, den, a1_cube, a3_cube;
 
    fp2_sqr(&a1_cube, input_a1);
    fp2_sqr(&a3_cube, input_a3);
    fp2_mul(&a1_cube, a1_cube, input_a1);
    fp2_mul(&a3_cube, a3_cube, input_a3);
 
    fp2_add(&tmp, input_a3, input_a3); //         2 × a₃
    fp2_add(&tmp, tmp, input_a3);      //         3 × a₃
    fp2_add(&aux, tmp, tmp);           //         6 × a₃
    fp2_add(&aux, aux, aux);           //        12 × a₃
 
    fp2_add(&aux, aux, aux);           //        24 × a₃
    fp2_add(&aux, aux, tmp);           //        27 × a₃
    fp2_add(&tmp, aux, aux);           //        54 × a₃
    fp2_add(&tmp, tmp, tmp);           //       108 × a₃
    
    fp2_add(&tmp, tmp, tmp);           //       216 × a₃
    fp2_add(&num, a1_cube, tmp);       // a₁³ + 216 × a₃
    fp2_sub(&den, a1_cube, aux);       // a₁³ -  27 × a₃
 
    fp2_sqr(&tmp, num);
    fp2_sqr(&aux, den);
    
    fp2_mul(&num, num, tmp);          // (a₁³ + 216 × a₃)³
    fp2_mul(&den, den, aux);          // (a₁³ -  27 × a₃)³
    fp2_mul(&num, a1_cube, num);      // (a₁³ + 216 × a₃)³ × a₁³
    fp2_mul(&den, input_a3, den);     // (a₁³ -  27 × a₃)³ × a₃
 
    fp2_inv(&den, den);
    fp2_mul(output_j, num, den);
 
}

References fp2_add, fp2_inv, fp2_mul, fp2_sqr, fp2_sub, and num.

Referenced by cgl_hash_digest_3().

Here is the caller graph for this function:

isogeny_walks_to_montgomery_model_3_fp()

void isogeny_walks_to_montgomery_model_3_fp	(	fp_t *	output_A,
		const fp_t *	input_t )

Definition at line 144 of file isogeny_walks_3_fp.c.

                                                                                {
    fp_t r_squared, s_squared, r_cubed;
    fp_t aux, alpha_cubed, alpha, rd;
 
    // input_t[0] is r
    // input_t[1] is s
    // r_squared = r**2
    fp_sqr(r_squared, input_t[0]);
    // s_squared = s**2
    fp_sqr(s_squared, input_t[1]);
    // r_cubed = r_squared * r
    fp_mul(r_cubed, r_squared, input_t[0]);
    // s_cubed = s_squared * s
    fp_mul(output_A[1], s_squared, input_t[1]);
    // aux = r * s_squared
    fp_mul(aux, s_squared, input_t[0]);
 
    // alpha_cubed = r * (r_squared - s_squared)
    fp_sub(alpha_cubed, r_squared, s_squared);
    fp_mul(alpha_cubed, alpha_cubed, input_t[0]);
    // alpha = setup['curt'](alpha_cubed)
    fp_curt(alpha, alpha_cubed);
 
    // Goal rd = 3 * (r * alpha**2 + r_squared * alpha + r_cubed) - s_sqr * alpha - 2 * aux
    //rd = (r * alpha**2 + r_squared * alpha + r_cubed)
    fp_mul(rd, input_t[0], alpha);
    fp_add(rd, rd, r_squared);
    fp_mul(rd, rd, alpha);
    fp_add(rd, rd, r_cubed);
    // rd = 3 * (r * alpha**2 + r_squared * alpha + r_cubed)
    fp_add(r_squared, rd, rd);
    fp_add(rd, rd, r_squared);
    // rd = 3 * (r * alpha**2 + r_squared * alpha + r_cubed) - s_sqr * alpha - 2 * aux
    fp_sub(rd, rd, aux);
    fp_sub(rd, rd, aux);
    fp_mul(r_squared, s_squared, alpha);
    fp_sub(output_A[0], rd, r_squared);
}

References fp_add, fp_curt(), fp_mul, fp_sqr, and fp_sub.

Referenced by isogeny_walks_3_fp(), and isogeny_walks_3_fp().

Here is the call graph for this function:

Here is the caller graph for this function: