论文部分内容阅读
【分类号】：O156；TN918.1
1. 引言
语言是人类表达思想和进行交流的基本手段。人们在讲话、写文章或者通信时通常总希望能把自己的意思表达得清清楚楚，使得任何听到讲话或看到文章或信件的人都能正确地领会自己的意思而不致产生误解。但在有些情况下，人们只希望某些特定的对象能理解自己的语言而不希望局外人从语言中获得任何信息。随着计算机和电子通讯技术，包括因特网的迅猛发展，金融电子化的步伐大大加快，現代密码学的应用范围已经远远超过了军事与外交领域，它也从狭义的通信保密理论发展为包含了诸如防篡改技术、防假冒技术、安全协议的制订、身份验证、电子商业、电子银行和电子签名、电子货币的研究、实施等多方面内容的枝繁叶茂的学科，因而也在金融、财贸和商业等领域有重要的应用。现代密码学当然是与计算机科学紧密联系的，而它所使用的数学工具已涉及数论、布尔函数、Walsh函数、群论、有限域理论、逻辑学乃至代数几何学中的椭圆曲线理论。如果不考虑技术实现方面的问题，就密码学现已达到的发展水平来说，应把它看成应用数学的一个分支。不过它使用最多的还是数论。
2. 密码学简述
密码学，也称密码术，是由保密通讯的需要而发展起来的一门学科。也就是一门研究信息的加密与解密技术，以及密码破译技术的学问。密码学有两个显著特点：一是历史悠久，二是数学性强。
在保密通讯中，信息从发送到接收要经过如下过程：发送者先将要发出的原始信息——称为明文，进行某种方式的变化或变换—称为加密，将加密后的信息—称为密文，发送出去；接收者收到密文后，将密文还原为明文—称为脱密，脱密后得到明文，即原始信息。密文在传输过程中可能被窃取者截取，窃取者无法从截取的密文中直接读出原始信息，他在不知道加密算法的前提下，想方设法从密文中恢复出明文来—称为破译或解密。
密码学是属于比较专业化和数学化的领域，它可分为：第一类是提供通讯的保密方法，即研究如何将发送的原始信息加密，才能使窃取者不易破密，也即密码技术；第二类是对窃取的别人的密文信息进行破译，以得到有用的原始信息，即密码分析。第一个方面称为密码编码学，或简称为编码学；第二个方面称为密码分析学或密码破译。这两个方面合起来构成密码学。编码学和密码分析学有时称为孪生科学，或称为互逆科学。在功能上，两者相互反映，第一类的目的是为了发展密码技术来提高加密的安全性，第二类是为了破密，两者既是一对矛盾，又相辅相成共同发展。
一个密码体制是指加密算法和实现其算法的一套设备。从密码发展的历史来看，主要有五种典型的密码体制：
2.1 文学替换密码体制 这是直到文艺复兴时期还使用的一种密码体制。它的加密法则是使用图形、符号或数字代替文字，通过手工操作进行加密。
2.2 机械密码体制 直到第二次世界大战时期还使用的一种密码体制，它的加密法则基本上是一种复杂的多表代替，通过机械操作进行加密。
2.3 序列密码体制 这是上世纪五十年代后发展起来的，至今仍在使用的一种密码体制。信息传输方式通常采用二元序列的形式。加密的实现是通过电子设备。
2.4 分组密码体制 一种私钥密码体制，将明文消息分组，逐组地进行加密。
2.5 公开密钥密码体制 也称公开密钥密码系统，它是七十年代中期出现的一种新的密码体制，具有部分密钥可以公开的特点，也是现代密码学的最重要的发明和进展。公开密钥体制是一种很有发展前途的密码体制，它在数据加密、用户和信息确证、密钥管理以及数字签名等方面有十分显著的特色。
3. 密码学算法
在传统密码系统中，使用的是对称密钥密码体制，也称传统密码体制，加密运算与解密运算使用相同的密钥。通常使用的加密算法比较简便高效，密钥简短，破译极其困难。但是，在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题。1976年美国斯坦福大学教授赫尔曼和他的研究助理迪菲（简称为D-H）为解决密钥管理问题，在他们的奠基性的工作“密码学的新方向”一文中，提出一种密钥交换协议，允许在不安全的媒体上通讯双方交换信息，安全地达成一致的密钥。在此新思想的基础上，很快出现了“不对称密钥密码体制”，即“公开密钥密码体制”，其中加密密钥不同于解密密钥，加密密钥公之于众，解密密钥只有解密人自己知道，分别称为“公开密钥”和“秘密密钥”，公开密钥是一对整数（N，P），秘密密钥也是一对整数（N，S），整数S是保密的，而整数N和P则是公开的。S可以看成是秘密密钥，P是公开密钥，而N是用户地址。并且具有从P难于推出S的性质。公钥密码学的提出使得密码学发生了一场变革。因此，公钥密码学也称现代密码学。
加密技术有两种完全不同的方法：机密密钥方法和公开密钥方法。
3.1 机密密钥算法—DES加密算法
DES是美国NBS于1977年批准通过作为全国数据加密标准，也是国际商业与银行业务中通用的数据加密标准。DES是一种分组密码，它是分组加密方法中的两种基本类型――换位和置换结合起来应用时构成的乘积密码。DES加密算法是一种复杂的非线性运算，是IBM公司在Lucifer密码设计的基础上研制成功的分组乘积密码系统，它集中了传统密码学中最主要的成果。因DES算法太过复杂，这里就不再介绍，但它最终已被攻破。
3.2 公钥密钥算法—RSA算法
RSA算法是1977年，由美国麻省理工学院的Rivest、Shamir和Adleman提出的第一个比较完善的公钥密码算法。RSA既可用于加密也可用于数字签名。在已有的公钥密码系统中，RSA算法是最容易理解和实现的。同时，它也是使用最广泛的。在Hellman和Diffie提出公钥密码学的概念时，指出设计一个使拥有解密密钥的人可以容易地解密消息，而破译者需要解此NP-完全问题。设计这样的密码，一个陷门函数是需要的，即公钥密码系统应基于陷门单向函数，从而，RSA公开密钥算法就是基于上述原理，它的理论基础是数论的Euler定理，它的安全性依赖于大整数因子分解的困难性。其公开密钥和秘密密钥是一对大素数（100到200位十进制整数）的函数。 由此，我们可以看出数论在密码学上有着至关重要的应用。
4. 在密码学上的应用
设发送者A想要传送一讯息p，但发送者将p伪装，使得即使被截取也无法解读此讯息，也就是经过编码器，传送出密码c，接收者B收到密碼c后，再设法转换为原来的讯息p。事先A与B要约定好，如何编码。由于窃取者可能知道编码的方式，A与B就须约定好一只秘密的钥匙。这只秘密的钥匙就是用来防止窃取者即使截取到密码c，也无法直接读出p。因此A就象有一袋子的函数，依据他与B约好的钥匙 ，A选一函数。若以 表此函数，，则c 。由于B知道 ，因此B知道A采用的函数是 ，故经由 之反函数，便可由c得到p。下举一个简单的例子。
例5.1 首先分别以数字0至25代表英文字母A至Z。编码的方式是加一整数 后以26为模，钥匙 即为加数，因此1至25的整数皆可以当作钥匙（ 为o表没有达到伪装的目的）。例如，若 ，而讯息为CAT，则密码为JHA。收到JHA后，将每个字母减7，便得到讯息CAT。
一旦知道编码的函数，只要决定其反函数便可解码。任何密码几乎没有破不了的，因它们就是一定的编码方式。但如果能发展出一套编码法，使得破解要花很长的时间，且此时间远超过要保密的讯息之有效期限，则便可充分达到保密的效果了。
5. 结束语
数论是数学中最古老、最纯粹的一个重要数学分支。素有“数学王子”之称的19世纪德国数学大师高斯曾说过，数学是科学的皇后，而数论是数学的皇冠。数论的一个主要任务，就是研究整数的性质，由于整数的性质复杂深刻，难以琢磨，因此数论长期以来一直被认为是一门优美漂亮、纯之又纯的数学学科。事实上，在计算机科学与电子技术深入发展的今天，数论已经不仅仅是一门纯数学学科，同时也是一门应用性极强的数学学科，比如，数论已经在诸如物理、化学、声学、电子、通讯、尤其如前所述的在密码学中有着广泛而深入的应用。但是由于本人知识水平有限，密码学中很多问题，特别是密码编码学中的一些问题，最后可归结为十分纯粹的数学问题，比如，关于有限域上的指数方程求解问题，另有数论中的高斯和的应用等理解掌握不深，还有关于某些公钥密码体制在数字签名、数字指纹的应用，及背包原理和中国剩余定理，也即孙子定理，在秘密分享方案中的应用和复合加密的公开钥密码系统没有做深入的学习、研究，以致本文就只是简单的介绍了数论中最基础的知识、方法在密码学中的应用。事实上，密码学与数论的关系，并不仅是前者依靠后者。密码学本身的发展，反过来又向数论提出许多有重要价值的课题，促进数论的发展。
参考文献
[1] 柯召，孙琦，数论讲义[M]，北京：高等教育出版社，2003：27-175.
[2] 黄文璋. 数学欣赏[M].北京：中国统计出版社， 2001：22-33.
[3] Rosen K.H. Elementary Number Theory and Its Applications[M]. 北京：机械工业出版社（影印版），2005：11-27.
[4] Song Y. Yan. Number Theory for computing[M].New York：Springer-Verlag， 2002：67-80.
[5] 王国俊.数论在密码学中的应用[J].工程数学学报，2002： 19（1）：07-14.
1. 引言
语言是人类表达思想和进行交流的基本手段。人们在讲话、写文章或者通信时通常总希望能把自己的意思表达得清清楚楚，使得任何听到讲话或看到文章或信件的人都能正确地领会自己的意思而不致产生误解。但在有些情况下，人们只希望某些特定的对象能理解自己的语言而不希望局外人从语言中获得任何信息。随着计算机和电子通讯技术，包括因特网的迅猛发展，金融电子化的步伐大大加快，現代密码学的应用范围已经远远超过了军事与外交领域，它也从狭义的通信保密理论发展为包含了诸如防篡改技术、防假冒技术、安全协议的制订、身份验证、电子商业、电子银行和电子签名、电子货币的研究、实施等多方面内容的枝繁叶茂的学科，因而也在金融、财贸和商业等领域有重要的应用。现代密码学当然是与计算机科学紧密联系的，而它所使用的数学工具已涉及数论、布尔函数、Walsh函数、群论、有限域理论、逻辑学乃至代数几何学中的椭圆曲线理论。如果不考虑技术实现方面的问题，就密码学现已达到的发展水平来说，应把它看成应用数学的一个分支。不过它使用最多的还是数论。
2. 密码学简述
密码学，也称密码术，是由保密通讯的需要而发展起来的一门学科。也就是一门研究信息的加密与解密技术，以及密码破译技术的学问。密码学有两个显著特点：一是历史悠久，二是数学性强。
在保密通讯中，信息从发送到接收要经过如下过程：发送者先将要发出的原始信息——称为明文，进行某种方式的变化或变换—称为加密，将加密后的信息—称为密文，发送出去；接收者收到密文后，将密文还原为明文—称为脱密，脱密后得到明文，即原始信息。密文在传输过程中可能被窃取者截取，窃取者无法从截取的密文中直接读出原始信息，他在不知道加密算法的前提下，想方设法从密文中恢复出明文来—称为破译或解密。
密码学是属于比较专业化和数学化的领域，它可分为：第一类是提供通讯的保密方法，即研究如何将发送的原始信息加密，才能使窃取者不易破密，也即密码技术；第二类是对窃取的别人的密文信息进行破译，以得到有用的原始信息，即密码分析。第一个方面称为密码编码学，或简称为编码学；第二个方面称为密码分析学或密码破译。这两个方面合起来构成密码学。编码学和密码分析学有时称为孪生科学，或称为互逆科学。在功能上，两者相互反映，第一类的目的是为了发展密码技术来提高加密的安全性，第二类是为了破密，两者既是一对矛盾，又相辅相成共同发展。
一个密码体制是指加密算法和实现其算法的一套设备。从密码发展的历史来看，主要有五种典型的密码体制：
2.1 文学替换密码体制 这是直到文艺复兴时期还使用的一种密码体制。它的加密法则是使用图形、符号或数字代替文字，通过手工操作进行加密。
2.2 机械密码体制 直到第二次世界大战时期还使用的一种密码体制，它的加密法则基本上是一种复杂的多表代替，通过机械操作进行加密。
2.3 序列密码体制 这是上世纪五十年代后发展起来的，至今仍在使用的一种密码体制。信息传输方式通常采用二元序列的形式。加密的实现是通过电子设备。
2.4 分组密码体制 一种私钥密码体制，将明文消息分组，逐组地进行加密。
2.5 公开密钥密码体制 也称公开密钥密码系统，它是七十年代中期出现的一种新的密码体制，具有部分密钥可以公开的特点，也是现代密码学的最重要的发明和进展。公开密钥体制是一种很有发展前途的密码体制，它在数据加密、用户和信息确证、密钥管理以及数字签名等方面有十分显著的特色。
3. 密码学算法
在传统密码系统中，使用的是对称密钥密码体制，也称传统密码体制，加密运算与解密运算使用相同的密钥。通常使用的加密算法比较简便高效，密钥简短，破译极其困难。但是，在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题。1976年美国斯坦福大学教授赫尔曼和他的研究助理迪菲（简称为D-H）为解决密钥管理问题，在他们的奠基性的工作“密码学的新方向”一文中，提出一种密钥交换协议，允许在不安全的媒体上通讯双方交换信息，安全地达成一致的密钥。在此新思想的基础上，很快出现了“不对称密钥密码体制”，即“公开密钥密码体制”，其中加密密钥不同于解密密钥，加密密钥公之于众，解密密钥只有解密人自己知道，分别称为“公开密钥”和“秘密密钥”，公开密钥是一对整数（N，P），秘密密钥也是一对整数（N，S），整数S是保密的，而整数N和P则是公开的。S可以看成是秘密密钥，P是公开密钥，而N是用户地址。并且具有从P难于推出S的性质。公钥密码学的提出使得密码学发生了一场变革。因此，公钥密码学也称现代密码学。
加密技术有两种完全不同的方法：机密密钥方法和公开密钥方法。
3.1 机密密钥算法—DES加密算法
DES是美国NBS于1977年批准通过作为全国数据加密标准，也是国际商业与银行业务中通用的数据加密标准。DES是一种分组密码，它是分组加密方法中的两种基本类型――换位和置换结合起来应用时构成的乘积密码。DES加密算法是一种复杂的非线性运算，是IBM公司在Lucifer密码设计的基础上研制成功的分组乘积密码系统，它集中了传统密码学中最主要的成果。因DES算法太过复杂，这里就不再介绍，但它最终已被攻破。
3.2 公钥密钥算法—RSA算法
RSA算法是1977年，由美国麻省理工学院的Rivest、Shamir和Adleman提出的第一个比较完善的公钥密码算法。RSA既可用于加密也可用于数字签名。在已有的公钥密码系统中，RSA算法是最容易理解和实现的。同时，它也是使用最广泛的。在Hellman和Diffie提出公钥密码学的概念时，指出设计一个使拥有解密密钥的人可以容易地解密消息，而破译者需要解此NP-完全问题。设计这样的密码，一个陷门函数是需要的，即公钥密码系统应基于陷门单向函数，从而，RSA公开密钥算法就是基于上述原理，它的理论基础是数论的Euler定理，它的安全性依赖于大整数因子分解的困难性。其公开密钥和秘密密钥是一对大素数（100到200位十进制整数）的函数。 由此，我们可以看出数论在密码学上有着至关重要的应用。
4. 在密码学上的应用
设发送者A想要传送一讯息p，但发送者将p伪装，使得即使被截取也无法解读此讯息，也就是经过编码器，传送出密码c，接收者B收到密碼c后，再设法转换为原来的讯息p。事先A与B要约定好，如何编码。由于窃取者可能知道编码的方式，A与B就须约定好一只秘密的钥匙。这只秘密的钥匙就是用来防止窃取者即使截取到密码c，也无法直接读出p。因此A就象有一袋子的函数，依据他与B约好的钥匙 ，A选一函数。若以 表此函数，，则c 。由于B知道 ，因此B知道A采用的函数是 ，故经由 之反函数，便可由c得到p。下举一个简单的例子。
例5.1 首先分别以数字0至25代表英文字母A至Z。编码的方式是加一整数 后以26为模，钥匙 即为加数，因此1至25的整数皆可以当作钥匙（ 为o表没有达到伪装的目的）。例如，若 ，而讯息为CAT，则密码为JHA。收到JHA后，将每个字母减7，便得到讯息CAT。
一旦知道编码的函数，只要决定其反函数便可解码。任何密码几乎没有破不了的，因它们就是一定的编码方式。但如果能发展出一套编码法，使得破解要花很长的时间，且此时间远超过要保密的讯息之有效期限，则便可充分达到保密的效果了。
5. 结束语
数论是数学中最古老、最纯粹的一个重要数学分支。素有“数学王子”之称的19世纪德国数学大师高斯曾说过，数学是科学的皇后，而数论是数学的皇冠。数论的一个主要任务，就是研究整数的性质，由于整数的性质复杂深刻，难以琢磨，因此数论长期以来一直被认为是一门优美漂亮、纯之又纯的数学学科。事实上，在计算机科学与电子技术深入发展的今天，数论已经不仅仅是一门纯数学学科，同时也是一门应用性极强的数学学科，比如，数论已经在诸如物理、化学、声学、电子、通讯、尤其如前所述的在密码学中有着广泛而深入的应用。但是由于本人知识水平有限，密码学中很多问题，特别是密码编码学中的一些问题，最后可归结为十分纯粹的数学问题，比如，关于有限域上的指数方程求解问题，另有数论中的高斯和的应用等理解掌握不深，还有关于某些公钥密码体制在数字签名、数字指纹的应用，及背包原理和中国剩余定理，也即孙子定理，在秘密分享方案中的应用和复合加密的公开钥密码系统没有做深入的学习、研究，以致本文就只是简单的介绍了数论中最基础的知识、方法在密码学中的应用。事实上，密码学与数论的关系，并不仅是前者依靠后者。密码学本身的发展，反过来又向数论提出许多有重要价值的课题，促进数论的发展。
参考文献
[1] 柯召，孙琦，数论讲义[M]，北京：高等教育出版社，2003：27-175.
[2] 黄文璋. 数学欣赏[M].北京：中国统计出版社， 2001：22-33.
[3] Rosen K.H. Elementary Number Theory and Its Applications[M]. 北京：机械工业出版社（影印版），2005：11-27.
[4] Song Y. Yan. Number Theory for computing[M].New York：Springer-Verlag， 2002：67-80.
[5] 王国俊.数论在密码学中的应用[J].工程数学学报，2002： 19（1）：07-14.