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