Why doesn't my implementation of El Gamal work for long text strings?
- by angstrom91
I'm playing with the El Gamal cryptosystem, and my goal is to be able to encipher and decipher long sequences of text. I have come up with a method that works for short sequences, but does not work for long sequences, and I cannot figure out why.
El Gamal requires the plaintext to be an integer. I have turned my string into a byte[] using the .getBytes() method for Strings, and then created a BigInteger out of the byte[]. After encryption/decryption, I turn the BigInteger into a byte[] using the .toByteArray() method for BigIntegers, and then create a new String object from the byte[].
This works perfectly when i call ElGamalEncipher with strings up to 129 characters. With 130 or more characters, the output produced is garbled.
Can someone suggest how to solve this issue? Is this an issue with my method of turning the string into a BigInteger? If so, is there a better way to turn my string of text into a BigInteger and back?
Below is my encipher/decipher code with a program to demonstrate the problem.
import java.math.BigInteger;
public class Main {
static BigInteger P = new BigInteger("15893293927989454301918026303382412" +
"2586402937727056707057089173871237566896685250125642378268385842" +
"6917261652781627945428519810052550093673226849059197769795219973" +
"9423619267147615314847625134014485225178547696778149706043781174" +
"2873134844164791938367765407368476144402513720666965545242487520" +
"288928241768306844169");
static BigInteger G = new BigInteger("33234037774370419907086775226926852" +
"1714093595439329931523707339920987838600777935381196897157489391" +
"8360683761941170467795379762509619438720072694104701372808513985" +
"2267495266642743136795903226571831274837537691982486936010899433" +
"1742996138863988537349011363534657200181054004755211807985189183" +
"22832092343085067869");
static BigInteger R = new BigInteger("72294619754760174015019300613282868" +
"7219874058383991405961870844510501809885568825032608592198728334" +
"7842806755320938980653857292210955880919036195738252708294945320" +
"3969657021169134916999794791553544054426668823852291733234236693" +
"4178738081619274342922698767296233937873073756955509269717272907" +
"8566607940937442517");
static BigInteger A = new BigInteger("32189274574111378750865973746687106" +
"3695160924347574569923113893643975328118502246784387874381928804" +
"6865920942258286938666201264395694101012858796521485171319748255" +
"4630425677084511454641229993833255506759834486100188932905136959" +
"7287419551379203001848457730376230681693887924162381650252270090" +
"28296990388507680954");
public static void main(String[] args) {
FewChars();
System.out.println();
ManyChars();
}
public static void FewChars() {
//ElGamalEncipher(String plaintext, BigInteger p, BigInteger g, BigInteger r)
BigInteger[] cipherText = ElGamal.ElGamalEncipher("This is a string " +
"of 129 characters which works just fine . This is a string " +
"of 129 characters which works just fine . This is a s", P, G, R);
System.out.println("This is a string of 129 characters which works " +
"just fine . This is a string of 129 characters which works " +
"just fine . This is a s");
//ElGamalDecipher(BigInteger c, BigInteger d, BigInteger a, BigInteger p)
String output = ElGamal.ElGamalDecipher(cipherText[0], cipherText[1], A, P);
System.out.println("The decrypted text is: " + output);
}
public static void ManyChars() {
//ElGamalEncipher(String plaintext, BigInteger p, BigInteger g, BigInteger r)
BigInteger[] cipherText = ElGamal.ElGamalEncipher("This is a string " +
"of 130 characters which doesn’t work! This is a string of " +
"130 characters which doesn’t work! This is a string of ", P, G, R);
System.out.println("This is a string of 130 characters which doesn’t " +
"work! This is a string of 130 characters which doesn’t work!" +
" This is a string of ");
//ElGamalDecipher(BigInteger c, BigInteger d, BigInteger a, BigInteger p)
String output = ElGamal.ElGamalDecipher(cipherText[0], cipherText[1], A, P);
System.out.println("The decrypted text is: " + output);
}
}
import java.math.BigInteger;
import java.security.SecureRandom;
public class ElGamal {
public static BigInteger[] ElGamalEncipher(String plaintext, BigInteger p, BigInteger g, BigInteger r) {
// returns a BigInteger[] cipherText
// cipherText[0] is c
// cipherText[1] is d
SecureRandom sr = new SecureRandom();
BigInteger[] cipherText = new BigInteger[2];
BigInteger pText = new BigInteger(plaintext.getBytes());
// 1: select a random integer k such that 1 <= k <= p-2
BigInteger k = new BigInteger(p.bitLength() - 2, sr);
// 2: Compute c = g^k(mod p)
BigInteger c = g.modPow(k, p);
// 3: Compute d= P*r^k = P(g^a)^k(mod p)
BigInteger d = pText.multiply(r.modPow(k, p)).mod(p);
// C =(c,d) is the ciphertext
cipherText[0] = c;
cipherText[1] = d;
return cipherText;
}
public static String ElGamalDecipher(BigInteger c, BigInteger d, BigInteger a, BigInteger p) {
//returns the plaintext enciphered as (c,d)
// 1: use the private key a to compute the least non-negative residue
// of an inverse of (c^a)' (mod p)
BigInteger z = c.modPow(a, p).modInverse(p);
BigInteger P = z.multiply(d).mod(p);
byte[] plainTextArray = P.toByteArray();
return new String(plainTextArray);
}
}
