Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
