some people ask me, it is posibble to break EL Gamal Cryptosytem...i said, that everything is posibble in the Computer World...But to break El Gamal it have a long way and a long time... El Gamal Security have a discrete problem. but i have some tips how to analyze the El gamal Strength... this way not to break and use to crime..but to give us some known, to make our El Gamal Criptosystem better strength....
ElGamal is very secure. The only ways to break it are by finding collisions in the hash functions it uses, or (in theory) by computing the secret key when two ciphertext messages are sent with the same function of the secret exponent. See Wikipedia for more details
You can do what I do when using safe (p=2p'+1) prime moduli, which is to
convert the plaintext to all QR's so semantic security is preserved -
although this is in effect working in the subgroup of QR's of order p',
which is presumed DDH-hard.
Which is just a feeble excuse :) to present this method of ensuring all the
bits are QR's, and the overall scheme is IND-CPA. I don't know who else
invented the method first, but I haven't seen it elsewhere:
[-
Chose p' so p' = 1 mod 4. Thus p = 3 mod 8, and (2/p) = -1 (ie 2 is a QNR
mod p).
Before encryption prepend the bits 001 to the plaintext, test for QR: if it
is QR then pass on to the encrypter, if it is NQR then shift left (multiply
by two) before passing it on.
2 is NQR, and any NQR x any NQR = a QR - so all the blocks sent to the
encrypter are QRs.
After decryption, shift right if the second bit of the block is set. Discard
the first 3 bits.
Posts
