2. General Requirements (一般要求)
2. General Requirements (一般要求)
今天, 一个常见的随机性要求是选择用户密码, 通常是一个简单的字符串。显然, 可以被猜到的密码不能提供安全性。对于可重用的密码, 期望用户能够记住密码。这可能使得使用可发音的字符串或由普通单词组成的短语是可取的。但这只影响密码信息的格式, 而不影响密码必须非常难以猜测的要求。
许多其他要求来自密码学领域。密码技术可用于提供各种服务, 包括保密性和认证。这些服务基于对手未知且无法猜测的数量, 传统上称为"密钥"。
甚至TCP/IP协议在选择初始序列号时也使用随机性 [RFC1948]。
一般来说, 上述例子也说明了可能需要的两种不同类型的随机数量。在人类可用密码的情况下, 唯一重要的特征是它们不可猜测。它们可能由ASCII字符组成并不重要, 例如每个字节的最高位都是零。另一方面, 对于固定长度的密钥等, 通常需要看起来真正随机的数量, 即其比特将通过统计随机性测试的数量。
在某些情况下, 例如使用一次性密码本的对称加密或像美国高级加密标准 [AES] 这样的算法, 希望保密通信和/或认证的各方必须都知道相同的秘密密钥。在其他情况下, 当使用非对称或"公钥"密码技术时, 密钥成对出现。密钥对的一个密钥是私有的, 必须由一方保密; 另一个是公开的, 可以向世界公布。从公钥确定私钥在计算上是不可行的, 并且知道公钥对对手没有帮助 [ASYMMETRIC]。参见一般参考文献 [SCHNEIER, FERGUSON, KAUFMAN]。
对随机数量的频率和容量要求因不同的密码系统而大不相同。使用纯RSA, 仅在生成新密钥对时需要随机数量; 此后, 可以在不需要进一步随机性的情况下签署任意数量的消息。美国国家标准与技术研究院 (NIST) 设计的公钥数字签名算法要求每个签名都有良好的随机数 [DSS]。使用一次性密码本加密 (原则上是最强的加密技术) 需要与要处理的所有消息等量的随机性。参见一般参考文献 [SCHNEIER, FERGUSON, KAUFMAN]。
在大多数这些情况下, 对手可以通过试错来尝试确定"秘密"密钥。只要密钥足够小于消息以使正确的密钥可以被唯一识别, 这就是可能的。必须使对手成功的概率达到可接受的低水平, 具体取决于特定应用程序。对手必须搜索的空间大小与在信息论意义上存在的密钥"信息"量有关 [SHANNON]。这取决于可能的不同秘密值的数量和每个值的概率, 如下所示:
-----
\
Bits of information = \ - p * log ( p )
/ i 2 i
/
-----
其中i从1计数到可能的秘密值的数量, p sub i是编号为i的值的概率。(因为p sub i小于1, 所以对数将是负数, 因此和中的每一项都将是非负的。)
如果有2^n个等概率的不同值, 那么存在n比特的信息, 对手平均必须尝试一半的值, 或2^(n-1), 才能猜出秘密数量。如果不同值的概率不相等, 那么存在的信息就更少, 对手平均需要更少的猜测。特别是, 对手可以知道不可能或低概率的任何值最初可以被对手忽略, 对手将首先搜索更可能的值。
例如, 考虑一个使用128位密钥的密码系统。如果这些密钥使用固定的伪随机数生成器派生, 该生成器使用8位种子进行播种, 那么对手只需要搜索256个密钥 (通过使用每个可能的种子运行伪随机数生成器), 而不是乍看之下的2^128个密钥。这些128位密钥中只有8比特的"信息"。
虽然上述分析平均来说是正确的, 但在某些情况下对于密码分析来说可能会产生误导, 因为真正重要的是对手的工作因子。例如, 假设有一个伪随机数生成器生成128位密钥, 如前一段所述, 但它一半时间生成零, 其余时间从剩余的2^128 - 1个值中随机选择。上面的Shannon方程说这些密钥值中有64比特的信息, 但对手只需尝试值零, 就可以破坏一半使用的安全性, 尽管是随机的一半。因此, 出于密码学目的, 查看其他度量也很有用, 例如最小熵, 定义为
Min-entropy = - log ( maximum ( p ) )
i
其中i如上所述。使用这个方程, 我们得到1比特的最小熵用于我们新的假设分布, 而不是64比特的经典Shannon熵。
已经定义了连续的熵谱, 有时称为Renyi熵, 由参数r指定。这里r = 1是Shannon熵, r = 无穷大是最小熵。当r = 零时, 它只是log(n), 其中n是非零概率的数量。Renyi熵是r的非递增函数, 因此最小熵始终是最保守的熵度量, 通常是用于密码评估的最佳度量 [LUBY]。
传统意义上的统计测试随机性与安全使用所需的不可预测性不同。
例如, 使用广泛可用的常量序列, 例如CRC标准数学表中的随机表, 对对手来说非常弱。了解或猜测它的对手可以轻易破坏基于该序列的所有安全性, 无论是未来的还是过去的 [CRC]。作为另一个例子, 使用具有恒定密钥的AES来加密连续的整数 (如1、2、3、...) 将产生也具有出色统计随机性属性但可预测的输出。另一方面, 连续掷六面骰子并以ASCII编码结果值将产生统计上较差的输出, 但具有实质性的不可预测成分。因此请注意, 通过或未通过统计测试并不能揭示某物是不可预测的还是可预测的。