Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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. – user11693 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? – user11693 Jan 29 '14 at 21:20

Your Answer


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