| // Copyright lowRISC contributors. | |
| // Licensed under the Apache License, Version 2.0, see LICENSE for details. | |
| // SPDX-License-Identifier: Apache-2.0 | |
| #include "sw/device/silicon_creator/lib/sigverify/mod_exp_ibex.h" | |
| #include <stddef.h> | |
| #include "sw/device/lib/base/macros.h" | |
| #include "sw/device/lib/base/memory.h" | |
| /** | |
| * Subtracts the modulus of `key` from `a` in-place, i.e. `a -= n`. | |
| * | |
| * Since `a` can be smaller than the modulus, this function also returns the | |
| * borrow. | |
| * | |
| * @param key An RSA public key. | |
| * @param[in,out] a Buffer that holds `a`, little-endian. | |
| * @return Borrow. | |
| */ | |
| static uint32_t subtract_modulus(const sigverify_rsa_key_t *key, | |
| sigverify_rsa_buffer_t *a) { | |
| uint32_t borrow = 0; | |
| for (size_t i = 0; i < ARRAYSIZE(a->data); ++i) { | |
| uint32_t temp = a->data[i] - borrow; | |
| // We borrow if either the above or the below subtraction wraps around. | |
| // Note: borrow can only be 0 or 1. | |
| borrow = (a->data[i] < borrow) + (temp < key->n.data[i]); | |
| a->data[i] = temp - key->n.data[i]; | |
| } | |
| return borrow; | |
| } | |
| /** | |
| * Checks if `a` is greater than or equal to the modulus of `key`. | |
| * | |
| * @param key An RSA public key. | |
| * @param a Buffer that holds `a`, little-endian. | |
| * @return Comparison result. | |
| */ | |
| static bool greater_equal_modulus(const sigverify_rsa_key_t *key, | |
| const sigverify_rsa_buffer_t *a) { | |
| // Note: Loop terminates when `i` wraps around. | |
| for (size_t i = ARRAYSIZE(a->data) - 1; i < ARRAYSIZE(a->data); --i) { | |
| if (a->data[i] != key->n.data[i]) { | |
| return a->data[i] > key->n.data[i]; | |
| } | |
| } | |
| return true; | |
| } | |
| /** | |
| * Shifts `a` left one bit in-place, i.e. `a <<= 1`. | |
| * | |
| * Since the result may not fit in `a`, this function also returns the most | |
| * significant bit of the result. | |
| * | |
| * @param[in,out] a Buffer that holds `a`, little-endian. | |
| * @return Most significant bit of the result. | |
| */ | |
| static uint32_t shift_left(sigverify_rsa_buffer_t *a) { | |
| const uint32_t msb = a->data[ARRAYSIZE(a->data) - 1] >> 31; | |
| for (size_t i = ARRAYSIZE(a->data) - 1; i > 0; --i) { | |
| a->data[i] = (a->data[i] << 1) | (a->data[i - 1] >> 31); | |
| } | |
| a->data[0] <<= 1; | |
| return msb; | |
| } | |
| /** | |
| * Computes the Montgomery reduction of the product of two integers. | |
| * | |
| * Given an RSA public key, x, and y this function computes x*y*R^-1 mod n, | |
| * where | |
| * - x and y are integers with `kSigVerifyRsaNumWords` base 2^32 digits, | |
| * - n is the modulus of the key, and | |
| * - R is 2^`kSigVerifyRsaNumBits`, e.g. 2^3072 for RSA-3072. | |
| * | |
| * See Handbook of Applied Cryptography, Ch. 14, Alg. 14.36. | |
| * | |
| * @param key An RSA public key. | |
| * @param x Buffer that holds `x`, little-endian. | |
| * @param y Buffer that holds `y`, little-endian. | |
| * @param[out] result Buffer to write the result to, little-endian. | |
| */ | |
| static void mont_mul(const sigverify_rsa_key_t *key, | |
| const sigverify_rsa_buffer_t *x, | |
| const sigverify_rsa_buffer_t *y, | |
| sigverify_rsa_buffer_t *result) { | |
| memset(result->data, 0, sizeof(result->data)); | |
| for (size_t i = 0; i < ARRAYSIZE(x->data); ++i) { | |
| // The loop below reads one word ahead of writes to avoid a separate loop | |
| // for the division by `b` in step 2.2 of the algorithm. Thus, `acc0` and | |
| // `acc1` are initialized here before the loop. `acc0` holds the sum of | |
| // first two addends in step 2.2 while `acc1` holds the entire sum. Carries | |
| // of these operations are stored separately in the upper words of `acc0` | |
| // and `acc1`. `acc0` and `acc1` can safely store these intermediate values, | |
| // i.e. without wrapping, because UINT32_MAX^2 + 2*UINT32_MAX is | |
| // 0xffff_ffff_ffff_ffff. | |
| // Holds the sum of the first two addends in step 2.2. | |
| uint64_t acc0 = (uint64_t)x->data[i] * y->data[0] + result->data[0]; | |
| const uint32_t u_i = (uint32_t)acc0 * key->n0_inv[0]; | |
| // Holds the sum of the all three addends in step 2.2. | |
| uint64_t acc1 = (uint64_t)u_i * key->n.data[0] + (uint32_t)acc0; | |
| // Process the i^th digit of `x`, i.e. `x[i]`. | |
| for (size_t j = 1; j < ARRAYSIZE(result->data); ++j) { | |
| acc0 = (uint64_t)x->data[i] * y->data[j] + result->data[j] + (acc0 >> 32); | |
| acc1 = (uint64_t)u_i * key->n.data[j] + (uint32_t)acc0 + (acc1 >> 32); | |
| result->data[j - 1] = (uint32_t)acc1; | |
| } | |
| acc0 = (acc0 >> 32) + (acc1 >> 32); | |
| result->data[ARRAYSIZE(result->data) - 1] = (uint32_t)acc0; | |
| // The intermediate result of this algorithm before the check below is | |
| // bounded by R + n (Eq. (4) in Montgomery Arithmetic from a Software | |
| // Perspective, Bos. J. W, Montgomery, P. L.) where n is the modulus of | |
| // `key` and n < R. Therefore, if there is a carry, then `result` is not the | |
| // least non-negative residue of x*y*R^-1 mod n. Since `acc0 >> 32` here is | |
| // at most 1, we can subtract the modulus from `result` without taking it | |
| // into account and fit `result` into `kSigVerifyRsaNumWords`. Since this is | |
| // not a direct comparison with the modulus, the final result is not | |
| // guaranteed to be the the least non-negative residue of x*y*R^-1 mod n. | |
| if (acc0 >> 32) { | |
| subtract_modulus(key, result); | |
| } | |
| } | |
| } | |
| /** | |
| * Calculates R^2 mod n, where R = 2^kSigVerifyRsaNumBits. | |
| * | |
| * @param key An RSA public key. | |
| * @param[out] result Buffer to write the result to, little-endian. | |
| */ | |
| static void calc_r_square(const sigverify_rsa_key_t *key, | |
| sigverify_rsa_buffer_t *result) { | |
| sigverify_rsa_buffer_t buf; | |
| memset(buf.data, 0, sizeof(result->data)); | |
| // This subtraction sets buf = -n mod R = R - n, which is equivalent to R | |
| // modulo n and ensures that `buf` fits in `kSigVerifyRsaNumWords` going | |
| // into the loop. | |
| subtract_modulus(key, &buf); | |
| // Compute (2^96 * R) mod n. | |
| // Each run of the loop doubles buf and reduces modulo n. | |
| for (size_t i = 0; i < 96; ++i) { | |
| uint32_t msb = shift_left(&buf); | |
| // Reduce until buf < n. Doing this at every iteration minimizes the | |
| // total number of subtractions that we need to perform. | |
| while (msb > 0 || greater_equal_modulus(key, &buf)) { | |
| msb -= subtract_modulus(key, &buf); | |
| } | |
| } | |
| // Perform 5 montgomery squares to get RR = ((2^96)^32 * R) mod n | |
| mont_mul(key, &buf, &buf, result); | |
| for (size_t i = 0; i < 2; ++i) { | |
| mont_mul(key, result, result, &buf); | |
| mont_mul(key, &buf, &buf, result); | |
| } | |
| } | |
| rom_error_t sigverify_mod_exp_ibex(const sigverify_rsa_key_t *key, | |
| const sigverify_rsa_buffer_t *sig, | |
| sigverify_rsa_buffer_t *result) { | |
| // Reject the signature if it is too large (n <= sig): RFC 8017, section | |
| // 5.2.2, step 1. | |
| if (greater_equal_modulus(key, sig)) { | |
| return kErrorSigverifyBadSignature; | |
| } | |
| sigverify_rsa_buffer_t buf; | |
| // result = R^2 mod n | |
| calc_r_square(key, result); | |
| // buf = sig * R mod n | |
| mont_mul(key, sig, result, &buf); | |
| for (size_t i = 0; i < 8; ++i) { | |
| // result = sig^{2*4^i} * R mod n (sig's exponent: 2, 8, 32, ..., 32768) | |
| mont_mul(key, &buf, &buf, result); | |
| // buf = sig^{4^{i+1}} * R mod n (sig's exponent: 4, 16, 64, ..., 65536) | |
| mont_mul(key, result, result, &buf); | |
| } | |
| // result = sig^65537 mod n | |
| mont_mul(key, &buf, sig, result); | |
| // We need this check because the result of `mont_mul` is not guaranteed to be | |
| // the least non-negative residue. We need to subtract the modulus n from | |
| // `result` at most once because R/2 < n < R. | |
| if (greater_equal_modulus(key, result)) { | |
| subtract_modulus(key, result); | |
| } | |
| return kErrorOk; | |
| } |