3 ms·

Because there is less entropy in 40 characters of public key than there is in 40 characters of cryptographic hash of a public key.

deleted 3y ago
[deleted]
brookst 3y ago
Great answer, but why? Doesn’t that suggest the public key should be suitable for lossless compression to fewer bits?
- smnc 3y ago
  Hashing is not compression, it should not be reversible/inflatable.
- Dylan16807 3y ago
  You have to leak information about the key generation to compress it.
- lucb1e 3y ago
  I think the two existing replies misunderstood your question, but it's a good one. Which is to say, I don't know the answer but I feel like I should! I'll take a guess. There are large gaps between good RSA keys. 100 may be a valid key and 138, but not anything in between. Or, well, they're valid but they're trivially broken by having a divisor other than 1, itself, and the huge prime factors (the example of 100 and 138 are not good keys for exactly that reason; finding secure keys is left as an...). That's why we need RSA keys that are more than 256 bits in length: the key space is sparse and an attacker can, with some amount of efficiency, skip over the gaps. (This is all from years-old memories of how RSA works, don't take this for absolute certainty.) What I'm guessing the answer to your question is, is this: it must be inefficient to reconstruct the key from an indexed form (e.g.: the first good key (100) has index 1, the second good key (138) index 2, etc.) without spending computational power disproportionate to the amount of extra resources that storing/transmitting the full key takes. Now that I read the other answers again, maybe that's what Dylan meant, but to me that answer seems wrong because the public key is argued to not be uniformly random and that's precisely what compression algorithms are able/made to deal with. Perhaps not as efficiently as indexing can, but still. You wouldn't need to apply it to the prime factors or private key (doing that would, as they say, leak information), just the public part which people were saying is not fully random.

deleted 3y ago

[deleted]

brookst 3y ago

Great answer, but why? Doesn’t that suggest the public key should be suitable for lossless compression to fewer bits?

smnc 3y ago
Hashing is not compression, it should not be reversible/inflatable.
Dylan16807 3y ago
You have to leak information about the key generation to compress it.
lucb1e 3y ago
I think the two existing replies misunderstood your question, but it's a good one. Which is to say, I don't know the answer but I feel like I should! I'll take a guess. There are large gaps between good RSA keys. 100 may be a valid key and 138, but not anything in between. Or, well, they're valid but they're trivially broken by having a divisor other than 1, itself, and the huge prime factors (the example of 100 and 138 are not good keys for exactly that reason; finding secure keys is left as an...). That's why we need RSA keys that are more than 256 bits in length: the key space is sparse and an attacker can, with some amount of efficiency, skip over the gaps. (This is all from years-old memories of how RSA works, don't take this for absolute certainty.) What I'm guessing the answer to your question is, is this: it must be inefficient to reconstruct the key from an indexed form (e.g.: the first good key (100) has index 1, the second good key (138) index 2, etc.) without spending computational power disproportionate to the amount of extra resources that storing/transmitting the full key takes. Now that I read the other answers again, maybe that's what Dylan meant, but to me that answer seems wrong because the public key is argued to not be uniformly random and that's precisely what compression algorithms are able/made to deal with. Perhaps not as efficiently as indexing can, but still. You wouldn't need to apply it to the prime factors or private key (doing that would, as they say, leak information), just the public part which people were saying is not fully random.