阅读下列材料,回答问题
定义1(椭圆曲线与点加法) 设 p 为素数,a,b 为整数且满足 $4a^3+27b^2 \not\equiv 0 \pmod p$。椭圆曲线 E 是所有满足方程
$$y^2 \equiv x^3+ax+b \pmod p$$的点 (x,y) 与一个特殊点 O(称为无穷远点)构成的集合。在 E 上定义加法运算 $\oplus$:
- O 为单位元,即对任意 $P\in E$,有 $P \oplus O = P$;
- 对 $P=(x_1,y_1)\neq O$,其逆元 $\ominus P = (x_1, -y_1 \bmod p)$;
- 设 $P=(x_1,y_1),\, Q=(x_2,y_2)$ 且 $P \neq \ominus Q$。若 $P \neq Q$,令 $\lambda \equiv (y_2-y_1)(x_2-x_1)^{-1} \pmod p$;若 $P=Q$ 且 $y_1 \neq 0$,令 $\lambda \equiv (3x_1^2+a)(2y_1)^{-1} \pmod p$。则 $P \oplus Q = (x_3,y_3)$,其中 $$x_3 \equiv \lambda^2 - x_1 - x_2 \pmod p,\quad y_3 \equiv \lambda(x_1-x_3) - y_1 \pmod p .$$ 定义标量乘法:$nP = \underbrace{P \oplus P \oplus \cdots \oplus P}_{n\text{个}}$。
定义2(椭圆曲线密钥交换) 双方公开参数 $p,a,b$ 及基点 $G \in E$。Alice 选取私钥 $d_A$,计算公钥 $P_A = d_A G$;Bob 选取私钥 $d_B$,计算公钥 $P_B = d_B G$。交换公钥后,双方计算共享密钥点 $K = d_A P_B = d_B P_A$,并取其 $x$ 坐标 $x_K$ 作为后续对称密钥种子。
定义3(矩阵分组密码) 设 $q$ 为素数,明文空间为 $\{0,1,\dots,q-1\}^2$ 中的列向量。取对称密钥 $k = x_K \bmod q$,定义加密矩阵
$$A_k = \begin{pmatrix} k & 1 \\ 1 & k \end{pmatrix} \pmod q .$$对明文向量 $\boldsymbol{m}$,密文 $\boldsymbol{c} = A_k \boldsymbol{m} \bmod q$。解密时,若行列式 $\Delta = k^2-1 \not\equiv 0 \pmod q$,则
$$A_k^{-1} \equiv \Delta^{-1} \begin{pmatrix} k & -1 \\ -1 & k \end{pmatrix} \pmod q,$$其中 $\Delta^{-1}$ 为 $\Delta$ 模 $q$ 的乘法逆元。解密计算 $\boldsymbol{m} = A_k^{-1} \boldsymbol{c} \bmod q$。
定义4(信息熵与完善保密性) 设离散随机变量 $X$ 的分布为 $P(X=x_i)=p_i$,定义其熵为
$$H(X) = -\sum_i p_i \log_2 p_i \quad (\text{规定 }0\log_2 0 = 0).$$条件熵定义为 $H(X|Y) = \sum_y P(Y=y)\, H(X|Y=y)$,其中 $H(X|Y=y)$ 是在条件 $Y=y$ 下 $X$ 的熵。若对于明文随机变量 $M$ 和密文随机变量 $C$ 满足 $H(M|C) = H(M)$,则称该加密系统具有完善保密性。
结合以上定义,解答下列问题:
(1)取 $p=5,\;a=1,\;b=1$,椭圆曲线 $E: y^2 \equiv x^3+x+1 \pmod 5$,基点 $G=(0,1)$。 (i) 验证 $G$ 在曲线 $E$ 上; (ii) 若 Alice 选取私钥 $d_A=2$,Bob 选取私钥 $d_B=3$,求 Alice 的公钥 $P_A$、Bob 的公钥 $P_B$,以及双方分别计算出的共享密钥点 $K$ 的坐标,并提取 $k = x_K \bmod 5$。
(2)在矩阵分组密码中,取 $q=5$,对称密钥 $k$ 为上述共享密钥的 $x$ 坐标模 $5$。已知明文向量 $\boldsymbol{m} = \begin{pmatrix} 4 \\ 3 \end{pmatrix}$。 (i) 求密文 $\boldsymbol{c}$; (ii) 写出解密矩阵 $A_k^{-1} \pmod 5$,并验证 $\boldsymbol{m}$ 可从 $\boldsymbol{c}$ 解密还原。
(3)假设攻击者截获密文,并知悉系统参数。从攻击者视角,密钥 $k$ 等可能取 $2$ 或 $3$;明文 $M$ 等可能取自集合
$$S = \left\{ \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \end{pmatrix} \right\},$$且 $k$ 与 $M$ 相互独立。 (i) 求明文熵 $H(M)$ 及密文熵 $H(C)$; (ii) 求条件熵 $H(M|C)$,并判断该系统是否具有完善保密性;若不具备,请说明其安全风险。

