# Digital Signing algorithm for a fixed set of private and public keys in broadcasting like system?

I have a broadcast kind of system. Where sender knows what to send and receivers will know what sender has sent. Now the sender will sign the message with his own private key and receivers will verify with the provided public key.

Now, all the receivers will have the same public key and the sender will have one protected private key that is being used for signing of the messages.

Keys are not going to be changed for a very long long time. So the senders and receivers will end up having same keys for eternity.

Which cryptographic approach would be suitable for this use case to make sure no one else can sign the message and send to the receivers?

• Is what they'll actually have a digital signature keypair, rather than one for PKE? ​ ​
– user991
Nov 30, 2016 at 19:36
• @RickyDemer then SHA512WithECDSA for signature with secp256k1 curve keys seems to be a good enough solution? Nov 30, 2016 at 20:59

There is a lot of confusion in the question:

• message encryption is performed to achieve confidentiality, it is performed using the public key of the receiver's key pair (the public key needs to be trusted by the sender);
• message signing is performed to achieve authentication and integrity of messages, it is performed with the private key of the sender's key pair (the public key needs to be trusted by the receiver);

Now you are missing the receiver's key pair in your question. This makes it impossible to encrypt messages for the receiver, as you cannot establish the identity of the entity that is trying to contact you. You could still use Diffie-Hellman key agreement to establish a secret key to prevent passive attacks, but the scheme would not be secure against active attacks.

Public keys are usually not protected against attack. For instance, an RSA public key exponent is usually set to 65537 so anybody that also processes the modulus can guess the public key using only a single guess. Public key operations are usually not protected against leaking the public key either. So any scheme that requires the public key to be secret is build on quicksand.

You need to provide the receiver with a shared secret key or a key pair with a trusted public key to create a secure scheme.

[UPDATE] After the update only message authentication and integrity seem to be requested. This can be performed using any secure digital signature format. RSA with a large key size and PKCS#1 v2.1 PSS padding would likely be the best choice.

Although key rotation is always preferable, a large enough key pair is likely to be secure enough unless quantum computers start to scale really well. Currently QC secure algorithms are not standardized all to well, so it's not like you have much of a choice in that regard. ECDSA could also be used.

It's probably best to use an existing container format for this. Usually CMS would be recommended as protocol.

• Since the message is same for all the receivers, it makes it tough or rather impossible to encrypt using public key of receiver's key pair. Signing looks a better idea but I'm not sure about its strength. Dec 1, 2016 at 9:32
• Edited the question as well Dec 1, 2016 at 9:40

It seems that you don't actually want to encrypt the messages, but rather to authenticate them, so that nobody but the legitimate sender can create a message that would be accepted as valid by the receivers.

Reading between the lines, I suspect you also want the system to remain secure (in the sense just described) even if some of the receivers are compromised. (Obviously, there's no way to keep the messages secret if even one of the receivers is compromised and leaks them, but we can still at least hope to retain authentication.)

The obvious off-the-shelf solution to this problem would be to use an asymmetric digital signature scheme such as RSA-PSS or DSA / ECDSA. Such signature schemes are public-key cryptosystems where the sender possesses the private signing key, and the recipients only have the corresponding public key. Crucially, knowing the public key allows the recipients to verify signatures created using the sender's private key, but not to create valid signatures themselves.

However, for very long term use, all currently known signature schemes have one practical problem: their security is unproven, or rather, is only conditionally proven based on the assumption that some difficult mathematical problem (such as the RSA problem or the DH problem) remains infeasible to solve. While we can generally account for expected increases in brute force computational power simply by increasing the parameters (e.g. key size) that control the difficulty of the problem, what we cannot guarantee is that some clever person won't come up with new algorithm or device tomorrow that quickly solves any reasonable-sized instance of those problems.

Indeed, we know that some of the most commonly used digital signature schemes today, such as RSA, would be utterly broken if practical quantum computers capable of running Shor's algorithm became reality. Like practical fusion power, these also seem to lie perpetually just a few years in the future, but there's no way to tell when, if ever, their promises might actually be realized. However, even if you picked a post-quantum secure signature scheme, that doesn't really help much — most post-quantum signature schemes still remain new and poorly tested, often with a poor track record of having to be redesigned as new attacks poke holes in them, and even the few exceptions, like Merkle–Lamport hash signatures, still rely on fundamentally unproven security assumptions (such as, in that particular case, the existence and availability of a secure cryptographic hash function).

One practical way to improve the odds would be to sign each message with multiple different signature schemes, with independent keys, and have the recipients only accept messages for which all the signatures are valid. Even this, however, will not achieve unconditional security — there remains the possibility that, given enough time, all the signatures schemes could be broken. Sure, it's very unlikely, but not impossible, and eternity is, well, "a very long long time" as you say.

All that said, there are ways to authenticate messages with unconditionally provable information-theoretic security, such as Carter–Wegman MACs masked with a one-time pad. Alas, all currently known ways to achieve that have two major limitations:

1. They are symmetric secret-key schemes, meaning that the information needed to verify a signature is also sufficient to forge one. Thus, to prevent a single compromised recipient from breaking the whole scheme, you'd need to arrange for each recipient to have its own unique key(s), and sign each message separately for each recipient.

2. They are one-time authentication schemes, such that each key can only be safely used to authenticate one message. Furthermore, unlike e.g. the Merkle–Lamport signatures mentioned above, they provide no obvious way to redistribute new keys as needed (since, these being symmetric schemes, the new keys would have to be kept unconditionally secret somehow). Thus, each recipient must store as many independent keys as the maximum number of messages they ever expect to receive (and, of course, the sender must store all these keys for all recipients).

Thus, while such schemes might have some use for niche applications with extreme security requirements and limited message volume (like, say, authenticating missile launch commands), they remain infeasible for most practical uses.

Also, while such schemes are unconditionally secure, meaning that their security rests on no unproven assumptions, they're still not 100% forgery resistant — for any signature scheme, an attacker can always try to forge a signature simply by guessing at random, and will succeed with a probability of at least $1/2^n$, where $n$ is the length of the signature in bits. We can obviously make this probability as close to zero as we want simply by using longer signatures (and correspondingly longer keys), but we cannot make it exactly zero.

• I think you understood pretty much correctly. I want to print a message in the form of a QR code and would use my mobile app to read it. Now all the people having my mobile app would be having the same public key. Even if one gets compromised, that must not bother me. Message transfer is print in nature, One can not play around much as what once printed in a volume of thousands, can not be rolled back or you would never know the time of verification. So ECDSA or signing remains the only choice here? Can I pass altogether different keys in every QR code to add dynamicity? Dec 1, 2016 at 6:09
• Also read somewhere about signcryption, though not sure about the theory behind. Dec 1, 2016 at 6:17
• Edited the question as well Dec 1, 2016 at 9:40