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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following problem: Alice wants to send Bob a message such that Bob knows it is from Alice but at the same time he cannot prove that Alice send him this message.

The solution I came up with, using RSA, is:

  1. Alice picks a random key K, and encrypts the message M using this key K. M'= aes(K, M)
  2. Alice hashes K and Bob's public key to get H. H = sha(K + Bob's Public Key)
  3. Alice signes H using her private key. S = rsa_sign(Alice's private key, H)
  4. Alice encrypts K and S using Bob's public key. P = rsa_encprypt(Bob's public key, K + S)
  5. Alice sends P, M' to Bob

Bob receives P, M':

  1. Uses his private key to get K, S.
  2. Uses Alice's public key to verify S
  3. Uses K to decrypt M'.

Do you see any holes in this?


share|improve this question
You may want to check out this question… – Maeher Jan 29 '14 at 0:09
up vote 1 down vote accepted

In step 2 for Alice, what is the purpose of including Bob's public key in the hash? you can include a timestamp to prevent replay attacks instead.

In step 2 for Bob, there is a typo - should use Alice's public key instead of her private key.

Actually your protocol is similar to PGP, and I dont think it provides deniability because if Bob can prove that the public key belongs to Alice then the owner of the private key is most likely Alice.

share|improve this answer
Bob's step 2. You are right! Fixed it. Regarding Step 2 for Alice. It is there so Bob cannot use K to encode another message and send it to Eve pretending it was from Alice to Eve. Regarding deniability, Bob can prove that Alice sent him a message, but he cannot prove it was M, since having access to K allows him to construct any message he wants. – SFO Jan 29 '14 at 2:27
oh I see.. So that was the reason the message M wasn't included in the hash. Then this leads to another issue, Bob cannot be sure that the received message was unmodified since encryption alone does not provide integrity. – jingyang Jan 29 '14 at 3:14
Hmm. Good point! I guess I will have to work that out as well. Thanks! Do you see any other holes? – SFO Jan 29 '14 at 21:20

Your Answer


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.