Why not generate a random number, checksum it, and sign it using a public key? Or is that overkill?
Eric’s reply:

That’s overkill. For an affordable microprocessor for the price point of an electronic lock, you can’t do a modular exponentiation in a reasonable amount of time. A two-second delay is likely too long for mass market, even if certain markets would bear it. Sandy also suggest public key.

A shared secret key for a symmetric cipher is sufficient, since the binding between a single garage and a single opener is usually not broken. If your opener had to work with multiple doors, and if the usual case pertained where two people share the permission to open some doors but not others, then public key would be needed.

So you can do challenge/response, but there’s no need to use public key. DES would be sufficient.