prime.h

voltage 公司提供的一个开发Ibe的工具包

/* Copyright 2003-2004, Voltage Security, all rights reserved.
 */

#include "vibecrypto.h"
#include "environment.h"
#include "base.h"
#include "libctx.h"
#include "algobj.h"
#include "mpint.h"

#ifndef _PRIME_H
#define _PRIME_H

#ifdef __cplusplus
extern "C" {
#endif

/* Generate a prime of bit size primeSizeBits using the sieve and
 * Rabin-Miller tests. The random object will be the source of random
 * bytes and the result will be placed into the prime.
 * <p>The primeSizeBits must be greater than 32. This is almost an
 * arbitrary limit. The code is written so that the length must be
 * greater than or equal to 9, but it is also safer to make sure the
 * length is long enough so that a prime of the exact specified length
 * is found.
 * <p>The leadingBits arg indicates how many of the most significant
 * bits must be set. If the arg is 1, the function will make sure the
 * most significant bit is set, but cannot guarantee any following bits
 * are set (of course, the least significant bit will be set, after
 * all, the prime number will be an odd number). It is possible that
 * the random object happens to generate a value for which the second
 * most significant bit is also set, it's just that the function cannot
 * guarantee any bit other than the most significant. If the arg is 2,
 * the function will make sure the two most significant bits are set.
 * If the leadingBits arg is anything other than 1 or 2, the function
 * will consider it to be 2.
 * <p>The reason for the leadingBits arg is for RSA key pair
 * generation. For example, if the requested RSA modulus size is 1024
 * bits, the key pair generator will generate two 512-bit primes.
 * However, when mulitplying two 512-bit numbers, the result can be
 * 1023 or 1024 bits. If the two most significant bits of each prime
 * are set, then the product will definitely be 1024 bits.
 * <p>The relativePrime arg can be NULL. If so, the function finds a
 * prime. If not, the function will find a prime such that
 * <pre>
 * <code>
 *    prime - 1  is relatively prime with  relativePrime
 * </code>
 * </pre>
 * <p>This is for RSA key pair generation, where the public exponent
 * must be relatively prime with p - 1 and q - 1.
 * <p>If this function cannot generate a prime, it will return
 * VT_ERROR_NO_PRIME_FOUND.
 *
 * @param primeSizeBits The size, in bits, of the prime to generate.
 * @param leadingBits Either 1 or 2, indicates how many of the most
 * significant bits of the prime should be guaranteed to be set.
 * @param random A random object, the source of any random bytes needed.
 * @param relativePrime If NULL, ignored, if not NULL, the function
 * will find a prime such that prime - 1 is relatively prime with this
 * value.
 * @param prime Where the resulting prime will be deposited.
 * @return an int, 0 if the function completed successfully or a
 * non-zero error code.
 */
int VOLT_CALLING_CONV VoltGeneratePrimeRabinMiller VOLT_PROTO_LIST ((
   unsigned int primeSizeBits,
   unsigned int leadingBits,
   VtRandomObject random,
   VoltMpInt *relativePrime,
   VoltMpInt *prime
));

/* Generate a prime of bit size primeSizeBits using the technique
 * outlined in FIPS 186-2, appendix 2. This will perform steps 1 - 5 of
 * section 2.1 in appendix 2.
 * <p>This function currently operates only when primeSizeBits is 160.
 * <p>The routine will use the Rabin-Miller test to determine if a
 * number is prime.
 * <p>The caller must pass in a SEED buffer large enough to hold
 * primeSizeBits. For example, if primeSizeBits is 160, the SEED buffer
 * must be at least 20 bytes. This function will not check the validity
 * of the SEED argument, it is the responsibility of the caller to make
 * sure SEED is a valid buffer (not NULL) and big enough. Upon return,
 * the SEED buffer will contain the original SEED used to generate the
 * prime. The function will set the unsigned int at seedLen to be the
 * number of bytes placed into the SEED buffer. Once again, this
 * function will not check the validity of the seedLen input argument,
 * it is the responsibility of the caller to pass in a valid pointer.
 * <p>If this function cannot generate a prime, it will return
 * VT_ERROR_NO_PRIME_FOUND.
 *
 * @param primeSizeBits The size, in bits, of the prime to generate.
 * @param random A random object, the source of any random bytes needed.
 * @param SEED The buffer into which the function will place the FIPS
 * SEED value.
 * @param seedLen The address where the function will deposit the
 * length, in bytes, of SEED. That is, it will be the number of bytes
 * placed into the SEED buffer.
 * @param prime Where the resulting prime will be deposited.
 * @return an int, 0 if the function completed successfully or a
 * non-zero error code.
 */
int VOLT_CALLING_CONV VoltGeneratePrimeFips VOLT_PROTO_LIST ((
   unsigned int primeSizeBits,
   VtRandomObject random,
   unsigned char *SEED,
   unsigned int *seedLen,
   VoltMpInt *prime
));

/* Run the sieve test on the candidate, then candidate + 2, then + 4
 * and so on. How far up do we go before we give up and generate a new
 * starting point? That's the SIEVE_SIZE.
 */
#define VOLT_SIEVE_SIZE  1000

/* Test the primeCandidate using the Rabin-Miller test. If it is prime,
 * set isPrime to 1, if not, set it to 0.
 * <p>Pass the primeSizeBits so the subroutine does not need to
 * recompute it. It will come in handy knowing how big the random value
 * needs to be.
 *
 * @param mpCtx The MpInt context.
 * @param primeCandidate The value to test.
 * @param primeSizeBits
 * @param random A random object, the source of any random bytes needed.
 * @param isPrime The result, set to 1 if prime, 0 if not.
 * @return an int, 0 if the function completed successfully or a
 * non-zero error code.
 */
int VOLT_CALLING_CONV VoltRabinMillerTest VOLT_PROTO_LIST ((
   VoltMpInt *primeCandidate,
   unsigned int primeSizeBits,
   VtRandomObject random,
   unsigned int *isPrime
));

/* The Rabin-Miller test is iterative. Try a random value, then another
 * and another and so on. How many random values? That's the
 * RABIN_MILLER_COUNT.
 * FIPS specifies the minimum count is 50.
 */
#define VOLT_RABIN_MILLER_COUNT  50

/* Perform sieving on the prime candidate.
 * <p>The sieve represents primeCandidate + increment. The increment is
 * 2 so that we represent only odd numbers.
 *    sieve[0] represents primeCandidate
 *    sieve[1] represents primeCandidate + 2
 *    sieve[2] represents primeCandidate + 4
 *       ...
 * <p> If primeCandidate is evenly divisible by 3, then it is not a
 * prime, no need to run a "costlier" test. But we also know that
 * primeCandidate + 3 and primeCandidate + 6 and so on are also
 * definitely not prime.
 * <p>If primeCandidate is evenly divisible by 5, then it is not a
 * prime, and so on.
 * <p>For all the entries in the sieve, set the value to 0 or 1. If 0,
 * we could not find a prime that evenly divides the candidate. If 1,
 * we did find a divisor. Later on we'll run a stricter test (such as
 * Rabin-Miller) on those entries with the 0. This way, we'll run the
 * time-consuming test fewer times.
 * <p>One more thing, we'll divide primeCandidate by 3. If it does not
 * divide evenly, we'll find the remainder. We can't set sieve[0] to 1,
 * but we know that 3 evenly divides candidate+(candidate-remainder).
 * Using this knowledge, we can still let some entries fal through the
 * sieve.
 *
 * @param primeCandidate The starting point for the sieve entriy
 * representations.
 * @param firstPrimes An array containing the first n odd primes.
 * @param firstPrimesLen How many of the first odd primes passed.
 * @param sieve An array of bytes we'll use. No need to initialize
 * their values.
 * @param sieveSize The number of entries in the sieve.
 * @return an int, 0 if the function completed successfully or a
 * non-zero error code.
 */
int VOLT_CALLING_CONV VoltSieveCandidate VOLT_PROTO_LIST ((
   VoltMpInt *primeCandidate,
   unsigned int *firstPrimes,
   unsigned int firstPrimesLen,
   unsigned char *sieve,
   unsigned int sieveSize
));

/* These are the first n odd primes. Useful in sieving.
 */

/*
 * The first 53 can all be represented by a single unsigned char.
 */
#define FIRST_53_ODD_PRIMES { \
      3,     5,     7,    11,    13,    17,    19,    23, \
     29,    31,    37,    41,    43,    47,    53,    59, \
     61,    67,    71,    73,    79,    83,    89,    97, \
    101,   103,   107,   109,   113,   127,   131,   137, \
    139,   149,   151,   157,   163,   167,   173,   179, \
    181,   191,   193,   197,   199,   211,   223,   227, \
    229,   233,   239,   241,   251 \
}

/* If you are using the first 100 primes, they must reside in a type
 * larger than an unsigned char.
 */
#define FIRST_100_ODD_PRIMES { \
      3,     5,     7,    11,    13,    17,    19,    23, \
     29,    31,    37,    41,    43,    47,    53,    59, \
     61,    67,    71,    73,    79,    83,    89,    97, \
    101,   103,   107,   109,   113,   127,   131,   137, \
    139,   149,   151,   157,   163,   167,   173,   179, \
    181,   191,   193,   197,   199,   211,   223,   227, \
    229,   233,   239,   241,   251,   257,   263,   269, \
    271,   277,   281,   283,   293,   307,   311,   313, \
    317,   331,   337,   347,   349,   353,   359,   367, \
    373,   379,   383,   389,   397,   401,   409,   419, \
    421,   431,   433,   439,   443,   449,   457,   461, \
    463,   467,   479,   487,   491,   499,   503,   509, \
    521,   523,   541,   547 \
}

#ifdef __cplusplus
}
#endif

#endif /* _PRIME_H */