公钥密码学的思想起源于Diffie与Hellman[1],提出把密码体制的加密密钥(公钥)与解密密钥(私钥)分开处理,以提高多用户保密通信的效率.其中,加密密钥是公开的,解密密钥是每个用户自己保密的,这样,从公钥计算出私钥是困难的.在这篇论文中,Diffie和Hellman并没有一个数学手段去实现他们的思想,而是提出实现公钥密码体制用单向函数(one-way function),直观地说,就是函数f(x)从x很容易计算f(x),但从y=f(x)很难计算x.在这篇论文中,他们也讨论了在不安全信道下建立密钥的方法,即现在称为Diffie-Hellman密钥交换(亦称Diffie-Hellman-Merkle key exchange)的内容.这个问题Merkle差不多同时也给出了解决方法[2].Merkle后来的博士论文导师即是Hellman.
1977年,文献[3]就报道了3位MIT的学者设计出了第1个公钥密码体制.1978年,Rivest,Shamir和Adleman发表了文献[4],提出用两个素数乘积的模同余类的幂运算来实现公钥密码体制.其中的关键单向函数是从两个素数算出其乘积是容易的,但是任给一定规模大的数(即使知道其是两个素数乘积),将其分解为素数因子乘积是困难的.RSA公钥密码体制是专利技术,1982年成立的RSA公司即以其为基础向IT工业界提供安全产品,2006年被美国EMC公司收购.
实际上,公钥密码学思想和RSA公钥密码体制及Diffie-Hellman-Merkle密钥交换(key exchange)的思想在1970年~1976年由为英国政府通信总部(government communications headquaters,简称GCHQ)工作的数学家Ellis(1970年提出公钥密码体制思想),Cocks(1973 年提出RSA),Williamson(1974~1976年提出key exchange)等人得到.GCHQ是英国国家安全通信机构,为其工作的数学家的工作是否公开是由政府决定的.这些文件直到1997年才可公开.1997年12月18日,在一个公开演讲中,Cocks公开了这段历史,这时,Ellis已经去世22天了.
1 . 公钥密码体制的早期密码分析与计算数论的起源从RSA公钥密码体制和密钥交换(key exchange)的构造,人们已经清楚两类单向函数:一类是数的素数因子分解,一类是有限域的离散对数.这直接刺激了这两个数学问题的算法学研究,即计算数论学科的来源(computational number theory).例如,我们可以在文献[5, 6, 7]中知道计算数论的风格.文献[6]文预印本1984年开始流传,刺激了1985年Koblitz[8]和Miller[9]分别独立地提出椭圆曲线公钥密码体制,椭圆曲线公钥密码体制没有专利.
一般而言,对阶为n的抽象循环群,计算其离散对数是$ O\left( {\sqrt n } \right)$ 困难的,并且这是最好的可能(victor shoup),Coppersmith[7]提出的算法说明:对特征2的有限域的离散对数问题,算法是$ O\left( {{n^{\frac{1}{3}}}} \right)$ 困难的.
一般而言,对大数分解和有限域离散对数问题最好的算法是数域筛法(number field sieve)和函数域筛法,例如,在Crypto2010上就报道了此方法对一个RSA-768模数的分解[10].我们同样建议参考关于RSA模数分解报道的网站:http://smartfacts.cr.yp.to/按照Diffie的论文[13],我们在公钥密码学的早期历史中必须提到的是Merkle-Helleman基于背包(knapsacks)公钥密码体制[15]和McEliece的基于代数编码(Goppa编码)的公钥密码体制[14].在基于代数编码的公钥密码体制中,困难的问题是把代数编码伪装成一般编码,其解码问题(decoding)已经被Berlekamp,McEliece和Tilborg证明是NP-完全.Diffie写道:因为基于代数编码的McEliece公钥密码体制的公钥要求几乎百万级别的比特,所以看来是永远不会实际使用的.McEliece公钥密码体制仍然是公钥密码分析的一个很受到注意的课题,可参见Minder等人的工作[16].
Merkle-Hellman的背包(knapsack)公钥密码体制是基于子集合问题(subset sum problem)的,这是NP-完全的问题,但其中用了super-increasing,在其提出4年以后的1982年,Shamir[17, 18]就用当时刚提出的格(lattice)的LLL(Lenstra-Lenstra-Lovasz)算法破解,这是以后格算法在密码分析中扮演重要角色的起源.LLL算法[19]是有理系数多项式分解的多项式时间算法,LLL算法后来成为基于格的密码分析基石.
多变量多项式公钥密码体制起源于Matsomoto-Imai在Eurocrypt 1988会议上提出的Matsomoto-Imai 方案,其想法是,基于解一般多变量代数方程组(即使是2次的)是NP-完全[22].后来,在该体制被法国密码分析学者Patarin破解并发展[23, 24],Matsumoto-Imai更早期(1983年)的一个用单变量多项式的公钥密码体制很快就被Delsarte-Desmedt-Odlyzko-Piret在Eurocrypt 1984会议上破解[20, 21].关于这个领域最新的一些成果,我们可以参见Dubois和Ding近年的论文.
在Diffie的上述公钥密码学综述中[13],他也提到了1979年Shamir和Blakley提出的秘密共享,这后来成为理论密码学的重要基础理论安全多方计算的基础.
从早期公钥密码体制的密码分析的历史发展可以看出:人们原来设想的基于NP-hard(完全)问题做些变形设计的公钥密码体制实际上都不牢靠,而基于分解(factoring)这个目前并不知道是不是NP-hard问题的RSA公钥密码体制反而经受住了考验.
公钥密码学早期的重要思想家包括:
· Whitfield Diffie(1944-),2010年被授予IEEE Richard W. Hamming奖;
· Mrtin Hellman(1945-),2010年被授予IEEE Richard W. Hamming奖,1987年后投身于反战运动,从事原子战争的风险分析;
· Ralph Merkle(1952-),对公钥密码学的早期起源和密码Hash函数都做出贡献,2010年被授予IEEE Richard W. Hamming奖,现在从事纳米技术研究;
· Rivest-Shamir-Adleman,2003年被授予ACM Turing award,这也是计算机科学界最高奖第1次授予密码学.第2次是2012年授予ShafiGoldwasser(1958-)和Silvio Micali(1954/10/13-);
· Ron Rivest(1947-),现在MIT工作.除RSA外,对密码Hash函数、电子选举都做出贡献;
· Adi Shamir(1952-),现在Weizmann Institute of Science工作.除RSA,对于密码分析、秘密共享等做出多种贡献;
· Leonard Adleman(1945-),现在南加州大学,除RSA对计算数论的起源做出很大贡献,也是DNA计算的提出者.
2 . 有限域离散对数的Barbulescu-Gaudry-Joux-Thome算法目前,关于有限域离散对数问题的最新进展见文献[11, 12].前面提到的Coppersmith算法的思想对于有限域的离散对数问题的后续工作是重要的,Joux于2013年在国际密码学会网站张贴的论文《A new index calculus algorithm with complexity L(1/4+o(1)) in small characteristic》首次提出经验式算法可以把小特征例如2的有限域离散对数算法计算量做到L(1/4),这个经验式算法依赖于一些有限域上多项式的假设.这个工作后来被他和合作者一起深化,即文献[11]的Barbulescu-Gaudry-Joux-Thome(BGJT)算法,当然仍是经验式的.后来一些工作,如文献[12]等探讨了其经验式假设成立的情况及算法的修正,我们下面简单介绍BGJT算法的思路.
BGJT算法的第1步是嵌入,这个思路是Joux的,就是把一个小特征的有限域$ {F_{{p^n}}}$ 嵌入在$ {F_{{q^{2m}}}}$ 中,并且希望可以找到$ {F_{{q^2}}}$ 上的低度数多项式h0(x)和h1(x),使得h(x)=h0(x)xq-h1(x)有一个度数不超过m的不可约化因子多项式g(x)可以表达有限域$ {F_{{q^{2m}}}}$ .这一步需要经验式假设的.
BGJT算法的第2步是用$ {F_{{q^2}}}[x]$ 中的首一线性多项式h(x),$ F_{{q^2}}^*$ 的一个生成元作为指标计算法(indexcalculus)的分解基(factor base),并且要求出其所有关系.上面这些多项式都是模g(x)运算的.由有限域的结果知道:上面的分解基确实是生成所有$ {F_{{q^{2m}}}}$ 的非零元素乘法群的,但是确定所有关系需要经验式假设.
BGJT算法的最后一步(decent step)是将$ {F_{{q^{2m}}}} = {F_{{q^2}}}[x]/g(x)$ 中的非零元素表示为分解基中元素的乘积,这里也需要经验式假设才可以在拟多项式时间完成.
BGJT算法本质上依赖于上述特定的低度数多项式表达有限域中元素、分解基关系的有效确定和最后一步的有效表达,其主要思想正如Joux在他2013年的论文提到的,是Coppersmith思想的非常广泛的拓展.目前,对这个算法的经验式假设在怎样情形成立有许多分析.在他们的论文里,对有限域$ {F_{{2^{4080}}}}$ 的离散对数进行了有效的计算.
3 RSA密码分析的近期进展 3.1 经典结果关于RSA的密码分析,1998年,Boneh的综述论文[25]仍然是很好的参考.近年来,德国学者Alexander May对RSA密码分析做了很多系统深入的工作,见http://www.cits.rub.de/personen/may.html,这里只简单介绍以下几个方面.这些虽然不是实际使用RSA中最常见情况,但体现了目前的数学和算法学手段可以达到的高度.
(1) 小私钥情况
(2) 部分信息泄露情况
在情况(1),其典型的结果是Wiener于1990年的结果[26],如果模N=pq,p和q是满足q<p<2q的素数,并且私钥$ d < \frac{1}{3}{N^{\frac{1}{4}}}$ ,那么从公开的模N和公钥e可以多项式时间计算出私钥d.这个结果在1998年被Boneh和Durfee改进为只要d<N0.292,也可以从模和公钥有效计算出私钥[27].
情况(2)的研究起源于Coppersmith在1996年提出的用LLL算法求整数系数的单变量多项式方程的小根[28],其应用于RSA密码分析有很多结果,例如,Coppersmith[28]当时给出:如果RSA模N是n比特的,如果N的某个素因子的最低或最高$ \frac{n}{4}$ 位置比特泄露,那么可以在多项式时间分解N.这些研究在后来May,Coron,Heninger,Shacham,Joux等人的工作中有很多发展.
3.2 Heninger-Shacham经验式算法实际使用RSA的密码分析常常是结合各种侧信道攻击(side-channel attack)得到部分信息加上情况2)的数学和算法学的研究成果,见文献[29, 30].
Heninger和Shacham文献[30]的主要结果是:在小公钥RSA情况下,只要私钥d及p,q,dp,dq的0.27随机部分比特泄露,那么其给出的算法可以算出私钥.但是这个算法依然是经验式的,依赖于一些算法上的假设.
Heninger-Shacham算法的主要数学思想来源于Boneh-Durfee-Frenkle于1998年在亚洲密码会的论文,在小公钥e的情况下,ed,edp,edq关于(p-1)(q-1),(p-1),(q-1)的倍数是可以分析的,而其中实际的那个倍数是真实私钥对应倍数的很好逼近.这样,通过一系列算法实验找出真实的私钥d,在模数N的因子p和q及私钥d的随机0.42部分比特泄露的情况下,他/她们的经验式算法也可以恢复私钥d.
上述工作中的假设随机比特泄露比早期经典结果假设的特定比特泄露更接近实际情况,如文献[29]所提出的cold boot攻击下,实际是可能发生随机比特的泄露.
4 ECC密码分析的最新进展椭圆曲线公钥密码体制和RSA不同的是可以选择不同有限域上的不同椭圆曲线做出密码体制,很可能,这些不同的选择导致的公钥密码体制性质是完全不同的.我们主要叙述有限域上椭圆曲线上离散对数问题的研究进展,现状是可以区分出一些类别的椭圆曲线,其离散对数问题相比困难的算法将更为有效.
4.1 经典结果首先要提到的是1993年的基于Weil pairing attack(MOV attack)[31],其基本原理是:可用Weil pairing将椭圆曲线的离散对数转化为一定扩域(指定义椭圆曲线基域的扩域)上的离散对数问题,在嵌入次数(embedding degree)不要太大,即,这个扩域不太大时,有限域的离散对数可以更有效解决.在文献[32]中,这个办法可以用椭圆曲线的Tate pairing实现.后来,一个本质的进步是1998年~1999年的Samaev[33],Satoh-Araki[35],Smart[34]这3人独立地区分出所谓的Anomalous椭圆曲线,即这种椭圆曲线对最低的基域GF(p),如果其GF(p)有理点个数可被p整除,那么其离散对数也是可以有效求出的.
4.2 Gaudry-Hess-Smart攻击Frey在1990年代末期就提出,Weil decent(一种代数几何技巧)可以用来处理椭圆曲线的离散对数问题. Gaudry等人对某些类别的超椭圆曲线的Jacobian得到一些关于glog q的有效算法后,结合这个想法,在2000年提出了基于Weil decent的离散对数算法,现在被广泛称为Gaudry-Hess-Smart攻击[36, 37].其基本原理是:对复合基域,即,定义椭圆曲线的基域是GF(pmn)形式,并且Weil decent转化为超椭圆曲线离散对数问题有效算法后,那么该椭圆曲线的离散对数问题存在有效算法.在文献[38, 39]中,对一些具体的复合基域,Menezes等人对其上有多少椭圆曲线可能对GHS攻击是虚弱的给出了分析.GHS攻击后来还有发展,见Smart的网页http://www.cs. bris.ac.uk/~nigel/.
4.3 基于Samaev多项式的Gaudry-Diem攻击Samaev于2004年提出了关于有限域上椭圆曲线的点和为0导致的坐标多项式关系[40],即:如果椭圆
曲线上的点(x1,y1),(x2,y2),…,(xm,ym)在椭圆曲线上和运算为0,那么坐标点x1,x2,…,xm必须满足多项式关系,这称为m阶Samaev和多项式,其算法时间是$ {e^{{m^2}\log q}}$ 的多项式.
Gaudry和Diem提出了复合基域上的利用Samaev和多项式的指标计算(index calculus)算法,例如,
Gaudry的分解基(factor base)$ {F_{{q^n}}}$ 是上椭圆曲线的使得其中坐标x在基域Fq中的所有点(x,y),而Diem的分解基$ {F_{{q^n}}}$ 是上椭圆曲线的使得x在$ {F_{{q^n}}}$ 的随机的Fq上线性子空间中的所有点(x,y),这时候,Samaev和多项式就可以用来计算上椭圆曲线上点的一系列表示为分解基的线性关系,这里实际上是表示为大量的代数关系式,
所以Gorbner基方法也扮演了关键的角色.他们设计了算法,并理论上分析这将是很有效的[41, 42].目前,这种算法的深入理解与实验分析是这个领域研究的重要热点,见文献[43, 44].
5 . 补充及一些重要的密码分析学家NTRU是1996年Brown大学的数学家Hoffstein,Pipher和Silverman提出的公钥密码体制(包括数字签名),是利用整数系数多项式环的代数运算及模运算给出的密码体制.自提出以来,其安全性一直受到质疑.例如,Coppersmith和Shamir给出了基于LLL恢复私钥的攻击[45].关于NTRU分析的近期进展,见文献[46, 47, 48, 49, 50].
关于格算法在公钥密码分析中的作用,见Nguyen的网页http://www.di.ens.fr/~pnguyen/.
关于Grobner基算法在公钥密码分析中的作用,见Faugere的网页http://www-salsa.lip6.fr/~jcf/.
重要的密码分析学家有:
· Adi Shamir,见第2节的描述;
· Don Coppersmith(1950-),重要的密码分析学者,对RSA,NTRU和有限域离散对数及数域筛法等做出重要贡献;
· Hendrik W. Lenstra(1949-),对整数分解算法(factoring)、LLL算法、数域筛法等作出重要贡献;
· Arjen K. Lenstra(1956-),对整数分解算法(factoring)、LLL算法、数域筛法、Hash函数分析等做出重要贡献;
· Andrew Odlyzko(1949-),对有限域离散对数、背包(knapsack)密码体制分析、整数分解算法等做出重要贡献;
· Jacques Stern(1949-),法国密码学派的奠基人,在多变量公钥密码体制分析、格密码分析等领域起到开拓作用;
· Antoine Joux (1967-),对公钥密码体制的密码分析的各个领域做出重要贡献.
6 . 总结和展望自公钥密码学诞生以来,随着公钥密码体制在通信和计算机网络中的大量使用,公钥密码体制的密码分析已经是一个国家国防、金融等关键部门信息安全保障实力的重要基础.此领域也已经发展成为大量使用计算机科学技术与数学的各种优秀成果达到密码分析目的多学科交叉研究领域.正是由于其交叉与需要大量算法实验等各种特点,在国内公开密码学界,集中从事公钥密码体制密码分析的研究人员还没有形成强大的研究队伍,本文可以给希望学习此研究领域的同行和研究生起到理清文献与历史发展线索的作用.
从RSA公钥密码体制的分析发展可以看出:May,Coron等人的工作及第3.2节的Heninger- Shacham经验式算法以后,思路上没有突破,但是国际密码学界仍然非常重视Coppersmith利用格方法求整系数单变量方程小根的算法,并力图精化其思想,而且非常关注这个思想是不是可以拓展到多变量尤其是两个变量情况,这是一个值得关注的研究方向.
在最近几年,尤其是2010年~2014年,在有限域离散对数和椭圆曲线离散对数问题上,国际密码学界与计算数论界已经取得了突破性进展.国内密码学界和数学界开始关注这些领域的进展,如果年轻学者能够加强计算数论和算法学的基础学习,是可以迎头赶上的,对文献[11, 12, 29, 30, 41, 42, 43, 44]中的经验式假设的分析进行更进一步的研究会很有益处.
公钥密码分析虽然经过多年的发展已经有大量文献,但是我们可以看出:其发展思路还是有线索可寻的,尤其是Coppersmith的一些思想,格算法和Gorbner基算法的巧妙使用都是极为重要的.学习这一领域的最新进展,并在这些工作基础上做出中国密码学者自己的世界水平的公钥密码分析工作,对国家的基本信息安全保障能力的真正提升做出贡献.