Question

Digital Signature (5-5): In the course notes we looked at RSA for encryption and signatures
(using exactly the same mathematical formula), and ElGamal for encryption. There has been
several questions on using ElGamal for signature. The ElGamal encryption algorithm cannot
be used for signatures but there are signature schemes that is based on discrete logarithm.

(a) Search for simple explanation of the ElGamal signature scheme and DSA signature
scheme (Hint: Wikipedia). Can these algorithms be used to encrypt a message? What
is the main di erence in how you verify the validity of the message with these schemes
when compared to RSA?

(b) Choose one of these schemes and do a worked example of signing a message and then
verifying the signature. You should use the following values:
ElGamal                      DSA
Private key x= 16         Private key x = 6
Base g = 7      Base g = 107
Prime p = 71             Primes p = 131 and q = 13
Random k = 9             Random k = 8
Message H(m) = 13     Message H(m) = 13

Answer 1

(a) The ElGamal signature scheme is a digital signature scheme based on the algebraic properties of modular exponentiation, together with the discrete logarithm problem. The algorithm uses a key pair consisting of a public key and a private key. The private key is used to generate a digital signature for a message, and such a signature can be verified by using the signer's corresponding public key. The digital signature provides message authentication (the receiver can verify the origin of the message), integrity (the receiver can verify that the message has not been modified since it was signed) and non-repudiation (the sender cannot falsely claim that they have not signed the message).

The DSA algorithm works in the framework of public-key cryptosystems and is based on the algebraic properties of modular exponentiation, together with the discrete logarithm problem, which is considered to be computationally intractable. The algorithm uses a key pair consisting of a public key and a private key. The private key is used to generate a digital signature for a message, and such a signature can be verified by using the signer's corresponding public key. The digital signature provides message authentication (the receiver can verify the origin of the message), integrity (the receiver can verify that the message has not been modified since it was signed) and non-repudiation (the sender cannot falsely claim that they have not signed the message).

These algorithms are not used to encrypt message . DSA stands for "Digital Signature Algorithm" - and is specifically designed to produce digital signatures, not perform encryption. The ElGamal cryptographic algorithm is a public key system like the Diffie-Hellman system. It is mainly used to establish common keys and not to encrypt messages.

RSA and ElGamal both use asymmetric key techniques. The fundamental difference lies in the number of variables used. RSA uses two variables during encryption while ElGamal uses three variables. The RSA algorithm's strength is at the difficulty level in factoring the numbers into a prime factor. DSA(Digital Signature Algorithm) can only be used for signing/verification, whereas RSA can be used for encryption/decrypt as well.

(b) El Gamal:

y=g^xmod p=19

a=g^kmod p=47

b=H(m)*y^kmod p=44

decrypted msg=(b/a^x) mod p=13