4 ms·

>Er, well, this fails because there is no way to compress cryptographic material, and we're talking about random or pseudo-random keys being compressed (which,

>Er, well, this fails because there is no way to compress cryptographic material, and we're talking about random or pseudo-random keys being compressed (which, you can't) then encrypted. So this particular idea fails immediately. Excuse me, but wtf. That's BS. Cryptographic material is nothing but data. A Huffman encode will work on a number that happens to be a public key just as happily as it will a anything else. Cryptographic material doesn't have a magic "immune to compression" characteristic.

astrange 4y ago
An RSA public key is a prime number. How are you going to compress a prime number? Encrypted material should not be compressable because it needs to appear random no matter what the unencrypted contents are, otherwise you have information about those contents. (You can trade off between the security and compressability, but shouldn't.)
- LegionMammal978 4y ago
  > An RSA public key is a prime number. How are you going to compress a prime number? In principle, given an n-bit prime p, you can store an expected log₂ n − 0.5 additional bits by using the gap between p and the next prime. Though in practice, I'd be surprised if the 19 or so extra bits could be dangerous.
- cryptonector 4y ago
  An RSA public key is a small exponent for encryption and a large composite pq where p and q are large primes. There's more to it, naturally, but I'll stop there. You can have many many RSA keys of any given size, say 2048 bits for now. So something somewhat less than 2^2048 possible keys for 2048 bit RSA keys, let's say 2^2000 keys, which... is a lot! Since one should generate keys randomly we can expect that no one key will be much more frequently used than any other, so Huffman encoding is right out, but even if you try Huffman encoding anyways you'll find that most keys will end up with Huffman codes that are longer than the keys themselves meaning that the keys are not compressible! Thinking about AES-256 will be easier. Say we have 2^40 computers able to randomly generate 2^64 AES-256 keys every day. Well, it will still take a long time to generate all possible AES-256 keys. So say in the best case scenario we get close to 2^120 keys or so. How would we even measure their frequencies so we could assign Huffman codes to them? Well, we can't, and even if we could most keys would have a frequency between 1 and 3. And still the next key to be generated could be outside that set so we really have to assign a code to each key, and there's... 2^256 possible keys... which means that even if we could assign a code to each key we couldn't write that down because there's not enough atoms on Earth to do it with. But let's say we just define a collation of AES-256 keys and assign then Huffman codes in order... But now we'll soon see that most keys will get codes assigned that are longer than 256 bits. Which means that the average input to this compressor would... yield an expansion, not a compression.
cryptonector 4y ago
Try it for yourself. Encrypt /dev/zero in some key using AES, then compress it with whatever compressor you like. Try it many times. Let us know how it goes! And, yes, you can compress specific pseudo-random looking symbols, but only a few. We're talking about arbitrary pseudo-random data, and that will not compress.

astrange 4y ago

An RSA public key is a prime number. How are you going to compress a prime number? Encrypted material should not be compressable because it needs to appear random no matter what the unencrypted contents are, otherwise you have information about those contents. (You can trade off between the security and compressability, but shouldn't.)

LegionMammal978 4y ago
> An RSA public key is a prime number. How are you going to compress a prime number? In principle, given an n-bit prime p, you can store an expected log₂ n − 0.5 additional bits by using the gap between p and the next prime. Though in practice, I'd be surprised if the 19 or so extra bits could be dangerous.
cryptonector 4y ago
An RSA public key is a small exponent for encryption and a large composite pq where p and q are large primes. There's more to it, naturally, but I'll stop there. You can have many many RSA keys of any given size, say 2048 bits for now. So something somewhat less than 2^2048 possible keys for 2048 bit RSA keys, let's say 2^2000 keys, which... is a lot! Since one should generate keys randomly we can expect that no one key will be much more frequently used than any other, so Huffman encoding is right out, but even if you try Huffman encoding anyways you'll find that most keys will end up with Huffman codes that are longer than the keys themselves meaning that the keys are not compressible! Thinking about AES-256 will be easier. Say we have 2^40 computers able to randomly generate 2^64 AES-256 keys every day. Well, it will still take a long time to generate all possible AES-256 keys. So say in the best case scenario we get close to 2^120 keys or so. How would we even measure their frequencies so we could assign Huffman codes to them? Well, we can't, and even if we could most keys would have a frequency between 1 and 3. And still the next key to be generated could be outside that set so we really have to assign a code to each key, and there's... 2^256 possible keys... which means that even if we could assign a code to each key we couldn't write that down because there's not enough atoms on Earth to do it with. But let's say we just define a collation of AES-256 keys and assign then Huffman codes in order... But now we'll soon see that most keys will get codes assigned that are longer than 256 bits. Which means that the average input to this compressor would... yield an expansion, not a compression.

cryptonector 4y ago

Try it for yourself. Encrypt /dev/zero in some key using AES, then compress it with whatever compressor you like. Try it many times. Let us know how it goes! And, yes, you can compress specific pseudo-random looking symbols, but only a few. We're talking about arbitrary pseudo-random data, and that will not compress.