Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 1 | /* mpi-mul.c - MPI functions |
| 2 | * Copyright (C) 1994, 1996, 1998, 2001, 2002, |
| 3 | * 2003 Free Software Foundation, Inc. |
| 4 | * |
| 5 | * This file is part of Libgcrypt. |
| 6 | * |
| 7 | * Note: This code is heavily based on the GNU MP Library. |
| 8 | * Actually it's the same code with only minor changes in the |
| 9 | * way the data is stored; this is to support the abstraction |
| 10 | * of an optional secure memory allocation which may be used |
| 11 | * to avoid revealing of sensitive data due to paging etc. |
| 12 | */ |
| 13 | |
| 14 | #include "mpi-internal.h" |
| 15 | |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 16 | int mpi_mul(MPI w, MPI u, MPI v) |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 17 | { |
| 18 | mpi_size_t usize, vsize, wsize; |
| 19 | mpi_ptr_t up, vp, wp; |
| 20 | mpi_limb_t cy; |
| 21 | int usign, vsign, sign_product; |
| 22 | int assign_wp = 0; |
| 23 | mpi_ptr_t tmp_limb = NULL; |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 24 | int err; |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 25 | |
| 26 | if (u->nlimbs < v->nlimbs) { |
| 27 | /* Swap U and V. */ |
| 28 | usize = v->nlimbs; |
| 29 | usign = v->sign; |
| 30 | up = v->d; |
| 31 | vsize = u->nlimbs; |
| 32 | vsign = u->sign; |
| 33 | vp = u->d; |
| 34 | } else { |
| 35 | usize = u->nlimbs; |
| 36 | usign = u->sign; |
| 37 | up = u->d; |
| 38 | vsize = v->nlimbs; |
| 39 | vsign = v->sign; |
| 40 | vp = v->d; |
| 41 | } |
| 42 | sign_product = usign ^ vsign; |
| 43 | wp = w->d; |
| 44 | |
| 45 | /* Ensure W has space enough to store the result. */ |
| 46 | wsize = usize + vsize; |
| 47 | if (w->alloced < wsize) { |
| 48 | if (wp == up || wp == vp) { |
| 49 | wp = mpi_alloc_limb_space(wsize); |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 50 | if (!wp) |
| 51 | return -ENOMEM; |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 52 | assign_wp = 1; |
| 53 | } else { |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 54 | err = mpi_resize(w, wsize); |
| 55 | if (err) |
| 56 | return err; |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 57 | wp = w->d; |
| 58 | } |
| 59 | } else { /* Make U and V not overlap with W. */ |
| 60 | if (wp == up) { |
| 61 | /* W and U are identical. Allocate temporary space for U. */ |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 62 | up = tmp_limb = mpi_alloc_limb_space(usize); |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 63 | if (!up) |
| 64 | return -ENOMEM; |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 65 | /* Is V identical too? Keep it identical with U. */ |
| 66 | if (wp == vp) |
| 67 | vp = up; |
| 68 | /* Copy to the temporary space. */ |
| 69 | MPN_COPY(up, wp, usize); |
| 70 | } else if (wp == vp) { |
| 71 | /* W and V are identical. Allocate temporary space for V. */ |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 72 | vp = tmp_limb = mpi_alloc_limb_space(vsize); |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 73 | if (!vp) |
| 74 | return -ENOMEM; |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 75 | /* Copy to the temporary space. */ |
| 76 | MPN_COPY(vp, wp, vsize); |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | if (!vsize) |
| 81 | wsize = 0; |
| 82 | else { |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 83 | err = mpihelp_mul(wp, up, usize, vp, vsize, &cy); |
| 84 | if (err) { |
| 85 | if (assign_wp) |
| 86 | mpi_free_limb_space(wp); |
| 87 | goto free_tmp_limb; |
| 88 | } |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 89 | wsize -= cy ? 0:1; |
| 90 | } |
| 91 | |
| 92 | if (assign_wp) |
| 93 | mpi_assign_limb_space(w, wp, wsize); |
| 94 | w->nlimbs = wsize; |
| 95 | w->sign = sign_product; |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 96 | |
| 97 | free_tmp_limb: |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 98 | if (tmp_limb) |
| 99 | mpi_free_limb_space(tmp_limb); |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 100 | return err; |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 101 | } |
Ignat Korchagin | f145d41 | 2022-06-17 09:42:10 +0100 | [diff] [blame] | 102 | EXPORT_SYMBOL_GPL(mpi_mul); |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 103 | |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 104 | int mpi_mulm(MPI w, MPI u, MPI v, MPI m) |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 105 | { |
Herbert Xu | 8e3a67f | 2024-08-10 14:20:57 +0800 | [diff] [blame] | 106 | return mpi_mul(w, u, v) ?: |
| 107 | mpi_tdiv_r(w, w, m); |
Tianjia Zhang | a8ea8bd | 2020-09-21 00:20:55 +0800 | [diff] [blame] | 108 | } |
| 109 | EXPORT_SYMBOL_GPL(mpi_mulm); |