*k33???1?3?3M33?1717?-51mod26=1

211823?mod26?

?14257??k?1??718????601??所以，

?4915????15176????24017??3－8 用Vigenere算法加密明文“We are discovered save yourself”，密钥是：deceptive。 解：密文应为：zi cvt wqngrzgvtw avzh cqyglmgj。

《应用密码学》习题和思考题答案

第4章 密码学数学引论

4－1 编写一个程序找出100~200间的素数。 略

4－2 计算下列数值：7503mod81、(－7503)mod81、81mod7503、(－81)mod7503。 解：7503mod81＝51 (－7503)mod81＝30 81mod7503＝81 (－81)mod7503＝7422

4－3 证明：（1）?a(modm)?b(modm)?modm?(a?b)(modm)

（2）?a?(b?c)?modm??(a?b)(modm)?(a?c)(modm)?(modm)

证明：

（1）设a(modm)?ra，b(modm)?rb，则a?ra?jm（j为某一整数），b?rb?km（k为某一整数）。于是有：

?a(modm)?b(modm)?modm?(rarb)(modm)

(a?b)(modm)??ra?jm??rb?km??modm???rarb?rakm?rbjm?kjm2??modm???rarb??modm?于是有：?a(modm)?b(modm)?modm?(a?b)(modm)

（2）设a(modm)?ra，b(modm)?rb，c(modm)?rc，则a?ra?j，m（j为某一整数）

b?rb?km（k为某一整数），c?rc?im（i为某一整数）。于是有：

?a?(b?c)?modm????rb?km???rc?im??????ra?jm???(modm)????ra?jm??rb?km?rc?im???(modm)??rarb?raim?rakm?rarc?rbjm?kjm?rcjm?ijm?modm22

??rarb?rarc?modm?(a?b)(modm)?(a?c)(modm)?(modm)????ra?jm??rb?km?modm??ra?jm??rc?im?modm???modm? ??rarb?rarc?modm于是有：?a?(b?c)?modm??(a?b)(modm)?(a?c)(modm)?(modm)

4－4 编写一个程序，用扩展的欧几里德算法求gcd(4655,12075)和550mod1723。 略。

4－5 求25的所有本原元。

解：25的所有本原元是：2, 3, 8, 12, 13, 17, 22, 23。 4－6 求Z5中各非零元素的乘法逆元。

解：Z5中各非零元素分别为1、2、3、4，它们的乘法逆元（mod5）分别是：1、3、2、4。 4－7 求?(100)。

222?12?1解：??100???2?5???2?2?1?????5?5?1????40

－1

??4－8 利用中国剩余定理求解：

?x?2(mod3)??x?1(mod5) ?x?1(mod7)?解： M = 3×5×7 = 105; M/3 = 35; M/5 = 21; M/7 = 15。

35b1＝1 (mod 3) 21b2＝ 1 (mod 5) 15b3＝1 (mod 7)

因此有： b1 = 2; b2 = 1; b3 = 1。

则：x ＝2×2×35 + 1×1×21 + 1×1×15＝176 (mod 105)＝71

4－9 解释：群、交换群、有限群、有限群的阶、循环群、生成元、域、有限域、不可约多项式。

答：群由一个非空集合G组成，在集合G中定义了一个二元运算符“· ”，满足： (1) 封闭性：对任意的a,b?G，有：a?b?G；

(2) 结合律：对任何的a,b,c?G，有：a?b?c??a?b??c?a??b?c?；

(3) 单位元：存在一个元素1?G (称为单位元)，对任意元素，有：a?1?1?a?a； (4) 逆元：对任意a?G，存在一个元素a?1?G (称为逆元)，使得：a?a?1?a?1?a?1。

如果一个群满足交换律，则称其为交换群。 如果一个群的元素是有限的，则称该群为有限群。 有限群的阶就是群中元素的个数。

如果群中每一个元素都是某一个元素a?G的幂a?G(k为整数)，则称该群是循环群。

在循环群中，认为元素a生成了群G，或a是群G的生成元。

域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”(加法)和“· ”(乘法)，并满足：

(1)F关于加法“+”是一个交换群；其单位元为“0”，a的逆元为?a。 (2) F关于乘法“· ”是一个交换群；其单位元为“1”，a的逆元为a。 (3)(分配律)对任何的a,b,c?F，有：a?(b?c)??b?c??a?a?b?a?c； (4)(无零因子)对任意的a,b?F，如果a?b?0，则a?0或b?0。 如果域F只包含有限个元素，则称其为有限域。

不可约多项式是指不能再分解为两个次数低于该多项式最高次的多项之积的多项式。 4－10 基于最优化正规基表示的GF(2)域，计算?1010?和?1101?分别等于多少？

4?1k109 解：按照最优化正规基表示的乘法计算方法，有：

?1010?10＝?1010?2??1010?8＝?0101???0101?＝?1010? ?1101?9＝?1101???1101?8＝?1101???1011?＝?0001?。

4－11 什么是计算复杂性？它在密码学中有什么意义？

答：计算复杂性理论提供了一种分析不同密码技术和算法的计算复杂性的方法，它对密码算法及技术进行比较，然后确定其安全性，是密码安全性理论的基础，涉及算法的复杂性和问题的复杂性两个方面，为密码算法的“实际上”安全提供了依据。

《应用密码学》习题和思考题答案

第5章 对称密码体制

5－1 画出分组密码算法的原理框图，并解释其基本工作原理。 答：

m?(m0,m,mL?1)1,m2,?明文分组加密算法c?(c0,c1,c2,?,cL?1)密文分组解密算法m?(m0,m,mL?1)1,m2,?明文分组k?(k0,k1,k2,?,kt?1)k?(k0,k1,k2,?,kt?1)图5-1 分组密码原理框图

分组密码处理的单位是一组明文，即将明文消息编码后的数字序列m0,m1,m2,?,miL的分组分别在密钥划分成长为L位的组m??m,,Lm0,m1,m2???1,各个长为

k??k0,k1,k2,?,kt?1?（密钥长为t）的控制下变换成与明文组等长的一组密文输出数字序

列c??c0,c1,c2,?,cL?1?。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密码结构的实现依赖的主要参数有哪些？ 答：