动机
知道一个秘密与泄露一个秘密是不同的行为。持有离散对数的用户可以在不发送该对数的情况下证明自己知道它:先承诺一个随机群元素,再回答一个新的挑战。随机承诺使见证(witness)在响应中被隐藏,而对同一承诺回答两个不同的挑战则会暴露见证。理解这两面,就能明白为什么临时随机数与长期密钥同样敏感。
由此得到的三消息协议是签名的数学起点。把验证者的挑战替换为消息与承诺的哈希值,便得到一种非交互的签名规则,但仅有正确性并不能确立不可伪造性。我们将证明确切的交互性质并给出具体的失效例子;完整的随机预言机模型归约既不被假设,也不被悄悄地声称。
定义:交互记录及各自的角色
见证是满足公开关系的值;这里的关系是 。验证者看到公钥与对话中的消息,诚实证明者还知道一个见证。交互记录按顺序保存一次对话,包括挑战。被接受的记录指验证者规定的检验通过。这些词描述数学角色,不自动保证软件实现具备相应性质。
均匀选择标量时,概率空间给每个域元素赋予 的概率。诚实执行中的挑战分布与证明者随机数相互独立。恶意参与者可以按别的规则选择;各定理会明确指出何处需要诚实分布,何处适用于任意被接受的记录。看清这些量词,才能避免把分布模拟误当成对一般攻击的防御保证。
群、见证与交互
设 为素数,设 为恰有 个元素的循环群,采用乘法记法。指数是域 中的元素;单位元记为 。公钥为 ,其中秘密 。群、其元素的规范编码以及 都是公开的。在实际实现中, 中的成员判定与相等判定必须可以高效检查;在下面的协议中,它们都是数学运算。
证明者从 中均匀地抽取 ,并发送 。验证者从 中均匀且独立地抽取挑战 。证明者返回
验证者当且仅当收到的各个值都是合法的群元素或标量,并且 时才接受。值 构成一份交互记录(transcript)。因为两次使用同一随机数而复用 ,并非对两次交互的无害压缩:其后果将被显式计算。
常见错误
(用错误的模数约化响应)
响应 是 的指数,所以只有它模群的阶 的剩余类才有意义;它并不是外层模数下的元素。取模 下由 生成、阶为 的群,并设 、、、、。则 。模 约化得 ,而 ,所以记录通过验证。若改为模 约化,得到 ,而 :诚实的证明者反而被拒绝。不约化 并无害处,因为 ;但以不是 的倍数的数取模就会出错。
定理 4.4.1
(完备性与特殊可靠性)
诚实的证明者总能通过验证。从任意两份接受的交互记录 与 (承诺相同、挑战不同)出发,可以高效地恢复满足 的见证 :
该结论针对的是同一公钥、同一承诺下的两份接受记录;仅有一份接受记录不足以使用这一提取公式。
证明
(把两个验证等式相除)
对于诚实的响应,。对于提取,将两个被接受的等式相除,得到 。因为 在域中非零,所以它有逆元。把等式两边同时取该逆元次幂,得到 。这一代数推导并不要求我们事先知道离散对数。 为素数很关键:在合数模的指数环中,非零的挑战之差不一定可逆。
证明透视
重复的承诺就是公共方程
两个响应包含同一见证的不同倍数,以及完全相同的未知随机数。相减即消去该随机数。若两个承诺不同,则两个响应相减后仍留下两个未知随机数,此提取论证便不再适用。若两个挑战相同,则所需的逆元不存在。这些都是假设条件,而不是记账式的装饰。
模拟诚实验证者
一份交互记录可以看起来真实可信,却并非利用见证生成。这一观察是关于诚实抽样的挑战的精确分布陈述;它还不是关于每一种交互式验证者的陈述。
定理 4.4.2
(诚实验证者交互记录的精确模拟)
对于合法的公钥 ,在 中独立且均匀地选取 ,并令 。所得的交互记录与带有独立均匀挑战的诚实执行具有完全相同的分布,并且总能通过验证。
证明
(随机数与响应之间的双射)
写 。在诚实执行中,数对 在 上均匀分布。映射 是双射,因为 。因此 同样均匀分布。此时承诺为 ,这恰好就是模拟器的输出。验证成立由 的定义直接得出。模拟器并不计算 ;证明只是为了比较分布而用到 在数学上的存在性。
各个值的生成顺序至关重要。在真实交互中,证明者在看到验证者的挑战之前就发送 。若模拟器在选定 之后才选择 ,它能重现最终的诚实交互记录分布,但这本身并不能模拟任意的验证者,因为这种验证者的挑战可以依赖于 及其自身状态。更强的零知识定义及其证明需要额外的工作。
概念视角结构
存在性、知识与分布
因为 生成 ,所以 中每个元素都有某个指数。这一存在性事实并不提供找出该指数的高效算法。特殊可靠性从两份具有特定关系的接受记录中给出这样一个算法。诚实验证者模拟则在没有见证的情况下给出一个不可区分的交互记录分布。这些陈述单独来看都不是计算困难性定理。
例题 4.4.3
(一份完整的小规模交互记录)
在模 的乘法群中,元素 的阶为 :,而其阶既不是 ,也不是素数 的其他任何因数。取 ,则 。取 ,则 。若挑战为 ,则响应为 。验证等式两边在模 下都等于 :,且 。这里的算术有意取得很小,便于手算检查;这样的群不提供任何实际安全性。
例题 4.4.4
(模拟同一份公开交互记录)
保持 、、。直接选取 与 。模拟器计算 。所得交互记录与前一个例子完全相同,而模拟器并不需要找出 。单个吻合的例子只是说明该公式;证明整个分布相等的是上面的双射,而不是这个例子。
一种签名规则及其边界
设 为一个指定的公开函数,它把 的规范编码映射到 。为消息 签名时,抽取一个新的均匀随机数 ,计算 ,令 ,并输出 ,其中 。验证时,根据所给的承诺与消息重新计算 ,检查所有编码与成员资格,并当且仅当 时接受。正确性由前面的等式得出。
哈希输入必须有无歧义的编码。在真实协议中,不同的群元素与消息不得意外地序列化为相同的输入,并且域分隔符与算法标识符需要有约定的格式。对于格式错误的元素或超出范围的标量,应当拒绝,而不是把它们的比特表示当作自动合法的成员。这些检查是“被签名之物”这一定义的一部分;仅仅写出群上的等式并不能提供它们。
常见错误
(只对消息哈希而不包括承诺)
若挑战取为 ,伪造者在选择承诺之前就已知道挑战。对任意消息,它任选 并令 ;于是 ,验证在不知道 的情况下就会接受。这正是以 为挑战运行的诚实验证者模拟器。在模 的小群中取 ,若某消息满足 并选 ,则 ,即上面模拟例子中的交互记录。把 纳入哈希输入,就迫使承诺在挑战被知道之前已经固定。
定理 4.4.5
(两个共用一个随机数的签名会泄露密钥)
假设同一公钥下的两个有效签名使用同一个随机数 ,其挑战满足 ,响应分别为 。则公开的交互记录决定秘密剩余类
若 本身从一个有效响应中被获知,且 ,则 。无论 是否具有任何密码学安全性质,这些陈述都成立。
证明
(特殊可靠性,以及已知的随机数)
第一个结论就是特殊可靠性:重复的随机数给出相同的 。对于第二个结论,将 整理,并对非零挑战取逆。若两个挑战相同,则上面所写的逆元不存在;不能由这些公式推断出秘密。随机数重用在其他方面仍可能是危险的,但那是另一个需要独立论证的命题。
例题 4.4.6
(恢复被重用随机数所保护的秘密)
继续上面的小群例子。用同一个 回答第二个挑战 ,得到 。挑战之差为 ,其逆元为 。因此 ,恢复出了秘密。这里并不假设一个现实的哈希函数可以被迫输出所选的那一对挑战;该计算以两个实际存在的不同挑战为条件。
例题 4.4.7
(为什么看似随机的密钥并不足够)
假设签名者只一次性均匀随机地选取秘密 ,但一个软件故障使同一个随机数被用于两条挑战不同的消息。提取公式恰好返回最初那个随机的 。良好的初始密钥分布并不能弥补随机数重用。反过来,若用带有隐藏偏差或泄露的过程产生不同的随机数,则需要作超出“检查所观察到的两个承诺不同”的分析。
反例模式
验证正确并不蕴含不可伪造性
取公开函数 ,对一切输入都成立。一个从未请求过签名的攻击者任选 ,令 ,并对任意消息输出 。验证会接受,因为 。诚实的签名等式仍然正确,但签名是可伪造的。这个例子排除了仅凭该等式就得出安全性结论的做法;它并不是说每一个非常数哈希函数都是安全的。
证明确立了什么,又没有确立什么
该交互具有完美完备性、上述的两份记录提取性质,以及精确的诚实验证者交互记录模拟器。这些都没有说明多项式时间的攻击者无法伪造签名。这样的定理需要精确的攻击实验、对群的计算性假设,以及对挑战函数适当的模型或具体性质,并配以计入查询次数与概率损失的归约。上面的模拟器不能简单地对一个普通的固定哈希函数进行编程。我们在此不证明这一更强的定理。
均匀性指的是在每次执行中都从整个 中独立抽样。特别地,这一数学版本允许取零;具体的标准可能规定不同的随机数取值域和抽样过程。避免模偏差、保护瞬时状态、防止崩溃后重复使用随机数,以及绑定正确的协议上下文,都是抽象证明所不能担保的实现问题。重放一个旧的有效签名,也不同于对新消息伪造签名:应用可能需要自己的重放策略。
练习
快速检查
(当 时验证一份诚实的交互记录。这一次执行是否揭示 ?)
比较响应与随机数。
解答
响应为 ,且 ,所以验证成功。由于 ,这份记录的响应等于随机数,不含 的任何代数倍数。已知随机数时的提取公式要求 ;这里不能使用。这并不分析跨其他交互的泄露。
快速检查
(对上面模 的群,模拟一份 、 的交互记录。在不使用 的情况下检查验证。)
使用 。
解答
模拟器取 (模 )。交互记录 通过验证,因为 。它由公开信息构造而成,而模拟器的完整分布是由双射证明的,并非由这一个样本证明。
快速检查
(两份接受的交互记录共用 ,在 中响应为 、,挑战为 、。恢复指数,并指出公开的群元素。)
套用特殊可靠性的公式,再计算 模 。
解答
响应之差为 ,挑战之差为 ,其模 的逆元为 。因此恢复的指数为 ,且 。两份记录确实以同一 与同一公钥通过验证,这一假设是必要的;任意的数值对未必是交互记录。这里两者是一致的:两份记录都给出随机数 。
快速检查
(说明当两个挑战相等时,两响应提取公式究竟在哪里失效。它们之差的逆元是否存在?)
看看验证等式对 与 有什么要求。
解答
若 ,则 ,而零在 中没有乘法逆元。对于同一承诺、同一挑战下的两个有效响应,验证等式迫使 (模群的阶),因此相减只得到 。这并不给出 的任何值。
快速检查
(在常数零哈希的反例中,在小群里取 。给出伪造的签名,并验证它对任意消息都满足验证等式。)
当 时,验证等式化为 。
解答
取 ,输出 。验证者得到 ,并检查 (模 )。该签名对每条消息都能通过验证,既不需要任何签名查询,也不需要知道秘密指数。