I have a small program that uses BIGNUM functions BN_exp() and BN_mod_exp() on 64-byte big integers (that are generated via BN_generate_prime_ex()).
Every time I compile and run, the program pauses forever while computing the first call to BN_exp(). I know the issue is BN_exp() because I have print statements before and after the function call. I'm just confused as to why the program stalls while computing BN_exp(). Are the 64-byte big integers too large for the function? Is it just taking a really long time to compute? Any help is appreciated.
Goal: compute (bn_one^bn_two) * (bn_two^bn_one) mod bn_mod. My way is incorrect, so any suggestions of how to compute this would be great.
Here is my program:
#include <stdio.h>
/* OpenSSL headers */
#include <openssl/bn.h>
void main()
{
BIGNUM *bn_one, *bn_two, *bn_one2two, *bn_two2one, *bn_mod, *bn_result;
BN_CTX *ctx; /* used internally by the bignum lib */
ctx = BN_CTX_new();
bn_one = BN_new();
bn_two = BN_new();
bn_one2two = BN_new();
bn_two2one = BN_new();
bn_mod = BN_new();
bn_result = BN_new();
// Generate two 64 byte integers
BN_generate_prime_ex(bn_one,512,0,NULL,NULL,NULL);
BN_generate_prime_ex(bn_two,512,0,NULL,NULL,NULL);
BN_generate_prime_ex(bn_mod,512,0,NULL,NULL,NULL);
printf("BIGNUM One:\t");
BN_print_fp(stdout, bn_one);
printf("\n");
printf("BIGNUM Two:\t");
BN_print_fp(stdout, bn_two);
printf("\n");
// Compute bn_one to the power of bn_two and store in bn_one2two
if(BN_exp( bn_one2two , bn_one , bn_two, ctx ) == 0) {
printf("Error in BN_exp\n");
}
printf("BIGNUM One2Two:\t\n");
BN_print_fp(stdout, bn_one2two);
printf("\n");
// Compute bn_two to the power of bn_one and store in bn_two2one
if(BN_exp( bn_two2one , bn_two , bn_one, ctx ) == 0) {
printf("Error in BN_exp\n");
}
printf("BIGNUM Two2One:\t\n");
BN_print_fp(stdout, bn_two2one);
printf("\n");
// Compute bn_one2two * bn_two2one mod bn_mod and store the remainder in
//bn_result
if(BN_mod_mul( bn_result , bn_one2two , bn_two2one, bn_mod , ctx ) == 0) {
printf("Error in BN_mod_exp\n");
}
printf("BIGNUM Mod Result:\t\n");
BN_print_fp(stdout, bn_result);
printf("\n");
BN_CTX_free(ctx);
BN_clear_free( bn_one );
BN_clear_free( bn_two );
BN_clear_free( bn_one2two );
BN_clear_free( bn_two2one );
BN_clear_free( bn_mod );
BN_clear_free( bn_result );
}
My output before the program stalls (these 64-byte values change with each run):
BIGNUM One: CE06C8663AB65AA2BF7C6B30273C5E002552CFB8548A6B8EC7204A23F6A8892FEA9EF315777660C5B4FD97EABB7703FCFB5B1C2D495A1863B5F9D290F72CF8A5
BIGNUM Two: CB4A929D982670B77F2544E7D5A990DEE76958CBEC5BEB638B8DA9D44880C46817D1D7616C58AF79378215368C76962FA88D08A215331019599945CAF933E417
I figured out how to compute (bn_one^bn_two) * (bn_two^bn_one) mod bn_mod
correctly thanks to this source: https://github.com/maK-/Digital-Signature-ElGamal/blob/master/Crypto2.java .
Previously, I was computing as such:
BN_exp
for bn_one^bn_two
BN_exp
for bn_two^bn_one
BN_mod
on results of both with bn_mod.The numbers were just too big to work with in this manner.
The associativity property of the operation of taking the remainder will simplify the work: (a*b)mod q = (a mod q)*(b mod q)
.
The computation to use for BIGNUM would flow as follows:
BN_mod_exp
for bn_one^bn_two
with bn_mod
BN_mod_exp
for bn_two^bn_one
with bn_mod
BN_mul
on the results of both previousBN_mod
on the result of BN_mul
with bn_mod.