Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. 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 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?

share|improve this question
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. – Henrick Hellström May 7 '13 at 9:37
up vote 7 down vote accepted

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.

share|improve this answer
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. – fgrieu May 7 '13 at 10:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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