lib/libmpa/mpa_expmod.c

// SPDX-License-Identifier: BSD-2-Clause
/*
 * Copyright (c) 2014, STMicroelectronics International N.V.
 */
#include "mpa.h"

#define swp(a, b) do { \
		mpanum *tmp = *a; \
		*a = *b; \
		*b = tmp; \
	} while (0)

/*------------------------------------------------------------
 *
 *  mpa_exp_mod
 *
 *  Calculates dest = op1 ^ op2 mod n
 *
 * This function uses the Montgomery ladder concept as proposed by Marc Joye and
 * Sun-Ming Yen, which makes the function more resistant to timing attacks.
 */
void mpa_exp_mod(mpanum dest,
		 const mpanum op1,
		 const mpanum op2,
		 const mpanum n,
		 const mpanum r_modn,
		 const mpanum r2_modn,
		 const mpa_word_t n_inv, mpa_scratch_mem pool)
{
	mpanum A;
	mpanum tmp_a;
	mpanum xtilde;
	mpanum tmp_xtilde;
	mpanum *ptr_a;
	mpanum *ptr_tmp_a;
	mpanum *ptr_xtilde;
	mpanum *ptr_tmp_xtilde;
	int idx;

	mpa_alloc_static_temp_var(&A, pool);
	mpa_alloc_static_temp_var(&tmp_a, pool);
	mpa_alloc_static_temp_var(&xtilde, pool);
	mpa_alloc_static_temp_var(&tmp_xtilde, pool);

	/*
	 * Transform the base (op1) into Montgomery space. Use internal version
	 * since xtilde is big enough.
	 */
	__mpa_montgomery_mul(xtilde, op1, r2_modn, n, n_inv);

	mpa_copy(A, r_modn);

	ptr_a = &A;
	ptr_tmp_a = &tmp_a;
	ptr_xtilde = &xtilde;
	ptr_tmp_xtilde = &tmp_xtilde;

	__mpa_set_unused_digits_to_zero(A);
	__mpa_set_unused_digits_to_zero(xtilde);

	for (idx = mpa_highest_bit_index(op2); idx >= 0; idx--) {
		if (mpa_get_bit(op2, idx) == 0) {
			/* x' = A*x' */
			__mpa_montgomery_mul(*ptr_tmp_xtilde, *ptr_a,
					     *ptr_xtilde, n, n_inv);

			/* A = A^2 */
			__mpa_montgomery_mul(*ptr_tmp_a, *ptr_a, *ptr_a, n,
					     n_inv);
		} else {
			/* A = A*x' */
			__mpa_montgomery_mul(*ptr_tmp_a, *ptr_a, *ptr_xtilde, n,
					     n_inv);

			/* x' = x'^2 */
			__mpa_montgomery_mul(*ptr_tmp_xtilde, *ptr_xtilde,
					     *ptr_xtilde, n, n_inv);
		}

		/*
		 * The simple reason for swapping here is to avoid copy
		 * intermediate results, instead we're just moving the pointers.
		 */
		swp(&ptr_tmp_a, &ptr_a);
		swp(&ptr_tmp_xtilde, &ptr_xtilde);
	}

	/* Transform back from Montgomery space */
	__mpa_montgomery_mul(*ptr_tmp_a, (const mpanum)&const_one, *ptr_a,
			     n, n_inv);

	mpa_copy(dest, *ptr_tmp_a);

	mpa_free_static_temp_var(&A, pool);
	mpa_free_static_temp_var(&tmp_a, pool);
	mpa_free_static_temp_var(&xtilde, pool);
	mpa_free_static_temp_var(&tmp_xtilde, pool);
}