内容发布更新时间 : 2024/9/21 13:55:24星期一 下面是文章的全部内容请认真阅读。

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

第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?kjm??rarb??modm?2??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????ra?jm????rb?km???rc?im????(modm)?????ra?jm??rb?km?rc?im???(modm)??rarb?raim?rakm?rarc?rbjm?kjm?rcjm?ijm22?modm

??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)。 解：??100????2?522－1

???????2?2?1???5?5?1???40

2?12?14－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?1k。

(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)域，计算?10104?10和?1101?9分别等于多少？

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

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

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

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