crypto/rsa.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* RSA asymmetric public-key algorithm [RFC3447]
   3  *
   4  * Copyright (c) 2015, Intel Corporation
   5  * Authors: Tadeusz Struk <[email protected]>
   6  */
   7
   8 #include <linux/fips.h>
   9 #include <linux/module.h>
  10 #include <linux/mpi.h>
  11 #include <crypto/internal/rsa.h>
  12 #include <crypto/internal/akcipher.h>
  13 #include <crypto/akcipher.h>
  14 #include <crypto/algapi.h>
  15
  16 struct rsa_mpi_key {
  17         MPI n;
  18         MPI e;
  19         MPI d;
  20         MPI p;
  21         MPI q;
  22         MPI dp;
  23         MPI dq;
  24         MPI qinv;
  25 };
  26
  27 static int rsa_check_payload(MPI x, MPI n)
  28 {
  29         MPI n1;
  30
  31         if (mpi_cmp_ui(x, 1) <= 0)
  32                 return -EINVAL;
  33
  34         n1 = mpi_alloc(0);
  35         if (!n1)
  36                 return -ENOMEM;
  37
  38         if (mpi_sub_ui(n1, n, 1) || mpi_cmp(x, n1) >= 0) {
  39                 mpi_free(n1);
  40                 return -EINVAL;
  41         }
  42
  43         mpi_free(n1);
  44         return 0;
  45 }
  46
  47 /*
  48  * RSAEP function [RFC3447 sec 5.1.1]
  49  * c = m^e mod n;
  50  */
  51 static int _rsa_enc(const struct rsa_mpi_key *key, MPI c, MPI m)
  52 {
  53         /*
  54          * Even though (1) in RFC3447 only requires 0 <= m <= n - 1, we are
  55          * slightly more conservative and require 1 < m < n - 1. This is in line
  56          * with SP 800-56Br2, Section 7.1.1.
  57          */
  58         if (rsa_check_payload(m, key->n))
  59                 return -EINVAL;
  60
  61         /* (2) c = m^e mod n */
  62         return mpi_powm(c, m, key->e, key->n);
  63 }
  64
  65 /*
  66  * RSADP function [RFC3447 sec 5.1.2]
  67  * m_1 = c^dP mod p;
  68  * m_2 = c^dQ mod q;
  69  * h = (m_1 - m_2) * qInv mod p;
  70  * m = m_2 + q * h;
  71  */
  72 static int _rsa_dec_crt(const struct rsa_mpi_key *key, MPI m_or_m1_or_h, MPI c)
  73 {
  74         MPI m2, m12_or_qh;
  75         int ret = -ENOMEM;
  76
  77         /*
  78          * Even though (1) in RFC3447 only requires 0 <= c <= n - 1, we are
  79          * slightly more conservative and require 1 < c < n - 1. This is in line
  80          * with SP 800-56Br2, Section 7.1.2.
  81          */
  82         if (rsa_check_payload(c, key->n))
  83                 return -EINVAL;
  84
  85         m2 = mpi_alloc(0);
  86         m12_or_qh = mpi_alloc(0);
  87         if (!m2 || !m12_or_qh)
  88                 goto err_free_mpi;
  89
  90         /* (2i) m_1 = c^dP mod p */
  91         ret = mpi_powm(m_or_m1_or_h, c, key->dp, key->p);
  92         if (ret)
  93                 goto err_free_mpi;
  94
  95         /* (2i) m_2 = c^dQ mod q */
  96         ret = mpi_powm(m2, c, key->dq, key->q);
  97         if (ret)
  98                 goto err_free_mpi;
  99
 100         /* (2iii) h = (m_1 - m_2) * qInv mod p */
 101         ret = mpi_sub(m12_or_qh, m_or_m1_or_h, m2) ?:
 102               mpi_mulm(m_or_m1_or_h, m12_or_qh, key->qinv, key->p);
 103
 104         /* (2iv) m = m_2 + q * h */
 105         ret = ret ?:
 106               mpi_mul(m12_or_qh, key->q, m_or_m1_or_h) ?:
 107               mpi_addm(m_or_m1_or_h, m2, m12_or_qh, key->n);
 108
 109 err_free_mpi:
 110         mpi_free(m12_or_qh);
 111         mpi_free(m2);
 112         return ret;
 113 }
 114
 115 static inline struct rsa_mpi_key *rsa_get_key(struct crypto_akcipher *tfm)
 116 {
 117         return akcipher_tfm_ctx(tfm);
 118 }
 119
 120 static int rsa_enc(struct akcipher_request *req)
 121 {
 122         struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
 123         const struct rsa_mpi_key *pkey = rsa_get_key(tfm);
 124         MPI m, c = mpi_alloc(0);
 125         int ret = 0;
 126         int sign;
 127
 128         if (!c)
 129                 return -ENOMEM;
 130
 131         if (unlikely(!pkey->n || !pkey->e)) {
 132                 ret = -EINVAL;
 133                 goto err_free_c;
 134         }
 135
 136         ret = -ENOMEM;
 137         m = mpi_read_raw_from_sgl(req->src, req->src_len);
 138         if (!m)
 139                 goto err_free_c;
 140
 141         ret = _rsa_enc(pkey, c, m);
 142         if (ret)
 143                 goto err_free_m;
 144
 145         ret = mpi_write_to_sgl(c, req->dst, req->dst_len, &sign);
 146         if (ret)
 147                 goto err_free_m;
 148
 149         if (sign < 0)
 150                 ret = -EBADMSG;
 151
 152 err_free_m:
 153         mpi_free(m);
 154 err_free_c:
 155         mpi_free(c);
 156         return ret;
 157 }
 158
 159 static int rsa_dec(struct akcipher_request *req)
 160 {
 161         struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
 162         const struct rsa_mpi_key *pkey = rsa_get_key(tfm);
 163         MPI c, m = mpi_alloc(0);
 164         int ret = 0;
 165         int sign;
 166
 167         if (!m)
 168                 return -ENOMEM;
 169
 170         if (unlikely(!pkey->n || !pkey->d)) {
 171                 ret = -EINVAL;
 172                 goto err_free_m;
 173         }
 174
 175         ret = -ENOMEM;
 176         c = mpi_read_raw_from_sgl(req->src, req->src_len);
 177         if (!c)
 178                 goto err_free_m;
 179
 180         ret = _rsa_dec_crt(pkey, m, c);
 181         if (ret)
 182                 goto err_free_c;
 183
 184         ret = mpi_write_to_sgl(m, req->dst, req->dst_len, &sign);
 185         if (ret)
 186                 goto err_free_c;
 187
 188         if (sign < 0)
 189                 ret = -EBADMSG;
 190 err_free_c:
 191         mpi_free(c);
 192 err_free_m:
 193         mpi_free(m);
 194         return ret;
 195 }
 196
 197 static void rsa_free_mpi_key(struct rsa_mpi_key *key)
 198 {
 199         mpi_free(key->d);
 200         mpi_free(key->e);
 201         mpi_free(key->n);
 202         mpi_free(key->p);
 203         mpi_free(key->q);
 204         mpi_free(key->dp);
 205         mpi_free(key->dq);
 206         mpi_free(key->qinv);
 207         key->d = NULL;
 208         key->e = NULL;
 209         key->n = NULL;
 210         key->p = NULL;
 211         key->q = NULL;
 212         key->dp = NULL;
 213         key->dq = NULL;
 214         key->qinv = NULL;
 215 }
 216
 217 static int rsa_check_key_length(unsigned int len)
 218 {
 219         switch (len) {
 220         case 512:
 221         case 1024:
 222         case 1536:
 223                 if (fips_enabled)
 224                         return -EINVAL;
 225                 fallthrough;
 226         case 2048:
 227         case 3072:
 228         case 4096:
 229                 return 0;
 230         }
 231
 232         return -EINVAL;
 233 }
 234
 235 static int rsa_check_exponent_fips(MPI e)
 236 {
 237         MPI e_max = NULL;
 238         int err;
 239
 240         /* check if odd */
 241         if (!mpi_test_bit(e, 0)) {
 242                 return -EINVAL;
 243         }
 244
 245         /* check if 2^16 < e < 2^256. */
 246         if (mpi_cmp_ui(e, 65536) <= 0) {
 247                 return -EINVAL;
 248         }
 249
 250         e_max = mpi_alloc(0);
 251         if (!e_max)
 252                 return -ENOMEM;
 253
 254         err = mpi_set_bit(e_max, 256);
 255         if (err) {
 256                 mpi_free(e_max);
 257                 return err;
 258         }
 259
 260         if (mpi_cmp(e, e_max) >= 0) {
 261                 mpi_free(e_max);
 262                 return -EINVAL;
 263         }
 264
 265         mpi_free(e_max);
 266         return 0;
 267 }
 268
 269 static int rsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
 270                            unsigned int keylen)
 271 {
 272         struct rsa_mpi_key *mpi_key = akcipher_tfm_ctx(tfm);
 273         struct rsa_key raw_key = {0};
 274         int ret;
 275
 276         /* Free the old MPI key if any */
 277         rsa_free_mpi_key(mpi_key);
 278
 279         ret = rsa_parse_pub_key(&raw_key, key, keylen);
 280         if (ret)
 281                 return ret;
 282
 283         mpi_key->e = mpi_read_raw_data(raw_key.e, raw_key.e_sz);
 284         if (!mpi_key->e)
 285                 goto err;
 286
 287         mpi_key->n = mpi_read_raw_data(raw_key.n, raw_key.n_sz);
 288         if (!mpi_key->n)
 289                 goto err;
 290
 291         if (rsa_check_key_length(mpi_get_size(mpi_key->n) << 3)) {
 292                 rsa_free_mpi_key(mpi_key);
 293                 return -EINVAL;
 294         }
 295
 296         if (fips_enabled && rsa_check_exponent_fips(mpi_key->e)) {
 297                 rsa_free_mpi_key(mpi_key);
 298                 return -EINVAL;
 299         }
 300
 301         return 0;
 302
 303 err:
 304         rsa_free_mpi_key(mpi_key);
 305         return -ENOMEM;
 306 }
 307
 308 static int rsa_set_priv_key(struct crypto_akcipher *tfm, const void *key,
 309                             unsigned int keylen)
 310 {
 311         struct rsa_mpi_key *mpi_key = akcipher_tfm_ctx(tfm);
 312         struct rsa_key raw_key = {0};
 313         int ret;
 314
 315         /* Free the old MPI key if any */
 316         rsa_free_mpi_key(mpi_key);
 317
 318         ret = rsa_parse_priv_key(&raw_key, key, keylen);
 319         if (ret)
 320                 return ret;
 321
 322         mpi_key->d = mpi_read_raw_data(raw_key.d, raw_key.d_sz);
 323         if (!mpi_key->d)
 324                 goto err;
 325
 326         mpi_key->e = mpi_read_raw_data(raw_key.e, raw_key.e_sz);
 327         if (!mpi_key->e)
 328                 goto err;
 329
 330         mpi_key->n = mpi_read_raw_data(raw_key.n, raw_key.n_sz);
 331         if (!mpi_key->n)
 332                 goto err;
 333
 334         mpi_key->p = mpi_read_raw_data(raw_key.p, raw_key.p_sz);
 335         if (!mpi_key->p)
 336                 goto err;
 337
 338         mpi_key->q = mpi_read_raw_data(raw_key.q, raw_key.q_sz);
 339         if (!mpi_key->q)
 340                 goto err;
 341
 342         mpi_key->dp = mpi_read_raw_data(raw_key.dp, raw_key.dp_sz);
 343         if (!mpi_key->dp)
 344                 goto err;
 345
 346         mpi_key->dq = mpi_read_raw_data(raw_key.dq, raw_key.dq_sz);
 347         if (!mpi_key->dq)
 348                 goto err;
 349
 350         mpi_key->qinv = mpi_read_raw_data(raw_key.qinv, raw_key.qinv_sz);
 351         if (!mpi_key->qinv)
 352                 goto err;
 353
 354         if (rsa_check_key_length(mpi_get_size(mpi_key->n) << 3)) {
 355                 rsa_free_mpi_key(mpi_key);
 356                 return -EINVAL;
 357         }
 358
 359         if (fips_enabled && rsa_check_exponent_fips(mpi_key->e)) {
 360                 rsa_free_mpi_key(mpi_key);
 361                 return -EINVAL;
 362         }
 363
 364         return 0;
 365
 366 err:
 367         rsa_free_mpi_key(mpi_key);
 368         return -ENOMEM;
 369 }
 370
 371 static unsigned int rsa_max_size(struct crypto_akcipher *tfm)
 372 {
 373         struct rsa_mpi_key *pkey = akcipher_tfm_ctx(tfm);
 374
 375         return mpi_get_size(pkey->n);
 376 }
 377
 378 static void rsa_exit_tfm(struct crypto_akcipher *tfm)
 379 {
 380         struct rsa_mpi_key *pkey = akcipher_tfm_ctx(tfm);
 381
 382         rsa_free_mpi_key(pkey);
 383 }
 384
 385 static struct akcipher_alg rsa = {
 386         .encrypt = rsa_enc,
 387         .decrypt = rsa_dec,
 388         .set_priv_key = rsa_set_priv_key,
 389         .set_pub_key = rsa_set_pub_key,
 390         .max_size = rsa_max_size,
 391         .exit = rsa_exit_tfm,
 392         .base = {
 393                 .cra_name = "rsa",
 394                 .cra_driver_name = "rsa-generic",
 395                 .cra_priority = 100,
 396                 .cra_module = THIS_MODULE,
 397                 .cra_ctxsize = sizeof(struct rsa_mpi_key),
 398         },
 399 };
 400
 401 static int __init rsa_init(void)
 402 {
 403         int err;
 404
 405         err = crypto_register_akcipher(&rsa);
 406         if (err)
 407                 return err;
 408
 409         err = crypto_register_template(&rsa_pkcs1pad_tmpl);
 410         if (err)
 411                 goto err_unregister_rsa;
 412
 413         err = crypto_register_template(&rsassa_pkcs1_tmpl);
 414         if (err)
 415                 goto err_unregister_rsa_pkcs1pad;
 416
 417         return 0;
 418
 419 err_unregister_rsa_pkcs1pad:
 420         crypto_unregister_template(&rsa_pkcs1pad_tmpl);
 421 err_unregister_rsa:
 422         crypto_unregister_akcipher(&rsa);
 423         return err;
 424 }
 425
 426 static void __exit rsa_exit(void)
 427 {
 428         crypto_unregister_template(&rsassa_pkcs1_tmpl);
 429         crypto_unregister_template(&rsa_pkcs1pad_tmpl);
 430         crypto_unregister_akcipher(&rsa);
 431 }
 432
 433 subsys_initcall(rsa_init);
 434 module_exit(rsa_exit);
 435 MODULE_ALIAS_CRYPTO("rsa");
 436 MODULE_LICENSE("GPL");
 437 MODULE_DESCRIPTION("RSA generic algorithm");