LXR linux/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.  */
  13struct 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
  25void 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 */
  36mpi_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
  65void 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 */
  93void 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
 151void 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}
 156