Every keyless/wireless car key already uses a challenge-response scheme, just like you described, to prevent replay attacks. However, that will not work against relay attacks. Cryptography does not prevent relaying.

Fun fact: Even most physical car keys produced >1990 have a small RFID based transponder in the key head (the plastic part that you hold). This transponder responds to a challenge transmitted by the ignition barrel. Without a correct response, the ECU will refuse to start the engine. This is mainly done to prevent 'Hollywood' style theft where you connect 2 wires from the ignition barrel together to start a car.