数论与群论密码学-07-公钥密码系统及RSA加密算法

公钥密码系统

如上一节所述,这里给出对公钥密码系统的概述以及一个实际的例子。

与先前描述的对称/古典的密码系统相对,公钥密码系统中所用于加密/解密的密钥(因此这对密钥所指示的函数)是不同的。我们可以概念地认为,公钥密码系统中加密的算法是公开的,也即此信息可为通信第三方所知。而解密的算法是私密的,确切来说仅为收信人所知。由此一来我们可以注意到另一种意义上的不对称性:密文仅可由收信人解密,而第三方,甚至于发信人都做不到这一点。因此公钥密码系统所建立的秘密信道是单向的。当然我们可以方便地重复两次同样的方法来建立双向的信道。

为了实现上述要求,我们需要一个被称之为陷阱门的函数:要求 \(f(x)\) 可以被轻易地计算。具体地说,至少可在多项式时间内计算。而 \(f^{-1}(x)\) 在合理的时间内(密文所携带的消息仍然有价值的时间内)不可被计算,除非有密文本身以外的信息。在见到实际的例子之前,这样的描述也许会显得十分抽象。我们可以这么来理解:函数 \(f\) 像陷阱门一样,掉进去容易,然而没有额外的一点帮助想从内部开门是十分困难的。

最后,我们定义协议为人(或计算机)与彼此通信时所遵守的一系列有序的步骤。

下面给出一个实际的公钥密码系统。值得注意的是,该系统并非是类似于前文中的数个系统那样的玩具。

RSA加密算法

概况性地来讲,RSA加密算法的概念如下:用户 A 有一个形如 \((n_A, e_A)\) 的公钥以及一个形如 \(d_A\) 的私钥。所谓公钥,是尽人可知意思。例如,A 可将其公钥公开发表在网络上,使得任何想向 A 发送信息的用户 B 皆可使用此密钥加密欲发送给 A 的信息。而收到加密信息的 A 则使用仅为其所知的私钥 \(B\) 解密信息。

如此通信双方仅需大方地在不安全的信道上交换各自的公钥,随后将欲发送的信息由对方的公钥加密,并用自己的私钥解密收到的信息。一个形象地比喻是,欲收信方公开发放锁而保留钥匙,而送信方用此公开可得的锁加密信息。如此一来由于解锁的钥匙是私密的,任何第三方,甚至是送信方本人都没有解密的能力。

接下来给出对 RSA 加密算法形式化的描述:

收信方 A 准备两不同的素数 \(p, q\),设 \(n := p \cdot q\)
准备数 \(e\) 使得其满足以下要求: \[1 < e < n, k = (p-1)(q-1) = \phi(n), gcd(e, k) = 1\] 准备数 \(d\) 使得 \(d \cdot e \equiv 1 \pmod k\)。前述要求保证这样的 \(d\) 是存在的。

A 将数 \((n, e)\) 公开发表。若 B 希望向 A 发信,其可获取这一对数字。 B 将信息以某种公开的方法编码并分组为 \(m_1, \cdots, m_r\),其中 \(m_i < n\)。 B 计算 \(M_i := m_i^e \bmod n\) 并将 \(M_1, \cdots, M_r\) 按序发送给 A.

A 收到信息后,计算 \(m_i' := M_i^d\),则有 \(m_i' = m_i\).

我们需要考虑如下几个问题:

  1. 何以使 RSA 构成一个密码系统?即为何有 \(m_i' = m_i\)?我们稍后将给出对此的证明。
  2. 何以使 RSA 是实际的?我们注意到,加密算法可以简单地通过模运算实现。特别地,该实现的效率可由模幂算法保证。类似地,在 \(d_A\) 已知的情况下,解密算法也可被高效地计算。
  3. 何以使 RSA 是安全的? RSA 的安全性来自于大数分解的困难性。当然随后我们将看到,对 \(p, q\) 不当的选取会于此造成安全上的漏洞。

以上提到的该算法的正确性(即对于 \(m_i' = m_i\) 的断言)由费马定理保证。下面为其于第三节的重复:

\(p\) 为素数,则

\[ \forall m\in \mathbb{Z}, m^{p-1} \equiv 1 \pmod p \]

等价地,有

\[ \forall m\in \mathbb{Z}, m^p \equiv m \pmod p \]

\(n := p \cdot q\),其中 \(p, q\) 为不同的素数,
\(k := (p-1)(q-1) = \phi(n)\),则
\(a \equiv 1 \pmod k\),有

\[ \forall m \in \mathbb{Z}, m^a \equiv m \pmod n \tag{1} \]

特别地,若 \(e\in\mathbb{Z}, gcd (e, k) = 1\)
\(\exists d, e \cdot d \equiv 1 \pmod k\),于是有

\[ \forall m\in\mathbb{Z}, (m^e)^d \equiv m \pmod n \tag{2} \]

该从理保证了 RSA 是一个密码系统。

我们使用费马定理证明上述从理。

首先最后一句陈述中的 \(\exists d, e \cdot d \equiv 1 \pmod k\) 可由拓展欧几里得算法证明,而式 (2) 可由式 (1) 直接导出,因为有 \((m^e)^d = m^{ed}\)

为了证明 (1),根据中国剩余定理(或者欧几里得引理),我们仅需证明

\[ m^a \equiv m \pmod p \text{ 且 } m^a \equiv m \pmod q \tag{$\star$} \]

为了证明式 (\(\star\)) 中的第一个同余,考虑
1. \(p \mid m\)
\(\quad \implies m \equiv 0 \pmod p\)
\(\quad \implies m^a \equiv 0 \pmod p\)
\(\quad \implies m^a \equiv m \pmod p\)
2. \(p \nmid m\)
根据费马,有
\(\quad m^{p-1} \equiv 1 \pmod p\)
根据假设,有

\[ \begin{aligned} a &= 1 + kt = 1 + (p-1)\underbrace{(q-1)t}_{s}\\ &= 1 + (p-1) s \end{aligned} \]

于是

\[ \begin{aligned} m^a = m^{1 + (p-1)s} = m \cdot m^{(p-1)s} &= m \cdot (m^{p-1})^s\\ \text{根据费马} &\equiv m \cdot 1 \pmod p\\ &\equiv m \pmod p \end{aligned} \]

同理可证第二个同余。

RSA 的设计特点

密钥生成

  1. 随机生成一数,使用后文将给出的素数判别测试判断此数是否为素数。重复直到获得一素数,设其为 \(p\). 类似选取数 \(q\). 设 \(n_A := p \cdot q\).

  2. \(k = (p-1)(q-1)\),并随机选取 \(\varepsilon_A\) 直到 \(gcd(\varepsilon_A, k) = 1)\). 通过拓展欧几里得算法解 \(d_A\).

接下来的问题是,这样生成的密钥是否安全?

设计原则

  1. 不失一般性地假设 \(p < q\),应有数 \(p\) 足够大,否则即可对公钥进行暴力破解。
  2. \(p-q\) 应该足够大,否则可对公钥进行费马分解。
  3. \(p-1\)\(q-1\) 应各自有一个足够大的素因数,否则有 Pollard's p − 1 算法。
  4. \(gcd(-1, q-1)\) 应足够小。
  5. \(d_A\) 应足够大,至少有 \(d_A > n_A^{1/4}\),否则有连分数算法。

费马分解

\(n = p \cdot q\),其中 \(p, q\) 为不同且皆不为 2 的素数。

\[ \begin{aligned} s &= \frac{p-q}{2} \\ t &= \frac{p+q}{2} \end{aligned} \]

由于要求, \(p, q\) 皆为奇数,则两者差与和皆为偶数。

那么有

\[ \begin{aligned} t^2 - s^2 &= \frac{(p+q)^2}{4} - \frac{(p-q)^2}{4} \\ &= pq \\ &= n \end{aligned} \]

因此

\[s^2 + n = t^2\]

如果 \(s\) 足够小,我们便可尝试 \(s = 1, 2, 3, \cdots\) 直到有 \(s^2 + n\) 为一平方数(平方数可以牛顿法非常快速地判定)。若是存在这样的数 \(s\),我们便可求出 \(t\),因此求出用于生成私钥的 \(p\)\(q\)

关于破解 RSA 耗时的几个事实

1999 年 8 月,S. Cavallar, B. Dodson, A.K. Lenstra, B. Murphy, P.L. Montgomery, H.J.J te Riele 完成了由 RSA 实验室悬赏的分解某一 512 比特(155 十进制位)的仅有两个素因数的数。该组人共用相当于一台计算机于 20 年能提供的算力,或者说 7500 台计算机 1 天的算力完成此挑战。这里一台计算机指的是搭载 64 MB 内存, 450 MHz 奔腾II 处理器的计算机。这样的配置在当年(1999 年)是非常标准的。因此即使是以当年的标准看,512 比特的密钥也是远不足以被称作是安全的。

而在 2009 年 12 月,T. Keinjung, K.Aoki, J. Franke, A.K. Lenstra, E. Thom´e, P. Gaudry, E. Kruppa, P. Montgomery, J. Bos, D. Osvik, H. te Riele, A, Timofeev,P. Zimmermann 成功达成了另一项分解 768 比特(232 十进制位)数的悬赏。该成就由平行运行的计算机在两年时间内完成。这些计算机提供了相当于一台计算机 2000 年所能提供的算力。这些计算机搭载的是单核 2.2GHz AMD 处理器。

事实上,后者是 RSA 实验室悬赏的诸多数中被分解的最大的一个。因此由于 1024 位的密钥已在当时有了被破解的趋势,其已不再鼓励被使用了。