How and why can a decryption program tell me that a key is incorrect? I have noticed that some programs used for file encryption will tell you if an entered key is wrong when you try to decrypt. It seems (to me at least) that this would mean that the key somehow is written into the encrypted file. And the algorithms that I know of will produce an output even if the key is wrong.


How does one built into an algorithm this type of validation of a key? Is it just a matter of encrypting the key with the original text?
Is this a security problem?
It's not a security problem but a necessary feature. It's not an exact science to distinguish a "good decryption" from a "bad decryption". What if the user had encrypted random data? you would not be able to figure out if the key is correct or not from that sole information, since in both cases the decrypted output would look completely random!

Similarly, what if the user typed his key wrong? You want to be able to inform him he made a typo ("invalid password") instead of blindly decrypting garbage and waiting for the user to realize he typed it wrong and try again.

What most programs do is store the hash of the key (or an HMAC of the encrypted file, using the encryption key) so that they can verify if the key is correct (or if the file is corrupt - you get free integrity/authentication with the HMAC method) without disclosing the key at all. An attacker would need to find an exact preimage to obtain the actual encryption key, which is designed to be infeasible.

In essence, you use a one-way function to store the key's image somewhere in the file, so that anyone without the key cannot invert the function and retrieve the key, but anyone who has the key can easily feed it into the one-way function and compare the result with the value that's in the file. If it matches, it's the correct key! (with very high probability)