Private keys do not provide security by having a large keyspace, they provide security through the difficulty of factoring huge semiprimes. Leaking part of a private key doesn't leak an equivalent amount of information.

As factoring semiprimes is assumed to be so secure that brute force is the best possible attack, the smaller key space applies as well. Just because you can skip quite some primes which would otherwise be a potential part of the key, because they would contain the leaked part of the key.

@forest What do you mean by "an equivalent amount of information"? Those private keys are one of the large semiprimes, so any leak of part of the key reduces the search space by "an equivalent factor", no?

All information in a private key is not equal, so there is no "equivalent factor". Leak the modulus or public exponent and nothing happened (versus sharing the public key). Leak "50%" of the prime numbers and you're 100% boned.

Ah, now this is interesting. Presumably it does leak some information though?

@JamieBull re-reading the question, you don't really specify what type of encryption you're using; 256 bits is tiny for RSA crypto, but large for AES... The question can't be definitively answered one way or the other.

@allo: factoring is hard, but not nearly as hard as brute force, however leaking enough bits might make bruteforce more feasible than other algorithms (where knowing those bits gains you nothing)

@NickT Isn't AES-256 pretty standard nowadays ? It's in NIST recommendation since 2010 and is implemented in BitLocker or FileVault full disk encryptions.

@forest Private keys do not provide security by having a large keyspace, they provide security through the difficulty of factoring huge semiprimes - This is only true for certain cryptosystems (namely RSA). This is not the case for most cryptosystems. Many cryptosystems use a uniformly random integer for a private key.

No, don't exchange a hash. Exchange the public key. That's what it's for!

@EllaRose Them saying private key implied asymmetric cryptography. All of those involve factorization, the discrete log problem, etc.

@allo As factoring semiprimes is assumed to be so secure that brute force is the best possible attack What? No it's not. The GNFS can factor a n-bit key in far fewer operations than it'd take to go through an n-bit keyspace. This comment is just patently false.

@forest I was referring to asymmetric cryptography. I will restate it again so there is no misinterpretation: There exist asymmetric cryptosystems that use uniformly random integers as a private key. All of those involve factorization - this is incorrect. In fact, it's almost the opposite of the truth, as most of them do not.

@EllaRose You're right. What I meant was that their security has nothing to do with a large keyspace, but rather with trapdoor functions (such as factorization or discrete log).

Though I would like to know what you mean by "There exist asymmetric cryptosystems...". I can't think of anything in public key cryptography where the entire private key is a uniform random blob. Sure, they use uniform randomness, but they all have a complex internal structure, where some bits are more "sensitive" than others, regardless of whether or not factorization is involved in breaking it.

@Stephane Given that this answer probably will remain on top, I think it would be nice if it could address some of the concern highlighted in comments and D.W. answer. Specifically, I think it might be good to be very clear that for some algorithms, doing this could be catastrophic. I don't think you're answer is wrong, just that a more pessimistic outlook highlighting the worst dangers would be more useful.

My key contains the letter a. Multiple times.

@forest ECC private keys are just arbitrary integers in the set [1,n). Revealing 8 bits of an ECC d (other than 0-bits beyond n) makes cracking it 256 times easier. (ECC private keys are uniform random, mod Ord(G)=n)

@Stephane Greats! Thanks for taking the time!