选择Problem1，Problem2，Problem3，Problem5，Problem6进行作答

Problem1

如果用Vigenere Cipher进行加密解密，则运算过程如下所示
KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲\label{2} &Enc…
根据字母表只有A，B，C。我们首先可以得到一个维吉尼亚密码表，如下所示

	A	B	C
A	A	B	C
B	B	C	A
C	C	A	B

如果密钥长度是2，那么我们可以将密文每两个分成一组，得到五组分别为AB,CB,AB,BB,AC，我们的密钥有六种可能，分别是AB,BA,AC,CA,BC,CB。

假设密钥为AB，对密文进行解密

解密结果为AACAAABAAB，也就是说对明文AACAAABAAB进行加密，得到的结果就是我们题目中的密文，所以我们的密钥长度有可能是2.

假设密钥为BA，对密文进行解密

解密结果为CBBBCBABCC,也就是说对明文CBBBCBABCC进行加密，得到的结果就是我们题目中的密文

假设密钥为AC，对密文进行解密

解密结果为ACCCACBCAA,也就是说对明文ACCCACBCAA进行加密，得到的结果就是我们题目中的密文

假设密钥为CA，对密文进行解密

解密结果为BBABBBCBBC,也就是说对明文BBABBBCBBC进行加密，得到的结果就是我们题目中的密文

假设密钥为BC，对密文进行解密

解密结果为CCBCCCACCA,也就是说对明文CCBCCCACCA进行加密，得到的结果就是我们题目中的密文

假设密钥为CB，对密文进行解密

解密结果为BAAABACABB,也就是说对明文BAAABACABB进行加密，得到的结果就是我们题目中的密文

对上述结果进行频率分析，发现当密钥为AB时，明文中A的出现频率为0.7，B的出现频率为0.2，C的出现频率为0.1，与经验频率相吻合，所以最有可能的密钥是AB

特别地，如果不对密钥长度加以限制，我们可以发现在密文中有一些重复的序列如下所示：

ABCBABBBAC : AB重复出现，两者之间相隔四个字母

ABCBABBBAC : BA重复出现，两者之间相隔四个字母

则可以认为4很可能是密钥的长度

Problem2

1. For a perfect secret encryption scheme E(K, M) = C, prove: Pr[C = c|M = m] = Pr[C = c].

Proof：
对 于 一 个 完 全 安 全 的 密 码 系 统 ， 我 们 有 P r [ M = m ∣ C = c ] = P r [ M = m ] ∵ P r [ M = m ∣ C = c ] = P r [ M = m , C = c ] P r [ C = c ] ∴ P r [ M = m ] P r [ C = c ] = P [ M = m , C = c ] ∴ P r [ C = c ] = P r [ M = m , C = c ] P r [ M = m ] ∴ P r [ C = c ] = P r [ C = c ∣ M = m ] 对于一个完全安全的密码系统，我们有Pr[M = m|C = c] = Pr[M = m]\\ ∵Pr[M = m|C = c] = \frac{Pr[M = m , C = c]}{Pr[C = c]}\\ ∴Pr[M = m]Pr[C = c] = P[M = m , C = c]\\ ∴Pr[C = c] = \frac{Pr[M = m , C = c]}{Pr[M = m]}\\ ∴Pr[C = c] = Pr[C = c|M = m] 对于一个完全安全的密码系统，我们有Pr[M=m∣C=c]=Pr[M=m]∵Pr[M=m∣C=c]=Pr[C=c]Pr[M=m,C=c]​∴Pr[M=m]Pr[C=c]=P[M=m,C=c]∴Pr[C=c]=Pr[M=m]Pr[M=m,C=c]​∴Pr[C=c]=Pr[C=c∣M=m]

2. Consider a biased one-time-pad system, where Pr[M = b] = pb, b = 0,1 and Pr[K = 0] = 0.4. The first attacker Randy randomly guesses M = 0 or M = 1: prove that the probability of success is 0.5. The second attacker Smartly guesses M based on C and p0, p1: suggest a good attack strategy.

(1) prove that the probability of success is 0.5.

Proof:
设 第 一 个 攻 击 者 做 出 M = 1 这 一 猜 测 的 概 率 为 p ′ , 做 出 M = 0 这 一 猜 测 的 概 率 为 p ′ ′ . 因 为 第 一 个 攻 击 者 是 随 机 进 行 猜 测 的 ， 所 以 p ′ = p ′ ′ = 0.5 所 以 第 一 个 攻 击 者 猜 测 正 确 的 概 率 为 : p c o r r e c t = p 0 ∗ p ′ ′ + p 1 ∗ p ′ = 0.5 ( p 0 + p 1 ) 因 为 我 们 已 知 p 0 + p 1 = 1 所 以 p c o r r e c t = 0.5 ∗ 1 = 0.5 设第一个攻击者做出M=1这一猜测的概率为p',做出M=0这一猜测的概率为p''.\\ 因为第一个攻击者是随机进行猜测的，所以p'=p''=0.5\\ 所以第一个攻击者猜测正确的概率为:\\ p_{correct} = p_0*p'' + p_1*p' = 0.5(p_0 + p_1)\\ 因为我们已知p_0+p_1 = 1\\ 所以p_{correct} = 0.5*1 = 0.5 设第一个攻击者做出M=1这一猜测的概率为p′,做出M=0这一猜测的概率为p′′.因为第一个攻击者是随机进行猜测的，所以p′=p′′=0.5所以第一个攻击者猜测正确的概率为:pcorrect​=p0​∗p′′+p1​∗p′=0.5(p0​+p1​)因为我们已知p0​+p1​=1所以pcorrect​=0.5∗1=0.5

(2) The second attacker Smartly guesses M based on C and p0, p1: suggest a good attack strategy.

首先我们可以知道明文取0或1这一事件与密钥取0或1这一事件是相互独立的，所以我们可以知道
p ( M = 0 , k = 0 ) = p ( M = 0 ) ∗ p ( k = 0 ) = p 0 ∗ 0.4 = 0.4 p 0 p ( M = 1 , k = 0 ) = p ( M = 1 ) ∗ p ( k = 0 ) = p 1 ∗ 0.4 = 0.4 p 1 p ( M = 0 , k = 1 ) = p ( M = 0 ) ∗ p ( k = 1 ) = p 0 ∗ ( 1 − 0.4 ) = 0.6 p 0 p ( M = 1 , k = 1 ) = p ( M = 1 ) ∗ p ( k = 1 ) = p 1 ∗ ( 1 − 0.4 ) = 0.6 p 1 p(M=0 , k=0) = p(M=0)*p(k=0) = p_0*0.4 = 0.4p_0\\ p(M=1 , k=0) = p(M=1)*p(k=0) = p_1*0.4 = 0.4p_1\\ p(M=0 , k=1) = p(M=0)*p(k=1) = p_0*(1-0.4) = 0.6p_0\\ p(M=1 , k=1) = p(M=1)*p(k=1) = p_1*(1-0.4) = 0.6p_1\\ p(M=0,k=0)=p(M=0)∗p(k=0)=p0​∗0.4=0.4p0​p(M=1,k=0)=p(M=1)∗p(k=0)=p1​∗0.4=0.4p1​p(M=0,k=1)=p(M=0)∗p(k=1)=p0​∗(1−0.4)=0.6p0​p(M=1,k=1)=p(M=1)∗p(k=1)=p1​∗(1−0.4)=0.6p1​
所以我们可以得到对应的密文取值的概率以及明文与密文取值的联合概率
p ( C = 1 ) = p ( M = 1 , k = 0 ) + p ( M = 0 , k = 1 ) = 0.4 p 1 + 0.6 p 0 p ( C = 0 ) = p ( M = 0 , k = 0 ) + p ( M = 1 , k = 1 ) = 0.4 p 0 + 0.6 p 1 p ( M = 1 , C = 1 ) = 0.4 p 1 p ( M = 1 , C = 0 ) = 0.6 p 1 p ( M = 0 , C = 1 ) = 0.6 p 0 p ( M = 0 , C = 0 ) = 0.4 p 0 p(C = 1) = p(M=1 , k=0) + p(M=0 , k=1) = 0.4p_1 + 0.6p_0\\ p(C = 0) = p(M=0 , k=0) + p(M=1 , k=1) = 0.4p_0 + 0.6p_1\\ p(M = 1,C = 1) = 0.4p_1\\ p(M = 1,C = 0) = 0.6p_1\\ p(M = 0,C = 1) = 0.6p_0\\ p(M = 0,C = 0) = 0.4p_0\\ p(C=1)=p(M=1,k=0)+p(M=0,k=1)=0.4p1​+0.6p0​p(C=0)=p(M=0,k=0)+p(M=1,k=1)=0.4p0​+0.6p1​p(M=1,C=1)=0.4p1​p(M=1,C=0)=0.6p1​p(M=0,C=1)=0.6p0​p(M=0,C=0)=0.4p0​
所以我们可以知道密文和明文取值的条件概率
p ( M = 1 ∣ C = 1 ) = p ( M = 1 , C = 1 ) p ( C = 1 ) = 0.4 p 1 0.4 P 1 + 0.6 p 0 p ( M = 0 ∣ C = 1 ) = p ( M = 0 , C = 1 ) p ( C = 1 ) = 0.6 p 0 0.4 P 1 + 0.6 p 0 p ( M = 1 ∣ C = 0 ) = p ( M = 1 , C = 0 ) p ( C = 0 ) = 0.6 p 1 0.4 P 0 + 0.6 p 0 p ( M = 0 ∣ C = 0 ) = p ( M = 0 , C = 0 ) p ( C = 0 ) = 0.4 p 0 0.4 P 0 + 0.6 p 1 p(M=1|C=1) = \frac{p(M=1,C=1)}{p(C=1)} = \frac{0.4p_1}{0.4P_1+0.6p_0}\\ p(M=0|C=1) = \frac{p(M=0,C=1)}{p(C=1)} = \frac{0.6p_0}{0.4P_1+0.6p_0}\\ p(M=1|C=0) = \frac{p(M=1,C=0)}{p(C=0)} = \frac{0.6p_1}{0.4P_0+0.6p_0}\\ p(M=0|C=0) = \frac{p(M=0,C=0)}{p(C=0)} = \frac{0.4p_0}{0.4P_0+0.6p_1} p(M=1∣C=1)=p(C=1)p(M=1,C=1)​=0.4P1​+0.6p0​0.4p1​​p(M=0∣C=1)=p(C=1)p(M=0,C=1)​=0.4P1​+0.6p0​0.6p0​​p(M=1∣C=0)=p(C=0)p(M=1,C=0)​=0.4P0​+0.6p0​0.6p1​​p(M=0∣C=0)=p(C=0)p(M=0,C=0)​=0.4P0​+0.6p1​0.4p0​​
所以当p0和p1满足下面的条件的时候我们可以做出相应的猜测
{ g u e s s M = 1 , w h e n p 1 > 3 2 p 0 g u e s s M = 0 , w h e n 2 3 p 0 < p 1 < 3 2 p 0 a n d C = 0 g u e s s M = 1 , w h e n 2 3 p 0 < p 1 < 3 2 p 0 a n d C = 1 g u e s s M = 0 , w h e n p 1 < 2 3 p 0 \begin{cases} guess\quad M = 1, when\quad p_1>\frac{3}{2}p_0\\ guess\quad M = 0, when\quad \frac{2}{3}p_0 <p_1<\frac{3}{2}p_0\quad and \quad C = 0\\ guess \quad M = 1, when\quad \frac{2}{3}p_0 <p_1<\frac{3}{2}p_0\quad and \quad C = 1\\ guess \quad M = 0, when\quad p_1<\frac{2}{3}p_0\\ \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​guessM=1,whenp1​>23​p0​guessM=0,when32​p0​<p1​<23​p0​andC=0guessM=1,when32​p0​<p1​<23​p0​andC=1guessM=0,whenp1​<32​p0​​

Problem3

我们可以看到k1在DESV和DESW中都是用来进行异或操作，这样一来我们就可以利用异或操作的性质将k1消掉。在DESV中，我们可以用两个密文进行异或，这样就可以将k1消掉，得到c1⊕c2,在这之后我们在对明文m1和m2用所有可能的k进行DES加密，再将加密后的结果进行异或，如果和c1⊕c2一致我们则可以认为这个对应的密钥即为k，所以在我们的操作中可以通过一个异或操作将k1消掉，主要的计算量在于破解k的DES，所以复杂度为O(2^{56)。在DESW中同理，我们先将两个密文进行DES解密，在将解密得到的结果进行异或消去k1，将异或的结果和明文异或即`m1⊕m2`进行对比，如果一致那么对应的k即为密钥，所以主要运算量仍为O(2}56).

综上所述，无论是DESW还是DESV，运算复杂度均为O(2^56).

Problem5

我们假设M0经过密钥K加密之后的得到的结果为M0‘，M1经过密钥K加密之后的得到的结果为M1‘，M2经过密钥K加密之后的得到的结果为M2‘。因为我们知到M1 = M2 = M，那么经过相同的密钥加密之后，也可以知道M1’ = M2‘ = M’。

对于这一个块加密系统，我们可以得到下面的等式
I V ⊕ M 0 ′ = C 0 ( 1 ) M 0 ⊕ M ′ = C 1 ( 2 ) M ⊕ M ′ = C 2 ( 3 ) IV ⊕ M_0' = C_0 \quad\quad\quad (1)\\ M_0 ⊕ M' = C_1 \quad\quad\quad (2)\\ M ⊕ M' = C_2 \quad\quad\quad (3) IV⊕M0′​=C0​(1)M0​⊕M′=C1​(2)M⊕M′=C2​(3)
将（2）式和（3）式进行异或操作可以消掉M’，得到下式
M 0 ⊕ M ′ ⊕ M ⊕ M ′ = M 0 ⊕ M = C 1 ⊕ C 2 M_0 ⊕ M' ⊕ M ⊕ M' = M_0 ⊕ M = C_1⊕C_2 M0​⊕M′⊕M⊕M′=M0​⊕M=C1​⊕C2​
因为我们已知C1，C2和M，所以可以知道
M 0 = C 1 ⊕ C 2 ⊕ M M_0 = C_1⊕C_2⊕M M0​=C1​⊕C2​⊕M

Problem6

Give a function that is one-way, but not collision-resistant.

模运算是一个非常典型的哈希函数，这个哈希函数就是满足单向性的不满足防碰撞特性，取模函数的具体表示如下所示
h ( n ) = n m o d p h(n) = n\quad mod\quad p h(n)=nmodp
其中p是一个常数，属于这个哈希函数规定的参数，不同的p对应不同的哈希函数。

在这个函数中，给定一个n，我们可以简单地将n带入表达式求出h(n)，但是如果给定一个h值，对应的n值可能是 n = k*p + h，其中k = 0，±1，±2……所以n的取值有无限多种可能，我们不能根据h，反推出n，满足单向性。

但是对于防碰撞性这个函数是不能满足的，因为n = k*p + h，其中k = 0，±1，±2……在经过这个哈希函数映射后都会映射到同一个值，也就是h，也就是说这些n经过这个哈希函数都会发生碰撞，这个函数不满足防碰撞性。

Give a function that is collision-resistant, but not one-way.

我们可以很轻易地举出一个简单的例子，如下所示
h ( n ) = n + 2 h(n) = n + 2 h(n)=n+2
这是一个非常简单的满足防碰撞性但不满足单向性的哈希函数的例子。

对于任给的一个n值，经过哈希函数后的值都不会相等。我们采用反证法证明上述结论
假 设 存 在 n 1 ≠ n 2 , 但 是 h ( n 1 ) = h ( n 2 ) 则 n 1 + 2 = n 2 + 2 , 即 n 1 = n 2 , 矛 盾 假设存在n_1≠n_2,但是h(n_1)=h(n_2)\\ 则n_1 + 2 = n_2 + 2,即n_1 = n_2,矛盾\\ 假设存在n1​​=n2​,但是h(n1​)=h(n2​)则n1​+2=n2​+2,即n1​=n2​,矛盾
所以这个函数是一个具有防冲突性的哈希函数。

但是这个函数并不具有单向性，因为对于任给的函数值h，我们可以轻易地知到这个函数值对应的n = h - 2，所以这个函数是一个不具有单向性但是具有防冲突性的函数。