ECDSA安全性分析：加法密钥派生与预签名机制

### ECDSA安全性分析：加法密钥派生与预签名机制 #### 1. ECDSA在EC - GGM模型中的安全性证明 在EC - GGM模型里，生成元G被编码为π(1)，公钥D被编码为π(d)，这里的d是从$Z_q^*$中随机选取的，且假定d ≠ 0。在签名攻击游戏开始时，G和D的这些编码会被提供给攻击者。 攻击者会与群预言机和签名预言机进行一系列交互查询。签名预言机处理消息m时，会像往常一样计算h = Hash(m)，并借助群预言机来计算R = rG的编码。需注意，R = s⁻¹hG + s⁻¹tD，其中(s, t)是签名。为简化，假设签名预言机也会输出R。 签名攻击游戏结束时，攻击者会输出针对消息m*的伪造签名(s*, t*)。接着使用验证算法来验证该签名，先计算h* = Hash(m*)，再利用群预言机计算R* = (s*)⁻¹h*G + (s*)⁻¹t*D的编码。 我们将伪造者分为以下三种类型： - **类型I**：存在签名预言机计算出的某个R，使得R* = ±R。 - **类型II**：对于签名预言机计算出的任意R，R* ≠ ±R，且h* ≠ 0。 - **类型III**：既不属于类型I也不属于类型II。 ##### 懒模拟器 在攻击游戏开始时，我们并非随机选择编码函数π，而是可以逐步构造它。即把π表示为一组随时间增长的对(i, P)，这样的对(i, P)代表关系π(i) = P。这里给出了伪造攻击游戏中群预言机和签名预言机的完整逻辑。 攻击游戏结束时，攻击者输出伪造签名(s*, t*)，验证例程会使用加法查询进行计算，这需要O(log q)次群预言机查询。我们用Ngrp表示攻击者明确进行的群预言机查询总数，这包括验证伪造签名和生成G、D所使用的群预言机查询，但不包括签名查询中使用的查询。用Nsig表示攻击者进行的签名查询次数，并设N := Nsig + Ngrp。 这种懒模拟是完全忠实的。具体而言，使用群预言机的懒模拟进行签名攻击游戏时，任何攻击者的优势与使用原始定义的群预言机时相同。 ##### 符号模拟器 现在定义攻击游戏的符号模拟。此游戏的本质区别在于，Domain(π)现在由形如a + bD的多项式组成，其中a, b ∈ Zq，D是一个不定元，这里D象征性地表示d的值。需注意，π仍需满足编码函数的所有要求。 **引理1**：在懒模拟和符号模拟游戏（如图2和图3所示）中，攻击者的伪造优势差异为O(N²/q)。 **定理1**：设A是如定义2中那样攻击Secdsa的攻击者，且最多进行N次签名或群查询。那么存在攻击者BI、BII和BIII，其运行时间与A基本相同，使得： CMAggmadv[A, Secdsa] ≤ CRadv[BI, Hash] + (4 + o(1))N · RPRadv[BII, Hash] + ZPRadv[BIII, Hash] + O(N²/q) 其证明过程如下： - **类型I伪造者**：在符号模拟器中，若R* = ±R（R由签名预言机产生且唯一），这意味着(s*)⁻¹(h* + t*D) = ±s⁻¹(h + tD)且t* = t。即对于η ∈ {±1}，有(s*)⁻¹(h* + tD) = ηs⁻¹(h + tD)，由此得到两个方程(s*)⁻¹h* = ηs⁻¹h和(s*)⁻¹t = ηs⁻¹t，这两个方程意味着h* = h，即哈希函数Hash出现碰撞，这就是定理中的攻击者BI。 - **类型II伪造者**：假设π⁻¹(R*) = a + bD，由验证方程可知π⁻¹(R*) = (s*)⁻¹(h* + t*D)，所以a = (s*)⁻¹h*，b = (s*)⁻¹t*。结合h* ≠ 0的假设，可知b ≠ 0，a ≠ 0，且t* = h*a⁻¹b。群元素R*必定是攻击者直接通过某个群预言机查询随机生成的。我们利用这个类型II伪造者来破解Hash的随机原像抗性。给定随机的h† ∈ Zq，我们猜测会产生伪造中R*值的群预言机查询，然后运行采样算法计算t† ← h†a⁻¹b，R† $← Samp(t†)。若采样器失败则中止，否则设置R* := R†和t* := t†，按常规流程操作：若攻击者伪造出签名，我们就成功找到h†在Hash下的原像，这就是定理中的攻击者BII。 - **类型III伪造者**：产生h* = 0的伪造签名，这就是定理中的攻击者BIII。 上述分析是基于符号模拟器的。为得到关于懒模拟器的结果，我们使用引理1，从而在定理中得到O(N²/q)这一项。 **注意事项**： - 我们所做的三个假设——抗碰撞性、随机原像抗性和零原像抗性——都是必要条件，因为若其中任何一个不成立，破解该方案就很容易。 - 上述分析表明，即使给攻击者提供“原始”签名预言机（输入是h而非m），ECDSA在相同假设下仍然安全。当然，在这个模型中，伪造的概念必须适当修改，以禁止对任何H(m*)已作为“原始”签名查询提交的消息m*进行伪造。 #### 2. 具有加法密钥派生的ECDSA 我们假定将秘密密钥d ∈ Zp用作主密钥，为“调整值”e ∈ Zq派生形式为d + e的秘密子密钥。对于这样派生的秘密子密钥，我们可以从公钥D计算出相应的派生公共子密钥为D + eG。 若不对调整值的选择加以限制，就无法实现安全性。我们假设任何调整值都必须来自在攻击游戏开始前选定的允许调整值集合E ⊆ Zq。这可以通过多种方式强制执行，其中一种是将调整值作为哈希函数的输出获取，该哈希函数被建模为随机预言机。 定义1（以及定义2）中的CMA安全游戏会被修改，使得签名预言机接收消息m和调整值e。同样，攻击者必须输出针对特定消息m*在特定调整值e*下的伪造签名，且只有当对(m*, e*)未被提供给签名预言机时，该伪造签名才有效。 我们定义CMAggm_akd_adv[A, S, E]为攻击者A在EC - GGM中赢得这个修改后的CMA游戏的优势。 引理1在这种情况下同样成立，处理签名查询(h, e)时，符号模拟器运行与之前相同的算法，但用e + D代替D。 **定理2**：设A是如定义2中那样使用加法密钥派生攻击Secdsa的攻击者，最多进行N次签名或群查询，其中Nsig是签名查询次数。那么存在攻击者BIa、BIb、BII和BIII，其运行时间与A基本相同，使得： CMAggm_akd_adv[A, Secdsa, E] ≤ CRadv[BIa, Hash] + (4 + o(1))Nsig|E| · RPRadv[BIb, Hash] + (4 + o(1))N|E| · RPRadv[BII, Hash] + ZPRadv[BIII, Hash] + O(N²/q) 其证明过程如下： - **类型I伪造者**：当R* = ±R（R由签名预言机产生且唯一）时，意味着(s*)⁻¹(h* + t*(e* + D)) = ±s⁻¹(h + t(e + D))且t* = t。即对于η ∈ {±1}，有(s*)⁻¹(h* + te* + tD) = ηs⁻¹(h + te + tD)，得到两个方