TheAlgorithms/Java · error · IllegalArgumentException

Message must be smaller than the prime modulus p.

Error message

Message must be smaller than the prime modulus p.

What it means

Thrown by ElGamalCipher.encrypt when message.compareTo(p) >= 0, i.e. the message is not smaller than the prime modulus. ElGamal requires the message to lie in [0, p-1]; a message >= p cannot be uniquely recovered after modular reduction, so it is rejected.

Source

Thrown at src/main/java/com/thealgorithms/ciphers/ElGamalCipher.java:116

    /**
     * Encrypts a message using the public key.
     *
     * @param message The message converted to BigInteger.
     * @param p       The prime modulus.
     * @param g       The generator.
     * @param y       The public key component.
     * @return The CipherText pair (a, b).
     * @throws IllegalArgumentException if inputs are null, negative, or message >= p.
     */
    public static CipherText encrypt(BigInteger message, BigInteger p, BigInteger g, BigInteger y) {
        if (message == null || p == null || g == null || y == null) {
            throw new IllegalArgumentException("Inputs cannot be null.");
        }
        if (message.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("Message must be non-negative.");
        }
        if (message.compareTo(p) >= 0) {
            throw new IllegalArgumentException("Message must be smaller than the prime modulus p.");
        }

        BigInteger k;
        BigInteger pMinus1 = p.subtract(BigInteger.ONE);

        // Select ephemeral key k such that 1 < k < p-1 and gcd(k, p-1) = 1
        do {
            k = new BigInteger(p.bitLength(), RANDOM);
        } while (k.compareTo(BigInteger.ONE) <= 0 || k.compareTo(pMinus1) >= 0 || !k.gcd(pMinus1).equals(BigInteger.ONE));

        BigInteger a = g.modPow(k, p);
        BigInteger b = y.modPow(k, p).multiply(message).mod(p);

        return new CipherText(a, b);
    }

    /**
     * Decrypts a ciphertext using the private key.

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Keep messages strictly smaller than p; for larger data, use hybrid encryption (encrypt a symmetric key with ElGamal).
2. If appropriate, reduce the message mod p before encrypting (note this loses information if not reversible).
3. Use a sufficiently large prime for the expected message size.

Example fix

// before
CipherText ct = ElGamalCipher.encrypt(largeMessage, p, g, y);

// after
// Hybrid: ElGamal encrypts a random AES key, AES encrypts the payload
SecretKey aesKey = generateAesKey();
byte[] enc = aesEncrypt(largeMessage, aesKey);
BigInteger keyMsg = new BigInteger(1, aesKey.getEncoded());
if (keyMsg.compareTo(p) >= 0) throw new IllegalStateException("key too large for prime");
CipherText ct = ElGamalCipher.encrypt(keyMsg, p, g, y);

if (message.compareTo(p) >= 0) {
    throw new IllegalArgumentException("message must be < p; use hybrid encryption for large data");
}
CipherText ct = ElGamalCipher.encrypt(message, p, g, y);

static boolean inRange(BigInteger m, BigInteger p) {
    return m != null && p != null && m.signum() >= 0 && m.compareTo(p) < 0;
}

try {
    CipherText ct = ElGamalCipher.encrypt(message, p, g, y);
} catch (IllegalArgumentException e) {
    // message >= p; switch to hybrid encryption
}

When it happens

Trigger: Passing a message whose BigInteger value is greater than or equal to the prime p. Happens when the encoded message is larger than the prime, or when p is small relative to the payload.

Common situations: Encrypting large payloads directly instead of using hybrid encryption (encrypt a symmetric key); a small test prime paired with a big message; message not reduced mod p.

Related errors

• Message must be non-negative.
• Base, secret, and prime must be non-null and positive values
• Other public value must be non-null and positive.
• Bit length must be at least {} for security.
• Inputs cannot be null.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/58e615cbeb23536b. Report an issue: GitHub.