In his original work (1) on the ElGamal encryption and signature scheme Taher ElGamal states in chapter V. section B.:

For the signature scheme using the above arguments for the sizes of the numbers in our system and the RSA system, the signature is double the size of the document. Then the size of the signature is the same size as that needed for the RSA scheme, and half the size of the signature for the new signature scheme that depends on quadratic forms [...]

However, I was under the impression that (schoolbook) RSA signatures have roughly the same length as the corresponding modulo n, while ElGamal signatures are roughly twice the size of their corresponding modulo p.

Could somebody please clarify?


Mistakes happen.

The author's scheme adds a signature about twice as large as $p$, when RSA signature (of the textbook variety of the reference) adds a signature about as large as $n$. It is clearly assumed that the public prime modulus $p$ is about the size of the RSA public composite moduli $n$.It follows that the size of the signature in the proposed scheme is twice that in RSA.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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