Problems with implementation of ElGamal using OpenSSL [closed]

Question

I recently did an implementation of a semantically secure modification of ElGamal using OpenSSL. I'm implementing part of a book that i have, and several parts of the book do not agree with things i've found online. I'm here hoping that someone can look at my book and code and see if i'm doing something dumb!

I can't post images yet, but here's a link: http://i9.photobucket.com/albums/a60/cacollo/elgamal.png

Relevant code:

// Generate "p", a safe prime.
BN_generate_prime(p, KEYSIZE, 1, 0, 0, 0, 0);

// Calculate "q" = p - 1 / 2, also a prime.
BN_rshift1(q, p); 

// Calculate "g":: This part i'm not certain about!
do {
    // 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) */
} while (isGenerator(p, q, g) && !BN_is_one(g));
// Tests at the end are:
// isGenerator: if g^2 mod p == 1 && g^q mod p == 1, return true
// BN_is_one just checks to make sure g is not 1.
// This is mostly for semantic security, if i understand

// Private Key = "s"
RAND_bytes(seed, KEYSIZE);
BN_rand_range(s, q);

// Public Key = "Y"
BN_mod_exp(Y, g, s, p, ctx); // Y = g^s mod p

// Encrypt //
// Random value "r"/
BN_rand_range(r, range);
// I had to limit "r" because values higher than 2000 take forever to calculate...
// Not sure what i can do about that!

 /* calculate c1 */
BN_mod_exp(c1, g, r, p, ctx); // = g^r mod p, r is from rand_range.

/* calculate c2 */
BIGNUM *Yr = BN_new(); // Temporary storage for y^r
BN_exp(Yr, Y, r, ctx); // = Y^r 
BN_mod_mul(c.c2, Yr, m, p, ctx); // = Y^r * m mod p


// Decrypt //
BN_mod_exp(u1, c1, s, p, ctx); //u1 = c1^s mod p
BN_mod_exp(u2, u1, negOne, p, ctx); // u2 = u1^(-1) mod p
BN_mod_mul(mPrime, u2, c2, p, ctx); // mPrime = u2^c2 mod p

I am open to any and all comments! :) Thanks in advance.

Answer 1

I find the description in the book a bit dubious. I can't tell what the broader context is, so it is hard to tell whether the scheme in the book will be secure -- but it appears that they are using El Gamal with no padding and no hashing, which I find a bit dubious. I'd want to see the rest of the scheme before forming a judgement on its suitability for use in practice, though.

In my experience, most cryptographic voting protocols are extremely delicate and require considerable cryptographic knowledge to implement safely. If you are planning on implementing the stuff from this book and use it to run a real election, and if you have to ask this sort of question, I'd wonder whether you are qualified to implement the protocol. As a matter of engineering ethics, if you're not qualified to implement it in a way that provides reasonable assurance of safety, you probably should recuse yourself -- just as a civil engineer who knows he/she is not qualified to build a bridge and provide reasonable assurance of its safety should recuse himself/herself rather than charging ahead and building a bridge that might end up falling down while someone is trying to use it.

Please don't take this personally; but some things need to be handled by a professional who is an expert on the subject, rather than someone who is just learning the subject for the first time out of books and Internet web sites. Only you can judge whether you have the necessary expertise.