# Client authentication on limited hardware

I'm developing a authentication and authorization protocol for a Bluetooth device. The device should communicate with an Android app and needs to be able to authenticate the app during the connection phase. Some kind of secret or asymmetric pair is therefore needed to be shared by the app and the Bluetooth device. As apps can be reverse-engineered we need to be able to update this secret.

RSA was the first solution that came to mind. The device can store the public key of some root certificate and then verify the signature of the app certificate like during TLS. The device keeps a list of valid certificate fingerprints.

However, the Bluetooth device is too weak to implement RSA. I need something (much) cheaper. Is there any such protocol?

• How weak is too weak? Elliptic curve cryptography uses much smaller numbers than RSA, for example, but it's still significantly slower than purely symmetric encryption. – otus Jul 2 '14 at 8:33
• RSA is very fast for the purpose of authenticating something (rather than: authenticate w.r.t. something). For 2048-bit public modulus, public exponent $e=3$, and a CPU with 32x32 bit multiplication, in the order of 17000 multiply-and-accumulate are enough, with textbook algorithms and straightforward loops. This can be about halved with Rabin, while still having standard-conformance, e.g to ISO/IEC 9796-2, and then there's DjB's work. – fgrieu Jul 9 '14 at 12:33