How many operations per key for partial character matching?

Given a substitution cipher having a key with n alphanumeric characters, if an attacker knows p characters in the key, how many operations per key are required by his computer to compare a permutation with the known characters (and return it if it matches)?

Example:

• key is 5 characters that could be A-Z/0-9, so n = 5
• attacker has [B * * 3 *], so p = 2
• What cipher, Vigenere? Which characters do you need to compare, and which ones do you know? – Maarten Bodewes Jan 18 '17 at 22:56
• @MaartenBodewes Just simple monalphabetic (so, not Vigenere, which I understand to be polyalphabetic) substitution in this case. In the example above, the attacker knows (or assumes) 2 of 5 characters in the key, so he's just looking to index and find all permutations where B is the first character and 3 is the fourth character. I'm just curious how to figure out how many operations go into comparing each key with such criteria. – thebaker Jan 18 '17 at 23:06
• It may be that other readers now have enough information to answer (so I certainly won't close or vote down), but I'm still too confused. – Maarten Bodewes Jan 19 '17 at 14:44
• @MaartenBodewes sorry I'm not being more clear, I'm a novice at this subject. I've been thinking about how to explain this better. I've read about how password crackers generally rely on comparing candidate hashes with real hashes and the time to crack a password is thus measured in hashes per second. But I'm wondering how you describe this in terms of keys per second when you don't have the entire key hidden in a hash, but rather just parts of the key. So I guess I'm just looking for a more generalized method of determining operations per key needed for cryptanalysis. – thebaker Jan 20 '17 at 3:44
• The characters in the key are not dependent on each other. So the comparison just takes a single operation (i.e. perform a decrypt with the known characters - full stop). Of course you would still not have any additional information about the rest of the key or plaintext, other than that the plaintext is easier to guess (like a crossword puzzle, with or without characters already filled in). That's as far as I can answer with the information given. No idea though if that really answers your question. – Maarten Bodewes Jan 20 '17 at 9:23