/* testcore.c by Adam L. Young
--- Forward ---
I have found the open source library OpenSSL to be very well
designed, programmed, documented, and supported. As such I
decided to use it as a library for implementing some of my
own advanced cryptographic protocols. In the process I found that
certain fundamental Number-Theoretic primitives were missing.
So, I have decided to give back to the community by donating these
core number theory functions. The functions are:
BN_perfectpower determines and proves if a number is a perfect power
BN_primepower determines and proves if a number is a prime power
BN_sqrtmodprime computes the square root of a number mod a prime
where the prime need not be of a special form
BN_jacobi computes the Jacobi Symbol of a value
BN_chinese_rem_thm chinese remainders two values together
The text books from which this code was written is cited in a
comment in each function. I hope that these routines assist the open
source community in implementing advanced protocols as well.
Adam L. Young
Sunday June 23, 2002
-------------------------------------------------------------
This program was compiled and tested using Cygwin on a Win98
machine, using the Cygwin distribution of openssl-0.9.6d-1.
*** The OpenSSL header file "bn_prime.h" is needed to compile this ****
With the OpenSSL library properly installed on a UNIX system
type:
gcc -o testcore testcore.c -lcrypto
to compile it to get the binary executable "testcore". */
#include <stdio.h>
#include <openssl/err.h>
#include <openssl/bn.h>
#include <openssl/rand.h>
#include "bn_prime.h" /* internal OpenSSL header file with 1st 2048 primes.
*/
#define NUMBEROF_MONTECARLO_ATTEMPTS 32000
/* Function codes. */
#define BN_F_BN_PERFECTPOWER 130
#define BN_F_BN_PRIMEPOWER 131
#define BN_F_BN_SQRTMODPRIME 132
#define BN_F_BN_JACOBI 133
#define BN_F_BN_CHINESE_REM_THM 134
/* Reason codes. */
#define BN_R_N_TOO_LARGE 120
/* -------Below is the Library Prototypes and Descriptions-------- */
int BN_perfectpower(const BIGNUM *n,BIGNUM *x,int *k,BN_CTX *ctx);
/* (**targeted for donation to OpenSSL**) n is a perfect power if
n = x^k, x >= 2, and k >= 2. If n is a perfect power then x and k
are returned. This function only works when lg n <= primes[NUMPRIMES-1]
(i.e., when lg n <= 17863). On success this function returns 1 if n is
a perfect power and 0 otherwise. This function returns -1 on failure.
-1 is returned if 1 >= n. Note that when n is a perfect power this
function may not return the smallest x such that n = x^k. It can be
repeatedly called to find the smallest x. This is done deliberately to
make this a fast test. This is an implementation of the algorithm on
pages 89-90 of the book "Handbook of Applied Cryptography" by
Menezes, Oorshot, Vanstone. This takes O((lg n)^3 lg lg lg n) bit
operations. Bach and Sorenson showed an improved algorithm. */
int BN_primepower(BIGNUM *ret,int *exponent,unsigned int checks,
const BIGNUM *a,BN_CTX *ctx,BN_MONT_CTX *m_ctx);
/* (**targeted for donation to OpenSSL**) On successful completion,
BN_primepower() returns 1 if a is a prime power and 0 otherwise. The
function returns -1 on failure. This function returns -1 if 1 >= a.
If it is a prime power, the prime is returned in ret and the power of
this prime is returned in exponent. This function uses Miller-Rabin
and so outputs wrong answers with probability at most
(1/4)^{checks}. This function can be used to test for primality,
since when it returns 1 and *exponent = 1 the number is a probable
prime. This is an implementation of Algorithm 1.7.5 on page 42
of "A Course in Computational Algebraic Number Theory" by Henri
Cohen. It can be improved slightly by using a binary search in step 4.
This function, like other functions defined here, have goto statements
in them. This was done deliberately to be as direct an implementation
of the algorithm from the source as possible. This helps in verifying
its correctness. Numerous other OpenSSL functions use goto
statements. */
int BN_sqrtmodprime(BIGNUM *x,int *hasroot,const BIGNUM *a,
const BIGNUM *p,BN_CTX *ctx);
/* (**targeted for donation to OpenSSL**) On successful completion,
BN_sqrtmodprime() returns hasroot = 1 if a is a quadratic residue mod p,
and 0 otherwise. The value -1 is returned if an error occurs. It is
required that 1 <= a < p, and p >= 2. If hasroot = 1, a square root of a
is returned in x. It is assumed that p is prime. This is a Monte-Carlo
algorithm that fails to find x with negligible probability. This is an
implementation of a Monte-Carlo version of Algorithm 9.2.9 on page 229 of
"Number Theory with Computer Applications" by R. Kumanduri and C.
Romero. */
int BN_jacobi(const BIGNUM *A,const BIGNUM *N,int *jacobi,
BN_CTX *ctx);
/* (**targeted for donation to OpenSSL**) BN_jacobi() computes the
Jacobi symbol of A with respect to N. Hence, *jacobi = 1 when the
jacobi symbol is unity and *jacobi = -1 when the jacobi symbol is
-1. N must be odd and >= 3. It is required that 0 <= A < N. When
successful 0 is returned. -1 is returned on failure. This is an
implementation of an iterative version of Algorithm 2.149 on page
73 of the book "Handbook of Applied Cryptography" by Menezes,
Oorshot, Vanstone. Note that there is a typo in step 1. Step 1
should return the value 1. The algorithm has a running time
of O((lg N)^2) bit operations. */
int BN_chinese_rem_thm(const BIGNUM *g1,const BIGNUM *p,
const BIGNUM *g2,const BIGNUM *q,BIGNUM *g,BN_CTX *ctx);
/* (**targeted for donation to OpenSSL**) BN_chinese_rem_thm(): This is
an implementation of the Chinese Remainder Theorem. It Chinese remainders g1
mod p with g2 mod q to get g mod pq. It is assumed that gcd(p,q)=1, g1 is in
Z_p^* and g2 is in Z_q^*. When successful this function returns 0. It
returns -1 on failure. This algorithm was taken from Kenneth R. Rosen
"Elementary Number Theory and its Applications"
Theorem 8.21 on page 313. Note: Code for the Chinese Remainder Theorem
could not be found in any of the OpenSSL C source files. This could be
because in version 2.0 and later of PKCS#1, RSA decryption does not use
the Chinese Remainder Theorem directly. A slighly more efficient
algorithm is used. */
int BN_witness(const BIGNUM *a,const BIGNUM *n,const BIGNUM *nminus1,
const BIGNUM *m,int k,BN_CTX *ctx,BN_MONT_CTX *mont);
/* (**targeted for donation to OpenSSL**) BN_witness() assumes that
n = (2^k) m + 1 and that m is odd. This function also assumes that
nminus1 = n-1. It is taken directly from page 137 of "Cryptography
Theory and Practice" by D. R. Stinson. It performs the Miller-Rabin
probabilistic primality test on n. It returns the wrong answer with
probability at most 1/4. It returns 1 if n is composite and 0 if it
is a probable prime. The input a is a candidate witness of
compositeness. This function was written and used in lieu of the
static internal OpenSSL function witness() defined in bn_prime.c.
The reason for this is that witness() defines an argument BIGNUM *w
without using const for it. witness() changes this value, which is
a potential witness for compositeness. The witness is used explicitly
in the ensuing computations of the prime power test algorithm, and so
Miller-Rabin should not modify it. That is why this routine uses
the temporary variable b. A witness of compositeness is what proves
that the number in question is composite, and this "proof" should
not be modified by the testing algorithm. */
int test_perfectpower(void);
/* (**targeted for donation to OpenSSL**) test_perfectpower() performs
some rudimentary tests on the function BN_perfectpower(). Just like
the OpenSSL BN testing routines. It returns 1 when successful and
0 on failure. */
int test_jacobi(void);
/* (**targeted for donation to OpenSSL**) test_jacobi() performs some
rudimentary tests on the function BN_jacobi(). It returns 1 when
successful and 0 on failure. */
int test_primepower(void);
/* (**targeted for donation to OpenSSL**) test_primepower() performs
rudimentary tests on BN_primepower(). It returns 1 when successful
and 0 on failure. */
int test_sqrtmodprime(void);
/* (**targeted for donation to OpenSSL**) test_sqrtmodprime()
performs rudimentary tests on the function BN_sqrtmodprime().
It returns 1 when successful and 0 on failure. */
int test_chinese_rem_thm(void);
/* (**targeted for donation to OpenSSL**) test_chinese_rem_thm()
performs some rudimenatary tests on the function
BN_chinese_rem_thm(). It returns 1 when successful and 0 on
failure. */
int test_core_number_theory_functions(void);
/* (**targeted for donation to OpenSSL**)
test_core_number_theory_functions tests the five functions:
BN_perfectpower,BN_primepower, BN_jacobi,BN_chinese_rem_thm,
and BN_sqrtmodprime. It prints the results to stdio. It
returns 1 when successful and 0 on failure. The OpenSSL BN test
functions return 1 on success and 0 on failure. */
/* -----------Below are the Library Routines---------------- */
int main(int argc,char **argv)
{
int i,retval;
for (i=0;i<25;i++)
{
retval = test_core_number_theory_functions();
if (retval == 0)
break;
}
return 0;
}
int BN_sqrtmodprime(BIGNUM *x,int *hasroot,const BIGNUM *a,
const BIGNUM *p,BN_CTX *ctx)
{
int i,jacobi,error = 0;
BIGNUM *two,*tmp2,*tmp,*minus1,*n,*s,*z,*b,*m;
BIGNUM *rminusm,*rminusmminus1,*pminus1,*r,*y;
/* (**targeted for donation to OpenSSL**) On successful completion,
BN_sqrtmodprime() returns hasroot = 1 if a is a quadratic residue mod p,
and 0 otherwise. The value -1 is returned if an error occurs. It is
required that 1 <= a < p, and p >= 2. If hasroot = 1, a square root of a
is returned in x. It is assumed that p is prime. This is a Monte-Carlo
algorithm that fails to find x with negligible probability. This is an
implementation of a Monte-Carlo version of Algorithm 9.2.9 on page 229 of
"Number Theory with Computer Applications" by R. Kumanduri and C.
Romero. */
if (!hasroot)
return -1;
*hasroot = 0;
if ((!x) || (!a) || (!p))
return -1;
if (BN_cmp(BN_value_one(),p) >= 0)
return -1;
if (BN_cmp(BN_value_one(),a) > 0)
return -1;
if (BN_cmp(a,p) >= 0)
return -1; /* Do some quick input verifications */
minus1 = BN_new();s = BN_new();n = BN_new();tmp = BN_new();
b = BN_new();m = BN_new();r = BN_new();y = BN_new();
two = BN_new();tmp2 = BN_new();rminusm = BN_new();
pminus1 = BN_new();rminusmminus1 = BN_new();z = BN_new();
BN_hex2bn(&minus1,"-1");
BN_set_word(r,0); /* This function was written by Adam L. Young */
BN_set_word(two,2);
BN_sub(pminus1,p,BN_value_one()); /* step 1 - Find r and s */
BN_copy(s,pminus1);
for (;;)
{
if (BN_is_odd(s))
break;
BN_add_word(r,1);
BN_rshift1(s,s);
}
for (i=0;i<NUMBEROF_MONTECARLO_ATTEMPTS;i++)
{ /* step 2 - Get nonresidue */
BN_rand_range(n,pminus1);
BN_add_word(n,1);
BN_jacobi(n,p,&jacobi,ctx);
if (jacobi == -1)
goto aftergetnonresidue;
}
error = -1;
goto endAlg929;
aftergetnonresidue:
BN_mod_exp(z,n,s,p,ctx); /* step 3 - Initialize */
BN_add(tmp,s,BN_value_one());
BN_rshift1(tmp,tmp);
BN_mod_exp(x,(BIGNUM *) a,tmp,p,ctx);
BN_mod_exp(b,(BIGNUM *) a,s,p,ctx);
step4Alg929: /* step 4 - Are we done? */
if (BN_is_one(b))
{
*hasroot = 1;
goto endAlg929; /* x is a root of a mod p */
}
BN_set_word(m,1); /* step 5 - Find the order of b */
BN_mod_mul(y,b,b,p,ctx);
for (;;)
{
if (BN_is_one(y))
break;
BN_mod_mul(y,y,y,p,ctx);
BN_add_word(m,1);
}
if (!BN_cmp(r,m)) /* step 6 - Nonresidue? */
goto endAlg929; /* a is a quadratic nonresidue */
BN_sub(rminusm,r,m); /* step 7 - Iterate */
BN_sub(rminusmminus1,rminusm,BN_value_one());
BN_mod_exp(tmp,two,rminusmminus1,pminus1,ctx);
BN_mod_exp(tmp2,z,tmp,p,ctx);
BN_mod_mul(x,x,tmp2,p,ctx);
BN_mod_exp(tmp,two,rminusm,pminus1,ctx);
BN_mod_exp(tmp,z,tmp,p,ctx);
BN_mod_mul(b,b,tmp,p,ctx);
BN_mod_mul(z,z,tmp,p,ctx);
goto step4Alg929;
endAlg929:
if (!(*hasroot))
BN_set_word(x,0);
BN_clear_free(minus1);BN_clear_free(s);BN_clear_free(r);
BN_clear_free(z);BN_clear_free(b);BN_clear_free(m);
BN_clear_free(y);BN_clear_free(n);BN_clear_free(tmp);
BN_clear_free(two);BN_clear_free(tmp2);BN_clear_free(pminus1);
BN_clear_free(rminusm);BN_clear_free(rminusmminus1);
return error;
}
int BN_perfectpower(const BIGNUM *n,BIGNUM *x,int *k,BN_CTX *ctx)
{
int compareval,isperfpow=0,exponent,i,numbits,p;
BIGNUM *a,*b,*bignump,*tmp;
/* (**targeted for donation to OpenSSL**) n is a perfect power if
n = x^k, x >= 2, and k >= 2. If n is a perfect power then x and k
are returned. This function only works when lg n <= primes[NUMPRIMES-1]
(i.e., when lg n <= 17863). On success this function returns 1 if n is
a perfect power and 0 otherwise. This function returns -1 on failure.
-1 is returned if 1 >= n. Note that when n is a perfect power this
function may not return the smallest x such that n = x^k. It can be
repeatedly called to find the smallest x. This is done deliberately to
make this a fast test. This is an implementation of the algorithm on
pages 89-90 of the book "Handbook of Applied Cryptography" by
Menezes, Oorshot, Vanstone. This takes O((lg n)^3 lg lg lg n) bit
operations. Bach and Sorenson showed an improved algorithm. */
if ((!n) || (!x) || (!k) || (!ctx))
return -1;
if (BN_cmp(BN_value_one(),n) >= 0)
return -1;
numbits = BN_num_bits(n);
if (numbits > primes[NUMPRIMES-1])
{
BNerr(BN_F_BN_PERFECTPOWER,BN_R_N_TOO_LARGE);
return -1;
}
/* This function was written by Adam L. Young */
tmp = BN_new();a = BN_new();b = BN_new();bignump = BN_new();
*k = 0;
for (i=0;;i++)
{ /* compute integer approximation x of n^{1/p} */
p = primes[i];
if (p > numbits)
break;
BN_set_word(bignump,p);
exponent = (numbits/p) + 1;
BN_set_word(a,2);
BN_lshift(b,BN_value_one(),exponent);
for (;;)
{ /* now do a binary search between a and b. */
BN_sub(x,b,a);
BN_rshift1(x,x);
BN_add(x,x,a);
BN_exp(tmp,x,bignump,ctx);
compareval = BN_cmp(tmp,n);
if (!compareval)
{
isperfpow = 1;
*k = p;
break;
}
BN_sub(tmp,b,BN_value_one());
if (!BN_cmp(a,tmp))
break;
if (compareval > 0)
BN_copy(b,x); /* set b = x */
else
BN_copy(a,x); /* set a = x */
}
if (isperfpow)
break;
}
if (!isperfpow)
BN_zero(x);
BN_clear_free(tmp);BN_clear_free(a);
BN_clear_free(b);BN_clear_free(bignump);
return isperfpow;
}
int BN_primepower(BIGNUM *ret,int *exponent,unsigned int checks,
const BIGNUM *a,BN_CTX *ctx,BN_MONT_CTX *m_ctx)
{
int isprimepower,retval,k;
BIGNUM *zero,*rem,*two,*q,*aminus1odd;
BIGNUM *d,*thewitness,*aminus1,*tmp,*p;
/* (**targeted for donation to OpenSSL**) On successful completion,
BN_primepower() returns 1 if a is a prime power and 0 otherwise. The
function returns -1 on failure. This function returns -1 if 1 >= a.
If it is a prime power, the prime is returned in ret and the power of
this prime is returned in exponent. This function uses Miller-Rabin
and so outputs wrong answers with probability at most
(1/4)^{checks}. This function can be used to test for primality,
since when it returns 1 and *exponent = 1 the number is a probable
prime. This is an implementation of Algorithm 1.7.5 on page 42
of "A Course in Computational Algebraic Number Theory" by Henri
Cohen. It can be improved slightly by using a binary search in step 4.
This function, like other functions defined here, have goto statements
in them. This was done deliberately to be as direct an implementation
of the algorithm from the source as possible. This helps in verifying
its correctness. Numerous other OpenSSL functions use goto
statements. */
if (!exponent)
return -1;
*exponent = 0;
if (!ret)
return -1;
BN_set_word(ret,0);
if ((!checks) || (!a) || (!ctx) || (!m_ctx))
return -1;
if (BN_cmp(BN_value_one(),a) >= 0)
return -1; /* invalid input */
isprimepower = 0;
tmp = BN_new();p = BN_new();rem = BN_new();q = BN_new();
d = BN_new();two = BN_new();aminus1odd = BN_new();
thewitness = BN_new();aminus1 = BN_new();zero = BN_new();
/* This function was written by Adam L. Young */
BN_set_word(zero,0);
BN_set_word(two,2);
if (!BN_is_odd(a)) /* step 1 */
{
BN_set_word(p,2);
goto step4;
}
else
BN_copy(q,a);
step2:
BN_sub(aminus1,q,BN_value_one());
/* now generate witness randomly between 1 and a-1 inclusive */
BN_rand_range(thewitness,aminus1);
BN_add(thewitness,thewitness,BN_value_one());
BN_copy(aminus1odd,aminus1);
for (k=0;;k++)
{
if (BN_is_odd(aminus1odd))
break;
BN_rshift1(aminus1odd,aminus1odd);
}
if (!BN_MONT_CTX_set(m_ctx,q,ctx))
{
isprimepower = -1;
goto endoftest;
}
retval = BN_witness(thewitness,q,aminus1,aminus1odd,k,ctx,m_ctx);
if (retval == -1)
{
isprimepower = -1; /* witness() failed in step 2 */
goto endoftest;
}
if (!retval) /* i.e., if q is a probable prime */
{
BN_copy(p,q);
goto step4;
}
BN_mod_exp_simple(tmp,thewitness,q,(BIGNUM *) q,ctx); /* step 3 */
BN_sub(tmp,tmp,thewitness);
if (BN_cmp(zero,tmp) > 0)
BN_sub(tmp,zero,tmp);
BN_gcd(d,tmp,q,ctx); /* BN_gcd() cannot handle negative values. */
if ((BN_is_one(d)) || (!BN_cmp(d,q)))
goto endoftest; /* if d = 1 or q then n is not prime so terminate */
else
{
BN_copy(q,d);
goto step2;
}
step4:
retval = BN_is_odd(p);
if (retval)
retval = BN_is_prime(p,checks,NULL,ctx,NULL);
else
retval = 0;
if (!BN_cmp(p,two))
retval = 1;
if (retval == -1)
{
isprimepower = -1; /* failed in step 4 */
goto endoftest;
}
if (!retval) /* i.e., if p is a composite */
{
BN_copy(q,p);
goto step2;
}
if (retval == 1) /* i.e., if p is a highly probable prime */
{ /* now divide a by p repeatedly, a binary search could be used here...
*/
BN_copy(tmp,a);
for (*exponent=1;;(*exponent)++)
{
BN_div(tmp,rem,tmp,p,ctx);
if ((BN_is_one(tmp)) && (BN_is_zero(rem)))
{
isprimepower = 1;
BN_copy(ret,p);
break;
}
if (!BN_is_zero(rem))
break; /* a is not a prime power */
}
}
endoftest:
if (!isprimepower)
{ /* produce a well-defined output when its not a prime power. */
*exponent = 0;
BN_set_word(ret,0);
}
BN_clear_free(q);BN_clear_free(two);BN_clear_free(tmp);
BN_clear_free(p);BN_clear_free(zero);BN_clear_free(rem);
BN_clear_free(d);BN_clear_free(aminus1);
BN_clear_free(aminus1odd);BN_clear_free(thewitness);
return isprimepower;
}
int BN_chinese_rem_thm(const BIGNUM *g1,const BIGNUM *p,
const BIGNUM *g2,const BIGNUM *q,BIGNUM *g,BN_CTX *ctx)
{
BIGNUM *tmp,*tmp2,*tmp3;
/* (**targeted for donation to OpenSSL**) BN_chinese_rem_thm(): This is
an implementation of the Chinese Remainder Theorem. It Chinese remainders
g1 mod p with g2 mod q to get g mod pq. It is assumed that gcd(p,q)=1,
g1 is in Z_p^* and g2 is in Z_q^*. When successful this function returns
0. It returns -1 on failure. This algorithm was taken from
Kenneth R. Rosen "Elementary Number Theory and its Applications"
Theorem 8.21 on page 313. Note: Code for the Chinese Remainder Theorem
could not be found in any of the OpenSSL C source files. This could be
because in version 2.0 and later of PKCS#1, RSA decryption does not use
the Chinese Remainder Theorem directly. A slighly more efficient
algorithm is used. */
if ((!g1) || (!p) || (!g2) || (!q) || (!g) || (!ctx))
return -1; /* This function was written by Adam L. Young */
if (BN_cmp(g1,p) >= 0)
return -1;
if (BN_cmp(g2,q) >= 0)
return -1;
tmp = BN_new();tmp2 = BN_new();tmp3 = BN_new();
BN_mod(tmp,q,p,ctx); /* compute tmp = q mod p */
BN_mod_inverse(tmp2,tmp,p,ctx);
BN_mul(tmp,tmp2,(BIGNUM *) q,ctx);
BN_mul(tmp2,tmp,(BIGNUM *) g1,ctx);
BN_mod(tmp3,p,q,ctx);
BN_mod_inverse(tmp,tmp3,q,ctx);
BN_mul(tmp3,tmp,(BIGNUM *) p,ctx);
BN_mul(tmp,tmp3,(BIGNUM *) g2,ctx);
BN_add(tmp3,tmp,tmp2);
BN_mul(tmp,(BIGNUM *) p,(BIGNUM *) q,ctx);
BN_mod(g,tmp3,tmp,ctx);
BN_clear_free(tmp);BN_clear_free(tmp2);BN_clear_free(tmp3);
return 0;
}
int test_core_number_theory_functions(void)
{
int error=0;
/* (**targeted for donation to OpenSSL**)
test_core_number_theory_functions tests the five functions:
BN_perfectpower,BN_primepower, BN_jacobi,BN_chinese_rem_thm,
and BN_sqrtmodprime. It prints the results to stdio. It
returns 1 when successful and 0 on failure. The OpenSSL test
functions return 1 on success and 0 on failure. */
if (!test_perfectpower())
{
printf("test_perfectpower() failed.\n");
goto endTestCoreNumberTheoryFunctions;
}
printf("test_perfectpower() succeeded.\n");
if (!test_primepower())
{
printf("test_primepower() failed.\n");
goto endTestCoreNumberTheoryFunctions;
}
printf("test_primepower() succeeded.\n");
if (!test_jacobi())
{
printf("test_jacobi() failed.\n");
goto endTestCoreNumberTheoryFunctions;
}
printf("test_jacobi() succeeded.\n");
if (!test_sqrtmodprime())
{
printf("test_sqrtmodprime() failed.\n");
goto endTestCoreNumberTheoryFunctions;
}
printf("test_sqrtmodprime() succeeded.\n");
if (!test_chinese_rem_thm())
{
printf("test_chinese_rem_thm() failed.\n");
goto endTestCoreNumberTheoryFunctions;
}
printf("test_chinese_rem_thm() succeeded.\n");
error = 1;
endTestCoreNumberTheoryFunctions:
return error;
}
int test_chinese_rem_thm(void)
{
unsigned char buff[16];
int error=0;
BIGNUM *p,*g1,*q,*g2,*g,*tmp,*two;
BN_CTX *thectx;
/* (**targeted for donation to OpenSSL**) test_chinese_rem_thm()
performs some rudimenatary tests on the function
BN_chinese_rem_thm(). It returns 1 when successful and 0 on
failure. */
p=BN_new();g1=BN_new();q=BN_new();g=BN_new();
tmp=BN_new();two=BN_new();g2=BN_new();
BN_set_word(two,2);
thectx = BN_CTX_new();
RAND_bytes(buff,16);
BN_bin2bn(buff,16,p);
BN_add(p,p,two);
do {
RAND_bytes(buff,16);
BN_bin2bn(buff,16,q);
BN_add(q,q,two);
BN_gcd(tmp,p,q,thectx);
} while (!BN_is_one(tmp));
do {
RAND_bytes(buff,16);
BN_bin2bn(buff,16,g1);
BN_add(g1,g1,two);
} while (BN_cmp(g1,p) >= 0);
do {
RAND_bytes(buff,16);
BN_bin2bn(buff,16,g2);
BN_add(g2,g2,two);
} while (BN_cmp(g2,q) >= 0);
fprintf(stdout,"p = ");
BN_print_fp(stdout,p);fprintf(stdout,"\n");
fprintf(stdout,"g1 = ");
BN_print_fp(stdout,g1);fprintf(stdout,"\n");
fprintf(stdout,"q = ");
BN_print_fp(stdout,q);fprintf(stdout,"\n");
fprintf(stdout,"g2 = ");
BN_print_fp(stdout,g2);fprintf(stdout,"\n");
if (BN_chinese_rem_thm(g1,p,g2,q,g,thectx))
goto endTestChineseRemThm;
BN_mod(tmp,g,p,thectx);
if (BN_cmp(tmp,g1))
goto endTestChineseRemThm;
BN_mod(tmp,g,q,thectx);
if (BN_cmp(tmp,g2))
goto endTestChineseRemThm;
fprintf(stdout,"g = ");
BN_print_fp(stdout,g);fprintf(stdout,"\n");
error = 1;
endTestChineseRemThm:
BN_clear_free(g);BN_clear_free(two);BN_clear_free(tmp);
BN_clear_free(p);BN_clear_free(q);
BN_clear_free(g1);BN_clear_free(g2);
BN_CTX_free(thectx);
return error;
}
int test_sqrtmodprime(void)
{
unsigned char buff[16];
int jacobi,error=0,hasroot;
BIGNUM *a,*p,*pminus1,*x,*tmp,*tmp2;
BN_CTX *thectx;
BN_MONT_CTX *mont;
/* (**targeted for donation to OpenSSL**) test_sqrtmodprime()
performs rudimentary tests on the function BN_sqrtmodprime().
It returns 1 when successful and 0 on failure. */
pminus1=BN_new();p=BN_new();x=BN_new();
tmp=BN_new();tmp2=BN_new();a=BN_new();
thectx = BN_CTX_new();
mont = BN_MONT_CTX_new();
BN_MONT_CTX_init(mont);
do { /* get a probable prime to test with */
RAND_bytes(buff,16);
BN_bin2bn(buff,16,p);
} while (BN_is_prime(p,90,NULL,thectx,NULL) != 1);
fprintf(stdout,"p = ");
BN_print_fp(stdout,p);fprintf(stdout,"\n");
BN_sub(pminus1,p,BN_value_one());
BN_rand_range(a,pminus1);
BN_add_word(a,1);
BN_mod_mul(a,a,a,p,thectx);
fprintf(stdout,"a^2 mod p = ");
BN_print_fp(stdout,a);fprintf(stdout,"\n");
if (BN_sqrtmodprime(x,&hasroot,a,p,thectx))
goto endTestSqrtModPrime;
if (!hasroot)
goto endTestSqrtModPrime;
fprintf(stdout,"sqrt = ");
BN_print_fp(stdout,x);fprintf(stdout,"\n");
BN_mod_mul(tmp2,x,x,p,thectx);
if (BN_cmp(tmp2,a))
goto endTestSqrtModPrime;
do { /* test quadratic non-residue */
BN_rand_range(a,pminus1);
BN_add_word(a,1);
BN_jacobi(a,p,&jacobi,thectx);
} while (jacobi == 1);
if (BN_sqrtmodprime(x,&hasroot,a,p,thectx))
goto endTestSqrtModPrime;
if (hasroot)
goto endTestSqrtModPrime;
error = 1;
endTestSqrtModPrime:
BN_clear_free(pminus1);BN_clear_free(x);
BN_clear_free(a);BN_clear_free(tmp2);
BN_clear_free(tmp);BN_clear_free(p);
BN_CTX_free(thectx);
BN_MONT_CTX_free(mont);
return error;
}
int test_perfectpower(void)
{
unsigned char buff[16];
int i,error=0,exponent;
int perfectpowers[14] = {4,8,9,16,25,27,32,36,49,64,81,100,144,169};
int nonperfectpowers[14] = {2,3,5,7,10,11,12,13,14,15,17,18,19,20};
BIGNUM *n,*x,*exp,*sixteen;
BN_CTX *thectx;
/* (**targeted for donation to OpenSSL**) test_perfectpower() performs
some rudimentary tests on the function BN_perfectpower(). Just like
the OpenSSL BN testing routines. It returns 1 when successful and
0 on failure. */
n=BN_new();x=BN_new();exp=BN_new();sixteen=BN_new();
BN_set_word(sixteen,16);
thectx = BN_CTX_new();
for (i = 0;i < 14;i++)
{
BN_set_word(n,perfectpowers[i]);
if (BN_perfectpower(n,x,&exponent,thectx) != 1)
goto endTestPerfectPower;
BN_set_word(n,nonperfectpowers[i]);
if (BN_perfectpower(n,x,&exponent,thectx))
goto endTestPerfectPower;
}
if (BN_perfectpower(BN_value_one(),x,&exponent,thectx) != -1)
goto endTestPerfectPower;
printf("Done with 15 tests in perfect power.\n");
RAND_bytes(buff,16);
BN_bin2bn(buff,16,x);
BN_add(x,x,BN_value_one());
BN_add(x,x,BN_value_one());
BN_rand_range(exp,sixteen); /* exp = 0,1,2,...,15 */
BN_add(exp,exp,BN_value_one()); /* exp = 1,2,3,...,16 */
BN_add(exp,exp,BN_value_one()); /* exp = 2,3,4,...,17 */
BN_exp(n,x,exp,thectx);
fprintf(stdout,"n = ");
BN_print_fp(stdout,n);fprintf(stdout,"\n");
if (!BN_perfectpower(n,x,&exponent,thectx))
{
printf("BN_perfectpower() returned 0.\n");
goto endTestPerfectPower;
}
if (exponent < 2)
{
printf("exponent = %d\n",exponent);
goto endTestPerfectPower;
}
fprintf(stdout,"x = ");
BN_print_fp(stdout,x);fprintf(stdout,"\n");
fprintf(stdout,"exponent = %d\n",exponent);
error = 1;
endTestPerfectPower:
BN_clear_free(x);BN_clear_free(sixteen);
BN_clear_free(exp);BN_clear_free(n);
BN_CTX_free(thectx);
return error;
}
int test_primepower(void)
{
unsigned char buff[16];
int primepowers[14] = {2,3,4,5,7,8,9,11,13,16,17,19,23,25};
int nonprimepowers[14] = {50,52,6,10,12,14,15,18,20,21,22,24,36,225};
int i,exponent,error=0;
BIGNUM *exp,*sixteen,*n,*p,*tmp,*tmp2;
BN_CTX *thectx;
BN_MONT_CTX *mont;
/* (**targeted for donation to OpenSSL**) test_primepower() performs
rudimentary tests on BN_primepower(). It returns 1 when successful
and 0 on failure. */
n=BN_new();p=BN_new();exp=BN_new();
tmp=BN_new();sixteen=BN_new();tmp2=BN_new();
thectx = BN_CTX_new();
mont = BN_MONT_CTX_new();
BN_MONT_CTX_init(mont);
BN_set_word(sixteen,16);
for (i = 0;i < 14;i++)
{
BN_set_word(n,primepowers[i]);
if (BN_primepower(p,&exponent,90,n,thectx,mont) != 1)
goto endTestPrimePower;
BN_set_word(n,nonprimepowers[i]);
if (BN_primepower(p,&exponent,90,n,thectx,mont))
goto endTestPrimePower;
}
do { /* now test a larger value */
RAND_bytes(buff,16);
BN_bin2bn(buff,16,p);
} while (BN_is_prime(p,90,NULL,thectx,NULL) != 1);
printf("the 14 test cases passed.\n");
BN_rand_range(exp,sixteen); /* exp = 0,1,2,...,15 */
BN_add(exp,exp,BN_value_one()); /* exp = 1,2,3,...,16 */
BN_exp(tmp,p,exp,thectx);
fprintf(stdout,"p^exp = ");
BN_print_fp(stdout,tmp);fprintf(stdout,"\n");
if (!BN_primepower(tmp2,&exponent,90,tmp,thectx,mont))
{
printf("ERROR: BN_primepower returned 0.\n");
goto endTestPrimePower;
}
if (BN_get_word(exp) != exponent)
{
printf("ERROR: exponent != exp.\n");
goto endTestPrimePower;
}
fprintf(stdout,"p = ");
BN_print_fp(stdout,tmp2);fprintf(stdout,"\n");
fprintf(stdout,"exp = %d\n",exponent);
error = 1;
endTestPrimePower:
BN_clear_free(n);BN_clear_free(p);
BN_clear_free(exp);BN_clear_free(sixteen);
BN_clear_free(tmp2);BN_clear_free(tmp);
BN_CTX_free(thectx);
BN_MONT_CTX_free(mont);
return error;
}
int BN_witness(const BIGNUM *a,const BIGNUM *n,const BIGNUM *nminus1,
const BIGNUM *m,int k,BN_CTX *ctx,BN_MONT_CTX *mont)
{
int i,retval,returnvalue;
BIGNUM *b;
/* (**targeted for donation to OpenSSL**) BN_witness() assumes that
n = (2^k) m + 1 and that m is odd. This function also assumes that
nminus1 = n-1. It is taken directly from page 137 of "Cryptography
Theory and Practice" by D. R. Stinson. It performs the Miller-Rabin
probabilistic primality test on n. It returns the wrong answer with
probability at most 1/4. It returns 1 if n is composite and 0 if it
is a probable prime. The input a is a candidate witness of
compositeness. This function was written and used in lieu of the
static internal OpenSSL function witness() defined in bn_prime.c.
The reason for this is that witness() defines an argument BIGNUM *w
without using const for it. witness() changes this value, which is
a potential witness for compositeness. The witness is used explicitly
in the ensuing computations of the prime power test algorithm, and so
Miller-Rabin should not modify it. That is why this routine uses
the temporary variable b. A witness of compositeness is what proves
that the number in question is composite, and this "proof" should
not be modified by the testing algorithm. */
b = BN_new();
BN_mod_exp_mont(b,(BIGNUM *) a,m,n,ctx,mont); /* compute b = a^m mod n */
if (BN_is_one(b))
{ /* This function was written by Adam L. Young */
returnvalue = 0;
goto endMillerRabin;
}
for (i=0;i<=k-1;i++)
{
if (BN_cmp(b,nminus1) == 0)
{
returnvalue = 0;
goto endMillerRabin;
}
else
{
retval = BN_mod_mul(b,b,b,n,ctx);
if (!retval)
{
printf("MillerRabin(): BN_mod_mul() failed.\n");
returnvalue = -1;
goto endMillerRabin;
}
}
}
returnvalue = 1; /* answer "n is composite" */
endMillerRabin:
BN_clear_free(b);
return returnvalue;
}
int test_jacobi(void)
{
unsigned char buff[32];
int retval,error=0,jacobi;
BIGNUM *a,*n,*tmp;
BN_CTX *thectx;
/* (**targeted for donation to OpenSSL**) test_jacobi() performs some
rudimentary tests on the function BN_jacobi(). It returns 1 when
successful and 0 on failure. */
thectx = BN_CTX_new();
a=BN_new();n=BN_new();tmp=BN_new();
BN_set_word(a,7411); /*--test case from p. 134 of D. R. Stinson --*/
BN_set_word(n,9283);
if (BN_jacobi(a,n,&jacobi,thectx))
goto endTestJacobi;
if (jacobi != -1)
goto endTestJacobi;
BN_set_word(a,6278); /*--test case from p. 132 of D. R. Stinson --*/
BN_set_word(n,9975);
if (BN_jacobi(a,n,&jacobi,thectx))
goto endTestJacobi;
if (jacobi != -1)
goto endTestJacobi;
BN_set_word(a,158); /*--test case from p. 74 of Men. Oorsh. Vans. --*/
BN_set_word(n,235);
if (BN_jacobi(a,n,&jacobi,thectx))
goto endTestJacobi;
if (jacobi != -1)
goto endTestJacobi;
BN_set_word(a,4); /*--test case from p. 216 of Kumanduri Romero --*/
BN_set_word(n,7);
if (BN_jacobi(a,n,&jacobi,thectx))
goto endTestJacobi;
if (jacobi != 1)
goto endTestJacobi;
BN_set_word(a,68); /*--test case from p. 363 of K. R. Rosen --*/
BN_set_word(n,111);
if (BN_jacobi(a,n,&jacobi,thectx))
goto endTestJacobi;
if (jacobi != 1)
goto endTestJacobi;
/* Now test a large square in Z_n^* */
RAND_bytes(buff,32);
BN_bin2bn(buff,32,n);
BN_add(n,n,BN_value_one());
BN_add(n,n,BN_value_one());
BN_add(n,n,BN_value_one()); /* n must be at least 3 */
if (!BN_is_odd(n))
BN_add(n,n,BN_value_one()); /* n must be odd */
fprintf(stdout,"n = ");
BN_print_fp(stdout,n);fprintf(stdout,"\n");
do {
BN_rand_range(a,n);
BN_add(a,a,BN_value_one());
BN_gcd(tmp,a,n,thectx);
} while (!BN_is_one(tmp));
fprintf(stdout,"a = ");
BN_print_fp(stdout,a);fprintf(stdout,"\n");
BN_mod_mul(a,a,a,n,thectx);
fprintf(stdout,"a^2 = ");
BN_print_fp(stdout,a);fprintf(stdout,"\n");
retval = BN_jacobi(a,n,&jacobi,thectx);
printf("BN_jacobi returned %d.\n",retval);
if (retval)
goto endTestJacobi;
fprintf(stdout,"jacobi = %d\n",jacobi);
if (jacobi != 1)
goto endTestJacobi;
error = 1;
endTestJacobi:
BN_clear_free(a);BN_clear_free(n);BN_clear_free(tmp);
BN_CTX_free(thectx);
return error;
}
int BN_jacobi(const BIGNUM *A,const BIGNUM *N,int *jacobi,
BN_CTX *ctx)
{
int e,returnvalue=0,s,bit0,bit1,bit2,a1bit0,a1bit1;
BIGNUM *zero,*a1,*n1,*three,*tmp;
/* (**targeted for donation to OpenSSL**) BN_jacobi() computes the
Jacobi symbol of A with respect to N. Hence, *jacobi = 1 when the
jacobi symbol is unity and *jacobi = -1 when the jacobi symbol is
-1. N must be odd and >= 3. It is required that 0 <= A < N. When
successful 0 is returned. -1 is returned on failure. This is an
implementation of an iterative version of Algorithm 2.149 on page
73 of the book "Handbook of Applied Cryptography" by Menezes,
Oorshot, Vanstone. Note that there is a typo in step 1. Step 1
should return the value 1. The algorithm has a running time
of O((lg N)^2) bit operations. */
if (!jacobi)
return -1;
*jacobi = 1;
if ((!A) || (!N) || (!ctx))
return -1;
if (!BN_is_odd(N))
return -1; /* ERROR: BN_jacobi() given an even N */
if (BN_cmp(A,N) >= 0)
return -1;
n1=BN_new();zero=BN_new();a1=BN_new();three=BN_new();tmp=BN_new();
BN_set_word(zero,0);
BN_set_word(three,3);
if (BN_cmp(N,three) < 0)
{ /* This function was written by Adam L. Young */
returnvalue = -1;
goto endBN_jacobi;
}
if (BN_cmp(zero,A) > 0)
{
returnvalue = -1;
goto endBN_jacobi;
}
BN_copy(a1,A);
BN_copy(n1,N);
startjacobistep1:
if (BN_is_zero(a1)) /* step 1 */
goto endBN_jacobi; /* *jacobi = 1; */
if (BN_is_one(a1)) /* step 2 */
goto endBN_jacobi; /* *jacobi = 1; */
for (e=0;;e++) /* step 3 */
if (BN_is_odd(a1))
break;
else
BN_rshift1(a1,a1);
s = 1; /* step 4 */
bit0 = BN_is_odd(n1);
bit1 = BN_is_bit_set(n1,1);
if (e % 2)
{
bit2 = BN_is_bit_set(n1,2);
if ((!bit2) && (bit1) && (bit0))
s = -1;
if ((bit2) && (!bit1) && (bit0))
s = -1;
}
a1bit0 = BN_is_odd(a1); /* step 5 */
a1bit1 = BN_is_bit_set(a1,1);
if (((bit1) && (bit0)) && ((a1bit1) && (a1bit0)))
s = -s;
BN_mod(n1,n1,a1,ctx); /* step 6 */
BN_copy(tmp,a1);
BN_copy(a1,n1);
BN_copy(n1,tmp);
*jacobi *= s; /* step 7 */
goto startjacobistep1;
endBN_jacobi:
BN_clear_free(zero);
BN_clear_free(tmp);BN_clear_free(a1);
BN_clear_free(n1);BN_clear_free(three);
return returnvalue;
}
_________________________________________________________________
Join the world�s largest e-mail service with MSN Hotmail.
http://www.hotmail.com
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
