lib/mpi/mpi-mod.c

0001 /* mpi-mod.c -  Modular reduction
0002  * Copyright (C) 1998, 1999, 2001, 2002, 2003,
0003  *               2007  Free Software Foundation, Inc.
0004  *
0005  * This file is part of Libgcrypt.
0006  */
0007
0008
0009 #include "mpi-internal.h"
0010 #include "longlong.h"
0011
0012 /* Context used with Barrett reduction.  */
0013 struct barrett_ctx_s {
0014     MPI m;   /* The modulus - may not be modified. */
0015     int m_copied;   /* If true, M needs to be released.  */
0016     int k;
0017     MPI y;
0018     MPI r1;  /* Helper MPI. */
0019     MPI r2;  /* Helper MPI. */
0020     MPI r3;  /* Helper MPI allocated on demand. */
0021 };
0022
0023
0024
0025 void mpi_mod(MPI rem, MPI dividend, MPI divisor)
0026 {
0027     mpi_fdiv_r(rem, dividend, divisor);
0028 }
0029
0030 /* This function returns a new context for Barrett based operations on
0031  * the modulus M.  This context needs to be released using
0032  * _gcry_mpi_barrett_free.  If COPY is true M will be transferred to
0033  * the context and the user may change M.  If COPY is false, M may not
0034  * be changed until gcry_mpi_barrett_free has been called.
0035  */
0036 mpi_barrett_t mpi_barrett_init(MPI m, int copy)
0037 {
0038     mpi_barrett_t ctx;
0039     MPI tmp;
0040
0041     mpi_normalize(m);
0042     ctx = kcalloc(1, sizeof(*ctx), GFP_KERNEL);
0043     if (!ctx)
0044         return NULL;
0045
0046     if (copy) {
0047         ctx->m = mpi_copy(m);
0048         ctx->m_copied = 1;
0049     } else
0050         ctx->m = m;
0051
0052     ctx->k = mpi_get_nlimbs(m);
0053     tmp = mpi_alloc(ctx->k + 1);
0054
0055     /* Barrett precalculation: y = floor(b^(2k) / m). */
0056     mpi_set_ui(tmp, 1);
0057     mpi_lshift_limbs(tmp, 2 * ctx->k);
0058     mpi_fdiv_q(tmp, tmp, m);
0059
0060     ctx->y  = tmp;
0061     ctx->r1 = mpi_alloc(2 * ctx->k + 1);
0062     ctx->r2 = mpi_alloc(2 * ctx->k + 1);
0063
0064     return ctx;
0065 }
0066
0067 void mpi_barrett_free(mpi_barrett_t ctx)
0068 {
0069     if (ctx) {
0070         mpi_free(ctx->y);
0071         mpi_free(ctx->r1);
0072         mpi_free(ctx->r2);
0073         if (ctx->r3)
0074             mpi_free(ctx->r3);
0075         if (ctx->m_copied)
0076             mpi_free(ctx->m);
0077         kfree(ctx);
0078     }
0079 }
0080
0081
0082 /* R = X mod M
0083  *
0084  * Using Barrett reduction.  Before using this function
0085  * _gcry_mpi_barrett_init must have been called to do the
0086  * precalculations.  CTX is the context created by this precalculation
0087  * and also conveys M.  If the Barret reduction could no be done a
0088  * straightforward reduction method is used.
0089  *
0090  * We assume that these conditions are met:
0091  * Input:  x =(x_2k-1 ...x_0)_b
0092  *     m =(m_k-1 ....m_0)_b   with m_k-1 != 0
0093  * Output: r = x mod m
0094  */
0095 void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx)
0096 {
0097     MPI m = ctx->m;
0098     int k = ctx->k;
0099     MPI y = ctx->y;
0100     MPI r1 = ctx->r1;
0101     MPI r2 = ctx->r2;
0102     int sign;
0103
0104     mpi_normalize(x);
0105     if (mpi_get_nlimbs(x) > 2*k) {
0106         mpi_mod(r, x, m);
0107         return;
0108     }
0109
0110     sign = x->sign;
0111     x->sign = 0;
0112
0113     /* 1. q1 = floor( x / b^k-1)
0114      *    q2 = q1 * y
0115      *    q3 = floor( q2 / b^k+1 )
0116      * Actually, we don't need qx, we can work direct on r2
0117      */
0118     mpi_set(r2, x);
0119     mpi_rshift_limbs(r2, k-1);
0120     mpi_mul(r2, r2, y);
0121     mpi_rshift_limbs(r2, k+1);
0122
0123     /* 2. r1 = x mod b^k+1
0124      *  r2 = q3 * m mod b^k+1
0125      *  r  = r1 - r2
0126      * 3. if r < 0 then  r = r + b^k+1
0127      */
0128     mpi_set(r1, x);
0129     if (r1->nlimbs > k+1) /* Quick modulo operation.  */
0130         r1->nlimbs = k+1;
0131     mpi_mul(r2, r2, m);
0132     if (r2->nlimbs > k+1) /* Quick modulo operation. */
0133         r2->nlimbs = k+1;
0134     mpi_sub(r, r1, r2);
0135
0136     if (mpi_has_sign(r)) {
0137         if (!ctx->r3) {
0138             ctx->r3 = mpi_alloc(k + 2);
0139             mpi_set_ui(ctx->r3, 1);
0140             mpi_lshift_limbs(ctx->r3, k + 1);
0141         }
0142         mpi_add(r, r, ctx->r3);
0143     }
0144
0145     /* 4. while r >= m do r = r - m */
0146     while (mpi_cmp(r, m) >= 0)
0147         mpi_sub(r, r, m);
0148
0149     x->sign = sign;
0150 }
0151
0152
0153 void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx)
0154 {
0155     mpi_mul(w, u, v);
0156     mpi_mod_barrett(w, w, ctx);
0157 }