现在，具体地谈一谈RSA的思想。

加密C≡Me(modn);

解密M≡Cd(modn);

其中M为明码，C为密码，(n，e)为公钥(加密钥)，d为私钥(解密钥)，并且要满足：n=pq，其中p和q为两个至少100位的素数;ed≡1(mod?准(n))，其中?准为欧拉函数，其计算公式为：如果n的标准分解为

n=p，

则准(n)=n(1-)。

(e，n)要公开出去，以便别人能用来对信息进行加密，但p和q(当然包括d)必须保护好，不能泄漏。RSA体制之所以能工作，是因为

Cd≡(Me)d≡Med≡M1+k?准(n)

≡M(M?准(n))k≡M(modn);

对于合法用户而言，因为他知道n=pq，故计算出?准(n)=(p-1)(q-1)，从而算出d≡1/e(mod?准(n))，这样他就可以对信息进行解密计算。上述计算的关键是欧拉函数。

显然，对于非法用户(即敌方)而言，要算出d，他必须先算出?准(n);而要算出?准(n)，他必须先分解n。如前所述，整数分解是个很困难的问题，事实上，在现有的计算条件下，当n为一个一般的大于200位的整数时，要分解n往往需要数亿年的时间。可以想像，任何一项秘密，过了数亿年的时间，其秘密性已不复存在了。因此，用RSA方法来加密信息还是很安全的(当然在具体实现上，其加密解密过程中的参数的选择还是很有讲究的)。

椭圆曲线密码体制简介

目前，国际上公认的比较安全实用的公钥密码体制是所谓的椭圆曲线密码体制。其思想是在基于有限域的椭圆曲线上对信息进行加密解密。由于有限域上椭圆曲线的离散对数实际上是一般有限域上的离散对数在椭圆曲线上的一种类比物，因此它至少在实用上比一般有限域上的离散对数的计算要困难些，因此其安全性也要强一些，当然目前人们还不能证明这一点。

椭圆曲线上的离散对数，可以认为是：给定有限域Fq(q=pr为素数幂)上的一条椭圆曲线y2=x3+ax+b，并给定这条曲线上的两点P和Q，求出正整数k(如果存在的话)，使之满足Q=kP，目前关于椭圆曲线离散对数问题还没有找到一种甚至是子指数(subexponential)复杂性的算法(对于整数分解与离散对数，已有子指数复杂性的算法)。西尔弗曼(J.H.Silverman)等人于2000年提出了一种称之为XedniCalculus的计算椭圆曲线离散对数的算法[5]，但该法过于复杂，并用了很多未被证明的数学结果，因此该法一是没有实用价值，二是连个复杂性的度量都提不出来。故而寻求快速实用的计算椭圆曲线离散对数的算法(哪怕是子指数复杂性的算法)是当前计算数论中的一项刻不容缓的艰巨任务。

下面介绍基于椭圆曲线的ElGamal公钥密码体制(其他的很多公钥密码体制都可以很容易地推广到椭圆曲线上去)。

A和B两人要事先在公开的通道上选定有限域Fq(其中q=pr，p为素数)上的一条椭圆曲线E，以及随机点P∈E(该点要能生成一个很大的子群，这个子群最好和椭圆曲线E本身所构成的群一样大或比较接近)。

A选定一个随机数a∈{1，2，…，q-1}(a可以认为是A之私钥)，并计算出aP(aP可以认为是A之公钥)，且将其传输给B;

B选定一个随机数b∈{1，2，…，q-1}(b可以认为是B之私钥)，并计算出bP(bP可以认为是B之公钥)，且将其传输给A;

现假定A要给B传输信息M(明码)。首先A要选定一个随机数k，并利用B的公钥bP计算出密码C=(kP，M+k(bP))，且将其传输给B。

为了能够将C变换回M，B需要对C进行解密计算，但由于B有b，所以他可以很容易地计算出M=M+k(bP)-b(kP)。

显然，敌方如能计算椭圆曲线上的离散对数，他就能从公开的信息P和bP中确定出b，从而破译C。遗憾的是，求解椭圆曲线上的离散对数比求解一般有限域上的离散对数更困难(前面讲到，求解一般有限域上的离散对数已经是一件很困难的事情了)，所以当所选的有限域Fq很大、所选的椭圆曲线以及这条曲线上的点P又很合适时，a或b是很难算出的，因此基于椭圆曲线离散对数的密码体制也就要更安全些(至少比基于整数分解或一般有限域上的离散对数的密码体制要更安全些)。另外，椭圆曲线密码体制与其他公钥密码体制相比，在钥的长度相同的情况下，它的安全性要更高些。正是基于上述这些原因，目前人们才会对椭圆曲线密码体制更感兴趣。

上面介绍的三种具有代表性的现代公钥密码体制，就是基于三种各不相同的数论难题的(即整数分解、离散对数以及椭圆曲线上的离散对数);目前世界上几乎所有具有实用价值的公钥密码体制，基本上都是基于这三种数论难题的。也就是说，事实上是将密码的加密、解密、破译等问题与数论难题的求解联系在一块了。密码难破译是因为数论问题难解。因此，在这里，不仅数论本身的理论与方法有实用价值，就是数论里的难题也为现实生活提供了应用的场所。也许正因为如此，国际数学大师陈省身先生才会主张把数论作为一门应用数学学科[6]。值得特别一提的是，数论密码是目前密码学中的主流学科，限于篇幅，这里不再对其做深入的介绍[3,7]。

(本文作者为南开大学信息技术科学学院特聘教授。)

[1]DiffieW,HellmanE.IEEETransactionsonInformationTheory,1976，22(5)：644

[2]MerkleRC.CommunicationsoftheACM,1978，21(4):294

[3]YanSY.NumberTheoryforComputing,2ndEdition.NewYork:Springer-Verlag，2002

[4]RivestRL,ShamirA,AdelmanL.CommunicationsoftheACM,1978，21(2):120

[5]YanSY.InternationalJournalofComputerMathematics,2003,80(5)：573

[6]陈省身.数学进展，1992，21(4)：385

[7]颜松远.数学的实践与认识,2002，32(3):486

精品学习网 数学论文栏目