Khan's intelligence isn't magical. He is smart, not omnipotent. When he was brought aboard in "Space Seed", they let him have access to the entire ship's library. That gave him a lot of insight into Starfleet capabilities and operations. If he had bothered to do the same thing again after capturing Reliant
, he might have won.
As for changing the prefix code, it could be anything from simply telling the computer to change it (he had Captain Terrell under his thumb to do it if he needed a senior officer to do so) to some major hardware swapping. We don't know what it takes, just that it can be done in the field.