# Can Alice send Bob a secure message with only DSA and no key exchange?

Suppose Bob has a DSA key pair, and Alice has Bob's public key. Is there any secure way that Alice can send Bob a message only he can read if Bob can not send any reply?

I think the answer is no, since DSA is only for messaging signing, so can only be used for things like authentication and Diffie-Hellman key exchange.

• DSA can't be used for DH key exchange. If it could you could implement ElGamal upon it. DSA can only be used to authenticate DH key-exchanges. Am I reading your question right as: Can I somehow turn DSA into a public key encryption scheme? - What do you mean by "if Bob can not send any reply"? Commented Jul 19, 2015 at 18:12
• DSA is used only used for signing. So you are right. RSA can be used both for encrypting and signing. With DSA you have also non-repudiation (can not be used for key-exchange).
– 111
Commented Jul 19, 2015 at 18:13
• So if Alice were sending Bob a message in the mail, for example. A back and forth exchange is not possible. And oops with the DH thing! I thought the messages involved in DH needed to be signed? Commented Jul 19, 2015 at 18:15
• DH by itself doesn't define the usage of signatures. However safe applications of DH require signatures. DSA also hashes the message always before signing it so there's no way in turning it an encryption scheme. Commented Jul 19, 2015 at 18:31

Let me first answer your actual question (and then I'll proceed to answer something slightly different that I think will be informative and helpful). Your question asks whether it's possible to use only a DSA key. Technically speaking, this is of course possible. The reason is that a DSA key has exactly the same format as an ElGamal key. No one forces you to use the key with the proper algorithm. (I know that this is a bit stupid, but it will be more meaningful after what follows below.) Just note that if you use the key both for DSA signing and for ElGamal encryption then you may have security problems, and you need to formally prove that this combination is OK. (By the way, this is all OK since Alice already has Bob's public key, so there is no problem of authenticating the key, etc.)

Despite the above answer, I have a feeling that what you are really asking is whether or not it's possible to use signatures alone in order to securely encrypt (in the public key setting, without a shared symmetric key). I'll translate it to "is it possible to use signatures alone to get key exchange" since key exchange is more relaxed than public-key encryption.

This is an excellent question. The first problem with the question is "how to formalize using one primitive to get another". The naive way of doing this is saying that if A exists then B exists. So, your question would be: is the following statement true "if signatures exist then key exchange exists". However, we believe that both signatures exist and key exchange exists, which if true, makes the statement logically true irrespective of any connection between signatures and key exchange. This led Impagliazzo and Rudich in their groundbreaking work Limits on the Provable Consequences of One 􏰀way Permutations to define that one primitive implies another if one can be constructed from the other using a black-box reduction (and in a world where no other crypto exists, which can be achieved by giving the adversary an NP-oracle to solve all NP problems, for example). Note that most (but not all) reductions in crypto are black box. It is beyond the scope here to define black box, but for here it suffices to say that the primitive is used based on its input/output functionality only, and the reduction uses the adversary in a black-box way as well.

Now, back to your question. The answer is no. Impagliazzo and Rudich proved that one-way functions do not imply key exchange in this setting. Stated differently, it is impossible to construct a black box reduction from one-way functions to key exchange. Noting now that signatures can be constructed from one-way functions only (One-Way Functions are Necessary and Sufficient for Secure Signatures, Rompel), this implies that there exists no black-box reduction from signatures to key exchange. I remark that this result by Impagliazzo and Rudich holds in the presence of an eavesdropping adversary only, so it has nothing to do with man-in-the-middle attacks or anything like that.

Let's conclude by going back to DSA. Note that it is possible to use a DSA key to get key exchange; as I said, just use it for El Gamal. However, this is exactly the difference. My use of DSA is not black box. Rather, I am utilizing the number-theoretic properties and the structure of the DSA key. Thus, this does not contradict the result of Impagliazzo and Rudich.

• Excellent answer as well! You may want to add some reference (e.g. Rompel) to make it clear that signatures can be constructed from one-way functions only (in your second last paragraph). Commented Jul 20, 2015 at 7:19
• @MaartenBodewes I'm not sure what you mean. What do you mean by generating a hash on one side and using the result on both sides? Commented Jul 20, 2015 at 12:45
• I think that as long as the signature generation and verification is performed in the right order that black box key derivation is not possible. I've reused RSA signature generation/verification before but that meant using the public key for generation and the private key for verification - abusing some gaps in the API. Still, I think there is some grey area between using a black box and just the key information that is not completely covered by this answer (although I don't think tricks like above could work for DSA). Commented Jul 20, 2015 at 13:03
• (and yes, this was for a proof of concept, not a actual product, I'm not that mad) Commented Jul 20, 2015 at 13:05
• Wow! I must admit that a lot of that was over my head. The context that I ask my question is that of github users' public keys (most of which are either RSA or DSA) and whether it's possible to leave them a secure message without them actively negotiating a key to use. Commented Jul 20, 2015 at 23:22