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

硕士研究生《应用密码学》课程论文

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

指导教师：***
专业：计算机应用技术
学号：*******
******
日期：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(modmj)
{xj≡0(modmi)i不等于j
令x为从1到najxj的和，则x适合下列联立同余式
x≡aj（modmj）,j=1,2,3,.....,n
另：求自然数a的个位数字，就是求a与哪一个一位数对于模10同余

3数论在密码学中的应用
3.1密码学概述
密码技术是实现网络信息安全的核心技术，是保护数据最重要的工具之一。
它通过加密变换，将可读文件变成不可理解的乱
码，其主要的目的是防止信息系统内的机密信息被非法用户破译，起到保护
信息和数据的作用。密码技术还可以使重要信息和数据得以不必通过专用的线
路进行传输和储存，从而大大降低信息传输的成本和信息存储的费用。
密码学的发展大致经历了三个历史阶段：古代加密方法（手工阶段）、