I need to sign the numbers from 1 to 1 billion (literally this, it's not an analogy) using a digital signature and then send these numbers in a particular order to someone. The message is not private and the receiver should be able to verify its authenticity without having to reply; it's a one-way public communication channel.

Are there any algorithms that are safe enough for this? How many bits should the key have and how many bits will the signature have?

  • 2
    $\begingroup$ You might want to pay close attention to exactly what "authentic" means in this context. It just means that the sender at some point in time, indeed signed a message with particular contents. Hence, replay attacks might be a concern in similar scenarios. If you need to know when and in response to what request the sender signed the message, the sender will have to sign that information too. $\endgroup$ Commented May 7, 2013 at 9:37

1 Answer 1


Yes. Any good standard digital signature algorithm will be secure in this setting.

Digital signature algorithms are designed to be secure against chosen-message attacks, where the attacker can choose any set of messages and learn the signatures on those messages; the security of the signature scheme means that this doesn't help the attacker at all. This means that it's safe to sign arbitrary messages; there's nothing dangerous or special about messages that are small numbers.

You should choose the key size based upon the desired security level. A bare-minimum security level is 80-bit security; that then translates to a key size (in a way that is dependent upon the specific signature algorithm you choose). Similarly, the size of the signature will depend upon the particular signature algorithm you use.

  • 4
    $\begingroup$ Perhaps make that any good digital signature algorithm; some standards have been lacking in this respect; e.g; ISO/IEC 9796 (better known as ISO/IEC 9796-1) which was withdrawn following attacks, and ISO/IEC 9796-2 which has a more or less serious vulnerability in its original (and most used) mode. $\endgroup$
    – fgrieu
    Commented May 7, 2013 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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