OMSCS-GA课程笔记05-Randomized Algorithms

这个系列是Gatech OMSCS 高级算法课程(CS 6515: Intro to Grad Algorithms)的同步课程笔记。课程内容涉及动态规划、随机算法、分治、图算法、最大流、线性规划以及NP完备等高级算法的设计思想和相关应用，本节主要介绍随机算法。

随机算法在密码学中有着非常重要的应用。

Modular Arithmetic

在介绍随机算法与密码学的关系前我们需要先来引入模算数(modular arithmetic)的相关概念。对于整数 $x$ 我们定义取模运算mod来获得它关于 $N$ 的余数，如果两个整数 $x$ 和 $y$ 具有相同的余数则称它们关于 $N$ 同余(congruence)：

以除数3为例，通过取模运算可以定义3个同余等价类。

Basic Fact

同余的一个基本性质是如果 $x$ 和 $y$ 以及 $a$ 和 $b$ 分别关于 $N$ 同余等价，则 $x + a$ 和 $y + b$ 同余等价且 $x a$ 和 $y b$ 同余等价。

Modular Exp

模算数的一个重要应用是计算指数的余数。对于n-bit整数 $x$ 和 $y$ ，我们可以通过递推的方法来计算 $x^{y}$ 的余数：

上述算法的复杂度依赖于 $y$ 的大小。更高效的算法是利用平方运算来减少迭代步骤：

Multiplicative Inverse

我们定义mod运算的逆为满足 $x z \equiv 1 mod N$ 的整数，记为 $x \equiv z^{- 1} mod N$ 。

需要注意的是并不是所有的整数都存在逆。

实际上当且仅当 $x$ 和 $N$ 的最大公约数(greatest common divisor, GCD)为1时才存在逆。

GCD

因此计算mod的逆就归结于计算 $x$ 和 $N$ 的最大公约数。关于最大公约数的研究可以追溯到古希腊的欧几里得，他指出 $x$ 和 $y$ 的最大公约数等于 $(x mod y)$ 和 $y$ 的最大公约数：

基于欧几里得定理可以得到计算最大公约数的算法，其复杂度为 $O (n^{3})$ ：


1
2
3
4
5
6
 Euclid(x, y):
  if y == 0:
    return x

  else:
    return Euclid(y, x mod y)

这样就可以计算mod的逆，其复杂度为 $O (n^{3})$ ：


1
2
3
4
5
6
7
 Ext-Euclid(x, y):
  if y == 0:
    return (x, 1, 0)

  else:
    d, alpha', beta' = Ext-Euclid(y, x mod y)
    return (d, beta', alpha' - x//y * beta')

RSA

Fermat’s Little Theorem

在模算数的基础上就可以介绍密码学中重要的RSA算法了，不过在此之前我们还需要引入费马小定理(Fermat’s little theorem)。它指出对于任意质数 $p$ 和小于 $p$ 的整数 $z$ ， $z^{p - 1}$ 与1关于 $p$ 同余：

Euler’s Theorem

欧拉定理(Euler’s theorem)是对费马小定理的推广，它指出互质的整数 $N$ 和 $z$ ， $z^{ϕ (N)}$ 与1关于 $N$ 同余，其中 $ϕ (N)$ 为小于 $N$ 且与 $N$ 互质的整数数量。

如果我们进一步令 $N$ 为两个质数 $p$ 和 $q$ 的积 $N = p q$ ，可以证明 $ϕ (N) = (p - 1) (q - 1)$ 。这样有 $z^{(p - 1) (q - 1)}$ 与1关于 $N$ 同余。

RSA Idea

RSA算法的基本思想是利用欧拉定理来对 $z$ 进行加密。我们取两个质数 $p$ 和 $q$ 并计算它们的积 $N = p q$ ，接下来取关于 $(p - 1) (q - 1)$ 互逆的一对整数 $d$ 和 $e$ 。进行加密时加密方已知 $e$ 和 $N$ ，这样可以计算 $z^{e}$ ；而在解密时解密方知道 $e$ ，利用 $z^{d e}$ 就可以恢复 $z$ 。

Cryptography Setting

在密码学中最常见的一类场景是公开密钥加密(public-key cryptography)。此时数据发送方通过加密函数e()对信息进行加密，而接收方通过解密函数d()进行解密，它们之间的直接通信都是加密后的消息e(m)。同时接收方会公开公钥(public key)，这样任何拥有公钥的人都可以加密，但只有数据接收方能够利用私钥(private key)进行解密。

RSA Protocols

因此数据接收方的任务在于计算公钥和私钥，然后公开公钥并保留私钥用来解密。为此它需要首先选择两个质数 $p$ 和 $q$ ，然后计算与 $(p - 1) (q - 1)$ 互质的 $e$ 用来加密，这样就得到了公钥 $N = p q$ 和 $e$ ，最后计算并保存私钥 $d$ 即可。

对于数据发送方来说，它只需要先获取公钥 $N$ 和 $e$ ，然后对消息 $m$ 进行加密 $y \equiv m^{e} mod N$ ，最后发送加密后的消息 $y$ 即可。

而当接收方需要进行解密时只需要利用私钥计算 $y^{d} mod N = m$ 。

RSA Pitfalls

使用RSA进行加密时需要注意的是保证原始数据 $m$ 和 $N = p q$ 是互质的，而如果它们存在公约数则容易导致一些问题。假设 $m$ 和 $N$ 存在公约数 $p$ ，对于数据接收方仍然可以正确地进行解密，但是任何截获加密数据 $m^{e}$ 的人都可以利用gcd(y, N)来破解 $p$ 进而获得私钥。因此在进行加密时需要注意验证 $m$ 和 $N$ 是否是互质。

另一方面我们还希望原始数据 $m$ 既不是特别大也不是特别小的数字，当 $m$ 特别大或者特别小时都容易导致加密失效。

RSA Recap

总结一下目前为止的内容，整个RSA算法的流程如下：

Random Prime Numbers

整个RSA算法依赖于选取质数 $p$ 和 $q$ ，因此我们需要设计随机质数的生成算法。要生成随机质数我们首先需要生成随机n-bit整数，这个过程比较简单只需要对n-bit随机赋予0或者1即可。然后我们验证这个随机整数是否是一个质数，如果它是质数就得到了一个随机质数，否则重新生成一个新的随机整数再进行判断即可。可以证明n-bit随机整数恰为质数的概率约为 $\frac{1}{n}$ ，因此理论上我们只需要重复生成n次随机整数就可以得到一个随机质数。

要验证一个整数是否是质数则需要费马素性检验(Fermat primality test)。根据费马小定理，任意小于质数 $r$ 的整数 $z$ 一定有 $z^{r - 1} \equiv 1 mod r$ 。因此如果我们能够找到一个小于 $r$ 的整数 $z$ 使得 $z^{r - 1} ≢ 1 mod r$ ，那么 $r$ 一定是一个合数，这样的 $z$ 称为Fermat witness。

可以证明任意合数都至少存在一个Fermat witness。

因此合数的因数一定是Fermat witness，称为trivial Fermat witness。而实际上Fermat witness不一定都是因数，此时则称其为non-trivial Fermat witness。只有trivial Fermat witness的合数称为Carmichael数(Carmichael number)，在使用费马素性检验时它们的性质非常接近于质数，因此也被称为伪质数(pseudo primes)。不过Carmichael数非常少见，在简单情况下我们可以忽略它们的存在。

如果我们忽略Carmichael数的存在可以得到质数的检验算法：

Bloom Filters

Ball into Bins

假设我们有 $n$ 个完全相同的小球与 $n$ 个盒子，每次随机将一个小球置入其中一个盒子中，此时第 $i$ 个盒子中的小球数量是一个随机变量 $load (i)$ 。记盒子中数目最多的小球数为 $max load$ ，它同样是一个随机变量且最大值为 $n$ ，即所有小球同时落入一个盒子中。不过这种情况的概率很低，为 $(\frac{1}{n})^{n}$ 。

要分析 $max load$ 的分布并不容易。首先，前 $\log (n)$ 个小球都落在第 $i$ 个盒子的概率为 $(\frac{1}{n})^{\log n}$ 。

在此基础上可以证明第 $i$ 个盒子中小球数量至少为 $\log (n)$ 的概率小于等于 $(\binom{n}{\log n}) (\frac{1}{n})^{\log n}$ 。

当 $n$ 比较大时组合数具有上界：

(\binom{n}{k}) \approx (\frac{n}{k})^{k} \leq (\frac{n e}{k})^{k}

带入概率上界可以得到：

P \leq (\frac{n e}{\log n})^{\log n} (\frac{1}{n})^{\log n} = (\frac{e}{\log n})^{\log n}

由于 $\frac{e}{\log n}$ 随 $n$ 的增加而减小，我们可以进一步使用常数 $\frac{1}{4}$ 进行放缩。进一步假设 $n > 2^{11}$ 可以得到最终的概率上界 $\frac{1}{n^{2}}$ 。

利用上面的结论可以推导出 $max load$ 至少为 $\log n$ 的概率上界为 $\frac{1}{n}$ ，而它的下界有大概率为 $\frac{\log n}{\log \log n}$ 。

除了随机放置小球外，另一种放置小球的方式是每次随机选择两个盒子然后把小球放到 $load$ 较小的那个盒子中。

可以证明按照这种方式进行放置时 $max load$ 的上界有大概率为 $\log \log n$ 。

Chain Hashing

Hashing在现实生活中有着非常多的应用，比如说可以使用hashing作为容器来保存数据，此时我们需要回答的问题是容器中是否存在某个给定的元素 $x$ 。最常见的实现方法是构造一个数组，其中每个位置对应一个链表。然后设计一个函数 $h (x)$ 将可能的元素 $x$ 映射到链表的编号。这样的实现方式称为chain hashing。假设 $h (x)$ 是一个随机函数，我们可以把链表想象成小球问题中的盒子，而元素 $x$ 则为小球，这样就可以使用上一节的结论来进行分析。

对于chain hashing这种数据结构，检测 $x$ 是否在容器中需要两步：

使用 $h (x)$ 计算链表的编号 $h (x) = i$ 。
检测 $x$ 是否在链表 $H [i]$ 中。

记 $x$ 的所有可能取值数量为 $m$ ，链表的数目为 $n$ 。利用上一小节的结论可以得到每个链表的大小有大概率为 $\log n$ ，即查询的复杂度为 $O (\log n)$ 。

要提升查询的效率可以使用两个 $h (x)$ 函数，每次添加元素时选择 $load$ 较少的那个链表来加入。需要注意的是在进行查询时需要同时检查两个链表中的元素。可以证明此时的查询复杂度为 $O (\log \log n)$ 。

Bloom Filter

Bloom滤波器(Bloom filter)是对chain hashing的一种改进，它可以实现 $O (1)$ 的查询效率而且实现起来非常简单。不过Bloom滤波器仅是概率正确的，存在假阳性的可能性。对于精度没有特别严格要求的场景，Bloom滤波器是一个非常强大的工具。

Bloom滤波器包括两个基本操作，插入insert(x)以及查询query(x)。

在实现时Bloom滤波器使用了一个大小为n的二进制数组。首先把数组的每一位都初始化为0，当我们需要插入 $x$ 时将数组的第 $h (x)$ 位设置为1，而在查询时只需要检测 $H [h (x)]$ 是否为1即可。显然此时两种操作都只需要 $O (1)$ 的复杂度，但查询操作可能会出现假阳性的情况。

要提升系统的鲁棒性可以同时使用k个hashing函数。此时要进行插入和查询则需要同时检查数组的k个可能位置，当数组的k个位置上都为1时说明 $x$ 在容器中。

显然k值对于假阳性的概率有着重要的影响，可以证明出现假阳性的概率约为 $(1 - e^{- \frac{k}{c}})^{k}$ ，这样最优的k值为 $c \ln 2$ 而对应的假阳性概率约为 ${0.6185}^{c}$ 。

Reference

Cryptography