【编者按】：数学论文是科技论文的一种是用来进行数学科学研究和描述研究成果的论说性文章。精品学习网论文网为您提供数学论文范文参考，以及论文写作指导和格式排版要求，解决您在论文写作中的难题。

数论密码，顾名思义，就是基于数论的密码。密码是相对于明码而言的。这是一个矛盾的两个方面。所谓明码(plaintext)，就是人们可以直接识别或使用的代码(也就是人们通常所说的信息，如文字、声像等);所谓密码(ciphertext)，就是将明码经过了一定处理，变换成一种外人(与此无关的人员)无法直接识别或使用的信息。

比如在军事上，上级首脑机关向部下发布军令时，就往往需要将军令的原文(明码)变换成密码之后再发布(比如通过无线电台或计算机网络等向外发布)。这样，即使敌方能够截获到这些密码，也无法直接辨别出这些密码的原意。当然，对于自己的部下而言，由于他们事先已经拥有解开这些密码的钥匙，所以能够正确地将密码再变换回明码，从而可以执行军令。

密码学就是一门研究信息的加密(encryption)与解密(decryption)技术(统称为cryptography)，以及密码破译(cryptanalysis)技术的学问。密码学有两个显著特点：一是历史悠久(事实上，密码学的历史几乎与人类文明史一样长)，二是数学性强(几乎所有的密码体制都程度不同地使用了数学的方法，尤其是代数、几何与数论的方法)。本文着重介绍基于数论的密码方法。

数论：从纯粹走向应用

数论是数学中最古老、最纯粹的一个重要数学分支。素有“数学王子”之称的19世纪德国数学大师高斯就曾说过，数学是科学的皇后，数论是数学的皇后。数论的一个主要任务，就是研究整数(尤其是正整数)的性质(包括代数方程的整数解)。由于在研究这些整数的过程中，人们往往要用到别的数学分支的知识与技巧，这样就诞生出了解析数论、代数数论、组合数论、概率数论、几何数论甚至计算数论等分支学科。

由于整数的性质复杂深刻，难以琢磨，因此数论长期以来一直被认为是一门优美漂亮、纯之又纯的数学学科。美国芝加哥大学著名数学家迪克森(L.E.Dickson)就曾说过：感谢神使得数论没有被任何应用所玷污。20世纪世界级数学大师、剑桥大学的哈代也曾说过：数论是一门与现实、与战争无缘的纯数学学科。哈代本人也则因主要从事数论的研究而被尊称为“纯之又纯的纯粹数学家”。

当然，上述两位大数学家所说的并不完全符合今天的现实。事实上，在计算机科学与电子技术深入发展的今天，数论已经不仅仅是一门纯数学学科，同时也是一门应用性极强的数学学科，比如在今天，数论已经在诸如物理、化学、生物、声学、电子、通讯，尤其是在密码学中有着广泛而深入的应用。

大家知道，密码设计长期以来一直是困扰军方的一个问题。要保证军方的密码不被敌方破译，不是件容易的事情。比如在第二次世界大战期间，德军设计了一种性能优良的编制密码的机器，称之为爱尼格玛(Enigma)机器。德军指挥机关向其部队发布的军令都是通过爱尼格玛机器加密之后再往下发布的。当时英军就想到，要打败德军，就必须要破译德军的密码，掌握德军的军事动向(即所谓的知彼知己)。因此，英军迅速在伦敦北边不到一百公里处征集了一块空旷的土地(该地名为布莱克利公园，后也成了该秘密机构的名字)，并在那里集结起一大批杰出的数学家、语言学家和象棋大师等，包括现代计算机科学的开山鼻祖图灵和后来在爱丁堡大学创办世界上第一个人工智能系的米基(D.Michie)。他们专门负责截获、破译爱尼格玛密码。由于这个组的努力，特别是图灵出色的工作，他们掌握了破译该密码的一整套方法，从而了解德军的军事动向，掌握了战争的主动权，为英美联军击败德军作出了突出的贡献。有人估算，如果没有图灵等人的贡献，第二次世界大战至少还要再打十年。

DHM的提出

目前，由于商用计算机网络的广泛应用，尤其是电子商务的普及与深入，密码设计在民间也大有用武之地。传统的密码体制，称之为“密钥密码体制”，在加密、解密的过程中都采用同一个钥，简称为“密钥”(secretkey)。所谓同一个钥，就是说知道了其中的一个钥，另一个钥就可以很容易地计算出来。具体到军用通讯，就是军事指挥机关要事先用密钥把军令加密，之后再下达到部队，与此同时(甚至是事先)还要将密钥也下达到部队，否则其部下解不开其军令。显然，密钥的管理与保护是个问题。一般而言，密钥比密码本身还重要，因为一旦敌方掌握了密钥，那么所有用此密钥加密的密码就成了人所皆知的明码。因此，在军事与外交等部门，都是不惜代价而派专人专管专送密钥。显然，这在电子商务方面是行不通的，因为代价太高。

1976年，美国斯坦福大学教授赫尔曼(E.Hellman)和他的研究助理迪菲(W.Diffie)，以及博士生默克勒(R.C.Merkle)(简称为DHM)首先创立并发表了所谓的“公钥密码体制”(publickeycryptography)，即加密、解密用两个不同的钥，加密用公钥(publickey)，即可以公开，不必保密，任何人都可以用;解密用私钥(privatekey)，此钥必须严加管理，不能泄漏。更为称绝的是，他们还发明了所谓的数字签名(digitalsignatures)技术，即用私钥签名，再用公钥验证。

在一般参考文献中，都认为公钥密码体制是迪菲和赫尔曼发明的[1]，可鲜为人知的是，默克勒甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的[2]，但投稿比较早。因此，公钥密码体制的创始人应该是DHM三人，这种观点目前已得到了国际上的认同，尤其得到了赫尔曼教授本人的认定。当然，英国军用情报中心也曾宣称他们早在1970年就发明了公钥密码体制，但经仔细分析其资料并与中心有关人员讨论后发现，他们只是提及了公钥密码体制的某种特殊形式。更为重要的是，DHM的公钥密码体制还包含数字签名，而情报中心的资料则是只字未提。注意，美国国家安全局也有过类似的宣称，不过这都是不可信的(至少不可全信)。如要详细了解公钥密码体制的发展史，读者可参考笔者的一本由赫尔曼教授作序的英文专著[3]。

当然，DHM只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。不过，他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。这里必须先介绍一下什么叫离散对数。

所谓离散对数，就是给定正整数x，y，n，求出正整数k(如果存在的话)，使y≡xk(modn)。就目前而言，人们还没有找到计算离散对数的快速算法(所谓快速算法，是指其计算复杂性在多项式范围内的算法，即O(logn)k，其中k为常数)。虽然有快速计算离散对数的量子算法，其计算复杂性为O(logn)2+?着，但现在并没有量子计算机(实用的量子计算机也许根本就建造不出来)。

现在，说明一下DHM的运作过程(假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用)。

首先，A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g;

A选定一个随机数a∈{1，2，…，q-1}(a可以认为是A之私钥)，并将ga(modq)传送给B;

B选定一个随机数b∈{1，2，…，q-1}(b可以认为是B之私钥)，并将gb(modq)传送给A;

此时A可以算出(gb)a(modq)，B也可以算出(ga)b(modq)，由于(gb)a(modq)=(ga)b(modq)=gab(modq)，因此，A和B就形成了一个公共的密钥gab(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。

显然，敌方可以截获到g，q，ga(modq)，gb(modq)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出gab(modq)。遗憾的是，目前世界上根本就没有快速的求解离散对数的算法，因此当所选的有限域Fq很大时，a或b就很难算出。值得注意的是，DHM密钥交换体制实际上是一座沟通密钥密码体制与公钥密码体制的桥梁，即用公钥密码体制的思想形成密钥(虽然公钥密码体制计算速度慢，但密钥的长度一般都很短，所以没有关系)，再用密钥进行传统的密钥密码体制的加密与解密运算(密钥密码体制的运算速度一般都很快，所以适合于对容量大的信息进行加密解密计算)。在这里，这两种密码体制交*使用，扬长避短，充分发挥了各自的优越性。

下面给出一个关于具体计算离散对数的实例。

A和B先约定公共的q=2739·(7149-1)/6+1和g=7。

A选随机数a，并计算7a(modq)，且将其送给B(注：a不能向外泄漏);

B收到7a=127402180119973946824269244334322849749382042586931621654557735290322914679095998681860978813046595166455458144280588076766033781;

B选随机数b，并计算7b(modq)，且将其送给A(注：b不能向外泄漏);

A收到7b=18016228528745312444782834836799895015967046695346697313025121734059953772058475958176910625380692101651848662362137934026803049。

此时A和B都能计算出密钥7ab(modq)，但别人不太容易算出，因为别人不知道a和b。有兴趣的读者不妨将此作为一个练习，试着计算出7ab(modq)的值。

RSA体制

1978年，仅在DHM发明公钥密码体制的两年后，美国MIT的三位科学家里维斯特(R.L.Rivest)，沙米尔(A.Shamir)和阿德尔曼(L.Adleman)(简称RSA)就提出了一种基于整数分解困难性的实用的公钥密码体制[4]，现通称为RSA体制。

所谓整数分解，可以认为是给定大于1的正整数n，求出正整数a和b，使之满足n=ab，其中a和b可以是素数，也可以是合数。根据算术基本定理，只要能够快速求出a，b，那么就能递归地快速求出n的素数分解式n=p1p2…pk，其中?琢i为正整数，pi为素数，i=1,2,…,k。现在的问题是，人们根本就没有满意的快速整数分解算法，目前世界上最快的整数分解算法是波拉德(J.Pollard)首创的数域筛法(NFS)。

波拉德是英国的数学奇才，曾在剑桥大学念数学本科，但因毕业考试不及格而肄业，后来因在计算数论中作出突出贡献而被剑桥免试授予博士学位。无独有偶，剑桥出身的另一位著名数学家罗斯(K.Ruth)也是因为在念本科时考试成绩不好而勉强毕业，后来却因在数论研究中取得杰出成就而获得菲尔兹奖，剑桥则因此而授予其名誉博士学位。

数域筛法的计算复杂性为O(exp(c(logn)1/3(loglogn)2/3))，其中c为一实常数，1