projects / mirror_ubuntu-jammy-kernel.git / blame
| Commit | Line | Data |
|---|---|---|
| a8ea8bdd TZ |
1 | /* mpi-mod.c - Modular reduction |
| 2 | * Copyright (C) 1998, 1999, 2001, 2002, 2003, | |
| 3 | * 2007 Free Software Foundation, Inc. | |
| 4 | * | |
| 5 | * This file is part of Libgcrypt. | |
| 6 | */ | |
| 7 | ||
| 8 | ||
| 9 | #include "mpi-internal.h" | |
| 10 | #include "longlong.h" | |
| 11 | ||
| 12 | /* Context used with Barrett reduction. */ | |
| 13 | struct barrett_ctx_s { | |
| 14 | MPI m; /* The modulus - may not be modified. */ | |
| 15 | int m_copied; /* If true, M needs to be released. */ | |
| 16 | int k; | |
| 17 | MPI y; | |
| 18 | MPI r1; /* Helper MPI. */ | |
| 19 | MPI r2; /* Helper MPI. */ | |
| 20 | MPI r3; /* Helper MPI allocated on demand. */ | |
| 21 | }; | |
| 22 | ||
| 23 | ||
| 24 | ||
| 25 | void mpi_mod(MPI rem, MPI dividend, MPI divisor) | |
| 26 | { | |
| 27 | mpi_fdiv_r(rem, dividend, divisor); | |
| 28 | } | |
| 29 | ||
| 30 | /* This function returns a new context for Barrett based operations on | |
| 31 | * the modulus M. This context needs to be released using | |
| 32 | * _gcry_mpi_barrett_free. If COPY is true M will be transferred to | |
| 33 | * the context and the user may change M. If COPY is false, M may not | |
| 34 | * be changed until gcry_mpi_barrett_free has been called. | |
| 35 | */ | |
| 36 | mpi_barrett_t mpi_barrett_init(MPI m, int copy) | |
| 37 | { | |
| 38 | mpi_barrett_t ctx; | |
| 39 | MPI tmp; | |
| 40 | ||
| 41 | mpi_normalize(m); | |
| 42 | ctx = kcalloc(1, sizeof(*ctx), GFP_KERNEL); | |
| 43 | ||
| 44 | if (copy) { | |
| 45 | ctx->m = mpi_copy(m); | |
| 46 | ctx->m_copied = 1; | |
| 47 | } else | |
| 48 | ctx->m = m; | |
| 49 | ||
| 50 | ctx->k = mpi_get_nlimbs(m); | |
| 51 | tmp = mpi_alloc(ctx->k + 1); | |
| 52 | ||
| 53 | /* Barrett precalculation: y = floor(b^(2k) / m). */ | |
| 54 | mpi_set_ui(tmp, 1); | |
| 55 | mpi_lshift_limbs(tmp, 2 * ctx->k); | |
| 56 | mpi_fdiv_q(tmp, tmp, m); | |
| 57 | ||
| 58 | ctx->y = tmp; | |
| 59 | ctx->r1 = mpi_alloc(2 * ctx->k + 1); | |
| 60 | ctx->r2 = mpi_alloc(2 * ctx->k + 1); | |
| 61 | ||
| 62 | return ctx; | |
| 63 | } | |
| 64 | ||
| 65 | void mpi_barrett_free(mpi_barrett_t ctx) | |
| 66 | { | |
| 67 | if (ctx) { | |
| 68 | mpi_free(ctx->y); | |
| 69 | mpi_free(ctx->r1); | |
| 70 | mpi_free(ctx->r2); | |
| 71 | if (ctx->r3) | |
| 72 | mpi_free(ctx->r3); | |
| 73 | if (ctx->m_copied) | |
| 74 | mpi_free(ctx->m); | |
| 75 | kfree(ctx); | |
| 76 | } | |
| 77 | } | |
| 78 | ||
| 79 | ||
| 80 | /* R = X mod M | |
| 81 | * | |
| 82 | * Using Barrett reduction. Before using this function | |
| 83 | * _gcry_mpi_barrett_init must have been called to do the | |
| 84 | * precalculations. CTX is the context created by this precalculation | |
| 85 | * and also conveys M. If the Barret reduction could no be done a | |
| 86 | * straightforward reduction method is used. | |
| 87 | * | |
| 88 | * We assume that these conditions are met: | |
| 89 | * Input: x =(x_2k-1 ...x_0)_b | |
| 90 | * m =(m_k-1 ....m_0)_b with m_k-1 != 0 | |
| 91 | * Output: r = x mod m | |
| 92 | */ | |
| 93 | void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx) | |
| 94 | { | |
| 95 | MPI m = ctx->m; | |
| 96 | int k = ctx->k; | |
| 97 | MPI y = ctx->y; | |
| 98 | MPI r1 = ctx->r1; | |
| 99 | MPI r2 = ctx->r2; | |
| 100 | int sign; | |
| 101 | ||
| 102 | mpi_normalize(x); | |
| 103 | if (mpi_get_nlimbs(x) > 2*k) { | |
| 104 | mpi_mod(r, x, m); | |
| 105 | return; | |
| 106 | } | |
| 107 | ||
| 108 | sign = x->sign; | |
| 109 | x->sign = 0; | |
| 110 | ||
| 111 | /* 1. q1 = floor( x / b^k-1) | |
| 112 | * q2 = q1 * y | |
| 113 | * q3 = floor( q2 / b^k+1 ) | |
| 114 | * Actually, we don't need qx, we can work direct on r2 | |
| 115 | */ | |
| 116 | mpi_set(r2, x); | |
| 117 | mpi_rshift_limbs(r2, k-1); | |
| 118 | mpi_mul(r2, r2, y); | |
| 119 | mpi_rshift_limbs(r2, k+1); | |
| 120 | ||
| 121 | /* 2. r1 = x mod b^k+1 | |
| 122 | * r2 = q3 * m mod b^k+1 | |
| 123 | * r = r1 - r2 | |
| 124 | * 3. if r < 0 then r = r + b^k+1 | |
| 125 | */ | |
| 126 | mpi_set(r1, x); | |
| 127 | if (r1->nlimbs > k+1) /* Quick modulo operation. */ | |
| 128 | r1->nlimbs = k+1; | |
| 129 | mpi_mul(r2, r2, m); | |
| 130 | if (r2->nlimbs > k+1) /* Quick modulo operation. */ | |
| 131 | r2->nlimbs = k+1; | |
| 132 | mpi_sub(r, r1, r2); | |
| 133 | ||
| 134 | if (mpi_has_sign(r)) { | |
| 135 | if (!ctx->r3) { | |
| 136 | ctx->r3 = mpi_alloc(k + 2); | |
| 137 | mpi_set_ui(ctx->r3, 1); | |
| 138 | mpi_lshift_limbs(ctx->r3, k + 1); | |
| 139 | } | |
| 140 | mpi_add(r, r, ctx->r3); | |
| 141 | } | |
| 142 | ||
| 143 | /* 4. while r >= m do r = r - m */ | |
| 144 | while (mpi_cmp(r, m) >= 0) | |
| 145 | mpi_sub(r, r, m); | |
| 146 | ||
| 147 | x->sign = sign; | |
| 148 | } | |
| 149 | ||
| 150 | ||
| 151 | void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx) | |
| 152 | { | |
| 153 | mpi_mul(w, u, v); | |
| 154 | mpi_mod_barrett(w, w, ctx); | |
| 155 | } |