工程科学与技术   2018, Vol. 50 Issue (2): 163-169
基于e次根攻击RSA的量子算法
王亚辉1,2, 张焕国2, 王后珍2     
1. 信阳师范学院 计算机与信息技术学院,河南 信阳 464000;
2. 武汉大学 计算机学院,湖北 武汉 430072
基金项目: 国家自然科学基金重点资助项目(61332019);国家重点基础研究发展规划资助项目(2014CB340601);国家自然科学基金资助项目(61402339;61202386);国家自然科学基金重大项目资助(91018008);国家密码发展基金资助项目(MMJJ201701304)
摘要: 量子算法的出现给现有的公钥密码体制带来了严峻挑战,其中,最具威胁的是Shor算法。Shor算法能够在多项式时间内求解整数分解问题和离散对数问题,使得当前应用广泛的RSA、ElGamal和ECC等公钥密码体制在量子计算环境下不再安全,因此研究量子计算环境下的密码破译就有重大意义。解决整数分解问题是Shor算法攻击RSA的核心思想,但攻破RSA并非一定要从解决整数分解问题入手。作者试图从非整数分解角度出发,设计攻破RSA密码体制的量子算法。针对RSA公钥密码体制的特点,通过量子傅里叶变换求出RSA密文 $C$ $n$ $e$ 次根进而得到RSA的明文 $M$ 。即不通过整数分解问题攻破了RSA。与以往密码分析者通过分解模数 $n$ 试图恢复私钥的做法不同,直接从恢复明文消息入手,给出一个对抗RSA密码体制的唯密文攻击算法。研究表明,本文算法的成功概率高于利用Shor算法攻击RSA的成功概率。同时本文算法具有如下性质,即不通过解决整数分解问题实现攻破RSA,且避开了密文 $C$ $ n$ 的阶为偶数这一限制。
关键词: 信息安全    密码学    RSA密码    量子计算    
Quantum Algorithm for Attacking RSA Based on the eth Root
WANG Yahui1,2, ZHANG Huanguo2, WANG Houzhen2     
1. School of Computer and Info. Technol., Xinyang Normal Univ.,Xinyang 464000,China;
2. Compute School,Wuhan Univ.,Wuhan 430072,China
Abstract: The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor’s algorithm is the most important threatening algorithm for cryptanalysis currently.Shor’s algorithm can solve the integer factorization problem (IFP) and discrete logarithm problem (DLP) in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment.Therefore,it is necessary to research the cryptanalysis in the quantum computing environment.Solving the IFP is the core idea of Shor’s algorithm for attacking RSA,but breaking RSA does not have to be solved by solving the IFP.A quantum algorithm is designed to attack the RSA cryptosystem starting from the angle of non-factorization.Focusing on the characteristics of RSA public key cryptosystem,using the quantum Fourier transform,the RSA plaintext $M$ can be got by calculating the ${e^{{th}}}$ root modulus $n$ .That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext $M$ to start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor’s algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus $n$ ,and avoids the restriction that the order of ciphertext $C$ modules $n$ is even.
Key words: information security    cryptology    RSA cryptography    quantum computing    

量子计算是综合利用量子力学原理和计算机科学相关知识进行计算的新的计算模式。它利用量子系统的叠加性、纠缠性和相干性等实现量子的并行计算。量子算法的出现给现有的公钥密码体制带来了严峻的挑战。公钥密码体制的安全性分析无论是在理论上还是实际应用中都具有重大意义,特别是广泛使用的RSA、ElGamal和ECC等公钥密码体制的安全性更值得深入研究[1]

现代公钥密码体制是基于计算数论中困难问题设计的,而整数分解问题是计算数论中重要的困难问题之一。如今广泛用于电子银行,网络等领域的RSA公钥密码体制的安全性正是基于整数分解问题的难解性[2]设计的。之所以RSA密码体制难以破译,就是因为它所依赖的整数分解问题不能快速解决。目前,对密码学最具威胁的两类量子算法是Shor算法和Grover搜索算法。Shor算法[34]能够在多项式时间内求解整数分解问题和离散对数问题,这使得当前应用广泛的RSA、ElGamal和ECC等公钥密码体制在量子计算环境下不再安全;Grover搜索算法[5]是一种通用的量子搜索算法,为一大类搜索问题的解决提供了平方根加速,相当于将密钥长度减半,从而威胁到现有的密码体制。此后,量子算法的研究得到了快速发展[614]

Shor算法的提出表明,在量子计算环境下,整数分解问题可以在多项式时间内得以解决,这就意味着基于整数分解问题设计的RSA公钥密码体制的安全性面临威胁。Shor算法对RSA的攻击是从求解整数分解问题角度出发,而关于整数分解问题的研究也一直是学者们的研究热点。研究者们在Shor算法的基础上,一方面,从减少量子位角度出发对算法进行优化;另一方面,从量子计算机实现角度出发实现对小整数的分解实验。Yang等[15]在国际上首次利用光量子计算机实现了Shor算法分解算法,并在该量子计算机上成功操纵了4个光子量子比特构造了一个简单的线性光网络来实现整数15的分解,然而仅仅只能实现诸如整数15这样的小整数分解。Bigrourd等[16]提出了Shor算法的一个改进版本,且利用时域泰伯效应验证了整数19 403的分解。Gilowski等[17]利用冷原子提出了高斯和方法的量子化版本,且利用此方法验证了整数263 193的分解。Peng等[18]提出了第一个绝热量子计算的整数分解算法,并利用该算法在NMR量子处理器上实现了21的分解。该方法使用的量子比特数不到Shor算法分解整数15时使用的量子比特数的一半,而且分解时间更短,但是分解仅仅是对一类具有特定规律的整数有效。Xu等[19]利用核磁共振量子处理器,仅仅需要4量子位实现了分解整数56 153。Smolin等[20]提出了一个量子整数分解新观点,通过寻找阶为2的元素 $a$ 实现对 $n$ 的分解。因为元素的阶为2,则第2个寄存器只需要2个量子位,从而大大减少量子位。Cao等[21]给出了Shor算法的一个改进算法,利用多量子寄存器实现因子分解,该方法所需要的量子位数多。Liu等[22]给出了Shor算法的改进算法,通过计算2的阶,进而利用数论的相关性质得到模数 $n$ 的因子。各方面的资源消耗与Shor算法相当。Geller等[23]利用费马数的特性,利用8量子比特实现对整数51和85的分解,并给出了量子实现电路图,虽然分解整数所用的量子位少,却是针对一些特殊的整数费马数的,不具有普适性。王亚辉等[24]从非整数分解角度出发,基于方程求解与相位估计提出攻击RSA的量子算法。

通过对Shor算法进一步研究和分析,发现以下两点有待优化:一是,Shor算法分解效率不高;二是,Shor算法要求元素 $a$ $n$ 的阶 $r$ 必须为偶数,且输出必须是 $n$ 的非平凡因子。正是由于Shor算法攻击RSA还有进一步可以优化的空间,作者放弃Shor算法基于求解整数分解问题的理论内核,从非整数分解角度出发,针对RSA公钥密码的特点,基于密文函数 ${C^x}\left( {{{mod }}\;n} \right)$ 的周期性,利用量子傅里叶变换可以求得RSA密文 $C$ $n$ $e$ 次根进而得到RSA的明文,即攻破RSA。本文算法不仅避开了Shor算法的元素的阶必须为偶数和因子是模数 $n$ 的非平凡因子这两个要求,且算法的成功概率高于Shor算法攻击RSA的成功概率。

1 背景知识介绍 1.1 计算数论基础

1977年,Rivest、Shamir和Adleman提出了第一个实用的公钥密码体制,也就是著名的RSA公钥密码体制。由于Rivest、Shamir 和Adleman在公钥密码体制方面的理论和实际应用中作出的贡献,尤其是RSA密码体制的发明,计算机学会(ACM)于2000年授予他们图灵奖,也就是计算科学领域的诺贝尔奖。RSA公钥密码体制定义如下:

定义1(RSA公钥密码体制[2]) RSA公钥密码体制可以定义为:

${{RSA}} = \left\{ {{\cal{M}},{\cal{C}},{\cal{K}},M,C,e,d,n,E,D} \right\}\text{。}$

其中:

1) ${\cal{M}}$ 是明文集合,称为明文空间; ${\cal{C}}$ 是密文集合,称为密文空间; ${\cal{K}}$ 是密钥集合,称为密钥空间。 $M$ 是一段特殊明文; $C$ 是一段特殊密文; $n = pq$ 是模数, $p$ $q$ 是不同的大素数, $n$ 通常至少有100位数。

2) $\left\{ {\left( {e,n} \right),\left( {d,n} \right) \in {\cal{K}}} \right\}$ $e$ 是公钥, $d$ 是私钥且满足 $ed \equiv 1\left( {{{ mod }}\;\varphi \left( n \right)} \right)$ ,其中, $\varphi \left( n \right) = \left( {p - 1} \right)\left( {q - 1} \right)$ 是欧拉函数。

3) $E$ 是加密函数 $E:M \mapsto C$ ,即

$C \equiv {M^e}\left( {{{mod }}\;n} \right)\text{。}$

4) $D$ 是解密函数 $D:C \mapsto M$

$M \equiv {C^d}\left( {{{mod }}\;n} \right)\text{。}$

RSA公钥密码体制是典型的基于整数分解问题的密码体制。且有结论:RSA的破译难度不超过整数分解。Shor提出的量子算法的初衷就是为了解决这一应用广泛的公钥密码体制。

定理1(线性丢番图方程的解[2]) 设 $\displaystyle\frac{a}{b}$ 的有限连分数渐进分数如下:

$\left[ {\frac{{{P_0}}}{{{Q_0}}},\frac{{{P_1}}}{{{Q_1}}}, \cdots ,\frac{{{P_n}}}{{{Q_n}}}} \right] = \frac{a}{b}$ (1)

则方程 $ax - by = d$ 的整数解为:

$\left\{ \begin{gathered} x = {\left( { - 1} \right)^{n - 1}}{Q_{n - 1}}, \hfill \\ y = {\left( { - 1} \right)^{n - 1}}{P_{n - 1}} \hfill \\ \end{gathered} \right.$ (2)

其中, $d = {{gcd}}\left( {a,b} \right)$

定理2[2]  乘法的逆元 ${{1/}}b\left( {{{mod }}\;n} \right)$ 存在当且仅当 ${{gcd}}\left( {b,n} \right) = 1$

定理3(欧拉定理[2]) 设 $a$ $n$ 都是正整数,且 ${{gcd}}\left( {a,n} \right) = 1$ 。则

${a^{\varphi \left( n \right)}} \equiv 1\left( {{{mod }}\;n} \right)$ (3)
1.2 量子计算基础

计算机要处理数据,必须把数据表示成计算机能够识别的形式。经典信息处理的最基本单元是比特(bit,即二进制0或1)。所有计算都建立在比特的基础上,与之对应,量子信息与量子计算也是建立在类似比特概念的量子比特上。一个量子比特是一个可以在二维希尔伯特空间(Hilbert space)中描述的两态量子体系。在此希尔伯特空间中,通常人们选择一对正交归一化的态

$\left| {{0}} \right\rangle = \left[ \begin{array}{l}{{1}}\\{{0}}\end{array} \right]\text{、}\!\!\left| {{1}} \right\rangle = \left[ \begin{array}{l}{{0}}\\{{1}}\end{array} \right]$

代表经典比特的0和1。一个量子比特的任意状态都可以表示为这个两个基本状态的线性组合。称 $\left| {} \right\rangle $ 为狄拉克(Dirac)记号,它在量子力学中表示状态。经典比特和量子比特的区别之处在于,量子比特的状态除了 $\left| {{0}} \right\rangle $ $\left| {{1}} \right\rangle $ 外,还可以是状态的线性组合,通常称为叠加态,即

$\left| {{\varPsi}} \right\rangle = \alpha \left| {{0}} \right\rangle + \beta \left| {{1}} \right\rangle $ (4)

其中, $\alpha $ $\beta $ 为复数,称为量子态的概率幅,可以用来检测一个量子比特是处于 $\left| {{0}} \right\rangle $ 态还是 $\left| {{1}} \right\rangle $ 态。即检测量子态 $\left| {{\varPsi}} \right\rangle $ 得到 $\left| {{0}} \right\rangle $ 的概率为 ${\left| \alpha \right|^{{2}}}$ ,得到 $\left| {{1}} \right\rangle $ 的概率为 ${\left| \beta \right|^{{2}}}$ ,且满足归一化条件:

${\left| \alpha \right|^{{2}}} + {\left| \beta \right|^{{2}}} = {{1}}$ (5)

类似于经典计算机线路用连线和逻辑门构成,量子计算机线路也可用连线和基本量子门组成的量子线路构造。这些量子逻辑门实质上是幺正操作,基于线性性质,几何上可用矩阵表示。常见的单量子比特门如Hadamard门为:

$H \equiv \frac{1}{{\sqrt 2 }}\left[ \begin{array}{l}1\\1\end{array} \right.\left. \begin{array}{l}\;\;\;\;1\\\;\; - 1\end{array} \right]\text{。}$

其作用在 $n$ 量子比特 ${\left| {{0}} \right\rangle ^{ \otimes n}}$ 上时,可产生均匀叠加态,即

$H{\left| 0 \right\rangle ^{ \otimes n}} = \frac{1}{{\sqrt {{2^n}} }}\sum\limits_{j = 0}^{{2^n} - 1} {\left| j \right\rangle } $ (6)

Hadamard门变换是量子算法中常用的重要量子门。

定义2(量子Fourier变换(QFT)[25]) 量子Fourier变换定义为: 在一组标准正交基 $\left| 0 \right\rangle ,\left| 1 \right\rangle , \cdots ,\left| {q - 1} \right\rangle $ 上的一个线性算子,在基态上的作用为:

${{QFT:}}\left| j \right\rangle \to \frac{1}{{\sqrt q }}\sum\limits_{k = 0}^{q - 1} {{{{e}}^{2{\text{π}} {{i}}jk/q}}\left| k \right\rangle } $ (7)

那么,对任意量子态的变换可写作:

$\sum\limits_{j = 0}^{q - 1} {{x_j}} \left| j \right\rangle \to \sum\limits_{k = 0}^{q - 1} {\sum\limits_{j = 0}^{q - 1} {{x_j}} } {{{e}}^{2{\text{π}} {{i}}jk/q}}\left| k \right\rangle $ (8)

Nielson等[25]给出了量子Fourier变换是可逆变换的证明,并且给出了其量子实现电路。

2 基于e次根攻击RSA的量子算法

RSA公钥密码体制的安全性取决于整数分解问题的困难性,因此解决整数分解问题是攻击RSA最直接的方式。然而攻破RSA却不一定要通过解决整数分解问题实现。从非整数分解角度出发,针对RSA公钥密码体制的特点,利用量子傅里叶变换可以求得RSA密文 $C$ $n$ $e$ 次根进而得到RSA的明文 $M$ ,即攻破RSA。算法1具体步骤如下:

算法1  基于 $e$ 次根攻击RSA的量子算法

输入:RSA的公钥 $\left( {e,n} \right)$ ,密文 $C$

输出:RSA的明文 $M$

1)选择 $q$ ,其中 $q = {2^k}$ 且满足 ${n^2} \le q = {2^k} < 2{n^2}$

2)给定两个量子寄存器,分别记为寄存器1,寄存器2。且初始化为零态 $\left| {{{\varPsi }_{{0}}}} \right\rangle = \left| {{0}} \right\rangle \left| {{0}} \right\rangle $ 。其中寄存器1需要 ${{2}}\left\lceil {{{lb}}\;n} \right\rceil $ 量子位,寄存器2需要需要 $\left\lceil {{{lb }}\;n} \right\rceil $ 量子位。

3)对寄存器1执行Hadamard门变换,得到叠加态为:

$H{{:}}\;\left| {{{{\varPsi}} _0}} \right\rangle \to \left| {{{{\varPsi}} _1}} \right\rangle = \frac{1}{{\sqrt q }}\sum\limits_{x = 0}^{q - 1} {\left| x \right\rangle } \left| {{0}} \right\rangle $ (9)

4)对 $\left| {{{{\varPsi}} _{{1}}}} \right\rangle $ 进行 ${U_f}$ 变换。由于希尔伯特空间是线性的,则得到寄存器1和寄存器2的纠缠态 $\left| {{{{\varPsi}} _{{2}}}} \right\rangle $ ,有:

$\begin{aligned}[b]& {U_{f}}{{:}}\;\left| {{{{\varPsi}} _1}} \right\rangle \to \left| {{{{\varPsi}} _2}} \right\rangle = {U_f}\left( {\frac{1}{{\sqrt q }}\sum\limits_{x = 0}^{q - 1} {\left| x \right\rangle } \left| 0 \right\rangle } \right) = \\& \quad\quad\frac{1}{{\sqrt q }}\sum\limits_{x = 0}^{q - 1} {{U_f}} \left| x \right\rangle \left| 0 \right\rangle = \frac{1}{{\sqrt q }}\sum\limits_{x = 0}^{q - 1} {\left| x \right\rangle } \left| {f\left( x \right)} \right\rangle = \\& \quad\quad\frac{1}{{\sqrt q }}\sum\limits_{x = 0}^{q - 1} {\left| x \right\rangle } \left| {{C^x}\left( {{{mod }}\;n} \right)} \right\rangle \text{。}\end{aligned}$

${U_f}:\sum\limits_{x = 0}^{q - 1} {\left| x \right\rangle } \left| 0 \right\rangle \to \sum\limits_{x = 0}^{q - 1} {\left| x \right\rangle } \left| {f\left( x \right)} \right\rangle $ (10)

其中, $f\left( x \right) = {C^x}\left( {{{mod }}\;n} \right)$ 。由此可以看出,对处于叠加态的 $\left| x \right\rangle $ 进行 ${U_f}$ 变换,可以产生每个 $x$ 对应的函数值 $f\left( x \right)$ ,也即量子的并行性能力在此得以体现。

5)观测寄存器2。不妨假设观测到态 $\left| k \right\rangle $ ,事实上, $k \equiv {C^t}\left( {{{mod }}\;n} \right)$ 。同时,寄存器1也相应地坍缩,此时寄存器1和寄存器2的态 $\left| {{{{\varPsi}} _{{3}}}} \right\rangle $ 为:

$\left| {{{{\varPsi}} _{{3}}}} \right\rangle = \frac{{{1}}}{{\sqrt A }}\sum\limits_{x{{:}}{C^x} \equiv {C^t}} {\left| x \right\rangle } \left| k \right\rangle $ (11)

其中, $A$ 是所有满足同余式 ${C^x} \equiv {C^t}\left( {{{mod }}\;n} \right)$ $x$ 的个数。

6)对寄存器1执行量子傅里叶变换(QFT),得到

$\begin{aligned}& {{QFT}}:\left| {{{{\varPsi}} _{{3}}}} \right\rangle \to \left| {{{{\varPsi}} _{{4}}}} \right\rangle = {{QFT}}\left| {{{{\varPsi}} _{{3}}}} \right\rangle =\\& \quad\quad\frac{{{1}}}{{\sqrt A }}{{QFT}}\sum\limits_{x:{C^x} \equiv {C^t}} {\left| x \right\rangle } \left| k \right\rangle = \\& \quad\quad\frac{1}{{\sqrt A }}\sum\limits_{c = 0}^{q - 1} {\frac{1}{{\sqrt q }}\sum\limits_{x:{C^x} \equiv {C^t}} {{{{e}}^{\frac{{2{\text{π}} {{i}}xc}}{q}}}} } \left| c \right\rangle \left| k \right\rangle = \\& \quad\quad\frac{1}{{\sqrt {Aq} }}\sum\limits_{c = 0}^{q - 1} {\sum\limits_{x:{C^x} \equiv {C^t}} {{{{e}}^{\frac{{2{\text{π}} {{i}}xc}}{q}}}} } \left| c \right\rangle \left| k \right\rangle \text{。}\end{aligned}$

其中, ${{0}} \le x < q$ 且满足 ${C^x} \equiv {C^t}\left( {{{mod }}\;n} \right)$ 。假设密文 $C$ $n$ 的阶为 $r$ 。即上面的求和式中的所有 $x$ 满足 $x \equiv t\left( {{{mod }}\;r} \right)$ ,不妨记为 $x = t + jr$ 。由此可以看出寄存器1是以 $r$ 为周期的态的叠加。此时寄存器的态 $\left| {{{{\varPsi}} _{{4}}}} \right\rangle $ 为:

$\left| {{{{\varPsi}} _{{4}}}} \right\rangle = \frac{{{1}}}{{\sqrt {Aq} }}\sum\limits_{c = 0}^{q - 1} {\sum\limits_{j = 0}^{A - 1} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)c}}{q}}}} } \left| c \right\rangle \left| k \right\rangle $ (12)

进而可知 $A$ 是不超过 $\displaystyle\frac{{q - t}}{r}$ 的最大正整数,且 $t \le r < n$ 。又 $q \approx O\left( {{n^2}} \right)$ ,因此 $A \approx q/r$ 。为了简化计算,假设 $q$ $r$ 的整数倍,因此 $A = q/r$ 。则此时寄存器1中的概率幅 $A'\left( c \right)$ 记为:

$A'\left( c \right) = \frac{{{1}}}{{\sqrt {Aq} }}\sum\limits_{j = {{0}}}^{A{{ - 1}}} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)c}}{q}}}} = \frac{{\sqrt r }}{q}\sum\limits_{j = {{0}}}^{q/r{{ - 1}}} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)c}}{q}}}} \text{。}$

注意到概率幅 $A'\left( c \right)$ 是关于 $c$ 的周期函数,且周期为 $\displaystyle\frac{q}{r}$ 。事实上,

$\begin{aligned}& A'\left( {c + \frac{q}{r}} \right) = \frac{{\sqrt r }}{q}\sum\limits_{j = {{0}}}^{q/r{{ - 1}}} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)\left( {c + \frac{q}{r}} \right)}}{q}}}} = \\&\quad\quad\quad\quad \frac{{\sqrt r }}{q}\sum\limits_{j = {{0}}}^{q/r{{ - 1}}} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)c}}{q}}}} {{ = }}A'\left( c \right)\text{。}\end{aligned}$

其中,利用到 ${{{e}}^{2{\text{π}} {{i}}}} = 1$

由此可以看出,量子傅里叶变换(QFT)使得寄存器1的周期从 $r$ 变为 $\displaystyle\frac{q}{r}$ $t$ 已经不存在寄存器1的测量结果中如图1所示。

7)测量寄存器1。不妨假设观测到态 $\left| c \right\rangle $ 。因为 $c$ $q$ 都是已知的,故利用 $\displaystyle\frac{c}{q}$ 的连分数展开就可得到阶 $r$

8)因为在RSA密码体制中 $ed \equiv 1\left( {{{mod }}\;\varphi \left( n \right)} \right)$ ,由定理2可知 ${{gcd}}\left( {e,\varphi \left( n \right)} \right) = 1$ 。而 $r|\varphi \left( n \right)$ ,故可得 ${{gcd}}\left( {e,r} \right) = 1$ 。构造线性丢番图方程:

$e\mu - \varphi \left( n \right)\nu = 1$ (13)

则由定理1可得到方程的解 $\mu $ $\nu $

9)计算 $M \equiv {C^\mu }\left( {{{mod }}\;n} \right)$ ,即为RSA的明文 $M$ 。这是因为:

${M^e} = {\left( {{C^\mu }} \right)^e} = {C^{e\mu }} = {C^{{{1}} + \varphi \left( n \right)\nu }} =C \cdot {\left( {{C^{\varphi \left( n \right)}}} \right)^\nu } \equiv C\left( {{{mod }}\;n} \right)\text{。}$

其中, ${C^{\varphi \left( n \right)}} \equiv 1\left( {{{mod }}\;n} \right)$ 是由定理3得知。

也即在已知 $C$ $e$ $n$ 的情况下,得到了加密函数 ${M^e} \equiv C\left( {{{mod }}\;n} \right)$ 的明文 $M$

算法1基于密文函数 ${C^x}\left( {{{mod }}\;n} \right)$ 的周期性,利用量子傅里叶变换求得RSA密文 $C$ $n$ 的阶 $r$ ,而截获密文 $C$ 在实际攻击中也是最容易实现的。与以往密码分析者通过分解模数 $n$ 试图恢复私钥 $d$ 的做法不同,作者直接从恢复明文消息入手,给出一个攻击RSA密码体制的唯密文攻击算法。

图1 函数 ${f}\left( x \right)$ 和概率幅 ${ A'}\left( c \right)$ Fig. 1 Function ${f}\left( x \right)$ and probability amplitude ${ A'}\left( c \right)$

3 量子算法分析 3.1 量子算法的物理操作可行性

算法1的第3)步执行的H变换和第6)步执行的量子傅里叶变换(QFT)都可以在多项式规模的量子门电路中得以实现。第4)步执行的酉变换 ${U_f}$ 中函数 $f\left( x \right)$ 的设计主要由模幂运算可逆电路实现,可以通过对其经典电路进行改进的可逆计算技术实现[26]

3.2 量子算法的成功概率分析

引理1  设 $a > 1$ ,则函数 $f\left( x \right) = \displaystyle\frac{{\sin ax}}{{\sin x}}$ 在区间 $\left( 0 \right.,\left. {\displaystyle\frac{{\text{π}} }{{{{2}}a}}} \right]$ 内单调递减。

证明:因为

$f\left( x \right) = \frac{{\sin ax}}{{\sin x}}$ (14)

所以

${f'}\left( x \right) = \frac{{\cos ax\cos x\left( {a\tan x - \tan ax} \right)}}{{{{\sin }^2}x}}$ (15)

$g\left( x \right) = a\tan x - \tan ax$ ,则

${g'}\left( x \right) = a\left( {{{\sec }^2}x - {{\sec }^2}ax} \right)$ (16)

而在区间 $\left( 0 \right.,\left. {\displaystyle\frac{{\text{π}} }{{{{2}}a}}} \right]$ ${g'}\left( x \right) \le 0$ ,而 $g\left( 0 \right) = 0$ 。因此在区间 $\left( 0 \right.,\left. {\displaystyle\frac{{\text{π}} }{{{{2}}a}}} \right]$ $g\left( x \right) \le 0$ 。又由在区间 $\left( 0 \right.,\left. {\displaystyle\frac{{\text{π}} }{{{{2}}a}}} \right]$ $\cos ax\cos x \ge 0$ ,因此 $g\left( x \right) \le 0$ ,即函数 $f\left( x \right)$ 在区间 $\left( 0 \right.,\left. {\displaystyle\frac{{\text{π}} }{{{{2}}a}}} \right]$ 内单调递减。

由算法第6)步可知,观测到态 $\left| c \right\rangle $ 的概率为:

$\begin{aligned} {{Prob}}\left( c \right) = & {\left| {A'\left( c \right)} \right|^2} = {\left| {\frac{{\sqrt r }}{q}\sum\limits_{j = 0}^{q/r - 1} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)c}}{q}}}} } \right|^{{2}}}= \\& \frac{r}{{{q^2}}}{\left| {\sum\limits_{j = 0}^{q/r - 1} {{{{e}}^{\frac{{2{\text{π}} {{i}}jrc}}{q}}}} } \right|^{{2}}} = \frac{r}{{{q^2}}}{\left| {\sum\limits_{j = 0}^{q/r - 1} {{{ e}^{\frac{{2{\text{π}} ij{{\left\{ {rc} \right\}}_q}}}{q}}}} } \right|^{{2}}}\text{。}\end{aligned}$

其中, ${\left\{ {rc} \right\}_q}$ 表示 $rc\left( {{{mod }}\;q} \right)$ 的余数。

又注意到

$A'\left( c \right) = \frac{{\sqrt r }}{q}\sum\limits_{j = {{0}}}^{q/r{{ - 1}}} {{{{e}}^{\frac{{2{\text{π}} {{i}}\left( {t + jr} \right)c}}{q}}}} $ (17)

因此,可得:

$A'\left( c \right) = \left\{ \begin{aligned}& \frac{1}{{\sqrt r }}{{{e}}^{\frac{{2{\text{π}} {{i}}tc}}{q}}},\;\;{\text{如果}}c{\text{是}}A{\text{的倍数}};\\& 0,\;\;\;{\text{其他}}\text{。}\end{aligned} \right.$

也即通过第6)步的量子傅里叶变换(QFT)使得所需要的结果增强,并使不需要的结果变为0。从而由上式的 $A\left( c \right)$ 可知,通过第7)步观测到的态 $\left| c \right\rangle $ 满足 $rc\left( {{{mod }}\;q} \right) = 0$ 。如果 $c$ 满足

$ - r/2 \le rc\left( {{{mod }}\;q} \right) \le r/2$ (18)

${{Prob}}\left( c \right)$ 能以较高的概率分布在一个半圆上。

${\delta _c} = 2{\text{π}}{\left\{ {rc} \right\}_q}/q$ ,则 ${{Prob}}\left( c \right)$ 是以 ${{{e}}^{{{i}}{\delta _c}}}$ 为等比的等比数列,则

$\begin{aligned} {{Prob}}\left( c \right) = & \frac{r}{{{q^2}}}{\left| {\sum\limits_{j = 0}^{q/r - 1} {{{{e}}^{\frac{{2{\text{π}} {{i}}j{{\left\{ {rc} \right\}}_q}}}{q}}}} } \right|^{{2}}}=\frac{r}{{{q^2}}}{\left| {\frac{{1 - {{{e}}^{\frac{{2{\text{π}} {{i}}{{\left\{ {rc} \right\}}_q}}}{q} \cdot \frac{q}{r}}}}}{{1 - {{{e}}^{\frac{{2{\text{π}} {{i}}{{\left\{ {rc} \right\}}_q}}}{q}}}}}} \right|^{{2}}} =\\& \frac{r}{{{q^2}}}{\left| {\frac{{1 - {{{e}}^{{{i}}{\delta _c} \cdot \frac{q}{r}}}}}{{1 - {{{e}}^{{{i}}{\delta _c}}}}}} \right|^{{2}}}{{ = }}\frac{r}{{{q^2}}}\frac{{{{si}}{{{n}}^2}\displaystyle\frac{{{\delta _c}q}}{{2r}}}}{{{{si}}{{{n}}^2}\displaystyle\frac{{{\delta _c}}}{2}}}\text{。}\end{aligned}$

又因为 $\left| {{{\left\{ {rc} \right\}}_q}} \right| \le \displaystyle\frac{r}{2}$ ,所以 $\left| {{\delta _c}} \right| \le \displaystyle\frac{{{\text{π}}r}}{q}$ 。而由引理1知,函数 $f\left( x \right) = \displaystyle\frac{{{{sin }}\;ax}}{{{{sin }}\;x}}$ 在区间 $\left( 0 \right.,\left. {\displaystyle\frac{{\text{π}} }{{{{2}}a}}} \right]$ 内单调递减。在 ${{Prob}}\left( c \right)$ 中, $a = \displaystyle\frac{q}{r}$ $x = \displaystyle\frac{{{\delta _c}}}{2}$ ,则有:

${{Prob}}\left( c \right) = \frac{r}{{{q^2}}}\displaystyle\frac{{{{\sin }^2}\displaystyle\frac{{{\delta _c}q}}{{2r}}}}{{{{\sin }^2}\displaystyle\frac{{{\delta _c}}}{2}}} \ge \displaystyle\frac{r}{{{q^2}}}\displaystyle\frac{{{{\sin }^2}\displaystyle\frac{q}{{2r}} \cdot \displaystyle\frac{{{\text{π}} r}}{q}}}{{{{\sin }^2}\displaystyle\frac{1}{2} \cdot \displaystyle\frac{{{\text{π}} r}}{q}}} \ge \frac{{{4}}}{{{{\text{π}} ^{{2}}}r}}\text{。}$

其中,不等式 ${{4}}{x^2}/{{\text{π}} ^2} \le {{si}}{{{n}}^2}x \le {x^2}$ $\left| x \right| \le {\text{π}} {{/2}}$ 。显然 ${{\text{π}}r}/ {2q} < {\text{π}}/{2}$

下面从观测到的 $c$ 值得到 $r$ 的信息。由于

$ - r/2 \le rc\left( {{{mod }}\;q} \right) \le r/2,$

而上式又等价于

$ - r/2 \le rc - dq \le r/2,$

两边同时除以 $rq$ ,得到

$\left| {\frac{c}{q} - \frac{d}{r}} \right| \le \frac{1}{{2q}}$ (19)

已知 $c$ $q$ ,又因为 $r \le n,q \ge {n^2}$ ,所以恰好有一个满足上式的分式 $\displaystyle\frac{d}{r}$ ,其中分母最多为 $n$ 。而该分式可以通过 $\displaystyle\frac{c}{q}$ 的连分数展开求得。因此,如果 ${{gcd}}\left( {d,r} \right) = 1$ ,就得到 $r$ 的值。由于与 $r$ 互素的 $d$ $\varphi \left( r \right)$ 个。因此有:

${{Prob}}\left( {{\text{与}}r{\text{互素的}}d} \right) \ge \frac{{{{4}}\varphi \left( r \right)}}{{{{\text{π}} ^{{2}}}r}}\text{。}$

也即利用算法1攻破RSA的成功概率≥ $\displaystyle\frac{{{{4}}\varphi \left( r \right)}}{{{{\text{π}}^{{2}}}r}}$

因为利用Shor算法攻破RSA的成功概率为:

$\frac{{{{3}}\varphi \left( r \right)}}{{{{\text{π}}^2}r}} \le {P_{{{Shor}}}} < \frac{{{{4}}\varphi \left( r \right)}}{{{{\text{π}}^2}r}},$

因此,利用算法1攻破RSA的成功概率大于利用Shor算法攻击RSA的成功概率。

3.3 量子算法的时间复杂度分析

算法1由经典计算部分和量子计算部分两部分组成,经典计算部分中算法1的第7)步执行的连分数展开和第8)步使用的线性丢番图方程求解都可以在多项式时间内完成。下面主要分析量子计算部分的时间消耗。算法1主要由第4)步的酉变换和第6)步的量子傅里叶变换(QFT)组成。而第4)步执行的酉变换需要 $O\left( {{{\left( {{{lb}}\;n} \right)}^{{3}}}} \right)$ 的量子门实现。第6步执行的量子傅里叶变换(QFT)同样需要 $O\left( {{{\left( {{{lb }}\;n} \right)}^{{2}}}} \right)$ 的量子门来实现。第2)步初始化两个寄存器为零态需要 $O\left( {{{lb }}\;n} \right)$ 的量子门来实现。第3)步执行Hadamard门变换需要 $O\left( {{{lb }}\;n} \right)$ 的量子门实现。因此算法1的量子计算部分也可以在多项式时间内完成。综上所述,算法1是多项式时间量子算法。

分析算法1所需要的量子比特数。由步骤2)可知,寄存器1需要 ${{2}}\left\lceil {{{lb}}\;n} \right\rceil $ 量子比特,寄存器2需要需要 $\left\lceil {{{lb}}\;n} \right\rceil $ 量子比特。因此算法1共需要 ${{3}}\left\lceil {{{lb}}\;n} \right\rceil $ 量子比特。

为了更直观看出算法1的特点以及与前人算法在攻击RSA方面的差异。在表1中,针对各算法在成功概率、时间复杂性、所需要的量子位、理论基础以及攻击类型等方面进行了比较。

表1 各算法消耗资源对比 Tab. 1 Comparision of the consuming in different algorithms

通过表1得出,算法1具有如下性质:1)从非整数分解角度出发,给出一个基于 $e$ 次根攻击RSA的量子算法;2)避开了Shor算法元素的阶为偶数和输出的因子是模数 $n$ 的非平凡因子这两条限制;3)具有多项式时间复杂度;4)具有高的成功概率。

4 结 论

由于RSA公钥密码体制的广泛应用,快速攻译RSA已成为现代密码分析的一个重要研究方向。Shor算法能够在多项式时间内攻破RSA,但其算法明确要求元素 $a$ $n$ 的阶为偶数,否则返回算法第1)步重新选择 $a$ 进行计算,并且输出结果有可能是 $n$ 的非平凡因子。

作者提出的基于 $e$ 次根攻击RSA的量子算法1,从非整数分解角度出发,利用量子傅里叶变换计算密文 $C$ $n$ $e$ 次根进而恢复出RSA的明文 $M$ 。与以往密码分析者通过分解模数 $n$ 试图恢复私钥 $d$ 的做法不同,本文直接从恢复明文消息入手,给出一个对抗RSA密码体制的唯密文攻击算法。研究表明,本算法的成功概率 $ \ge 4\varphi \left( r \right)/{{\text{π}} ^2}r$ ,高于利用Shor算法攻击RSA的成功概率,同时避开了Shor算法的两点限制。

本文主要针对基于整数分解问题的RSA密码体制进行量子攻击研究,那么,对于基于离散对数问题和椭圆曲线离散对数问题的密码体制的量子攻击将是下一步的研究方向。

参考文献
[1]
Zhang Huanguo, Han Wenbao, Lai Xuejia. Survey on cyberspace security[J]. Scientia Sinica(Informationis), 2016, 46(2): 125-164. [张焕国, 韩文报, 来学嘉. 网络空间安全综述[J]. 中国科学(信息科学), 2016, 46(2): 125-164.]
[2]
Yan Songyuan.Quantum computational number theory[M].Berlin:Springer,2015.
[3]
Shor P W.Algorithms for quantum computation:Discrete logarithms and factoring[C]//Proceedings of 35th Annual Symposium on Foundations of Computer Science.Washington:IEEE,1994:124–134.
[4]
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509. DOI:10.1137/S0097539795293172
[5]
Grover L K. Quantum mechanics helps in searching for a needle in a haystack[J]. Physical Review Letters, 1977, 79(23): 325-328.
[6]
Broadbent A,Fitzsimons J,Kashefi E.Universal blind quantum computation[C]//Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science.Las Vegas:IEEE,2010:517–526.
[7]
Li Q, Chan W H, Wu C H. Triple-server blind quantum computation using entanglement swapping[J]. Physical Review A, 2014, 89(4): 040302. DOI:10.1103/PhysRevA.89.040302
[8]
Wang Hongfu. Quantum algorithm for obtaining the eigenstates of a physical system[J]. Physical Review A, 2016, 93(5): 052334. DOI:10.1103/PhysRevA.93.052334
[9]
Wu Wanqing, Zhang Huanguo, Wang Houzhen. Polynomial-time quantum algorithms for finding the linear structures of boolean function[J]. Quantum Information Process, 2015, 14(4): 1215-1226. DOI:10.1007/s11128-015-0940-1
[10]
Zhang Huanguo, Mao Shaowu, Wu Wanqing. Overview of quantum computation complexity theory[J]. Chinese Journal of Computers, 2016, 39(12): 2403-2428. [张焕国, 毛少武, 吴万青. 量子计算复杂性理论综述[J]. 计算机学报, 2016, 39(12): 2403-2428. DOI:10.11897/SP.J.1016.2016.02403]
[11]
Wu Nan, Song Fangmin, Li Xiangdong. Universal quantum computer:Theory,organization and implementation[J]. Chinese Journal of Computers, 2016, 39(12): 2429-2445. [吴楠, 宋方敏, LiX. 通用量子计算机:理论、组成与实现[J]. 计算机学报, 2016, 39(12): 2429-2445. DOI:10.11897/SP.J.1016.2016.02429]
[12]
He Yefeng. Two-party quantum key agreement protocol based on GHZ states[J]. Journal of Sichuan University(Engineering Science Edition), 2016, 48(6): 197-201. [何业锋. 基于GHZ态的两方量子密钥协商协议[J]. 四川大学学报(工程科学版), 2016, 48(6): 197-201.]
[13]
Zhu B L, Zhu W Y, Liu Z J. A novel quantum-behaved bat algorithm with mean best position directed for numerical optimization[J]. Computational Intelligence and Neuroscience, 2016, 2016(2): 1-17.
[14]
Fu Xiangqun, Bao Wansu, Wang Shuai. Quantum algorithm for discrete logarithm over ZN[J]. Chinese Journal of Computers, 2014, 37(5): 1058-1062. [付向群, 鲍皖苏, 王帅. ZN上离散对数量子计算算法 [J]. 计算机学报, 2014, 37(5): 1058-1062.]
[15]
Yang C, Daniel L, Yang T. Demonstration of a complied version of Shor’s quantum factoring algorithm using photonic qubits[J]. Physical Review Letters, 2007, 99(25): 250504. DOI:10.1103/PhysRevLett.99.250504
[16]
Bigourd D, Chatel B, Schleich W P. Factorization of numbers with the temporal talbot effect:Optical implementation by a sequence of shaped uitrashort pulse[J]. Physical Review Letters, 2008, 100(3): 030202. DOI:10.1103/PhysRevLett.100.030202
[17]
Gilowski M, Wendrich T. Gauss sum factoring with cold atoms[J]. Physical Review Letters, 2008, 100(3): 030201. DOI:10.1103/PhysRevLett.100.030201
[18]
Peng X H, Liao Z Y, Xu N Y. Quantum adiabatic algorithm for factorization and its experimental implementation[J]. Physical Review Letters, 2008, 101(2): 220405.
[19]
Xu N Y,Zhu J,Lu D W,et al.Quantum factorization of 143 on a dipolar coupling nuclear magnetic resonance system[J].Physical Review Letters, 2012,108(13):130501.
[20]
Smolin J A, Smith G, Vargo A. Oversimplifying quantum factoring[J]. Nature, 2013, 499(7457): 163-165. DOI:10.1038/nature12290
[21]
Cao Zhengjun,Cao Zhenfu.On Shor’s factoring algorithm with more registers and the problem to certify quantum computers[EB/OL](2014-09-10)[2017-08-05]. https://arxiv.org/abs/1409.7352.
[22]
Liu L H, Cao Z J. On computing ordn(2) and its application [J]. Information and Computation, 2006, 204(7): 1173-1178. DOI:10.1016/j.ic.2006.04.003
[23]
Geller M R,Zhou Z Y.Factoring 51 and 85 with 8 qubits[J].Scientific Reports,2013,3:3023.
[24]
Wang Yahui, Zhang Huanguo, Wu Wanqing. Quantum algorithms for breaking RSA based on phase estimation and equation solving[J]. Chinese Journal of Computers, 2017, 40(12): 2688-2699. [王亚辉, 张焕国, 吴万青. 基于方程求解与相位估计攻击RSA的量子算法[J]. 计算机学报, 2017, 40(12): 2688-2699. DOI:10.11897/SP.J.1016.2017.02688 ]
[25]
Nielson M A,Chuang I L.Quantum computation and quantum information[M].10th Anniversary Edition.Cambridge:Cambridge University Press,2010.
[26]
Bennett C H. Time/space trade-offs for reversible computaion[J]. SIAM Journal on Computing, 1989, 18(4): 766-776. DOI:10.1137/0218053