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 | |
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 | */ |
36 | mpi_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 | |
67 | void 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 | */ |
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(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 | |
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(r: w, x: w, ctx); |
157 | } |
158 | |