英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料
计算数论和密码学
Preda Mihailescu and Michael Th. Rassias
摘要
这是一篇对公钥密码体制时代密码学的发展简明的总结和概述。论文适合于对此领域感兴趣的大众读者。我们也回顾了计算数论中的基础数学思想已经在现代密码学中发挥的重要作用。
关键词：
计算数论、密码学、有限域上的椭圆曲线、Diffie-Hellman算法
2000年数学分类号：
11Y11, 11G05, 11Y16, 11Y40,68Q17, 68Q25
前言
密码学是一门在信息传递过程中为了避免非授权方和非接受信息方得到信息而对传递信息进行相应隐藏的学科。
处理这类问题的逻辑艺术从古代便为人所知了，它的发展基于通信双方互相交流的过程，例如贵族和将军、秘密的恋情双方之间的交流。他们通过书信的形式传递给对方一些信息，这些信息只有在知道其他的一些信息——密钥以及加密和解密的过程——算法的基础上才可以理解，这些算法通常来源于传统的常用的基础思想。
古典密码学
将信息文字中的字母转化为一组数字编码是古典密码学中的常用思想，例如将拉丁字母a、b、hellip;hellip;、z按升序对应于阿拉伯数字0,1，hellip;hellip;、25。其中，通过确定一个常数来循环的排列字母的方法据讲曾被凯撒大帝在加菲尔战争中使用过，因此，这类密码也被称为凯撒密码。
例如，时，单词ATHENS就被加密成了DWKHQV。解密过程中，我们只需要将密文中每个字母对应的数值减去3便可得到真实信息中相应字母对应的数值。
前面所言的密钥，只是一个特定的常数，如果密钥是使用一组特定的数列或者其他有着明确定义的组合（16世纪法国外交官Blaise de Vigenegrave;re发明了很多可以使用的密钥形式），将会提高密文的安全性，可以克服凯撒密码在应对频繁攻击之下的明显弱点：提供足够的密文的情况下，而且知道一些字母（e，a，m）的出现频率与另一些字母（z，h，q）相比较高基础上，可以比较容易的确定密钥从而破解全部的密文。
由于上述的加密思想可以和常见的文本修改相结合，所以简单的手工加密技术也提供了足够的多样性以满足加密需求，直至20世纪的到来。
与新型加密算法的发展一样，破解密钥和特定的解密算法的分析方法也发展成了一门科学——密码分析，例如，凯撒密码所涉及的频率分析法。今天，密码分析学和密码编码学被认为是密码学的两个互补的分支。虽然私人密码和密钥的创建在一定程度上可以被认为是一种有趣的，甚至令人愉快的事情，但这需要一些严格的限制，以防止密码分析仪的对策，而经典加密受到一个更大的限制：行内需要对加密算法和密钥有一致的预期。这也引起了以下几点：一是算法需要足够强大使得可以满足更长的时间内使用相同的算法来交换密钥，二是，需要训练有素且足够忠实的信使来传递密钥。
为了说明经典密码学中应用的方法和其面临的挑战，我们让读者尝试解密下面的密文：
T G GM C I T G W KKNK V C T ZCOKN UKE CF GOZC CF C W K
计算机的出现
二十世界以来，军事对抗的影响更具毁灭性，同时，在机器的协助下数据处理的力量也是空前强大。然而，直到第二次世界大战甚至更晚，安全通信的基本方案并没有什么变化：秘密通信者分享一些一致的算法，这些算法可以由一台机器执行，传递信息的双方使用共享的密钥。使用加密技术最成熟的一个案例是德国开发的加密机器Enigma II，其基础是一个更简单的早期版本的Enigma I，它是战前的商业产品。他们并不知道经济和军事应用这种的结合导致了一个波兰南部的数学家团队掌握了破解Enigma I的方法。当其被英国当局聘用时，破解增强版本是一个完全可以实现的目标，这与德国的期望相反，而Enigma的破解对战争的结果产生了重要的影。
个人计算机和社交网络的出现
计算机的出现一方面大大提高了计算能力，然后在20世纪70年代，美军建立了ARPA-net展现了计算机应用的另一方面，即网络通信。ARPA-net是互联网的前身。鉴于这一发展，密码学开始被引导向去简化自己的对象和任务的定义。此时，一些有用的原则已经被建立起来了并仍在运用。首先，专有的密码体制几乎没有了安全性，密码学者倾向于选择简单公开并且易于理解的加密解密算法。
简而言之，现代的安全态度因公开已知的密码算法和密钥体制而恢复。因此，密钥的保护成为了安全问题的中心，应该重点关注的是：系统和密钥一样安全。
此外，新的加密方法承诺，由于加密内容的集体审查，当在进程中出现弱点和攻击时，在时间上自然选择最有效和最可靠的算法。受到长期社会公众监督和审查的算法要比基于复杂的加密技巧的算法更可靠。
我们前面提到在密码学诞生的早期，密钥是通过信使运送的，这也使得信使们因为这个目的而活在危险之中。而在进入了电报传输密钥的时代后，最关键的问题是建立密钥传输的安全通道。20世纪七十年代，第一个联网的计算机诞生。美国军方建立的ARPA-net体现了计算机联网的雏形，1972-1974年间，ARPA网连接了东西方的一些大学，用于研究和实验。从此，远程计算机通信的概念对于网络用户来说变得具体。
在这种情况下，针对于旧系统的密钥体制不再满足新的技术发展的需求，为了用简单高效和可靠的方式解决问题，新的思想开始被提出。
这种新的思想被称为公钥密码，公钥密码诞生于Stanford大学，是由研究公钥基础设施的W. Diffie和R. Hellman以及研究密钥分发的R. Merkle提出。下面是Diffie和Hellman在[8]中提出的问题，其中包含了二人与Merkle的合作内容：反过来，这样的应用程序（快速计算机）带来了适用于新型密码体制的需求：将安全密钥的分发模式的必要性降到最低并提供可等价的书面签名
公钥密码学
公钥密码的思想非常简单和漂亮。在30年后，当它被公认和证实的时候，它的自然属性得到了显著的反映。J.Ellison 是一位为军情五处GCHQ工作的工程师和密码学家，他早于Diffie和Hellman七年提出了完全相同的概念和方案。但他的研究在2000年以后才被解密，这是一个学术争论：一个在学术界外进行秘密研究的工作人员应不应该被授予有关科学贡献的赞誉。
传统上，是使用私有密码体制建立起受保护的通信。在一个广泛的通信网络中，许多人可以超越距离的交流沟通，在通信之前建立公共密钥的机会很低，所以需要一个算法使得通信双方A和B——Alice 和Bob（密码学家通常这样称呼他们），在配置的过程中共享密钥，无需任何前期通信，只有一些公共的数据库和算法才能作为实现该目的的前提。
上述三位作者提到的公钥密码学概念可以简述如下：如果是想要进行安全网络通信的一方，他需要先生成一组数据，这些数据被捆绑成他自己的密钥。捆绑在公钥中的一系列数据将被公开给所有他可能希望进行通信的另一方，这些数据是数据库的一部分或者它可以通过任何不安全的信道传输。这两个密钥应该具有下列性质：
性质1：密钥都可以根据一些尚未定义的算法加密文本内容。
性质2：由加密的内容可以由解密，反之亦然。此外，密钥应该是非常随机的：通信双方产生两个相同密钥的机会应接近于0.
性质3：从导出从计算上讲是不可行的。
为了满足第三个条件，通常通过使用某种陷门函数从密文派生出公钥。我们可以这样理解陷门函数：的值非常容易计算，但是求其逆在实际中是不可行的（即使理论上可行，但当数据足够大时无法实际操作）。
一个典型的例子如下：定义映射，它将两个素数映射到二者的乘积。
我们不能证明不存在一些快速的算法，例如多项式算法：对于整数n的因子分解的时间复杂度为的多项式。整数的因子分解问题是算法数论中研究最多的问题之一，经过数十年的研究，最有效的分解算法数域筛选（NFS）也需要个二进制操作。
在满足上述性质1-3的基础上，如果Alice和Bob想要通信，Alice可以从公钥库中检索到她发送给Bob的由加密的信息。但是，只有Bob才可以解密消息，所以通信是安全的。基于这个想法，可以得出一个更有价值的认知：能够认证一些消息的所有权并以独特且不可否认的方式签署消息通常是有用的。在这种情况下，保密性不如所有权。
该解决方案包括将短密码Hash值 H与消息相关联 并用加密。然后，任何接受者将能够自己重新生成Hash值，并用解密密文，然后比较两个结果。如果两者匹配，Bob可以证明是Alice发送了这个消息。
在未来20年内，公钥密码学将广泛应用到传统上认为使用私有密钥更具安全性的银行和外交方。
古典公钥体制
抽象的公钥加密定义出现后的两年中，两种主要算法在此思想基础上被提出并且今天仍在使。
第一个是使用有限域中的乘法群里的离散对数问题作为陷门。如果是一个很大的素数，生成乘法群模且，则可
以得到对于任意的有：
然而，从逆得出属于有限域中的离散对数问题，其在计算上非常困难，因此完全可以作为陷门函数。对于分解问题，没有证据表明没有更快的算法可以被发现，但到目前为止发现的最好的算法与上面所提到的整数因子的筛选具有相近的渐近复杂性。
Diffie和Hellman提出了一种在不安全通道上交换共享密钥的算法，被广泛地称为Diffie-Hellman密钥交换算法。
它的内容如下：如果之前提到是作为共享数据，并且Alice和Bob分别选择随机的一次性密钥是中的元素。然后Alice发送给Bob的消息为并接收到Bob的消息。读者可以通过使用自己的私钥和收到的数据来验证，Alice和Bob都可以检索到，然而一个窃听者，密码学中常常称其为Eve，仅仅可以窃听到和，而不是。
最近，已经提出了Diffie-Hellman密钥交换的变型，其可以被证明等同于DH问题：即当且仅当DH问题被破坏时它们可以被破坏。密钥交换算法不提供生成签名的可能性，但 L. Massey和J.K.Omura在1983年提出了一种基于离散对陷门函数的变体，该变体允许公钥加密从而进行数字签名。
一般来说，公钥算法要比私密密钥加密慢得多，因此，最有可能使用它们来建立共享密钥，之后可以使用建立的密钥通过公认的密钥算法来加密通信内容。最初的Diffie-Hellman算法就可以满足相应目的。这种两步加密算法是1992-2002年间开发的SSL/TLS协议的核心思想，目前在互联网上的所有机密https通信中使用，例如：当您预订电子机票时或者从亚马逊买一本书时。
一年后，公钥加密算法RSA诞生，RSA是在1977年由R. Rivest，A. Shamir和L. Adleman在麻省理工学院发明。这种算法是将整数分解问题作为陷门。
密钥由，其中是满足一些附加的随机条件的两个较大素数，为满足以下条件的随机数：
如果
则在是固定数值的情况下，将由密钥的持有者使用相同的定义一致性来确定。
基于这些假设，如果是一条短信息，它将被定义为中的一个数值，它可以公开的被公钥进行加密，但只有的所有者Alice可以对其解密，因此
相反，如果Alice用加密，那么任何人都可以恢复，一旦这样做，Alice就会产生加密证明：事实上，只有秘密密钥的所有者可以产生这种可以作为爱丽丝私有签名的加密。
同在1978年，麦克尔斯从编码理论得到启发提出了一个有些不同的密码体制。 在这种体制中，陷门函数是从一般线性代码绘制的，其中线性代码的参数特别适用于公钥加密的目的 所得到的算法相比较于上述基于数论的算法例如基于椭圆曲线的算法更具优势，因为它更快。 然而该体制下的密钥可能大到1MB，比RSA所要求的128B的可靠级别的安全性要。
Dickman 定理和陷门函数
在上世纪三十年代，J.Dickson 考虑如何估计任意整数n的最大素因子。通过对重新分配素数使用启发式估计对重新分配素数，他发现如果是最大的整除的素因子，则。
更一般的是，如果整数且其不存在大于y的素因子，则n被定义为y光滑。如下的集合包含了小于等于的所有光滑数：
基于这些概念，Dickman证明了对于所有,存在一个实数使得：
(1)
函数是用一个微分方程描述的，其中当时，是固定的。
半个世纪之后，Canfield, Erdos 和 Pomerance证明了如下的定：
定理1：对于所有的实数列，当在的约束下趋于无穷时，有
由此可以得出在区间取出任意一个整数是光滑的概率其中
被称作子指数，因为它的增长速度比任意的要快，但确定比要慢。用于解决离散对数问题体或因子分解整问题的所有最先进的子指数算法都以某种方式利用了这个结论或其推论。
二次筛方法是一种用于分解整数的经典快速算法，下面我们举例介绍一下这种方法。它起源于Fermat的简单观察：如果m是一个合数，则同余式
至少有四个解，且存在满足
且是的一个非平凡因子。由定理1我们可以找到一对数，如下：对于区间的，求解如下的同余：
并且仅保留的值，其中是平滑数。在收集了很多这样的关系后，希望存在是平方数：即存在子集使得：
令
我们可得：
此外，如果的概率,则是的非平凡因子。该方法依赖于对因子分配的经验假设：即，通过这些余数的分布可以应用公式1
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[25238]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
