diff options
| -rw-r--r-- | contrib/pgcrypto/Makefile | 19 | ||||
| -rw-r--r-- | contrib/pgcrypto/README.pgcrypto | 42 | ||||
| -rw-r--r-- | contrib/pgcrypto/crypt-des.c | 5 | ||||
| -rw-r--r-- | contrib/pgcrypto/crypt-gensalt.c | 4 | ||||
| -rw-r--r-- | contrib/pgcrypto/crypt-md5.c | 16 | ||||
| -rw-r--r-- | contrib/pgcrypto/expected/sha2.out | 31 | ||||
| -rw-r--r-- | contrib/pgcrypto/fortuna.c | 44 | ||||
| -rw-r--r-- | contrib/pgcrypto/imath.c | 3261 | ||||
| -rw-r--r-- | contrib/pgcrypto/imath.h | 212 | ||||
| -rw-r--r-- | contrib/pgcrypto/internal-sha2.c | 317 | ||||
| -rw-r--r-- | contrib/pgcrypto/internal.c | 226 | ||||
| -rw-r--r-- | contrib/pgcrypto/misc.c | 51 | ||||
| -rw-r--r-- | contrib/pgcrypto/openssl.c | 40 | ||||
| -rw-r--r-- | contrib/pgcrypto/pgcrypto.c | 30 | ||||
| -rw-r--r-- | contrib/pgcrypto/pgcrypto.h | 3 | ||||
| -rw-r--r-- | contrib/pgcrypto/pgcrypto.sql.in | 5 | ||||
| -rw-r--r-- | contrib/pgcrypto/pgp-mpi-internal.c | 251 | ||||
| -rw-r--r-- | contrib/pgcrypto/px-crypt.h | 10 | ||||
| -rw-r--r-- | contrib/pgcrypto/sha2.c | 139 | ||||
| -rw-r--r-- | contrib/pgcrypto/sha2.h | 12 | ||||
| -rw-r--r-- | contrib/pgcrypto/sql/sha2.sql | 7 | ||||
| -rw-r--r-- | contrib/pgcrypto/uninstall_pgcrypto.sql | 46 |
22 files changed, 4397 insertions, 374 deletions
diff --git a/contrib/pgcrypto/Makefile b/contrib/pgcrypto/Makefile index a8f17adf5e0..94b1767eaa2 100644 --- a/contrib/pgcrypto/Makefile +++ b/contrib/pgcrypto/Makefile @@ -1,29 +1,26 @@ # -# $PostgreSQL: pgsql/contrib/pgcrypto/Makefile,v 1.23 2005/09/27 17:13:08 tgl Exp $ +# $PostgreSQL: pgsql/contrib/pgcrypto/Makefile,v 1.24 2006/07/13 04:15:24 neilc Exp $ # -INT_SRCS = md5.c sha1.c sha2.c internal.c blf.c rijndael.c \ - fortuna.c random.c pgp-mpi-internal.c +INT_SRCS = md5.c sha1.c sha2.c internal.c internal-sha2.c blf.c rijndael.c \ + fortuna.c random.c pgp-mpi-internal.c imath.c INT_TESTS = sha2 OSSL_SRCS = openssl.c pgp-mpi-openssl.c -OSSL_TESTS = des 3des cast5 +OSSL_TESTS = sha2 des 3des cast5 ZLIB_OFF_CFLAGS = -DDISABLE_ZLIB ZLIB_TST = pgp-compression ZLIB_OFF_TST = pgp-zlib-DISABLED -PUBENC_ON = pgp-pubkey-decrypt pgp-pubkey-encrypt pgp-info -PUBENC_OFF = pgp-pubkey-DISABLED CF_SRCS = $(if $(subst no,,$(with_openssl)), $(OSSL_SRCS), $(INT_SRCS)) CF_TESTS = $(if $(subst no,,$(with_openssl)), $(OSSL_TESTS), $(INT_TESTS)) CF_CFLAGS = $(if $(subst yes,,$(with_zlib)), $(ZLIB_OFF_CFLAGS)) -CF_PGP_TESTS = $(if $(subst no,,$(with_zlib)), $(ZLIB_TST), $(ZLIB_OFF_TST)) \ - $(if $(subst no,,$(with_openssl)), $(PUBENC_ON), $(PUBENC_OFF)) +CF_PGP_TESTS = $(if $(subst no,,$(with_zlib)), $(ZLIB_TST), $(ZLIB_OFF_TST)) PG_CPPFLAGS = $(CF_CFLAGS) -SRCS = pgcrypto.c px.c px-hmac.c px-crypt.c misc.c \ +SRCS = pgcrypto.c px.c px-hmac.c px-crypt.c \ crypt-gensalt.c crypt-blowfish.c crypt-des.c \ crypt-md5.c $(CF_SRCS) \ mbuf.c pgp.c pgp-armor.c pgp-cfb.c pgp-compress.c \ @@ -35,12 +32,14 @@ MODULE_big = pgcrypto OBJS = $(SRCS:.c=.o) DOCS = README.pgcrypto DATA_built = pgcrypto.sql +DATA = uninstall_pgcrypto.sql EXTRA_CLEAN = gen-rtab REGRESS = init md5 sha1 hmac-md5 hmac-sha1 blowfish rijndael \ $(CF_TESTS) \ crypt-des crypt-md5 crypt-blowfish crypt-xdes \ - pgp-armor pgp-decrypt pgp-encrypt $(CF_PGP_TESTS) + pgp-armor pgp-decrypt pgp-encrypt $(CF_PGP_TESTS) \ + pgp-pubkey-decrypt pgp-pubkey-encrypt pgp-info ifdef USE_PGXS diff --git a/contrib/pgcrypto/README.pgcrypto b/contrib/pgcrypto/README.pgcrypto index 8da62b39a21..5cacaf875ca 100644 --- a/contrib/pgcrypto/README.pgcrypto +++ b/contrib/pgcrypto/README.pgcrypto @@ -49,14 +49,14 @@ There are some other differences with and without OpenSSL: ---------------------------------------------------- MD5 yes yes SHA1 yes yes - SHA256/384/512 yes since 0.9.8 + SHA224/256/384/512 yes yes (3) Any other digest algo no yes (1) Blowfish yes yes AES yes yes (2) DES/3DES/CAST5 no yes Raw encryption yes yes PGP Symmetric encryption yes yes - PGP Public-Key encryption no yes + PGP Public-Key encryption yes yes ---------------------------------------------------- 1. Any digest algorithm OpenSSL supports is automatically picked up. @@ -67,6 +67,9 @@ There are some other differences with and without OpenSSL: compiled against older version, it will use built-in AES code, so it has AES always available. +3. SHA2 algorithms were added to OpenSSL in version 0.9.8. For + older versions, pgcrypto will use built-in code. + 2.2. NULL handling ~~~~~~~~~~~~~~~~~~~~ @@ -621,14 +624,24 @@ is equal to encrypt(data, 'fooz', 'bf-cbc/pad:pkcs') -7. Credits +7. Random bytes +----------------- + + gen_random_bytes(count integer) + +Returns `count` cryptographically strong random bytes as bytea value. +There can be maximally 1024 bytes extracted at a time. This is to avoid +draining the randomness generator pool. + + +8. Credits ------------ I have used code from following sources: -`--------------------`-------------------------`---------------------- +`--------------------`-------------------------`------------------------------- Algorithm Author Source origin ----------------------------------------------------------------------- +------------------------------------------------------------------------------- DES crypt() David Burren and others FreeBSD libcrypt MD5 crypt() Poul-Henning Kamp FreeBSD libcrypt Blowfish crypt() Solar Designer www.openwall.com @@ -636,21 +649,22 @@ I have used code from following sources: Rijndael cipher Brian Gladman OpenBSD sys/crypto MD5 and SHA1 WIDE Project KAME kame/sys/crypto SHA256/384/512 Aaron D. Gifford OpenBSD sys/crypto ----------------------------------------------------------------------- + BIGNUM math Michael J. Fromberger dartmouth.edu/~sting/sw/imath +------------------------------------------------------------------------------- -8. Legalese +9. Legalese ------------- * I owe a beer to Poul-Henning. * This product includes software developed by Niels Provos. -9. References/Links ---------------------- +10. References/Links +---------------------- -9.1. Useful reading -~~~~~~~~~~~~~~~~~~~~~ +10.1. Useful reading +~~~~~~~~~~~~~~~~~~~~~~ http://www.gnupg.org/gph/en/manual.html[]:: The GNU Privacy Handbook @@ -668,8 +682,8 @@ http://www.interhack.net/people/cmcurtin/snake-oil-faq.html[]:: Describes good and bad cryptography. -9.2. Technical references -~~~~~~~~~~~~~~~~~~~~~~~~~~~ +10.2. Technical references +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ http://www.ietf.org/rfc/rfc2440.txt[]:: OpenPGP message format @@ -699,4 +713,4 @@ http://www.cs.ut.ee/~helger/crypto/[]:: Collection of cryptology pointers. -// $PostgreSQL: pgsql/contrib/pgcrypto/README.pgcrypto,v 1.14 2005/11/03 02:54:07 tgl Exp $ +// $PostgreSQL: pgsql/contrib/pgcrypto/README.pgcrypto,v 1.15 2006/07/13 04:15:24 neilc Exp $ diff --git a/contrib/pgcrypto/crypt-des.c b/contrib/pgcrypto/crypt-des.c index e5cdc370e95..a907626d398 100644 --- a/contrib/pgcrypto/crypt-des.c +++ b/contrib/pgcrypto/crypt-des.c @@ -1,7 +1,7 @@ /* * FreeSec: libcrypt for NetBSD * - * $PostgreSQL: pgsql/contrib/pgcrypto/crypt-des.c,v 1.14 2006/03/11 04:38:30 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/crypt-des.c,v 1.15 2006/07/13 04:15:24 neilc Exp $ * * Copyright (c) 1994 David Burren * All rights reserved. @@ -71,6 +71,9 @@ #define _PASSWORD_EFMT1 '_' +static const char _crypt_a64[] = +"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + static uint8 IP[64] = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, diff --git a/contrib/pgcrypto/crypt-gensalt.c b/contrib/pgcrypto/crypt-gensalt.c index c7d85110618..30a35b1796b 100644 --- a/contrib/pgcrypto/crypt-gensalt.c +++ b/contrib/pgcrypto/crypt-gensalt.c @@ -2,7 +2,7 @@ * Written by Solar Designer and placed in the public domain. * See crypt_blowfish.c for more information. * - * $PostgreSQL: pgsql/contrib/pgcrypto/crypt-gensalt.c,v 1.8 2006/03/11 04:38:30 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/crypt-gensalt.c,v 1.9 2006/07/13 04:15:24 neilc Exp $ * * This file contains salt generation functions for the traditional and * other common crypt(3) algorithms, except for bcrypt which is defined @@ -19,7 +19,7 @@ typedef unsigned int BF_word; -unsigned char _crypt_itoa64[64 + 1] = +static unsigned char _crypt_itoa64[64 + 1] = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; char * diff --git a/contrib/pgcrypto/crypt-md5.c b/contrib/pgcrypto/crypt-md5.c index a9f22c412aa..556a0e9e8e8 100644 --- a/contrib/pgcrypto/crypt-md5.c +++ b/contrib/pgcrypto/crypt-md5.c @@ -8,7 +8,7 @@ * * $FreeBSD: src/lib/libcrypt/crypt-md5.c,v 1.5 1999/12/17 20:21:45 peter Exp $ * - * $PostgreSQL: pgsql/contrib/pgcrypto/crypt-md5.c,v 1.6 2005/10/15 02:49:06 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/crypt-md5.c,v 1.7 2006/07/13 04:15:24 neilc Exp $ */ #include "postgres.h" @@ -17,6 +17,20 @@ #include "px-crypt.h" #define MD5_SIZE 16 + +static const char _crypt_a64[] = +"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + +static void +_crypt_to64(char *s, unsigned long v, int n) +{ + while (--n >= 0) + { + *s++ = _crypt_a64[v & 0x3f]; + v >>= 6; + } +} + /* * UNIX password */ diff --git a/contrib/pgcrypto/expected/sha2.out b/contrib/pgcrypto/expected/sha2.out index 20bdf0ed814..2df5a0d0f99 100644 --- a/contrib/pgcrypto/expected/sha2.out +++ b/contrib/pgcrypto/expected/sha2.out @@ -1,6 +1,37 @@ -- -- SHA2 family -- +-- SHA224 +SELECT encode(digest('', 'sha224'), 'hex'); + encode +---------------------------------------------------------- + d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f +(1 row) + +SELECT encode(digest('a', 'sha224'), 'hex'); + encode +---------------------------------------------------------- + abd37534c7d9a2efb9465de931cd7055ffdb8879563ae98078d6d6d5 +(1 row) + +SELECT encode(digest('abc', 'sha224'), 'hex'); + encode +---------------------------------------------------------- + 23097d223405d8228642a477bda255b32aadbce4bda0b3f7e36c9da7 +(1 row) + +SELECT encode(digest('abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq', 'sha224'), 'hex'); + encode +---------------------------------------------------------- + 75388b16512776cc5dba5da1fd890150b0c6455cb4f58b1952522525 +(1 row) + +SELECT encode(digest('12345678901234567890123456789012345678901234567890123456789012345678901234567890', 'sha224'), 'hex'); + encode +---------------------------------------------------------- + b50aecbe4e9bb0b57bc5f3ae760a8e01db24f203fb3cdcd13148046e +(1 row) + -- SHA256 SELECT encode(digest('', 'sha256'), 'hex'); encode diff --git a/contrib/pgcrypto/fortuna.c b/contrib/pgcrypto/fortuna.c index cf69cee28bc..cd08fd2bc68 100644 --- a/contrib/pgcrypto/fortuna.c +++ b/contrib/pgcrypto/fortuna.c @@ -26,7 +26,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.6 2006/05/21 20:22:16 tgl Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.7 2006/07/13 04:15:24 neilc Exp $ */ #include "postgres.h" @@ -125,7 +125,7 @@ struct fortuna_state struct timeval last_reseed_time; unsigned pool0_bytes; unsigned rnd_pos; - int counter_init; + int tricks_done; }; typedef struct fortuna_state FState; @@ -332,7 +332,7 @@ add_entropy(FState * st, const uint8 *data, unsigned len) /* * Make sure the pool 0 is initialized, then update randomly. */ - if (st->reseed_count == 0 && st->pool0_bytes < POOL0_FILL) + if (st->reseed_count == 0) pos = 0; else pos = get_rand_pool(st); @@ -357,21 +357,34 @@ rekey(FState * st) } /* - * Fortuna relies on AES standing known-plaintext attack. - * In case it does not, slow down the attacker by initialising - * the couter to random value. + * Hide public constants. (counter, pools > 0) + * + * This can also be viewed as spreading the startup + * entropy over all of the components. */ static void -init_counter(FState * st) +startup_tricks(FState * st) { + int i; + uint8 buf[BLOCK]; + /* Use next block as counter. */ encrypt_counter(st, st->counter); + /* Now shuffle pools, excluding #0 */ + for (i = 1; i < NUM_POOLS; i++) + { + encrypt_counter(st, buf); + encrypt_counter(st, buf + CIPH_BLOCK); + md_update(&st->pool[i], buf, BLOCK); + } + memset(buf, 0, BLOCK); + /* Hide the key. */ rekey(st); - /* The counter can be shuffled only once. */ - st->counter_init = 1; + /* This can be done only once. */ + st->tricks_done = 1; } static void @@ -380,13 +393,14 @@ extract_data(FState * st, unsigned count, uint8 *dst) unsigned n; unsigned block_nr = 0; - /* Can we reseed? */ - if (st->pool0_bytes >= POOL0_FILL && enough_time_passed(st)) - reseed(st); + /* Should we reseed? */ + if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0) + if (enough_time_passed(st)) + reseed(st); - /* Is counter initialized? */ - if (!st->counter_init) - init_counter(st); + /* Do some randomization on first call */ + if (!st->tricks_done) + startup_tricks(st); while (count > 0) { diff --git a/contrib/pgcrypto/imath.c b/contrib/pgcrypto/imath.c new file mode 100644 index 00000000000..4fef2184211 --- /dev/null +++ b/contrib/pgcrypto/imath.c @@ -0,0 +1,3261 @@ +/* imath version 1.3 */ +/* + Name: imath.c + Purpose: Arbitrary precision integer arithmetic routines. + Author: M. J. Fromberger <http://www.dartmouth.edu/~sting/> + Info: $Id: imath.c,v 1.1 2006/07/13 04:15:24 neilc Exp $ + + Copyright (C) 2002 Michael J. Fromberger, All Rights Reserved. + + Permission is hereby granted, free of charge, to any person + obtaining a copy of this software and associated documentation files + (the "Software"), to deal in the Software without restriction, + including without limitation the rights to use, copy, modify, merge, + publish, distribute, sublicense, and/or sell copies of the Software, + and to permit persons to whom the Software is furnished to do so, + subject to the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. + */ + +#include "postgres.h" +#include "px.h" +#include "imath.h" + +#undef assert +#define assert(TEST) +#define TRACEABLE_CLAMP 0 +#define TRACEABLE_FREE 0 + +/* {{{ Constants */ + +const mp_result MP_OK = 0; /* no error, all is well */ +const mp_result MP_FALSE = 0; /* boolean false */ +const mp_result MP_TRUE = -1; /* boolean true */ +const mp_result MP_MEMORY = -2; /* out of memory */ +const mp_result MP_RANGE = -3; /* argument out of range */ +const mp_result MP_UNDEF = -4; /* result undefined */ +const mp_result MP_TRUNC = -5; /* output truncated */ +const mp_result MP_BADARG = -6; /* invalid null argument */ + +const mp_sign MP_NEG = 1; /* value is strictly negative */ +const mp_sign MP_ZPOS = 0; /* value is non-negative */ + +static const char *s_unknown_err = "unknown result code"; +static const char *s_error_msg[] = { + "error code 0", + "boolean true", + "out of memory", + "argument out of range", + "result undefined", + "output truncated", + "invalid null argument", + NULL +}; + +/* }}} */ + +/* Optional library flags */ +#define MP_CAP_DIGITS 1 /* flag bit to capitalize letter digits */ + +/* Argument checking macros + Use CHECK() where a return value is required; NRCHECK() elsewhere */ +#define CHECK(TEST) assert(TEST) +#define NRCHECK(TEST) assert(TEST) + +/* {{{ Logarithm table for computing output sizes */ + +/* The ith entry of this table gives the value of log_i(2). + + An integer value n requires ceil(log_i(n)) digits to be represented + in base i. Since it is easy to compute lg(n), by counting bits, we + can compute log_i(n) = lg(n) * log_i(2). + */ +static const double s_log2[] = { + 0.000000000, 0.000000000, 1.000000000, 0.630929754, /* 0 1 2 3 */ + 0.500000000, 0.430676558, 0.386852807, 0.356207187, /* 4 5 6 7 */ + 0.333333333, 0.315464877, 0.301029996, 0.289064826, /* 8 9 10 11 */ + 0.278942946, 0.270238154, 0.262649535, 0.255958025, /* 12 13 14 15 */ + 0.250000000, 0.244650542, 0.239812467, 0.235408913, /* 16 17 18 19 */ + 0.231378213, 0.227670249, 0.224243824, 0.221064729, /* 20 21 22 23 */ + 0.218104292, 0.215338279, 0.212746054, 0.210309918, /* 24 25 26 27 */ + 0.208014598, 0.205846832, 0.203795047, 0.201849087, /* 28 29 30 31 */ + 0.200000000, 0.198239863, 0.196561632, 0.194959022, /* 32 33 34 35 */ + 0.193426404, 0.191958720, 0.190551412, 0.189200360, /* 36 37 38 39 */ + 0.187901825, 0.186652411, 0.185449023, 0.184288833, /* 40 41 42 43 */ + 0.183169251, 0.182087900, 0.181042597, 0.180031327, /* 44 45 46 47 */ + 0.179052232, 0.178103594, 0.177183820, 0.176291434, /* 48 49 50 51 */ + 0.175425064, 0.174583430, 0.173765343, 0.172969690, /* 52 53 54 55 */ + 0.172195434, 0.171441601, 0.170707280, 0.169991616, /* 56 57 58 59 */ + 0.169293808, 0.168613099, 0.167948779, 0.167300179, /* 60 61 62 63 */ + 0.166666667 +}; + +/* }}} */ +/* {{{ Various macros */ + +/* Return the number of digits needed to represent a static value */ +#define MP_VALUE_DIGITS(V) \ +((sizeof(V)+(sizeof(mp_digit)-1))/sizeof(mp_digit)) + +/* Round precision P to nearest word boundary */ +#define ROUND_PREC(P) ((mp_size)(2*(((P)+1)/2))) + +/* Set array P of S digits to zero */ +#define ZERO(P, S) \ +do{mp_size i__=(S)*sizeof(mp_digit);mp_digit *p__=(P);memset(p__,0,i__);}while(0) + +/* Copy S digits from array P to array Q */ +#define COPY(P, Q, S) \ +do{mp_size i__=(S)*sizeof(mp_digit);mp_digit *p__=(P),*q__=(Q);\ +memcpy(q__,p__,i__);}while(0) + +/* Reverse N elements of type T in array A */ +#define REV(T, A, N) \ +do{T *u_=(A),*v_=u_+(N)-1;while(u_<v_){T xch=*u_;*u_++=*v_;*v_--=xch;}}while(0) + +#if TRACEABLE_CLAMP +#define CLAMP(Z) s_clamp(Z) +#else +#define CLAMP(Z) \ +do{mp_int z_=(Z);mp_size uz_=MP_USED(z_);mp_digit *dz_=MP_DIGITS(z_)+uz_-1;\ +while(uz_ > 1 && (*dz_-- == 0)) --uz_;MP_USED(z_)=uz_;}while(0) +#endif + +#undef MIN +#undef MAX +#define MIN(A, B) ((B)<(A)?(B):(A)) +#define MAX(A, B) ((B)>(A)?(B):(A)) +#define SWAP(T, A, B) do{T t_=(A);A=(B);B=t_;}while(0) + +#define TEMP(K) (temp + (K)) +#define SETUP(E, C) \ +do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0) + +#define CMPZ(Z) \ +(((Z)->used==1&&(Z)->digits[0]==0)?0:((Z)->sign==MP_NEG)?-1:1) + +#define UMUL(X, Y, Z) \ +do{mp_size ua_=MP_USED(X),ub_=MP_USED(Y);mp_size o_=ua_+ub_;\ +ZERO(MP_DIGITS(Z),o_);\ +(void) s_kmul(MP_DIGITS(X),MP_DIGITS(Y),MP_DIGITS(Z),ua_,ub_);\ +MP_USED(Z)=o_;CLAMP(Z);}while(0) + +#define USQR(X, Z) \ +do{mp_size ua_=MP_USED(X),o_=ua_+ua_;ZERO(MP_DIGITS(Z),o_);\ +(void) s_ksqr(MP_DIGITS(X),MP_DIGITS(Z),ua_);MP_USED(Z)=o_;CLAMP(Z);}while(0) + +#define UPPER_HALF(W) ((mp_word)((W) >> MP_DIGIT_BIT)) +#define LOWER_HALF(W) ((mp_digit)(W)) +#define HIGH_BIT_SET(W) ((W) >> (MP_WORD_BIT - 1)) +#define ADD_WILL_OVERFLOW(W, V) ((MP_WORD_MAX - (V)) < (W)) + +/* }}} */ + +/* Default number of digits allocated to a new mp_int */ +static mp_size default_precision = 64; + +/* Minimum number of digits to invoke recursive multiply */ +static mp_size multiply_threshold = 32; + +/* Default library configuration flags */ +static mp_word mp_flags = MP_CAP_DIGITS; + +/* Allocate a buffer of (at least) num digits, or return + NULL if that couldn't be done. */ +static mp_digit *s_alloc(mp_size num); +#if TRACEABLE_FREE +static void s_free(void *ptr); +#else +#define s_free(P) px_free(P) +#endif + +/* Insure that z has at least min digits allocated, resizing if + necessary. Returns true if successful, false if out of memory. */ +static int s_pad(mp_int z, mp_size min); + +/* Normalize by removing leading zeroes (except when z = 0) */ +#if TRACEABLE_CLAMP +static void s_clamp(mp_int z); +#endif + +/* Fill in a "fake" mp_int on the stack with a given value */ +static void s_fake(mp_int z, int value, mp_digit vbuf[]); + +/* Compare two runs of digits of given length, returns <0, 0, >0 */ +static int s_cdig(mp_digit *da, mp_digit *db, mp_size len); + +/* Pack the unsigned digits of v into array t */ +static int s_vpack(int v, mp_digit t[]); + +/* Compare magnitudes of a and b, returns <0, 0, >0 */ +static int s_ucmp(mp_int a, mp_int b); + +/* Compare magnitudes of a and v, returns <0, 0, >0 */ +static int s_vcmp(mp_int a, int v); + +/* Unsigned magnitude addition; assumes dc is big enough. + Carry out is returned (no memory allocated). */ +static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b); + +/* Unsigned magnitude subtraction. Assumes dc is big enough. */ +static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b); + +/* Unsigned recursive multiplication. Assumes dc is big enough. */ +static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b); + +/* Unsigned magnitude multiplication. Assumes dc is big enough. */ +static void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b); + +/* Unsigned recursive squaring. Assumes dc is big enough. */ +static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a); + +/* Unsigned magnitude squaring. Assumes dc is big enough. */ +static void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a); + +/* Single digit addition. Assumes a is big enough. */ +static void s_dadd(mp_int a, mp_digit b); + +/* Single digit multiplication. Assumes a is big enough. */ +static void s_dmul(mp_int a, mp_digit b); + +/* Single digit multiplication on buffers; assumes dc is big enough. */ +static void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, + mp_size size_a); + +/* Single digit division. Replaces a with the quotient, + returns the remainder. */ +static mp_digit s_ddiv(mp_int a, mp_digit b); + +/* Quick division by a power of 2, replaces z (no allocation) */ +static void s_qdiv(mp_int z, mp_size p2); + +/* Quick remainder by a power of 2, replaces z (no allocation) */ +static void s_qmod(mp_int z, mp_size p2); + +/* Quick multiplication by a power of 2, replaces z. + Allocates if necessary; returns false in case this fails. */ +static int s_qmul(mp_int z, mp_size p2); + +/* Quick subtraction from a power of 2, replaces z. + Allocates if necessary; returns false in case this fails. */ +static int s_qsub(mp_int z, mp_size p2); + +/* Return maximum k such that 2^k divides z. */ +static int s_dp2k(mp_int z); + +/* Return k >= 0 such that z = 2^k, or -1 if there is no such k. */ +static int s_isp2(mp_int z); + +/* Set z to 2^k. May allocate; returns false in case this fails. */ +static int s_2expt(mp_int z, int k); + +/* Normalize a and b for division, returns normalization constant */ +static int s_norm(mp_int a, mp_int b); + +/* Compute constant mu for Barrett reduction, given modulus m, result + replaces z, m is untouched. */ +static mp_result s_brmu(mp_int z, mp_int m); + +/* Reduce a modulo m, using Barrett's algorithm. */ +static int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2); + +/* Modular exponentiation, using Barrett reduction */ +static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c); + +/* Unsigned magnitude division. Assumes |a| > |b|. Allocates + temporaries; overwrites a with quotient, b with remainder. */ +static mp_result s_udiv(mp_int a, mp_int b); + +/* Compute the number of digits in radix r required to represent the + given value. Does not account for sign flags, terminators, etc. */ +static int s_outlen(mp_int z, mp_size r); + +/* Guess how many digits of precision will be needed to represent a + radix r value of the specified number of digits. Returns a value + guaranteed to be no smaller than the actual number required. */ +static mp_size s_inlen(int len, mp_size r); + +/* Convert a character to a digit value in radix r, or + -1 if out of range */ +static int s_ch2val(char c, int r); + +/* Convert a digit value to a character */ +static char s_val2ch(int v, int caps); + +/* Take 2's complement of a buffer in place */ +static void s_2comp(unsigned char *buf, int len); + +/* Convert a value to binary, ignoring sign. On input, *limpos is the + bound on how many bytes should be written to buf; on output, *limpos + is set to the number of bytes actually written. */ +static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad); + +#if 0 +/* Dump a representation of the mp_int to standard output */ +void s_print(char *tag, mp_int z); +void s_print_buf(char *tag, mp_digit *buf, mp_size num); +#endif + +/* {{{ get_default_precision() */ + +mp_size mp_get_default_precision(void) +{ + return default_precision; +} + +/* }}} */ + +/* {{{ mp_set_default_precision(s) */ + +void mp_set_default_precision(mp_size s) +{ + NRCHECK(s > 0); + + default_precision = (mp_size) ROUND_PREC(s); +} + +/* }}} */ + +/* {{{ mp_get_multiply_threshold() */ + +mp_size mp_get_multiply_threshold(void) +{ + return multiply_threshold; +} + +/* }}} */ + +/* {{{ mp_set_multiply_threshold(s) */ + +void mp_set_multiply_threshold(mp_size s) +{ + multiply_threshold = s; +} + +/* }}} */ + +/* {{{ mp_int_init(z) */ + +mp_result mp_int_init(mp_int z) +{ + return mp_int_init_size(z, default_precision); +} + +/* }}} */ + +/* {{{ mp_int_alloc() */ + +mp_int mp_int_alloc(void) +{ + mp_int out = px_alloc(sizeof(mpz_t)); + + assert(out != NULL); + out->digits = NULL; + out->used = 0; + out->alloc = 0; + out->sign = 0; + + return out; +} + +/* }}} */ + +/* {{{ mp_int_init_size(z, prec) */ + +mp_result mp_int_init_size(mp_int z, mp_size prec) +{ + CHECK(z != NULL); + + prec = (mp_size) ROUND_PREC(prec); + prec = MAX(prec, default_precision); + + if((MP_DIGITS(z) = s_alloc(prec)) == NULL) + return MP_MEMORY; + + z->digits[0] = 0; + MP_USED(z) = 1; + MP_ALLOC(z) = prec; + MP_SIGN(z) = MP_ZPOS; + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_init_copy(z, old) */ + +mp_result mp_int_init_copy(mp_int z, mp_int old) +{ + mp_result res; + mp_size uold, target; + + CHECK(z != NULL && old != NULL); + + uold = MP_USED(old); + target = MAX(uold, default_precision); + + if((res = mp_int_init_size(z, target)) != MP_OK) + return res; + + MP_USED(z) = uold; + MP_SIGN(z) = MP_SIGN(old); + COPY(MP_DIGITS(old), MP_DIGITS(z), uold); + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_init_value(z, value) */ + +mp_result mp_int_init_value(mp_int z, int value) +{ + mp_result res; + + CHECK(z != NULL); + + if((res = mp_int_init(z)) != MP_OK) + return res; + + return mp_int_set_value(z, value); +} + +/* }}} */ + +/* {{{ mp_int_set_value(z, value) */ + +mp_result mp_int_set_value(mp_int z, int value) +{ + mp_size ndig; + + CHECK(z != NULL); + + /* How many digits to copy */ + ndig = (mp_size) MP_VALUE_DIGITS(value); + + if(!s_pad(z, ndig)) + return MP_MEMORY; + + MP_USED(z) = (mp_size)s_vpack(value, MP_DIGITS(z)); + MP_SIGN(z) = (value < 0) ? MP_NEG : MP_ZPOS; + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_clear(z) */ + +void mp_int_clear(mp_int z) +{ + if(z == NULL) + return; + + if(MP_DIGITS(z) != NULL) { + s_free(MP_DIGITS(z)); + MP_DIGITS(z) = NULL; + } +} + +/* }}} */ + +/* {{{ mp_int_free(z) */ + +void mp_int_free(mp_int z) +{ + NRCHECK(z != NULL); + + if(z->digits != NULL) + mp_int_clear(z); + + px_free(z); +} + +/* }}} */ + +/* {{{ mp_int_copy(a, c) */ + +mp_result mp_int_copy(mp_int a, mp_int c) +{ + CHECK(a != NULL && c != NULL); + + if(a != c) { + mp_size ua = MP_USED(a); + mp_digit *da, *dc; + + if(!s_pad(c, ua)) + return MP_MEMORY; + + da = MP_DIGITS(a); dc = MP_DIGITS(c); + COPY(da, dc, ua); + + MP_USED(c) = ua; + MP_SIGN(c) = MP_SIGN(a); + } + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_swap(a, c) */ + +void mp_int_swap(mp_int a, mp_int c) +{ + if(a != c) { + mpz_t tmp = *a; + + *a = *c; + *c = tmp; + } +} + +/* }}} */ + +/* {{{ mp_int_zero(z) */ + +void mp_int_zero(mp_int z) +{ + NRCHECK(z != NULL); + + z->digits[0] = 0; + MP_USED(z) = 1; + MP_SIGN(z) = MP_ZPOS; +} + +/* }}} */ + +/* {{{ mp_int_abs(a, c) */ + +mp_result mp_int_abs(mp_int a, mp_int c) +{ + mp_result res; + + CHECK(a != NULL && c != NULL); + + if((res = mp_int_copy(a, c)) != MP_OK) + return res; + + MP_SIGN(c) = MP_ZPOS; + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_neg(a, c) */ + +mp_result mp_int_neg(mp_int a, mp_int c) +{ + mp_result res; + + CHECK(a != NULL && c != NULL); + + if((res = mp_int_copy(a, c)) != MP_OK) + return res; + + if(CMPZ(c) != 0) + MP_SIGN(c) = 1 - MP_SIGN(a); + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_add(a, b, c) */ + +mp_result mp_int_add(mp_int a, mp_int b, mp_int c) +{ + mp_size ua, ub, uc, max; + + CHECK(a != NULL && b != NULL && c != NULL); + + ua = MP_USED(a); ub = MP_USED(b); uc = MP_USED(c); + max = MAX(ua, ub); + + if(MP_SIGN(a) == MP_SIGN(b)) { + /* Same sign -- add magnitudes, preserve sign of addends */ + mp_digit carry; + + if(!s_pad(c, max)) + return MP_MEMORY; + + carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub); + uc = max; + + if(carry) { + if(!s_pad(c, max + 1)) + return MP_MEMORY; + + c->digits[max] = carry; + ++uc; + } + + MP_USED(c) = uc; + MP_SIGN(c) = MP_SIGN(a); + + } + else { + /* Different signs -- subtract magnitudes, preserve sign of greater */ + mp_int x, y; + int cmp = s_ucmp(a, b); /* magnitude comparision, sign ignored */ + + /* Set x to max(a, b), y to min(a, b) to simplify later code */ + if(cmp >= 0) { + x = a; y = b; + } + else { + x = b; y = a; + } + + if(!s_pad(c, MP_USED(x))) + return MP_MEMORY; + + /* Subtract smaller from larger */ + s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y)); + MP_USED(c) = MP_USED(x); + CLAMP(c); + + /* Give result the sign of the larger */ + MP_SIGN(c) = MP_SIGN(x); + } + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_add_value(a, value, c) */ + +mp_result mp_int_add_value(mp_int a, int value, mp_int c) +{ + mpz_t vtmp; + mp_digit vbuf[MP_VALUE_DIGITS(value)]; + + s_fake(&vtmp, value, vbuf); + + return mp_int_add(a, &vtmp, c); +} + +/* }}} */ + +/* {{{ mp_int_sub(a, b, c) */ + +mp_result mp_int_sub(mp_int a, mp_int b, mp_int c) +{ + mp_size ua, ub, uc, max; + + CHECK(a != NULL && b != NULL && c != NULL); + + ua = MP_USED(a); ub = MP_USED(b); uc = MP_USED(c); + max = MAX(ua, ub); + + if(MP_SIGN(a) != MP_SIGN(b)) { + /* Different signs -- add magnitudes and keep sign of a */ + mp_digit carry; + + if(!s_pad(c, max)) + return MP_MEMORY; + + carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub); + uc = max; + + if(carry) { + if(!s_pad(c, max + 1)) + return MP_MEMORY; + + c->digits[max] = carry; + ++uc; + } + + MP_USED(c) = uc; + MP_SIGN(c) = MP_SIGN(a); + + } + else { + /* Same signs -- subtract magnitudes */ + mp_int x, y; + mp_sign osign; + int cmp = s_ucmp(a, b); + + if(!s_pad(c, max)) + return MP_MEMORY; + + if(cmp >= 0) { + x = a; y = b; osign = MP_ZPOS; + } + else { + x = b; y = a; osign = MP_NEG; + } + + if(MP_SIGN(a) == MP_NEG && cmp != 0) + osign = 1 - osign; + + s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y)); + MP_USED(c) = MP_USED(x); + CLAMP(c); + + MP_SIGN(c) = osign; + } + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_sub_value(a, value, c) */ + +mp_result mp_int_sub_value(mp_int a, int value, mp_int c) +{ + mpz_t vtmp; + mp_digit vbuf[MP_VALUE_DIGITS(value)]; + + s_fake(&vtmp, value, vbuf); + + return mp_int_sub(a, &vtmp, c); +} + +/* }}} */ + +/* {{{ mp_int_mul(a, b, c) */ + +mp_result mp_int_mul(mp_int a, mp_int b, mp_int c) +{ + mp_digit *out; + mp_size osize, ua, ub, p = 0; + mp_sign osign; + + CHECK(a != NULL && b != NULL && c != NULL); + + /* If either input is zero, we can shortcut multiplication */ + if(mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0) { + mp_int_zero(c); + return MP_OK; + } + + /* Output is positive if inputs have same sign, otherwise negative */ + osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG; + + /* If the output is not equal to any of the inputs, we'll write the + results there directly; otherwise, allocate a temporary space. */ + ua = MP_USED(a); ub = MP_USED(b); + osize = ua + ub; + + if(c == a || c == b) { + p = ROUND_PREC(osize); + p = MAX(p, default_precision); + + if((out = s_alloc(p)) == NULL) + return MP_MEMORY; + } + else { + if(!s_pad(c, osize)) + return MP_MEMORY; + + out = MP_DIGITS(c); + } + ZERO(out, osize); + + if(!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub)) + return MP_MEMORY; + + /* If we allocated a new buffer, get rid of whatever memory c was + already using, and fix up its fields to reflect that. + */ + if(out != MP_DIGITS(c)) { + s_free(MP_DIGITS(c)); + MP_DIGITS(c) = out; + MP_ALLOC(c) = p; + } + + MP_USED(c) = osize; /* might not be true, but we'll fix it ... */ + CLAMP(c); /* ... right here */ + MP_SIGN(c) = osign; + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_mul_value(a, value, c) */ + +mp_result mp_int_mul_value(mp_int a, int value, mp_int c) +{ + mpz_t vtmp; + mp_digit vbuf[MP_VALUE_DIGITS(value)]; + + s_fake(&vtmp, value, vbuf); + + return mp_int_mul(a, &vtmp, c); +} + +/* }}} */ + +/* {{{ mp_int_mul_pow2(a, p2, c) */ + +mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c) +{ + mp_result res; + CHECK(a != NULL && c != NULL && p2 >= 0); + + if((res = mp_int_copy(a, c)) != MP_OK) + return res; + + if(s_qmul(c, (mp_size) p2)) + return MP_OK; + else + return MP_MEMORY; +} + +/* }}} */ + +/* {{{ mp_int_sqr(a, c) */ + +mp_result mp_int_sqr(mp_int a, mp_int c) +{ + mp_digit *out; + mp_size osize, p = 0; + + CHECK(a != NULL && c != NULL); + + /* Get a temporary buffer big enough to hold the result */ + osize = (mp_size) 2 * MP_USED(a); + if(a == c) { + p = ROUND_PREC(osize); + p = MAX(p, default_precision); + + if((out = s_alloc(p)) == NULL) + return MP_MEMORY; + } + else { + if(!s_pad(c, osize)) + return MP_MEMORY; + + out = MP_DIGITS(c); + } + ZERO(out, osize); + + s_ksqr(MP_DIGITS(a), out, MP_USED(a)); + + /* Get rid of whatever memory c was already using, and fix up its + fields to reflect the new digit array it's using + */ + if(out != MP_DIGITS(c)) { + s_free(MP_DIGITS(c)); + MP_DIGITS(c) = out; + MP_ALLOC(c) = p; + } + + MP_USED(c) = osize; /* might not be true, but we'll fix it ... */ + CLAMP(c); /* ... right here */ + MP_SIGN(c) = MP_ZPOS; + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_div(a, b, q, r) */ + +mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r) +{ + int cmp, last = 0, lg; + mp_result res = MP_OK; + mpz_t temp[2]; + mp_int qout, rout; + mp_sign sa = MP_SIGN(a), sb = MP_SIGN(b); + + CHECK(a != NULL && b != NULL && q != r); + + if(CMPZ(b) == 0) + return MP_UNDEF; + else if((cmp = s_ucmp(a, b)) < 0) { + /* If |a| < |b|, no division is required: + q = 0, r = a + */ + if(r && (res = mp_int_copy(a, r)) != MP_OK) + return res; + + if(q) + mp_int_zero(q); + + return MP_OK; + } + else if(cmp == 0) { + /* If |a| = |b|, no division is required: + q = 1 or -1, r = 0 + */ + if(r) + mp_int_zero(r); + + if(q) { + mp_int_zero(q); + q->digits[0] = 1; + + if(sa != sb) + MP_SIGN(q) = MP_NEG; + } + + return MP_OK; + } + + /* When |a| > |b|, real division is required. We need someplace to + store quotient and remainder, but q and r are allowed to be NULL + or to overlap with the inputs. + */ + if((lg = s_isp2(b)) < 0) { + if(q && b != q && (res = mp_int_copy(a, q)) == MP_OK) { + qout = q; + } + else { + qout = TEMP(last); + SETUP(mp_int_init_copy(TEMP(last), a), last); + } + + if(r && a != r && (res = mp_int_copy(b, r)) == MP_OK) { + rout = r; + } + else { + rout = TEMP(last); + SETUP(mp_int_init_copy(TEMP(last), b), last); + } + + if((res = s_udiv(qout, rout)) != MP_OK) goto CLEANUP; + } + else { + if(q && (res = mp_int_copy(a, q)) != MP_OK) goto CLEANUP; + if(r && (res = mp_int_copy(a, r)) != MP_OK) goto CLEANUP; + + if(q) s_qdiv(q, (mp_size) lg); qout = q; + if(r) s_qmod(r, (mp_size) lg); rout = r; + } + + /* Recompute signs for output */ + if(rout) { + MP_SIGN(rout) = sa; + if(CMPZ(rout) == 0) + MP_SIGN(rout) = MP_ZPOS; + } + if(qout) { + MP_SIGN(qout) = (sa == sb) ? MP_ZPOS : MP_NEG; + if(CMPZ(qout) == 0) + MP_SIGN(qout) = MP_ZPOS; + } + + if(q && (res = mp_int_copy(qout, q)) != MP_OK) goto CLEANUP; + if(r && (res = mp_int_copy(rout, r)) != MP_OK) goto CLEANUP; + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_mod(a, m, c) */ + +mp_result mp_int_mod(mp_int a, mp_int m, mp_int c) +{ + mp_result res; + mpz_t tmp; + mp_int out; + + if(m == c) { + if((res = mp_int_init(&tmp)) != MP_OK) + return res; + + out = &tmp; + } + else { + out = c; + } + + if((res = mp_int_div(a, m, NULL, out)) != MP_OK) + goto CLEANUP; + + if(CMPZ(out) < 0) + res = mp_int_add(out, m, c); + else + res = mp_int_copy(out, c); + + CLEANUP: + if(out != c) + mp_int_clear(&tmp); + + return res; +} + +/* }}} */ + + +/* {{{ mp_int_div_value(a, value, q, r) */ + +mp_result mp_int_div_value(mp_int a, int value, mp_int q, int *r) +{ + mpz_t vtmp, rtmp; + mp_digit vbuf[MP_VALUE_DIGITS(value)]; + mp_result res; + + if((res = mp_int_init(&rtmp)) != MP_OK) return res; + s_fake(&vtmp, value, vbuf); + + if((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK) + goto CLEANUP; + + if(r) + (void) mp_int_to_int(&rtmp, r); /* can't fail */ + + CLEANUP: + mp_int_clear(&rtmp); + return res; +} + +/* }}} */ + +/* {{{ mp_int_div_pow2(a, p2, q, r) */ + +mp_result mp_int_div_pow2(mp_int a, int p2, mp_int q, mp_int r) +{ + mp_result res = MP_OK; + + CHECK(a != NULL && p2 >= 0 && q != r); + + if(q != NULL && (res = mp_int_copy(a, q)) == MP_OK) + s_qdiv(q, (mp_size) p2); + + if(res == MP_OK && r != NULL && (res = mp_int_copy(a, r)) == MP_OK) + s_qmod(r, (mp_size) p2); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_expt(a, b, c) */ + +mp_result mp_int_expt(mp_int a, int b, mp_int c) +{ + mpz_t t; + mp_result res; + unsigned int v = abs(b); + + CHECK(b >= 0 && c != NULL); + + if((res = mp_int_init_copy(&t, a)) != MP_OK) + return res; + + (void) mp_int_set_value(c, 1); + while(v != 0) { + if(v & 1) { + if((res = mp_int_mul(c, &t, c)) != MP_OK) + goto CLEANUP; + } + + v >>= 1; + if(v == 0) break; + + if((res = mp_int_sqr(&t, &t)) != MP_OK) + goto CLEANUP; + } + + CLEANUP: + mp_int_clear(&t); + return res; +} + +/* }}} */ + +/* {{{ mp_int_expt_value(a, b, c) */ + +mp_result mp_int_expt_value(int a, int b, mp_int c) +{ + mpz_t t; + mp_result res; + unsigned int v = abs(b); + + CHECK(b >= 0 && c != NULL); + + if((res = mp_int_init_value(&t, a)) != MP_OK) + return res; + + (void) mp_int_set_value(c, 1); + while(v != 0) { + if(v & 1) { + if((res = mp_int_mul(c, &t, c)) != MP_OK) + goto CLEANUP; + } + + v >>= 1; + if(v == 0) break; + + if((res = mp_int_sqr(&t, &t)) != MP_OK) + goto CLEANUP; + } + + CLEANUP: + mp_int_clear(&t); + return res; +} + +/* }}} */ + +/* {{{ mp_int_compare(a, b) */ + +int mp_int_compare(mp_int a, mp_int b) +{ + mp_sign sa; + + CHECK(a != NULL && b != NULL); + + sa = MP_SIGN(a); + if(sa == MP_SIGN(b)) { + int cmp = s_ucmp(a, b); + + /* If they're both zero or positive, the normal comparison + applies; if both negative, the sense is reversed. */ + if(sa == MP_ZPOS) + return cmp; + else + return -cmp; + + } + else { + if(sa == MP_ZPOS) + return 1; + else + return -1; + } +} + +/* }}} */ + +/* {{{ mp_int_compare_unsigned(a, b) */ + +int mp_int_compare_unsigned(mp_int a, mp_int b) +{ + NRCHECK(a != NULL && b != NULL); + + return s_ucmp(a, b); +} + +/* }}} */ + +/* {{{ mp_int_compare_zero(z) */ + +int mp_int_compare_zero(mp_int z) +{ + NRCHECK(z != NULL); + + if(MP_USED(z) == 1 && z->digits[0] == 0) + return 0; + else if(MP_SIGN(z) == MP_ZPOS) + return 1; + else + return -1; +} + +/* }}} */ + +/* {{{ mp_int_compare_value(z, value) */ + +int mp_int_compare_value(mp_int z, int value) +{ + mp_sign vsign = (value < 0) ? MP_NEG : MP_ZPOS; + int cmp; + + CHECK(z != NULL); + + if(vsign == MP_SIGN(z)) { + cmp = s_vcmp(z, value); + + if(vsign == MP_ZPOS) + return cmp; + else + return -cmp; + } + else { + if(value < 0) + return 1; + else + return -1; + } +} + +/* }}} */ + +/* {{{ mp_int_exptmod(a, b, m, c) */ + +mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c) +{ + mp_result res; + mp_size um; + mpz_t temp[3]; + mp_int s; + int last = 0; + + CHECK(a != NULL && b != NULL && c != NULL && m != NULL); + + /* Zero moduli and negative exponents are not considered. */ + if(CMPZ(m) == 0) + return MP_UNDEF; + if(CMPZ(b) < 0) + return MP_RANGE; + + um = MP_USED(m); + SETUP(mp_int_init_size(TEMP(0), 2 * um), last); + SETUP(mp_int_init_size(TEMP(1), 2 * um), last); + + if(c == b || c == m) { + SETUP(mp_int_init_size(TEMP(2), 2 * um), last); + s = TEMP(2); + } + else { + s = c; + } + + if((res = mp_int_mod(a, m, TEMP(0))) != MP_OK) goto CLEANUP; + + if((res = s_brmu(TEMP(1), m)) != MP_OK) goto CLEANUP; + + if((res = s_embar(TEMP(0), b, m, TEMP(1), s)) != MP_OK) + goto CLEANUP; + + res = mp_int_copy(s, c); + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_exptmod_evalue(a, value, m, c) */ + +mp_result mp_int_exptmod_evalue(mp_int a, int value, mp_int m, mp_int c) +{ + mpz_t vtmp; + mp_digit vbuf[MP_VALUE_DIGITS(value)]; + + s_fake(&vtmp, value, vbuf); + + return mp_int_exptmod(a, &vtmp, m, c); +} + +/* }}} */ + +/* {{{ mp_int_exptmod_bvalue(v, b, m, c) */ + +mp_result mp_int_exptmod_bvalue(int value, mp_int b, + mp_int m, mp_int c) +{ + mpz_t vtmp; + mp_digit vbuf[MP_VALUE_DIGITS(value)]; + + s_fake(&vtmp, value, vbuf); + + return mp_int_exptmod(&vtmp, b, m, c); +} + +/* }}} */ + +/* {{{ mp_int_exptmod_known(a, b, m, mu, c) */ + +mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c) +{ + mp_result res; + mp_size um; + mpz_t temp[2]; + mp_int s; + int last = 0; + + CHECK(a && b && m && c); + + /* Zero moduli and negative exponents are not considered. */ + if(CMPZ(m) == 0) + return MP_UNDEF; + if(CMPZ(b) < 0) + return MP_RANGE; + + um = MP_USED(m); + SETUP(mp_int_init_size(TEMP(0), 2 * um), last); + + if(c == b || c == m) { + SETUP(mp_int_init_size(TEMP(1), 2 * um), last); + s = TEMP(1); + } + else { + s = c; + } + + if((res = mp_int_mod(a, m, TEMP(0))) != MP_OK) goto CLEANUP; + + if((res = s_embar(TEMP(0), b, m, mu, s)) != MP_OK) + goto CLEANUP; + + res = mp_int_copy(s, c); + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_redux_const(m, c) */ + +mp_result mp_int_redux_const(mp_int m, mp_int c) +{ + CHECK(m != NULL && c != NULL && m != c); + + return s_brmu(c, m); +} + +/* }}} */ + +/* {{{ mp_int_invmod(a, m, c) */ + +mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c) +{ + mp_result res; + mp_sign sa; + int last = 0; + mpz_t temp[2]; + + CHECK(a != NULL && m != NULL && c != NULL); + + if(CMPZ(a) == 0 || CMPZ(m) <= 0) + return MP_RANGE; + + sa = MP_SIGN(a); /* need this for the result later */ + + for(last = 0; last < 2; ++last) + if((res = mp_int_init(TEMP(last))) != MP_OK) + goto CLEANUP; + + if((res = mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL)) != MP_OK) + goto CLEANUP; + + if(mp_int_compare_value(TEMP(0), 1) != 0) { + res = MP_UNDEF; + goto CLEANUP; + } + + /* It is first necessary to constrain the value to the proper range */ + if((res = mp_int_mod(TEMP(1), m, TEMP(1))) != MP_OK) + goto CLEANUP; + + /* Now, if 'a' was originally negative, the value we have is + actually the magnitude of the negative representative; to get the + positive value we have to subtract from the modulus. Otherwise, + the value is okay as it stands. + */ + if(sa == MP_NEG) + res = mp_int_sub(m, TEMP(1), c); + else + res = mp_int_copy(TEMP(1), c); + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_gcd(a, b, c) */ + +/* Binary GCD algorithm due to Josef Stein, 1961 */ +mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c) +{ + int ca, cb, k = 0; + mpz_t u, v, t; + mp_result res; + + CHECK(a != NULL && b != NULL && c != NULL); + + ca = CMPZ(a); + cb = CMPZ(b); + if(ca == 0 && cb == 0) + return MP_UNDEF; + else if(ca == 0) + return mp_int_abs(b, c); + else if(cb == 0) + return mp_int_abs(a, c); + + if((res = mp_int_init(&t)) != MP_OK) + return res; + if((res = mp_int_init_copy(&u, a)) != MP_OK) + goto U; + if((res = mp_int_init_copy(&v, b)) != MP_OK) + goto V; + + MP_SIGN(&u) = MP_ZPOS; MP_SIGN(&v) = MP_ZPOS; + + { /* Divide out common factors of 2 from u and v */ + int div2_u = s_dp2k(&u), div2_v = s_dp2k(&v); + + k = MIN(div2_u, div2_v); + s_qdiv(&u, (mp_size) k); + s_qdiv(&v, (mp_size) k); + } + + if(mp_int_is_odd(&u)) { + if((res = mp_int_neg(&v, &t)) != MP_OK) + goto CLEANUP; + } + else { + if((res = mp_int_copy(&u, &t)) != MP_OK) + goto CLEANUP; + } + + for(;;) { + s_qdiv(&t, s_dp2k(&t)); + + if(CMPZ(&t) > 0) { + if((res = mp_int_copy(&t, &u)) != MP_OK) + goto CLEANUP; + } + else { + if((res = mp_int_neg(&t, &v)) != MP_OK) + goto CLEANUP; + } + + if((res = mp_int_sub(&u, &v, &t)) != MP_OK) + goto CLEANUP; + + if(CMPZ(&t) == 0) + break; + } + + if((res = mp_int_abs(&u, c)) != MP_OK) + goto CLEANUP; + if(!s_qmul(c, (mp_size) k)) + res = MP_MEMORY; + + CLEANUP: + mp_int_clear(&v); + V: mp_int_clear(&u); + U: mp_int_clear(&t); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_egcd(a, b, c, x, y) */ + +/* This is the binary GCD algorithm again, but this time we keep track + of the elementary matrix operations as we go, so we can get values + x and y satisfying c = ax + by. + */ +mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, + mp_int x, mp_int y) +{ + int k, last = 0, ca, cb; + mpz_t temp[8]; + mp_result res; + + CHECK(a != NULL && b != NULL && c != NULL && + (x != NULL || y != NULL)); + + ca = CMPZ(a); + cb = CMPZ(b); + if(ca == 0 && cb == 0) + return MP_UNDEF; + else if(ca == 0) { + if((res = mp_int_abs(b, c)) != MP_OK) return res; + mp_int_zero(x); (void) mp_int_set_value(y, 1); return MP_OK; + } + else if(cb == 0) { + if((res = mp_int_abs(a, c)) != MP_OK) return res; + (void) mp_int_set_value(x, 1); mp_int_zero(y); return MP_OK; + } + + /* Initialize temporaries: + A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7 */ + for(last = 0; last < 4; ++last) { + if((res = mp_int_init(TEMP(last))) != MP_OK) + goto CLEANUP; + } + TEMP(0)->digits[0] = 1; + TEMP(3)->digits[0] = 1; + + SETUP(mp_int_init_copy(TEMP(4), a), last); + SETUP(mp_int_init_copy(TEMP(5), b), last); + + /* We will work with absolute values here */ + MP_SIGN(TEMP(4)) = MP_ZPOS; + MP_SIGN(TEMP(5)) = MP_ZPOS; + + { /* Divide out common factors of 2 from u and v */ + int div2_u = s_dp2k(TEMP(4)), div2_v = s_dp2k(TEMP(5)); + + k = MIN(div2_u, div2_v); + s_qdiv(TEMP(4), k); + s_qdiv(TEMP(5), k); + } + + SETUP(mp_int_init_copy(TEMP(6), TEMP(4)), last); + SETUP(mp_int_init_copy(TEMP(7), TEMP(5)), last); + + for(;;) { + while(mp_int_is_even(TEMP(4))) { + s_qdiv(TEMP(4), 1); + + if(mp_int_is_odd(TEMP(0)) || mp_int_is_odd(TEMP(1))) { + if((res = mp_int_add(TEMP(0), TEMP(7), TEMP(0))) != MP_OK) + goto CLEANUP; + if((res = mp_int_sub(TEMP(1), TEMP(6), TEMP(1))) != MP_OK) + goto CLEANUP; + } + + s_qdiv(TEMP(0), 1); + s_qdiv(TEMP(1), 1); + } + + while(mp_int_is_even(TEMP(5))) { + s_qdiv(TEMP(5), 1); + + if(mp_int_is_odd(TEMP(2)) || mp_int_is_odd(TEMP(3))) { + if((res = mp_int_add(TEMP(2), TEMP(7), TEMP(2))) != MP_OK) + goto CLEANUP; + if((res = mp_int_sub(TEMP(3), TEMP(6), TEMP(3))) != MP_OK) + goto CLEANUP; + } + + s_qdiv(TEMP(2), 1); + s_qdiv(TEMP(3), 1); + } + + if(mp_int_compare(TEMP(4), TEMP(5)) >= 0) { + if((res = mp_int_sub(TEMP(4), TEMP(5), TEMP(4))) != MP_OK) goto CLEANUP; + if((res = mp_int_sub(TEMP(0), TEMP(2), TEMP(0))) != MP_OK) goto CLEANUP; + if((res = mp_int_sub(TEMP(1), TEMP(3), TEMP(1))) != MP_OK) goto CLEANUP; + } + else { + if((res = mp_int_sub(TEMP(5), TEMP(4), TEMP(5))) != MP_OK) goto CLEANUP; + if((res = mp_int_sub(TEMP(2), TEMP(0), TEMP(2))) != MP_OK) goto CLEANUP; + if((res = mp_int_sub(TEMP(3), TEMP(1), TEMP(3))) != MP_OK) goto CLEANUP; + } + + if(CMPZ(TEMP(4)) == 0) { + if(x && (res = mp_int_copy(TEMP(2), x)) != MP_OK) goto CLEANUP; + if(y && (res = mp_int_copy(TEMP(3), y)) != MP_OK) goto CLEANUP; + if(c) { + if(!s_qmul(TEMP(5), k)) { + res = MP_MEMORY; + goto CLEANUP; + } + + res = mp_int_copy(TEMP(5), c); + } + + break; + } + } + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_divisible_value(a, v) */ + +int mp_int_divisible_value(mp_int a, int v) +{ + int rem = 0; + + if(mp_int_div_value(a, v, NULL, &rem) != MP_OK) + return 0; + + return rem == 0; +} + +/* }}} */ + +/* {{{ mp_int_is_pow2(z) */ + +int mp_int_is_pow2(mp_int z) +{ + CHECK(z != NULL); + + return s_isp2(z); +} + +/* }}} */ + +/* {{{ mp_int_sqrt(a, c) */ + +mp_result mp_int_sqrt(mp_int a, mp_int c) +{ + mp_result res = MP_OK; + mpz_t temp[2]; + int last = 0; + + CHECK(a != NULL && c != NULL); + + /* The square root of a negative value does not exist in the integers. */ + if(MP_SIGN(a) == MP_NEG) + return MP_UNDEF; + + SETUP(mp_int_init_copy(TEMP(last), a), last); + SETUP(mp_int_init(TEMP(last)), last); + + for(;;) { + if((res = mp_int_sqr(TEMP(0), TEMP(1))) != MP_OK) + goto CLEANUP; + + if(mp_int_compare_unsigned(a, TEMP(1)) == 0) break; + + if((res = mp_int_copy(a, TEMP(1))) != MP_OK) + goto CLEANUP; + if((res = mp_int_div(TEMP(1), TEMP(0), TEMP(1), NULL)) != MP_OK) + goto CLEANUP; + if((res = mp_int_add(TEMP(0), TEMP(1), TEMP(1))) != MP_OK) + goto CLEANUP; + if((res = mp_int_div_pow2(TEMP(1), 1, TEMP(1), NULL)) != MP_OK) + goto CLEANUP; + + if(mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0) break; + if((res = mp_int_sub_value(TEMP(0), 1, TEMP(0))) != MP_OK) goto CLEANUP; + if(mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0) break; + + if((res = mp_int_copy(TEMP(1), TEMP(0))) != MP_OK) goto CLEANUP; + } + + res = mp_int_copy(TEMP(0), c); + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_to_int(z, out) */ + +mp_result mp_int_to_int(mp_int z, int *out) +{ + unsigned int uv = 0; + mp_size uz; + mp_digit *dz; + mp_sign sz; + + CHECK(z != NULL); + + /* Make sure the value is representable as an int */ + sz = MP_SIGN(z); + if((sz == MP_ZPOS && mp_int_compare_value(z, INT_MAX) > 0) || + mp_int_compare_value(z, INT_MIN) < 0) + return MP_RANGE; + + uz = MP_USED(z); + dz = MP_DIGITS(z) + uz - 1; + + while(uz > 0) { + uv <<= MP_DIGIT_BIT/2; + uv = (uv << (MP_DIGIT_BIT/2)) | *dz--; + --uz; + } + + if(out) + *out = (sz == MP_NEG) ? -(int)uv : (int)uv; + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_to_string(z, radix, str, limit) */ + +mp_result mp_int_to_string(mp_int z, mp_size radix, + char *str, int limit) +{ + mp_result res; + int cmp = 0; + + CHECK(z != NULL && str != NULL && limit >= 2); + + if(radix < MP_MIN_RADIX || radix > MP_MAX_RADIX) + return MP_RANGE; + + if(CMPZ(z) == 0) { + *str++ = s_val2ch(0, mp_flags & MP_CAP_DIGITS); + } + else { + mpz_t tmp; + char *h, *t; + + if((res = mp_int_init_copy(&tmp, z)) != MP_OK) + return res; + + if(MP_SIGN(z) == MP_NEG) { + *str++ = '-'; + --limit; + } + h = str; + + /* Generate digits in reverse order until finished or limit reached */ + for(/* */; limit > 0; --limit) { + mp_digit d; + + if((cmp = CMPZ(&tmp)) == 0) + break; + + d = s_ddiv(&tmp, (mp_digit)radix); + *str++ = s_val2ch(d, mp_flags & MP_CAP_DIGITS); + } + t = str - 1; + + /* Put digits back in correct output order */ + while(h < t) { + char tc = *h; + *h++ = *t; + *t-- = tc; + } + + mp_int_clear(&tmp); + } + + *str = '\0'; + if(cmp == 0) + return MP_OK; + else + return MP_TRUNC; +} + +/* }}} */ + +/* {{{ mp_int_string_len(z, radix) */ + +mp_result mp_int_string_len(mp_int z, mp_size radix) +{ + int len; + + CHECK(z != NULL); + + if(radix < MP_MIN_RADIX || radix > MP_MAX_RADIX) + return MP_RANGE; + + len = s_outlen(z, radix) + 1; /* for terminator */ + + /* Allow for sign marker on negatives */ + if(MP_SIGN(z) == MP_NEG) + len += 1; + + return len; +} + +/* }}} */ + +/* {{{ mp_int_read_string(z, radix, *str) */ + +/* Read zero-terminated string into z */ +mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str) +{ + return mp_int_read_cstring(z, radix, str, NULL); + +} + +/* }}} */ + +/* {{{ mp_int_read_cstring(z, radix, *str, **end) */ + +mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end) +{ + int ch; + + CHECK(z != NULL && str != NULL); + + if(radix < MP_MIN_RADIX || radix > MP_MAX_RADIX) + return MP_RANGE; + + /* Skip leading whitespace */ + while(isspace((int)*str)) + ++str; + + /* Handle leading sign tag (+/-, positive default) */ + switch(*str) { + case '-': + MP_SIGN(z) = MP_NEG; + ++str; + break; + case '+': + ++str; /* fallthrough */ + default: + MP_SIGN(z) = MP_ZPOS; + break; + } + + /* Skip leading zeroes */ + while((ch = s_ch2val(*str, radix)) == 0) + ++str; + + /* Make sure there is enough space for the value */ + if(!s_pad(z, s_inlen(strlen(str), radix))) + return MP_MEMORY; + + MP_USED(z) = 1; z->digits[0] = 0; + + while(*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0)) { + s_dmul(z, (mp_digit)radix); + s_dadd(z, (mp_digit)ch); + ++str; + } + + CLAMP(z); + + /* Override sign for zero, even if negative specified. */ + if(CMPZ(z) == 0) + MP_SIGN(z) = MP_ZPOS; + + if(end != NULL) + *end = (char *)str; + + /* Return a truncation error if the string has unprocessed + characters remaining, so the caller can tell if the whole string + was done */ + if(*str != '\0') + return MP_TRUNC; + else + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_count_bits(z) */ + +mp_result mp_int_count_bits(mp_int z) +{ + mp_size nbits = 0, uz; + mp_digit d; + + CHECK(z != NULL); + + uz = MP_USED(z); + if(uz == 1 && z->digits[0] == 0) + return 1; + + --uz; + nbits = uz * MP_DIGIT_BIT; + d = z->digits[uz]; + + while(d != 0) { + d >>= 1; + ++nbits; + } + + return nbits; +} + +/* }}} */ + +/* {{{ mp_int_to_binary(z, buf, limit) */ + +mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit) +{ + static const int PAD_FOR_2C = 1; + + mp_result res; + int limpos = limit; + + CHECK(z != NULL && buf != NULL); + + res = s_tobin(z, buf, &limpos, PAD_FOR_2C); + + if(MP_SIGN(z) == MP_NEG) + s_2comp(buf, limpos); + + return res; +} + +/* }}} */ + +/* {{{ mp_int_read_binary(z, buf, len) */ + +mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len) +{ + mp_size need, i; + unsigned char *tmp; + mp_digit *dz; + + CHECK(z != NULL && buf != NULL && len > 0); + + /* Figure out how many digits are needed to represent this value */ + need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT; + if(!s_pad(z, need)) + return MP_MEMORY; + + mp_int_zero(z); + + /* If the high-order bit is set, take the 2's complement before + reading the value (it will be restored afterward) */ + if(buf[0] >> (CHAR_BIT - 1)) { + MP_SIGN(z) = MP_NEG; + s_2comp(buf, len); + } + + dz = MP_DIGITS(z); + for(tmp = buf, i = len; i > 0; --i, ++tmp) { + s_qmul(z, (mp_size) CHAR_BIT); + *dz |= *tmp; + } + + /* Restore 2's complement if we took it before */ + if(MP_SIGN(z) == MP_NEG) + s_2comp(buf, len); + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_binary_len(z) */ + +mp_result mp_int_binary_len(mp_int z) +{ + mp_result res = mp_int_count_bits(z); + int bytes = mp_int_unsigned_len(z); + + if(res <= 0) + return res; + + bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT; + + /* If the highest-order bit falls exactly on a byte boundary, we + need to pad with an extra byte so that the sign will be read + correctly when reading it back in. */ + if(bytes * CHAR_BIT == res) + ++bytes; + + return bytes; +} + +/* }}} */ + +/* {{{ mp_int_to_unsigned(z, buf, limit) */ + +mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit) +{ + static const int NO_PADDING = 0; + + CHECK(z != NULL && buf != NULL); + + return s_tobin(z, buf, &limit, NO_PADDING); +} + +/* }}} */ + +/* {{{ mp_int_read_unsigned(z, buf, len) */ + +mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len) +{ + mp_size need, i; + unsigned char *tmp; + mp_digit *dz; + + CHECK(z != NULL && buf != NULL && len > 0); + + /* Figure out how many digits are needed to represent this value */ + need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT; + if(!s_pad(z, need)) + return MP_MEMORY; + + mp_int_zero(z); + + dz = MP_DIGITS(z); + for(tmp = buf, i = len; i > 0; --i, ++tmp) { + (void) s_qmul(z, CHAR_BIT); + *dz |= *tmp; + } + + return MP_OK; +} + +/* }}} */ + +/* {{{ mp_int_unsigned_len(z) */ + +mp_result mp_int_unsigned_len(mp_int z) +{ + mp_result res = mp_int_count_bits(z); + int bytes; + + if(res <= 0) + return res; + + bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT; + + return bytes; +} + +/* }}} */ + +/* {{{ mp_error_string(res) */ + +const char *mp_error_string(mp_result res) +{ + int ix; + if(res > 0) + return s_unknown_err; + + res = -res; + for(ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix) + ; + + if(s_error_msg[ix] != NULL) + return s_error_msg[ix]; + else + return s_unknown_err; +} + +/* }}} */ + +/*------------------------------------------------------------------------*/ +/* Private functions for internal use. These make assumptions. */ + +/* {{{ s_alloc(num) */ + +static mp_digit *s_alloc(mp_size num) +{ + mp_digit *out = px_alloc(num * sizeof(mp_digit)); + + assert(out != NULL); /* for debugging */ + + return out; +} + +/* }}} */ + +/* {{{ s_realloc(old, num) */ + +static mp_digit *s_realloc(mp_digit *old, mp_size num) +{ + mp_digit *new = px_realloc(old, num * sizeof(mp_digit)); + + assert(new != NULL); /* for debugging */ + + return new; +} + +/* }}} */ + +/* {{{ s_free(ptr) */ + +#if TRACEABLE_FREE +static void s_free(void *ptr) +{ + px_free(ptr); +} +#endif + +/* }}} */ + +/* {{{ s_pad(z, min) */ + +static int s_pad(mp_int z, mp_size min) +{ + if(MP_ALLOC(z) < min) { + mp_size nsize = ROUND_PREC(min); + mp_digit *tmp = s_realloc(MP_DIGITS(z), nsize); + + if(tmp == NULL) + return 0; + + MP_DIGITS(z) = tmp; + MP_ALLOC(z) = nsize; + } + + return 1; +} + +/* }}} */ + +/* {{{ s_clamp(z) */ + +#if TRACEABLE_CLAMP +static void s_clamp(mp_int z) +{ + mp_size uz = MP_USED(z); + mp_digit *zd = MP_DIGITS(z) + uz - 1; + + while(uz > 1 && (*zd-- == 0)) + --uz; + + MP_USED(z) = uz; +} +#endif + +/* }}} */ + +/* {{{ s_fake(z, value, vbuf) */ + +static void s_fake(mp_int z, int value, mp_digit vbuf[]) +{ + mp_size uv = (mp_size)s_vpack(value, vbuf); + + z->used = uv; + z->alloc = MP_VALUE_DIGITS(value); + z->sign = (value < 0) ? MP_NEG : MP_ZPOS; + z->digits = vbuf; +} + +/* }}} */ + +/* {{{ s_cdig(da, db, len) */ + +static int s_cdig(mp_digit *da, mp_digit *db, mp_size len) +{ + mp_digit *dat = da + len - 1, *dbt = db + len - 1; + + for(/* */; len != 0; --len, --dat, --dbt) { + if(*dat > *dbt) + return 1; + else if(*dat < *dbt) + return -1; + } + + return 0; +} + +/* }}} */ + +/* {{{ s_vpack(v, t[]) */ + +static int s_vpack(int v, mp_digit t[]) +{ + unsigned int uv = (unsigned int)((v < 0) ? -v : v); + int ndig = 0; + + if(uv == 0) + t[ndig++] = 0; + else { + while(uv != 0) { + t[ndig++] = (mp_digit) uv; + uv >>= MP_DIGIT_BIT/2; + uv >>= MP_DIGIT_BIT/2; + } + } + + return ndig; +} + +/* }}} */ + +/* {{{ s_ucmp(a, b) */ + +static int s_ucmp(mp_int a, mp_int b) +{ + mp_size ua = MP_USED(a), ub = MP_USED(b); + + if(ua > ub) + return 1; + else if(ub > ua) + return -1; + else + return s_cdig(MP_DIGITS(a), MP_DIGITS(b), ua); +} + +/* }}} */ + +/* {{{ s_vcmp(a, v) */ + +static int s_vcmp(mp_int a, int v) +{ + mp_digit vdig[MP_VALUE_DIGITS(v)]; + int ndig = 0; + mp_size ua = MP_USED(a); + + ndig = s_vpack(v, vdig); + + if(ua > ndig) + return 1; + else if(ua < ndig) + return -1; + else + return s_cdig(MP_DIGITS(a), vdig, ndig); +} + +/* }}} */ + +/* {{{ s_uadd(da, db, dc, size_a, size_b) */ + +static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b) +{ + mp_size pos; + mp_word w = 0; + + /* Insure that da is the longer of the two to simplify later code */ + if(size_b > size_a) { + SWAP(mp_digit *, da, db); + SWAP(mp_size, size_a, size_b); + } + + /* Add corresponding digits until the shorter number runs out */ + for(pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) { + w = w + (mp_word)*da + (mp_word)*db; + *dc = LOWER_HALF(w); + w = UPPER_HALF(w); + } + + /* Propagate carries as far as necessary */ + for(/* */; pos < size_a; ++pos, ++da, ++dc) { + w = w + *da; + + *dc = LOWER_HALF(w); + w = UPPER_HALF(w); + } + + /* Return carry out */ + return (mp_digit)w; +} + +/* }}} */ + +/* {{{ s_usub(da, db, dc, size_a, size_b) */ + +static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b) +{ + mp_size pos; + mp_word w = 0; + + /* We assume that |a| >= |b| so this should definitely hold */ + assert(size_a >= size_b); + + /* Subtract corresponding digits and propagate borrow */ + for(pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) { + w = ((mp_word)MP_DIGIT_MAX + 1 + /* MP_RADIX */ + (mp_word)*da) - w - (mp_word)*db; + + *dc = LOWER_HALF(w); + w = (UPPER_HALF(w) == 0); + } + + /* Finish the subtraction for remaining upper digits of da */ + for(/* */; pos < size_a; ++pos, ++da, ++dc) { + w = ((mp_word)MP_DIGIT_MAX + 1 + /* MP_RADIX */ + (mp_word)*da) - w; + + *dc = LOWER_HALF(w); + w = (UPPER_HALF(w) == 0); + } + + /* If there is a borrow out at the end, it violates the precondition */ + assert(w == 0); +} + +/* }}} */ + +/* {{{ s_kmul(da, db, dc, size_a, size_b) */ + +static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b) +{ + mp_size bot_size; + + /* Make sure b is the smaller of the two input values */ + if(size_b > size_a) { + SWAP(mp_digit *, da, db); + SWAP(mp_size, size_a, size_b); + } + + /* Insure that the bottom is the larger half in an odd-length split; + the code below relies on this being true. + */ + bot_size = (size_a + 1) / 2; + + /* If the values are big enough to bother with recursion, use the + Karatsuba algorithm to compute the product; otherwise use the + normal multiplication algorithm + */ + if(multiply_threshold && + size_a >= multiply_threshold && + size_b > bot_size) { + + mp_digit *t1, *t2, *t3, carry; + + mp_digit *a_top = da + bot_size; + mp_digit *b_top = db + bot_size; + + mp_size at_size = size_a - bot_size; + mp_size bt_size = size_b - bot_size; + mp_size buf_size = 2 * bot_size; + + /* Do a single allocation for all three temporary buffers needed; + each buffer must be big enough to hold the product of two + bottom halves, and one buffer needs space for the completed + product; twice the space is plenty. + */ + if((t1 = s_alloc(4 * buf_size)) == NULL) return 0; + t2 = t1 + buf_size; + t3 = t2 + buf_size; + ZERO(t1, 4 * buf_size); + + /* t1 and t2 are initially used as temporaries to compute the inner product + (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0 + */ + carry = s_uadd(da, a_top, t1, bot_size, at_size); /* t1 = a1 + a0 */ + t1[bot_size] = carry; + + carry = s_uadd(db, b_top, t2, bot_size, bt_size); /* t2 = b1 + b0 */ + t2[bot_size] = carry; + + (void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1); /* t3 = t1 * t2 */ + + /* Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so that + we're left with only the pieces we want: t3 = a1b0 + a0b1 + */ + ZERO(t1, bot_size + 1); + ZERO(t2, bot_size + 1); + (void) s_kmul(da, db, t1, bot_size, bot_size); /* t1 = a0 * b0 */ + (void) s_kmul(a_top, b_top, t2, at_size, bt_size); /* t2 = a1 * b1 */ + + /* Subtract out t1 and t2 to get the inner product */ + s_usub(t3, t1, t3, buf_size + 2, buf_size); + s_usub(t3, t2, t3, buf_size + 2, buf_size); + + /* Assemble the output value */ + COPY(t1, dc, buf_size); + (void) s_uadd(t3, dc + bot_size, dc + bot_size, + buf_size + 1, buf_size + 1); + + (void) s_uadd(t2, dc + 2*bot_size, dc + 2*bot_size, + buf_size, buf_size); + + s_free(t1); /* note t2 and t3 are just internal pointers to t1 */ + } + else { + s_umul(da, db, dc, size_a, size_b); + } + + return 1; +} + +/* }}} */ + +/* {{{ s_umul(da, db, dc, size_a, size_b) */ + +static void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, + mp_size size_a, mp_size size_b) +{ + mp_size a, b; + mp_word w; + + for(a = 0; a < size_a; ++a, ++dc, ++da) { + mp_digit *dct = dc; + mp_digit *dbt = db; + + if(*da == 0) + continue; + + w = 0; + for(b = 0; b < size_b; ++b, ++dbt, ++dct) { + w = (mp_word)*da * (mp_word)*dbt + w + (mp_word)*dct; + + *dct = LOWER_HALF(w); + w = UPPER_HALF(w); + } + + *dct = (mp_digit)w; + } +} + +/* }}} */ + +/* {{{ s_ksqr(da, dc, size_a) */ + +static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a) +{ + if(multiply_threshold && size_a > multiply_threshold) { + mp_size bot_size = (size_a + 1) / 2; + mp_digit *a_top = da + bot_size; + mp_digit *t1, *t2, *t3; + mp_size at_size = size_a - bot_size; + mp_size buf_size = 2 * bot_size; + + if((t1 = s_alloc(4 * buf_size)) == NULL) return 0; + t2 = t1 + buf_size; + t3 = t2 + buf_size; + ZERO(t1, 4 * buf_size); + + (void) s_ksqr(da, t1, bot_size); /* t1 = a0 ^ 2 */ + (void) s_ksqr(a_top, t2, at_size); /* t2 = a1 ^ 2 */ + + (void) s_kmul(da, a_top, t3, bot_size, at_size); /* t3 = a0 * a1 */ + + /* Quick multiply t3 by 2, shifting left (can't overflow) */ + { + int i, top = bot_size + at_size; + mp_word w, save = 0; + + for(i = 0; i < top; ++i) { + w = t3[i]; + w = (w << 1) | save; + t3[i] = LOWER_HALF(w); + save = UPPER_HALF(w); + } + t3[i] = LOWER_HALF(save); + } + + /* Assemble the output value */ + COPY(t1, dc, 2 * bot_size); + (void) s_uadd(t3, dc + bot_size, dc + bot_size, + buf_size + 1, buf_size + 1); + + (void) s_uadd(t2, dc + 2*bot_size, dc + 2*bot_size, + buf_size, buf_size); + + px_free(t1); /* note that t2 and t2 are internal pointers only */ + + } + else { + s_usqr(da, dc, size_a); + } + + return 1; +} + +/* }}} */ + +/* {{{ s_usqr(da, dc, size_a) */ + +static void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a) +{ + mp_size i, j; + mp_word w; + + for(i = 0; i < size_a; ++i, dc += 2, ++da) { + mp_digit *dct = dc, *dat = da; + + if(*da == 0) + continue; + + /* Take care of the first digit, no rollover */ + w = (mp_word)*dat * (mp_word)*dat + (mp_word)*dct; + *dct = LOWER_HALF(w); + w = UPPER_HALF(w); + ++dat; ++dct; + + for(j = i + 1; j < size_a; ++j, ++dat, ++dct) { + mp_word t = (mp_word)*da * (mp_word)*dat; + mp_word u = w + (mp_word)*dct, ov = 0; + + /* Check if doubling t will overflow a word */ + if(HIGH_BIT_SET(t)) + ov = 1; + + w = t + t; + + /* Check if adding u to w will overflow a word */ + if(ADD_WILL_OVERFLOW(w, u)) + ov = 1; + + w += u; + + *dct = LOWER_HALF(w); + w = UPPER_HALF(w); + if(ov) { + w += MP_DIGIT_MAX; /* MP_RADIX */ + ++w; + } + } + + w = w + *dct; + *dct = (mp_digit)w; + while((w = UPPER_HALF(w)) != 0) { + ++dct; w = w + *dct; + *dct = LOWER_HALF(w); + } + + assert(w == 0); + } +} + +/* }}} */ + +/* {{{ s_dadd(a, b) */ + +static void s_dadd(mp_int a, mp_digit b) +{ + mp_word w = 0; + mp_digit *da = MP_DIGITS(a); + mp_size ua = MP_USED(a); + + w = (mp_word)*da + b; + *da++ = LOWER_HALF(w); + w = UPPER_HALF(w); + + for(ua -= 1; ua > 0; --ua, ++da) { + w = (mp_word)*da + w; + + *da = LOWER_HALF(w); + w = UPPER_HALF(w); + } + + if(w) { + *da = (mp_digit)w; + MP_USED(a) += 1; + } +} + +/* }}} */ + +/* {{{ s_dmul(a, b) */ + +static void s_dmul(mp_int a, mp_digit b) +{ + mp_word w = 0; + mp_digit *da = MP_DIGITS(a); + mp_size ua = MP_USED(a); + + while(ua > 0) { + w = (mp_word)*da * b + w; + *da++ = LOWER_HALF(w); + w = UPPER_HALF(w); + --ua; + } + + if(w) { + *da = (mp_digit)w; + MP_USED(a) += 1; + } +} + +/* }}} */ + +/* {{{ s_dbmul(da, b, dc, size_a) */ + +static void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, mp_size size_a) +{ + mp_word w = 0; + + while(size_a > 0) { + w = (mp_word)*da++ * (mp_word)b + w; + + *dc++ = LOWER_HALF(w); + w = UPPER_HALF(w); + --size_a; + } + + if(w) + *dc = LOWER_HALF(w); +} + +/* }}} */ + +/* {{{ s_ddiv(da, d, dc, size_a) */ + +static mp_digit s_ddiv(mp_int a, mp_digit b) +{ + mp_word w = 0, qdigit; + mp_size ua = MP_USED(a); + mp_digit *da = MP_DIGITS(a) + ua - 1; + + for(/* */; ua > 0; --ua, --da) { + w = (w << MP_DIGIT_BIT) | *da; + + if(w >= b) { + qdigit = w / b; + w = w % b; + } + else { + qdigit = 0; + } + + *da = (mp_digit)qdigit; + } + + CLAMP(a); + return (mp_digit)w; +} + +/* }}} */ + +/* {{{ s_qdiv(z, p2) */ + +static void s_qdiv(mp_int z, mp_size p2) +{ + mp_size ndig = p2 / MP_DIGIT_BIT, nbits = p2 % MP_DIGIT_BIT; + mp_size uz = MP_USED(z); + + if(ndig) { + mp_size mark; + mp_digit *to, *from; + + if(ndig >= uz) { + mp_int_zero(z); + return; + } + + to = MP_DIGITS(z); from = to + ndig; + + for(mark = ndig; mark < uz; ++mark) + *to++ = *from++; + + MP_USED(z) = uz - ndig; + } + + if(nbits) { + mp_digit d = 0, *dz, save; + mp_size up = MP_DIGIT_BIT - nbits; + + uz = MP_USED(z); + dz = MP_DIGITS(z) + uz - 1; + + for(/* */; uz > 0; --uz, --dz) { + save = *dz; + + *dz = (*dz >> nbits) | (d << up); + d = save; + } + + CLAMP(z); + } + + if(MP_USED(z) == 1 && z->digits[0] == 0) + MP_SIGN(z) = MP_ZPOS; +} + +/* }}} */ + +/* {{{ s_qmod(z, p2) */ + +static void s_qmod(mp_int z, mp_size p2) +{ + mp_size start = p2 / MP_DIGIT_BIT + 1, rest = p2 % MP_DIGIT_BIT; + mp_size uz = MP_USED(z); + mp_digit mask = (1 << rest) - 1; + + if(start <= uz) { + MP_USED(z) = start; + z->digits[start - 1] &= mask; + CLAMP(z); + } +} + +/* }}} */ + +/* {{{ s_qmul(z, p2) */ + +static int s_qmul(mp_int z, mp_size p2) +{ + mp_size uz, need, rest, extra, i; + mp_digit *from, *to, d; + + if(p2 == 0) + return 1; + + uz = MP_USED(z); + need = p2 / MP_DIGIT_BIT; rest = p2 % MP_DIGIT_BIT; + + /* Figure out if we need an extra digit at the top end; this occurs + if the topmost `rest' bits of the high-order digit of z are not + zero, meaning they will be shifted off the end if not preserved */ + extra = 0; + if(rest != 0) { + mp_digit *dz = MP_DIGITS(z) + uz - 1; + + if((*dz >> (MP_DIGIT_BIT - rest)) != 0) + extra = 1; + } + + if(!s_pad(z, uz + need + extra)) + return 0; + + /* If we need to shift by whole digits, do that in one pass, then + to back and shift by partial digits. + */ + if(need > 0) { + from = MP_DIGITS(z) + uz - 1; + to = from + need; + + for(i = 0; i < uz; ++i) + *to-- = *from--; + + ZERO(MP_DIGITS(z), need); + uz += need; + } + + if(rest) { + d = 0; + for(i = need, from = MP_DIGITS(z) + need; i < uz; ++i, ++from) { + mp_digit save = *from; + + *from = (*from << rest) | (d >> (MP_DIGIT_BIT - rest)); + d = save; + } + + d >>= (MP_DIGIT_BIT - rest); + if(d != 0) { + *from = d; + uz += extra; + } + } + + MP_USED(z) = uz; + CLAMP(z); + + return 1; +} + +/* }}} */ + +/* {{{ s_qsub(z, p2) */ + +/* Subtract |z| from 2^p2, assuming 2^p2 > |z|, and set z to be positive */ +static int s_qsub(mp_int z, mp_size p2) +{ + mp_digit hi = (1 << (p2 % MP_DIGIT_BIT)), *zp; + mp_size tdig = (p2 / MP_DIGIT_BIT), pos; + mp_word w = 0; + + if(!s_pad(z, tdig + 1)) + return 0; + + for(pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp) { + w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word)*zp; + + *zp = LOWER_HALF(w); + w = UPPER_HALF(w) ? 0 : 1; + } + + w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word)*zp; + *zp = LOWER_HALF(w); + + assert(UPPER_HALF(w) != 0); /* no borrow out should be possible */ + + MP_SIGN(z) = MP_ZPOS; + CLAMP(z); + + return 1; +} + +/* }}} */ + +/* {{{ s_dp2k(z) */ + +static int s_dp2k(mp_int z) +{ + int k = 0; + mp_digit *dp = MP_DIGITS(z), d; + + if(MP_USED(z) == 1 && *dp == 0) + return 1; + + while(*dp == 0) { + k += MP_DIGIT_BIT; + ++dp; + } + + d = *dp; + while((d & 1) == 0) { + d >>= 1; + ++k; + } + + return k; +} + +/* }}} */ + +/* {{{ s_isp2(z) */ + +static int s_isp2(mp_int z) +{ + mp_size uz = MP_USED(z), k = 0; + mp_digit *dz = MP_DIGITS(z), d; + + while(uz > 1) { + if(*dz++ != 0) + return -1; + k += MP_DIGIT_BIT; + --uz; + } + + d = *dz; + while(d > 1) { + if(d & 1) + return -1; + ++k; d >>= 1; + } + + return (int) k; +} + +/* }}} */ + +/* {{{ s_2expt(z, k) */ + +static int s_2expt(mp_int z, int k) +{ + mp_size ndig, rest; + mp_digit *dz; + + ndig = (k + MP_DIGIT_BIT) / MP_DIGIT_BIT; + rest = k % MP_DIGIT_BIT; + + if(!s_pad(z, ndig)) + return 0; + + dz = MP_DIGITS(z); + ZERO(dz, ndig); + *(dz + ndig - 1) = (1 << rest); + MP_USED(z) = ndig; + + return 1; +} + +/* }}} */ + +/* {{{ s_norm(a, b) */ + +static int s_norm(mp_int a, mp_int b) +{ + mp_digit d = b->digits[MP_USED(b) - 1]; + int k = 0; + + while(d < (mp_digit) (1 << (MP_DIGIT_BIT - 1))) { /* d < (MP_RADIX / 2) */ + d <<= 1; + ++k; + } + + /* These multiplications can't fail */ + if(k != 0) { + (void) s_qmul(a, (mp_size) k); + (void) s_qmul(b, (mp_size) k); + } + + return k; +} + +/* }}} */ + +/* {{{ s_brmu(z, m) */ + +static mp_result s_brmu(mp_int z, mp_int m) +{ + mp_size um = MP_USED(m) * 2; + + if(!s_pad(z, um)) + return MP_MEMORY; + + s_2expt(z, MP_DIGIT_BIT * um); + return mp_int_div(z, m, z, NULL); +} + +/* }}} */ + +/* {{{ s_reduce(x, m, mu, q1, q2) */ + +static int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2) +{ + mp_size um = MP_USED(m), umb_p1, umb_m1; + + umb_p1 = (um + 1) * MP_DIGIT_BIT; + umb_m1 = (um - 1) * MP_DIGIT_BIT; + + if(mp_int_copy(x, q1) != MP_OK) + return 0; + + /* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */ + s_qdiv(q1, umb_m1); + UMUL(q1, mu, q2); + s_qdiv(q2, umb_p1); + + /* Set x = x mod b^(k+1) */ + s_qmod(x, umb_p1); + + /* Now, q is a guess for the quotient a / m. + Compute x - q * m mod b^(k+1), replacing x. This may be off + by a factor of 2m, but no more than that. + */ + UMUL(q2, m, q1); + s_qmod(q1, umb_p1); + (void) mp_int_sub(x, q1, x); /* can't fail */ + + /* The result may be < 0; if it is, add b^(k+1) to pin it in the + proper range. */ + if((CMPZ(x) < 0) && !s_qsub(x, umb_p1)) + return 0; + + /* If x > m, we need to back it off until it is in range. + This will be required at most twice. */ + if(mp_int_compare(x, m) >= 0) + (void) mp_int_sub(x, m, x); + if(mp_int_compare(x, m) >= 0) + (void) mp_int_sub(x, m, x); + + /* At this point, x has been properly reduced. */ + return 1; +} + +/* }}} */ + +/* {{{ s_embar(a, b, m, mu, c) */ + +/* Perform modular exponentiation using Barrett's method, where mu is + the reduction constant for m. Assumes a < m, b > 0. */ +static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c) +{ + mp_digit *db, *dbt, umu, d; + mpz_t temp[3]; + mp_result res; + int last = 0; + + umu = MP_USED(mu); db = MP_DIGITS(b); dbt = db + MP_USED(b) - 1; + + while(last < 3) + SETUP(mp_int_init_size(TEMP(last), 2 * umu), last); + + (void) mp_int_set_value(c, 1); + + /* Take care of low-order digits */ + while(db < dbt) { + int i; + + for(d = *db, i = MP_DIGIT_BIT; i > 0; --i, d >>= 1) { + if(d & 1) { + /* The use of a second temporary avoids allocation */ + UMUL(c, a, TEMP(0)); + if(!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2))) { + res = MP_MEMORY; goto CLEANUP; + } + mp_int_copy(TEMP(0), c); + } + + + USQR(a, TEMP(0)); + assert(MP_SIGN(TEMP(0)) == MP_ZPOS); + if(!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2))) { + res = MP_MEMORY; goto CLEANUP; + } + assert(MP_SIGN(TEMP(0)) == MP_ZPOS); + mp_int_copy(TEMP(0), a); + + + } + + ++db; + } + + /* Take care of highest-order digit */ + d = *dbt; + for(;;) { + if(d & 1) { + UMUL(c, a, TEMP(0)); + if(!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2))) { + res = MP_MEMORY; goto CLEANUP; + } + mp_int_copy(TEMP(0), c); + } + + d >>= 1; + if(!d) break; + + USQR(a, TEMP(0)); + if(!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2))) { + res = MP_MEMORY; goto CLEANUP; + } + (void) mp_int_copy(TEMP(0), a); + } + + CLEANUP: + while(--last >= 0) + mp_int_clear(TEMP(last)); + + return res; +} + +/* }}} */ + +/* {{{ s_udiv(a, b) */ + +/* Precondition: a >= b and b > 0 + Postcondition: a' = a / b, b' = a % b + */ +static mp_result s_udiv(mp_int a, mp_int b) +{ + mpz_t q, r, t; + mp_size ua, ub, qpos = 0; + mp_digit *da, btop; + mp_result res = MP_OK; + int k, skip = 0; + + /* Force signs to positive */ + MP_SIGN(a) = MP_ZPOS; + MP_SIGN(b) = MP_ZPOS; + + /* Normalize, per Knuth */ + k = s_norm(a, b); + + ua = MP_USED(a); ub = MP_USED(b); btop = b->digits[ub - 1]; + if((res = mp_int_init_size(&q, ua)) != MP_OK) return res; + if((res = mp_int_init_size(&t, ua + 1)) != MP_OK) goto CLEANUP; + + da = MP_DIGITS(a); + r.digits = da + ua - 1; /* The contents of r are shared with a */ + r.used = 1; + r.sign = MP_ZPOS; + r.alloc = MP_ALLOC(a); + ZERO(t.digits, t.alloc); + + /* Solve for quotient digits, store in q.digits in reverse order */ + while(r.digits >= da) { + assert(qpos <= q.alloc); + + if(s_ucmp(b, &r) > 0) { + r.digits -= 1; + r.used += 1; + + if(++skip > 1) + q.digits[qpos++] = 0; + + CLAMP(&r); + } + else { + mp_word pfx = r.digits[r.used - 1]; + mp_word qdigit; + + if(r.used > 1 && (pfx < btop || r.digits[r.used - 2] == 0)) { + pfx <<= MP_DIGIT_BIT / 2; + pfx <<= MP_DIGIT_BIT / 2; + pfx |= r.digits[r.used - 2]; + } + + qdigit = pfx / btop; + if(qdigit > MP_DIGIT_MAX) + qdigit = 1; + + s_dbmul(MP_DIGITS(b), (mp_digit) qdigit, t.digits, ub); + t.used = ub + 1; CLAMP(&t); + while(s_ucmp(&t, &r) > 0) { + --qdigit; + (void) mp_int_sub(&t, b, &t); /* cannot fail */ + } + + s_usub(r.digits, t.digits, r.digits, r.used, t.used); + CLAMP(&r); + + q.digits[qpos++] = (mp_digit) qdigit; + ZERO(t.digits, t.used); + skip = 0; + } + } + + /* Put quotient digits in the correct order, and discard extra zeroes */ + q.used = qpos; + REV(mp_digit, q.digits, qpos); + CLAMP(&q); + + /* Denormalize the remainder */ + CLAMP(a); + if(k != 0) + s_qdiv(a, k); + + mp_int_copy(a, b); /* ok: 0 <= r < b */ + mp_int_copy(&q, a); /* ok: q <= a */ + + mp_int_clear(&t); + CLEANUP: + mp_int_clear(&q); + return res; +} + +/* }}} */ + +/* {{{ s_outlen(z, r) */ + +/* Precondition: 2 <= r < 64 */ +static int s_outlen(mp_int z, mp_size r) +{ + mp_result bits; + double raw; + + bits = mp_int_count_bits(z); + raw = (double)bits * s_log2[r]; + + return (int)(raw + 0.999999); +} + +/* }}} */ + +/* {{{ s_inlen(len, r) */ + +static mp_size s_inlen(int len, mp_size r) +{ + double raw = (double)len / s_log2[r]; + mp_size bits = (mp_size)(raw + 0.5); + + return (mp_size)((bits + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT); +} + +/* }}} */ + +/* {{{ s_ch2val(c, r) */ + +static int s_ch2val(char c, int r) +{ + int out; + + if(isdigit((int)c)) + out = c - '0'; + else if(r > 10 && isalpha((int)c)) + out = toupper(c) - 'A' + 10; + else + return -1; + + return (out >= r) ? -1 : out; +} + +/* }}} */ + +/* {{{ s_val2ch(v, caps) */ + +static char s_val2ch(int v, int caps) +{ + assert(v >= 0); + + if(v < 10) + return v + '0'; + else { + char out = (v - 10) + 'a'; + + if(caps) + return toupper(out); + else + return out; + } +} + +/* }}} */ + +/* {{{ s_2comp(buf, len) */ + +static void s_2comp(unsigned char *buf, int len) +{ + int i; + unsigned short s = 1; + + for(i = len - 1; i >= 0; --i) { + unsigned char c = ~buf[i]; + + s = c + s; + c = s & UCHAR_MAX; + s >>= CHAR_BIT; + + buf[i] = c; + } + + /* last carry out is ignored */ +} + +/* }}} */ + +/* {{{ s_tobin(z, buf, *limpos) */ + +static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad) +{ + mp_size uz; + mp_digit *dz; + int pos = 0, limit = *limpos; + + uz = MP_USED(z); dz = MP_DIGITS(z); + while(uz > 0 && pos < limit) { + mp_digit d = *dz++; + int i; + + for(i = sizeof(mp_digit); i > 0 && pos < limit; --i) { + buf[pos++] = (unsigned char)d; + d >>= CHAR_BIT; + + /* Don't write leading zeroes */ + if(d == 0 && uz == 1) + i = 0; /* exit loop without signaling truncation */ + } + + /* Detect truncation (loop exited with pos >= limit) */ + if(i > 0) break; + + --uz; + } + + if(pad != 0 && (buf[pos - 1] >> (CHAR_BIT - 1))) { + if(pos < limit) + buf[pos++] = 0; + else + uz = 1; + } + + /* Digits are in reverse order, fix that */ + REV(unsigned char, buf, pos); + + /* Return the number of bytes actually written */ + *limpos = pos; + + return (uz == 0) ? MP_OK : MP_TRUNC; +} + +/* }}} */ + +/* {{{ s_print(tag, z) */ + +#if 0 +void s_print(char *tag, mp_int z) +{ + int i; + + fprintf(stderr, "%s: %c ", tag, + (MP_SIGN(z) == MP_NEG) ? '-' : '+'); + + for(i = MP_USED(z) - 1; i >= 0; --i) + fprintf(stderr, "%0*X", (int)(MP_DIGIT_BIT / 4), z->digits[i]); + + fputc('\n', stderr); + +} + +void s_print_buf(char *tag, mp_digit *buf, mp_size num) +{ + int i; + + fprintf(stderr, "%s: ", tag); + + for(i = num - 1; i >= 0; --i) + fprintf(stderr, "%0*X", (int)(MP_DIGIT_BIT / 4), buf[i]); + + fputc('\n', stderr); +} +#endif + +/* }}} */ + +/* HERE THERE BE DRAGONS */ diff --git a/contrib/pgcrypto/imath.h b/contrib/pgcrypto/imath.h new file mode 100644 index 00000000000..150c9e4047f --- /dev/null +++ b/contrib/pgcrypto/imath.h @@ -0,0 +1,212 @@ +/* + Name: imath.h + Purpose: Arbitrary precision integer arithmetic routines. + Author: M. J. Fromberger <http://www.dartmouth.edu/~sting/> + Info: $Id: imath.h,v 1.1 2006/07/13 04:15:24 neilc Exp $ + + Copyright (C) 2002 Michael J. Fromberger, All Rights Reserved. + + Permission is hereby granted, free of charge, to any person + obtaining a copy of this software and associated documentation files + (the "Software"), to deal in the Software without restriction, + including without limitation the rights to use, copy, modify, merge, + publish, distribute, sublicense, and/or sell copies of the Software, + and to permit persons to whom the Software is furnished to do so, + subject to the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. + */ + +#ifndef IMATH_H_ +#define IMATH_H_ + +/* use always 32bit digits - should some arch use 16bit digits? */ +#define USE_LONG_LONG + +#include <limits.h> + +typedef unsigned char mp_sign; +typedef unsigned int mp_size; +typedef int mp_result; +#ifdef USE_LONG_LONG +typedef unsigned int mp_digit; +typedef unsigned long long mp_word; +#else +typedef unsigned short mp_digit; +typedef unsigned int mp_word; +#endif + +typedef struct mpz { + mp_digit *digits; + mp_size alloc; + mp_size used; + mp_sign sign; +} mpz_t, *mp_int; + +#define MP_DIGITS(Z) ((Z)->digits) +#define MP_ALLOC(Z) ((Z)->alloc) +#define MP_USED(Z) ((Z)->used) +#define MP_SIGN(Z) ((Z)->sign) + +extern const mp_result MP_OK; +extern const mp_result MP_FALSE; +extern const mp_result MP_TRUE; +extern const mp_result MP_MEMORY; +extern const mp_result MP_RANGE; +extern const mp_result MP_UNDEF; +extern const mp_result MP_TRUNC; +extern const mp_result MP_BADARG; + +#define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT) +#define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT) + +#ifdef USE_LONG_LONG +# ifndef ULONG_LONG_MAX +# ifdef ULLONG_MAX +# define ULONG_LONG_MAX ULLONG_MAX +# else +# error "Maximum value of unsigned long long not defined!" +# endif +# endif +# define MP_DIGIT_MAX (ULONG_MAX * 1ULL) +# define MP_WORD_MAX ULONG_LONG_MAX +#else +# define MP_DIGIT_MAX (USHRT_MAX * 1UL) +# define MP_WORD_MAX (UINT_MAX * 1UL) +#endif + +#define MP_MIN_RADIX 2 +#define MP_MAX_RADIX 36 + +extern const mp_sign MP_NEG; +extern const mp_sign MP_ZPOS; + +#define mp_int_is_odd(Z) ((Z)->digits[0] & 1) +#define mp_int_is_even(Z) !((Z)->digits[0] & 1) + +mp_size mp_get_default_precision(void); +void mp_set_default_precision(mp_size s); +mp_size mp_get_multiply_threshold(void); +void mp_set_multiply_threshold(mp_size s); + +mp_result mp_int_init(mp_int z); +mp_int mp_int_alloc(void); +mp_result mp_int_init_size(mp_int z, mp_size prec); +mp_result mp_int_init_copy(mp_int z, mp_int old); +mp_result mp_int_init_value(mp_int z, int value); +mp_result mp_int_set_value(mp_int z, int value); +void mp_int_clear(mp_int z); +void mp_int_free(mp_int z); + +mp_result mp_int_copy(mp_int a, mp_int c); /* c = a */ +void mp_int_swap(mp_int a, mp_int c); /* swap a, c */ +void mp_int_zero(mp_int z); /* z = 0 */ +mp_result mp_int_abs(mp_int a, mp_int c); /* c = |a| */ +mp_result mp_int_neg(mp_int a, mp_int c); /* c = -a */ +mp_result mp_int_add(mp_int a, mp_int b, mp_int c); /* c = a + b */ +mp_result mp_int_add_value(mp_int a, int value, mp_int c); +mp_result mp_int_sub(mp_int a, mp_int b, mp_int c); /* c = a - b */ +mp_result mp_int_sub_value(mp_int a, int value, mp_int c); +mp_result mp_int_mul(mp_int a, mp_int b, mp_int c); /* c = a * b */ +mp_result mp_int_mul_value(mp_int a, int value, mp_int c); +mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c); +mp_result mp_int_sqr(mp_int a, mp_int c); /* c = a * a */ +mp_result mp_int_div(mp_int a, mp_int b, /* q = a / b */ + mp_int q, mp_int r); /* r = a % b */ +mp_result mp_int_div_value(mp_int a, int value, /* q = a / value */ + mp_int q, int *r); /* r = a % value */ +mp_result mp_int_div_pow2(mp_int a, int p2, /* q = a / 2^p2 */ + mp_int q, mp_int r); /* r = q % 2^p2 */ +mp_result mp_int_mod(mp_int a, mp_int m, mp_int c); /* c = a % m */ +#define mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R)) +mp_result mp_int_expt(mp_int a, int b, mp_int c); /* c = a^b */ +mp_result mp_int_expt_value(int a, int b, mp_int c); /* c = a^b */ + +int mp_int_compare(mp_int a, mp_int b); /* a <=> b */ +int mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */ +int mp_int_compare_zero(mp_int z); /* a <=> 0 */ +int mp_int_compare_value(mp_int z, int value); /* a <=> v */ + +/* Returns true if v|a, false otherwise (including errors) */ +int mp_int_divisible_value(mp_int a, int v); + +/* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */ +int mp_int_is_pow2(mp_int z); + +mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, + mp_int c); /* c = a^b (mod m) */ +mp_result mp_int_exptmod_evalue(mp_int a, int value, + mp_int m, mp_int c); /* c = a^v (mod m) */ +mp_result mp_int_exptmod_bvalue(int value, mp_int b, + mp_int m, mp_int c); /* c = v^b (mod m) */ +mp_result mp_int_exptmod_known(mp_int a, mp_int b, + mp_int m, mp_int mu, + mp_int c); /* c = a^b (mod m) */ +mp_result mp_int_redux_const(mp_int m, mp_int c); + +mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */ + +mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c); /* c = gcd(a, b) */ + +mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, /* c = gcd(a, b) */ + mp_int x, mp_int y); /* c = ax + by */ + +mp_result mp_int_sqrt(mp_int a, mp_int c); /* c = floor(sqrt(q)) */ + +/* Convert to an int, if representable (returns MP_RANGE if not). */ +mp_result mp_int_to_int(mp_int z, int *out); + +/* Convert to nul-terminated string with the specified radix, writing at + most limit characters including the nul terminator */ +mp_result mp_int_to_string(mp_int z, mp_size radix, + char *str, int limit); + +/* Return the number of characters required to represent + z in the given radix. May over-estimate. */ +mp_result mp_int_string_len(mp_int z, mp_size radix); + +/* Read zero-terminated string into z */ +mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str); +mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, + char **end); + +/* Return the number of significant bits in z */ +mp_result mp_int_count_bits(mp_int z); + +/* Convert z to two's complement binary, writing at most limit bytes */ +mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit); + +/* Read a two's complement binary value into z from the given buffer */ +mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len); + +/* Return the number of bytes required to represent z in binary. */ +mp_result mp_int_binary_len(mp_int z); + +/* Convert z to unsigned binary, writing at most limit bytes */ +mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit); + +/* Read an unsigned binary value into z from the given buffer */ +mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len); + +/* Return the number of bytes required to represent z as unsigned output */ +mp_result mp_int_unsigned_len(mp_int z); + +/* Return a statically allocated string describing error code res */ +const char *mp_error_string(mp_result res); + +#if 0 +void s_print(char *tag, mp_int z); +void s_print_buf(char *tag, mp_digit *buf, mp_size num); +#endif + +#endif /* end IMATH_H_ */ diff --git a/contrib/pgcrypto/internal-sha2.c b/contrib/pgcrypto/internal-sha2.c new file mode 100644 index 00000000000..6e1d97c4e31 --- /dev/null +++ b/contrib/pgcrypto/internal-sha2.c @@ -0,0 +1,317 @@ +/* + * internal.c + * Wrapper for builtin functions + * + * Copyright (c) 2001 Marko Kreen + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $PostgreSQL: pgsql/contrib/pgcrypto/internal-sha2.c,v 1.1 2006/07/13 04:15:24 neilc Exp $ + */ + +#include "postgres.h" + +#include <time.h> + +#include "px.h" +#include "sha2.h" + +void init_sha224(PX_MD * h); +void init_sha256(PX_MD * h); +void init_sha384(PX_MD * h); +void init_sha512(PX_MD * h); + +/* SHA224 */ + +static unsigned +int_sha224_len(PX_MD * h) +{ + return SHA224_DIGEST_LENGTH; +} + +static unsigned +int_sha224_block_len(PX_MD * h) +{ + return SHA224_BLOCK_LENGTH; +} + +static void +int_sha224_update(PX_MD * h, const uint8 *data, unsigned dlen) +{ + SHA224_CTX *ctx = (SHA224_CTX *) h->p.ptr; + + SHA224_Update(ctx, data, dlen); +} + +static void +int_sha224_reset(PX_MD * h) +{ + SHA224_CTX *ctx = (SHA224_CTX *) h->p.ptr; + + SHA224_Init(ctx); +} + +static void +int_sha224_finish(PX_MD * h, uint8 *dst) +{ + SHA224_CTX *ctx = (SHA224_CTX *) h->p.ptr; + + SHA224_Final(dst, ctx); +} + +static void +int_sha224_free(PX_MD * h) +{ + SHA224_CTX *ctx = (SHA224_CTX *) h->p.ptr; + + memset(ctx, 0, sizeof(*ctx)); + px_free(ctx); + px_free(h); +} + +/* SHA256 */ + +static unsigned +int_sha256_len(PX_MD * h) +{ + return SHA256_DIGEST_LENGTH; +} + +static unsigned +int_sha256_block_len(PX_MD * h) +{ + return SHA256_BLOCK_LENGTH; +} + +static void +int_sha256_update(PX_MD * h, const uint8 *data, unsigned dlen) +{ + SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; + + SHA256_Update(ctx, data, dlen); +} + +static void +int_sha256_reset(PX_MD * h) +{ + SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; + + SHA256_Init(ctx); +} + +static void +int_sha256_finish(PX_MD * h, uint8 *dst) +{ + SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; + + SHA256_Final(dst, ctx); +} + +static void +int_sha256_free(PX_MD * h) +{ + SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; + + memset(ctx, 0, sizeof(*ctx)); + px_free(ctx); + px_free(h); +} + +/* SHA384 */ + +static unsigned +int_sha384_len(PX_MD * h) +{ + return SHA384_DIGEST_LENGTH; +} + +static unsigned +int_sha384_block_len(PX_MD * h) +{ + return SHA384_BLOCK_LENGTH; +} + +static void +int_sha384_update(PX_MD * h, const uint8 *data, unsigned dlen) +{ + SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; + + SHA384_Update(ctx, data, dlen); +} + +static void +int_sha384_reset(PX_MD * h) +{ + SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; + + SHA384_Init(ctx); +} + +static void +int_sha384_finish(PX_MD * h, uint8 *dst) +{ + SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; + + SHA384_Final(dst, ctx); +} + +static void +int_sha384_free(PX_MD * h) +{ + SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; + + memset(ctx, 0, sizeof(*ctx)); + px_free(ctx); + px_free(h); +} + +/* SHA512 */ + +static unsigned +int_sha512_len(PX_MD * h) +{ + return SHA512_DIGEST_LENGTH; +} + +static unsigned +int_sha512_block_len(PX_MD * h) +{ + return SHA512_BLOCK_LENGTH; +} + +static void +int_sha512_update(PX_MD * h, const uint8 *data, unsigned dlen) +{ + SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; + + SHA512_Update(ctx, data, dlen); +} + +static void +int_sha512_reset(PX_MD * h) +{ + SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; + + SHA512_Init(ctx); +} + +static void +int_sha512_finish(PX_MD * h, uint8 *dst) +{ + SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; + + SHA512_Final(dst, ctx); +} + +static void +int_sha512_free(PX_MD * h) +{ + SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; + + memset(ctx, 0, sizeof(*ctx)); + px_free(ctx); + px_free(h); +} + +/* init functions */ + +void +init_sha224(PX_MD * md) +{ + SHA224_CTX *ctx; + + ctx = px_alloc(sizeof(*ctx)); + memset(ctx, 0, sizeof(*ctx)); + + md->p.ptr = ctx; + + md->result_size = int_sha224_len; + md->block_size = int_sha224_block_len; + md->reset = int_sha224_reset; + md->update = int_sha224_update; + md->finish = int_sha224_finish; + md->free = int_sha224_free; + + md->reset(md); +} + +void +init_sha256(PX_MD * md) +{ + SHA256_CTX *ctx; + + ctx = px_alloc(sizeof(*ctx)); + memset(ctx, 0, sizeof(*ctx)); + + md->p.ptr = ctx; + + md->result_size = int_sha256_len; + md->block_size = int_sha256_block_len; + md->reset = int_sha256_reset; + md->update = int_sha256_update; + md->finish = int_sha256_finish; + md->free = int_sha256_free; + + md->reset(md); +} + +void +init_sha384(PX_MD * md) +{ + SHA384_CTX *ctx; + + ctx = px_alloc(sizeof(*ctx)); + memset(ctx, 0, sizeof(*ctx)); + + md->p.ptr = ctx; + + md->result_size = int_sha384_len; + md->block_size = int_sha384_block_len; + md->reset = int_sha384_reset; + md->update = int_sha384_update; + md->finish = int_sha384_finish; + md->free = int_sha384_free; + + md->reset(md); +} + +void +init_sha512(PX_MD * md) +{ + SHA512_CTX *ctx; + + ctx = px_alloc(sizeof(*ctx)); + memset(ctx, 0, sizeof(*ctx)); + + md->p.ptr = ctx; + + md->result_size = int_sha512_len; + md->block_size = int_sha512_block_len; + md->reset = int_sha512_reset; + md->update = int_sha512_update; + md->finish = int_sha512_finish; + md->free = int_sha512_free; + + md->reset(md); +} + diff --git a/contrib/pgcrypto/internal.c b/contrib/pgcrypto/internal.c index f5dd11c90b3..4b90399cdd6 100644 --- a/contrib/pgcrypto/internal.c +++ b/contrib/pgcrypto/internal.c @@ -26,7 +26,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/internal.c,v 1.23 2005/10/15 02:49:06 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/internal.c,v 1.24 2006/07/13 04:15:24 neilc Exp $ */ #include "postgres.h" @@ -77,9 +77,11 @@ static void init_md5(PX_MD * h); static void init_sha1(PX_MD * h); -static void init_sha256(PX_MD * h); -static void init_sha384(PX_MD * h); -static void init_sha512(PX_MD * h); + +void init_sha224(PX_MD * h); +void init_sha256(PX_MD * h); +void init_sha384(PX_MD * h); +void init_sha512(PX_MD * h); struct int_digest { @@ -91,6 +93,7 @@ static const struct int_digest int_digest_list[] = { {"md5", init_md5}, {"sha1", init_sha1}, + {"sha224", init_sha224}, {"sha256", init_sha256}, {"sha384", init_sha384}, {"sha512", init_sha512}, @@ -193,150 +196,6 @@ int_sha1_free(PX_MD * h) px_free(h); } -/* SHA256 */ - -static unsigned -int_sha256_len(PX_MD * h) -{ - return SHA256_DIGEST_LENGTH; -} - -static unsigned -int_sha256_block_len(PX_MD * h) -{ - return SHA256_BLOCK_LENGTH; -} - -static void -int_sha256_update(PX_MD * h, const uint8 *data, unsigned dlen) -{ - SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; - - SHA256_Update(ctx, data, dlen); -} - -static void -int_sha256_reset(PX_MD * h) -{ - SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; - - SHA256_Init(ctx); -} - -static void -int_sha256_finish(PX_MD * h, uint8 *dst) -{ - SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; - - SHA256_Final(dst, ctx); -} - -static void -int_sha256_free(PX_MD * h) -{ - SHA256_CTX *ctx = (SHA256_CTX *) h->p.ptr; - - memset(ctx, 0, sizeof(*ctx)); - px_free(ctx); - px_free(h); -} - -/* SHA384 */ - -static unsigned -int_sha384_len(PX_MD * h) -{ - return SHA384_DIGEST_LENGTH; -} - -static unsigned -int_sha384_block_len(PX_MD * h) -{ - return SHA384_BLOCK_LENGTH; -} - -static void -int_sha384_update(PX_MD * h, const uint8 *data, unsigned dlen) -{ - SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; - - SHA384_Update(ctx, data, dlen); -} - -static void -int_sha384_reset(PX_MD * h) -{ - SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; - - SHA384_Init(ctx); -} - -static void -int_sha384_finish(PX_MD * h, uint8 *dst) -{ - SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; - - SHA384_Final(dst, ctx); -} - -static void -int_sha384_free(PX_MD * h) -{ - SHA384_CTX *ctx = (SHA384_CTX *) h->p.ptr; - - memset(ctx, 0, sizeof(*ctx)); - px_free(ctx); - px_free(h); -} - -/* SHA512 */ - -static unsigned -int_sha512_len(PX_MD * h) -{ - return SHA512_DIGEST_LENGTH; -} - -static unsigned -int_sha512_block_len(PX_MD * h) -{ - return SHA512_BLOCK_LENGTH; -} - -static void -int_sha512_update(PX_MD * h, const uint8 *data, unsigned dlen) -{ - SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; - - SHA512_Update(ctx, data, dlen); -} - -static void -int_sha512_reset(PX_MD * h) -{ - SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; - - SHA512_Init(ctx); -} - -static void -int_sha512_finish(PX_MD * h, uint8 *dst) -{ - SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; - - SHA512_Final(dst, ctx); -} - -static void -int_sha512_free(PX_MD * h) -{ - SHA512_CTX *ctx = (SHA512_CTX *) h->p.ptr; - - memset(ctx, 0, sizeof(*ctx)); - px_free(ctx); - px_free(h); -} - /* init functions */ static void @@ -379,66 +238,6 @@ init_sha1(PX_MD * md) md->reset(md); } -static void -init_sha256(PX_MD * md) -{ - SHA256_CTX *ctx; - - ctx = px_alloc(sizeof(*ctx)); - memset(ctx, 0, sizeof(*ctx)); - - md->p.ptr = ctx; - - md->result_size = int_sha256_len; - md->block_size = int_sha256_block_len; - md->reset = int_sha256_reset; - md->update = int_sha256_update; - md->finish = int_sha256_finish; - md->free = int_sha256_free; - - md->reset(md); -} - -static void -init_sha384(PX_MD * md) -{ - SHA384_CTX *ctx; - - ctx = px_alloc(sizeof(*ctx)); - memset(ctx, 0, sizeof(*ctx)); - - md->p.ptr = ctx; - - md->result_size = int_sha384_len; - md->block_size = int_sha384_block_len; - md->reset = int_sha384_reset; - md->update = int_sha384_update; - md->finish = int_sha384_finish; - md->free = int_sha384_free; - - md->reset(md); -} - -static void -init_sha512(PX_MD * md) -{ - SHA512_CTX *ctx; - - ctx = px_alloc(sizeof(*ctx)); - memset(ctx, 0, sizeof(*ctx)); - - md->p.ptr = ctx; - - md->result_size = int_sha512_len; - md->block_size = int_sha512_block_len; - md->reset = int_sha512_reset; - md->update = int_sha512_update; - md->finish = int_sha512_finish; - md->free = int_sha512_free; - - md->reset(md); -} - /* * ciphers generally */ @@ -821,19 +620,12 @@ px_find_cipher(const char *name, PX_Cipher ** res) */ /* - * Use libc for all 'public' bytes. - * - * That way we don't expose bytes from Fortuna - * to the public, in case it has some bugs. + * Use always strong randomness. */ int px_get_pseudo_random_bytes(uint8 *dst, unsigned count) { - int i; - - for (i = 0; i < count; i++) - *dst++ = random(); - return i; + return px_get_random_bytes(dst, count); } static time_t seed_time = 0; diff --git a/contrib/pgcrypto/misc.c b/contrib/pgcrypto/misc.c deleted file mode 100644 index b53a70a5095..00000000000 --- a/contrib/pgcrypto/misc.c +++ /dev/null @@ -1,51 +0,0 @@ -/* - * Copyright (c) 1999 - * University of California. All rights reserved. - * - * $PostgreSQL: pgsql/contrib/pgcrypto/misc.c,v 1.3 2006/03/11 04:38:30 momjian Exp $ - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of the author nor the names of any co-contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS - * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED - * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY - * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE - * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER - * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR - * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN - * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * $FreeBSD: src/lib/libcrypt/misc.c,v 1.1 1999/09/20 12:45:49 markm Exp $ - * - */ - -#include "px-crypt.h" - -char px_crypt_a64[] = -"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; - -/* 0000000000111111111122222222223333333333444444444455555555556666 */ -/* 0123456789012345678901234567890123456789012345678901234567890123 */ - -void -px_crypt_to64(char *s, unsigned long v, int n) -{ - while (--n >= 0) - { - *s++ = px_crypt_a64[v & 0x3f]; - v >>= 6; - } -} diff --git a/contrib/pgcrypto/openssl.c b/contrib/pgcrypto/openssl.c index 8fc60eba420..74234e9bf02 100644 --- a/contrib/pgcrypto/openssl.c +++ b/contrib/pgcrypto/openssl.c @@ -26,7 +26,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/openssl.c,v 1.27 2006/02/18 20:48:51 neilc Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/openssl.c,v 1.28 2006/07/13 04:15:25 neilc Exp $ */ #include "postgres.h" @@ -147,6 +147,38 @@ static int EVP_DigestFinal_ex(EVP_MD_CTX *ctx, unsigned char *res, unsigned int #endif /* old OpenSSL */ /* + * Provide SHA2 for older OpenSSL < 0.9.8 + */ +#if OPENSSL_VERSION_NUMBER < 0x00908000L + +#include "sha2.c" +#include "internal-sha2.c" + +typedef int (*init_f)(PX_MD *md); + +static int compat_find_digest(const char *name, PX_MD **res) +{ + init_f init = NULL; + if (pg_strcasecmp(name, "sha224") == 0) + init = init_sha224; + else if (pg_strcasecmp(name, "sha256") == 0) + init = init_sha256; + else if (pg_strcasecmp(name, "sha384") == 0) + init = init_sha384; + else if (pg_strcasecmp(name, "sha512") == 0) + init = init_sha512; + else + return PXE_NO_HASH; + *res = px_alloc(sizeof(PX_MD)); + init(*res); + return 0; +} + +#else +#define compat_find_digest(name, res) (PXE_NO_HASH) +#endif + +/* * Hashes */ @@ -223,7 +255,7 @@ px_find_digest(const char *name, PX_MD ** res) md = EVP_get_digestbyname(name); if (md == NULL) - return PXE_NO_HASH; + return compat_find_digest(name, res); digest = px_alloc(sizeof(*digest)); digest->algo = md; @@ -526,7 +558,7 @@ ossl_des3_ecb_encrypt(PX_Cipher * c, const uint8 *data, unsigned dlen, ossldata *od = c->ptr; for (i = 0; i < dlen / bs; i++) - DES_ecb3_encrypt(data + i * bs, res + i * bs, + DES_ecb3_encrypt((void *)(data + i * bs), (void *)(res + i * bs), &od->u.des3.k1, &od->u.des3.k2, &od->u.des3.k3, 1); return 0; } @@ -540,7 +572,7 @@ ossl_des3_ecb_decrypt(PX_Cipher * c, const uint8 *data, unsigned dlen, ossldata *od = c->ptr; for (i = 0; i < dlen / bs; i++) - DES_ecb3_encrypt(data + i * bs, res + i * bs, + DES_ecb3_encrypt((void *)(data + i * bs), (void *)(res + i * bs), &od->u.des3.k1, &od->u.des3.k2, &od->u.des3.k3, 0); return 0; } diff --git a/contrib/pgcrypto/pgcrypto.c b/contrib/pgcrypto/pgcrypto.c index 6196a1b4d69..ee976a69a07 100644 --- a/contrib/pgcrypto/pgcrypto.c +++ b/contrib/pgcrypto/pgcrypto.c @@ -26,7 +26,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/pgcrypto.c,v 1.21 2006/05/30 22:12:13 tgl Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/pgcrypto.c,v 1.22 2006/07/13 04:15:25 neilc Exp $ */ #include "postgres.h" @@ -537,6 +537,34 @@ pg_decrypt_iv(PG_FUNCTION_ARGS) PG_RETURN_BYTEA_P(res); } +/* SQL function: pg_random_bytes(int4) returns bytea */ +PG_FUNCTION_INFO_V1(pg_random_bytes); + +Datum +pg_random_bytes(PG_FUNCTION_ARGS) +{ + int err; + int len = PG_GETARG_INT32(0); + bytea *res; + + if (len < 1 || len > 1024) + ereport(ERROR, + (errcode(ERRCODE_EXTERNAL_ROUTINE_INVOCATION_EXCEPTION), + errmsg("Length not in range"))); + + res = palloc(VARHDRSZ + len); + VARATT_SIZEP(res) = VARHDRSZ + len; + + /* generate result */ + err = px_get_random_bytes((uint8*)VARDATA(res), len); + if (err < 0) + ereport(ERROR, + (errcode(ERRCODE_EXTERNAL_ROUTINE_INVOCATION_EXCEPTION), + errmsg("Random generator error: %s", px_strerror(err)))); + + PG_RETURN_BYTEA_P(res); +} + /* SQL function: pg_cipher_exists(text) returns bool */ PG_FUNCTION_INFO_V1(pg_cipher_exists); diff --git a/contrib/pgcrypto/pgcrypto.h b/contrib/pgcrypto/pgcrypto.h index 6db7efc407a..3211fc4dede 100644 --- a/contrib/pgcrypto/pgcrypto.h +++ b/contrib/pgcrypto/pgcrypto.h @@ -26,7 +26,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/pgcrypto.h,v 1.9 2006/07/10 22:06:11 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/pgcrypto.h,v 1.10 2006/07/13 04:15:25 neilc Exp $ */ #ifndef _PG_CRYPTO_H @@ -47,5 +47,6 @@ Datum pg_decrypt(PG_FUNCTION_ARGS); Datum pg_encrypt_iv(PG_FUNCTION_ARGS); Datum pg_decrypt_iv(PG_FUNCTION_ARGS); Datum pg_cipher_exists(PG_FUNCTION_ARGS); +Datum pg_random_bytes(PG_FUNCTION_ARGS); #endif diff --git a/contrib/pgcrypto/pgcrypto.sql.in b/contrib/pgcrypto/pgcrypto.sql.in index a6ff645c4fc..c442f6176c3 100644 --- a/contrib/pgcrypto/pgcrypto.sql.in +++ b/contrib/pgcrypto/pgcrypto.sql.in @@ -71,6 +71,11 @@ RETURNS bool AS 'MODULE_PATHNAME', 'pg_cipher_exists' LANGUAGE C IMMUTABLE STRICT; +CREATE OR REPLACE FUNCTION gen_random_bytes(int4) +RETURNS bytea +AS 'MODULE_PATHNAME', 'pg_random_bytes' +LANGUAGE 'C' VOLATILE STRICT; + -- -- pgp_sym_encrypt(data, key) -- diff --git a/contrib/pgcrypto/pgp-mpi-internal.c b/contrib/pgcrypto/pgp-mpi-internal.c index 3a81ed46a78..3292548e1f4 100644 --- a/contrib/pgcrypto/pgp-mpi-internal.c +++ b/contrib/pgcrypto/pgp-mpi-internal.c @@ -26,36 +26,273 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/pgp-mpi-internal.c,v 1.4 2005/10/15 02:49:06 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/pgp-mpi-internal.c,v 1.5 2006/07/13 04:15:25 neilc Exp $ */ #include "postgres.h" +#include "imath.h" + #include "px.h" #include "mbuf.h" #include "pgp.h" +static mpz_t *mp_new() +{ + mpz_t *mp = mp_int_alloc(); + mp_int_init_size(mp, 256); + return mp; +} + +static void mp_clear_free(mpz_t *a) +{ + if (!a) + return; + // fixme: no clear? + mp_int_free(a); +} + + +static int mp_px_rand(uint32 bits, mpz_t *res) +{ + int err; + unsigned bytes = (bits + 7) / 8; + int last_bits = bits & 7; + uint8 *buf; + + buf = px_alloc(bytes); + err = px_get_random_bytes(buf, bytes); + if (err < 0) { + px_free(buf); + return err; + } + + /* clear unnecessary bits and set last bit to one */ + if (last_bits) { + buf[0] >>= 8 - last_bits; + buf[0] |= 1 << (last_bits - 1); + } else + buf[0] |= 1 << 7; + + mp_int_read_unsigned(res, buf, bytes); + + px_free(buf); + + return 0; +} + +static void mp_modmul(mpz_t *a, mpz_t *b, mpz_t *p, mpz_t *res) +{ + mpz_t *tmp = mp_new(); + mp_int_mul(a, b, tmp); + mp_int_mod(tmp, p, res); + mp_clear_free(tmp); +} + +static mpz_t * +mpi_to_bn(PGP_MPI * n) +{ + mpz_t *bn = mp_new(); + mp_int_read_unsigned(bn, n->data, n->bytes); + + if (!bn) + return NULL; + if (mp_int_count_bits(bn) != n->bits) + { + px_debug("mpi_to_bn: bignum conversion failed: mpi=%d, bn=%d", + n->bits, mp_int_count_bits(bn)); + mp_clear_free(bn); + return NULL; + } + return bn; +} + +static PGP_MPI * +bn_to_mpi(mpz_t *bn) +{ + int res; + PGP_MPI *n; + int bytes; + + res = pgp_mpi_alloc(mp_int_count_bits(bn), &n); + if (res < 0) + return NULL; + + bytes = (mp_int_count_bits(bn) + 7) / 8; + if (bytes != n->bytes) + { + px_debug("bn_to_mpi: bignum conversion failed: bn=%d, mpi=%d", + bytes, n->bytes); + pgp_mpi_free(n); + return NULL; + } + mp_int_to_unsigned(bn, n->data, n->bytes); + return n; +} + +/* + * Decide the number of bits in the random componont k + * + * It should be in the same range as p for signing (which + * is deprecated), but can be much smaller for encrypting. + * + * Until I research it further, I just mimic gpg behaviour. + * It has a special mapping table, for values <= 5120, + * above that it uses 'arbitrary high number'. Following + * algorihm hovers 10-70 bits above gpg values. And for + * larger p, it uses gpg's algorihm. + * + * The point is - if k gets large, encryption will be + * really slow. It does not matter for decryption. + */ +static int +decide_k_bits(int p_bits) +{ + if (p_bits <= 5120) + return p_bits / 10 + 160; + else + return (p_bits / 8 + 200) * 3 / 2; +} + int pgp_elgamal_encrypt(PGP_PubKey * pk, PGP_MPI * _m, PGP_MPI ** c1_p, PGP_MPI ** c2_p) { - return PXE_PGP_NO_BIGNUM; + int res = PXE_PGP_MATH_FAILED; + int k_bits; + mpz_t *m = mpi_to_bn(_m); + mpz_t *p = mpi_to_bn(pk->pub.elg.p); + mpz_t *g = mpi_to_bn(pk->pub.elg.g); + mpz_t *y = mpi_to_bn(pk->pub.elg.y); + mpz_t *k = mp_new(); + mpz_t *yk = mp_new(); + mpz_t *c1 = mp_new(); + mpz_t *c2 = mp_new(); + + if (!m || !p || !g || !y || !k || !yk || !c1 || !c2) + goto err; + + /* + * generate k + */ + k_bits = decide_k_bits(mp_int_count_bits(p)); + res = mp_px_rand(k_bits, k); + if (res < 0) + return res; + + /* + * c1 = g^k c2 = m * y^k + */ + mp_int_exptmod(g, k, p, c1); + mp_int_exptmod(y, k, p, yk); + mp_modmul(m, yk, p, c2); + + /* result */ + *c1_p = bn_to_mpi(c1); + *c2_p = bn_to_mpi(c2); + if (*c1_p && *c2_p) + res = 0; +err: + mp_clear_free(c2); + mp_clear_free(c1); + mp_clear_free(yk); + mp_clear_free(k); + mp_clear_free(y); + mp_clear_free(g); + mp_clear_free(p); + mp_clear_free(m); + return res; } int pgp_elgamal_decrypt(PGP_PubKey * pk, PGP_MPI * _c1, PGP_MPI * _c2, PGP_MPI ** msg_p) { - return PXE_PGP_NO_BIGNUM; + int res = PXE_PGP_MATH_FAILED; + mpz_t *c1 = mpi_to_bn(_c1); + mpz_t *c2 = mpi_to_bn(_c2); + mpz_t *p = mpi_to_bn(pk->pub.elg.p); + mpz_t *x = mpi_to_bn(pk->sec.elg.x); + mpz_t *c1x = mp_new(); + mpz_t *div = mp_new(); + mpz_t *m = mp_new(); + + if (!c1 || !c2 || !p || !x || !c1x || !div || !m) + goto err; + + /* + * m = c2 / (c1^x) + */ + mp_int_exptmod(c1, x, p, c1x); + mp_int_invmod(c1x, p, div); + mp_modmul(c2, div, p, m); + + /* result */ + *msg_p = bn_to_mpi(m); + if (*msg_p) + res = 0; +err: + mp_clear_free(m); + mp_clear_free(div); + mp_clear_free(c1x); + mp_clear_free(x); + mp_clear_free(p); + mp_clear_free(c2); + mp_clear_free(c1); + return res; } int -pgp_rsa_encrypt(PGP_PubKey * pk, PGP_MPI * m, PGP_MPI ** c) +pgp_rsa_encrypt(PGP_PubKey * pk, PGP_MPI * _m, PGP_MPI ** c_p) { - return PXE_PGP_NO_BIGNUM; + int res = PXE_PGP_MATH_FAILED; + mpz_t *m = mpi_to_bn(_m); + mpz_t *e = mpi_to_bn(pk->pub.rsa.e); + mpz_t *n = mpi_to_bn(pk->pub.rsa.n); + mpz_t *c = mp_new(); + + if (!m || !e || !n || !c) + goto err; + + /* + * c = m ^ e + */ + mp_int_exptmod(m, e, n, c); + + *c_p = bn_to_mpi(c); + if (*c_p) + res = 0; +err: + mp_clear_free(c); + mp_clear_free(n); + mp_clear_free(e); + mp_clear_free(m); + return res; } int -pgp_rsa_decrypt(PGP_PubKey * pk, PGP_MPI * c, PGP_MPI ** m) +pgp_rsa_decrypt(PGP_PubKey * pk, PGP_MPI * _c, PGP_MPI ** m_p) { - return PXE_PGP_NO_BIGNUM; + int res = PXE_PGP_MATH_FAILED; + mpz_t *c = mpi_to_bn(_c); + mpz_t *d = mpi_to_bn(pk->sec.rsa.d); + mpz_t *n = mpi_to_bn(pk->pub.rsa.n); + mpz_t *m = mp_new(); + + if (!m || !d || !n || !c) + goto err; + + /* + * m = c ^ d + */ + mp_int_exptmod(c, d, n, m); + + *m_p = bn_to_mpi(m); + if (*m_p) + res = 0; +err: + mp_clear_free(m); + mp_clear_free(n); + mp_clear_free(d); + mp_clear_free(c); + return res; } diff --git a/contrib/pgcrypto/px-crypt.h b/contrib/pgcrypto/px-crypt.h index 957b30e5dc0..c2460cb9f9b 100644 --- a/contrib/pgcrypto/px-crypt.h +++ b/contrib/pgcrypto/px-crypt.h @@ -26,7 +26,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $PostgreSQL: pgsql/contrib/pgcrypto/px-crypt.h,v 1.9 2005/10/15 02:49:06 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/px-crypt.h,v 1.10 2006/07/13 04:15:25 neilc Exp $ */ #ifndef _PX_CRYPT_H @@ -55,14 +55,6 @@ int px_gen_salt(const char *salt_type, char *dst, int rounds); * internal functions */ -/* misc.c */ -extern void px_crypt_to64(char *s, unsigned long v, int n); -extern char px_crypt_a64[]; - -/* avoid conflicts with system libs */ -#define _crypt_to64 px_crypt_to64 -#define _crypt_a64 px_crypt_a64 - /* crypt-gensalt.c */ char *_crypt_gensalt_traditional_rn(unsigned long count, const char *input, int size, char *output, int output_size); diff --git a/contrib/pgcrypto/sha2.c b/contrib/pgcrypto/sha2.c index 19febaa1199..98e1fc1964d 100644 --- a/contrib/pgcrypto/sha2.c +++ b/contrib/pgcrypto/sha2.c @@ -33,7 +33,7 @@ * * $From: sha2.c,v 1.1 2001/11/08 00:01:51 adg Exp adg $ * - * $PostgreSQL: pgsql/contrib/pgcrypto/sha2.c,v 1.6 2006/05/30 12:56:45 momjian Exp $ + * $PostgreSQL: pgsql/contrib/pgcrypto/sha2.c,v 1.7 2006/07/13 04:15:25 neilc Exp $ */ #include "postgres.h" @@ -189,6 +189,18 @@ static const uint32 K256[64] = { 0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL }; +/* Initial hash value H for SHA-224: */ +static const uint32 sha224_initial_hash_value[8] = { + 0xc1059ed8UL, + 0x367cd507UL, + 0x3070dd17UL, + 0xf70e5939UL, + 0xffc00b31UL, + 0x68581511UL, + 0x64f98fa7UL, + 0xbefa4fa4UL +}; + /* Initial hash value H for SHA-256: */ static const uint32 sha256_initial_hash_value[8] = { 0x6a09e667UL, @@ -521,55 +533,61 @@ SHA256_Update(SHA256_CTX * context, const uint8 *data, size_t len) usedspace = freespace = 0; } -void -SHA256_Final(uint8 digest[], SHA256_CTX * context) +static void +SHA256_Last(SHA256_CTX *context) { unsigned int usedspace; - /* If no digest buffer is passed, we don't bother doing this: */ - if (digest != NULL) - { - usedspace = (context->bitcount >> 3) % SHA256_BLOCK_LENGTH; + usedspace = (context->bitcount >> 3) % SHA256_BLOCK_LENGTH; #if BYTE_ORDER == LITTLE_ENDIAN - /* Convert FROM host byte order */ - REVERSE64(context->bitcount, context->bitcount); + /* Convert FROM host byte order */ + REVERSE64(context->bitcount, context->bitcount); #endif - if (usedspace > 0) - { - /* Begin padding with a 1 bit: */ - context->buffer[usedspace++] = 0x80; + if (usedspace > 0) + { + /* Begin padding with a 1 bit: */ + context->buffer[usedspace++] = 0x80; - if (usedspace <= SHA256_SHORT_BLOCK_LENGTH) - { - /* Set-up for the last transform: */ - memset(&context->buffer[usedspace], 0, SHA256_SHORT_BLOCK_LENGTH - usedspace); - } - else - { - if (usedspace < SHA256_BLOCK_LENGTH) - { - memset(&context->buffer[usedspace], 0, SHA256_BLOCK_LENGTH - usedspace); - } - /* Do second-to-last transform: */ - SHA256_Transform(context, context->buffer); - - /* And set-up for the last transform: */ - memset(context->buffer, 0, SHA256_SHORT_BLOCK_LENGTH); - } + if (usedspace <= SHA256_SHORT_BLOCK_LENGTH) + { + /* Set-up for the last transform: */ + memset(&context->buffer[usedspace], 0, SHA256_SHORT_BLOCK_LENGTH - usedspace); } else { - /* Set-up for the last transform: */ - memset(context->buffer, 0, SHA256_SHORT_BLOCK_LENGTH); + if (usedspace < SHA256_BLOCK_LENGTH) + { + memset(&context->buffer[usedspace], 0, SHA256_BLOCK_LENGTH - usedspace); + } + /* Do second-to-last transform: */ + SHA256_Transform(context, context->buffer); - /* Begin padding with a 1 bit: */ - *context->buffer = 0x80; + /* And set-up for the last transform: */ + memset(context->buffer, 0, SHA256_SHORT_BLOCK_LENGTH); } - /* Set the bit count: */ - *(uint64 *) &context->buffer[SHA256_SHORT_BLOCK_LENGTH] = context->bitcount; + } + else + { + /* Set-up for the last transform: */ + memset(context->buffer, 0, SHA256_SHORT_BLOCK_LENGTH); + + /* Begin padding with a 1 bit: */ + *context->buffer = 0x80; + } + /* Set the bit count: */ + *(uint64 *) &context->buffer[SHA256_SHORT_BLOCK_LENGTH] = context->bitcount; - /* Final transform: */ - SHA256_Transform(context, context->buffer); + /* Final transform: */ + SHA256_Transform(context, context->buffer); +} + +void +SHA256_Final(uint8 digest[], SHA256_CTX * context) +{ + /* If no digest buffer is passed, we don't bother doing this: */ + if (digest != NULL) + { + SHA256_Last(context); #if BYTE_ORDER == LITTLE_ENDIAN { @@ -587,7 +605,6 @@ SHA256_Final(uint8 digest[], SHA256_CTX * context) /* Clean up state data: */ memset(context, 0, sizeof(*context)); - usedspace = 0; } @@ -963,3 +980,47 @@ SHA384_Final(uint8 digest[], SHA384_CTX * context) /* Zero out state data */ memset(context, 0, sizeof(*context)); } + +/*** SHA-224: *********************************************************/ +void +SHA224_Init(SHA224_CTX * context) +{ + if (context == NULL) + return; + memcpy(context->state, sha224_initial_hash_value, SHA256_DIGEST_LENGTH); + memset(context->buffer, 0, SHA256_BLOCK_LENGTH); + context->bitcount = 0; +} + +void +SHA224_Update(SHA224_CTX * context, const uint8 *data, size_t len) +{ + SHA256_Update((SHA256_CTX *) context, data, len); +} + +void +SHA224_Final(uint8 digest[], SHA224_CTX * context) +{ + /* If no digest buffer is passed, we don't bother doing this: */ + if (digest != NULL) + { + SHA256_Last(context); + +#if BYTE_ORDER == LITTLE_ENDIAN + { + /* Convert TO host byte order */ + int j; + + for (j = 0; j < 8; j++) + { + REVERSE32(context->state[j], context->state[j]); + } + } +#endif + memcpy(digest, context->state, SHA224_DIGEST_LENGTH); + } + + /* Clean up state data: */ + memset(context, 0, sizeof(*context)); +} + diff --git a/contrib/pgcrypto/sha2.h b/contrib/pgcrypto/sha2.h index 95f8a2400d7..f6fde39c5b4 100644 --- a/contrib/pgcrypto/sha2.h +++ b/contrib/pgcrypto/sha2.h @@ -1,4 +1,4 @@ -/* $PostgreSQL: pgsql/contrib/pgcrypto/sha2.h,v 1.3 2006/05/30 12:56:45 momjian Exp $ */ +/* $PostgreSQL: pgsql/contrib/pgcrypto/sha2.h,v 1.4 2006/07/13 04:15:25 neilc Exp $ */ /* $OpenBSD: sha2.h,v 1.2 2004/04/28 23:11:57 millert Exp $ */ /* @@ -49,7 +49,10 @@ #define SHA512_Update pg_SHA512_Update #define SHA512_Final pg_SHA512_Final -/*** SHA-256/384/512 Various Length Definitions ***********************/ +/*** SHA-224/256/384/512 Various Length Definitions ***********************/ +#define SHA224_BLOCK_LENGTH 64 +#define SHA224_DIGEST_LENGTH 28 +#define SHA224_DIGEST_STRING_LENGTH (SHA224_DIGEST_LENGTH * 2 + 1) #define SHA256_BLOCK_LENGTH 64 #define SHA256_DIGEST_LENGTH 32 #define SHA256_DIGEST_STRING_LENGTH (SHA256_DIGEST_LENGTH * 2 + 1) @@ -75,8 +78,13 @@ typedef struct _SHA512_CTX uint8 buffer[SHA512_BLOCK_LENGTH]; } SHA512_CTX; +typedef SHA256_CTX SHA224_CTX; typedef SHA512_CTX SHA384_CTX; +void SHA224_Init(SHA224_CTX *); +void SHA224_Update(SHA224_CTX *, const uint8 *, size_t); +void SHA224_Final(uint8[SHA224_DIGEST_LENGTH], SHA224_CTX *); + void SHA256_Init(SHA256_CTX *); void SHA256_Update(SHA256_CTX *, const uint8 *, size_t); void SHA256_Final(uint8[SHA256_DIGEST_LENGTH], SHA256_CTX *); diff --git a/contrib/pgcrypto/sql/sha2.sql b/contrib/pgcrypto/sql/sha2.sql index f1d0ca63f01..447ae907653 100644 --- a/contrib/pgcrypto/sql/sha2.sql +++ b/contrib/pgcrypto/sql/sha2.sql @@ -2,6 +2,13 @@ -- SHA2 family -- +-- SHA224 +SELECT encode(digest('', 'sha224'), 'hex'); +SELECT encode(digest('a', 'sha224'), 'hex'); +SELECT encode(digest('abc', 'sha224'), 'hex'); +SELECT encode(digest('abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq', 'sha224'), 'hex'); +SELECT encode(digest('12345678901234567890123456789012345678901234567890123456789012345678901234567890', 'sha224'), 'hex'); + -- SHA256 SELECT encode(digest('', 'sha256'), 'hex'); SELECT encode(digest('a', 'sha256'), 'hex'); diff --git a/contrib/pgcrypto/uninstall_pgcrypto.sql b/contrib/pgcrypto/uninstall_pgcrypto.sql new file mode 100644 index 00000000000..56103f09db1 --- /dev/null +++ b/contrib/pgcrypto/uninstall_pgcrypto.sql @@ -0,0 +1,46 @@ + +SET search_path = public; + +DROP FUNCTION digest(text, text); +DROP FUNCTION digest(bytea, text); +DROP FUNCTION digest_exists(text); + +DROP FUNCTION hmac(text, text, text); +DROP FUNCTION hmac(bytea, bytea, text); +DROP FUNCTION hmac_exists(text); + +DROP FUNCTION crypt(text, text); +DROP FUNCTION gen_salt(text); +DROP FUNCTION gen_salt(text, int4); + +DROP FUNCTION encrypt(bytea, bytea, text); +DROP FUNCTION decrypt(bytea, bytea, text); +DROP FUNCTION encrypt_iv(bytea, bytea, bytea, text); +DROP FUNCTION decrypt_iv(bytea, bytea, bytea, text); +DROP FUNCTION cipher_exists(text); +DROP FUNCTION gen_random_bytes(int4); + +DROP FUNCTION pgp_sym_encrypt(text, text); +DROP FUNCTION pgp_sym_encrypt_bytea(bytea, text); +DROP FUNCTION pgp_sym_encrypt(text, text, text); +DROP FUNCTION pgp_sym_encrypt_bytea(bytea, text, text); +DROP FUNCTION pgp_sym_decrypt(bytea, text); +DROP FUNCTION pgp_sym_decrypt_bytea(bytea, text); +DROP FUNCTION pgp_sym_decrypt(bytea, text, text); +DROP FUNCTION pgp_sym_decrypt_bytea(bytea, text, text); + +DROP FUNCTION pgp_pub_encrypt(text, bytea); +DROP FUNCTION pgp_pub_encrypt_bytea(bytea, bytea); +DROP FUNCTION pgp_pub_encrypt(text, bytea, text); +DROP FUNCTION pgp_pub_encrypt_bytea(bytea, bytea, text); +DROP FUNCTION pgp_pub_decrypt(bytea, bytea); +DROP FUNCTION pgp_pub_decrypt_bytea(bytea, bytea); +DROP FUNCTION pgp_pub_decrypt(bytea, bytea, text); +DROP FUNCTION pgp_pub_decrypt_bytea(bytea, bytea, text); +DROP FUNCTION pgp_pub_decrypt(bytea, bytea, text, text); +DROP FUNCTION pgp_pub_decrypt_bytea(bytea, bytea, text, text); + +DROP FUNCTION pgp_key_id(bytea); +DROP FUNCTION armor(bytea); +DROP FUNCTION dearmor(text); + |