Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am currently using the ElGamalEngine of bouncy castle to implement exponential ElGamal for the purpose of making ElGamal additively homomorphic. To do this i raise the message to be encrypted to the generator g and modulo it with the group parameter p, like this:

private BigInteger g;
private BigInteger p;

public BigInteger raiseGenerator(long message)
{
    return g.modPow(BigInteger.valueOf(message), p);
}

In non-exponential ElGamal i would encrypt message, but to make it exponential i encrypt g^message%p. I use the following values of g and p:

private static BigInteger g512 = new BigInteger("153d5d6172adb43045b68ae8e1de1070b6137005686d29d3d73a7749199681ee5b212c9b96bfdcfa5b20cd5e3fd2044895d609cf9b410b7a0f12ca1cb9a428cc", 16);
private static BigInteger p512 = new BigInteger("9494fec095f3b85ee286542b3836fc81a5dd0a0349b4c239dd38744d488cf8e31db8bcb7d33b41abb9e5a33cca9144b1cef332c94bf0573bf047a3aca98cdf3b", 16);

With some values of message I get org.bouncycastle.crypto.DataLengthException: input too large for ElGamal cipher.

The reason this exception is raised is because of the following condition in the processBlock function of ElGamalEngine in bouncy castle.

if (input.bitLength() >= p.bitLength())
{
    throw new DataLengthException("input too large for ElGamal cipher.\n");
}

This is the same p as shown in the code above. The input can obviously have the same bit length as p because g^m%p can have almost the same numerical size as p and therefore also the same bit length.

Why is the input data restricted this way?

As an additional question: Is it possible to make ElGamal exponential using bouncy castle?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

In standard ElGamal you compute the second component of the ciphertext as $m\cdot y^k \bmod p$ where $k$ is your randomness and $y$ your public key. Consequently you multiply two group elements in $Z_p^*$ and therefore $m$ needs to be an element of $Z_p^*$, i.e. $1 \leq m\leq p-1$.

If you use exponential ElGamal, your message can come from $Z_{p-1}$, i.e. an integer within this additive group, which means $0\leq m\leq p-2$, and the second component of the ciphertext then is $g^my^k \bmod p$.

Btw. surely you can use this implementation for exponential ElGamal. Just compute your message as $m':=g^m \bmod p$ and encrypt $m'$.

Update After your comment and re-reading the question. Bouncycastle obviously has a bug in the check as they are checking the bitlength of the values instead of comparing the integer values.

share|improve this answer
    
If m is equal to p-1, then the exception is raised, so i do not understand why you explain the implmentation with the reason that m can take the value of p-1. The first function raiseGenerator returns m', and this is what i encrypt. I agree with your understanding of the legal values of m, but i still get the exception when i implement it according to your description. –  user3621524 May 9 at 19:47

Originally we had restrictions like this in place as the alternative was emails about bugs in ciphers like RSA resulting from people not understanding the implications of modular arithmetic (if you are going to push right to the boundary you really have to understand what's going on). Having said that, I actually think we'd outgrown this by the time ElGamal appeared (around BC 1.12).

Oh dear, looks like there's another test further down. Perhaps partially outgrown would be a better way of putting this.

Okay, this is now fixed and checked in it should appear on github shortly.

share|improve this answer
    
Thank you for the update! –  user3621524 May 10 at 10:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.