第一章

4．设多表代换密码C_i=AM_i＋B (mod 26)中，A是2×2矩阵，B是0矩阵，又知明文“dont”被加密为“elni”，求矩阵A。

解：明文对应数字为：3，14，13，19；密文对应数字为4，11，13，8

设A为，则由名密文对应关系可得：

a₁₁×3＋a₁₂×14＝4(mod 26)

a₂₁×3＋a₂₂×14＝11(mod 26)

a₁₁×13＋a₁₂×19＝13(mod 26)

a₂₁×13＋a₂₂×19＝8(mod 26)

解以上四元一次方程组可得矩阵A＝＝

第二章

1．3级线性反馈移位寄存器在c₃＝1时可有4种线性反馈函数，设其初始状态为(a₁,a₂,a₃)=(1,0,1)，求各线性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为f(a₁,a₂,a₃)=a₁⊕c₂a₂⊕c₁a₃

当c₁＝0，c₂＝0时，f(a₁,a₂,a₃)=a₁⊕c₂a₂⊕c₁a₃＝a₁，

输出序列为101101…，周期＝3

当c₁＝0，c₂＝1时，f(a₁,a₂,a₃)=a₁⊕c₂a₂⊕c₁a₃＝a₁⊕a₂，

输出序列为10111001011100…，周期＝7

当c₁＝1，c₂＝0时，f(a₁,a₂,a₃)=a₁⊕c₂a₂⊕c₁a₃＝a₁⊕a₃，

输出序列为10100111010011…，周期＝7

当c₁＝1，c₂＝1时，f(a₁,a₂,a₃)=a₁⊕c₂a₂⊕c₁a₃＝a₁⊕a₂⊕a₃，

有输出序列为1010…，周期＝2

3．设n＝4，f(a₁,a₂,a₃,a₄)=a₁⊕a₄⊕1⊕a₂a₃，初始状态为(a₁,a₂,a₃,a₄)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

解：由反馈函数和初始状态得状态输出表为

(a₄a₃a₂a₁) 输出 (a₄a₃a₂a₁) 输出

1 0 1 1 1 1 1 1 1 1

1 1 0 1 1 0 1 1 1 1

1 1 1 0 0 1 0 1 1 1（回到初始状态）

所以此反馈序列输出为：11011…周期为5

5．设密钥流是由n级LFSR产生，其周期为2ⁿ－1，i是任一正整数，在密钥流中考虑以下比特对

(S_i, S_i₊₁), (S_i₊₁, S_i₊₂), …, (S_i₊₂ⁿ_－3, S_i₊₂ⁿ_－2), (S_i₊₂ⁿ_－2, S_i₊₂ⁿ_－1),

问有多少形如(S_j, S_j₊₁)＝(1,1)的比特对？证明你的结论。

答：共有2^(n-2)

证明：

证明方法一：由于产生的密钥流周期为2ⁿ－1，且LFSR的级数为n，所以是m序列

以上比特对刚好是1个周期上，两两相邻的所有比特对，其中等于(1,1)的比特对包含在所有大于等于2的1游程中。由m序列的性质，所有长为i的1游程(1≤ i ≤n-2)有2ⁿ^-ⁱ^-1/2个，没有长为n－1的1游程，有1个长为n的1游程。

长为i (i>1)的1游程可以产生i-1个(1,1)比特对，

所以共有(1,1)比特对的数目N＝2ⁿ^-2-2×(2－1)＋2ⁿ^-3-2×(3－1)＋…＋2ⁿ^-i-2×(i－1)＋…＋2ⁿ^-(ⁿ^－2)－2×(n－2－1)＋n－1＝＋n－1＝2^(n-2)

证明方法2：考察形如11*…*的状态的数目，共有2^(n-2)个

6．已知流密码得密文串为1010110110和相应明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。

解：由二元加法流密码的加密算法可知，将密文串和相应的明文串对应位模2加可得连续的密钥流比特为1110100111

设该三级线性反馈移位寄存器的反馈函数为f(a₁,a₂,a₃)=c₃a₁⊕c₂a₂⊕c₁a₃

取其前6比特可建立如下方程

(a₄a₅a₆)＝(c₃,c₂,c₁)，

即(c₃,c₂,c₁)＝(a₄a₅a₆)＝(0 1 0) =(0 1 0) =(1 0 1)

所以f(a₁,a₂,a₃)=a₁⊕a₃，即流密码的递推关系式为a_i₊₃=a_i₊₂⊕a_i

8.设J-K触发器中{a_k}和{b_k}分别为3级和4级m序列，且

{a_k}＝11101001110100…

{b_k}＝001011011011000 001011011011000…

求输出序列{c_k}及周期。

解：由于gcd(3，4)=1且a₀＋b₀＝1所以序列{c_k}的周期为(2³-1)(2⁴-1)=105

又由J-K触发器序列的递推式c_k=( a_k+b_k+1) )c_k_-1+a_k，令c_-1=0可得输出序列为：

{c_k}=11001001…

9．设基本钟控序列产生器中{a_k}和{b_k}分别为2级和3级m序列，且

{a_k}＝101101…

{b_k}＝10011011001101…

求输出序列{c_k}及周期。

解：序列{a_k}的周期p₁＝2²－1＝3，序列{b_k}的周期p₂＝2³－1＝7，w₁＝a₀＋a₁＋a₂＝2

而gcd(w₁, p₂)=1。所以序列{c_k}的周期p＝p₁p₂＝3×7＝21

记LFSR2(产生序列{b_k})的状态向量为σ_k，则σ₀＝(100)，在LFSR1(产生序列{a_k})的控制下，状态转移为：

{a_k} 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1

(100),(001),(001),(011),(110),(110),(101),(011),(011),(110),(100),(100),(001),(011),(011),(110)

1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1

{a_k} 1 0 1 1 0 1 1 0 1

(101),(101),(011),(110),(110),(100),(001), (001),(011)

1 1 0 1 1 1 0 0 0

所以输出序列为100011100111000111011 1000…

第三章

3．在DES的CBC模式中C₁的一个错误明显地将影响P₁和P₂的结果

（1）P₂以后的分组不受影响，这是因为C₁以后的密文都是正确的，而恢复明文主要看对应密文分组和其前一个密文分组的正确性。

（2）加密前的明文分组P₁有1比特错误，则这一错误将在所有后续密文分组中传播，但接受者能够正确解密，除了P₁的一个错误比特之外。这是因为相当于发送者将明文改变了1比特得到一个新明文，而该明文的对应密文正确的传送给了接受方。

4．在8bitCFB中密文字符中出现1比特错误，该错误将影响包括该密文的连续9组密文的解密。

第四章

10．设通信双方使用RSA加密体制，接收方的公开钥是(e，n)＝(5,35)，接收到的密文是C＝10，求明文M。

解：由n＝35，易知35＝5×7，进而ϕ(n)= ϕ(35)=24，

由RSA加密体制可知，ed≡1 mod ϕ(n)，即5d≡1 mod 24，所以d＝5

∴M=C^d mod n＝10⁵ mod 35＝5

Ps：ϕ(n)=(p-1)(q-1)

13．在ElGamal体制中，设素数p＝71，本原根g＝7，

（1）如果接收方B的公开钥是y_B＝3，发送方A选择的随机整数k＝3，求明文M＝30所对应的密文。

解：C₁=g^k mod p＝7³ mod 71＝59

C₂=y_B^kM mod p＝3³×30 mod 71＝29

所以密文为(59，29)

（2）如果A选择另一个随机数k，使得明文M=30，加密后的密文是C＝（59，C₂），求C₂

解：由C₁=g^k mod p得59＝g^k mod p＝7^k mod 71，即k＝3

而C₂=y_B^kM mod p＝3³×30 mod 71＝29

14．设背包密码系统得超递增序列为（3，4，9，17，35），乘数为t＝19，模数k＝73，试对good night加密。

解：由A=（3，4，9，17，35），乘数为t＝19，模数k＝73，

得B=t×A mod k＝(57，3，25，31，8）

名文“good night”的编码为“00111”，“01111”，“01111”，“00100”，“00000”，“01110”“01001”“00111”“01000”“10100”

f(00111)=25+31+8=64，f(01111)=3+25+31+8=67，f(01111)=3+25+31+8=67，f(00100)=25

f(00000)=0，f(01110)=3+25+31=59，f(01001)=3+8=11，f(00111)=25+31+8=64，

f(01000)=3，f(10100)=57＋25=82＝9 mod 73

相应的密文为（64，67，67，25，0，59，11，64，3，9）

15．设背包密码系统的超递增序列为（3，4，8，17，33），乘数为t＝17，模数k＝67，试对密文25，2，72，92解密。

解：t^－1mod k＝17^－1 mod 67＝4 mod 67

所以4×(25，2，72，92)mod 67＝(33,8,20,33)

从而可得4个明文分组为(00001,00100,10010,00001)，所以由表4－5明文为：“ADRA”

19．已知点G=（2，7）在椭圆曲线E₁₁(1,6)上，求2G和3G

解：求2G:

λ=(3×2²＋1)/(2×7) mod11＝13×4 mod11＝8

x₃＝8²－2－2 mod 11＝5，y₃＝8(2－5)－7 mod 11＝2

所以2G＝（5，2）

求3G＝2G＋G＝（5，2）＋（2，7）

λ=(7－2)/(2－5) mod11＝5×7 mod11＝2

x₃＝2²－5－2 mod 11＝8，y₃＝2(5－8)－2 mod 11＝3

所以3G＝（8，3）

20．利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E₁₁(1,6)，生成元G=（2，7），接收方A的秘密钥n_A＝7

（1）求A的公开钥P_A

解：P_A＝7G＝2×2G＋3G

先求2×2G

λ=(3×5²＋1)/2×2 mod11＝10×3 mod11＝8

x₃＝8²－5－5 mod 11＝10，y₃＝8(5－10)－2 mod 11＝2

所以2×2G＝2×(5，2)＝(10，2)

P_A＝(10，2)＋(8，3）

由于λ=(3－2)/(8－10) mod11＝1×5 mod11＝5

x₃＝5²－10－8 mod 11＝7，y₃＝5(10－7)－2 mod 11＝2

所以P_A＝(7，2)

（2）发送方B欲发送P_m＝(10，9)，选择随机数k＝3，求密文C

解：C=(kG，P_m＋kP_A)，kG＝3G＝（8，3），kP_A＝2P_A＋P_A＝3G+7G＝(2，7)＋(7，2)

由于λ=(2－7)/(7－2) mod11＝－1

x₃＝(－1)²－2－7 mod 11＝3，y₃＝－1(2－3)－7 mod 11＝5

P_m＋kP_A＝(10，9)＋(3，5)

由于λ=(5－9)/(3－10) mod11＝－1

x₃＝(－1)²－10－3 mod 11＝10，y₃＝－1(10－10)－9 mod 11＝2

所以C=(kG，P_m＋kP_A)＝（（8，3），（10，2））

（3）显示接收方A从密文C_m恢复消息P_m的过程

解：P_m＝（P_m＋kP_A）－n_A(kG)＝（10，2）－7（8，3）＝（10，2）－（3，5）

＝（10，2）＋（3，6）＝(10，9)

第五章

2．Diffie-Hellman密钥交换协议易受中间人攻击，即攻击者截获通信双方通信的内容后可分别冒充通信双方，以获得通信双方协商的密钥。详细分析攻击者如何实施攻击。

虽然Diffie-Hellman密钥交换算法十分巧妙，但由于没有认证功能，存在中间人攻击。当Alice和Bob交换数据时，Trudy拦截通信信息，并冒充Alice欺骗Bob，冒充Bob欺骗Alice。其过程如下：

(1)Alice选取大的随机数x，并计算X=g^x (mod P)，Alice将g、P、X传送给Bob，但被Trudy拦截。

(2)Trudy冒充Alice选取大的随机数z，并计算Z=g^z(mod P)，Trudy将Z传送给Bob。

(3)Trudy冒充Bob，再将Z=g^z(mod P)传送给Alice。

(4)Bob选取大的随机数y，并计算Y =g^y(mod P)，Bob将Y传送给Alice，但被Trudy拦截。

由(1)、(3)Alice与Trudy共享了一个秘密密钥g^xz，由(2)、(4)Trudy与Bob共享了一个秘密密钥g^yz。

以后在通信过程中，只要Trudy作中间人，Alice和Bob不会发现通信的异常，但Trudy可以获取所有通信内容。

3．Diffie-Hellman密钥交换过程中，设大素数p＝11，a＝2是p的本原根，

(1) 用户A的公开钥Y_A＝9，求其秘密钥X_A

解：X_A满足Y_A＝a^XA mod p 即9＝2^XA mod 11，所以由X_A＝6

(2)设用户B的公开钥Y_B＝3，求A和B的共享密钥K

解：由Diffie-Hellman协议可知K= Y_B^XA mod p＝3⁶ mod 11＝3

4．线性同余算法X_n_＋1＝(aX_n) mod 2⁴，问：

(1)该算法产生的数列的最大周期是多少？

解：由于模m＝2⁴因此它没有原根，又由递推式不难得知X_n＝aⁿX₀ mod 2⁴

因此该算法产生的序列的最大周期为a mod 2⁴的最大阶l，而l|ϕ(2⁴)，但l≠ϕ(2⁴)＝8

若l＝4，则不难验证，X₀=1,a＝3时，数列周期为4，因此该算法产生数列的最大周期是4

(2) a的值是多少？

解：a必须满足gcd(a,2⁴)=1，所以a在{1,3,5,…,15}中取值。

周期为4的有{3，5，11，13}，即为a的取值

(3) 对种子有何限制？

答：种子X₀必须满足gcd(X₀,2⁴)=1。

5．在Shamir秘密分割门限方案中，设k＝3，n＝5，q＝17，5个子密钥分别是8、7、10、0、11，从中任选3个，构造插值多项式并求秘密数据s

解：取f(1)=8, f(2)=7, f(4)=0,构造插值多项式

f(x)=8(x-2)(x-4)/(1-2)(1-4)+7(x-1)(x-4)/(2-1)(2-4)＋0(x-1)(x-2)/(4-1)(4-2)

=8(x-2)(x-4)6+7(x-1)(x-4)8 mod 17

=2x²+10x+13

s= f(0)=13

第七章

1．在DSS数字签名标准中，取p=83=2×41+1，q＝41，h＝2，于是g≡2²≡4 mod 83，若取x＝57，则y≡g^x≡4⁵⁷＝77 mod 83。在对消息M=56签名时选择k＝23,计算签名并进行验证。

解：这里忽略对消息M求杂凑值的处理

计算r＝(g^k mod p) mod q＝(4²³ mod 83) mod 41=51 mod 41=10

k^-1mod q=23^-1 mod 41=25

s=k^-1(M+xr) mod q=25(56+57*10) mod 41=29

所以签名为(r,s)=(10,29)

接收者对签名(r′,s′)=(10,29)做如下验证：

计算w＝(s′)^-1 mod q=29^-1 mod 41=17

u1＝[M′w] mod q=56*17 mod 41=9

u2＝r′w mod q＝10×17 mod 41＝6

v＝(g^u¹y^u2 mod p) mod q=(4⁹×77⁶ mod 83) mod 41＝10

所以有v＝r′，即验证通过。

526互联

现代密码学 - 计算题

第一章

第二章

第三章

第四章

第五章

第七章