The problem turned out to be related to the Permissions of the "C:\Users\All Users\Microsoft\Crypto\RSA\MachineKeys" folder.
Making sure the commands are executed using a user that belongs to the administrator group on the machine, and that the administrator group is the owner of that folder, enabled those commands to execute successfully.