A microprocessor is provided with a method for decrypting encrypted instruction data into plain text instruction data and securely executing the same. The microprocessor includes a master key register file comprising a plurality of master keys. Selection logic circuitry in the microprocessor selects a combination of at least two of the plurality of master keys. Key expansion circuitry in the microprocessor performs mathematical operations on the selected master keys to generate a decryption key having a long effective key length. Instruction decryption circuitry performs an efficient mathematical operation on the encrypted instruction data and the decryption key to decrypt the encrypted instruction data into plain text instruction data.