# Problems with implementation of ElGamal using OpenSSL [closed]

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.

-
Reading code is painful. I recommend that you remove the code and focus on figuring out how to ask a concise question that can be expressed without requiring us to read code. Conceptual questions are much better suited to this site's format, and more likely to be relevant to other readers. For example, you said "several parts of the book do not agree with things i've found online"; perhaps you might try identifying one of those where you've seen conflicting advice, and asking what is the right procedure? – D.W. Oct 22 '12 at 5:38
If you notice, after each line of code i put in the exact logic that the code is trying to accomplish. As to the second part: I notice that the description on Wikipedia for example does not use modulus. I suspect that this doesn't matter and it's just intended to cut down on really large values, but wanted to check. Alternately if you're not much for code, i'm really just wondering if the implementation suggested by my book is correct, since i've reviewed my code a dozen times and i'm pretty certain my implementation is. – Chris C Oct 22 '12 at 14:30
Sorry, this site is really not a code review site. (We have a sister site with same initials for that, actually.) – Paŭlo Ebermann Oct 22 '12 at 17:52
I suggest that you post a new question where you ask a single specific question (not: are there any errors in my code, but something more like "should I reduce this value mod p or mod q?"); in that question, use math, not code; and then close this question. – D.W. Oct 22 '12 at 17:58
I did not read the code, but you might want to change BN_rshift1(q, p); into BN_rshift1(q, pMinusOne);. – bob Oct 22 '12 at 18:47
show 1 more comment

## closed as off topic by Paŭlo Ebermann♦Oct 22 '12 at 18:56

Questions on Cryptography Stack Exchange are expected to relate to cryptography within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.