A microprocessor and method are provided for securely decrypting and executing encrypted instructions within a microprocessor. A plurality of master keys are stored in a secure memory. Encrypted instructions are fetched from an instruction cache. A set of one or more master keys are selected from the secure memory based upon an encrypted instruction fetch address. The selected set of master keys or a decryption key derived therefrom is used to decrypt the encrypted instructions fetched from the instruction cache. The decrypted instructions are then securely executed within the microprocessor. In one implementation, the master keys are intervolved with each other to produce a new decryption key with every fetch quantum. Moreover, a new set of master keys is selected with every new block of instructions.