《应用密码学》胡向东版习题和思考题答案(1)

解： 密B E E A K F Y D J X U Q Y H Y J I Q R Y H T Y J I Q F B Q D U Y J I I K F U H C Q D 文 -1 a d d z j e x e 1 c f f b l g 2 d g g c 3 e h h 4 f i i 5 g j j 6 h k k 7 i l l h 8 j m 9 k n n 10 l o o k u p i n t h e a i r i t s a b i r d i t s a p l a n e i t s s u p e r m a n 11 m p p 12 n q q 13 o r r n 14 p s s 15 q t t 16 r u u 17 s v v 18 t w w 19 u x x 20 v y 21 w z 22 x a 23 y b 24 z c 因此，本题的解密结果应为：Look up in the air,it’s a bird, it’s a plane, it’s superman。 提示：表中最左边一列的数字表示代替变换时字母的后移位数。 技巧：由于密文的前三个字母为“BEE”，因此根据不同的移位可先观察前三位的明文结果，判断其是否是可能的明文，如果不可能，就中止当前移位，换新的移位数。

3－6 用Playfair算法加密明文“Playfair cipher was actually invented by wheatstone”，密钥是：fivestars。 解：两个“l”间插入“x”（也可插入其他字母）。

ftdmui/jagnwvrhoxebkpysclqz字母矩阵表明文 密文 明文 密文 pl qk ly kz ay bw in aw fa it ve es ir va nt ma ci as ed fk ph ok by ke er vb wh xg wa ig ea ib sa ic ts cf ct ta to rm ua wt ne pi lx hz 3－7 用Hill密码加密明文“pay more money”,密钥是：

?17175??

k??211821????2219??解：明文“pay more money”可编码为：15 0 24；12 14 17；4 12 14；13 4 24。

由于：

?17175???303303531mod26=[17 17 11]

211821?15024????????2219???17175???532490677mod26=[12 22 1]

211821?121417????????2219???17175??41214???211821????348312??2219???17175??13424???211821??353341219????2??故对应的密文为：RRLMWBKASPDH。

提示：解密计算逆矩阵：

17175det?k??211821?－939mod26=23

2219k*11???1?1?1M11?1821219?300=14

k*?1?2?117512??M21??219??313=25

k*3?117513???1?M31?1821?267=7

k*1?2?1M212121???12??219??357=7

k*2?217522???1?M22?219?313=1

k*1?3?217523???M32??2121??252=8

k*1?3?211831???1?M1322?6

k*?2?3M171732???123??22?0

k*???1?3?3M17173333?2118?-51mod26=1

538?mod26=[10 0 18]

605?mod26=[15 3 7]

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

?4915????15176????24017??23?mod26?

3－8 用Vigenere算法加密明文“We are discovered save yourself”，密钥是：deceptive。

解：密文应为：zi cvt wqngrzgvtw avzh cqyglmgj。

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)

证明：

m（j为某一整数）（1）设a(modm)?ra，b(modm)?rb，则a?ra?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)

m（j为某一整数）（2）设a(modm)?ra，b(modm)?rb，c(modm)?rc，则a?ra?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。

－1

4－6 求Z5中各非零元素的乘法逆元。

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

2?12?1??解：??100???22?52??22?15???5?1???????40

??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?G (称为逆元)，使得：a?a如果一个群满足交换律，则称其为交换群。

如果一个群的元素是有限的，则称该群为有限群。 有限群的阶就是群中元素的个数。

k?1?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只包含有限个元素，则称其为有限域。

不可约多项式是指不能再分解为两个次数低于该多项式最高次的多项之积的多项式。

?1