初等数论在密码学中的应用初探

论文总字数：9861字

摘 要

关键词：初等数论，密码学，应用

Abstract： The paper briefly expounds the basic knowledge of elementary number theory and cryptography, and introduces the simple applications of congruence theory, Chinese remainder theorem and quadratic residue in cryptography.

Keywords：elementary number theory, cryptography, applications

目 录

1 前言 4

2 初等数论在密码学中的应用 6

2.1 几种基于模运算的密码体制 7

2.2 中国剩余定理在文件集合加密中的应用 12

2.3 二次剩余在电子拋币中的应用 13

2.4 RSA公钥密码体制 14

结 论 17

参 考 文 献 18

致 谢 19

1 前言

数论又称高等算术，它是研究整数性质和方程整数解的一门学科，而初等数论主要是用初等方法研究整数性质的数论分支. 在很长的一个历史时期内，数论被认为是一门没有应用价值的“纯”理论学科，而事实并非如此. 随着通信的数字化和计算机技术的快速发展，这个曾被誉为“纯数学”的基础性学科进入了“应用数学”的领域. 如今，初等数论不仅被广泛应用到组合数学、数理逻辑、代数学等领域，它也是现代计算机科学的重要基础理论，特别是在密码学中发挥着至关重要的作用. 华盛顿大学布兰克（B.E. Blank）教授曾说：“现今如果你教一门数论课程，计算机专业的学生很可能比数学专业的学生更感兴趣. 许多人较少关心能被表成两个平方和的整数，但更关心Alice如何与Bob进行保密通信.”^[1]

本文简要阐述了几类基于模运算的简单密码体制，并结合实例具体介绍了同余理论、中国剩余定理以及二次剩余等在密码学中的简单应用，初步体会初等数论在密码学中的应用价值. 下面简单交代一下本文所使用到的初等数论知识.

1.1 同余与同余方程

定义1^[2,3] 设 若，则称与关于模同余,记为

；若，则称和关于模不同余，记为.

定理1^[2,3] 设，，，则

， ， ，

，其中为任意给定的一个整系数多项式.

定理2^[2,3] 设，则方程有解，若有解则恰有个解.

定义2^[2,3] 设则称的一个解为模的逆，记住.

定理3^[2,3] 设，则一次同余方程有且仅有一解.

定义3^[2,3] 设,，

，那么

方程（2.2）有解同余方程组（2.3）有解.

如果（2.3）式中有个解，，那么方程（2.2）有个解.

1.2 中国剩余定理

设，，，

则一次同余式组恰有一解，且解为

，

其中满足.^[2,3]

1.3 Euler函数与Euler定理

定义4^[2,3] 设，中与互质的数的个数为，则称为Euler.

定理4^[2,3] 设，则.

Euler定理^[2,3] 设，则，为Euler函数.

Fermat小定理^[2,3] 设，为素数. 若，则.

1.4 二次剩余

定义5^[2,3] 设是素数，，若有解，则称为模的二次剩余；若无解，则称为模的二次非剩余.

定义6^[2,3] 设为奇素数，，规定对模的符号为

Euler判别条件^[2,3] 设是奇素数，，则.

定理5^[2,3] 设是奇素数，.时，的解为.

2 初等数论在密码学中的应用

密码学是一门研究信息的保密以及复原保密信息以获得其真实信息的学科，主要分为密码分析学、密码编码学两大块. 密码学的基本目的是保证两个在不安全信道上进行通信的人（通常称为Alice和Bob）能够进行保密通信，使得第三方（通常称为Oscar）即使截获了通信双方的通信内容也无法理解其准确含义. 在通信过程中,Alice和Bob分别被称为信息的发送方和接受方. Alice发送给Bob的消息，通常称为明文，一般用P表示，它是人们可以直接识别和使用的信息，例如文本、图像、语音信息或者视频信息等. Alice使用预先和Bob商量好的密钥(Key)对明文进行一定的处理，变换成Oscar无法直接识别或使用的信息. 这种将明文转化为密文的变换叫作加密，经过加密变换后的明文叫作密文，用C表示. 与加密相反，解密是将密文转化为明文的过程.^[4]

密码学有着悠久的历史，最早的密码技术可以追溯到几千年以前. 19世纪末，无线电的发明使密码学进入一个快速发展的时期. 该时期密码的加密与破译主要通过手工操作或机械操作实现的. 古典密码变化较小，比较简单且容易破译，但其设计原理和分析方法对于理解、设计和分析现代密码有着重要作用. 古典密码主要应用于军事、政治和外交等领域. 例如第二次世界大战期间德军使用的Enigma（恩尼格玛）密码、盟军使用的Hagelin（哈格林）密码、日军使用的“蓝密”和“紫密”. 密码战的胜利对于反法西斯战争的胜利起了重大的作用.^[5] 密码学正式作为一门科学的理论基础应该首推1949年美国科学家Shannon的一篇文章《保密通信的信息理论》，他在研究保密机的基础上，提出了将密码建立在解某个已知数学难题基础上的观点. 1976年，Diffie和Hellman在发表的“密码学新方向”一文中提出了一种崭新的密码设计思想. 公钥密码体制的设计原理与安全性主要取决于该体制所依赖的加密函数的单向性. 以公钥密码体制的提出和数据加密标准DES的问世为标志，现代密码学开始蓬勃发展. ^[6,7]

2.1 几种基于模运算的密码体制

剩余内容已隐藏，请支付后下载全文，论文总字数：9861字