英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
作为Blum-Blum-Shub伪随机生成器的应用之一的基于密码的密钥派生函数
Y.D. Vybornov
萨马拉国立研究大学，俄罗斯萨马拉摩斯科夫斯基街34号，邮编：443086
摘要
研究的主要目的是分析密码安全软件Blum-Blum-Shub伪随机数生成器在不同身份验证和加密任务中的实际适用性。结果表明，该伪随机序列发生器具有较高的计算复杂度，可以有效地应用于密钥生成率较低的加密任务中。提出了一种基于密码的密钥派生函数的实现方法，该方法是基于将Blum-Blum-Shub生成器作为伪随机函数来实现的。该算法可以降低字典速度和暴力攻击。实验研究表明，该算法可以自适应地调整为特定的认证和加密任务生成密钥的保证最小时间。
2017年作者编写，由爱思唯尔有限公司出版。
由第三届国际会议“信息技术与纳米技术”科学委员会负责的同行评审。
关键词：基于密码的密钥派生函数;PBKDF; 加密密钥; 伪随机序列; 不可预测的伪随机数发生器; 密码安全发生器; Blum-Blum-Shub发生器; 暴力攻击; 数据保护; 信息安全
1.介绍
在密码学中，伪随机序列生成器是一种允许从小的初始化值快速生成长位序列的算法。 这个序列生成器应该给人的印象是它的结果是由两面的硬币连续翻转决定的。当然，证明这种非确定性行为的快速确定性机制的想法似乎是矛盾的：通过长期观察序列生成器的输出，我们原则上可以逐渐认识到其确定性，并再次复制这种序列生成器。
通常，为了解决这个问题，对这种发生器只有一个要求：获得的序列应该通过某些标准的统计测试（例如，在足够长的输出序列中，零和一的出现频率应该几乎相同，零和一应该完全“混合”）。
但是，对于认证和加密任务，除了通过标准统计测试之外，对于真正的计算机，伪随机序列应该是不可预测的。这意味着伪随机序列生成器具有不可预测性的多项式估计（向右和向左），如果且仅当所生成序列的每个有限初始片段的一个元素（最右或最左）被删除，概率图灵机无法在多项式时间内预测概率大于0.5的缺失元素。生成器的可预测性意味着对于给定的小序列片段，可以快速地对初始化值进行假设，并在两个方向上合理地继续生成该片段。
左右不可预测的特性提供了对统计攻击的保护，这些攻击分为两个子类：
（1）加密伽玛统计特性的密码分析，旨在研究密码系统的输出序列：通过各种统计测试，密码学分析人员试图确定概率高于随机选择概率的序列下一位的值；
（2）序列复杂性的密码分析：密码分析者尝试生成类似于伽玛的序列，但更容易实现。
然而，对于现代伪随机序列发生器，另一个重要的要求是高比特生成速率。 由于其高计算复杂性，本文所研究的发生器速度较慢，但在许多任务中，这一缺点会成为一个优点。
2.Blum-Blum-Shub生成器
mod生成器从小的初始化值产生长的良好分布的序列。 它的核心问题是二次剩余问题。
设N={整数N|N=P*Q，其中P和Q是等长质数（|P|=|Q|），Pequiv;3（mod 4）且Qequiv;3（mod 4）作为一组参数值
设={整数 x|0lt;xlt;N且gcd（x,n）=1}。对于Nisin;N,设XN={x2 mod N|xisin;}是一组二次剩余模N。让不相交的组合X=成为种子域。
设（N,x）isin;Xn,让mu;n(N,x)=，其中是均匀概率分布{Nisin;N||N|=n},且是一个均匀分布。这样{mu;n}就是一个可得概率分布X只要满足：
1）渐近地，1/（k ln2）中的所有k位数中的k都是素数，任何长度的一半素数都与3模4一致（根据valle-poussin素数定理）；
2）初等性检验可通过概率算法（蒙特卡罗）在多项式时间内求解，例如solovay-strassen检验、rabin检验或miller确定性多项式检验；
3）最大公因子可在多项式时间内计算，并且。
设转换关系T：X→X被定义为。转换关系T是在多项式时间内可计算的置换。设B:X→{0,1}被定义为,B是可计算的多项式时间。然后（X,T,B）定义伪随机序列发生器（基数2），称为mod发生器。因此，对于输入（N,X0），modN发生器通过设置并提取位，形成一个位hellip;的伪随机序列等同于奇偶校验位()。
通常，这种序列是周期性的，周期等于lambda;(),其中，被称为Carmichael函数。该发生器的另一个吸引人的特性是当知道N的因式分解时，它可以直接确定地提供单个位。等式
中，如果，和给出，则可以计算出igt;0时的的序列元素。当ilt;0时，可以运用以下公式：
不可预测性和密码安全性的主要结果来源于用概率多项式算法对数论中某些问题的不可解性的假设。
mod发生器基于二次剩余假设，让n是两个不同的奇数素数的乘积。中恰好有一半的元素的Jacobi符号等于 1，另一半元素的Jacobi符号等于-1。分别把它们表示为和。在中没有二次剩余，刚好中有一般的元素是二次剩余。参数和x的二次残差问题是从中的x是否是二次残差决定的，假设任何确定输入元素是否为二次余数的有效算法都是错误的。
今天，大整数因式分解的最快算法是普通数域筛选法。假设的因式分解是困难的，那么mod发生器有一个左不可预测的多项式估计。
从Yao定理中可以得出，基于二次剩余问题的mod发生器产生的序列通过了所有概率多项式时间统计检验（即，没有一个统计检验可以将这些序列与poly（n）中时间超过无限小的连续“硬币翻转”生成的序列区分开来。）
1986年，Lenore Blum、Manuel Blum和Michael Shub为mod发生器的加密安全性提供了数学依据，并发布了一种现在称为Blum-Blum-Shub发生器器的算法。该算法生成一个长度为,各位为的伪随机序列：
（1）首先，选取两个足够大的秘密随机（和不同的）素数P和Q，每个都与3个模4一致；
（2）然后，计算；
（3）在这之后，从区间[1，N-1]中选择一个随机整数s（seed），n这样使得gcd（s，N）=1；
（4）然后，计算；
（5）设，执行以下转换：
i. ;
ii.。
（6）在这之后，从区间[1，N-1]中选择一个随机整数s（seed），这样使得gcd(s,N)=1。
下面列举一个算法执行的例子。
（1）最初，我们选择两个质数P=47 和Q=67，这两个数都与3 modulo 4一致，即47mod4=3和67mod4=3；
（2）现在，N=47*67=3149；
（3）下一步，我们选取sdde s=7,gcd(7,3149)=1；
（4）现在，；
（5）然后，我们在1到16中循环运行并计算和；
（6）运行后，得到16位的序列结果：1110101011010010。
在研究了Blum-Blum-Shub发生器的不同实现的平均速度，并且得出结论，该发生器由于其低速而具有有限的应用领域。 Blum-Blum-Shub发生器的平均速度比现代对称分组密码的平均速度低许多倍。例如，AES算法的平均速度为2.5 Gb / s，Twofish算法——415 Mb / s，Serpent算法——255 Mb / s，而Blum-Blum-Shub生成器的平均速度（即最快的实现之一）是23 kb / s。因此，该生成器不能用作伽马生成器，但可以应用于需要不可预测性和加密安全性的系统和协议中的数据生成，而生成速率不是那么重要（例如，用于在非对称系统中生成密钥，例如RSA;用于生成消息身份验证代码或其密钥;以及用于身份验证和加密的其他一些加密协议）。
但是，值得注意的是，低速并不总是一个缺点。在密码学的一些任务中，故意使用慢速算法，其中一个任务是基于密码的密钥派生。
3.基于密码的密钥派生
3.1基于密码的密钥派生函数
密码或密码短语是访问系统时用于对用户进行身份验证的字符串。通常，密码是由用户选择的。由于大多数用户选择的密码不够随机，且具有低熵，因此不建议将它们直接用作加密密钥。
基于密码的密钥派生函数（PBKDF）是一种确定性算法，用于从某个秘密值生成密钥材料。因此，此函数允许从易于记忆的密码派生给定长度的加密密钥，称为主密钥。
主密钥用于生成数据保护密钥。 数据保护密钥是用于数据保护或恢复，数据真实性和完整性验证以及用于生成数字签名的私钥的保护的密钥或密钥集。 数据保护密钥可以通过两种方式从主密钥导出：直接使用主密钥（或其片段）作为数据保护密钥，或者使用密钥派生函数。 密钥导出函数是生成密钥材料的函数（二进制字符串，使得其所需长度的非重叠片段可用作对称密码密钥）。 此外，主密钥可用于保护现有的随机生成的数据保护密钥。
PBKDF由伪随机函数PRF和迭代计数C（指示伪随机函数被调用的次数的固定值）定义。 该算法需要以下一组输入：password P ,salt S（每个密码唯一的非秘密二进制字符串），以及主密钥的所需长度。因此，主密钥MK可以定义如下：
基于密码的密钥派生的一般方案如图1所示
图1 基于密码的密钥推导的一般方案
字典攻击的目的是通过尝试存储在专门创建的词典中的最流行的密码来获取访问权限。 使用包含大写和小写字母以及数值的随机组合的密码时，此类型的攻击不太可能成功。 这种密码可以通过实施暴力攻击来恢复，即通过尝试所有可能的字符组合。 这种破解密码的方法被认为是最低效的。
PBKDF的主要思想是通过增加攻击者每次尝试寻找正确密码所需的时间来减缓字典和强力攻击。此外，使用独特的salt使得攻击者无法实施彩虹表攻击。
虽然salt值不是保密的，但是在这个算法中使用salt密码是必要的。假设键是从用户密码中导出的，而不添加唯一的随机盐。我们还假设攻击者评估了密钥派生算法，并生成了一个结果密钥表（彩虹表）。然后，如果攻击者能够访问结果密钥的数据库，他可以使用计算出的彩虹表轻松确定用户密码。
即使在注册过程中有多个用户输入相同的密码，结果数据库中的键值也会不同（因为salt对于每个用户都是唯一的），攻击者也无法猜测用户拥有相同的密码。
现在考虑另一种情况。攻击者无法访问生成的密钥的数据库，并试图通过实施暴力或字典攻击来获取用户密码。当然，如果攻击者以某种方式访问salt值，那么他可能能够恢复特定用户的密码。但是，要确定所有用户的密码将更加困难：由于每个用户的salt都是唯一的，因此攻击者必须对每个用户执行单独的搜索。因此，salt不保护单独的密码免受暴力/字典攻击，但它提供了一个机会，防止攻击者在一次通过中恢复所有用户密码。
因此，salt的主要目的是使从每个密码中生成一组大的密钥，以获得迭代计数的固定值。对于每个密码，可能的键的数量大约是，其中Salt _length是salt的一个位长度。因此，在字典攻击的情况下，使用salt会使攻击者更难生成这样的字典，即使对于一个小组最可能的密码也是如此，而在彩虹表攻击的情况下，使用salt也会使生成结果键表变得不可能。
迭代计数的主要目的是增加密钥派生所需的计算数量，从而显著增加攻击实现的复杂性。因此，对于PBKDF running C迭代来获得密钥，使用t位熵对密码进行字典攻击的计算复杂度从操作增加到操作。
但是，值得注意的是，对于合法用户，密钥推导所需的计算次数也随着迭代次数而增加。 例如，用户可能注意到认证时间的增加，或者访问受保护数据的时间。 因此，迭代计数的增加不仅影响成功攻击的概率，而且影响合法用户的性能。 因此，迭代次数应该非常大，但它应该保持系统的可接受性能（可接受的性能可以根据特定的PBKDF应用程序而变化）。
PBKDF最明显的应用是加密密钥生成。
例如，使用数据保护密钥（从主密钥派生），您可以加密硬盘或可移动介质上的卷。 用于创建加密逻辑磁盘的最着名的软件程序是TrueCrypt和BitLocker。
为了加密数据，用户应首先输入所需长度的密码。 然后，使用PBKDF生成加密密钥。 之后，执行数据加密。 在多个用户在同一台计算机上工作的情况下，每个用户都会创建自己的虚拟磁盘并对其进行加密。
为了访问加密数据，用户输入加密期间指定的密码。 此后，使用PBKDF，生成解密密钥（与加密密钥相同）。 如果密码正确，则数据将被准确解密。 否则，数据将被不正确地解密。
如果数据大小很大，那么为了在不解密存储介质上的整个数据的情况下检查密码是否正确，可以在加密之前将前缀添加到明文。 使用此方法时，通过仅解密包含前缀的密文片段并将结果与前缀的预期值进行比较来检查密码。
设置新密码会导致更改相关的数据保护密钥。 因此，每当更改密码时，必须使用与旧密码相关联的适当数据保护密钥对由旧密码保护的任何数据进行解密，然后使用与新密码相关联的适当数据保护密钥进行加密。
3.2 用于基于密码的密钥派生的Blum-Blum-Shub生成器
为了证明伪随机数发生器的低速可能是有用的，我们开发了PBKDF，其中Blum-Blum-Shub发生器（以下称为BBS）用作伪随机函数。
所开发算法的输入和输出参数在表1中给出。
表1 算法的输入和输出参数
|
输入 |
|
|
P S C 虚拟比特数 真比特数 |
密码 Salt 迭代次数 主密钥所需的长度 BBS输出的虚拟位数 BBS输出的真实位 全文共8557字，剩余内容已隐藏，支付完成后下载完整资料 资料编号：[2809] |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
