You don't need PKI for this - the car and the key have pre-shared keys.
All you need is to include a counter in the signal that is incremented for each button press. The car remembers the last counter value it receives and ignores any before that. Obviously the counter needs to be encrypted in some way but it's not exactly difficult.
I'm kind of amazed this still happens in 2016. Or maybe it doesn't. The cars could be old.