【密码学】8. 密码协议

密码协议

中国剩余定理（数论基础）

1. 核心用途
   • 重构数：已知一个数关于若干两两互素数的同余类，可唯一确定该数。
   • 大数运算简化：将大数用其关于小互素数的同余类表示，通过小数运算实现大数运算。
2. 直观例子
   • 例 1：已知某数模 2 余 0、模 5 余 3，可确定该数为 8（1~10 范围内唯一解）。
   • 例 2：15 以内的数可通过模 3（行号）和模 5（列号）的同余类表示（如 12 mod 3=0、mod 5=2，对应第 0 行第 2 列），通过行号和列号的运算（如 12+13 对应行号 0+1=1、列号 2+3=5≡0 mod5，对应第 1 行第 0 列的 10）实现大数运算。
   • 物不知数问题：求解方程组$x\hat{a}‰¡2\mathrm{mod}3$，$x\hat{a}‰¡3\mathrm{mod}5$，$x\hat{a}‰¡2\mathrm{mod}7$，通过构造法得解 23（小于 105 的唯一解）。
3. 定理内容
   设$m_1,m_2,...,m_k$是两两互素的正整数，$M=m_1{m}_2...m_k$，则同余方程组$\{\begin{array}{l}x\hat{a}‰¡a_1\mathrm{mod}{m}_1\\ x\hat{a}‰¡a_2\mathrm{mod}{m}_2\\ ...\\ x\hat{a}‰¡a_k\mathrm{mod}{m}_k\end{array}$对模$M$有唯一解：$x=(a_1{M}_1{e}_1+a_2{M}_2{e}_2+...+a_k{M}_k{e}_k)\mathrm{mod}M$
   其中，$M_i=M/m_i$，$e_i$满足$M_i{e}_i\hat{a}‰¡1\mathrm{mod}{m}_i$（即$e_i$是$M_i$模$m_i$的逆元）。
4. 推论（模运算性质）
   若$A=(a_1,a_2,...,a_k)$，$B=(b_1,b_2,...,b_k)$（其中$a_i,b_i$分别为$A,B$模$m_i$的同余类），则：
   • $(A+B)\mathrm{mod}M=((a_1+b_1)\mathrm{mod}{m}_1,...,(a_k+b_k)\mathrm{mod}{m}_k)$
   • $(A-B)\mathrm{mod}M=((a_1-b_1)\mathrm{mod}{m}_1,...,(a_k-b_k)\mathrm{mod}{m}_k)$
   • $(A\tilde{A}—B)\mathrm{mod}M=((a_1\tilde{A}—b_1)\mathrm{mod}{m}_1,...,(a_k\tilde{A}—b_k)\mathrm{mod}{m}_k)$

零知识证明

零知识证明指证明者（P）能向验证者（V）证明自己知道某秘密，且不泄露任何与秘密相关的信息。

1. 零知识洞穴协议（直观例子）
   • 场景：洞穴深处 C、D 间有一扇需秘密咒语打开的门，P 知道咒语，需向 V 证明但不泄露咒语。
   • 步骤：
     ① P 进入洞穴，随机选择 C 或 D；
     ② V 随机要求 P 从 A 或 B 出来；
     ③ 若 P 知道咒语，可根据 V 的要求从指定出口出来（若在 C 则直接从 A 出，若在 D 则开门到 C 再从 A 出，反之亦然）；
     ④ 重复多次，若 P 均能满足要求，V 可相信 P 知道咒语。
2. 破译 RSA 能力的零知识证明协议
   • 场景：Alice 知道 Carol 的 RSA 私钥$d$，需向 Bob 证明但不泄露$d$。
   • 步骤：
     ① Alice 与 Bob 商定随机数$k,m$，满足$km\hat{a}‰¡e\mathrm{mod}\ddot{I}†(n)$（$e$为 Carol 的公钥，$n$为模数）；
     ② 共同生成随机密文$C$；
     ③ Alice 用$d$计算$M=C^d\mathrm{mod}n$，再计算$X=M^m\mathrm{mod}n$并发送给 Bob；
     ④ Bob 验证$X^k\mathrm{mod}n=C$（因$X^k=(M^m{)}^k=M^{km}=M^e=(C^d{)}^e=C^{de}=C\mathrm{mod}n$），若成立则相信 Alice 知道$d$。

不经意传输

指发送者（A）以特定概率向接收者（B）传递秘密，B 知道是否收到秘密，但 A 不知道 B 是否收到。

1. 基于大数分解问题的不经意传输协议
   • 场景：A 传递秘密为大整数$n=pq$（两素数积）的因数分解。
   • 原理：已知某数模$n$的两个不同平方根，可分解$n$。
   • 步骤：
     ① B 随机选$x$，发送$x^2\mathrm{mod}n$给 A；
     ② A 计算$x^2\mathrm{mod}n$的 4 个平方根$\hat{A}\pm x,\hat{A}\pm y$，随机发送一个给 B；
     ③ B 检查收到的数是否与$\hat{A}\pm x$同余：若同余，未获新信息；否则，获得两个不同平方根，可分解$n$（概率 1/2）。
2. 基于离散对数问题的不经意传输协议（非交互）
   • 系统参数：大素数$p$，GF(p)−{0}GF(p)-\{0\}GF(p)−{0}的生成元$g$，大素数$c$（离散对数未知）。
   • B 的密钥生成：随机选比特$i$和$x$，计算$y_i=g^x$，$y_{1-i}=c\hat{A}\cdot (g^x{)}^{-1}$；公钥为$(y_0,y_1)$，私钥为$(i,x)$（B 仅知$y_i$的离散对数）。
   • 协议（二传一）：
     ① A 随机选$k_0,k_1\hat{a}ˆˆ[0,p-2]$，计算$c_j=g^{k_j}$，$d_j=y_j^{k_j}$，$m_j=s_j\hat{a}\check{S}•d_j$（$s_0,s_1$为 A 的两个秘密，⊕为异或），发送$c_0,c_1,m_0,m_1$给 B；
     ② B 用私钥$(i,x)$计算$d_i=y_i^{k_i}=g^{x\hat{A}\cdot k_i}=c_i^x$，再得$s_i=m_i\hat{a}\check{S}•d_i$（无法获取$s_{1-i}$，因不知$y_{1-i}$的离散对数）。
3. “多传一” 不经意传输协议
   • 基于单向函数：
     ① A 告知 B 单向函数$f$，保密$f^{-1}$；
     ② B 想获取秘密$s_i$，选$x_1,...,x_k$，发送$(y_1,...,y_k)$（其中$y_i=f(x_i)$，$y_j$为随机数$j\hat{a}‰i$）；
     ③ A 计算$z_j=f^{-1}(y_j)$，发送$z_j\hat{a}\check{S}•s_j$给 B；
     ④ B 用$z_i=x_i$得$s_i=z_i\hat{a}\check{S}•(z_i\hat{a}\check{S}•s_i)$，A 不知 B 获取的是哪个秘密。
   • 基于大数分解：
     ① A 构造$k$个 RSA 体制（$n_j=p_j{q}_j$，$p_j\hat{a}‰¡q_j\hat{a}‰¡3\mathrm{mod}4$），发送加密密钥$(e_j,n_j)$及加密秘密$s_j^{e_j}\mathrm{mod}{n}_j$；
     ② B 选$x_j$，计算$x_j^2\mathrm{mod}{n}_j$及 Jacobi 符号：若想获取$s_i$，发送$(x_i^2\mathrm{mod}{n}_i,J(x_i,n_i))$和$(x_j^2\mathrm{mod}{n}_j,-J(x_j,n_j))$（$j\hat{a}‰i$）；
     ③ A 返回与接收的 Jacobi 符号一致的平方根；
     ④ B 通过$x_i$和收到的平方根分解$n_i$，得$s_i$（$j\hat{a}‰i$无法分解）。
4. 改进的 “多传一” 不经意传输（保护双方隐私）
   • 系统参数：$q$为大素数，$G_q$为$q$阶群，生成元$g,h$；A 的秘密$m_1,...,m_n\hat{a}ˆˆG_q$，B 的选择$\hat{I}\pm$。
   • 步骤：
     ① B 发送$y=g^r{h}^{\hat{I}{\pm }^{\prime }}$，$y^{\prime }=g^{r^{\prime }}{h}^{\hat{I}\pm }$（$r,r^{\prime },\hat{I}{\pm }^{\prime }\hat{a}ˆˆZ_q$随机）；
     ② A 发送随机$c\hat{a}ˆˆZ_q$；
     ③ B 发送$z_1=(r+r^{\prime }c)\mathrm{mod}q$，$z_2=(\hat{I}\pm +\hat{I}{\pm }^{\prime }c)\mathrm{mod}q$；
     ④ A 验证$y\hat{A}\cdot y^{\prime c}=g^{z_1}{h}^{z_2}$，若通过，发送$c_i=(g^{k_i},m_i\hat{A}\cdot (y/h^i{)}^{k_i})$（$k_i\hat{a}ˆˆZ_q$随机）；
     ⑤ B 用$c_{\hat{I}}\pm =(a,b)$计算$m_{\hat{I}}\pm =b/a^r$（因$a=g^{k_{\hat{I}}\pm }$，$b=m_{\hat{I}}\pm \hat{A}\cdot (y/h^{\hat{I}}\pm {)}^{k_{\hat{I}}\pm }=m_{\hat{I}}\pm \hat{A}\cdot g^{r{k}_{\hat{I}}\pm }$，故$b/a^r=m_{\hat{I}}\pm$）。

比特承诺

承诺者（A）向验证者（B）承诺一个比特 / 消息，承诺后不可篡改，公开时可验证真实性。

1. 基于对称加密的比特承诺协议
   • 步骤：
     ① B 生成随机比特串$r$，发送给 A；
     ② A 选密钥$k$和承诺比特$b$，用对称加密$E$计算$c=E_k(r,b)$，发送$c$给 B；
     ③ 公开时，A 发送$k$和$b$；B 用$k$解密，验证$r$和$b$的一致性。
2. 基于单向函数的比特承诺协议
   • 步骤：
     ① A 生成随机数$r_1,r_2$，计算$h=H(r_1,r_2,M)$（$H$为单向函数 / Hash 函数），发送$h$和$r_1$给 B；
     ② 公开时，A 发送$r_2$和消息$M$；B 计算$H(r_1,r_2,M)$，与$h$比对验证。
3. 基于离散对数的 Pedersen 承诺（消息承诺）
   • 系统参数：大素数$p=2q+1$（$q$为大素数），$G_q$为$Z_p^{\ast }$的$q$阶子群，生成元$g$。
   • 步骤：
     ① B 发送$G_q$中随机元素$h$给 A；
     ② A 选承诺密钥$r\hat{a}ˆˆZ_q^{\ast }$，计算承诺值$C=g^x{h}^r\mathrm{mod}p$（$x$为消息），发送$C$给 B；
     ③ 公开时，A 发送$x$和$r$；B 验证$C=g^x{h}^r\mathrm{mod}p$。
   • 性质：隐藏性（无法从$C$推出$x$）、约束性（基于离散对数难题，A 无法篡改$x$）。

其他协议相关概念

1. 防止重放攻击：通过时间戳、随机数等机制，避免攻击者重复发送截获的协议消息以欺骗合法方。
2. 密钥确证：协议参与方验证对方是否真正掌握协商的密钥，确保密钥一致性和安全性。
3. 证书与可信第三方（TA）：TA 负责初始化发放证书（含用户公钥及验证签名算法），仅在纠纷时参与，密钥协商过程无需 TA 在线；证书确保用户身份真实性（发放时 TA 验明身份）。