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 
mpi_mod(MPI rem,MPI dividend,MPI divisor)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  */
mpi_barrett_init(MPI m,int copy)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 
mpi_barrett_free(mpi_barrett_t ctx)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  */
mpi_mod_barrett(MPI r,MPI x,mpi_barrett_t ctx)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 
mpi_mul_barrett(MPI w,MPI u,MPI v,mpi_barrett_t ctx)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