2022.5.21 密码学作业

# 9.1

证明不可能设计出一个安全的基于随机挑战的仅含有两个消息流的身份识别方案

证明：若基于随机挑战的仅含有两个消息流的身份识别方案仅基于随机挑战$r$ 加密，敌手可以主动通过并行会话攻击来攻破

若基于随机挑战的仅含有两个消息流的身份识别方案同时对身份信息$\rm ID$ 加密，敌手可以被动通过中转通话双方的信息来收集信息修改信息

# 9.7

该方案流程如下：

• Bob 发送$x$ 给 Alice，$x$ 是随机选择的模$n$ 的二次剩余
• Alice 计算$y = x^2 \mod{n}$，并把${\rm Cert(A)},y$ 发送给 Bob
• Bob 验证$y^2 \equiv x \pmod{n}$ 是否成立，若成立，Bob 接受；否则，Bob 拒绝

graph LR;

Bob -- x --> Alice;

Alice -- y = x^2  mod n, Cert --> Bob

如果此时有一个攻击者 Carol 在中间监听 Alice 和 Bob 的通话

graph LR;

Bob -- x --> Carol -- x --> Alice;

Alice -- y = x^2  mod n, Cert --> Carol;

Carol -- y' = x^2  mod n, Cert --> Bob

如果 Carol 可以构造出$y'$，让 Bob 验证$y' \equiv x \pmod{n}$ 是正确的，即 Carol 冒充 Alice 攻击成功

根据欧拉准则可以验证$a^{\frac{p}{2} - 1} \equiv 1 \pmod{p}$ 算出$x^2 \equiv a \pmod{n}$ 的$a$，则$y' = a$

# 10.1

(a) 根据 Diffie-Hellman KPS 定义可以得到

$$\begin{aligned} b_U & = \alpha^{a_U} \mod{p} = 36138 \\ b_V & = \alpha^{a_V} \mod{p} = 106355 \\ b_W & = \alpha^{a_W} \mod{p} = 93325 \\ \end{aligned}$$

(b)

$$\begin{aligned} K_{U,V} = b_V^{a_U} \mod{p} = 75452 \\ K_{U,W} = b_W^{a_U} \mod{p} = 119360 \\ \end{aligned}$$

(c)

$$\begin{aligned} K_{U,V} = b_U^{a_V} \mod{p} = 75452 = b_V^{a_U} \mod{p} \end{aligned}$$

(d) 已知$b_U,\alpha,p$，要计算出$\alpha^{a_U} \equiv b_U \pmod{p}$ 的$a_U$，是离散对数问题

因为$p-1$ 本身极容易分解，可以利用 Shanks 算法或者 Pohlig-Hellman 算法迅速得到答案

# 11.1

$$\begin{aligned} b_U & = \alpha^{a_U} \mod{p} = 7580 \\ b_V & = \alpha^{a_V} \mod{p} = 22181 \\ K_{U,V} & = b_U^{a_V} \mod{p} = b_V ^{a_U} \mod{p} = 10141 \end{aligned}$$

# 11.3

$$\begin{aligned} b_U & = \alpha^{a_U} \mod{p} = 19392 \\ b_V & = \alpha^{a_V} \mod{p} = 7592 \\ S_U & = \alpha^{r_U} \mod{p} = 18143 \\ S_V & = \alpha^{r_V} \mod{p} = 12 \\ K & = S_U^{a_V}b_U^{a_V} \mod{p} = S_V^{a_U}b_V^{a_U} \mod{p} = \alpha^{r_Ua_V+r_Va_U} = 7841 \\ \end{aligned}$$