侯毅苇++张晓媛+肖倩

摘要：本文首先介绍了密钥码体制几种重要的数论定理，而后分析了几种传统的密钥码体制和公开密钥码体制的编码原理，探讨来常见的几种密钥码体制的解码方法，分析密钥码体制的安全性。

Abstract： This paper first introduces several important theorem of key code system， and then analyzes the encoding principle of several traditional key cryptography and public key cryptography system， discusses the decoding method of several common key code systems， and analyzes the security of key code system.

关键词：密钥码体制；数论；安全性

Key words： key code system；number theory；security

中图分类号：O156.2 文献标识码：A 文章编号：1006-4311（2017）07-0220-03

0 引言

数论是一门古老的纯数学学科，高斯曾经说过“数学是科学的女王，而数论则是数学的女王”。近年来，随着社会和技术的发展，数论中素数理论、欧拉定理、同余理论、费马大定理、中国剩余理论、高次剩余理论等许多基本理论在现代保密通讯、数字签名、身份验证等方面获得了广泛的应用，为信息技术的发展提供来重要的支撑。本文就密码数论解码方法进行探讨，研究常用密钥码体制的安全性。

1 密钥码体制中常用的数论定理

1.1 素数分布规律

素数，又称质数。自然界中除了自身和1以外，不再有其他因数的数字就叫做素数。素数有无限个，以36N（N+1）为单位，随着的增大，素数的个数以波浪形式渐渐增多，越往后越无规律性。

1.2 欧拉定理

欧拉定理，又称费马-欧拉定理，若n，a为正整数，且n，a互质，则

aφ （n）≡1（modn），

其中φ（n）为欧拉函数。

1.3 费马大定理

费马大定理，数学史上著名的定理，由法国17世纪数学家费马提出，又被称为“费马最后的定理”，提出后，经历三百多年的猜想辩证，在1995年被英国数学家安德鲁·怀尔斯彻底证明。定理指出，

当n>2时，关于x，y，z的方程

xn+yn=zn

没有正整数解。

1.4 费马小定理与素数测定

若N是素数，对于任意1？燮a？燮n-1的整数有：

an-1modn=1

但它的逆命题就不一定成立了，即an-1modn=1，则n不一定为素数，比如当a=4，n=15时，414mod15=1，但是4不是素数而是合数。

1.5 大整数分解问题

整数分解又称因子分解，是指：将一个正整数写成几个素数的乘积。大整数分解是数论研究的重要内容，是许多现代密码系统的关键所在。如果能够快速解决整数分解问题，则RSA公钥算法和Blum Shub随机数发生器等几种重要的密钥码体系将会被瓦解。大整数的分解同素数测定问题一样，难度甚至超过素数的测定。比如对于一个较大的，有n个二进制数位长度的两个相差不多的素数的乘积数，目前还没有已知算法可以在O（n）的时间内分解它，最好的渐进线性运行时间是普通数域筛选法（GNFS）。不过，彼得·肖在1994年发现了一种可以运用量子计算机构造出2n量子位在多项式时间来解决这个问题的算法。2001年，首台7量子位的量子计算机分解15，验证了算法。对于现在的计算机，GNFS是已知最好的分解n个二进制数位大素数的方法。

2 數论在传统密钥码体制的运用

2.1 Ceasar密钥码体制

2.2 PH密钥码体制

Pohlig和Hellman在1978年，发表了一种新的加密方法，具体加密方法是：取满足的（e，p-1）=1奇素数p和正整数e作为编码密钥，首先对字母表进行变换，如表2。

2.3 “随机数序列”加密

随机数序列加密法方法：

①转换成二进制数；

②随机地选择一个二进制数，即随机数序列，作为加密密钥；

③将明码按照随机数序列的位数分组，最后一组位数不足时，用0补齐；

④把各组明码与随机数序列按位模加，方法是两数相加结果等于它们的和被2除得的余数，即0+0=0，0+1=1，1+1=0

例：明码：01100011101011001

随机数序列：10100001101000011

密码：11000110000011010

密码解密的方法：用密钥随机数序列，与密码模加。

随机数序列密钥码原理被机械和电子密码机广泛使用。随机数序列密码的保密性完全取决于密钥的随机性，如果密钥是真正的随机数，那么这种密钥码体制在理论上就是不可破解的。但这种方式所需的的密钥量大的惊人，在实际应用中不可能实现。目前一般采用伪随机序列来替代随机序列，即现使用的随机数序列密钥码都存在一定的循环周期，周期的长短决定了加密的强度，一般使用的密钥周期长度都大于，最长的甚至超过来。

随机数序列密钥码体制的安全性依赖于简单的异或运算和一次一密的乱码本，也就是密钥流发生器。密钥流发生器输出的密码越接近随即，对密码分析者来说就越困难。

3 数论在公开密钥体制中运用

3.1 陷门单向函数y=fk（x），（k为参数）

在没有附加信息的情况下，陷门函数只能正向计算，逆向计算是不可行的，只有在获得了附加信息后，逆向计算才可行。

3.2 公开密钥码体制

1976年，美国学者Diffile和Hellman为解决密钥码的分发与管理问题，以陷门单向函数为基础提出来公开密钥码体制：为用户（假定为A）创建一个密钥对（e，d），其中e由A作为公开密钥对外公开，d则是私人密钥由A保密。根据陷门函数单向性可知，明文使用公开密钥利用陷门单向函数加密后，可以向A发送加密信息，由于只有A保存有陷门密钥，故密文可以安全的发送到A。从而解决来陌生人之间的保密通讯问题。

3.3 RSA方案

公开密钥码体制算法中使用最广泛的是RSA。RSA一对密钥由公共密钥和专用密钥组成，公共密钥用来加密而专用密钥则是用来解密。该算法是1977年由麻省理工（MIT）的Rivest、Shamir和Adleman基于欧拉定理利用陷门单向函数实现的密钥码体制。RSA方案实现原理如下：

④设p，q是两个不相等大素数，n=pq（其中p，q保密，n公开）。

明文空间M=密文空间C=Zn，随机生成e，且ed≡1modn，将（n，e）作为公开密钥，（n，d）为私人密钥；

加密过程为：

fe：M→C即y≡xemodn其中x∈M，y∈C。

解密过程为：

fd：C→M即x≡ydmodn其中x∈M，y∈C

3.4 RSA方案的安全性

已知p或q，则可计算欧拉函数φ（n），根据公开密钥e计算出私人密钥d，可以看出RSA的安全性在于分解开n的难度（一般令p≠q）。密钥的長度从40bit到2048bit可变，加密计算时要把明文分块，各块的长度也要根据密钥的长度改变，加密成相同长度的密钥块。理论上密钥码越长，加密安全性就越高，但加密解密的计算成本也相应增加，目前常用的密钥码长度为64位。

4 结论

密钥码实质是整数性质的具体应用，是数论研究领域的一个分支。随着信息技术的爆炸性发展，数字城市，工业4.0，物联网，个人支付，社交网络等技术正在逐步渗透进社会生活的方方面面。保密通讯，密钥码体制不再局限于国防和商业领域，已经进入到了每个人日常生活中。数论这门古老的纯数学学科，也走出了象牙塔，焕发出勃勃生机，深刻的影响着每个人的生活。

参考文献：

[1][加]Douglas R.Stinson（冯登国译）.密码学原理与实践[M].北京：电子工业出版社，2003.

[2]肖国镇.密码计算机和通信系统数据安全[M].北京：人民邮电出版社，1993.

[3]胡向东，魏琴芳.应用密码学教程[M].北京：电子工业出版设，2005.

[4]闵嗣鹤，严士健.初等数论[M].北京：高等教育出版社，2003，7.

[5]Koblitz N. A Course in Number Theory and Cryptography[M]. New York： Springer2Verlag， 1987.

[6]Kranakis E. Primality and Cryptography[M]. New York ： John Wiley and Sons ， 1986.