I want to send short messages to cell phones.Commonly a short message is no longer than 70 bytes. I need 20 bytes or more holding information and the rest bytes are for signature provided by asymmetric schemes from server. It is because short messages can be easily faked with faked radio towers.

My app will get public key through https channel from the server.After getting public key, the phone may always be offline.When the server wants to contact a phone, it sends a short message to it and sign by private key.So the phone can trust the message and do the orders on the message.The public key will be refreshed every month and has a expired time of several month.

I've read some papers introducing RSA,DSA and BLS.The shortest RSA has a 128 bytes sign, while a DSA sign with readable charset like BASE64 is 64 bytes.Is there any shorter signature scheme? I saw BLS but it's not a international standard now and no jvm implementation found.

We assume the raw text is visible since attackers can read client code and know what happens to it.So is it still secure using a short signature with 30 bytes(others being redundancy)?


  1. sign length is around 30 bytes

  2. expired time is several months

  3. asymmetric scheme so messages cannot be mock

  4. raw text is some how visible

  • 3
    Crypto wise BLS is a great choice since it offers both high security and small signatures. With DSA/ECDSA you'd get a 120 bit curve which has 60 bits of security. The current academic record is breaking a 113 bit curve, so it wouldn't be totally broken, but the security margin is still quite low. Commented Sep 18, 2014 at 8:21
  • @CodesInChaos I agree. For short, secure signatures you have to use some sort of EC algorithm. A 160-bit EC would give strong security in 20 bytes.
    – RoraΖ
    Commented Sep 18, 2014 at 11:29
  • 1
    @raz An ECDSA signature using a 160 bit curve (80 bits of security) costs 40 bytes, not 20. Commented Sep 18, 2014 at 11:57
  • @CodesInChaos thank you.Which is stronger between BLS and ECDSA in the same length of signature? Does it mean that 160 bit curve costs 40 bytes in hex characters(160/8*2)?
    – leo
    Commented Sep 18, 2014 at 12:40
  • @CodesInChaos >.<
    – RoraΖ
    Commented Sep 18, 2014 at 12:49

1 Answer 1


AFAIK you should check elliptic curves. Since BitCoin "account number" is a public key itself, I would suggest:


You should be even able to find an implementation in a BitCoin client.

However, I don't see a reason to use asymmetric cryptography in your case. Your application can just obtain a shared secret from the server and then use just HMAC to authenticate. Why not?

  • We assume that client was unsafe, so a shared secret may got by attackers from client.And they could send a validated short message to the phone and control it
    – leo
    Commented Sep 18, 2014 at 12:31
  • @leo You'd use a different shared secret for each client. If an attacker can extract the shared secret, they probably could remove the signature verification code just as easily. Either way, if the client doesn't trust itself, you're doomed. Commented Sep 18, 2014 at 13:11
  • @CodesInChaos I really agree with you.Actually asymmetric scheme is no need and even harmful here.But when we design(it means not coding yet) a system of security, we can't be more careful and nervous.Over engineering is bad, while over thinking is not.
    – leo
    Commented Sep 18, 2014 at 14:08
  • @leo Your choice is between a strong MAC, a hard to implement signature (BLS), a weak signature (DSA with small curve) and a longer signature. I wouldn't pick the weak signature. Commented Sep 18, 2014 at 14:14
  • @CodesInChaos I found jpbclink which generates a signature with 128 bits length.I changed some configration to generate 32 bits signature.But I'm not sure if 32 bits BLS signature is strong enough.I can't find any docs talking about bit length of BLS scheme
    – leo
    Commented Sep 19, 2014 at 10:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .