2  * \brief  Multi-precision integer library, ESP32 hardware accelerated parts
6  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
8  *  SPDX-License-Identifier: Apache-2.0
14  *  http://www.apache.org/licenses/LICENSE-2.0
42  * - Naming convention x_words, y_words, z_words for number of words (limbs) used in a particular
45 …* - Naming convention hw_words for the hardware length of the operation. This number maybe be roun…
49 …* - Timing behaviour of these functions will depend on the length of the inputs. This is fundament…
73     for (size_t i = mpi->n; i > 0; i--) {  in mpi_words()
74         if (mpi->p[i - 1] != 0) {  in mpi_words()
85  * There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1,
86  * where B^-1(B-1) mod N=1. Actually, only the least significant part of
95     uint64_t two_2_i_minus_1 = 2;   /* 2^(i-1) */  in modular_inverse()
97     uint64_t N = M->p[0];  in modular_inverse()
108     return (mbedtls_mpi_uint)(UINT32_MAX - t + 1);  in modular_inverse()
143 /* Z = (X * Y) mod M
147 int esp_mpi_mul_mpi_mod(mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi *Y, const mbedtls_m…  in esp_mpi_mul_mpi_mod()  argument
151     size_t x_bits = mbedtls_mpi_bitlen(X);  in esp_mpi_mul_mpi_mod()
169     /* Load and start a (X * Y) mod M calculation */  in esp_mpi_mul_mpi_mod()
170     esp_mpi_mul_mpi_mod_hw_op(X, Y, M, &Rinv, Mprime, hw_words);  in esp_mpi_mul_mpi_mod()
175     Z->s = X->s * Y->s;  in esp_mpi_mul_mpi_mod()
188  * Return the most significant one-bit.
190 static size_t mbedtls_mpi_msb( const mbedtls_mpi *X )  in mbedtls_mpi_msb()  argument
193     if (X != NULL && X->n != 0) {  in mbedtls_mpi_msb()
194         for (i = X->n - 1; i >= 0; i--) {  in mbedtls_mpi_msb()
195             if (X->p[i] != 0) {  in mbedtls_mpi_msb()
196                 for (j = biL - 1; j >= 0; j--) {  in mbedtls_mpi_msb()
197                     if ((X->p[i] & (1 << j)) != 0) {  in mbedtls_mpi_msb()
208  * Montgomery exponentiation: Z = X ^ Y mod M  (HAC 14.94)
210 static int mpi_montgomery_exp_calc( mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi *Y, con…  in mpi_montgomery_exp_calc()  argument
232         // 1.1 x_ = mont(x, R^2 mod m)  in mpi_montgomery_exp_calc()
233         //        = mont(x, rb)  in mpi_montgomery_exp_calc()
234         MBEDTLS_MPI_CHK( esp_mont_hw_op(&X_, X, Rinv, M, Mprime, hw_words, false) );  in mpi_montgomery_exp_calc()
237         // now z = R mod m = Mont (R^2 mod m, 1) mod M (as Mont(x) = X&R^-1 mod M)  in mpi_montgomery_exp_calc()
241         for (int i = t; i >= 0; i--) {  in mpi_montgomery_exp_calc()
269  * Z = X ^ Y mod M
271  * _Rinv is optional pre-calculated version of Rinv (via calculate_rinv()).
276 static int esp_mpi_exp_mod( mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi *Y, const mbedt…  in esp_mpi_exp_mod()  argument
284     size_t x_words = mpi_words(X);  in esp_mpi_exp_mod()
297     if (mbedtls_mpi_cmp_int(M, 0) <= 0 || (M->p[0] & 1) == 0) {  in esp_mpi_exp_mod()
317     if (Rinv->p == NULL) {  in esp_mpi_exp_mod()
323     // Montgomery exponentiation: Z = X ^ Y mod M  (HAC 14.94)  in esp_mpi_exp_mod()
325     ret = mpi_montgomery_exp_calc(Z, X, Y, M, Rinv, num_words, Mprime) ;  in esp_mpi_exp_mod()
330     esp_mpi_exp_mpi_mod_hw_op(X, Y, M, Rinv, Mprime, num_words);  in esp_mpi_exp_mod()
340     // Compensate for negative X  in esp_mpi_exp_mod()
341     if (X->s == -1 && (Y->p[0] & 1) != 0) {  in esp_mpi_exp_mod()
342         Z->s = -1;  in esp_mpi_exp_mod()
345         Z->s = 1;  in esp_mpi_exp_mod()
358  * Sliding-window exponentiation: X = A^E mod N  (HAC 14.85)
360 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,  in mbedtls_mpi_exp_mod()  argument
367     ret = esp_mpi_exp_mod( X, A, E, N, _RR );  in mbedtls_mpi_exp_mod()
369         ret = mbedtls_mpi_exp_mod_soft( X, A, E, N, _RR );  in mbedtls_mpi_exp_mod()
373     ret = esp_mpi_exp_mod( X, A, E, N, _RR );  in mbedtls_mpi_exp_mod()
383 static int mpi_mult_mpi_failover_mod_mult( mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi …
384 static int mpi_mult_mpi_overlong(mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi *Y, size_t…
386 /* Z = X * Y */
387 int mbedtls_mpi_mul_mpi( mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi *Y )  in mbedtls_mpi_mul_mpi()  argument
390     size_t x_bits = mbedtls_mpi_bitlen(X);  in mbedtls_mpi_mul_mpi()
397     /* Short-circuit eval if either argument is 0 or 1.  in mbedtls_mpi_mul_mpi()
410         Z->s *= X->s;  in mbedtls_mpi_mul_mpi()
414         ret = mbedtls_mpi_copy(Z, X);  in mbedtls_mpi_mul_mpi()
415         Z->s *= Y->s;  in mbedtls_mpi_mul_mpi()
427        number of bits in X plus number of bits in in Y.)  in mbedtls_mpi_mul_mpi()
435             return mpi_mult_mpi_failover_mod_mult(Z, X, Y, z_words);  in mbedtls_mpi_mul_mpi()
439                 return mpi_mult_mpi_overlong(Z, X, Y, y_words, z_words);  in mbedtls_mpi_mul_mpi()
441                 return mpi_mult_mpi_overlong(Z, Y, X, x_words, z_words);  in mbedtls_mpi_mul_mpi()
449     esp_mpi_mul_mpi_hw_op(X, Y, hw_words);  in mbedtls_mpi_mul_mpi()
454     Z->s = X->s * Y->s;  in mbedtls_mpi_mul_mpi()
460 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )  in mbedtls_mpi_mul_int()  argument
470     return( mbedtls_mpi_mul_mpi( X, A, &_B ) );  in mbedtls_mpi_mul_int()
473 /* Deal with the case when X & Y are too long for the hardware unit, by splitting one operand
483    Z = X * Y
484    Z = X * (Yp + Ypp<<b)
485    Z = (X * Yp) + (X * Ypp<<b)
487    Note that this function may recurse multiple times, if both X & Y
490 static int mpi_mult_mpi_overlong(mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi *Y, size_t…  in mpi_mult_mpi_overlong()  argument
498         .p = Y->p,  in mpi_mult_mpi_overlong()
500         .s = Y->s  in mpi_mult_mpi_overlong()
504         .p = Y->p + words_slice,  in mpi_mult_mpi_overlong()
505         .n = y_words - words_slice,  in mpi_mult_mpi_overlong()
506         .s = Y->s  in mpi_mult_mpi_overlong()
510     /* Get result Ztemp = Yp * X (need temporary variable Ztemp) */  in mpi_mult_mpi_overlong()
511     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi(&Ztemp, X, &Yp) );  in mpi_mult_mpi_overlong()
514     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi(Z, X, &Ypp) );  in mpi_mult_mpi_overlong()
528 /* Special-case of mbedtls_mpi_mult_mpi(), where we use hardware montgomery mod
537    * Modulus is chosen with M=(2^num_bits - 1) (ie M=R-1), so output
546 static int mpi_mult_mpi_failover_mod_mult( mbedtls_mpi *Z, const mbedtls_mpi *X, const mbedtls_mpi …  in mpi_mult_mpi_failover_mod_mult()  argument
553     esp_mpi_mult_mpi_failover_mod_mult_hw_op(X, Y, hw_words );  in mpi_mult_mpi_failover_mod_mult()
557     Z->s = X->s * Y->s;  in mpi_mult_mpi_failover_mod_mult()