计算机密码学习题

一、已知密文ILPQPUN 使用的是移位密码，试解密（提示：明文为有意义的英文）。 答：原文： ILPQPUN

移动1位：HKOPOTM 移动2位：GJNONSL 移动3位：FIMNMRK 移动4位：EHLMLQJ 移动5位：DGKLKPI 移动6位：CFJKJOH 移动7位：BEIJING 明文为BEIJING

二、已知playfair 加密矩阵如下, 试将I LOVE ELLEN 加密 U N J /I V S 答：先填充为IL,OV ,EX,EL,LE,NX C E A D T 加密

IL →AK OV →GN EX →DR

H O L G Y EL →AO LE →OA NX →VR B F K M P 密文为AKGNDRAOOA VR Q R W X Z

三、假定在置换密码中，其置换表如下 X 1 2 3 4 5 6 7 8 π(x) 4 1 6 2 7 3 8 5 1 求出逆置换表π-1(x). 2 解密下面的密文

ETEGENLMDNTNEOORDAHATECOESAHLRMI 解1 根据原置换表，其逆置换表如下

X 1 2 3 4 5 6 7 8 π-1(x) 2 4 6 1 8 3 5 7

2 根据上面的逆置换表，可以得出该密文对应的明文为 Gentemendonotreadeachothersmail ， Gentle men do not read each other’s mail

四、下表是DES 算法中S4 盒的选择矩阵，如果其输入为101011，则输出为

解、0001

五、求gcd(4655, 12075) 。 六、求gcd(1970, 1066)。

七、叙述扩展欧几里德算法，并使用其求解61u ≡1(mod101) 解：扩展欧几里德算法是用来在已知a , b 求解一组 ) p a +q b =g c d (a , b

具体算法如下：输入a , b , 输出p , q

p , q

使得

1. i ←0, r -1←a , r 0←b , t -1←1, s -1←0, t 0←0, s 0←1 i ←1；

r(0)←a , r(1)←b ,t(0)←1, s(0)←0; 2. while

r i ≠0

do

r i +1=r i -1m od r i

2.1 2.2 2.3 3.

⎢r ⎥u ←⎢i -1⎥

⎣r i ⎦

t i +1←t i -1-ut i , s i +1←s i -1-us i i ←i +1

p =t i -1, q =s i -1

61u +101v ≡1

求解61u ≡1(mod101) 即求解 1）i ←0, r -1←101, r 02）r 0

←61, t -1←1, s -1←0, t 0←0, s 0←1

⎢101⎥

=61≠0，u ← r =40

⎢61⎥=11⎣⎦

t 1=1-1⨯0=1, s 1=0-1⨯1=-1，

3）r 1≠0 4）r 2

⎢61⎥

r =21 t 2=0-1⨯1=-1, s 2=1-1⨯(-1) =2u ←⎢⎥=12

40⎣⎦

⎢40⎥

=21≠0 u ← r =19 t 3=1-1⨯(-1) =2, s 3=-1-1⨯2=-3

⎢21⎥=13⎣⎦

⎢21⎥

u ←⎢⎥=1 r 4=2 t 4=-1-1⨯2=-3, s 4=2-1⨯(-3) =5

⎣19⎦

5）r 3=19≠0 6）r 46）r 57）r 6

⎢19⎥

=2≠0 u ← r 5=1 t 5=2-9⨯(-3) =29, s 5=-3-9⨯5=-48

⎢2⎥=9⎣⎦

=1≠0

⎢2⎥

u ←⎢⎥=2 r 6=0

⎣1⎦

t 6=-3-2⨯29=-61, s 6=5-2⨯(-48) =101

=0

u =t 5=29, v =s 5=-48

所以61u ≡1(mo d 101) 的解为u =29

八、用推广的Euclid 算法求67 mod 119的逆元。

九、RSA 加密体制中p =47，q =61，e =13，使用扩展欧几里德算法计算出解密指数d （需要详细过程） 解： p =47，q =61，n =

2760=212⨯13+4

pq =2867，Φ(n ) =(p -1)(q -1) =27603⨯

4+ 1

1

3=

所以1=13-3⨯4=13-3⨯(2760-212⨯13) =637⨯13-3⨯2760 所以13-1≡637(mod2760) 十、考虑RSA 密码体制：

1. 取e=3有何优缺点？取d=3安全吗？为什么？

2设n=35，已截获发给某用户的密文C ＝10，并查到该用户的公钥e=5，求出明文M 。 解答：

①e=3的优点是计算快，因为其二进制表示中只有2个1，缺点是不安全。当M 较小时，直接开立方可求出M 。d=3不安全，经不起穷举攻击。

②分解n=35=7×5，于是p=7,q=5。φ（n ）=6×4=24。因为e=5，根据ed=1 modφ（n ），求出d=5。

根据M=Cd mod n,M=105 mod 35,求出M ＝5。

十一．用模n 的大数幂乘的快速算法求112119mod 221(写出算法的过程) 。

解：112119mod 221=112×112118mod 221=112×16859mod

221=31×16858mod 221=31×15729mod 221=5×15728mod 221 =5×11814mod 221=5×17mod 221=5×10mod 221=5

十二、用Fermat 费尔马定理求3201mod 11 解：根据Fermat 定理有310=1mod11 ，故 3 201mod 11= 3 200+ 1mod 11= (3200 ×3)mod 11

=[(3 200mod 11) (3mod 11)]mod 11= [((3 10) 20mod 11) 3]mod 11 =[((3 10) 20 mod 11) 3]mod 11= [(3 10mod 11) 20 3]mod 11 =[1 20×3]mod 11= 3.

十三、请用公开密钥密码体制描述具有保密性的数字签名。（可以用图示说明表示）

十四、对密码的攻击主要有哪几种方法?

答：1、唯密文分析（攻击），密码分析者取得一个或多个用同

一密钥加密的密文；

2、已知明文分析（攻击），除要破译的密文外，密码分析者还取得一些用同一密钥加密的密文对；

3、选择明文分析（攻击），密码分析者可取得他所选择的任何明文所对应的密文（不包括他要恢复的明文），这些密文对和要破译的密文是用同一密钥加密的；

4、选择密文分析（攻击），密码分析者可取得他所选择的任何密文所对应的明文（要破译的密文除外），这些密文和明文和要破译的密文是用同一解密密钥解密的，它主要应用于公钥密码体制。

十五、在公钥密码的密钥管理中，公开的加密钥Ke 和保密的解密钥Kd 的秘密性、真实性和完整性都需要确保吗？说明为什么？ 解答：

①公开的加密钥Ke ：秘密性不需确保，真实性和完整性都需要确保。因为公钥是公开的，所以不需要保密。但是如果其被篡改或出现错误，则不能正确进行加密操作。如果其被坏人置换，则基于公钥的各种安全性将受到破坏，坏人将可冒充别人而获得非法利益。

②保密的解密钥Kd ：秘密性、真实性和完整性都需要确保。因为解密钥是保密的，如果其秘密性不能确保，则数据的秘密性和真实性将不能确保。如果其真实性和完整性受到破坏，则数据的秘密性和真实

性将不能确保。 ③举例

（A ）攻击者C 用自己的公钥置换PKDB 中A 的公钥：

（B ）设B 要向A 发送保密数据，则要用A 的公钥加密，但此时已被换为C 的公钥，因此实际上是用C 的公钥加密。 （C ）C 截获密文，用自己的解密钥解密获得数据。