contrib/pgcrypto/pgp-mpi-internal.c

   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  * $PostgreSQL$
  30  */
  31 #include "postgres.h"
  32
  33 #include "imath.h"
  34
  35 #include "px.h"
  36 #include "mbuf.h"
  37 #include "pgp.h"
  38
  39 static mpz_t *
  40 mp_new()
  41 {
  42         mpz_t      *mp = mp_int_alloc();
  43
  44         mp_int_init_size(mp, 256);
  45         return mp;
  46 }
  47
  48 static void
  49 mp_clear_free(mpz_t * a)
  50 {
  51         if (!a)
  52                 return;
  53         /* fixme: no clear? */
  54         mp_int_free(a);
  55 }
  56
  57
  58 static int
  59 mp_px_rand(uint32 bits, mpz_t * res)
  60 {
  61         int                     err;
  62         unsigned        bytes = (bits + 7) / 8;
  63         int                     last_bits = bits & 7;
  64         uint8      *buf;
  65
  66         buf = px_alloc(bytes);
  67         err = px_get_random_bytes(buf, bytes);
  68         if (err < 0)
  69         {
  70                 px_free(buf);
  71                 return err;
  72         }
  73
  74         /* clear unnecessary bits and set last bit to one */
  75         if (last_bits)
  76         {
  77                 buf[0] >>= 8 - last_bits;
  78                 buf[0] |= 1 << (last_bits - 1);
  79         }
  80         else
  81                 buf[0] |= 1 << 7;
  82
  83         mp_int_read_unsigned(res, buf, bytes);
  84
  85         px_free(buf);
  86
  87         return 0;
  88 }
  89
  90 static void
  91 mp_modmul(mpz_t * a, mpz_t * b, mpz_t * p, mpz_t * res)
  92 {
  93         mpz_t      *tmp = mp_new();
  94
  95         mp_int_mul(a, b, tmp);
  96         mp_int_mod(tmp, p, res);
  97         mp_clear_free(tmp);
  98 }
  99
 100 static mpz_t *
 101 mpi_to_bn(PGP_MPI * n)
 102 {
 103         mpz_t      *bn = mp_new();
 104
 105         mp_int_read_unsigned(bn, n->data, n->bytes);
 106
 107         if (!bn)
 108                 return NULL;
 109         if (mp_int_count_bits(bn) != n->bits)
 110         {
 111                 px_debug("mpi_to_bn: bignum conversion failed: mpi=%d, bn=%d",
 112                                  n->bits, mp_int_count_bits(bn));
 113                 mp_clear_free(bn);
 114                 return NULL;
 115         }
 116         return bn;
 117 }
 118
 119 static PGP_MPI *
 120 bn_to_mpi(mpz_t * bn)
 121 {
 122         int                     res;
 123         PGP_MPI    *n;
 124         int                     bytes;
 125
 126         res = pgp_mpi_alloc(mp_int_count_bits(bn), &n);
 127         if (res < 0)
 128                 return NULL;
 129
 130         bytes = (mp_int_count_bits(bn) + 7) / 8;
 131         if (bytes != n->bytes)
 132         {
 133                 px_debug("bn_to_mpi: bignum conversion failed: bn=%d, mpi=%d",
 134                                  bytes, n->bytes);
 135                 pgp_mpi_free(n);
 136                 return NULL;
 137         }
 138         mp_int_to_unsigned(bn, n->data, n->bytes);
 139         return n;
 140 }
 141
 142 /*
 143  * Decide the number of bits in the random componont k
 144  *
 145  * It should be in the same range as p for signing (which
 146  * is deprecated), but can be much smaller for encrypting.
 147  *
 148  * Until I research it further, I just mimic gpg behaviour.
 149  * It has a special mapping table, for values <= 5120,
 150  * above that it uses 'arbitrary high number'.  Following
 151  * algorihm hovers 10-70 bits above gpg values.  And for
 152  * larger p, it uses gpg's algorihm.
 153  *
 154  * The point is - if k gets large, encryption will be
 155  * really slow.  It does not matter for decryption.
 156  */
 157 static int
 158 decide_k_bits(int p_bits)
 159 {
 160         if (p_bits <= 5120)
 161                 return p_bits / 10 + 160;
 162         else
 163                 return (p_bits / 8 + 200) * 3 / 2;
 164 }
 165
 166 int
 167 pgp_elgamal_encrypt(PGP_PubKey * pk, PGP_MPI * _m,
 168                                         PGP_MPI ** c1_p, PGP_MPI ** c2_p)
 169 {
 170         int                     res = PXE_PGP_MATH_FAILED;
 171         int                     k_bits;
 172         mpz_t      *m = mpi_to_bn(_m);
 173         mpz_t      *p = mpi_to_bn(pk->pub.elg.p);
 174         mpz_t      *g = mpi_to_bn(pk->pub.elg.g);
 175         mpz_t      *y = mpi_to_bn(pk->pub.elg.y);
 176         mpz_t      *k = mp_new();
 177         mpz_t      *yk = mp_new();
 178         mpz_t      *c1 = mp_new();
 179         mpz_t      *c2 = mp_new();
 180
 181         if (!m || !p || !g || !y || !k || !yk || !c1 || !c2)
 182                 goto err;
 183
 184         /*
 185          * generate k
 186          */
 187         k_bits = decide_k_bits(mp_int_count_bits(p));
 188         res = mp_px_rand(k_bits, k);
 189         if (res < 0)
 190                 return res;
 191
 192         /*
 193          * c1 = g^k c2 = m * y^k
 194          */
 195         mp_int_exptmod(g, k, p, c1);
 196         mp_int_exptmod(y, k, p, yk);
 197         mp_modmul(m, yk, p, c2);
 198
 199         /* result */
 200         *c1_p = bn_to_mpi(c1);
 201         *c2_p = bn_to_mpi(c2);
 202         if (*c1_p && *c2_p)
 203                 res = 0;
 204 err:
 205         mp_clear_free(c2);
 206         mp_clear_free(c1);
 207         mp_clear_free(yk);
 208         mp_clear_free(k);
 209         mp_clear_free(y);
 210         mp_clear_free(g);
 211         mp_clear_free(p);
 212         mp_clear_free(m);
 213         return res;
 214 }
 215
 216 int
 217 pgp_elgamal_decrypt(PGP_PubKey * pk, PGP_MPI * _c1, PGP_MPI * _c2,
 218                                         PGP_MPI ** msg_p)
 219 {
 220         int                     res = PXE_PGP_MATH_FAILED;
 221         mpz_t      *c1 = mpi_to_bn(_c1);
 222         mpz_t      *c2 = mpi_to_bn(_c2);
 223         mpz_t      *p = mpi_to_bn(pk->pub.elg.p);
 224         mpz_t      *x = mpi_to_bn(pk->sec.elg.x);
 225         mpz_t      *c1x = mp_new();
 226         mpz_t      *div = mp_new();
 227         mpz_t      *m = mp_new();
 228
 229         if (!c1 || !c2 || !p || !x || !c1x || !div || !m)
 230                 goto err;
 231
 232         /*
 233          * m = c2 / (c1^x)
 234          */
 235         mp_int_exptmod(c1, x, p, c1x);
 236         mp_int_invmod(c1x, p, div);
 237         mp_modmul(c2, div, p, m);
 238
 239         /* result */
 240         *msg_p = bn_to_mpi(m);
 241         if (*msg_p)
 242                 res = 0;
 243 err:
 244         mp_clear_free(m);
 245         mp_clear_free(div);
 246         mp_clear_free(c1x);
 247         mp_clear_free(x);
 248         mp_clear_free(p);
 249         mp_clear_free(c2);
 250         mp_clear_free(c1);
 251         return res;
 252 }
 253
 254 int
 255 pgp_rsa_encrypt(PGP_PubKey * pk, PGP_MPI * _m, PGP_MPI ** c_p)
 256 {
 257         int                     res = PXE_PGP_MATH_FAILED;
 258         mpz_t      *m = mpi_to_bn(_m);
 259         mpz_t      *e = mpi_to_bn(pk->pub.rsa.e);
 260         mpz_t      *n = mpi_to_bn(pk->pub.rsa.n);
 261         mpz_t      *c = mp_new();
 262
 263         if (!m || !e || !n || !c)
 264                 goto err;
 265
 266         /*
 267          * c = m ^ e
 268          */
 269         mp_int_exptmod(m, e, n, c);
 270
 271         *c_p = bn_to_mpi(c);
 272         if (*c_p)
 273                 res = 0;
 274 err:
 275         mp_clear_free(c);
 276         mp_clear_free(n);
 277         mp_clear_free(e);
 278         mp_clear_free(m);
 279         return res;
 280 }
 281
 282 int
 283 pgp_rsa_decrypt(PGP_PubKey * pk, PGP_MPI * _c, PGP_MPI ** m_p)
 284 {
 285         int                     res = PXE_PGP_MATH_FAILED;
 286         mpz_t      *c = mpi_to_bn(_c);
 287         mpz_t      *d = mpi_to_bn(pk->sec.rsa.d);
 288         mpz_t      *n = mpi_to_bn(pk->pub.rsa.n);
 289         mpz_t      *m = mp_new();
 290
 291         if (!m || !d || !n || !c)
 292                 goto err;
 293
 294         /*
 295          * m = c ^ d
 296          */
 297         mp_int_exptmod(c, d, n, m);
 298
 299         *m_p = bn_to_mpi(m);
 300         if (*m_p)
 301                 res = 0;
 302 err:
 303         mp_clear_free(m);
 304         mp_clear_free(n);
 305         mp_clear_free(d);
 306         mp_clear_free(c);
 307         return res;
 308 }