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
44 if (copy) {
45 ctx->m = mpi_copy(m);
46 ctx->m_copied = 1;
47 } else
48 ctx->m = m;
49
50 ctx->k = mpi_get_nlimbs(m);
51 tmp = mpi_alloc(ctx->k + 1);
52
53 /* Barrett precalculation: y = floor(b^(2k) / m). */
54 mpi_set_ui(tmp, 1);
55 mpi_lshift_limbs(tmp, 2 * ctx->k);
56 mpi_fdiv_q(tmp, tmp, m);
57
58 ctx->y = tmp;
59 ctx->r1 = mpi_alloc(2 * ctx->k + 1);
60 ctx->r2 = mpi_alloc(2 * ctx->k + 1);
61
62 return ctx;
63 }
64
mpi_barrett_free(mpi_barrett_t ctx)65 void mpi_barrett_free(mpi_barrett_t ctx)
66 {
67 if (ctx) {
68 mpi_free(ctx->y);
69 mpi_free(ctx->r1);
70 mpi_free(ctx->r2);
71 if (ctx->r3)
72 mpi_free(ctx->r3);
73 if (ctx->m_copied)
74 mpi_free(ctx->m);
75 kfree(ctx);
76 }
77 }
78
79
80 /* R = X mod M
81 *
82 * Using Barrett reduction. Before using this function
83 * _gcry_mpi_barrett_init must have been called to do the
84 * precalculations. CTX is the context created by this precalculation
85 * and also conveys M. If the Barret reduction could no be done a
86 * straightforward reduction method is used.
87 *
88 * We assume that these conditions are met:
89 * Input: x =(x_2k-1 ...x_0)_b
90 * m =(m_k-1 ....m_0)_b with m_k-1 != 0
91 * Output: r = x mod m
92 */
mpi_mod_barrett(MPI r,MPI x,mpi_barrett_t ctx)93 void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx)
94 {
95 MPI m = ctx->m;
96 int k = ctx->k;
97 MPI y = ctx->y;
98 MPI r1 = ctx->r1;
99 MPI r2 = ctx->r2;
100 int sign;
101
102 mpi_normalize(x);
103 if (mpi_get_nlimbs(x) > 2*k) {
104 mpi_mod(r, x, m);
105 return;
106 }
107
108 sign = x->sign;
109 x->sign = 0;
110
111 /* 1. q1 = floor( x / b^k-1)
112 * q2 = q1 * y
113 * q3 = floor( q2 / b^k+1 )
114 * Actually, we don't need qx, we can work direct on r2
115 */
116 mpi_set(r2, x);
117 mpi_rshift_limbs(r2, k-1);
118 mpi_mul(r2, r2, y);
119 mpi_rshift_limbs(r2, k+1);
120
121 /* 2. r1 = x mod b^k+1
122 * r2 = q3 * m mod b^k+1
123 * r = r1 - r2
124 * 3. if r < 0 then r = r + b^k+1
125 */
126 mpi_set(r1, x);
127 if (r1->nlimbs > k+1) /* Quick modulo operation. */
128 r1->nlimbs = k+1;
129 mpi_mul(r2, r2, m);
130 if (r2->nlimbs > k+1) /* Quick modulo operation. */
131 r2->nlimbs = k+1;
132 mpi_sub(r, r1, r2);
133
134 if (mpi_has_sign(r)) {
135 if (!ctx->r3) {
136 ctx->r3 = mpi_alloc(k + 2);
137 mpi_set_ui(ctx->r3, 1);
138 mpi_lshift_limbs(ctx->r3, k + 1);
139 }
140 mpi_add(r, r, ctx->r3);
141 }
142
143 /* 4. while r >= m do r = r - m */
144 while (mpi_cmp(r, m) >= 0)
145 mpi_sub(r, r, m);
146
147 x->sign = sign;
148 }
149
150
mpi_mul_barrett(MPI w,MPI u,MPI v,mpi_barrett_t ctx)151 void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx)
152 {
153 mpi_mul(w, u, v);
154 mpi_mod_barrett(w, w, ctx);
155 }
156