随机数（random numbers）有丰富的密码学应用

1?? 在认证协议中，有三种方法可以抵抗重放攻击：序列号、时间戳、随机数挑战响应

2?? 会话密钥(尽量少重复)

3?? 公钥生成

4?? 一次密码流

在任何情况下，其值都应严格遵循以下特征

满足随机性（random），一致传播（uniform distribution），独立（independent）

不可预测性

下图把一个真随机数生成器TRNG两个伪随机数生成器PRNG、PRF对比。

伪随机数生成器 Pseudorandom Number Generators (PRNGs)

确定性算法技术通常用于生成随机数

虽然不是真正的随机

但是可以通过各种随机性测试

被称为“伪随机数”；通过“伪随机数生成器”生成

PRNG的要求

随机性：均匀性；可伸缩性；一致性

不可预测性：正向不可预测的反向不可预测

种子要求：不可预测，应为随机或伪随机数

该方案的随机数序列采用以下迭代技术生成 X n 1 = ( a X n c ) mod m X_{n 1}=(aX_n c)\ \text{mod}\ m Xn 1=(aXn​+c) mod m 通过给定相应的参数可以获得像随机（random-like）的数（通常m较大，是一个接近或等于2³¹的数

评价一个随机数生成器的准则：

这个函数应当是一个完整周期的生成函数、

产生的序列应当是看上去随机的（a=7⁵=16807)

这个函数应当采用32bit算术高效实现

攻击者可以通过获取少量的值重构序列（比如同余方程）

可复杂化：修改m（比如将其与系统时钟联系）

基于公钥密码算法

在密码学应用当中，可以采用块加密器（block cipher）生成随机数

常用来从主密钥（长期保存的密钥）（master key 生成会话密钥（真正用的密钥））

1️⃣ 计数器模式（Counter Mode）——CTR X i = E k m [ i ] X_i=E_{km}[i] Xi​=Ekm​[i]

2️⃣ 输出反馈模式（Output Feedback Mode）——OFB X i = E k m [ X i − 1 ] X_i=E_{km}[X_{i-1}] Xi​=Ekm​[Xi−1​]

最好的资源是真实世界中的自然随机

寻找经常性的与随机性的事件并进行监控

常常需要特别的设备以完成：比如，辐射计数器，电磁噪声，音频噪声，二极管热噪声等等

比较新的cpu中包含了这样的组件

信号的非平坦

在采样与使用时需要进行补偿

最好每次采样仅用若干噪音比特

一个典型的流密码每次加密一个字节的明文，当然流密码也可被设计为每次操作一位或者大于一字节的单元。下图给出了一个典型的流密码的结构图。在该结构中密钥输入到一个伪随机数（位）发生器，该伪随机数生成器产生一串随机的8位数。生成器的输出称为密钥流，密钥流和明文流的每一个字节进行按位异或运算，得到一个密文字节。

例如，如果发生器产生的下一字节为01101100，而下一明文字节为11001100，则得出的密文字节为 11001100 明 文 ⊕   01101100 ‾ 密 钥 流 10100000 密 文 \begin{aligned} &11001100 &明文\\ \oplus\ &\underline{01101100} &密钥流\\ &10100000 &密文\\ \end{aligned} ⊕ ​1100110001101100​10100000​明文密钥流密文​

解密需要使用相同的伪随机序列 10100000 密 文 ⊕   01101100 ‾ 密 钥 流 11001100 明 文 \begin{aligned} &10100000 &密文\\ \oplus\ &\underline{01101100} &密钥流\\ &11001100 &明文\\ \end{aligned} ⊕ ​1010000001101100​11001100​密文密钥流明文​

流密码类似于“一次一密”，不同的是“一次一密”使用的是真正的随机数流，而流密码使用的是伪随机数流。

设计准则应该满足：

长时期的不重复

较强的统计随机性

依赖于足够大的密钥

较大的线性复杂度

设计恰当的话能达到不亚于块加密的效果

简便高速

Ron Rivest设计，简单高效

可变密钥长度，面向字节的

广泛应用（ssl，wep）

密钥构成对8比特数据的置换

每次一个字节将报文进行置换乱排

作业题。

/*初始化*/
for i = 0 to 255 do
	S[i] = i
	T[i] = K[i mod keylen]；

/*S的初始置换*/
j = 0
for i = 0 to 255 do 
	j = (j + S[i] + T[i]) (mod 256) 
	swap (S[i], S[j])

/*密钥流的生成*/
i = j = 0 
while(true)
	i = (i + 1) (mod 256)
	j = (j + S[i]) (mod 256)
	swap(S[i], S[j])
	t = (S[i] + S[j]) (mod 256) 
	k=S[t];

对已知攻击方式抵御较好

很好的非线性

不可重用密钥

WEP的应用问题

基于反馈移位寄存器（FSR）的流密码表现得性能非常适用于紧凑的硬件实现。

FSR由一系列1位存储单元构成。每个单元有一条输出线和一条输入线，其中输出线指示当前存储的值。在离散时刻（时钟时间），每个存储设备中的值被替换为输入线指示的值。结果如下：最右（最低有效）位被移出，作为该时钟周期的输出位，其它位右移一位。然后根据FSR种的其它位重新计算最左（最高有效位）

若f(x+y)=f(x)+f(y)且af(x）=f(ax），则f是线性的 B n = A 1 B n − 1 A 2 B n − 2 . . . A n B 0 = ∑ i = 1 n A i B i − 1 B_n=A_1B_{n-1}A_2B_{n-2}...A_nB_0=\sum_{i=1}^nA_iB_{i-1} Bn​=A1​Bn−1​A2​Bn−2​...An​B0​=i=1∑n​Ai​Bi−1​ 要会用多项式查找生成序列 P ( X ) = 1 + A 1 X + A 2 X 2 + . . . + A n − 1 X n − 1 + A n X n = 1 + ∑ i = 1 n A i X i P(X)=1+A_1X+A_2X^2+...+A_{n-1}X^{n-1}+A_nX^n=1+\sum_{i=1}^nA_iX^i P(X)=1+A1​X+A2​X2+...+An−1​Xn−1+An​Xn=1+i=1∑n​Ai​Xi 特征多项式的性质是，取多项式的倒数后可以查找对应LDSR的生成序列

例如：1+X+X³

生成111010011…

对于NFSR，系数可以是变量

例如 B 5 = B 4 ⊕ B 3 B 2 B_5=B_4\oplus B_3B_2 B5​=B4​⊕B3​B2​等效表示为 P ( X ) = 1 + X + X 2 X 4 P(X)=1+X+X^2X^4 P(X)=1+X+X2X4

Grain是一系列硬件效率的流密码。

Grainv1的规范定义了两种流密码：

80位密钥和一个64位初始化向量（IV）

128位密钥和一个80位的IV

Grain-128a针对身份认证进行了修订和扩展

由两个移位寄存器（一个线性反馈，另一个具有非线性反馈）和一个滤波组成

哈希函数H使用变长数据分组M作为输入，生成定长结果 h = H ( M ) h=H(M) h=H(M)。这一结果称为哈希值或哈希码

密码学哈希函数要求在以下两种情况下计算上的不可行

找到一个映射为某个哈希结果的数据对象（单向性）——不可逆

找到两个映射为相同哈希结果的数据对象（抗碰撞性）

密码学哈希函数的应用：消息认证；数字签名；其他应用（密码存储）

消息认证是用来验证消息完整性的一种机制或服务

1️⃣ 保证收发的数据的一致性（保证没有修改，插入，删除或重放）。

2️⃣ 保证发送方生成的身份的真实有效

消息认证中使用Hash函数的本质如下：发送者根据待发送的消息使用该函数计算一组Hash值，然后将Hash值和消息一起发送过去。接收者收到后对于消息执行同样的Hash计算，并将结果与收到的Hash值进行对比。如果不匹配，则接收者推断出消息（当然也可能是Hash值）遭受了篡改[参见下图]。

🔑 Hash函数的运算结果必须通过安全的方式传输。因为Hash函数必须得到保护，使得如果攻击者篡改或替换消息的话，对于攻击者不能够轻易地同时对Hsh值进行修改以蒙骗接收者。这种类型的攻击如图(b)所示。该例中，Alice传输消息时附上数据的Hash值。Darth拦截了该消息，篡改或替换其中的数据，然后重新计算Hash值并附在后面。Bob收到篡改后的数据块以及新的Hash值，未能发现消息已经被篡改。为了防止该类攻击，由Alice生成的Hash值必须得到保护。——防止中间人攻击。

当哈希函数用于提供消息认证功能时，哈希函数通常称为消息摘要

1️⃣ 使用对称加密提供消息认证

**使用对称密码算法E加密消息和Hash码。**因为只有A和B共享密钥K，所以消息必然是发自A处，并且未被更改过。这里附加的Hash码提供了实现认证功能的结构。因为对于整个消息以及Hash码都使用了加密，保密性也被提供。

防止了中间人攻击。

2️⃣ 只使用对称加密算法E加密哈希函数。（不强调机密性情况下可有效降低运算开销）

适用于强调真实性>保密性：例如档案——不怕被看，怕被改

使用对称密码算法E只对Hash码进行加密。对于无须保密性的应用，这种方案减少了加解密操作的负担。

3️⃣ 只使用哈希函数实现消息认证（结合共享秘密值）

不使用加密算法，仅使用Hsh函数也能够实现消息认证。该方案假设通信双方共享相同的秘密值S。发送方A将消息M和秘密值S串联后计算其Hash值，并将得到的Hash值附在消息M后发送。因为接收方B同时掌握S,所以能够重新计算该Hash值进行验证。由于秘密值S本身并没有在信道传送，攻击者不能够对在信道上拦截的消息进行修改，进而也不能制作假消息。

message同样是使用明文传输，适用于强调真实性>保密性

4️⃣ 加密整个消息和哈希值（为上面的方案提供机密性）

通过将整个消息和Hash值加密，能够在方案©的基础上提供保密性。

同消息认证应用类似，对于Hash函数的另外一个重要应用就是数字签名。数字签名的操作与MAC相似，在进行数字签名过程中使用用户的私钥加密消息的Hash值，其他任何知道该用户公钥的人都能够**通过数字签名来验证消息的完整性。**在这种情况下，攻击者要想篡改消息，则需要知道用户的私钥。数字签名的应用比消息认证更为广泛。

数字签名有如下两种方法：

1️⃣ 使用发送方的私钥，利用公钥密码算法仅对Hash码进行加密。这种方法可提供认证：由于只有发送方可以产生加密后的Hash码，所以这种方法也提供了数字签名，事实上，这就是数字签名技术的本质所在。

2️⃣ 若既希望保证保密性又希望有数字签名，则先用发送方的私钥对Hash码加密，再用对称密码中的密钥对消息和公钥算法加密结果进行加密，这种技术比较常用。

用于生成单向口令文件

用于入侵检测与病毒扫描

构建随机函数（PRF）（用于生成对称密钥）或伪随机数生成器（RPNG）

把包文数据划分为若干n比特定长分组的B1，B2，… ，Bm 。