Line data Source code
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 : Libgcrypt is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU Lesser General Public License as
9 : published by the Free Software Foundation; either version 2.1 of
10 : the License, or (at your option) any later version.
11 :
12 : Libgcrypt is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU Lesser General Public License for more details.
16 :
17 : You should have received a copy of the GNU Lesser General Public
18 : License along with this program; if not, write to the Free Software
19 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 : USA. */
21 :
22 :
23 : #include <config.h>
24 : #include <stdio.h>
25 : #include <stdlib.h>
26 :
27 : #include "mpi-internal.h"
28 : #include "longlong.h"
29 : #include "g10lib.h"
30 :
31 :
32 : /* Context used with Barrett reduction. */
33 : struct barrett_ctx_s
34 : {
35 : gcry_mpi_t m; /* The modulus - may not be modified. */
36 : int m_copied; /* If true, M needs to be released. */
37 : int k;
38 : gcry_mpi_t y;
39 : gcry_mpi_t r1; /* Helper MPI. */
40 : gcry_mpi_t r2; /* Helper MPI. */
41 : gcry_mpi_t r3; /* Helper MPI allocated on demand. */
42 : };
43 :
44 :
45 :
46 : void
47 0 : _gcry_mpi_mod (gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor)
48 : {
49 0 : _gcry_mpi_fdiv_r (rem, dividend, divisor);
50 0 : }
51 :
52 :
53 : /* This function returns a new context for Barrett based operations on
54 : the modulus M. This context needs to be released using
55 : _gcry_mpi_barrett_free. If COPY is true M will be transferred to
56 : the context and the user may change M. If COPY is false, M may not
57 : be changed until gcry_mpi_barrett_free has been called. */
58 : mpi_barrett_t
59 0 : _gcry_mpi_barrett_init (gcry_mpi_t m, int copy)
60 : {
61 : mpi_barrett_t ctx;
62 : gcry_mpi_t tmp;
63 :
64 0 : mpi_normalize (m);
65 0 : ctx = xcalloc (1, sizeof *ctx);
66 :
67 0 : if (copy)
68 : {
69 0 : ctx->m = mpi_copy (m);
70 0 : ctx->m_copied = 1;
71 : }
72 : else
73 0 : ctx->m = m;
74 :
75 0 : ctx->k = mpi_get_nlimbs (m);
76 0 : tmp = mpi_alloc (ctx->k + 1);
77 :
78 : /* Barrett precalculation: y = floor(b^(2k) / m). */
79 0 : mpi_set_ui (tmp, 1);
80 0 : mpi_lshift_limbs (tmp, 2 * ctx->k);
81 0 : mpi_fdiv_q (tmp, tmp, m);
82 :
83 0 : ctx->y = tmp;
84 0 : ctx->r1 = mpi_alloc ( 2 * ctx->k + 1 );
85 0 : ctx->r2 = mpi_alloc ( 2 * ctx->k + 1 );
86 :
87 0 : return ctx;
88 : }
89 :
90 : void
91 0 : _gcry_mpi_barrett_free (mpi_barrett_t ctx)
92 : {
93 0 : if (ctx)
94 : {
95 0 : mpi_free (ctx->y);
96 0 : mpi_free (ctx->r1);
97 0 : mpi_free (ctx->r2);
98 0 : if (ctx->r3)
99 0 : mpi_free (ctx->r3);
100 0 : if (ctx->m_copied)
101 0 : mpi_free (ctx->m);
102 0 : xfree (ctx);
103 : }
104 0 : }
105 :
106 :
107 : /* R = X mod M
108 :
109 : Using Barrett reduction. Before using this function
110 : _gcry_mpi_barrett_init must have been called to do the
111 : precalculations. CTX is the context created by this precalculation
112 : and also conveys M. If the Barret reduction could no be done a
113 : straightforward reduction method is used.
114 :
115 : We assume that these conditions are met:
116 : Input: x =(x_2k-1 ...x_0)_b
117 : m =(m_k-1 ....m_0)_b with m_k-1 != 0
118 : Output: r = x mod m
119 : */
120 : void
121 0 : _gcry_mpi_mod_barrett (gcry_mpi_t r, gcry_mpi_t x, mpi_barrett_t ctx)
122 : {
123 0 : gcry_mpi_t m = ctx->m;
124 0 : int k = ctx->k;
125 0 : gcry_mpi_t y = ctx->y;
126 0 : gcry_mpi_t r1 = ctx->r1;
127 0 : gcry_mpi_t r2 = ctx->r2;
128 : int sign;
129 :
130 0 : mpi_normalize (x);
131 0 : if (mpi_get_nlimbs (x) > 2*k )
132 : {
133 0 : mpi_mod (r, x, m);
134 0 : return;
135 : }
136 :
137 0 : sign = x->sign;
138 0 : x->sign = 0;
139 :
140 : /* 1. q1 = floor( x / b^k-1)
141 : * q2 = q1 * y
142 : * q3 = floor( q2 / b^k+1 )
143 : * Actually, we don't need qx, we can work direct on r2
144 : */
145 0 : mpi_set ( r2, x );
146 0 : mpi_rshift_limbs ( r2, k-1 );
147 0 : mpi_mul ( r2, r2, y );
148 0 : mpi_rshift_limbs ( r2, k+1 );
149 :
150 : /* 2. r1 = x mod b^k+1
151 : * r2 = q3 * m mod b^k+1
152 : * r = r1 - r2
153 : * 3. if r < 0 then r = r + b^k+1
154 : */
155 0 : mpi_set ( r1, x );
156 0 : if ( r1->nlimbs > k+1 ) /* Quick modulo operation. */
157 0 : r1->nlimbs = k+1;
158 0 : mpi_mul ( r2, r2, m );
159 0 : if ( r2->nlimbs > k+1 ) /* Quick modulo operation. */
160 0 : r2->nlimbs = k+1;
161 0 : mpi_sub ( r, r1, r2 );
162 :
163 0 : if ( mpi_has_sign ( r ) )
164 : {
165 0 : if (!ctx->r3)
166 : {
167 0 : ctx->r3 = mpi_alloc ( k + 2 );
168 0 : mpi_set_ui (ctx->r3, 1);
169 0 : mpi_lshift_limbs (ctx->r3, k + 1 );
170 : }
171 0 : mpi_add ( r, r, ctx->r3 );
172 : }
173 :
174 : /* 4. while r >= m do r = r - m */
175 0 : while ( mpi_cmp( r, m ) >= 0 )
176 0 : mpi_sub ( r, r, m );
177 :
178 0 : x->sign = sign;
179 : }
180 :
181 :
182 : void
183 0 : _gcry_mpi_mul_barrett (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v,
184 : mpi_barrett_t ctx)
185 : {
186 0 : mpi_mul (w, u, v);
187 0 : mpi_mod_barrett (w, w, ctx);
188 0 : }
|
