Say we have Alice and Bob.
Alice sends Bob a message she encrypted with Bob's public key. Bob is the only person who can decrypt it, using his private key. But how can he be certain the message came from Alice?
Suppose he replies, encrypting his message using Alice's public key. Only Alice can decrypt the message. But how can she be certain it was sent by Bob?
Would Alice have to add some kind of public hash to her message so bob can say "This definitely came from Alice?"
Bob has Alice's public key also, and Alice signed the message with her private key. Bob uses Alice's public key to verify the signature.
Go in reverse for Alice to ensure the message was from Bob.
All you have to do now is make sure that Bob has Alice's real public key and not one injected by a man in the middle.
The scenario you describe does indeed not provide authenticity. So both Alice and Bob cannot be certain that they are talking to each other. The scenario does only provide confidentiality and as such also not secrecy.
Bob would have to manually confirm with Alice that the public key he thinks is Alice's public key is indeed hers (by calling her and reading it out load and confirming by her voice that it is Alice).
This problem is normally solved with a trusted third party (a Certificate Authority for example, like VeriSign) that issues certificates stating the e.g. Alice is indeed the owner of this particular public key. This is the way it is solved in modern browsers and this is the way all SSL sessions (with your bank of choice) work. A certificate authority signs the certificate from your bank (stating that your bank is indeed the owner of the public key the certificate contains) and your browser has an already built-in certificate from the certificate authority (building a chain of certificates that can be verified).
The scenario you describe is vulnerable to a so called MITM (Man-in-the-middle) attack and not solvable purely with public-key-encryption.
What you are talking about very very very loosely looks like another implementation of an Asymmetric Encryption Algorithm found in the .Net framework.
.Net employs two branches for Asymmetric Encryption !!!
Both are Abstract
Both are very similar to one another as to how they work and how a developer implements them but underneath I have read that two very different algorithms exist.
You are talking option 2.
.Net provides a class called DSACryptoServiceProvider which allows you tag your data with a value that is commonly referred to as signature.
According to a MS official course textbook heres roughly how it works.
Data >>> Hash Alg >>> Hash Value >>>>>>>>> Asymm' Alg >>>> Signature Sender's PVT.KEY >>>
Below shows how Bob can check to see if Alice is indeed the sender.
Data >>> Hash Alg >>> Hash Value || Decrypted Signature <<< Asymm' Alg <<< Signature <<< Sender's PUB.KEY ? == ?
As you can see Bob has to compare the generated Hash and Decrypted Signature in order to verify that Alice is the sender. The DSACrypto' class has 4 methods that can be used here but only two are effective contextually speaking. At this point in time, this is all Bob can do, if his public key is not alice's public key, then essentially the software application should stop Bob dead in his tracks from proceeding any further as bob is trying to use a bogus public key when trying to communicate with Alice. This is the imposed relationship and stressed importance of the public key. The signature allows you verify the public keys owner.
Here why? ::
If Bob has Alice's public key then he can use the same algorithm again to decrypt the encrypted data using the .VerifyHash or VerifyData methods. Should be straight forward what they do given this context. This is all done ofc using the Alice's Public Key. Only Alice can use the SignHash and SignData methods as they require Alice's Private Key.
As you can see above, a certain level of functionality is encapsulated already inside the DSA and RSA CryptoServiceProvider classes. It boils down to how well you implement them to verify Alice's as the sender everytime as the DSA algorithm allows you to certify a sender by matching the generated output. A certain signature and hash should match, if they do then in essence DSA has granted you a certain level of confidentiality between Bob and Alice.
