[proofplan] Fix any ciphertext $c \in \mathcal{C}$ with $\mathbb{P}(C = c) > 0$ — such a $c$ exists because $C$ takes values in $\mathcal{C}$. Perfect secrecy forces $\mathbb{P}(M = m \mid C = c) = \mathbb{P}(M = m) > 0$ for every $m \in \mathcal{M}$, so for each $m$ there is at least one key $k$ with $e(m, k) = c$. Choosing such a $k_m$ for each $m$ defines a map $\mathcal{M} \to \mathcal{K}$ which is injective: if $k_m = k_{m'}$ then applying the decryption map $d$ to $c$ under that common key recovers both $m$ and $m'$, forcing $m = m'$. Injectivity from $\mathcal{M}$ to $\mathcal{K}$ between finite sets gives the cardinality inequality. [/proofplan]

[step:Fix a ciphertext that actually occurs] Since $C$ is a random variable valued in the finite set $\mathcal{C}$, the law of total probability gives \begin{align*} 1 = \sum_{c \in \mathcal{C}} \mathbb{P}(C = c). \end{align*} Hence the set $\mathcal{C}^+ := \{c \in \mathcal{C} : \mathbb{P}(C = c) > 0\}$ is nonempty. Fix any $c \in \mathcal{C}^+$. [/step]

[step:Show that every message has a key encrypting it to $c$]Fix $m \in \mathcal{M}$. By perfect secrecy applied to $m$ and our fixed $c \in \mathcal{C}^+$, \begin{align*} \mathbb{P}(M = m \mid C = c) = \mathbb{P}(M = m) > 0, \end{align*} where positivity comes from the hypothesis that every message has positive prior probability. On the other hand, by Bayes' theorem and the definition of conditional probability, \begin{align*} \mathbb{P}(M = m \mid C = c) = \frac{\mathbb{P}(M = m,\, C = c)}{\mathbb{P}(C = c)} = \frac{\mathbb{P}(M = m,\, e(M, K) = c)}{\mathbb{P}(C = c)}. \end{align*} Expanding the joint probability using independence of $M$ and $K$, \begin{align*} \mathbb{P}(M = m,\, e(M, K) = c) = \sum_{k \in \mathcal{K}:\, e(m, k) = c} \mathbb{P}(M = m)\, \mathbb{P}(K = k). \end{align*} Positivity of $\mathbb{P}(M = m \mid C = c)$ therefore forces the set \begin{align*} \mathcal{K}_m := \{k \in \mathcal{K} : e(m, k) = c\} \end{align*} to be nonempty (if it were empty, the numerator above would vanish, making the conditional probability zero, contradicting $\mathbb{P}(M = m) > 0$).[/step]

[guided]We want to conclude that for each message $m$ at least one key $k$ encrypts $m$ to our fixed $c$. How does perfect secrecy force this? Perfect secrecy says that learning the ciphertext gives no information about the message: $\mathbb{P}(M = m \mid C = c) = \mathbb{P}(M = m)$. Combined with the hypothesis $\mathbb{P}(M = m) > 0$ (every message occurs with positive prior probability), this yields \begin{align*} \mathbb{P}(M = m \mid C = c) > 0. \end{align*} In words: under our fixed $c$, every message remains possible. The cryptosystem cannot "rule out" any message based on the ciphertext. Now translate "possible" into "there exists a key". By the definition of conditional probability and the joint distribution, \begin{align*} \mathbb{P}(M = m,\, C = c) = \mathbb{P}(M = m \mid C = c) \cdot \mathbb{P}(C = c) > 0. \end{align*} Since $C = e(M, K)$, the event $\{M = m,\, C = c\}$ equals $\{M = m,\, e(m, K) = c\}$ (substituting $M = m$). Using independence of $M$ and $K$, this joint event has probability \begin{align*} \mathbb{P}(M = m) \cdot \mathbb{P}(e(m, K) = c) = \mathbb{P}(M = m) \cdot \sum_{k:\, e(m,k) = c} \mathbb{P}(K = k). \end{align*} Positivity of this product (given $\mathbb{P}(M = m) > 0$) forces $\sum_{k:\, e(m,k) = c} \mathbb{P}(K = k) > 0$, hence the set $\mathcal{K}_m = \{k : e(m, k) = c\}$ is nonempty. Why do we need $\mathbb{P}(M = m) > 0$? Without it, the perfect-secrecy equation would be trivially satisfied with zero on both sides, and we could not deduce that $c$ is achievable from $m$. The hypothesis rules out "dead" messages.[/guided]

[step:Construct an injection $\mathcal{M} \to \mathcal{K}$ using the axiom of choice on a finite set] Using that each $\mathcal{K}_m$ is nonempty, define a map \begin{align*} \kappa: \mathcal{M} &\to \mathcal{K} \\ m &\mapsto \kappa(m) \in \mathcal{K}_m, \end{align*} where $\kappa(m)$ is an arbitrary element of $\mathcal{K}_m$. The map is well-defined because each $\mathcal{K}_m$ is nonempty, and the selection requires only finitely many choices since $\mathcal{M}$ is finite (so no nontrivial use of the axiom of choice is needed). By construction, $e(m, \kappa(m)) = c$ for every $m \in \mathcal{M}$. [/step]

[step:Verify injectivity of $\kappa$ via the decryption map] Suppose $m, m' \in \mathcal{M}$ satisfy $\kappa(m) = \kappa(m') =: k$. Then by the defining property of $\kappa$, \begin{align*} e(m, k) = c = e(m', k). \end{align*} Apply the decryption map $d$ in the second argument $k$ to both sides. By the cryptosystem axiom $d(e(m, k), k) = m$, \begin{align*} m = d(e(m, k), k) = d(c, k) = d(e(m', k), k) = m'. \end{align*} Hence $\kappa(m) = \kappa(m')$ implies $m = m'$, so $\kappa$ is injective. [/step]

[step:Conclude the cardinality inequality] We have constructed an injective map $\kappa: \mathcal{M} \to \mathcal{K}$ between finite sets. By the pigeonhole principle for finite sets, the existence of an injection from a finite set $A$ to a finite set $B$ implies $|A| \leq |B|$. Therefore \begin{align*} |\mathcal{M}| \leq |\mathcal{K}|, \end{align*} which is the statement of the theorem. [/step]