密码学(5)

习题五
1. 什么是篡改检测码（MDC）？MDC 是如何产生和怎样使用的？消息认证码（MAC）
是MDC 吗？（消息的）数字签名是MDC 吗？
2. 什么是随机预言机？随机预言机存在吗？随机预言机的行为是如何逼近现实世界的？
3. 设杂凑函数的输出空间大小为2160，找到该杂凑函数碰撞所的花费时间期望值是什么？
4. 为什么说杂凑函数实际上是不可逆的？
5. 对称和非对称数据完整性技术的主要区别是什么？
6. “来自Malice 的数据完整性”安全性概念？
7. RSA-OAEP 算法的密文输出是一个有效的MDC 吗？
8. 设f: {0, 1}*→{0, 1}*为一保长单向函数，证明g(x) =f(x)⊕x也是单向函数。

9. 设 f(x)，g(x)都是单向函数，问f(x)+g(x)，f(x)g(x), f(g(x)) 是否都是单向函数？指出哪
个是？哪个不是？并给出直观说明。

《应用密码学》习题和思考题答案第5章 对称密码体制5－1 画出分组密码算法的原理框图，并解释其基本工作原理。

答：图5-1 分组密码原理框图1210-t 1210-t )分组密码处理的单位是一组明文，即将明文消息编码后的数字序列im m m m ,,,,210 划分成长为L 位的组()0121,,,,L m m m m m -=,各个长为L 的分组分别在密钥()0121,,,,t k k k k k -= （密钥长为t ）的控制下变换成与明文组等长的一组密文输出数字序列()0121,,,,L c c c c c -= 。

L 通常为64或128。

解密过程是加密的逆过程。

5－2 为了保证分组密码算法的安全强度，对分组密码算法的要求有哪些？ 答：（1）分组长度足够大；（2）密钥量足够大；（3）密码变换足够复杂。

5－3 什么是SP 网络？答：SP 网络就是由多重S 变换和P 变换组合成的变换网络，即迭代密码，它是乘积密码的一种，由Shannon 提出。

其基本操作是S 变换（代替）和P 变换（换位），前者称为S 盒，后者被称为P 盒。

S 盒的作用是起到混乱作用，P 盒的作用是起到扩散的作用。

5－4 什么是雪崩效应？答：雪崩效应是指输入（明文或密钥）即使只有很小的变化，也会导致输出发生巨大变化的现象。

即明文的一个比特的变化应该引起密文许多比特的改变。

5－5 什么是Feistel 密码结构？Feistel 密码结构的实现依赖的主要参数有哪些？ 答：1K nK i密文明文图5－6　Feistel密码结构Feistel 密码结构如图5－6所示。

加密算法的输入是长为2w 位的明文和密钥K ，明文被均分为长度为w 位的0L 和0R 两部分。

这两部分经过n 轮迭代后交换位置组合在一起成为密文。

其运算逻辑关系为：1(1,2,,)i i L R i n -==11(,)(1,2,,)i i i i R L F R K i n --=⊕=每轮迭代都有相同的结构。

密码学笔记（5）——Rabin密码体制和语义安全性⼀、Rabin密码体制 Rabin密码体制是RSA密码体制的⼀种，假定模数n=pq不能被分解，该类体制对于选择明⽂攻击是计算安全的。

因此，Rabin密码体制提供了⼀个可证明安全的密码体制的例⼦：假定分解整数问题是整数上不可⾏的，那么Rabin密码体制是安全的。

Thm1 (Rabin密码体制)设n=pq，其中p和q是素数，且p,q \equiv 3 (mod \, 4)，设P=C=Z^{\star}_{n}，且定义\kappa =\{(n,p,q)\}对K=(n,p,q)，定义e_{K}(x)=x^{2} (mod \, n)和d_{K}=\sqrt{y} (mod \, n)n为公钥，p和q为私钥。

注：条件p,q \equiv 3 (mod \, 4)可以省去，条件P=C=Z^n_{\star}也可以弱化为P=C=Z^n，只是在使⽤更多的限制性描述的时候，简化了许多⽅⾯的计算和密码体制分析。

注意看到这个函数y=x^{2}对于加密来说不是⼀个单射，所以解密不能以⼀种明显的⽅式完成，特别的，对于y \equiv x^{2} (mod \, n)，对于某⼀个x \in Z^{\star}_{n}，存在y模n的是个解，除⾮有其他的冗余信息，否则⽆法确认是那⼀个值。

从Bob的观点来看解密问题，它有⼀个密⽂y，要想得到x使得x^2 \equiv y(mod \, n)这是⼀个关于Z_{n}中未知元x的⼆次⽅程，解密需要求出模n的平⽅根，等价于求解以下两个同余⽅程。

z^{2} \equiv y (mod \, p)z^{2} \equiv y (mod \, q)虽然我们可以利⽤Euler准则来判断y是否为⼀个模p或模q的⼆次剩余。

事实上，如果加密正确的执⾏，y是⼀个模p和模q的⼆次剩余，遗憾的是它并不能帮助我们找到y。

当p \equiv 3(mod \, 4)时，有⼀个简单公式来计算模p的⼆次剩余的平⽅根，假定y是⼀个模p的⼆次剩余，且y \equiv 3 (mod \, 4)那么有\begin{align} (\pm y^{\frac {p+1}{4}})^{2} \equiv & y^{\frac{p+1}{2}} (mod \, p) \\ \equiv & y^{\frac{p-1}{2}}y (mod \, p) \\ \equiv & y(mod \, p) \\ \end{align}这⾥⼜⼀次使⽤了Euler准则，即当y是⼀个模p的⼆次剩余时，有y^{\frac{p-1}{2}} \equiv 1 (mod \, p)，因此，y模p的两个平⽅根为\pm y^{\frac{p+1}{4}} (mod \, p)，同样的讨论可以知道，y模q的两个平⽅根为\pm y^{\frac{p+1}{4}} (mod \, q)，再利⽤中国剩余定理可以得到y模n的四个平⽅根。

《应用密码学》习题和思考题答案第5章 对称密码体制5－1 画出分组密码算法的原理框图，并解释其基本工作原理。

答：图5-1 分组密码原理框图1210-t 1210-t )分组密码处理的单位是一组明文，即将明文消息编码后的数字序列im m m m ,,,,210 划分成长为L 位的组()0121,,,,L m m m m m -=,各个长为L 的分组分别在密钥()0121,,,,t k k k k k -= （密钥长为t ）的控制下变换成与明文组等长的一组密文输出数字序列()0121,,,,L c c c c c -= 。

L 通常为64或128。

解密过程是加密的逆过程。

5－2 为了保证分组密码算法的安全强度，对分组密码算法的要求有哪些？ 答：（1）分组长度足够大；（2）密钥量足够大；（3）密码变换足够复杂。

5－3 什么是SP 网络？答：SP 网络就是由多重S 变换和P 变换组合成的变换网络，即迭代密码，它是乘积密码的一种，由Shannon 提出。

其基本操作是S 变换（代替）和P 变换（换位），前者称为S 盒，后者被称为P 盒。

S 盒的作用是起到混乱作用，P 盒的作用是起到扩散的作用。

5－4 什么是雪崩效应？答：雪崩效应是指输入（明文或密钥）即使只有很小的变化，也会导致输出发生巨大变化的现象。

即明文的一个比特的变化应该引起密文许多比特的改变。

5－5 什么是Feistel 密码结构？Feistel 密码结构的实现依赖的主要参数有哪些？ 答：1K nK i密文明文图5－6　Feistel密码结构Feistel 密码结构如图5－6所示。

加密算法的输入是长为2w 位的明文和密钥K ，明文被均分为长度为w 位的0L 和0R 两部分。

这两部分经过n 轮迭代后交换位置组合在一起成为密文。

其运算逻辑关系为：1(1,2,,)i i L R i n -==11(,)(1,2,,)i i i i R L F R K i n --=⊕=每轮迭代都有相同的结构。

密码学中五个专用术语在密码学领域，这五个专用术语是极其基础且关键的概念，它们分别是：1. 明文（Message或Plaintext）：这是需要被保护和隐藏的数据，可能是比特流、文本文件、位图、数字化的语音流，或者数字化的视频、图像等。

明文是未进行加密或隐藏处理的数据形式，是加密算法的输入。

2. 密文（Cipher）：这是经过加密处理后的数据形式，也是二进制数据。

密文和明文一样大，有时甚至稍大一些。

然而，通过压缩和加密的结合，密文可能比明文小些。

密文是加密算法的输出，也是解密算法的输入。

3. 密钥（Key）：这是加密函数和解密函数的输入参数。

密钥可以是很多数值里的任意值，其取值范围叫作密钥空间。

密钥空间必须大到足以抵抗暴力攻击。

用于加密的密钥称为加密密钥，用于解密的密钥称为解密密钥。

4. 选择明文攻击（chosen-plaintext attack）：这是一种攻击方式，分析者不仅可得到一些消息的密文和相应的明文，而且他们也可以选择被加密的明文。

这种攻击方式给攻击者提供了更大的灵活性，使他们能够选择特定的明文进行加密和分析，从而获取更多的信息。

5. 自适应选择明文攻击（adaptive-chosen-plaintext attack）：这是选择明文攻击的特殊情况。

分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。

这种攻击方式进一步增强了攻击者的能力，使他们能够根据先前的加密结果调整自己的选择，从而更有效地获取信息。

这些术语构成了密码学的基础概念，对于理解加密算法和安全协议的设计和实施至关重要。

它们之间的相互关系和作用构成了密码学的基础，并影响了我们如何设计和评估一个安全系统的能力。

实验报告一、实验目的1.MD5算法（1）理解Hash函数的计算原理和特点（2）理解MD5算法原理2.SHA1算法（1）理解SHA1函数的计算原理和特点（2）理解SHA1算法原理二、实验内容与设计思想①MD5算法MD5哈希算法流程：1.对于任意长度的明文，MD5首先对其进行分组，使得每一组的长度为512位，然后对这些明文分组反复重复处理。

对于每个明文分组的摘要生成过程如下：（1）将512位的明文分组划分为16个子明文分组，每个子明文分组为32位。

（2）申请4个32位的链接变量，记为A、B、C、D。

（3）子明文分组与链接变量进行第1轮运算。

（4）子明文分组与链接变量进行第2轮运算。

（5）子明文分组与链接变量进行第3轮运算。

（6）子明文分组与链接变量进行第4轮运算。

（7）链接变量与初始链接变量进行求和运算。

（8）链接变量作为下一个明文分组的输入重复进行以上操作。

（9）最后，4个链接变量里面的数据就是MD5摘要。

2.MD5分组过程对于任意长度的明文，MD5可以产生128位的摘要。

任意长度的明文首先需要添加位数，使明文总长度为448（mod512）位。

在明文后添加位的方法是第一个添加位是l，其余都是0。

然后将真正明文的长度（没有添加位以前的明文长度）以64位表示，附加于前面已添加过位的明文后，此时的明文长度正好是512位的倍数。

当明文长度大于2的64次方时，仅仅使用低64位比特填充，附加到最后一个分组的末尾。

经过添加处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组（block），可以划分成L份明文分组，我们用Y0，Y1，……，YL-1表示这些明文分组。

对于每一个明文分组，都要重复反复的处理，如图所示。

3.MD5子明文分组和链接变量对于512位的明文分组，MD5将其再分成16份子明文分组（sub-block），每份子明文分组为32位，我们使用M[k]（k= 0, 1,……15）来表示这16份子明文分组。

2.4 已知下面的密文由单表代换算法产生：请将它破译。

提示：1、正如你所知，英文中最常见的字母是e。

因此，密文第一个或第二个（或许第三个）出现频率最高的字符应该代表e。

此外，e经常成对出现（如meet,fleet,speed,seen,been,agree,等等）。

找出代表e的字符，并首先将它译出来。

2、英文中最常见的单词是“the”。

利用这个事实猜出什么字母t和h。

3、根据已经得到的结果破译其他部分。

解：由题意分析：“8”出现次数最多，对应明文为“e”，“；48”代表的明文为“the”，“）”、“*”、“5”出现频率都比较高，分别对应“s”、“n”、“a”，由此破译出密文对应的明文为： A good glass in the Bishop’s hostel in the Devil’s seat-twenty-one degrees and thirteen minutes-northeast and by north-main branch seventh limb east side-shoot from the left eye of the death’s head-a bee line from the tree through the shot fifty feet out.2.20 在多罗的怪诞小说中，有一个故事是这样的：地主彼得遇到了下图所示的消息，他找到了密钥，是一段整数：11234a.破译这段消息。

提示：最大的整数是什么？b.如果只知道算法而不知道密钥，这种加密方案的安全性怎么样？c.如果只知道密钥而不知道算法，这种加密方案的安全性又怎么样？解：A.根据提示，将密文排成每行8字母的矩阵，密钥代表矩阵中每行应取的字母，依次取相应字母即可得明文。

明文为：He sitteth between the cherubims.The isles may be glad thereof.As the rivers in the South.B.安全性很好。

4.6习题一.判断题1~5二.选择题1~5 ACBDE6~10 BCA三.填空题1. vernam算法2.驱动部分组合部分3.如何将一小段的比特串（密钥）扩展成足够长的密钥4.同步和自同步5. 移位寄存器反馈函数6.参数n 种子密钥7.2的n次方减1 n8.奇数互素本原的四.简答题（1）简述序列密码算法和分组密码算法的不同。

（2）密钥序列生成器是序列密码算法的核心，请说出至少5点关于密钥序列生成器的基本要求。

①种子密钥K的长度足够大，一般应在128位以上；②KG生成的密钥序列｛ki｝具极大周期；③｛ki｝具有均匀的n元分布；④利用统计分析方法由｛ki｝提取关于KG结构或K的信息在计算上不可行；⑤混乱性，即｛ki｝的每一比特位均与K的大多数比特有关；⑥扩散性，即K 的任一比特的改变要引起｛ki ｝在全貌上的变化；⑦序列密钥｛ki ｝不可预测，密文和相应明文的部分信息，不能确定整个｛ki ｝。

（3）已知序列密码的密文串1010110110和相应的明文串010*******，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。

解：由()12341423,,,1f a a a a a a a a =⊕⊕⊕，初态为 ()()1234,,,1,1,0,1a a a a =。

线性递归可得：511101a =⊕⊕⊕=611101a =⊕⊕⊕=701111a =⊕⊕⊕=811110a =⊕⊕⊕=910111a =⊕⊕⊕=1011101a =⊕⊕⊕=可以得到输出序列为()1101111011，周期为5p =。

（4）简述RC4算法的实现过程。

RC4算法的原理很简单，包括初始化算法和伪随机子密码生成算法两大部分。

假设S-box 长度和密钥长度均为n 。

先来看看算法的初始化部分（用类C 伪代码表示）：for (i=0; i<n; i++) {s[i]=i;}j=0;for (i=0; i<n; i++){j=(j+s[i]+k[i])%n;swap(s[i], s[j]);}在初始化的过程中，密钥的主要功能是将S-box搅乱，i 确保S-box的每个元素都得到处理，j保证S-box的搅乱是随机的。

密码学第五版部分课后答案已知下面的密文单表代换算法产生：请将它破译。

提示：1、正如你所知，英文中最常见的字母是e。

因此，密文第一个或第二个出现频率最高的字符应该代表e。

此外，e 经常成对出现。

找出代表e的字符，并首先将它译出来。

2、英文中最常见的单词是“the”。

利用这个事实猜出什么字母t和h。

3、根据已经得到的结果破译其他部分。

解：题意分析：“8”出现次数最多，对应明文为“e”，“；48”代表的明文为“the”，“）”、“*”、“5”出现频率都比较高，分别对应“s”、“n”、“a”，此破译出密文对应的明文为： A good glass in the Bishop’s hostel in the Devil’s seat-twenty-one degrees and thirteen minutes-northeast and by north-main branch seventh limb east side-shoot from the left eye of the death’s head-a bee line from the tree through the shot fifty feet out.在多罗的怪诞小说中，有一个故事是这样的：地主彼得遇到了下图所示的消息，他找到了密钥，是一段整数：7876565434321123434565678788787656543432112343456567878878765654343211234 a.破译这段消息。

提示：最大的整数是什么？b.如果只知道算法而不知道密钥，这种加密方案的安全性怎么样？c.如果只知道密钥而不知道算法，这种加密方案的安全性又怎么样？解：A.根据提示，将密文排成每行8字母的矩阵，密钥代表矩阵中每行应取的字母，依次取相应字母即可得明文。

明文为：He sitteth between the isles may be glad the rivers in the South.B.安全性很好。