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	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
 67void 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 */
 95void 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
153void 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}