量子算法与实践——Shor算法

导读 Shor算法诞生于量子算法的质变阶段，量子计算的纠缠与叠加特性使量子算法具有重大应用价值。相对成熟的经典算法其算力与效率依然不能媲美量子算法，由此基于经典算法逻辑设计的安全性也因量子计算技术的发展受到威胁。Shor算法就是著名的量子算法之一，它出现代表着量子计算机将能以强大的算力高效破解已被广泛使用的公开密钥加密方法（即RSA算法）。理解Shor算法需要具备的一定数学知识，如欧拉定理、连分式展开公式、复分析和离散傅里叶变换等知识。本文将从RSA算法原理、Shor算法基本原理及应用等方面介绍Shor算法。

01 RSA加密算法

RSA加密是一种非对称通信加密技术，通常广泛应用于通信安全要求较高的场景。RSA算法加密的安全性强度依赖于对极大整数做因数分解的难度。该难度主要体现在经典计算机对极大整数做因数分解耗费的时间成本与信息价值不成正比。例如计算机学科的学者们认为经典计算机不可能实际分解超过2048位数字，而已有科学家已展示仅用2000万个量子比特8小时就能完成2048位数字的分解。尽管可实现2000万量子比特的量子计算机遥不可及，但减少算法运行所需资源等优化研究还在不断进行。下文将从RSA加密基础知识与原理方面介绍RSA加密算法。

同余式

同余式是数论的基本概念之一，设m是给定的一个正整数，a、b是整数，若满足m∣(a−b)，则称a与b对模m同余，记为a≡b(mod m)，或记为a≡b(m)。这个式子称为模m的同余式，若m∤(a−b)，则称a、b对模m不同余，同余概念又常表达为：a=b+km(k∈Z)。如16=3×5+1，19=3×6+1；则16≡19(mod 3)。同余式常用定理有欧拉公式、费马小定理、威尔逊公式扩展欧几里德。

欧拉函数和公式

欧拉函数，1~N种与N互质的个数称为欧拉函数，记作φ(N)。若有a,b∈N，gcd(a,b)=1，则称a与b互质。如当N=8，1、3、5、7均与8互质，则φ(8)=4。欧拉函数计算通式为：φ(x)=(1−P1−1)∗(1−P2−1)∗(1−P3−1)⋅⋅⋅⋅⋅⋅(1−Pn−1)，其中Pi表示x的质因数。欧拉定理若gcd(a,m)=1,则aφ(m)≡1(mod m)。

单个欧拉函数的代码实现：

def euler_phi(n):

    ans = n

    for i in range(2, int(sqrt(n)) + 1):

        if n % i == 0:

            ans = ans // i * (i - 1)

            while n % i == 0:

                n = n / i

    if n > 1:

        ans = ans // n * (n - 1)

    return ans

02 RSA密码原理

数据加密是采用相应的算法对明文、文件或数据进行处理实现信息保密的过程。数据加密技术有对称加密和非对称加密两种。其中RSA算法就是一种非对称加密技术。RSA算法的保密强度随其密钥长度的增加而增强，当密钥越长，其加密解密所耗费的时间越长。RSA算法保密技术将时间效率和信息价值等综合因素纳入考虑，其基本思想是通过预设经典计算的计算难度与效率来达到保密效果，融入了极大的人类智慧。

对称加密技术

对称加密技术的原理逻辑为Alice和Bob都拥有同一个保密信息的钥匙，密钥在信息传送过程中容易被窃取。对称加密体制又称为单钥密码体制，对称加密的整个加密过程中只使用一个密钥，实质上是使用一把密钥加密，并使用同一把密钥解密。对称加密由于加解和解密使用的是同一个密钥算法，故而在加解密过程较快，适合于数据量比较大的加解密。对称加密的主要有优点就是算法公开、计算量小、加密速度快、加密效率高；但对称加密的效率优势也是对称加密技术的缺点所在，其缺点即在密钥协商过程中，一旦造成密钥泄露，密文的安全性也将不复存在。此外，每对用户每次使用对称加密算法时，都需要生成只有双方已知的唯一密钥，造成密钥数量庞大，从而增加双方密钥管理负担。

RSA加密技术

非对称加密又称为公钥密码，该技术是针对私钥密码体制即对称加密算法的缺陷而提出的。非对称加密会产生公钥（Public Key）和私钥（Private Key）两把密钥，其中一把密钥用于加密，另一把密钥用于解密。非对称加密的安全性的提高依赖于算法强度的复杂性与减少了密钥的直接传输过程，因此非对称加密算法的效率相对于对称密码解密效率较低。常用的非对称加密算法有RSA、Elgamal、背包算法、Rabin、D-H等算法。

RSA加密技术属于非对称加密体制又称为双钥密码体制或公钥密码体制，是迄今为止发展较为成熟的公钥密码体制，也是非对称密码体制的的典型代表。RSA算法在网络与信息安全、身份认证、电子商务等方面有着广泛应用，如典型的在通信中的数字签名利用RSA算法实现对方身份的确定性验证。Alice要给Bob传送一个明文，但不是采用直接传输的方式传递。首先Alice告诉Bob，将会给Bob发送一个信息；然后，Bob会制作两把密钥，一把是公开密钥给Alice，一个是私有密钥只有Bob才有；Bob将公开密钥给了Alice，Alice将明文A加密成密文B，并传给Bob;Bob使用自己的私有密钥得到明文A。RSA加密过程主要包括两个方面：

• 制作所有人（Alice和Bob）可见的公钥e：

设两个互质的数p1和p2，n=p1∗p2，则φ(n)=(p1−1)∗(p2−1)，其中只有Bob知道φ(n)。Bob构造一个整数e，满足1<<e<φ(n),gcd(e,φ(n))=1,e=p1,p2。

• 制作只有收件人（Bob）可见的私钥d：

已知Bob构造的整数e，求出e对同余φ(n)的逆元d,即e∗d=1(mod φ(n))，即e∗d=1+k∗φ(n)，此时d即为Bob制作的私钥。引入任意整数a，只要a满足1≤a<n,a=p1,p2必有gcd(a,n)=1。

• 将所传递的信息加密（将明文加密成密文）并传输：

Alice已经告诉Bob，不久将会给Bob发送一个信息。在上一步骤中Bob已经制作了一把公钥和一把密钥，Alice和Bob都可见到公钥e。于是Alice利用Bob制作的公钥将明文a加密成只有Bob用私钥d才能打开的密文c，并将密文c以邮件等形式传送给Bob。

03 RSA算法实现

以下为RSA算法生成公钥和私钥，再对明文加密解密算法过程。

步骤1:Bob制作公钥e与私钥d

    from gcd import ext_gcd

    from exponentiation import exp_mode

根据密文情况选择两个大质数p、q，令n=p*q。用欧拉函数公式计算与n互质的整数个数。

def gen_key(p, q):
    n = p * q                
    fy = (p - 1) * (q - 1)      

制作公钥e，再由公钥e生成私钥d

    e = 65537                   
    a = e
    b = fy
    r, x, y = ext_gcd(a, b)   
    if x < 0:
        x = x + fy
    d = x    
    return    (n, e), (n, d)

步骤2：将明文a加密为密文c

def encrypt(a, pubkey):
    n = pubkey[0]
    e = pubkey[1]
    c = exp_mode(a, e, n)
    return a

步骤3：将密文c解密为密文a

def decrypt(c, selfkey):
    n = selfkey[0]
    d = selfkey[1]
    a = exp_mode(c, d, n)
    return a

代码来源：https://blog.csdn.net/bian_h_f612701198412/article/details/7935877

04 shor算法

shor算法也称秀尔算法，由数学家彼得·秀尔设计，主要用于解决找出一个给定整数N的质因数的问题即整数分解问题。Shor算法一经提出就引起极大轰动，按照Shor的算法思想，依赖于RSA算法加密技术的安全体系随着量子计算机的发展将被瓦解。虽然Shor算法利用了量子力学的多种特性显示出在RSA加密技术破解方面的优势，但真正利用Shor算法破解RSA还面临诸多技术挑战，如目前百比特量子计算机的现实与破解2048位RSA需要2000万-1亿的量子比特需求还相去甚远。Shor算法与Grover算法的思想共性在于都利用了量子计算的并行性特点对数据进行验证，本质上都是一种概率计算。下文将从shor算法原理及其实现方面揭开Shor的神秘面纱。

shor算法原理

量子计算的一个主要原理是使构成叠加态的各个基态通过量子门的作用相互干涉，从而改变它们之间的相对相位，使其概率振幅发生变化，从而使各个由基态所表示的运算结果被观测的概率发生变化。量子计算的另一个重要的机制是量子纠缠态，即对处于纠缠态的量子位中的某几位进行操作，不仅会改变这些量子位的状态，还会改变与它们相对纠缠的其他量子位的状态。Shor算法中得到量子傅里叶变换所需要的状态时，就利用了量子纠缠这一特性。一般而言，量子算法有两个储存器，我们分别称之为A储存器和B储存器。首先将A储存器中的量子比特进行旋转，得到储存器的计算初态；再通过多个逻辑门操作组成组合而成一个总的幺正算符U(f)，将U(f)作用于储存器A和B；利用量子算法的并行计算特性一次性计算出所有f的值；紧接着利用U中的相互作用，立即存入B存储器中对应的量子态，使A与B中的量子态产生纠缠；最后测量存储器A与B其中一个，造成另一个存储器坍缩。

Shor算法所解决的问题为设一个很大的奇数N，N为两个质数n1和n2的乘积，现在已知N求n1和n2。Shor算法求解的具体步骤包括：a.先取随机数找周期：先随机取一个小于N且与N互质的数y，按照欧拉定理一定可以找到N的周期r；b.求得周期r为偶数的同余式方程组:当周期r为奇数时，回到步骤a重新取y值，当r为偶数时取y^(r/2)=x可得x^2=1 mod N；c.求解公因子n1与n2并验证n1*n2=N：x^2=1 mod N方程得n1=gcd(x-1,N),n2=gcd(x+1,N)，即求得n1与n2。

05 Shor算法实现

以下对35做分解步骤如下:

首先需要准备六个量子比特：

function shor_sample()
{
    var N = 35;             // The number we're factoring
    var precision_bits = 6; // See the text for a description
    var coprime = 2;        // must be 2 in this QPU implementation
    var result = Shor(N, precision_bits, coprime);
    if (result != null)
        qc.print('Success! '+N+'='+result[0]+'*'+result[1]+'\n');
    else
        qc.print('Failure: No non-trivial factors were found.\n')
}

步骤1 Shor算法首先准备足够的量子比特对输入的较大整数做因式分解

function Shor(N, precision_bits, coprime)
{
    var repeat_period = ShorQPU(N, precision_bits, coprime); // quantum part
    var factors = ShorLogic(N, repeat_period, coprime);      // classical part
    return check_result(N, factors);
}

步骤2 求a与b的最大公因数

function gcd(a, b)
{
    // return the greatest common divisor of a,b
    while (b) {
      var m = a % b;
      a = b;
      b = m;
}
 }
    return a;

步骤3 验证整数N是否为分解的两因数乘积，如果验证结果正确则输出因子，若验证失败则重新返进行计算

function check_result(N, factor_candidates)
{
    for (var i = 0; i < factor_candidates.length; ++i)
    {
        var factors = factor_candidates[i];
        if (factors[0] * factors[1] == N)
        {
            if (factors[0] != 1 && factors[1] != 1)
            {
                // Success!
                return factors;
            }
        }
    }
    // Failure
    return null;
}

图为QCEgine中的一个Shor算法示例代码运行后输出的电路图

结尾

Shor算法的实现中的寻找周期r为Shor算法的关键步骤，也是量子计算并行计算优势的重要体现。虽然Shor算法的问世引发关于RSA安全性将受到威胁的争议，但从现实角度而言利用Shor算法破解RSA加密技术是量子比特数与RSA密码位数之间的博弈。此外，量子算法普遍采用一种验证的思想，是一种面对指数级数据的概率计算，关于量子算法计算结果的真实性与准确性将会在之后的文章中继续探讨。