Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

closed as off topic by Mark Trapp Nov 12 '11 at 4:06

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

For example "RSA" would be an answer if RSA keys could be stored in a 16 bytes field. (They cannot.) – badp Feb 20 '11 at 2:51

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.

share|improve this answer
The cryptology class I took in college finally is coming to something useful:-) – PearsonArtPhoto Feb 20 '11 at 4:03
+1. Keep in mind, however, that the 112-bit and 109-bit breaks were done quite some time ago (close to 10 years, if memory serves). It wouldn't require nearly as much machine time to do the same today. – Jerry Coffin Feb 20 '11 at 4:32
The reference says July 2009, so not that long ago. Still, with that key size, you know what you're getting yourself into, so... – PearsonArtPhoto Feb 20 '11 at 5:03
Sorry, my memory was wrong -- I was thinking of the 108-bit key, which was broken in 2000. It's not surprising that it's the one I'd remember, I guess -- I did the original Windows port of that code to Windows. – Jerry Coffin Feb 20 '11 at 5:57
Unfortunately the signature size is 3x the security level with EC-Schnorr and 4x the security level with ECDSA. Even with the rather dubious security level of 80 bits, that means 20 byte public/private keys and 40 byte signatures. There are some schemes with smaller signatures, e.g. BLS at 2x security level and some really exotic ones with less, but finding good implementations of those will be tricky. – CodesInChaos Oct 21 '13 at 12:03

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.