数论密码的数论

数论与密码的关系~

这里主要是公共密码系统依赖于因子分解的数论知识。两个素数的乘积很好算，反过来一个合数的素分解很困难，这样可以设置公共密码，相互可以解读，但第三方想知道这双方传递的信息就很难。另外，对一个大数，判断它是否是素数也需要数论知识。更复杂的密码是用有限域上椭圆曲线的离散算法编制的，这也需要很多数论知识。

1976年，美国斯坦福大学教授赫尔曼(E.Hellman)和他的研究助理迪菲(W.Diffie)，以及博士生默克勒(R.C.Merkle)（简称为DHM）首先创立并发表了所谓的“公钥密码体制”（public key cryptography），即加密、解密用两个不同的钥，加密用公钥（public key），即可以公开，不必保密，任何人都可以用；解密用私钥（private key），此钥必须严加管理，不能泄漏。更为称绝的是，他们还发明了所谓的数字签名（digital signatures）技术，即用私钥签名，再用公钥验证。
在一般参考文献中，都认为公钥密码体制是迪菲和赫尔曼发明的[1]，可鲜为人知的是，默克勒甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的[2]，但投稿比较早。因此，公钥密码体制的创始人应该是DHM三人，这种观点目前已得到了国际上的认同，尤其得到了赫尔曼教授本人的认定。当然，英国军用情报中心也曾宣称他们早在1970年就发明了公钥密码体制，但经仔细分析其资料并与中心有关人员讨论后发现，他们只是提及了公钥密码体制的某种特殊形式。更为重要的是，DHM的公钥密码体制还包含数字签名，而情报中心的资料则是只字未提。注意，美国国家安全局也有过类似的宣称，不过这都是不可信的（至少不可全信）。如要详细了解公钥密码体制的发展史，读者可参考笔者的一本由赫尔曼教授作序的英文专著[3]。
当然，DHM只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。不过，他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。这里必须先介绍一下什么叫离散对数。
所谓离散对数，就是给定正整数x，y，n，求出正整数k（如果存在的话），使y≡xk(mod n)。就目前而言，人们还没有找到计算离散对数的快速算法（所谓快速算法，是指其计算复杂性在多项式范围内的算法，即O(logn)k，其中k为常数）。虽然有快速计算离散对数的量子算法，其计算复杂性为O(logn)2+?着，但现在并没有量子计算机（实用的量子计算机也许根本就建造不出来）。
现在，说明一下DHM的运作过程（假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用）。
首先，A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g；
A选定一个随机数a∈{1，2，…，q-1}（a可以认为是A之私钥），并将g a(modq)传送给B；
B选定一个随机数b∈{1，2，…，q-1}（b可以认为是B之私钥），并将gb(modq)传送给A；
此时A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一个公共的密钥g ab(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。
显然，敌方可以截获到g，q，g a(modq)，g b(modq)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出g ab(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=p1 p2…pk，其中?琢i为正整数，pi为素数，i=1,2,…,k。现在的问题是，人们根本就没有满意的快速整数分解算法，目前世界上最快的整数分解算法是波拉德（J.Pollard）首创的数域筛法（NFS）。
波拉德是英国的数学奇才，曾在剑桥大学念数学本科，但因毕业考试不及格而肄业，后来因在计算数论中作出突出贡献而被剑桥免试授予博士学位。无独有偶，剑桥出身的另一位著名数学家罗斯（K.Ruth）也是因为在念本科时考试成绩不好而勉强毕业，后来却因在数论研究中取得杰出成就而获得菲尔兹奖，剑桥则因此而授予其名誉博士学位。
数域筛法的计算复杂性为O(exp(c(logn)1/3(loglogn)2/3 ))，其中c为一实常数，1
现在，具体地谈一谈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年提出了一种称之为Xedni Calculus的计算椭圆曲线离散对数的算法[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]。

就是给定正整数x，y，n，求出正整数k（如果存在的话），使y≡xk(mod n)。就目前而言，人们还没有找到计算离散对数的快速算法（所谓快速算法，是指其计算复杂性在多项式范围内的算法，即O(logn)k，其中k为常数）。虽然有快速计算离散对数的量子算法，其计算复杂性为O(logn)2+?着，但现在并没有量子计算机（实用的量子计算机也许根本就建造不出来）。
现在，说明一下DHM的运作过程（假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用）。
首先，A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g；
A选定一个随机数a∈{1，2，…，q-1}（a可以认为是A之私钥），并将g a(modq)传送给B；
B选定一个随机数b∈{1，2，…，q-1}（b可以认为是B之私钥），并将gb(modq)传送给A；
此时A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一个公共的密钥g ab(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。 下面给出一个关于具体计算离散对数的实例。
A和B先约定公共的q=2739·（7149-1）/6+1和g=7。
A选随机数a，并计算7a(modq)，且将其送给B（注：a不能向外泄漏）；
（见扩展阅读）
此时A和B都能计算出密钥7ab(modq)，但别人不太容易算出，因为别人不知道a和b。有兴趣的读者不妨将此作为一个练习，试着计算出7ab(modq)的值。 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=p1 p2…pk，其中?琢i为正整数，pi为素数，i=1,2,…,k。现在的问题是，人们根本就没有满意的快速整数分解算法，目前世界上最快的整数分解算法是波拉德（J.Pollard）首创的数域筛法（NFS）。
波拉德是英国的数学奇才，曾在剑桥大学念数学本科，但因毕业考试不及格而肄业，后来因在计算数论中作出突出贡献而被剑桥免试授予博士学位。无独有偶，剑桥出身的另一位著名数学家罗斯（K.Ruth）也是因为在念本科时考试成绩不好而勉强毕业，后来却因在数论研究中取得杰出成就而获得菲尔兹奖，剑桥则因此而授予其名誉博士学位。
数域筛法的计算复杂性为O(exp(c(logn)1/3(loglogn)2/3 ))，其中c为一实常数，1
现在，具体地谈一谈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年提出了一种称之为Xedni Calculus的计算椭圆曲线离散对数的算法[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]。

数论密码的数论
答：上面介绍的三种具有代表性的现代公钥密码体制,就是基于三种各不相同的数论难题的(即整数分解、离散对数以及椭圆曲线上的离散对数);目前世界上几乎所有具有实用价值的公钥密码体制,基本上都是基于这三种数论难题的。也就是说,事实上是将密码的加密、解密、破译等问题与数论难题的求解联系在一块了。密码难破译是因为数论...

数论密码数论
答：椭圆曲线密码体制，以基于有限域的椭圆曲线上的离散对数难题为理论基础，提供了更为安全的公钥密码。相比于其他方法，它在安全性上有明显优势，因此成为现代密码学中的主流。综上，数论在密码学中的应用不仅展示了其理论价值，也反映了数论难题在现实世界中的实际应用，使其成为一门兼具理论和实际意义的应...

密码学:数论基础
答：如果我们用 代替 ， 称为此过程称为模约化，而 代表了 除以 的余数 对于 ，如果 整除 ，则称“ 同余于 模 ”，记做 我们定义算术模 为 ：表示具有两个运算符 （加法）和 （乘法）的集合 。 中的加法和乘法与实数加法和乘法完全一样，只是结果要进行模 约化。讲...

数论与密码的关系
答：这里主要是公共密码系统依赖于因子分解的数论知识。两个素数的乘积很好算，反过来一个合数的素分解很困难，这样可以设置公共密码，相互可以解读，但第三方想知道这双方传递的信息就很难。另外，对一个大数，判断它是否是素数也需要数论知识。更复杂的密码是用有限域上椭圆曲线的离散算法编制的，这也需要很多...

数论密码延伸阅读(密码学)
答：密码体制的设计和分析往往紧密依赖于数学，尤其是代数、几何和数论这些分支。数学在密码学中的应用是多方面的，从简单的替换密码到复杂的公钥加密系统，如RSA，都离不开数学的支撑。数论，作为基础的数学分支，提供了许多基础的加密原理，如大数分解和素数理论，这些都是保证密码安全性的关键元素。总的来说...

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

数论与密码内容简介
答：《数论与密码》是一本适用于信息安全领域专家、数论及相关专业工作者，以及高校教师和高年级学生的实用参考书籍。这本书致力于探索与传统原则不同的视角，挑战现有学科教育框架的局限。它不只停留在理论层面，而是试图打破常规，以数论和密码学为核心，结合实际应用，为教育研究和实践提供新的思考方向。该书...

初等数论及其在密码学中的应用与Maple实现内容简介
答：初等数论是一门古老的数学分支，它以直观且基础的方法探讨整数的性质。此书《初等数论及其在密码学中的应用与Maple实现》详细阐述了该领域的基础理论，以及它在古典密码和现代公钥密码系统中的应用实例。特别值得一提的是，书中介绍了如何借助强大的数学软件Maple来解决初等数论问题，这为理论学习和实际应用...

初等数论及其在密码学中的应用与Maple实现图书目录
答：本文主要探讨的是初等数论的基本理论及其在密码学领域的实际应用，以及如何通过Maple软件进行相关实践。首先，我们从第1章开始，深入理解整除性理论，这是数论研究的基础，它揭示了整数之间的重要关系。在第2章，我们将探讨常用的数论函数，如欧几里得函数、最大公约数和最小公倍数等，这些函数在数论计算中...

数论的应用有哪些?
答：1.密码学：数论在密码学中的应用非常广泛，例如RSA公钥加密算法就是基于大数分解问题的困难性。此外，椭圆曲线密码学、Diffie-Hellman密钥交换协议等也离不开数论的支持。2.计算机科学：在计算机科学中，数论被用于解决一系列问题，如素数检测、最大公约数和最小公倍数的计算、模运算等。这些问题在计算机...