题目摘录自：密码学原理与实践（第三版）[加]Douglas R. Stinson 著 冯登国 等译
\(\)
4.13 假定\((P,C,K,\varepsilon ,D)\)是一个内嵌式密码体制，其中\(P=C={{\{0,1\}}^{m}}\)。令\(n\ge 2\)和\(m\ge 3\)均为整数，定义Hash函数族\((X,Y,K,H)\)如下（\(X={{({{\{0,1\}}^{m}})}^{n}}\)，\(Y={{\{0,1\}}^{m}}\)）:
\[{{h}_{K}}({{x}_{1}},\cdots ,{{x}_{n}})={{e}_{k}}({{x}_{1}})+3{{e}_{k}}({{x}_{2}})+\cdots +(2n-1){{e}_{k}}({{x}_{n}})\bmod {{2}^{m}}\]
(a)当n为奇数时，证明该Hash函数族存在(1,2)假冒者。
(b)当n=2时，证明该Hash函数族存在如下的(1/2,2)假冒者：
1.求\(({{x}_{1}},{{x}_{2}})\)和\(({{x}_{2}},{{x}_{1}})\)的MAC，其中\({{x}_{1}}\ne {{x}_{2}}\)。假定\(a={{h}_{K}}({{x}_{1}},{{x}_{2}})\)和\(b={{h}_{K}}({{x}_{2}},{{x}_{1}})\)。
2.证明恰有八个有序对\(({{y}_{1}},{{y}_{2}})\)满足：\({{y}_{1}}={{e}_{K}}({{x}_{1}})\),\({{y}_{2}}={{e}_{K}}({{x}_{2}})\)且与给定的MAC值a和b相一致。
3.对\({{y}_{1}}\)随机选择八个可能的值之一，定义\(y=\text{4}{{y}_{1}}\bmod {{2}^{m}}\)，并输出可能的假冒\(({{x}_{1}},{{x}_{2}})\)，y。证明：该假冒有效的概率为1/2。
(c)证明该Hash函数族存在(1,3)假冒者：对任意的消息\(({{y}_{1}},\cdots ,{{y}_{n}})\)，均可假冒MAC。
参考解答
(a)
当\(n=2k+1\) 时，\(\gcd (2k+1,{{2}^{m}})=1\) (奇数与偶数互素)
所以\(\gcd ({{n}^{2}},{{2}^{m}})=1\)，即存在\({{({{n}^{2}})}^{-\text{1}}}\) 使得\({{({{n}^{2}})}^{-\text{1}}}{{n}^{2}}\equiv \text{1 mod }{{2}^{m}}\)
那么\[H={{h}_{k}}(\overbrace{x,x,\cdots ,x}^{n*x})={{e}_{k}}(x)+3{{e}_{k}}(x)+\cdots +(2n-1){{e}_{k}}(x)={{n}^{2}}{{e}_{k}}(x)\text{ mod }{{2}^{m}}\]
只需要求出\({{({{n}^{2}})}^{-\text{1}}}\)，就可以求得\[{{e}_{k}}(x)=H{{({{n}^{2}})}^{-\text{1}}}\text{ mod }{{2}^{m}}\]
同理，也可以求得\({{e}_{k}}(y)\)
这样就可以伪造\[{{h}_{k}}(\overbrace{x,x,\cdots ,x}^{(n-1)*x},y)={{(n-1)}^{2}}{{e}_{k}}(x)+(2n-1){{e}_{k}}(y)\text{ mod }{{2}^{m}}\]
(b)
1.\[a={{h}_{K}}({{x}_{1}},{{x}_{2}})={{e}_{K}}({{x}_{1}})+3{{e}_{k}}({{x}_{2}})\bmod {{2}^{m}}\]\[b={{h}_{K}}({{x}_{2}},{{x}_{1}})={{e}_{K}}({{x}_{2}})+3{{e}_{k}}({{x}_{1}})\bmod {{2}^{m}}\]
2.\[\left\{\begin{array}{lr}
a={{y}_{1}}+3{{y}_{2}}\bmod {{2}^{m}} \\
b=3{{y}_{1}}+{{y}_{2}}\bmod {{2}^{m}} \\
\end{array}
\right.
\Rightarrow
\left\{
\begin{array}{lr}
8{{y}_{1}}=a-3b\bmod {{2}^{m}} \\
{{y}_{2}}=b-3{{y}_{1}}\bmod {{2}^{m}} \\
\end{array}
\right.\]
由于\(m\ge 3\)，\(\gcd ({{2}^{m}},8)=8\)对于方程\[8{{y}_{1}}=a-3b\bmod {{2}^{m}}\]可以求出其通解为\[{{y}_{1}}={{y}_{10}}+k\frac{{{2}^{m}}}{\gcd ({{2}^{m}},8)=8},k=0,1,2,3,4,5,6,7\]
其中\({{y}_{1\text{0}}}\)是方程的一个特解
共8个解，因此对应\({{y}_{2}}\)八个解
3.由于\({{h}_{K}}({{x}_{1}},{{x}_{1}})=4{{e}_{K}}({{x}_{1}})=4{{y}_{1}}=y\)，由2 \(8{{y}_{1}}=a-3b\bmod {{2}^{m}}\)，代入得
\[2y=a-3b\bmod {{2}^{m}}\]
由于\(\gcd ({{2}^{m}},2)=2\)，该方程有两个解，其中一个是正确的Hash值。当解出方程的两个解时，给出正确的假冒的概率是1/2
(c)构造：\[a={{h}_{K}}(\overbrace{x,x,\cdots ,x}^{n*x})={{h}_{K}}({{x}^{n}})={{n}^{2}}{{e}_{K}}(x)\]\[b={{h}_{K}}(\overbrace{{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{n-1}}}^{(n-1)*{{y}_{i}}},x)=\sum\limits_{i=i}^{n-1}{(2i-1){{e}_{K}}({{y}_{i}})}+(2n-1){{e}_{K}}(x)\]\[c={{h}_{K}}(\overbrace{x,x,\cdots ,x}^{(n-1)*x},{{y}_{n}})={{h}_{K}}({{x}^{n-1}},{{y}_{n}})={{(n-1)}^{2}}{{e}_{K}}(x)+(2n-1){{e}_{K}}({{y}_{n}})\]可以伪造出\[{{h}_{K}}(\overbrace{{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{n}}}^{n*{{y}_{i}}})=\sum\limits_{i=i}^{n}{(2i-1){{e}_{K}}({{y}_{i}})}=b+c-a\]