密码学-课后习题.doc

第三章：
3-1 使用密钥字为common的代换密码方案，列出字母代换表
解：去除后来重复的字母后，真正的密钥字为comn
明文

密文
C
O
M
N
A
B
D
E
F
G
H
I
J
明文

密文
K
L
P
Q
R
S
T
U
V
W
X
Y
Z
3-2 解密下面的一段恺撒密码密文（明文单词间留空，以便阅读）：
EHVWWLPHRIWKHBHDULVVSULQJZKHQIORZHUVEORRP
解：将密文字母在英文字母表上前移3个位置，即可得到这段恺撒密码密文对应的明文如下： best time of the year is spring when flowers bloom
3-3 利用仿射密码算法加密下面的明文，假设k1=7，k2=3（要求首先列出明文字母-密文字母代换表，然后给出对应的密文，并以字母t的加密为例给出计算过程）：
解：因为k1=7，k2=3，因此仿射密码的加密公式为

字母t（19）被加密为

完整的明文字母-密文字母代换表如下表所示：
明文

密文
D
K
R
Y
F
M
T
A
H
O
V
C
J
明文

密文
Q
X
E
L
S
Z
G
N
U
B
I
P
W
3-4 解密3-3题所得仿射密码密文，并以密文字母F的解密为例说明计算过程。
解：因为k1=7，k2=3，因此，根据仿射密码的解密公式，有

密文字母F（5）解密为：
密文
A
B
C
D
E
F
G
H
I
J
K
L
M
明文
h
w
l
a
p
e
t
i
x
m
b
q
f
密文
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
明文
u
j
y
n
c
r
g
v
k
z
o
d
s
3-5 使用密钥字student 对明文cryptography进行维吉尼亚密码加密和解密，要求仿照表3-7（P51）给出其加密和解密过程，并说明相同明文字符的加密结果。
解：去除密钥字student中后来重复的字母后，真正的密钥为studen。因此，应将明文、密文按照6位长度进行分组，每组使用同样的密钥studen加密、解密。
3-6 选择希尔密码的加密密钥矩阵k为：试以明文love为例
解：将明文字符love变换为数字，分别为11、14、21、4。 因为加密密钥矩阵k为2阶矩阵，所以应将明文分成和两组分别进行加密。
（1）确定解密密钥矩阵k-1

（见表2-2（P21））

（2）加密

因此，明文字符love的加密密文为ZQFS。
（3）解密

因此，密文字符ZQFS的解密明文为love，即解密后恢复了原来的明文。
3-7 使用每行5个字符的格子和密钥字money，将下面的明文置乱为密文（多余的空格内依次填入字母a、b、c…）：cryptography is the science and study of secret writing
提示：将密钥字money变换为数字（字母表上最靠前的密钥字母用0表示，然后依次递增），即是读出列的顺序。
解：置乱密码的格纸表如下表所示：
列
行
0
1
2
3
4
0
c
r
y
p
t
1
o
g
r
a
p
2
h
y
i
s
t
3
h
e
s
c
i
4
e
n
c
e
a
5
n
d
s
t
u
6
d
y
o
f
s
7
e
c
r
e
t
8
w
r
i
t
i
9
n
g
a
b
c
根据密钥字money，得到读出列的顺序为1、3、2、0、4。按照此顺序读出各列，得到置乱密文如下：RGYENDYCRG PASCETFETB YRISCSORIA COHHENDEWN TPTIAUSTIC
3-9 用频数法破译下面的一段仿射密码密文（不含空格）：
FMXVE DKAPH FERBN DKRXR SREFM ORUDS DKDVS HVUFE DKAPR KDLYE VLRHH RH
解：（1）密文字母频数统计
该段仿射密码密文一共有57个密文字符，密文字母出现的频数如下表所示：
字母
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频数
2
1
0
7
5
4
0
5
0
0
5
2
2
1
1
2
0
8
3
0
2
4
0
2
1
0

从上表可见频数比较高的密文字母：R：8 ； D：7； E、H、K：5 ； F、V：4
而明文字母频数比较高的几个英文字母依次为e、t、a、o、i、n、s、h、r。
（2）假设与推论、证实
第一次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数次高的密文字母D（3）对应频数次高的明文字母t（19）。第二次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数第三高的密文字母E（4）对应频数次高的明文字母t（19）。第三次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数并列第三的密文字母H（7）对应频数次高的明文字母t（19）。
第四次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数并列第三的密文字母K（10）对应频数次高的明文字母t（19）。根据仿射密码的加密公式，列出密文和明文的关系方程组如下：
⑦
⑧
⑧-⑦得：
解得：
由于，因此存在乘法逆元，且，说明第四次假设正确。
将代入⑦式，得：
因此，破译得到该仿射密码的加密密钥为，。将它们代入仿射密码的解密公式，得到： ⑨
将密文字母代入⑨式，得到对应的明文字母，如下表所示：
密
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
明
h
q
z
i
r
a
j
s
b
k
t
c
l
u
d
m
v
e
n
w
f
o
x
g
p
y
例如，密文字母U（20）代入⑨式，得到明文字母为

对照题上表，将密文变换为明文，得到如下的一段具有明确意义的明文：
algorithms are quite general definitions of arithmetic processes
第四章：
4-5 分别使用（4-14）式和表4-1的S盒查找表，求16进制数{5c}和{e2}的字节代换结果。已知{5c}-1={51}，{e2}-1={d6}。
解 由于{5c}-1={51}=（01010001）

而根据表4-1的S盒查找表，可以直接得到{5c}的字节代换结果为{4a}，可见二者结果相同。
同理，由于{e2}-1={d6}=（11010110），根据（4-14）式，有

而根据表4-1的S盒查找表，可以直接得到{e2}的字节代换结果为{98}，可见二者结果也相同。
4-6 AES的中间态如题4-6图所示。求AES对其执行行移位运算ShiftRows后的结果。
e55
f18
ae C
306
983
11A
527
5d 6
27C
41c0
b4eC
bfE
1e7
b8D
e02
d47
305
e58
f1C
ae6
523
5dA
987
116
41C
b4c0
bfeC
27E
1e7
b8D
e02
d47

解 AES对其执行行移位运算ShiftRows后的结果如题4-6图2所示。
4-7 分别用多项式乘法、移位相加法和表操作法计算下列字节乘法运算：
（1） （2）
解 （1），。
① 多项式乘法计算字节乘法运算

② 移位相加法计算字节乘法运算
由于，且

因此，有

③ 表操作法计算字节乘法运算
查表4-2的对数表，有：，。因此，

查表4-3的反对数表，有：。因此，。
4-9 利用的已知结果，证明域上的元素。
解

4-10 利用表操作法，计算域上的元素和的乘法逆元。
解：，
根据表4-2，有，，因此，

根据表4-3，得到

4-11 分别用移位相加法和表操作法计算AES的下列字运算：
（1）
（2）
解
（1）
① 移位相加法计算

② 表操作法计算

（2）
① 移位相加法计算

② 表操作法计算

4-12 假设128比特种子密钥k为：
k=ab 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c
试仿照表4-6列表给出轮密钥字的密钥扩展过程及结果。
解 轮密钥字的密钥扩展过程及结果如题4-12表所示。

0

ab7e1516
1

28aed2a6
2

abf71588
3

09cf4f3c
4
09cf4f3c
cf4f3c09
8a84eb01
01000000
8b84eb01
ab7e1516
20fafe17
5
20fafe17

28aed2a6
08542cb1
6
08542cb1

abf71588
a3a33939
7
a3a33939

09cf4f3c
aa6c7605
8
aa6c7605
6c7605aa
50386bac
02000000
52386bac
20fafe17
72c295bb
9
72c295bb

08542cb1
7a96b90a

4-20 画出题4-20图所示4级序列产生器的全状态图，从最小的非0状态开始写出一个周期的输出序列，并说明它是否是m序列产生器。
题4-20图 4级序列产生器

解：该4级序列产生器的全状态图如题4-20图2所示。由图可见，从最小的非0状态开始，一个周期的输出序列为100011110101100，其周期为15，因此它是m序列产生器。

0000
0001
1000
1100
1110
1111
0111
1011
0101
1010
1101
0110
0011
1001
0100
0010
题4-20图2 4级序列产生器的全状态图

4-23 检验周期序列“100011110101100”的平衡特性、游程特性和自相关特性。其中，自相关特性直接通过（4-57）式和（4-58）式的计算来进行检验。
解：（1）平衡特性检验。该序列的周期为15 ，且一个周期中有8个“1”、7个“0”，因此符合戈龙提出的随机性公设中的平衡特性。如用频数法检验，将、代入（4-59）式，有
显然，它远远小于1自由度的分布表中5%显著性水平值3.84，所以通过频数检验。
（2） 游程特性检验。该序列的一个周期中，有两个长度为1的“1”游程，有1个长度为2的“1”游程，有1个长度为4的“1”游程，“1”游程的总数为4。除了长度为4的“1”游程外，长度为1的“1”游程数为“1”游程总数的1/2，长度为2的“1”游程数为“1”游程总数的1/4，因此基本符合游程特性。
同样，该序列的一个周期中，有两个长度为1的“0”游程，有1个长度为2的“0”游程，有1个长度为3的“0”游程，“0”游程的总数为4。除了长度为3的“0”游程外，长度为1的“0”游程数为“0”游程总数的1/2，长度为2的“0”游程数为“0”游程总数的1/4，因此也基本符合游程特性。
（3）自相关特性检验。检验结果见题4-23表。从该表可见：
① 该序列的自相关函数值符合（4-58）式的特性，即时，；时，。因此该序列具有很好的自相关特性。
② 自相关函数具有周期性，其周期与要检验序列的周期相同。

题4-23表 自相关特性检验

序列
相同位数A
不同位数D

0
100011110101100
15
0
1
1
000111101011001
7
8
-1/15
2
001111010110010
7
8
-1/15
3
011110101100100
7
8
-1/15
4
111101011001000
7
8
-1/15
5
111010110010001
7
8
-1/15
6
110101100100011
7
8
-1/15
7
101011001000111
7
8
-1/15
8
010110010001111
7
8
-1/15
9
101100100011110
7
8
-1/15
10
011001000111101
7
8
-1/15
11
110010001111010
7
8
-1/15
12
100100011110101
7
8
-1/15
13
001000111101011
7
8
-1/15
14
010001111010110
7
8
-1/15
15
100011110101100
15
0
1
第5章：
5-5　在RSA体制中：
（1）若,,，求、和。
（2）若，，求。该计算结果说明了什么问题？
解 （1），

（2）由于，因此,。

该结果说明， 、太小是不安全的，攻击者容易通过因式分解从分解出、，并进而根据和计算出私钥。
5-6　使用快速计算法计算下列模指数，要求列表给出计算过程。
（1）1613 mod 4661 （2）432159 mod 4661
解（1）b=13=（1101），a=16，n=4661，计算过程如下表所示

3
1

2
1

1
0

0
1

因此，。
（2）b=59=（111011），a=4321，n=4661，计算过程如下表所示。

5
1

4
1

3
1

2
0

1
1

0
1

因此，。
5-7　假设Alice和Bob采用RSA密码体制进行保密通信。已知Alice的公钥为（eA，nA）=(13，115)，私钥为（dA，nA）=（62，115）；Bob的公钥为（eB，nB）=(7，119)，私钥为（dB，nB）=（55，119）。
（1）若Alice想将明文加密后传送给Bob，试计算密文。
（2）若Bob要解密密文，试计算明文。
解（1）
（2）
5-8 假设Alice和Bob采用RSA密码体制进行保密通信。已知Alice的公钥为（eA，nA）=(13，115)，私钥为（dA，nA）=（62，115）；Bob的公钥为（eB，nB）=(1223，2867)，私钥为（dB，nB）=（167，2867）。字符代换规则为：字母a~z分别用01~26表示，空格用00表示。
（1) 若Alice想将明文“rsa algorithm”秘密地发送给Bob，帮Alice计算密文。
（2）Bob收到Alice发来的密文后，帮Bob计算明文，并将明文替换回英文字符。
（3）若Bob想将明文“rs”秘密地发送给Alice，帮Bob计算密文。
解（1）由于Bob的模数nB=2867，因此Alice可以一次加密两个字符。将明文“rsa algorithm”替换为数字，并按两个字符分组为：1819 0100 0112 0715 1809 2008 1300。各组明文加密如下：

因此，Alice加密后的密文为：2756 2001 0542 0669 2347 0408 1815。
（2）Bob收到Alice发来的密文后，分组解密得到各组明文：

因此，Bob解密后的明文为：1819 0100 0112 0715 1809 2008 1300。替换回英文字符后，明文为：rsa algorithm。
（3）由于Alice的模数nA=115，因此Bob只能一次加密一个字符。将明文“rs”替换为数字，为：18 19。各组明文加密如下：

因此，Bob加密后的密文为：48 99。
5-9 假设Alice采用EIGamal密码体制，并选择素数，私钥， 且已知的一个生成元。
（1） 计算Alice的公钥y。
（2） 若Bob想秘密发送消息给Alice，且他选择的随机数，试给出Bob和Alice的加密和解密过程。
（3）若Bob发送上述密文时，不慎将密文交换了位置，会出现什么问题？
解
（1）Alice的公钥。
（2）Bob和Alice的加密和解密过程
Bob加密：

Alice解密：

（3）若Bob发送上述密文时，不慎将密文交换了位置，Alice将无法正确解密。此时，Alice的解密结果为：

5-10 说明实数域上的椭圆曲线能否构成一个阿贝尔群。
解 由于、，因此，不满足（5-37）式关于的要求，所以实数域上的椭圆曲线不能构成一个阿贝尔群。
5-11　找出素域上的椭圆曲线即上的所有点。
解 对于、的所有可能值0~10，列一张方表如题5-11表所示，逐对验证、值是否素域上椭圆曲线即上的点（注意，数值运算时要进行mod 11运算）。若是，对应表格内划√；若不是，对应表格内不做记号。
题5-11表 寻找素域上椭圆曲线即上的所有点

0
1
2
3
4
5
6
7
8
9
10
0

1

2

√

√

3

√
√

4

5

√

√

6

7

√

√

8

√

√

9

10

√

√

根据题5-11表，得到素域上椭圆曲线即上的所有点（不含无穷远点）为：（2,4）,（2,7）,（3,5）,（3,6）,（5,2）,（5,9）,（7,2）,（7,9）, （8,3）, （8,8）, （10,2）,（10,9）。
5-13 由不可约多项式定义的有限域有一个生成元，非0元素与生成元的关系参见表5-4。已知上的椭圆曲线为，其上的两个点分别为和。计算：
（1） （2）
（3） （4）
解 ，，，，，。
（1）由于，因此Q与R为互逆点。根据互逆点规则和（5-61）式，有

因此，有
。
（2）。因为，所以P、R是非互逆点。
根据（5-65）式，有

将代入（5-63）、（5-64）式，得到

因此，有

（3） 。根据倍点规则，有

将代入（5-67）和（5-68）式，得到

因此，有

（4）。
首先计算。根据倍点规则，有

将代入（5-67）和（5-68）式，得到

因此，有

再计算。因为，所以P、W是非互逆点。
根据（5-65）式，有

将代入（5-63）、（5-64）式，得到

因此，有

5-15 由不可约多项式定义的有限域有一个生成元，非0元素与生成元的关系参见表5-4。已知上的椭圆曲线为，以其上阶的点构造椭圆曲线的子群。假设Alice和Bob使用基于上述参数的椭圆曲线密码体制进行保密通信。
（1） 若Bob选择私钥，计算Bob的公钥。
（2） 若Alice要秘密发送消息m=（01101011）给Bob，给出Alice的加密过程。假设她随机选择整数，满足。
（3） 给出Bob的解密过程。
（4） 该题的参数选择是否有问题？为什么？
解 ，，。
（1）计算Bob的公钥：
根据（5-80）式，Bob的公钥为：

假设：

则有：

现在，首先计算。根据倍点规则，有

将代入（5-67）和（5-68）式，得到

因此，有

然后，计算Bob的公钥。由于，因此不是互逆点。
根据（5-65）式，有

将代入（5-63）、（5-64）式，得到

因此，有

（2）Alice要秘密发送消息m=（01101011）给Bob的加密过程：
① 查找Bob的公钥。
② 将消息划分为域元素，满足：

③ 随机选择一个整数，满足。
④ 计算密文：
首先计算。根据倍点规则，有

将代入（5-67）和（5-68）式，得到

因此，有

然后计算。根据倍点规则，有

将代入（5-67）和（5-68）式，得到

因此，有

最后计算：

⑤ 将和密文、按下面的数据格式：

发送给Bob。
（3）Bob的解密过程
当Bob收到Alice发送来的密文时，按如下过程进行解密操作：
① 用Bob自己的私钥，计算：

假设：

则有：

现在，首先计算。根据倍点规则，有

将代入（5-67）和（5-68）式，得到

因此，有

然后，计算。由于，因此不是互逆点。
根据（5-65）式，有

将代入（5-63）、（5-64）式，得到

因此，有

② 计算，恢复明文：

可见，解密结果完全正确。
（4） 该题的参数选择有问题。因为计算结果显示，导致，即密文与明文相同。这是密码系统必须要避免的
第六章：
6-6 根据式6-7有，此处n=200，
计算可得，
因此，当n为200时，k为16.67。
6-7 根据下式
（）
（）
计算：

第七章：
7-12 对于RSA数字签名体制，假设模n=824737，公钥e=3。
（1）已知签名s=8798，计算m

（2）数据对（m，s）=（96551,366314）是有效的消息-签名对吗？
根据s=366314，计算m’

因为m’=m=96551，所以数据对（m，s）=（96551，366314）是有效的消息-签名对。
（3）因为：

所以m1×m2的签名s可计算

经验证，m1×m2的签名s是有效的签名。
7-13 （1）已知p，q，h，计算g

（2）已知x，计算y

（3）首先求出k模q的逆，然后计算r，s

消息m的数字签名为（40，38）
（4）验证签名，计算

由前面计算可知，因此签名正确。

26