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

浅谈数论在密码学上的应用--第1页

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

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

指导教师：***

专业：计算机应用技术

学号：*******

******

日期：2011年6月30日

浅谈数论在密码学上的应用--第1页

浅谈数论在密码学上的应用--第2页

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

摘要：众所周知．数论是数学中最古老、最纯粹、最优美的一个学科．不

过鲜为人知的还是，数论同时也是一门应用性极强的应用数学学科．著名国际

数学大师陈省身教授早在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)存在唯一的一对整数