lib/rsa/rsa-mod-exp.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (c) 2013, Google Inc.
   4  */
   5
   6 #ifndef USE_HOSTCC
   7 #include <common.h>
   8 #include <fdtdec.h>
   9 #include <asm/types.h>
  10 #include <asm/byteorder.h>
  11 #include <linux/errno.h>
  12 #include <asm/types.h>
  13 #include <asm/unaligned.h>
  14 #else
  15 #include "fdt_host.h"
  16 #include "mkimage.h"
  17 #include <fdt_support.h>
  18 #endif
  19 #include <u-boot/rsa.h>
  20 #include <u-boot/rsa-mod-exp.h>
  21
  22 #define UINT64_MULT32(v, multby)  (((uint64_t)(v)) * ((uint32_t)(multby)))
  23
  24 #define get_unaligned_be32(a) fdt32_to_cpu(*(uint32_t *)a)
  25 #define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_fdt32(a))
  26
  27 /* Default public exponent for backward compatibility */
  28 #define RSA_DEFAULT_PUBEXP      65537
  29
  30 /**
  31  * subtract_modulus() - subtract modulus from the given value
  32  *
  33  * @key:        Key containing modulus to subtract
  34  * @num:        Number to subtract modulus from, as little endian word array
  35  */
  36 static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[])
  37 {
  38         int64_t acc = 0;
  39         uint i;
  40
  41         for (i = 0; i < key->len; i++) {
  42                 acc += (uint64_t)num[i] - key->modulus[i];
  43                 num[i] = (uint32_t)acc;
  44                 acc >>= 32;
  45         }
  46 }
  47
  48 /**
  49  * greater_equal_modulus() - check if a value is >= modulus
  50  *
  51  * @key:        Key containing modulus to check
  52  * @num:        Number to check against modulus, as little endian word array
  53  * @return 0 if num < modulus, 1 if num >= modulus
  54  */
  55 static int greater_equal_modulus(const struct rsa_public_key *key,
  56                                  uint32_t num[])
  57 {
  58         int i;
  59
  60         for (i = (int)key->len - 1; i >= 0; i--) {
  61                 if (num[i] < key->modulus[i])
  62                         return 0;
  63                 if (num[i] > key->modulus[i])
  64                         return 1;
  65         }
  66
  67         return 1;  /* equal */
  68 }
  69
  70 /**
  71  * montgomery_mul_add_step() - Perform montgomery multiply-add step
  72  *
  73  * Operation: montgomery result[] += a * b[] / n0inv % modulus
  74  *
  75  * @key:        RSA key
  76  * @result:     Place to put result, as little endian word array
  77  * @a:          Multiplier
  78  * @b:          Multiplicand, as little endian word array
  79  */
  80 static void montgomery_mul_add_step(const struct rsa_public_key *key,
  81                 uint32_t result[], const uint32_t a, const uint32_t b[])
  82 {
  83         uint64_t acc_a, acc_b;
  84         uint32_t d0;
  85         uint i;
  86
  87         acc_a = (uint64_t)a * b[0] + result[0];
  88         d0 = (uint32_t)acc_a * key->n0inv;
  89         acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a;
  90         for (i = 1; i < key->len; i++) {
  91                 acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i];
  92                 acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] +
  93                                 (uint32_t)acc_a;
  94                 result[i - 1] = (uint32_t)acc_b;
  95         }
  96
  97         acc_a = (acc_a >> 32) + (acc_b >> 32);
  98
  99         result[i - 1] = (uint32_t)acc_a;
 100
 101         if (acc_a >> 32)
 102                 subtract_modulus(key, result);
 103 }
 104
 105 /**
 106  * montgomery_mul() - Perform montgomery mutitply
 107  *
 108  * Operation: montgomery result[] = a[] * b[] / n0inv % modulus
 109  *
 110  * @key:        RSA key
 111  * @result:     Place to put result, as little endian word array
 112  * @a:          Multiplier, as little endian word array
 113  * @b:          Multiplicand, as little endian word array
 114  */
 115 static void montgomery_mul(const struct rsa_public_key *key,
 116                 uint32_t result[], uint32_t a[], const uint32_t b[])
 117 {
 118         uint i;
 119
 120         for (i = 0; i < key->len; ++i)
 121                 result[i] = 0;
 122         for (i = 0; i < key->len; ++i)
 123                 montgomery_mul_add_step(key, result, a[i], b);
 124 }
 125
 126 /**
 127  * num_pub_exponent_bits() - Number of bits in the public exponent
 128  *
 129  * @key:        RSA key
 130  * @num_bits:   Storage for the number of public exponent bits
 131  */
 132 static int num_public_exponent_bits(const struct rsa_public_key *key,
 133                 int *num_bits)
 134 {
 135         uint64_t exponent;
 136         int exponent_bits;
 137         const uint max_bits = (sizeof(exponent) * 8);
 138
 139         exponent = key->exponent;
 140         exponent_bits = 0;
 141
 142         if (!exponent) {
 143                 *num_bits = exponent_bits;
 144                 return 0;
 145         }
 146
 147         for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits)
 148                 if (!(exponent >>= 1)) {
 149                         *num_bits = exponent_bits;
 150                         return 0;
 151                 }
 152
 153         return -EINVAL;
 154 }
 155
 156 /**
 157  * is_public_exponent_bit_set() - Check if a bit in the public exponent is set
 158  *
 159  * @key:        RSA key
 160  * @pos:        The bit position to check
 161  */
 162 static int is_public_exponent_bit_set(const struct rsa_public_key *key,
 163                 int pos)
 164 {
 165         return key->exponent & (1ULL << pos);
 166 }
 167
 168 /**
 169  * pow_mod() - in-place public exponentiation
 170  *
 171  * @key:        RSA key
 172  * @inout:      Big-endian word array containing value and result
 173  */
 174 static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
 175 {
 176         uint32_t *result, *ptr;
 177         uint i;
 178         int j, k;
 179
 180         /* Sanity check for stack size - key->len is in 32-bit words */
 181         if (key->len > RSA_MAX_KEY_BITS / 32) {
 182                 debug("RSA key words %u exceeds maximum %d\n", key->len,
 183                       RSA_MAX_KEY_BITS / 32);
 184                 return -EINVAL;
 185         }
 186
 187         uint32_t val[key->len], acc[key->len], tmp[key->len];
 188         uint32_t a_scaled[key->len];
 189         result = tmp;  /* Re-use location. */
 190
 191         /* Convert from big endian byte array to little endian word array. */
 192         for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--)
 193                 val[i] = get_unaligned_be32(ptr);
 194
 195         if (0 != num_public_exponent_bits(key, &k))
 196                 return -EINVAL;
 197
 198         if (k < 2) {
 199                 debug("Public exponent is too short (%d bits, minimum 2)\n",
 200                       k);
 201                 return -EINVAL;
 202         }
 203
 204         if (!is_public_exponent_bit_set(key, 0)) {
 205                 debug("LSB of RSA public exponent must be set.\n");
 206                 return -EINVAL;
 207         }
 208
 209         /* the bit at e[k-1] is 1 by definition, so start with: C := M */
 210         montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */
 211         /* retain scaled version for intermediate use */
 212         memcpy(a_scaled, acc, key->len * sizeof(a_scaled[0]));
 213
 214         for (j = k - 2; j > 0; --j) {
 215                 montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
 216
 217                 if (is_public_exponent_bit_set(key, j)) {
 218                         /* acc = tmp * val / R mod n */
 219                         montgomery_mul(key, acc, tmp, a_scaled);
 220                 } else {
 221                         /* e[j] == 0, copy tmp back to acc for next operation */
 222                         memcpy(acc, tmp, key->len * sizeof(acc[0]));
 223                 }
 224         }
 225
 226         /* the bit at e[0] is always 1 */
 227         montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
 228         montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */
 229         memcpy(result, acc, key->len * sizeof(result[0]));
 230
 231         /* Make sure result < mod; result is at most 1x mod too large. */
 232         if (greater_equal_modulus(key, result))
 233                 subtract_modulus(key, result);
 234
 235         /* Convert to bigendian byte array */
 236         for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++)
 237                 put_unaligned_be32(result[i], ptr);
 238         return 0;
 239 }
 240
 241 static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len)
 242 {
 243         int i;
 244
 245         for (i = 0; i < len; i++)
 246                 dst[i] = fdt32_to_cpu(src[len - 1 - i]);
 247 }
 248
 249 int rsa_mod_exp_sw(const uint8_t *sig, uint32_t sig_len,
 250                 struct key_prop *prop, uint8_t *out)
 251 {
 252         struct rsa_public_key key;
 253         int ret;
 254
 255         if (!prop) {
 256                 debug("%s: Skipping invalid prop", __func__);
 257                 return -EBADF;
 258         }
 259         key.n0inv = prop->n0inv;
 260         key.len = prop->num_bits;
 261
 262         if (!prop->public_exponent)
 263                 key.exponent = RSA_DEFAULT_PUBEXP;
 264         else
 265                 key.exponent =
 266                         fdt64_to_cpu(*((uint64_t *)(prop->public_exponent)));
 267
 268         if (!key.len || !prop->modulus || !prop->rr) {
 269                 debug("%s: Missing RSA key info", __func__);
 270                 return -EFAULT;
 271         }
 272
 273         /* Sanity check for stack size */
 274         if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) {
 275                 debug("RSA key bits %u outside allowed range %d..%d\n",
 276                       key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS);
 277                 return -EFAULT;
 278         }
 279         key.len /= sizeof(uint32_t) * 8;
 280         uint32_t key1[key.len], key2[key.len];
 281
 282         key.modulus = key1;
 283         key.rr = key2;
 284         rsa_convert_big_endian(key.modulus, (uint32_t *)prop->modulus, key.len);
 285         rsa_convert_big_endian(key.rr, (uint32_t *)prop->rr, key.len);
 286         if (!key.modulus || !key.rr) {
 287                 debug("%s: Out of memory", __func__);
 288                 return -ENOMEM;
 289         }
 290
 291         uint32_t buf[sig_len / sizeof(uint32_t)];
 292
 293         memcpy(buf, sig, sig_len);
 294
 295         ret = pow_mod(&key, buf);
 296         if (ret)
 297                 return ret;
 298
 299         memcpy(out, buf, sig_len);
 300
 301         return 0;
 302 }
 303
 304 #if defined(CONFIG_CMD_ZYNQ_RSA)
 305 /**
 306  * zynq_pow_mod - in-place public exponentiation
 307  *
 308  * @keyptr:     RSA key
 309  * @inout:      Big-endian word array containing value and result
 310  * @return 0 on successful calculation, otherwise failure error code
 311  *
 312  * FIXME: Use pow_mod() instead of zynq_pow_mod()
 313  *        pow_mod calculation required for zynq is bit different from
 314  *        pw_mod above here, hence defined zynq specific routine.
 315  */
 316 int zynq_pow_mod(u32 *keyptr, u32 *inout)
 317 {
 318         u32 *result, *ptr;
 319         uint i;
 320         struct rsa_public_key *key;
 321         u32 val[RSA2048_BYTES], acc[RSA2048_BYTES], tmp[RSA2048_BYTES];
 322
 323         key = (struct rsa_public_key *)keyptr;
 324
 325         /* Sanity check for stack size - key->len is in 32-bit words */
 326         if (key->len > RSA_MAX_KEY_BITS / 32) {
 327                 debug("RSA key words %u exceeds maximum %d\n", key->len,
 328                       RSA_MAX_KEY_BITS / 32);
 329                 return -EINVAL;
 330         }
 331
 332         result = tmp;  /* Re-use location. */
 333
 334         for (i = 0, ptr = inout; i < key->len; i++, ptr++)
 335                 val[i] = *(ptr);
 336
 337         montgomery_mul(key, acc, val, key->rr);  /* axx = a * RR / R mod M */
 338         for (i = 0; i < 16; i += 2) {
 339                 montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod M */
 340                 montgomery_mul(key, acc, tmp, tmp); /* acc = tmp^2 / R mod M */
 341         }
 342         montgomery_mul(key, result, acc, val);  /* result = XX * a / R mod M */
 343
 344         /* Make sure result < mod; result is at most 1x mod too large. */
 345         if (greater_equal_modulus(key, result))
 346                 subtract_modulus(key, result);
 347
 348         for (i = 0, ptr = inout; i < key->len; i++, ptr++)
 349                 *ptr = result[i];
 350
 351         return 0;
 352 }
 353 #endif