1、1数论在几种常见密钥码体制中的运用摘要：本文首先介绍了密钥码体制几种重要的数论定理，而后分析了几种传统的密钥码体制和公开密钥码体制的编码原理，探讨来常见的几种密钥码体制的解码方法，分析密钥码体制的安全性。 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 syst
2、em， 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 引言 数论是一门古老的纯数学学科，高斯曾经说过“数学是科学的女王，而数论则是数学的女王” 。近年来，随着社会和技术的发展，数论
3、中素数理论、欧拉定理、同余理论、费马大定理、中国剩余理论、高次剩余理论等许多基本理论在现代保密通讯、数字签名、身份验证等方面获得了广泛的应用，为信息技术的发展提供来重要的支撑。本文就密码数论解2码方法进行探讨，研究常用密钥码体制的安全性。 1 密钥码体制中常用的数论定理 1.1 素数分布规律 素数，又称质数。自然界中除了自身和 1 以外，不再有其他因数的数字就叫做素数。素数有无限个，以 36N（N+1）为单位，随着的增大，素数的个数以波浪形式渐渐增多，越往后越无规律性。 1.2 欧拉定理 欧拉定理，又称费马-欧拉定理，若 n，a 为正整数，且 n，a 互质，则 a （n）1（modn） ， 其
4、中 （n）为欧拉函数。 1.3 费马大定理 费马大定理，数学史上著名的定理，由法国 17 世纪数学家费马提出，又被称为“费马最后的定理” ，提出后，经历三百多年的猜想辩证，在1995 年被英国数学家安德鲁?怀尔斯彻底证明。定理指出， 当 n2 时，关于 x，y，z 的方程 xn+yn=zn 没有正整数解。 1.4 费马小定理与素数测定 若 N 是素数，对于任意 1？燮 a？燮 n-1 的整数有： an-1modn=1 但它的逆命题就不一定成立了，即 an-1modn=1，则 n 不一定为素数，3比如当 a=4，n=15 时，414mod15=1，但是 4 不是素数而是合数。 1.5 大整数分解
5、问题 整数分解又称因子分解，是指：将一个正整数写成几个素数的乘积。大整数分解是数论研究的重要内容，是许多现代密码系统的关键所在。如果能够快速解决整数分解问题，则 RSA 公钥算法和 Blum Shub 随机数发生器等几种重要的密钥码体系将会被瓦解。大整数的分解同素数测定问题一样，难度甚至超过素数的测定。比如对于一个较大的，有 n 个二进制数位长度的两个相差不多的素数的乘积数，目前还没有已知算法可以在 O（n）的时间内分解它，最好的渐进线性运行时间是普通数域筛选法（GNFS） 。不过，彼得?肖在 1994 年发现了一种可以运用量子计算机构造出 2n 量子位在多项式时间来解决这个问题的算法。200
6、1 年，首台 7 量子位的量子计算机分解 15，验证了算法。对于现在的计算机，GNFS 是已知最好的分解 n 个二进制数位大素数的方法。 2 ?德墼诖?统密钥码体制的运用 2.1 Ceasar 密钥码体制 2.2 PH 密钥码体制 Pohlig 和 Hellman 在 1978 年，发表了一种新的加密方法，具体加密方法是：取满足的（e，p-1）=1 奇素数 p 和正整数 e 作为编码密钥，首先对字母表进行变换，如表 2。 2.3 “随机数序列”加密 随机数序列加密法方法： 转换成二进制数； 4随机地选择一个二进制数，即随机数序列，作为加密密钥； 将明码按照随机数序列的位数分组，最后一组位数不足
7、时，用 0补齐； 把各组明码与随机数序列按位模加，方法是两数相加结果等于它们的和被 2 除得的余数，即 0+0=0，0+1=1，1+1=0 例：明码：01100011101011001 随机数序列：10100001101000011 密码：11000110000011010 密码解密的方法：用密钥随机数序列，与密码模加。 随机数序列密钥码原理被机械和电子密码机广泛使用。随机数序列密码的保密性完全取决于密钥的随机性，如果密钥是真正的随机数，那么这种密钥码体制在理论上就是不可破解的。但这种方式所需的的密钥量大的惊人，在实际应用中不可能实现。目前一般采用伪随机序列来替代随机序列，即现使用的随机数序列
8、密钥码都存在一定的循环周期，周期的长短决定了加密的强度，一般使用的密钥周期长度都大于，最长的甚至超过来。 随机数序列密钥码体制的安全性依赖于简单的异或运算和一次一密的乱码本，也就是密钥流发生器。密钥流发生器输出的密码越接近随即，对密码分析者来说就越困难。 3 数论在公开密钥体制中运用 3.1 陷门单向函数 y=fk（x） ， （k 为参数） 在没有附加信息的情况下，陷门函数只能正向计算，逆向计算是不可行的，只有在获得了5附加信息后，逆向计算才可行。 3.2 公开密钥码体制 1976 年，美国学者 Diffile 和 Hellman 为解决密钥码的分发与管理问题，以陷门单向函数为基础提出来公开密
9、钥码体制：为用户（假定为A）创建一个密钥对（e，d） ，其中 e 由 A 作为公开密钥对外公开，d 则是私人密钥由 A 保密。根据陷门函数单向性可知，明文使用公开密钥利用陷门单向函数加密后，可以向 A 发送加密信息，由于只有 A 保存有陷门密钥，故密文可以安全的发送到 A。从而解决来陌生人之间的保密通讯问题。 3.3 RSA 方案 公开密钥码体制算法中使用最广泛的是 RSA。RSA 一对密钥由公共密钥和专用密钥组成，公共密钥用来加密而专用密钥则是用来解密。该算法是 1977 年由麻省理工（MIT）的 Rivest、Shamir 和 Adleman 基于欧拉定理利用陷门单向函数实现的密钥码体制。
10、RSA 方案实现原理如下： 设 p，q 是两个不相等大素数，n=pq（其中 p，q 保密，n 公开） 。 明文空间 M=密文空间 C=Zn，随机生成 e，且 ed1modn，将（n，e）作为公开密钥， （n，d）为私人密钥； 加密过程为： fe：MC 即 yxemodn 其中 xM，yC。 解密过程为： fd：CM 即 xydmodn 其中 xM，yC 3.4 RSA 方案的安全性 6已知 p 或 q，则可计算欧拉函数 （n） ，根据公开密钥 e 计算出私人密钥 d，可以看出 RSA 的安全性在于分解开 n 的难度（一般令 pq） 。密钥的?L 度从 40bit 到 2048bit 可变，加密
11、计算时要把明文分块，各块的长度也要根据密钥的长度改变，加密成相同长度的密钥块。理论上密钥码越长，加密安全性就越高，但加密解密的计算成本也相应增加，目前常用的密钥码长度为 64 位。 4 结论 密钥码实质是整数性质的具体应用，是数论研究领域的一个分支。随着信息技术的爆炸性发展，数字城市，工业 4.0，物联网，个人支付，社交网络等技术正在逐步渗透进社会生活的方方面面。保密通讯，密钥码体制不再局限于国防和商业领域，已经进入到了每个人日常生活中。数论这门古老的纯数学学科，也走出了象牙塔，焕发出勃勃生机，深刻的影响着每个人的生活。 参考文献： 1加Douglas R.Stinson（冯登国译）.密码学原
12、理与实践M.北京：电子工业出版社，2003. 2肖国镇.密码计算机和通信系统数据安全M.北京：人民邮电出版社，1993. 3胡向东，魏琴芳.应用密码学教程M.北京：电子工业出版设，2005. 4闵嗣鹤，严士健.初等数论M.北京：高等教育出版社，2003，7. 75Koblitz N. A Course in Number Theory and CryptographyM. New York： Springer2Verlag， 1987. 6Kranakis E. Primality and CryptographyM. New York ： John Wiley and Sons ， 1986.
