>What does information really measure? It measures the uncertainty we overcome
My thought here is that matters because human beings have to make decisions all the time, and reducing the uncertainty regarding the situation makes it more likely you will make the correct decision.
For example: if you measure a voltage using a volt-meter then, if the volt-meter is working properly, there will be a correlation between the readout on the meter and the actual voltage, and so the meter contains information about the voltage.
Note that information is symmetric: the voltage in this case also contains information about the meter.
So... if information resides in correlations, where does the information reside in this system? Because K is random, it has zero correlation to M (that's what "random" means). It also has zero correlation to C, though this is not so obvious. (Proof is left as an exercise.) In fact it turns out that C and K are both completely random, and so it's not even possible to tell by looking at C and K which is which. They are interchangeable.
So we have the following situation:
1. Information about M obviously has to reside somewhere in the composite system comprising C and K because we can completely recover M simply by computing C XOR K.
2. The information is not in C and it is not in K.
So where is it?
[Spoiler alert. It's worth thinking about this for a while to see if you can figure it out on your own. Hint: think about the case where C, M and K are all just a single bit, because the multi-bit case is just a straightforward extension of the single-bit case.]
Answer: the information about M is contained in the correlations (or anti-correlations) between C and K. In the one-bit case, if C and K correspond (i.e. are both 0 or are both 1) then M is 1. If they don't correspond, then M is 0.
The more complicated cryptographic cases are very similar, but of course, more complicated. What cryptography is really about in some sense is trying to get the same results but with a smaller key, i.e. it's about trying to take a fixed-size K that is (much!) smaller than M and "distribute" the entropy in such a way that the information is hidden in correspondences between bits in such a way that an attacker can't figure out where those correspondences are.
> In the one-bit case, if C and K correspond (i.e. are both 0 or are both 1) then M is 1.
That should have read "... then M is 0." (Obviously.)
> If the number of messages in the set is finite then this number [...] can be regarded as a measure of the information produced when one message is chosen from the set, all choices being equally likely.
From the abstract of his famous paper http://math.harvard.edu/~ctm/home/text/others/shannon/entrop...