密码学部分题目解答

题目摘录自:密码学原理与实践(第三版)[加]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\]

发表评论

电子邮件地址不会被公开。 必填项已用*标注