1 /*
2 * pgp-mpi-internal.c
3 * OpenPGP MPI functions.
4 *
5 * Copyright (c) 2005 Marko Kreen
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 * contrib/pgcrypto/pgp-mpi-internal.c
30 */
31 #include "postgres.h"
32
33 #include "imath.h"
34
35 #include "px.h"
36 #include "pgp.h"
37
38 static mpz_t *
mp_new()39 mp_new()
40 {
41 mpz_t *mp = mp_int_alloc();
42
43 mp_int_init_size(mp, 256);
44 return mp;
45 }
46
47 static void
mp_clear_free(mpz_t * a)48 mp_clear_free(mpz_t *a)
49 {
50 if (!a)
51 return;
52 /* fixme: no clear? */
53 mp_int_free(a);
54 }
55
56
57 static int
mp_px_rand(uint32 bits,mpz_t * res)58 mp_px_rand(uint32 bits, mpz_t *res)
59 {
60 #ifdef HAVE_STRONG_RANDOM
61 unsigned bytes = (bits + 7) / 8;
62 int last_bits = bits & 7;
63 uint8 *buf;
64
65 buf = px_alloc(bytes);
66 if (!pg_strong_random((char *) buf, bytes))
67 {
68 px_free(buf);
69 return PXE_NO_RANDOM;
70 }
71
72 /* clear unnecessary bits and set last bit to one */
73 if (last_bits)
74 {
75 buf[0] >>= 8 - last_bits;
76 buf[0] |= 1 << (last_bits - 1);
77 }
78 else
79 buf[0] |= 1 << 7;
80
81 mp_int_read_unsigned(res, buf, bytes);
82
83 px_free(buf);
84
85 return 0;
86 #else
87 return PXE_NO_RANDOM;
88 #endif
89 }
90
91 static void
mp_modmul(mpz_t * a,mpz_t * b,mpz_t * p,mpz_t * res)92 mp_modmul(mpz_t *a, mpz_t *b, mpz_t *p, mpz_t *res)
93 {
94 mpz_t *tmp = mp_new();
95
96 mp_int_mul(a, b, tmp);
97 mp_int_mod(tmp, p, res);
98 mp_clear_free(tmp);
99 }
100
101 static mpz_t *
mpi_to_bn(PGP_MPI * n)102 mpi_to_bn(PGP_MPI *n)
103 {
104 mpz_t *bn = mp_new();
105
106 mp_int_read_unsigned(bn, n->data, n->bytes);
107
108 if (!bn)
109 return NULL;
110 if (mp_int_count_bits(bn) != n->bits)
111 {
112 px_debug("mpi_to_bn: bignum conversion failed: mpi=%d, bn=%d",
113 n->bits, mp_int_count_bits(bn));
114 mp_clear_free(bn);
115 return NULL;
116 }
117 return bn;
118 }
119
120 static PGP_MPI *
bn_to_mpi(mpz_t * bn)121 bn_to_mpi(mpz_t *bn)
122 {
123 int res;
124 PGP_MPI *n;
125 int bytes;
126
127 res = pgp_mpi_alloc(mp_int_count_bits(bn), &n);
128 if (res < 0)
129 return NULL;
130
131 bytes = (mp_int_count_bits(bn) + 7) / 8;
132 if (bytes != n->bytes)
133 {
134 px_debug("bn_to_mpi: bignum conversion failed: bn=%d, mpi=%d",
135 bytes, n->bytes);
136 pgp_mpi_free(n);
137 return NULL;
138 }
139 mp_int_to_unsigned(bn, n->data, n->bytes);
140 return n;
141 }
142
143 /*
144 * Decide the number of bits in the random component k
145 *
146 * It should be in the same range as p for signing (which
147 * is deprecated), but can be much smaller for encrypting.
148 *
149 * Until I research it further, I just mimic gpg behaviour.
150 * It has a special mapping table, for values <= 5120,
151 * above that it uses 'arbitrary high number'. Following
152 * algorithm hovers 10-70 bits above gpg values. And for
153 * larger p, it uses gpg's algorithm.
154 *
155 * The point is - if k gets large, encryption will be
156 * really slow. It does not matter for decryption.
157 */
158 static int
decide_k_bits(int p_bits)159 decide_k_bits(int p_bits)
160 {
161 if (p_bits <= 5120)
162 return p_bits / 10 + 160;
163 else
164 return (p_bits / 8 + 200) * 3 / 2;
165 }
166
167 int
pgp_elgamal_encrypt(PGP_PubKey * pk,PGP_MPI * _m,PGP_MPI ** c1_p,PGP_MPI ** c2_p)168 pgp_elgamal_encrypt(PGP_PubKey *pk, PGP_MPI *_m,
169 PGP_MPI **c1_p, PGP_MPI **c2_p)
170 {
171 int res = PXE_PGP_MATH_FAILED;
172 int k_bits;
173 mpz_t *m = mpi_to_bn(_m);
174 mpz_t *p = mpi_to_bn(pk->pub.elg.p);
175 mpz_t *g = mpi_to_bn(pk->pub.elg.g);
176 mpz_t *y = mpi_to_bn(pk->pub.elg.y);
177 mpz_t *k = mp_new();
178 mpz_t *yk = mp_new();
179 mpz_t *c1 = mp_new();
180 mpz_t *c2 = mp_new();
181
182 if (!m || !p || !g || !y || !k || !yk || !c1 || !c2)
183 goto err;
184
185 /*
186 * generate k
187 */
188 k_bits = decide_k_bits(mp_int_count_bits(p));
189 res = mp_px_rand(k_bits, k);
190 if (res < 0)
191 return res;
192
193 /*
194 * c1 = g^k c2 = m * y^k
195 */
196 mp_int_exptmod(g, k, p, c1);
197 mp_int_exptmod(y, k, p, yk);
198 mp_modmul(m, yk, p, c2);
199
200 /* result */
201 *c1_p = bn_to_mpi(c1);
202 *c2_p = bn_to_mpi(c2);
203 if (*c1_p && *c2_p)
204 res = 0;
205 err:
206 mp_clear_free(c2);
207 mp_clear_free(c1);
208 mp_clear_free(yk);
209 mp_clear_free(k);
210 mp_clear_free(y);
211 mp_clear_free(g);
212 mp_clear_free(p);
213 mp_clear_free(m);
214 return res;
215 }
216
217 int
pgp_elgamal_decrypt(PGP_PubKey * pk,PGP_MPI * _c1,PGP_MPI * _c2,PGP_MPI ** msg_p)218 pgp_elgamal_decrypt(PGP_PubKey *pk, PGP_MPI *_c1, PGP_MPI *_c2,
219 PGP_MPI **msg_p)
220 {
221 int res = PXE_PGP_MATH_FAILED;
222 mpz_t *c1 = mpi_to_bn(_c1);
223 mpz_t *c2 = mpi_to_bn(_c2);
224 mpz_t *p = mpi_to_bn(pk->pub.elg.p);
225 mpz_t *x = mpi_to_bn(pk->sec.elg.x);
226 mpz_t *c1x = mp_new();
227 mpz_t *div = mp_new();
228 mpz_t *m = mp_new();
229
230 if (!c1 || !c2 || !p || !x || !c1x || !div || !m)
231 goto err;
232
233 /*
234 * m = c2 / (c1^x)
235 */
236 mp_int_exptmod(c1, x, p, c1x);
237 mp_int_invmod(c1x, p, div);
238 mp_modmul(c2, div, p, m);
239
240 /* result */
241 *msg_p = bn_to_mpi(m);
242 if (*msg_p)
243 res = 0;
244 err:
245 mp_clear_free(m);
246 mp_clear_free(div);
247 mp_clear_free(c1x);
248 mp_clear_free(x);
249 mp_clear_free(p);
250 mp_clear_free(c2);
251 mp_clear_free(c1);
252 return res;
253 }
254
255 int
pgp_rsa_encrypt(PGP_PubKey * pk,PGP_MPI * _m,PGP_MPI ** c_p)256 pgp_rsa_encrypt(PGP_PubKey *pk, PGP_MPI *_m, PGP_MPI **c_p)
257 {
258 int res = PXE_PGP_MATH_FAILED;
259 mpz_t *m = mpi_to_bn(_m);
260 mpz_t *e = mpi_to_bn(pk->pub.rsa.e);
261 mpz_t *n = mpi_to_bn(pk->pub.rsa.n);
262 mpz_t *c = mp_new();
263
264 if (!m || !e || !n || !c)
265 goto err;
266
267 /*
268 * c = m ^ e
269 */
270 mp_int_exptmod(m, e, n, c);
271
272 *c_p = bn_to_mpi(c);
273 if (*c_p)
274 res = 0;
275 err:
276 mp_clear_free(c);
277 mp_clear_free(n);
278 mp_clear_free(e);
279 mp_clear_free(m);
280 return res;
281 }
282
283 int
pgp_rsa_decrypt(PGP_PubKey * pk,PGP_MPI * _c,PGP_MPI ** m_p)284 pgp_rsa_decrypt(PGP_PubKey *pk, PGP_MPI *_c, PGP_MPI **m_p)
285 {
286 int res = PXE_PGP_MATH_FAILED;
287 mpz_t *c = mpi_to_bn(_c);
288 mpz_t *d = mpi_to_bn(pk->sec.rsa.d);
289 mpz_t *n = mpi_to_bn(pk->pub.rsa.n);
290 mpz_t *m = mp_new();
291
292 if (!m || !d || !n || !c)
293 goto err;
294
295 /*
296 * m = c ^ d
297 */
298 mp_int_exptmod(c, d, n, m);
299
300 *m_p = bn_to_mpi(m);
301 if (*m_p)
302 res = 0;
303 err:
304 mp_clear_free(m);
305 mp_clear_free(n);
306 mp_clear_free(d);
307 mp_clear_free(c);
308 return res;
309 }
310