# 9.1

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

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

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

# 9.7

该方案流程如下:

  • Bob 发送xx 给 Alice,xx 是随机选择的模nn 的二次剩余
  • Alice 计算y=x2modny = x^2 \mod{n},并把Cert(A),y{\rm Cert(A)},y 发送给 Bob
  • Bob 验证y2x(modn)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 可以构造出yy',让 Bob 验证yx(modn)y' \equiv x \pmod{n} 是正确的,即 Carol 冒充 Alice 攻击成功

根据欧拉准则可以验证ap211(modp)a^{\frac{p}{2} - 1} \equiv 1 \pmod{p} 算出x2a(modn)x^2 \equiv a \pmod{n}aa,则y=ay' = a

# 10.1

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

bU=αaUmodp=36138bV=αaVmodp=106355bW=αaWmodp=93325\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)

KU,V=bVaUmodp=75452KU,W=bWaUmodp=119360\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)

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

(d) 已知bU,α,pb_U,\alpha,p,要计算出αaUbU(modp)\alpha^{a_U} \equiv b_U \pmod{p}aUa_U,是离散对数问题

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

# 11.1

bU=αaUmodp=7580bV=αaVmodp=22181KU,V=bUaVmodp=bVaUmodp=10141\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

bU=αaUmodp=19392bV=αaVmodp=7592SU=αrUmodp=18143SV=αrVmodp=12K=SUaVbUaVmodp=SVaUbVaUmodp=αrUaV+rVaU=7841\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}