随机数据的无损压缩
Lossless Compression of Random Data
tl;博士
最近开始收听安全播客，听到了下面这句话（意译）
One of the good hallmarks of a cryptographically strong random number is its lack of compressibility
这让我立刻想到，随机数据可以无损压缩吗？我开始阅读，发现 this wikipedia article。下面是引用的块
In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm: indeed, this result is used to define the concept of randomness in algorithmic complexity theory.
我理解 pigeon hole principle，所以我假设我在某处错了，但我错过了什么？
想法：
假设您有一个非对称可变长度加密方法，通过该方法您可以将任何 N 位转换为 N-16 位数字或 N+16 位数字。这可能吗？
如果我们有一个非对称算法可以使数据说大 16 位或小 16 位，那么我想我可以想出一种可靠地产生无损压缩的算法。
任意数据的无损压缩算法
将初始数据分成给定大小的块。然后使用 "key" 并尝试按如下方式压缩每个块。
function compress(data)
compressedData = []
chunks = data.splitBy(chunkSize);
foreach chunk in chunks
encryptedChunk = encrypt(chunk, key)
if (encryptedChunk.Length <= chunk.Length - 16) // arbitrary amount
compressedData.append(0) // 1 bit, not an integer
compressedData.append(encryptedChunk)
else
compressedData.append(1) // 1 bit, not an integer
compressedData.append(chunk)
end foreach
return compressedData;
end function
并且对于解压缩，如果您知道块大小，那么每个以 0 开头的块都会执行非对称加密并将数据附加到正在进行的数组中。如果块以 0 开头，只需按原样附加数据。如果加密方法产生较小的 16 位值的频率甚至是产生较大的 16 位值的频率的 1/16，那么这是否可行？每个块要么大 1 位，要么小 15 位。
另一个考虑因素是压缩算法使用的 "key" 可以是固定的，也可以附加到压缩数据的开头。同样考虑块大小。
有2N−16个可能的(N−16)位序列, 和 2N 个可能的 N 位序列。因此，每 216 N 位序列中最多只有一个可以无损压缩为 N −16 位。所以它发生的频率会比 1/16 的时间少很多。它最多有 1/65536 次发生。
如您的推理所示，剩余的 N 位序列可以扩展为 N+1 位；没有必要浪费额外的 15 位来编码它们。尽管如此，随机 N 位序列在 (N−16) 位可压缩序列集合中的概率很小平均压缩率（或预期压缩率）将继续为 1.0（最多）。
tl;博士
最近开始收听安全播客，听到了下面这句话（意译）
One of the good hallmarks of a cryptographically strong random number is its lack of compressibility
这让我立刻想到，随机数据可以无损压缩吗？我开始阅读，发现 this wikipedia article。下面是引用的块
In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm: indeed, this result is used to define the concept of randomness in algorithmic complexity theory.
我理解 pigeon hole principle，所以我假设我在某处错了，但我错过了什么？
想法：
假设您有一个非对称可变长度加密方法，通过该方法您可以将任何 N 位转换为 N-16 位数字或 N+16 位数字。这可能吗？
如果我们有一个非对称算法可以使数据说大 16 位或小 16 位，那么我想我可以想出一种可靠地产生无损压缩的算法。
任意数据的无损压缩算法
将初始数据分成给定大小的块。然后使用 "key" 并尝试按如下方式压缩每个块。
function compress(data)
compressedData = []
chunks = data.splitBy(chunkSize);
foreach chunk in chunks
encryptedChunk = encrypt(chunk, key)
if (encryptedChunk.Length <= chunk.Length - 16) // arbitrary amount
compressedData.append(0) // 1 bit, not an integer
compressedData.append(encryptedChunk)
else
compressedData.append(1) // 1 bit, not an integer
compressedData.append(chunk)
end foreach
return compressedData;
end function
并且对于解压缩，如果您知道块大小，那么每个以 0 开头的块都会执行非对称加密并将数据附加到正在进行的数组中。如果块以 0 开头，只需按原样附加数据。如果加密方法产生较小的 16 位值的频率甚至是产生较大的 16 位值的频率的 1/16，那么这是否可行？每个块要么大 1 位，要么小 15 位。
另一个考虑因素是压缩算法使用的 "key" 可以是固定的，也可以附加到压缩数据的开头。同样考虑块大小。
有2N−16个可能的(N−16)位序列, 和 2N 个可能的 N 位序列。因此，每 216 N 位序列中最多只有一个可以无损压缩为 N −16 位。所以它发生的频率会比 1/16 的时间少很多。它最多有 1/65536 次发生。
如您的推理所示，剩余的 N 位序列可以扩展为 N+1 位；没有必要浪费额外的 15 位来编码它们。尽管如此，随机 N 位序列在 (N−16) 位可压缩序列集合中的概率很小平均压缩率（或预期压缩率）将继续为 1.0（最多）。