dre*_*ves 42 encryption entropy data-compression information-theory
有没有标准的方法来做到这一点？
谷歌搜索 - "近似熵"位 - 揭示多篇学术论文,但我想找到一个伪代码块来定义任意长度的给定位串的近似熵.
(如果这说起来容易做起,而且取决于应用程序,我的应用程序涉及16,320位加密数据(密文).但加密为难题而不是无法破解.我以为我先检查一下熵,但不能轻易找到这样的好定义.所以这似乎是一个应该在StackOverflow上的问题!关于从哪里开始去除16k随机看似位的想法也是受欢迎的......)
另请参阅此相关问题:
熵的计算机科学定义是什么？
Tho*_*nin 31
熵不是你得到的字符串的属性,而是你可以获得的字符串的属性.换句话说,它限定了生成字符串的过程.
在简单情况下,将得到的一组中的一个串Ñ可能的字串,其中每个串具有被选择比所有其他的相同的概率,即,1/N.在这种情况下,该字符串被称为具有N的熵.熵常用于位表示,这是一个对数标度:"的一个熵Ñ位"是等于熵2 Ñ.
例如:我喜欢将密码生成为两个小写字母,然后是两个数字,然后是两个小写字母,最后是两个数字(例如va85mw24).字母和数字是随机,均匀和相互独立地选择的.此过程可能产生26*26*10*10*26*26*10*10 = 4569760000个不同的密码,并且所有这些密码都有相同的机会被选中.这样的密码的熵是4569760000,这意味着大约32.1比特.
fma*_*ark 20
香农熵方程是标准的计算方法.这是Python中的一个简单实现,从Revelation代码库中无耻地复制,因此GPL许可:
import math
def entropy(string):
"Calculates the Shannon entropy of a string"
# get probability of chars in string
prob = [ float(string.count(c)) / len(string) for c in dict.fromkeys(list(string)) ]
# calculate the entropy
entropy = - sum([ p * math.log(p) / math.log(2.0) for p in prob ])
return entropy
def entropy_ideal(length):
"Calculates the ideal Shannon entropy of a string with given length"
prob = 1.0 / length
return -1.0 * length * prob * math.log(prob) / math.log(2.0)
请注意,此实现假定您的输入比特流最好表示为字节.这可能是您的问题域的情况,也可能不是.你真正想要的是你的比特流转换成一串数字.您如何决定这些数字是特定于域的.如果你的数字真的只有一个零,那么将你的比特流转换为一个零和一个零的数组.但是,您选择的转换方法会影响您获得的结果.
dre*_*ves 11
我相信答案是字符串的Kolmogorov复杂性.这不仅对一大块伪代码负责,Kolmogorov复杂性不是一个可计算的函数!
您可以在实践中做的一件事是使用最佳可用数据压缩算法压缩位串.压缩越多,熵越低.
rob*_*rob 10
NIST 随机数生成器评估工具包有一种计算“近似熵”的方法。这是简短的描述：
近似熵测试描述：此测试的重点是每个重叠 m 位模式的频率。测试的目的是将两个连续/相邻长度（m 和 m+1）的重叠块的频率与随机序列的预期结果进行比较。
本页的PDF提供了更全面的解释：
http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
小智 8
没有一个答案.熵始终与某些模型相关.当有人谈论熵有限的密码时,他们的意思是"相对于智能攻击者预测的能力",并且它始终是一个上限.
你的问题是,你正试图测量熵以帮助你找到一个模型,这是不可能的; 熵测量可以告诉你的是模型有多好.
话虽如此,你可以尝试一些相当通用的模型; 它们被称为压缩算法.如果gzip可以很好地压缩您的数据,那么您已经找到了至少一个可以很好地预测数据的模型.例如,gzip对简单替换几乎不敏感.它可以在文本中经常处理"wkh",就像处理"the"一样容易.
很抱歉这么久回答这个问题.
看看我最近的论文:
"BiEntropy - 有限二进制串的近似熵"
http://arxiv.org/abs/1305.0954
"我们设计,实现并测试一个简单的算法,该算法计算任意长度的有限二进制串的近似熵.该算法使用字符串的Shannon Entropies的加权平均值和除字符串的最后二进制导数之外的所有.我们成功在素数理论(我们明确证明素数序列不是周期性的),人类视觉,密码学,随机数生成和定量金融领域中测试算法"