If RSA (textbook RSA that is) generates a digital signature by using the sender's private key, couldn't any cryptosystem (the only two that come to mind are RSA and ElGamal) capable of asymmetric encryption do the same?

For example, I've read that ElGamal is encryption only. Why can't ElGamal encryption (not DSA) do the same that RSA does?


Because the function used for RSA encryption and decryption is commutative. This means that given secret key $sk$ and public key $pk$ for all messages $m$ you have that $$D(E(m,pk),sk)=E(D(m,sk),pk)=m.$$ This means that first encrypting a message with the public key and then decrypting the so obtained ciphertext with the corresponding secret key yields the same as first decrypting a message with the secret key and then encrypting the result with the corresponding public key.

Since the RSA function enjoys this property, one can obtain a public key encryption scheme and a signature scheme using the same function (I ignore padding and stuff like hashing and speak only of textbook RSA). Due to this property, people often wrongly say that in general signing a message is identical to decrypting (often also encrypting) with the secret key.

However, this property does not hold for ElGamal, where the public key encryption scheme and the signature scheme are very different.

| improve this answer | |
  • $\begingroup$ Elgamal cryptosystem also hold the property of commutative (paper: DAI Wei " Commutative-like Encryption: A New Characterization of ElGamal ") $\endgroup$ – Aria Jun 24 '15 at 8:05

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.