Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I understand that signing is often a case of hashing data and then encrypting the hash with the private key. What properties keep Diffie-Hellman from being useful for this?

share|improve this question
add comment

3 Answers 3

up vote 6 down vote accepted

Actually the presentation of digital signatures as "encryption with the private key" is a misleading historical way of explaining RSA signatures; but it really works only for RSA. For such a scheme to work, you need the asymmetric encryption algorithm to be a trapdoor permutation, so that the space of encrypted messages is the same than the space of decrypted messages.

Most asymmetric encryption algorithms are not trapdoor permutations. This does not mean, however, that it is not possible to reuse parts of an asymmetric encryption algorithm to design a digital signature scheme.

Consider Diffie-Hellman. It is not an asymmetric encryption scheme; only a key exchange algorithm (a key exchange algorithm can be viewed as an asymmetric encryption algorithm in which you do not get to choose what is the encrypted message you send). From DH, we can build an asymmetric encryption scheme, and this is what ElGamal is about. An ElGamal public key is much similar to a DH public key: given fixed public parameters which describe a group $G$ of size $q$ and a generator $g$ of that group, the ElGamal private key is an integer $x$ (smaller than $q$) and the public key is $g^x$. To encrypt a message $m$ with the public key, the sender:

  • chooses a random $y$ modulo $q$;
  • computes $g^y$;
  • computes $s = (g^x)^y$;
  • sends $g^y$ and $m*s$ to the private key owner (this assumes that $m$ can be mapped to a group element, and back).

We recognize Diffie-Hellman in the first three steps: $s$ is the "shared secret" resulting from using DH with the public $g^x$. The fourth steps simply "encrypts" m by multiplying it with the shared secret.

Here, the private key is an integer modulo $q$ and the public key is an element of group $G$, which could be, e.g., an elliptic curve. You cannot swap them and try to encrypt with the private key: encryption needs a group element, not an integer modulo $q$.

Nevertheless, an ElGamal signature scheme has been designed, but it really does not look like Diffie-Hellman. It rather looks like a computational zero-knowledge proof of knowledge of the private key. With $G$ being non-zero integers modulo a prime $p$, signature works like this:

  • hash message $m$ into value $h$ which you map to an integer;
  • choose a random value $k$ relatively prime to $p-1$;
  • compute $r = g^k \mod p$;
  • compute $s = (h-xr)/k \mod (p-1)$. The signature is $(r, s)$.

To verify:

  • hash message $m$ into value $h$ which you map to an integer;
  • verify that $g^h = y^r r^s \mod p$.

So there are modular exponentiations in there, but nothing which is really "just Diffie-Hellman". ElGamal signatures are called such because Taher ElGamal described that algorithm, not because of any specific link with the ElGamal encryption scheme (which is also called ElGamal because it was also published by ElGamal).

Remark: with RSA, when you verify a signature, to process (exponentiate) the signature value with the public key, and this yields $H(m)$ (the hash of the message which is signed), which you them compare with the expected hash value. This does not work so with other signature algorithms, in which the hashed message is an input to the verification algorithm; you cannot recover the hashed message from the signature and the public key alone. RSA signatures are said to be signatures with recovery because you obtain the hashed message out of the signature; ElGamal signatures (and its offsprings DSA and ECDSA) are just "regular" digital signature schemes. Having the "recovery" feature is a byproduct of RSA being a trapdoor permutation.

share|improve this answer
    
Excellent research. Great insight. –  Sunny R Gupta Feb 27 at 10:13
add comment

Each algorithm or technique has its purpose. DH provides a way to generate two numbers, one that can be called the private key another the pub key. The DH algorithm does not cover encryption i.e. how to use the key.

As Thomas and poncho point out in elegant detail, one can take inspiration from DH and come up with an encryption scheme. But then once can't still call it DH. The important thing to keep in mind is that encryption and key exchange are two different aspects/needs.

A good example is to think of a combination lock, just knowing the key (a 3 digit number) is not sufficient to open the lock. One needs to know the encryption scheme: turn left 2 times and get to first digit, then right once and then left again 3 times. They encryption scheme and the key are independent items.

share|improve this answer
add comment

Well, signing "often" operates like that because that's what RSA does, and the vast majority of signatures are, in fact, RSA signatures.

In any case, it is not sufficient to "encrypt" the hash; what we really want to do is do a non-malleable encryption (where the attacker cannot modify the encrypted value to come up with the value he wants).

Now, Diffie-Hellman is a key exchange protocol, and so doesn't actually encrypt anything at all. There is a standard way of turning a two-pass key exchange protocol into a public key encryption primitive; if we do that to DH, we come up with the public key primitive known as El Gammal.

However, how El Gammal works is that it what is actually passed is a random number that the encryptor doesn't choose; the idea is that this random number is used as a key to protect the message being sent. This works fairly well as an encryption primitive, however because this random number is used as a symmetric key, it doesn't provide any non-malleability properties (because the attacker can see that symmetric key; it would be used during the signature verification).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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