一类特殊函数在信息密码学中应用证明与算法改进

摘  要：本文对单向陷门函数的概念、设计原则和应用等方面进行了描述。并对单向陷门函数在密码学中的应用、如何在非对称加密函数中实现的算法，及在KDC、PKI中的使用进行了说明，且在Diffie-Hellman算法基础上提出并研究了一个带时间戳的公共模非对称改进加密算法，证明主要的数学结论。

关键词：陷门函数;非对称加密算法;算法改进

中图分类号：TP309.7      文献标识码：A 文章编号：2096-4706（2019）18-0106-05

Abstract：This paper gives the concept and design principle of one-way trapdoor function，its application in cryptography，how to implement the algorithm in asymmetric encryption function，and how to use it in KDC and PKI. On the basis of Diffie-Hellman algorithm，an improved public modulus asymmetric encryption algorithm with time stamp is proposed and studied，and the main mathematical conclusions are proved.

Keywords：trapdoor function;asymmetric encryption algorithm;algorithm improvement

0  引  言

身份認证、数据的保密性、不可篡改性和防止抵赖性等安全服务，是信息安全的一项关键技术。这些技术离不开函数，设计一个单向陷门函数，可以为网络和信息交换提供安全保障。

如果在单向函数中另加一个条件，使得原先不可解的函数变为可解，对于加密具有特殊的意义，这就是单向求逆的意义所在，这样的函数就是单向陷门函数。

1  密码学简介及非对称密码体制

密码学是对加密密码和破译密码的技术进行分析研究的学科，对信息安全领域中各项技术起支撑作用。按加密密钥与解密是否一样进行划分，可以分为对称密钥和非对称密钥。下面我们对这两种密码分别进行介绍。

1.1  对称密码体制

在对称密钥中，使用一样的密钥对明文和密文进行加解密。

1.2  非对称密码体制

1976年，Diffie和Hellman第一次提出了公钥密码学的概念，以此来解决传统密码学中难以保存管理密钥分配及抗否认的数字签名认证问题。这种较为复杂的密码体制与对称密码体制明显的区别在于，它使用两个密钥，且互不相同和不能相互推出，可以完成对加密明文和解密密文的操作，而且解密密钥不能仅仅根据公开密码算法和另一个密钥计算得到。

2  公钥密码PKC的核心元素

公钥密码的核心元素主要基于单向函数、单向陷门函数、单向散列函数。

单向陷门函数的定义：已知x，可容易地计算y=f（x），而给定y，求满足y=f（x）的x非常困难，当得到对应的陷门t，可以使y=f（x）中x的计算变得容易。

3  单向陷门函数的设计

单向函数和陷门函数是公钥密码学的核心，公钥密码体制的设计主要取决于单向陷门函数的设计。

事实上给出单向函数的定义是很棘手的，其原因如下：

（1）由于单向函数一般求逆都是困难的，故严格意义上说陷门函数不是单向函数;

（2）陷门有可能不唯一，通过大量研究，通过很多陷门就可容易地找到逆。一旦陷门信息的保密性被破坏，求逆就变得容易。

非对称密码的原理就是建立在单向陷门函数基础之上，加密是容易的方向，每个人都可以利用公钥加密数据，解密却是难的方向，它的设计非常困难，在没有陷门信息的情况下，即使用群集计算机，在可接受的时间内也不能解密数据。

下面给出一些常见的近似单向函数：

（1）离散对数。存在一个大素数p，p-1含有一大素数因子q。整数g满足：1

当y、g、p为给定的值，求x=loggy mod p则变为离散对数问题。目前最快的达到L（p）次运算的方法，运算复杂度为L（p）=exp{（lnpln（lnp））1/2}。

（2）因数分解问题。通过算法给出大素数p和q，计算n=pq，只需要一次乘法运算。若已知n，求p和q，即为因数分解问题，运算次数最少需要T（n）次，次数T（n）=exp{m（lnnln（lnn））1/2}，其中m为大于1的自然数。在实际密码算法操作中，整数n可取309位十进制。比如当n为300时，每μs运算一次，因子分解运算次数1.5E20次，所需时间为4E15年。

（3）背包问题。已知有限个自然数序列组合B=（b1，b2，…，bn），xi取0或1中的一个值时，求S=xibi，至多仅需要n-1次加法运算;如果给定B和S，求xi非常困难。各种情况共有2n种可能，当n规模很大时，在计算上是不可行的。

4  素性测试、求模逆元算法介绍

4.1  素性测试

很多密码算法首先需要随机选择一个或者多个非常大的素数。可以先产生很大的随机整数，再判断该大数是否是素数。当前还没找到简单有效的算法确定一个大数是否为素数。下面介绍Miller-Rabin的素数存在性概率检测法。

6.3  椭圆曲线密码算法

椭圆曲线上每个点另加一个叫做无穷远点构成的SET，其中定义了一个加法运算，这就构成一个阿贝尔群。在等式kD=D+D+…+D=S中，已知k和点D求点S比较容易，反之已知点S和点D求k却是相当困难的，这个问题则叫做椭圆曲线上点阿贝尔群的离散对数问题（Elliptic Curve Discrete Logarithm Proble，ECDLP）。椭圆曲线密码算法就是利用这个非常困难的问题研究设计的。

6.3.1  ElGaml的橢圆曲线密码求解过程

6.3.1.1  密钥产生

如果系统公开参数是一个椭圆曲线E及模数p，那么使用者可以执行如下步骤。

（1）选择一个任意整数k，满足0

（2）选择一个任意点A∈E，并运算B=kA。

（3）公钥就是（A，B），私钥就是k。

6.3.1.2  加密过程

假设明文N为E上的一点。首先选择一个任意的整数r∈Zp，其次运算密文（c1，c2）=（rA，N+rB）。密文有两点。

6.3.1.3  解密过程

计算明文N=c2-kc1。

6.3.2  Menezes-Vanstone梅内泽斯的椭圆曲线密码求解过程

Menezes-Vanstone梅内泽斯的椭圆曲线密码求解过程是效率很高的椭圆曲线加密法，其明文可以不落在椭圆曲线E上。

6.3.2.1  密钥产生

如果系统公开参数是一个椭圆曲线E和模数m，那么使用者执行以下过程。

（1）选择一个任意整数k，满足0

（2）选择一个任意点A∈E，运算B=kA。

（3）公钥是（A，B），私钥是k。

6.3.2.2  加密过程

假设明文N=（n1，n2），明文的点可在E上也可不在E上。

（1）选择一个任意数r∈ZH，H是E包含的一个循环子群。

（2）算出密文（C1，C2），有：

C1=rA，Y=（y1，y2）=rB，C2=（c21，c22）=（y1×n1 mod m，y2×n2 mod m）

6.3.2.3  解密过程

（1）算出Z=（z1，z2）=kC1。

（2）算出明文N=（c21×z1-1 mod m，c22×z2-1 mod m）。

7  密钥分发中心、PKI介绍

7.1  密钥分发中心（KDC）

Kerberos身份认证通过让被认证方和认证方知晓的Key来鉴定对方的真实身份。用这个Key加密的数据包可在客户端与服务器之间传送，因此这个Key是短效密钥。由于这个密钥仅在一次Session（会话）中有效，称这个Key是client和server之间的Session Key（会话密钥）。

7.2  PKI

公钥基础设施PKI是Public Key Infrastructure的简称，PKI是利用公钥加密技术为网上活动的开展建立一套安全基础设施。

为完善、规范这些互联网交易活动，各个国家对其进行了很多年的攻坚，形成了一套初步的互联网安全解决策略，这就是PKI。PKI采用证书发布维护管理公钥，通过认证中心CA（Certificate Authority），把客户的公钥和客户的其他信息（如名称、算法、颁布机构、有效期、E-mail、身份证号等）放在一起，通过PKI查询确认，对传输的数字信息进行加密，确保信息传输的保密性、完整性、真实性和抗抵赖。

8  Diffie-Hellman算法介绍与应用

Diffie-Hellman是指通过非对称加密实现一种确保共享对称密钥安全穿越不安全网络的方法，它是OAKLEY密钥确定协议的一个组成部分。Whitefield与Martin Hellman在上世纪提出了安全的密钥交换协议，称其为Diffie-Hellman密钥交换协议/算法。

基于本原根的定义及其性质，可以确定Diffie-Hellman密钥交换步骤，对该操作过程描述如下：

（1）有两个对外公开的参数，一个素数p和一个整数a，a是p的一个本原根。

（2）如果使用者甲和乙希望交换一个密钥，使用者甲选择一个作为私有密钥的随机数X甲（X甲

（3）使用者甲产生密钥的方式是key= mod p。同

样，使用者乙产生共享密钥的计算是key= mod p。这两个计算产生相同的结果：key=（Y乙）^X甲 mod p=（a^X乙 mod p）^X甲 mod p=（a^X乙）^X甲 mod p=a^（X乙X甲） mod p=（a^X甲）^X乙 mod p=（a^X甲 mod p）^X乙 mod p=（Y甲）^X乙 mod p，因此相当于双方已经共同拥有了一个相同的密钥。

（4）由于X甲和X乙是不公开的，一个网络侵入者可利用的参数值仅为p、a、Y甲和Y乙，所以网络侵入者被迫使用离散对数来确定密钥，这是一件很困难的事，对于大素数p，计算出离散对数几乎是不可能的。

9  带时间戳的公共模非对称加密算法介绍

如果通信双方不想利用KDC或PKI的基础设施，这样的通信过程复杂，会导致时间延误，成本相对比较高，也不易实现，现提出一个简化方便的通信算法，不需要第三方来进行服务，手续简单，有相当高的安全性，对于临时需要加密传输的数据能够马上实施。此算法的实现不考虑使用对称加密技术是因为在第三方攻击者用Sniffer或者Wireshark这样的网上抓包软件进行分析攻击的情况下，其安全性不高，并且密码本身的交换约定是一个容易泄密的过程。这个算法基于RSA思想，并作了一定的优化改进，约定双方都有一对公钥public key和私钥private key，为了简化操作约定，这两对公钥的模module相同，这样更加方便，但是安全性相对降低，如果双方交换这个模就容易被攻破原文，且这个模由谁来约定也是一个问题，如果由一方来确定就不够公平公正，导致通信双方的信任产生问题。下面来论证一下，如果这个模n被获取了，双方的公钥e1、e2被获取，这时，攻击者得到两组密文：

c1=me1 mod n

c2=me2 mod n

由于e1与e2互素，攻击者可以解出两整数r和s，满足：根据素数的性质r×e1+s×e2=1，在这个等式中，r和s有一个为负数，假设s为负数，则攻击者很容易算出明文m=（c1）r×（）-s，这样在一组用户之间共享n就不会很安全。设计的算法由双方共同产生模n，这个模是由两个素数p、q来确定，并且，这两个素数是较大的正整数，由双方各产生一个，然后传给对方，其安全性由后面的两个因素来保证，获得了两个素数p、q，就可计算出模n，再计算出欧拉数，再由欧拉数产生一个逆元，这个逆元就是私钥，不传给对方，这是安全因素一。安全因素二采用时间戳来使系统通信更加安全，主动通信方每过一个时间片约定更换新的模，即使第三方通过非法手段获取两个素数p、q，但是通过模n来求逆元是一个非常难的事，即使偶然破解出来，但是每隔一个时间片素数p、q的值发生了改变，这样确保整个通信是安全的。下面给出实现的具体算法。

（1）约定一个数s作为一个时间片，time=0。

（2）通信发起方调用素性算法生成一个很大的素数p，发送给接受方，等待。

（3）通信接受方调用素性算法生成一个很大的素数q，发送给接受方，等待。

（4）通信双方计算模n=p*q，欧拉函数ϕ（n）=（p-1）*（q-1）。

（5）time=time+1。

（6）通信发起方调用素性算法，找一个素数e1，使gcd（e1，ϕ（n））=1，发送e1给接收方，再调用求逆元算法求d1，满足d1*e1=1（mod ϕ（n））。

（7）通信接受方調用素性算法，找一个素数e2，使gcd（e2，ϕ（n））=1，发送e2给发送方，再调用求逆元算法求d2，满足d2*e2=1（mod ϕ（n））。

（8）通信发送方对原码m进行加密得出密码c，其计算公式为c=md1*e2（mod n）。time=time+1。

（9）通信接受方对密文c进行解密得出原文m，其计算公式为m=cd2*e1（mod n）。

（10）如果时间time

这个算法可用于通信双方进行密钥交换，向对方传递一个对称密钥，也可以对不复杂的通信直接进行加密传输，通过双非对称密钥进行传输。这个过程不需要第三方进行公钥传递，实现身份认证和信息传递。

10  结  论

上述所涉及的加密算法都是基于单向陷门函数设计，这些算法没有绝对的优劣性，而是可以在不同的情境下使用。当没有KDC第三方协议分发中心并且没有大量信息交换情形下，安全性更高的选择是用改进算法，即带时间戳的公共模非对称加密算法。

参考文献：

[1] 郭姝，施滔滔，张新玉.基于单向陷门函数的加密算法 [J].硅谷，2009（18）：97.

[2] 孙永雄，赵永哲，杨永健，等.基于遍历矩阵的单向（陷门）函数的构造方案 [J].吉林大学学报（信息科学版），2006（5）：555-560

[3] 郭亚军，宋建华，李莉，等.信息安全原理与技术（第2版） [M].北京：清华大学出版社，2013：111-115.

[4] 武春岭.信息安全技术与实施（第2版） [M].北京：电子工业出版社，2015：99-102.

[5] 覃中平，张焕国，乔秦宝，等.信息安全数学基础 [M].北京：清华大学出版社，2006.

[6] 张贤科.初等数论 [M].北京：高等教育出版社，2016.

作者简介：江忠（1966-），男，汉族，四川渠县人，副教授，本科，研究方向：计算机教育、高等数学、初等数学。