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