浅谈数论在密码学上的应用

硕士研究生《应用密码学》课程论文浅谈数论在密码学上的应用指导教师：***专业：计算机应用技术学号：*************日期：2011年6月30日浅谈数论在密码学上的应用摘要：众所周知．数论是数学中最古老、最纯粹、最优美的一个学科．不过鲜为人知的还是，数论同时也是一门应用性极强的应用数学学科．著名国际数学大师陈省身教授早在1992年精辟地指出：“数学中我愿意把数论看作应用数学。

”我想数学中有两个很重要的数学部门，一个是数论，另一个是理论物理。

在本文中我将先扼要介绍下数论中的一些基本概念、几个主要难题，紧接着我们要介绍数论在现代密码学与计算机科学中的应用。

关键词：数论；计算数论；密码学；1 引言随着现代计算机网络通信的广泛使用，传统密码受到很大挑战，它们已经不能完全适应网络环境下使用密码的需求。

于是在上世纪七十年代，提出了公钥密码的概念，并且利用数论方法设计了第一个公钥密码体制（RSA公钥密码），经过二十多年的研究，RSA已得到了广泛的应用。

在RSA密码体制中，使用了一个大整数（目前通常取这个数有1024比特长），它是两个素数的乘积，这个大整数是公开的，而它的两个素因子是保密的。

如果有人能将这个大整数分解因子而得到它的两个素因子，就能破译这个密码体制，所以RSA的安全性是建立在大整数因子分解问题的基础之上的。

这是一个经典的数论问题，RSA的提出大大推动了大整数因子分解算法的研究。

在上世纪八十年代，人们又提出了椭圆曲线公钥密码，它应用了更深刻的数论知识，它的安全性也得到了密码界的公认，现在也正逐步推向应用。

公钥密码的出现，使数学在密码研究中发挥了更加核心的作用。

2 数论概述数论，顾名思义，就是关于数的理论，数学，顾名思义，就是关于数的学问．高斯曾说过一句名言：“数学是科学的女王，而数论是数学的女王”。

基础数论作为一门古老的数学学科，在很常时间内都属于一种纯数学，随着现代科技的发展，数论在整个科学中的应用非常重要[1]。

数论中许多基本内容，如同余理论、中国剩余定理（CRT）、高次剩余理论等，在现代密码体制、密钥分配与管理、数字签名、身份认证等方面有重要的应用。

1 数论概述1.1 整除理论1)整除：设 a 和 b 是两个整数，且 b≠0，如果存在一个整数 q，使等式a=bq 成立，那么我们称 a 能被 b 整除或 b 整除 a，记作 b—a，其性质有：(1) 若 b | a，a ≠0，则 | b | ≤ | a | ；(2) 若 b | a，a | b，a ≠0，则 a=b 或 b=a；(3) 若 c | b，b | a, 则 c | a；（c≠0）(4) 若 b | a，则 cb | ca（c≠0）；(5) 若 c | a，c | b,则 c | ma+nb，m，n∈Z（c≠0）。

2) 整除的基本定理：对于任意整数 a，b(b≠0)存在唯一的一对整数 q，r，且使得 a=qb+r，（0≤r＜b）。

其中 q 和 r 分别称为 b 除 a 的商和余数。

3) 最大公约数和最小公倍数：a，b 的最小公倍数记为[a，b]，a，b 的最大公约数记为(a，b)，其性质有：(1) 设 m 为正整数，则(am，bm)=m(a，b) [am，bm]=m[a，b]；(2) 设 a，b 是两个正整数，则(a，b)[a，b]=ab；(3) 设 a，b，c 是三个正整数，则(ab，bd，ac)[a，b，c]=abc；(4) 设正整数 k 是整数 a，b 的公倍数，则(k/a，k/b)=k/[a，b]；(5) 设正整数 c 是 a，b 的公约数，则(a/c，b/c)=(a，b)/c；(6) 若(a，b)=1， (ab，c)=(a，c)(b，c)；(7) 若 a1, a2, …an,是 n 个不全为零的整数，则(a1, a2, …an)=( (a1, a2, …ak), (ak+1, ak+2, …an))。

4) 两个定理[5]:(1) 欧拉函数：设整数 n≥2，n=p1a1,p2a2,…,pmam 是 n 的质因数分解式，以准（n）表示小于 n 且与 n 互质的自然数的个数，则{xj≡1(mod mj){xj≡0(mod mi) i 不等于 j令 x 为从 1 到 najxj 的和，则 x 适合下列联立同余式x≡aj（mod mj）, j=1,2,3,.....,n另：求自然数 a 的个位数字，就是求 a 与哪一个一位数对于模 10 同余3 数论在密码学中的应用3.1 密码学概述密码技术是实现网络信息安全的核心技术，是保护数据最重要的工具之一。

它通过加密变换，将可读文件变成不可理解的乱码，其主要的目的是防止信息系统内的机密信息被非法用户破译，起到保护信息和数据的作用。

密码技术还可以使重要信息和数据得以不必通过专用的线路进行传输和储存，从而大大降低信息传输的成本和信息存储的费用。

密码学的发展大致经历了三个历史阶段：古代加密方法（手工阶段）、古典密码（机械阶段）和近代计算机密码（计算机阶段）。

近代密码学与计算机技术、电子通信技术紧密相关。

密码学真正成为一门新的学科是在 20 世纪 70 年代，在现代密码学的发展中有两个重要的里程碑：1949 年 Shanon 发表的“The Communication Theory of Secrecy System”和 1976 年 Diffie 和 Hellman 发表的“New Di-rection of The Cryptography”。

Shanon 的理论奠定了密码学的理论基础，并使之成为一门独立的科学；“密码学的新方向”一文提出了公钥密码学的基本思想，开创了公钥密码学的新纪元。

由于公钥密码学弥补了私钥密码的缺点，所以提出以后，立刻引起了密码学专家们的广泛关注。

从 1976 年以来，密码学家们提出了许多种公钥密码体制的实现方案，所有这些方案都是基于某个数学难题的。

目前几种通用的密码体制一般基于以下三类数学难题：1) 基于大整数因子分解问题（Integer Factorization Problem）的公钥密码体制。

这一类公钥密码体系基于大整数因子分解的困难性。

其中最著名的当属 RSA 公钥密码体制，该算法是美国麻省理工学院 Rivest、Shamir、Adlman 三位学者于 1978 年首次发表的，简称 RSA，是目前被广泛接收并实现的通用公钥密码体系之一。

2) 基于有限域上离散对数问题（Discrete Logarithm Problem）的公钥密码体制。

DLP 公钥密码体系基于有限乘法群上的离散对数问题的求解困难性，其中最著名的有 ELGamal 公钥密码体系和 DSA 数字签名算法。

3) 基于椭圆曲线离散对数问题（Elliptic Curve Discrete Logarithm Problem）公钥密码体系。

其数学基础是椭圆曲线有限加法群上的椭圆曲线离散对数问题的求解困难性。

主要包括椭圆曲线型的 Diffie-Hellman 问题、椭圆曲线签名方案等。

1985 年，华盛顿大学的 Neal Koblitz 和 IBM 公司的 Victor Miller 各自独立地提出椭圆曲线公钥密码（Elliptic Curves Cryptogra-phy ,ECC），这是继 Goldwasser 和 Killian 的素性检验，Lenstra 的椭圆曲线大数分解后，椭圆曲线理论在密码学中的又一次全新的应用，它的思想仍然在各种涉及有限域乘法群的公钥密码体制中，用有限域上的椭圆曲线构成的群来类比有限域的乘法群，从而获得类似的公钥密码体制。

这类体制的安全性是基于椭圆曲线上离散对数问题求解的困难性，目前还没有找到解决此问题的亚指数时间算法，因而它具有一些其他公钥密码体制无法比拟的优点，如在相同的安全强度下，椭圆曲线密码系统具有参数和密钥尺寸较短、计算量小、处理速度快、带宽要求低等优势。

另外利用椭圆曲线建立密码体制还有两大潜在的优点：一是有取之不尽的椭圆曲线可用于构造有限点群；二是不存在计算椭圆曲线有限点群的离散对数亚指数算法。

正是这些特点，几年来，一直引起数学家、密码学家和计算机科学家们的极大关注，因此椭圆曲线密码系统被认为是下一代最通用的公钥密码系统。

目前，RSA 密码体制是国际上公钥加密技术的通用标准，但是基于椭圆曲线的公钥加密算法以其优越的性能已经得到了世界上许多著名组织和国家的认可，并制定了相应的新标准，我们国家也已经将 ECC 的研究作为“十五”期间的重点研究课题。

欧美许多国家已经有相关产品问世，因此加速对椭圆曲线密码系统的研究，对于促进我国信息化工程建设的高速发展，增强我国的经济竞争实力，维护我国的主权独立和战略安全，具有十分重要的意义。

3.2 对称密码学对称密码体制是一种传统密码体制，也称为私钥密码体制。

在对称加密系统中，加密和解密采使用相同的密钥。

因为加解密密钥相同，需要通信双方必须选择和保存他们共同的密钥，各方必须信任对方不会将密钥泄密出去，这样就可以实现数据的机密性和完整性。

对于具有 n 个用户的网络，需要 n(n-1)/2 个密钥，在用户群不是很大的情况下，对称加密系统是有效的。

但是对于大型网络，当用户群很大，分布很广时，密钥的分配和保存就成了问题。

对机密信息进行加密和验证随报文一起发送报文摘要(或散列值)来实现。

比较典型的算法有DES(Data Encryption Standard 数据加密标准)算法及其变形 Triple DES(三重DES)、欧洲的 IDEA、日本的FEAL N、RC5 等。

DES 标准由美国国家标准局提出，主要应用于银行业的电子资金转帐(EFT)领域。

DES 的密钥长度为 56bit，TripleDES 使用两个独立的 56bit 密钥对交换的信息进行 3 次加密，从而使其有效长度达到 112bit。

RC2 和 RC4 方法是 RSA 数据安全公司的对称加密专利算法，它们采用可变密钥长度的算法。

通过规定不同的密钥长度，C2 和 RC4 能够提高或降低安全的程度。

对称密码算法的优点是计算开销小，加密速度快，是目前用于信息加密的主要算法。

它的局限性在于它存在着通信的贸易双方之间确保密钥安全交换的问题。

此外，某一贸易方有几个贸易关系，他就要维护几个专用密钥。

它也没法鉴别贸易发起方或贸易最终方，因为贸易的双方的密钥相同。

另外，由于对称加密系统仅能用于对数据进行加解密处理，提供数据的机密性，不能用于数字签名。

因而人们迫切需要寻找新的密码体制。

3.3 DES 加密算法本世纪五十年代以来，密码学研究领域出现了最具代表性的两大成就。

其中之一就是 1971 年美国学者 Tuchman 和 Meyer 根据信息论创始人 Shannon 提出的多重加密有效性理论创立的，后于 1977 年由美国国家标准局颁布的数据加密标准。