/* libpaillier - A library implementing the Paillier cryptosystem. Copyright (C) 2006 SRI International. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. */ /* Include gmp.h before including this file. */ /* IMPORTANT SECURITY NOTES: On paillier_keygen and strong primes: When selecting a modulus n = p q, we do not bother ensuring that p and q are strong primes. While this was at one point considered important (e.g., it is required by ANSI X9.31), modern factoring algorithms make any advantage of strong primes doubtful [1]. RSA Laboratories no longer recommends the practice [2]. On memory handling: At no point is any special effort made to securely "shred" sensitive memory or prevent it from being paged out to disk. This means that it is important that functions dealing with private keys and plaintexts (e.g., paillier_keygen and paillier_enc) only be run on trusted machines. The resulting ciphertexts and public keys, however, may of course be handled in an untrusted manner. [1] Are "strong" primes needed for RSA? Ron Rivest and Robert Silverman. Cryptology ePrint Archive, Report 2001/007, 2001. [2] RSA Laboratories' Frequently Asked Questions About Today's Cryptography, Version 4.1, Section 3.1.4. */ /****** TYPES *******/ /* This represents a Paillier public key, which is basically just the modulus n. The other values should be considered private. */ typedef struct { unsigned int bits; /* e.g., 1024 */ mpz_t n; /* public modulus n = p q */ mpz_t n_squared; /* cached to avoid recomputing */ mpz_t n_plusone; /* cached to avoid recomputing */ } paillier_pubkey_t; /* This represents a Paillier private key; it needs to be used with a paillier_pubkey_t to be meaningful. It only includes the Carmichael function (lambda) of the modulus. The other value is kept for efficiency and should be considered private. */ typedef struct { mpz_t lambda; /* lambda(n), i.e., lcm(p-1,q-1) */ mpz_t x; /* cached to avoid recomputing */ } paillier_prvkey_t; /* This is a (semantic rather than structural) type for plaintexts. These can be converted to and from ASCII strings and byte arrays. */ typedef struct { mpz_t m; } paillier_plaintext_t; /* This is a (semantic rather than structural) type for ciphertexts. These can also be converted to or from byte arrays (for example in order to store them in a file). */ typedef struct { mpz_t c; } paillier_ciphertext_t; /* This is the type of the callback functions used to obtain the randomness needed by the probabilistic algorithms. The functions paillier_get_rand_devrandom and paillier_get_rand_devurandom (documented later) may be passed to any library function requiring a paillier_get_rand_t, or you may implement your own. If you implement your own such function, it should fill in "len" random bytes in the array "buf". */ typedef void (*paillier_get_rand_t) ( void* buf, int len ); /***************** BASIC OPERATIONS *****************/ /* Generate a keypair of length modulusbits using randomness from the provided get_rand function. Space will be allocated for each of the keys, and the given pointers will be set to point to the new paillier_pubkey_t and paillier_prvkey_t structures. The functions paillier_get_rand_devrandom and paillier_get_rand_devurandom may be passed as the final argument. */ void paillier_keygen( unsigned int modulusbits, paillier_pubkey_t** pub, paillier_prvkey_t** prv, paillier_get_rand_t get_rand ); /* Encrypt the given plaintext with the given public key using randomness from get_rand for blinding. If res is not null, its contents will be overwritten with the result. Otherwise, a new paillier_ciphertext_t will be allocated and returned. */ paillier_ciphertext_t* paillier_enc( paillier_ciphertext_t* res, paillier_pubkey_t* pub, paillier_plaintext_t* pt, paillier_get_rand_t get_rand ); /* Decrypt the given ciphertext with the given key pair. If res is not null, its contents will be overwritten with the result. Otherwise, a new paillier_plaintext_t will be allocated and returned. */ paillier_plaintext_t* paillier_dec( paillier_plaintext_t* res, paillier_pubkey_t* pub, paillier_prvkey_t* prv, paillier_ciphertext_t* ct ); /***************************** USE OF ADDITIVE HOMOMORPHISM *****************************/ /* Multiply the two ciphertexts assuming the modulus in the given public key and store the result in the contents of res, which is assumed to have already been allocated. */ void paillier_mul( paillier_pubkey_t* pub, paillier_ciphertext_t* res, paillier_ciphertext_t* ct0, paillier_ciphertext_t* ct1 ); /* Raise the given ciphertext to power pt and store the result in res, which is assumed to be already allocated. If ct is an encryption of x, then res will become an encryption of x * pt mod n, where n is the modulus in pub. */ void paillier_exp( paillier_pubkey_t* pub, paillier_ciphertext_t* res, paillier_ciphertext_t* ct, paillier_plaintext_t* pt ); /**************************** PLAINTEXT IMPORT AND EXPORT ****************************/ /* Allocate and initialize a paillier_plaintext_t from an unsigned long integer, an array of bytes, or a null terminated string. */ paillier_plaintext_t* paillier_plaintext_from_ui( unsigned long int x ); paillier_plaintext_t* paillier_plaintext_from_bytes( void* m, unsigned int len ); paillier_plaintext_t* paillier_plaintext_from_str( char* str ); /* Export a paillier_plaintext_t as a null terminated string or an array of bytes. In either case the result is allocated for the caller and the original paillier_plaintext_t is unchanged. */ char* paillier_plaintext_to_str( paillier_plaintext_t* pt ); void* paillier_plaintext_to_bytes( unsigned int len, paillier_plaintext_t* pt ); /***************************** CIPHERTEXT IMPORT AND EXPORT *****************************/ /* Import or export a paillier_ciphertext_t from or to an array of bytes. These behave like the corresponding functions for paillier_plaintext_t's. */ paillier_ciphertext_t* paillier_ciphertext_from_bytes( void* c, unsigned int len ); void* paillier_ciphertext_to_bytes( unsigned int len, paillier_ciphertext_t* ct ); /********************** KEY IMPORT AND EXPORT **********************/ /* Import or export public and private keys from or to hexadecimal, ASCII strings, which are suitable for I/O. Note that the corresponding public key is necessary to initialize a private key from a hex string. In all cases, the returned value is allocated for the caller and the values passed are unchanged. */ char* paillier_pubkey_to_hex( paillier_pubkey_t* pub ); char* paillier_prvkey_to_hex( paillier_prvkey_t* prv ); paillier_pubkey_t* paillier_pubkey_from_hex( char* str ); paillier_prvkey_t* paillier_prvkey_from_hex( char* str, paillier_pubkey_t* pub ); /******** CLEANUP ********/ /* These free the structures allocated and returned by various functions within library and should be used when the structures are no longer needed. */ void paillier_freepubkey( paillier_pubkey_t* pub ); void paillier_freeprvkey( paillier_prvkey_t* prv ); void paillier_freeplaintext( paillier_plaintext_t* pt ); void paillier_freeciphertext( paillier_ciphertext_t* ct ); /*********** MISC STUFF ***********/ /* These functions may be passed to the paillier_keygen and paillier_enc functions to provide a source of random numbers. The first reads bytes from /dev/random. On Linux, this device exclusively returns entropy gathered from environmental noise and therefore frequently blocks when not enough is available. The second returns bytes from /dev/urandom. On Linux, this device also returns environmental noise, but augments it with a pseudo-random number generator when not enough is available. The latter is probably the better choice unless you have a specific reason to believe it is insufficient. */ void paillier_get_rand_devrandom( void* buf, int len ); void paillier_get_rand_devurandom( void* buf, int len ); /* This function just allocates and returns a paillier_ciphertext_t which is a valid, _unblinded_ encryption of zero (which may actually be done without knowledge of a public key). Note that this encryption is UNBLINDED, so don't use it unless you want anyone who sees it to know it is an encryption of zero. This function is sometimes handy to get some homomorphic computations started or quickly allocate a paillier_ciphertext_t in which to place some later result. */ paillier_ciphertext_t* paillier_create_enc_zero(void); /* Just a utility used internally when we need round a number of bits up the number of bytes necessary to hold them. */ #define PAILLIER_BITS_TO_BYTES(n) ((n) % 8 ? (n) / 8 + 1 : (n) / 8)