lib/mpi/mpi-mod.c

   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 }