BS Chap 10:Public Key tools

type

status

date

slug

summary

Anonymous key exchange

这一章正式进入公钥密码学的学习。在最开始部分，我们首先来看密钥交换（Key Exchange）相关的一些概念。

什么是密钥交换？我们为什么要做密钥交换？

假设 Alice 和 Bob 是在网上认识的一对陌生人，他们之前从来没有 pre-share 过用来加密会话的密钥，而他们正在使用一个不安全的信道，这使得他们没法在信道上直接暴露他们准备选定的密钥，这时候要怎么做呢？

这时 Alice 和 Bob 就可以使用某种 key exchange protocol，也就是说他们可以轮流给对方发信息，当双方都执行完协议的时候，他们就可以得到同一个密钥。

Protocol transcript 即是 Alice 和 Bob 所发的信息的一个序列，由于他们在发信息的时候会带上一些 randomness，因此对于协议的每次执行，都能得到不同的 transcript。我们可以将 transcript 看成一个随机变量。

“Anonymous” 指的是什么？

这里的匿名性和我们平时遇到的匿名性有一点不同，这里的匿名性指的是 Alice 无法确认与她交互的是不是 Bob，而 Bob 也不能确认对面的人到底是不是 Alice。也就是说这里没办法提供身份的确认。

Attack game

对于 key exchange protocol ，给定一个攻击者，attack game 定义如下：

挑战者让和运行协议，以共享密钥，并把这次协议运行的 transcript 发给

输出

攻破该协议的优势为：

从 attack game 定义可以看出，得到的只是协议的 transcript，也就是说在这里攻击者可以看到协议执行中双方的信息，可以窃听全部信息，但是不能修改或者注入自己的信息，是一种被动攻击。此外，攻击者的优势被描述为他猜出完整的密钥的概率，但在现实世界里，如果攻击者能猜出中一半的比特呢？那这个协议其实就已经不怎么安全了。但按定义来说，这并不算在攻击者的优势中。所以，这个定义其实是很弱的。

One-way trapdoor functions

在这一部分，我们将介绍如何用 One-way trapdoor functions 去构造密钥交换协议。

什么是 One-way trapdoor function

One-way trapdoor function 是能被高效计算，但在没有 trapdoor 的情况下，难以进行逆运算的函数 .但如果我们有 trapdoor，那就可以高效地求逆。

以下给出 Trapdoor function scheme 的形式化定义：

设是有限集，Trapdoor function scheme 定义在上，包含算法 :

是一个概率性的密钥生成算法，生成一个公私钥对

是一个确定性算法，输入为公钥和中的某个元素，输出为中的某个元素

是一个确定性算法，输入为私钥和中的某个元素，输出为中的某个元素

的正确性被定义为：

对的所有可能输出 )，对所有，都有e

在这里，中的算法就是一个 One-way trapdoor function，私钥就是这一函数的 trapdoor，如果没有，就无法进行高效的逆运算（算法）。

注意到对于一个公私钥对，存在逆运算，因此一定是一个单射的函数；但我们并不要求满射，也就是说可以允许有某些没有原像。

Attack game

对于定义在上的 Trapdoor function scheme ，给定攻击者，attack game 定义如下：

挑战者计算：

挑战者将发送给攻击者

输出

攻破的优势为：

注意到在上随机分布，且单射，因此在的 image 中也随机分布。

RSA

著名的 RSA 便是 Trapdoor function scheme 的一个实例，它的命名源于三位作者的首字母。和上面的 scheme 稍有不同，准确地说，RSA 是一个 Trapdoor permutation scheme，也就是说 trapdoor function 的定义域和值域是同一个集合。又由于单射，且定义域和值域相同，所以是一个双射函数，因此称为 permutation。

首先来看 RSA 需要什么参数：我们需要一个长度参数，并且需要一个秘密整数，注意是一个奇数。接下来我们随机生成两个比特长度的不同素数和，其中和都要和互素。

整个 scheme 大概是下面这个样子：

Key generation：输入长度参数和秘密整数，输出和，公钥即为，私钥为 .

Encrypt：输入和需要加密的信息，

Decrypt：输入和需要解密的信息，

我们来看一下 RSA 的正确性：设有两个不同的素数和，且，并且有，那么对于任意，是否都有？

首先，根据欧拉定理，有：

因此，对于任意，都有：

所以：

QED.

看到这里，大家可能会有这样的几个问题：

为什么和都要和互素？

攻击者为什么不能算出私钥中的？

第一个问题涉及一些数论知识，简单来说，就是如果和与不互素，那么就不存在一个，使得。

第二个问题，如果攻击者已知，并且知道，则攻击者算出的前提是至少要已知。但有证明分析出，攻击者从中获取的难度并不比获取和小，而我们认为从中分解出和（大整数分解）是个难题，因此攻击者无法计算出。

最后，通过 RSA，Alice 和 Bob 就可以安全地交换密钥啦。

Diffie-Hellman Key exchange

刚刚我们讨论了用 trapdoor function 构造密钥交换协议，那么密钥交换协议有没有别的构造方法呢？有！接下来的 Diffie-Hellman 就是一个例子。

DH 协议需要生成一个大素数，且存在一个较大的素数，使得整除。我们知道的阶是，那么根据 Sylow’s Theorem，中必定存在一个阶为的循环子群，我们设的一个生成元为，并且公开和。

Alice 和 Bob 用以下方式进行密钥交换：

Alice 计算：，并将发送给 Bob

Bob 计算：，并将发送给 Alice

Alice 计算得到

Bob 计算得到

协议是非常简单直观的，但也非常具有启发性。我们介绍三个和 DH 相关的难题：

离散对数（Discrete logarithm，DL）

在一个阶为素数的循环群中，已知生成元和某一群元，计算出满足是难的。

计算性 Diffie-Hellman（Computation Diffie-Hellman，CDH）

在一个阶为素数的循环群中，已知生成元和群元，，则计算出是难的。

判定性 Diffie-Hellman（Decisional Diffie-Hellman，DDH）

在一个阶为素数的循环群中，已知生成元和群元，，，则判定是否等于是难的。如果等于，那么我们把称为一个 DH-triple。

我们可以考虑上述三个难题的难度：如果能解离散对数问题，那么显然就能解 CDH 和 DDH。而如果能解 CDH，那显然也能解 DDH。

因此上述三个难题的难度：

离散对数的随机自规约（Random self-reducibility)

群中的离散对数难题有一个重要的特性：要么对于中的任意群元，解离散对数都是难的，要么就都是简单的。不存在说中有部分群元很好算离散对数，但另一部分难以计算离散对数。我们通过离散对数的随机自规约去说明上述特性。

首先，什么是随机自规约？随机自规约指的是，对于一个函数，如果存在一个算法对于随机输入，都能高效地以一定概率计算出正确结果，那么就可以构造出一个算法，算法通过调用，就可以在任意输入上以一定概率计算出正确结果。

设在中满足随机分布，是的生成元，并假设算法计算出随机输入的离散对数的概率：，我们构造算法：

输入：

输出：的离散对数或者 fail

在中选择一个随机数：

计算

调用：

如果，输出 fail；否则输出

我们观察算法的构造，重点是要选择一个在中随机分布的随机数，使得在中满足随机分布，接下来调用算法。如果以的概率成功算出了的离散对数，那么就能算出给定输入 的离散对数。

随机自规约的重要性

密码学的基础就是难题：RSA 的安全基于大整数分解难题，DH 的安全基于离散对数问题。但是有一些难题，它们仅仅在最坏情况（worst case）下没有多项式时间解法，而我们想要的是在平均情况下，难题都没有多项式时间的解。

随机自规约性质恰恰就是在告诉我们，如果一个难题满足随机自规约，那么它在平均情况下都是难的，都没有多项式时间的解法，这对构建一个安全的密码学体系来说有着重要的意义。

总结

这一章主要讲了：

密钥交换协议的出发点

用 One-way trapdoor functions 去构造密钥交换协议的实例——RSA

什么是 Diffie-Hellman key exchange，以及相关的三种难题

随机自规约性的意义