I would like to use an asymmetric rather than symmetric signature for authorization, since I don't want a compromised service being able to forge authorization tokens (obviously). An authorization token is generated by an authentication server for a specific set of services, and returned to the client, always transported as a base64 encoded string. After expiry, the principal must re-authenticate to retrieve a fresh token.

I need to handle a high volume of very small stateless HTTP-REST requests (potentially several a second per client), and I'm conscious of the overall size of the token saturating the network. Currently I'm (randomly) considering using 2048-bit RSA with SHA-256, but further reducing this overhead would be great.

Since a given token will always expire within at most 15 minutes, it dawned on me that it should be possible to use an even smaller key/hash by regularly generating new key-pairs.

Services would periodically poll a key provider service to retrieve the current and next public key, and a byte or so of the token would identify the key used to sign it.

Is my assumption correct? Can I stoop to as low as 1024-bit keys? I vaguely recall that there is a break for RSA <= 512 bits, how severe is it, and could one compensate by rotating the keypairs faster?

I'm not married to either RSA or SHA256, but I am dependent on OpenSSL.

I'd like to first ensure my reasoning is sound, and second, to solicit any algorithm/key-sizes/alternative techniques that would be considered good practice in this situation.

  • I'm not seeing the connection b/w reducing the bit level and the 15 minute expiration. Is it that you suspect brute force can't feasibly be applied within 15 minutes to 1024 bit keys or smaller hashes? If so, you may be onto something... at least the SHA1 (160bit) hash was cracked in almost an hour, it was nowhere near 15 minutes
    – dozer
    May 14, 2014 at 15:46
  • In addition to my previous comment RSA 1024 currently hasn't been cracked yet if I recall correctly, the highest cracked bit strength is 768 bits.. I'm not sure if this info is relevant though, it depends on my clarification sought earlier
    – dozer
    May 14, 2014 at 15:53
  • Hi, yes, that's exactly it. The conventional wisdom on key/hash sizes is based on the principle that the key must be uncompromised for the duration of its lifetime, and that the expected lifetime is at least a year or so. In my case, if it is likely to take a week to crack, then the key is already useless, since forgeries will not be accepted. The key is only being used for signatures, so unless your opponent has a time machine, you're safe. I may be on risky ground here, though, and I can never find believably up to date effort tables.
    – mseddon
    May 14, 2014 at 17:37

1 Answer 1


If you want fast & secure crypto, use NaCl library by Bernstein et al. Relevant to your question is its ED25519 asymmetric crypto system. Key generation, signatures, and verification are lightening fast. Far as space goes, the keys are 32 bytes and signatures are 64 bytes. Their implementations are resistant to timing channels. They also implement more common algorithms for compatibility. They also give you high level features along the lines of "sign this" rather than forcing use of low-level primitives on people who aren't cryptographers.


You must log in to answer this question.

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