Signing 2x128 bits key vs 1x256

1. Is signing something 2 times with two different 128 bit keys as safe as signing once with 256 bit key ?
2. Does signing 2 times with 256 bit key will make it stronger than signing once ?
• Signing two times with two 128-bit key = signing one time with a 129-bit key, and wastes twice the time. – DannyNiu Aug 23 '17 at 0:10
• Can you get more into details ? – user50694 Aug 23 '17 at 2:16
• You can't sign something with an AES key (it can only be used as MAC). And both a 128-bit and a 256-bit RSA key are ridiculously unsafe. A 1024-bit RSA key is the bare minimum, with 2048 bits strongly recommended. – CodesInChaos Aug 23 '17 at 7:14
• @CodesInChaos but a 256-bit ECC key is fine :p – SEJPM Aug 23 '17 at 14:31

Ok, first things first: Your question actually touches on two subjects:

1. Is it better / as good to sign something with two different half-length keys than with one full-length key?
2. Is it better / as good to use two half-entropy passwords as one full-entropy password?

The (theoretical) answer to both of these questions is a clear no. However, details matter, which can turn the "no" into a "yes".

To adress the first question: If "half-length" means that each key has a secure keylength to begin with, then yes, this is about as secure as using a full-length key, because each key is unbreakable to begin with, meaning we have "unbreakable" vs "even more unbreakable" at which point other considerations should pitch in. For example it might be easier to ensure correct usage if two keys are forced. It will be harder to extract two keys using side-channels or malware than it will be to extract one.

However, if half-length means that only the full-length key has a secure standard key-length, then this will be completely broken. As an example consider Elliptic Curve keys (such as used by ECDSA in Bitcoin): One 256-bit key is unbreakable right now because you need $2^{128}$ operations to break it, but two 128-bit keys are very much breakable because they require less than $2^{64}+2^{64}=2^{65}$ operations to be broken (because you can re-use parts of the computations).

Now for the specific instance noted in the comments:

Are you familiar with bitcoin bip39 wallet creation ? My initial concern is, if multi-signature wallet created by two accounts with both seed of 12 words (128 bits of entropy) is safer or safe same as regular single signature account with seed of 24 words (256 bits of entropy ) ?

Now this is the question 2) I named above. While yes, this password will only offer 129 bits of security, this is already "unbreakable" at which point we would be discussing about "unbreakable" vs "unbreakable". Now nobody would successfully guess a 128-bit entropy secret, so it has to be stolen. It is harder to steal two secrets (which preferably are at different locations) than it is to steal one secret, so using two keys is actually preferable in this scenario.

So it would be actually better to set up this account with 2x 24 word seed account which will produce 257 bits of [security].

Yes, it would be "better" in a theoretical sense. In a practical sense there's no security gain and all you achieve is making your own life harder by having to remember / type more words. Also see this Q&A on why really long passwords aren't better.

Out of curiosity, does ed25519 support full security of 256 bits ?

No, Ed25519 has about 126 bits of security. The linked source talks about Curve25519 but can be equally applied to Ed25519 with minimal transformations.

at some point i've heard that bitcoin developers were saying that it's way more secure than Secp256k1 ecdsa

Theoretically no, practically yes. secp256k1 provides the "full" 128-bit security that you would expect and thus is "more secure" than Ed25519. However, Ed25519 is a more modern mode and curve than ECDSA with secp256k1 meaning it is easier to get right and secure against implementation mistakes. This (and the speed bonus) is why it's usually preferred over ECDSA.

Also - is there any asymmetrical cryptography algorithm with 256 bit security, if yes - then why Bitcoin or other crpyotcurrencies are not utilising it ?

Yes, if you replace secp256k1 with the P-521 curve, you get about 256-bits of security. However this will also be a lot slower because there are likely less optimizations and the operations are more complex due to larger values. Also see this answer for some discussion on curve sizes larger than 256-bit.

One final note: When I'm talking about "x-bit security" here, I mean that $2^x$ operations are needed to carry out a successful attack. The actual keying material may be bigger than the "security bitlength" which is only the lower bound.

• Yes, I know this isn't precisely answering the standard interpretation of the question, but I'm sure it will help the OP more than the "standard" answer. – SEJPM Aug 23 '17 at 19:03
• Thanks for answer, really appreciate. Last one question - according to "so using two keys is actually preferable in this scenario" Using multiple signature account with 2x 12 word seed will provide in total 129 bits of entropy. So it would be actually better to set up this account with 2x 24 word seed account which will produce 257 bits of entropy. (assuming bitcoin can support it) - is that correct ? Out of curiosity, does ed25519 support full security of 256 bits ? (at some point i've heard that bitcoin developers were saying that it's way more secure than Secp256k1 ecdsa) – user50694 Aug 23 '17 at 22:19
• @user3370412 yes, two long(er) passwords will make the "unbreakable" password "more" "unbreakable" (ie "upgrade the security" from 129 to 257 bit). Ed25519 has about 125-bit security as opposed to secp256k1's 128-bit. However this small difference doesn't matter and Ed25519 implementations are likely more resistant to implementation mistakes. – SEJPM Aug 24 '17 at 12:05
• I see. However i still don't understand why Ed25519 has 125-bit security and secpk256k1's 128bit while both private keys are 256bit ? Can you send link to something to let me understand ? Also - is there any asymmetrical cryptography algorithm with 256 bit security, if yes - then why Bitcoin or other crpyotcurrencies are not utilising it ? – user50694 Aug 24 '17 at 14:37
• I'm still not sure, even when modulus is 255 bit, why does security is limited to 125 bit or 128 for bitcoin sepck256k1 ? – user50694 Aug 24 '17 at 16:58

Let's assume we're talking about public-key cryptography, and the signature scheme in question have the same security level as its key size. Your questions may be answered as follow:

1. No

Breaking any n-bit key requires searching through $2^n$ possible keys.

Breaking something signed with two 128-bit key requires breaking 128-bit keys for two times - that is $2 \cdot 2^{128} = 2^{129}$ work load.

2. Yes, by 1 bit at most.

• Yes, it's public key cryptography. Thanks for reply, but i have question. If it was signed twice with 128-bit key, why 2 * 2^128 and not 2^128+2^128 ? – user50694 Aug 23 '17 at 4:29
• Do maths please. x+x=2x. – DannyNiu Aug 23 '17 at 4:38
• Sorry, that's correct. Are you familiar with bitcoin bip39 wallet creation ? My initial concern is, if multi-signature wallet created by two accounts with both seed of 12 words (128 bits of entropy) is safer or safe same as regular single signature account with seed of 24 words (256 bits of entropy ) ? Based on this discussion, i think multi-signature account provides only 2^129 in that case ? – user50694 Aug 23 '17 at 12:22
• Actually, the second part of the answer may very well be wrong depending on the details of the scheme used, but in general the security increase would be less than a bit. – SEJPM Aug 23 '17 at 14:30
• @user3370412 Bitcoin's security is limited to 128 bits, since it uses a 256 bit elliptic curve. There is some complexity due to expensive hashing of the passphrase and multi-target attacks, but having more than 15 words certainly won't improve security. – CodesInChaos Aug 23 '17 at 15:40