That depends on you connection... Are you connecting through ethernet or WIFI?
My first sugestion would be to check firewall settings on both computers.. You can also confirm if the RDP server is running on 3389 or some other.
Try the following steps -
The main cause behind this problems is some problem in the registry entries at the following path:
Follow the procedure below to fix it.
Open Start >> Run and type regedit and press enter.
Navigate to the following path:
Now delete registry keys named Certificate, X500 Certificate and X509 Certificate ID values. (These keys will get auto generated after system restart with system default values, which is actually needed)
Exit Registry editor and restart your computer.
Try to establish a remote desktop connection by typing mstsc at Run Prompt.
(Note: Always back up the registry before making any changes that may damage your system configuration.)