I just need it to support signing and signature verification. I need it to have public and private keys that fit each in 16 bytes. The signature itself must fit 16 bytes.
I don't really care about cryptographic strength, as this is part of something bigger.
Is there such a thing?
You want to do an elliptical encryption system, that'll give you the most protection for your bang. See this wikipedia article. The specific algorithm that appears to fit your needs is the Elliptical Curve DSA
Just to quote a few juicy spots from said article:
The hardest ECC scheme (publicly) broken to date had a 112-bit key for the prime field case and a 109-bit key for the binary field case.
16 bytes= 128 bits, so should should be fine.
Why would you need digital signatures at all when cryptographic strength is not required ? It is ok that anyone can break or forge your signatures, is that so ? Weak or wrongfully implemented cryptography is worse than none because it gives false sense of security.
+1 for ECC but beware of its tricky implementation details such as the requirement for random numbers.
No more than 128 bits for the public key, the private key and the signature: that's hard requirements; the harder being on the signature size.
If you use ECDSA, you could work over a 128-bit curve. A public key can fit in about 129 bits; you can omit one bit (this just means that whoever verifies signatures must "guess" the missing bit, i.e. try two possible public keys; if one matches the signature, that's ok). The private key would use 128 bits, still on par with your requirements. Security would be up to 264 curve operation, something which is technologically feasible but not easily (a distributed computation for breaking a 128-bit curve has begun; it involves quite a lot of Universities and it is expected to take about 10 years -- that's what I mean by "not easy"). But the signature size would be 256 bits (two 128-bit integers), twice your requirement. So ECDSA does not work for you.
If you look at research papers, you may find the BLS scheme. To match the requirements, you would have to use a 128-bit curve with a supersingular curve (mathematically, you need both the public key and the signatures to be in the curve on the base field, not the field extension, so this implies use of a distortion map). To get at least some security (something no more than barely crackable), the embedding degree should be at least 6, and you want to avoid fields of characteristic 2, so you'll need to implement computations in a field of characteristic 3. There is no published standard, only shards of high mathematical knowledge scattered over dozens of article of only relative readability. If you understood any of that paragraph, then you have already lost your sanity, probably where I mislaid mine.
Summary: there is no known digital signature algorithm which both fits your requirements and is reasonable to use. There may be one in the future, when current research on pairings stabilizes. But it will not be easy to implement.
I would suggest that if short term keys and only verification and signing are needed then you could look at the Diffie Hellman key exchange to do this and use small prime numbers. It would be insecure, but you know this already.
