This is effectively how a rolling code works. You have a space of say, 2^16 keys that repeats. The car and keyfob share the same index to the keyspace, and increment one for every transaction.
If someone tried to "replay" an older key, the car would reject it. However, what if the user accidentally presses the button while not in range of the car?
To account for this, the system will "partially accept" keys "ahead of schedule" for about half the keyspace. The car advances its pointer (let's say N+5), and waits for N+6 to unlock.
Since most older keyfobs are simply "one way transmitters", PKI is out of the question. Newer keyfobs are able to receive as well, and could preform a handshake. However, car manufacturers are notoriously bad at security.