How do I compare key from one hash with values from other?

mug has asked for the wisdom of the Perl Monks concerning the following question:

I have two hashes. The keys of %hash1 are values in %hash2. %hash2 can have multiple values for the same key. I want to find the missing set of values (that is, keys of %hash1) for each key in %hash2.

Example:

my %hash1 = (
    A => 5,
    B => 7,
    C => 2,
    D => 8,
);
my %hash2 = (
    1234 => "A,C",
    4567 => "A,B,D",
    5678 => "C",
);
[download]

Originally posted as a Categorized Question.

Back to Seekers of Perl Wisdom