Cannot RDP to Azure VM (error 0x904)

Today I had a annoying problem in a Azure Virtual machine that would give me an instant error when trying to login using RDP. The error was:
This computer can’t connect to the remote computer. Error code: 0x904, Extended error code 0x7.
and:
This computer can’t connect to the remote computer. Error code: 0x4, Extended error code 0x7.

Why is RDP giving this error?

After searching the internet I couldn’t find a satisfying answer and I started digging into the problem using the Azure Console. This didn’t give any conclusive answers so I went to the next troubleshooting tool

From the Azure Portal it is possible to Run PowerShell scripts.

After a while I found out that everything relying on certificates returned an error around certificates, either corrupt certificate store and for RDP, cannot create a new self signed certificate:

How to resolve?

The resolution is actually simple, we need to rename the MachineKeys store and reboot the server.

From the Azure Portal go to the VM and select Run Command and then RunPowerShellScript:

Rename-Item -path "C:\ProgramData\Microsoft\Crypto\RSA\MachineKeys" -NewName "MachineKeys_old"

Reboot your machine and you should be good to go again!