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(a: m);
42 ctx = kcalloc(n: 1, size: sizeof(*ctx), GFP_KERNEL);
43 if (!ctx)
44 return NULL;
45
46 if (copy) {
47 ctx->m = mpi_copy(a: m);
48 ctx->m_copied = 1;
49 } else
50 ctx->m = m;
51
52 ctx->k = mpi_get_nlimbs(m);
53 tmp = mpi_alloc(nlimbs: ctx->k + 1);
54
55 /* Barrett precalculation: y = floor(b^(2k) / m). */
56 mpi_set_ui(w: tmp, u: 1);
57 mpi_lshift_limbs(a: tmp, count: 2 * ctx->k);
58 mpi_fdiv_q(quot: tmp, dividend: tmp, divisor: m);
59
60 ctx->y = tmp;
61 ctx->r1 = mpi_alloc(nlimbs: 2 * ctx->k + 1);
62 ctx->r2 = mpi_alloc(nlimbs: 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(a: ctx->y);
71 mpi_free(a: ctx->r1);
72 mpi_free(a: ctx->r2);
73 if (ctx->r3)
74 mpi_free(a: ctx->r3);
75 if (ctx->m_copied)
76 mpi_free(a: ctx->m);
77 kfree(objp: 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(a: x);
105 if (mpi_get_nlimbs(x) > 2*k) {
106 mpi_mod(rem: r, dividend: x, divisor: 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(w: r2, u: x);
119 mpi_rshift_limbs(a: r2, count: k-1);
120 mpi_mul(w: r2, u: r2, v: y);
121 mpi_rshift_limbs(a: r2, count: 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(w: r1, u: x);
129 if (r1->nlimbs > k+1) /* Quick modulo operation. */
130 r1->nlimbs = k+1;
131 mpi_mul(w: r2, u: r2, v: m);
132 if (r2->nlimbs > k+1) /* Quick modulo operation. */
133 r2->nlimbs = k+1;
134 mpi_sub(w: r, u: r1, v: r2);
135
136 if (mpi_has_sign(r)) {
137 if (!ctx->r3) {
138 ctx->r3 = mpi_alloc(nlimbs: k + 2);
139 mpi_set_ui(w: ctx->r3, u: 1);
140 mpi_lshift_limbs(a: ctx->r3, count: k + 1);
141 }
142 mpi_add(w: r, u: r, v: ctx->r3);
143 }
144
145 /* 4. while r >= m do r = r - m */
146 while (mpi_cmp(u: r, v: m) >= 0)
147 mpi_sub(w: r, u: r, v: 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(r: w, x: w, ctx);
157}
158

source code of linux/lib/crypto/mpi/mpi-mod.c