OpenSSL BIGNUM BN_mod_exp problems
-
30-06-2021 - |
Question
I am having some issues coming up with "the correct answer" using OpenSSL's BIGNUM library. I am using OpenSSL 1.0.1c (May 2012, latest package available in the standard Mint repos).
I am using BIGNUMs for a cryptography project that uses finite fields (aka Galois fields). Basically i have a large prime (q) and a safe prime (p, where p = 2q + 1). My field is Fp of order q.
I need to generate a "g". The easiest way i've found to do this is to pick a random "h" (1 < h < p-1), then do g = h^((p-1)/q) mod p. With the "g" i get out of that, i should be able to prove that it is in the FF by doing g^q mod p = 1.
When I do this for any reasonable small numbers on paper it holds true. However, when I do it using OpenSSL and big, prime numbers, it doesn't work! When I test whether my result of g^q mod p == 1, it constantly fails using BN_is_one(). If I print out the value, it's always a large unrelated prime.
What is going on? I'm not sure what's going on here, or if I'm misunderstanding something.
Snippets of my code below:
BN_generate_prime(q, KEYSIZE - 1, 0, 0, 0, 0, 0); //generate "q"
// Calculate "p" = 2q + 1
BN_lshift1(p, q);
BN_add(p, p, one); //one = BN_one()
// 1: gExp = (p-1)/q
// 2: h => 1 < h < (p-1)
// 3: g = h^gExp mod p
BN_div(gExp, NULL, pMinusOne, q, ctx); // (1)
BN_pseudo_rand_range(h, pMinusOne); // (2)
BN_mod_exp(g, h, gExp, p, ctx); // (3)
BN_mod_exp(temp, g, q, p, ctx); // g^q mod p = 1, or it should
La solution
As you are computing it in your snippet, p
is not necessarily prime, it's just a number that is of the form 2*q+1
with q
prime. For many small values of q
, this p
happens to be prime, but that is mostly coincidence and if you checked with BN_is_prime
you will likely find the p
s you are generating do not pass the tests.
Instead, generate p
directly by setting the safe
parameter of BN_generate_prime
and then compute q
by a right shift, as with safe
the prime will be of the form you need, and chopping off the lowest bit gives you a prime q
.