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 if (!ctx) 44 return NULL; 45 46 if (copy) { 47 ctx->m = mpi_copy(m); 48 ctx->m_copied = 1; 49 } else 50 ctx->m = m; 51 52 ctx->k = mpi_get_nlimbs(m); 53 tmp = mpi_alloc(ctx->k + 1); 54 55 /* Barrett precalculation: y = floor(b^(2k) / m). */ 56 mpi_set_ui(tmp, 1); 57 mpi_lshift_limbs(tmp, 2 * ctx->k); 58 mpi_fdiv_q(tmp, tmp, m); 59 60 ctx->y = tmp; 61 ctx->r1 = mpi_alloc(2 * ctx->k + 1); 62 ctx->r2 = mpi_alloc(2 * ctx->k + 1); 63 64 return ctx; 65 } 66 67 void mpi_barrett_free(mpi_barrett_t ctx) 68 { 69 if (ctx) { 70 mpi_free(ctx->y); 71 mpi_free(ctx->r1); 72 mpi_free(ctx->r2); 73 if (ctx->r3) 74 mpi_free(ctx->r3); 75 if (ctx->m_copied) 76 mpi_free(ctx->m); 77 kfree(ctx); 78 } 79 } 80 81 82 /* R = X mod M 83 * 84 * Using Barrett reduction. Before using this function 85 * _gcry_mpi_barrett_init must have been called to do the 86 * precalculations. CTX is the context created by this precalculation 87 * and also conveys M. If the Barret reduction could no be done a 88 * straightforward reduction method is used. 89 * 90 * We assume that these conditions are met: 91 * Input: x =(x_2k-1 ...x_0)_b 92 * m =(m_k-1 ....m_0)_b with m_k-1 != 0 93 * Output: r = x mod m 94 */ 95 void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx) 96 { 97 MPI m = ctx->m; 98 int k = ctx->k; 99 MPI y = ctx->y; 100 MPI r1 = ctx->r1; 101 MPI r2 = ctx->r2; 102 int sign; 103 104 mpi_normalize(x); 105 if (mpi_get_nlimbs(x) > 2*k) { 106 mpi_mod(r, x, m); 107 return; 108 } 109 110 sign = x->sign; 111 x->sign = 0; 112 113 /* 1. q1 = floor( x / b^k-1) 114 * q2 = q1 * y 115 * q3 = floor( q2 / b^k+1 ) 116 * Actually, we don't need qx, we can work direct on r2 117 */ 118 mpi_set(r2, x); 119 mpi_rshift_limbs(r2, k-1); 120 mpi_mul(r2, r2, y); 121 mpi_rshift_limbs(r2, k+1); 122 123 /* 2. r1 = x mod b^k+1 124 * r2 = q3 * m mod b^k+1 125 * r = r1 - r2 126 * 3. if r < 0 then r = r + b^k+1 127 */ 128 mpi_set(r1, x); 129 if (r1->nlimbs > k+1) /* Quick modulo operation. */ 130 r1->nlimbs = k+1; 131 mpi_mul(r2, r2, m); 132 if (r2->nlimbs > k+1) /* Quick modulo operation. */ 133 r2->nlimbs = k+1; 134 mpi_sub(r, r1, r2); 135 136 if (mpi_has_sign(r)) { 137 if (!ctx->r3) { 138 ctx->r3 = mpi_alloc(k + 2); 139 mpi_set_ui(ctx->r3, 1); 140 mpi_lshift_limbs(ctx->r3, k + 1); 141 } 142 mpi_add(r, r, ctx->r3); 143 } 144 145 /* 4. while r >= m do r = r - m */ 146 while (mpi_cmp(r, m) >= 0) 147 mpi_sub(r, r, m); 148 149 x->sign = sign; 150 } 151 152 153 void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx) 154 { 155 mpi_mul(w, u, v); 156 mpi_mod_barrett(w, w, ctx); 157 } 158