基于非均匀B-样条曲线的加密算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于非均匀B-样条曲线的加密算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：
提出一种适用于软件加密和身份认证的新型加密方法。基于非均匀B惭条曲线函数的构造方法和几何特征，提出了基于非均匀B惭条曲线的加密算法。利用密钥埋置非均匀B惭条基函数节点信息，并通过明文生成控制点，从而得到形态丰富的样条曲线，并通过曲线抽取有效信息作为密文，达到加密散列效果。该加密算法有效地利用样条曲线丰富的特征信息进行加密散列，在增强加密强度的同时有效地保证了加密效率，能够广泛地应用于软件加密和身份认证领域，适应当前加密算法需要经常更新的需求。
ス丶词：
非均匀B惭条； 加密算法； 密钥埋置； 间距变异
ブ型挤掷嗪牛 TP309.7
文献标志码：A
英文标题
Encryption algorithm based on nonuniform Bspline curve
び⑽淖髡呙
WU Sheng1,2, GUO Xinyu1,2, XIAO Boxiang1,2, LU Shenglian1,2, WEN Weiliang1,2
び⑽牡刂(
1.National Engineering Research Center for Information Technology in Agriculture, Beijing 100097, China;
2.Open Key Laboratory of Information Technology in Agriculture, Ministry of Agriculture，Beijing 100097, China
英文摘要
)
Abstract:
A new encryption method for software encryption and authentication was proposed. This approach was based on nonuniform Bspline curve function constructing method and geometric characteristics. Key was embedded into nodes of nonuniform Bspline basis function, and then the control points which can construct a rich shape curve were generated according to explicitly, thus the spline curve was obtained. Finally, effective information was collected through the curve as the cipher text for encryption. The encryption algorithm used effectively curve features information to encrypt hash, at the same time strengthening encryption and enhancing the encryption efficiency. The proposed algorithm can be widely used in software encryption and authentication. Furthermore, encryption algorithm can satisfy current needs of frequent updates.
英文关键词
Key words:
nonuniform Bspline; encryption scheme; key embedding; pitch variation
0 引言
随着计算机通信网络化的飞速发展，信息作为一种社会发展的重要战略资源，在社会生产和日常生活中发挥着重要的作用，社会的信息化已经成为当今世界发展的潮流和核心。信息加密技术是保障信息安全最基本、最主要的技术措施，也是现代密码学的主要组成部分。在很多情况下，信息加密是保证信息安全的唯一方法，信息加密的目的是保护静态存储的数据、文件、信息和动态传输的数据信息。加密过程必须由各种加密算法来具体实现，利用密钥来确保双方信息的安全，尽可能以很小的代价换取很大的安全保障。而所谓的加密，就是用基于数学方法的程序和保密的密钥对信息进行编码，把计算机数据变成一堆杂乱无章难以理解的字符串，只允许合法的接收者恢复数据的本来面目，而对于非法窃取者，即使得到了密文，也无法辨认原始数据。
近年来许多专家学者在这方面做了一些研究。到目前为止，已的加密算法已有几百种，包括MD5算法、RSA算法、量子加密算法、基于图像的加密算法以及椭圆算法[1-3]等。葛丽娜等人[4]提出一种基于圆性质的对称密钥加密算法，实现了抗密码分析攻击。李娟等人[5]提出一种压缩图像的三维混沌加密算法，能有效抵抗已知明文攻击。David Salomon[6]提出的基于椭圆曲线的加密算法，很好地利用了密钥量小、灵活性好等优点。本文通过分析非均匀B惭条基函数的构建特征，提出了一种新的加密算法。该加密算法有效地利用样条曲线丰富的特征信息进行加密散列，在增强加密强度的同时有效地保证了加密效率，能够广泛地应用于软件加密和身份认证领域，适应当前加密算法需要经常更新的需求。
1 信息加密与B惭条曲线
1.1 信息加密原理
密码学是研究如何实现秘密通信的科学,为了保证在发送者和接收者之间传递的信息不被第三者获得而对要传递的信息进行加密。根据加密特点，通常将加密算法分为3类：1)对称加密。对明文的加密和解密使用同一组密钥。2)非对称加密。密钥是以一对的方式出现的，成为公钥和私钥，主要应用于加密和签名。3)散列。散列又称单向函数。一组字串经单向函数作用后，生成一组固定位数的字串，这个过程是不可逆的。为了使密文信息安全可靠,需要经常更新算法,增加算法的安全强度,这是信息加密和解密研究的一个中心内容。
散列算法[7]一般是对明文信息的提炼形成明文摘要，通常摘要信息长度比明文长度小得多，且为一个固定长度。散列算法要求任何输入信息的变化，哪怕仅一位，都将导致散列结果的明显变化，并且防止冲突，即找不出具有相同散列结果的两条信息。本文提出的基于非均匀B惭条曲线加密算法，是对散列加密方法的一种逆运算。对有限长度的明文信息，施加非均匀B惭条曲线加密散列算法，能够生成非均匀B惭条曲线函数，通过曲线函数导出能够反映出曲线细节的离散节点信息作为密文，并通过埋置随机密钥，对非均匀B惭条曲线随机生成，达到散列防冲突效果。该算法能够广泛应用于软件加密和身份认证领域。
1.2 B惭条曲线
B惭条曲线是在Bezier曲线的基础上提出的。给定n+1个控制点Pi(i=0,1,…,n),也称为特征多边形的顶点,B勃样条曲线定义为[8]：オ
C(t)=∑ni=0PiNi,k(t);i=0,1,…,nВ1）
其中：Pi是控制多边形的顶点；Ni.k(t)称为k阶(k-1次)B勃样条基函数；非递减的参数t序列T： t0≤t1≤…≤tn+k+1称为B勃样条函数的节点矢量。И
B惭条曲线按其节点矢量中节点的分布情况，可划分为均匀B惭条、准均匀B惭条和非均匀B惭条3种类型。假定控制多边形的顶点为Pi(i=0,1,…,n)，阶数为k（次数为k-1），则节点矢量是T=[t0,t1,…,tn+k]。那么非均匀B惭条曲线的节点矢量是任意分布的，只要在数学上成立（节点序列非递减，两端节点重复度小于等于k，内节点重复度小于等于k-1）Ф伎裳∪。这样的节点矢量定义了非均匀B惭条基函数。非均匀B惭条曲线可以根据基函数的次数分为不同次数的样条函数类型，如图1所示为3次非均匀B惭条曲线。
图片
图1 非均匀B惭条曲线
2 基于非均匀B惭条曲线的加密算法
周阳花等人[9]利用三次B惭条曲线特征信息进行身份认证系统的研究，提出了一种新的身份认证系统几何加密算法。本文利用随机生成的节点信息，对非均匀样条曲线形态特征进行调整，从而避免控制点加密曲线散列碰撞问题。由明文生成控制点信息，有效地丰富了非均匀B惭条曲线的几何特征。该算法计算效率高、散列强度好，能够有效地应用于软件加密过程和身份认证中，适应于当前加密算法需要经常更新的软件加密环境。
┑2期
吴升等：基于非均匀B惭条曲线的加密算法
┆扑慊应用 ┑31卷
2.1 密钥生成与埋置
密钥一般具备以下3种特性：1）由一串固定长度的杂乱无章的字符串表示；2）能够随机生成，且尽量唯一；3）满足加密算法需要。在非均匀B惭条曲线的加密算法中，密钥信息用来构建基函数的节点信息，有效调整曲线形态，达到加密曲线形态多样化，从而有效防止密文冲突。郭凤华等人[10]研究表明,通过调整一个节点使之变大或者变小可以调整B惭条曲线的形状,为B惭条曲线形状调整提供了简便有效的方法。如图2所示。
图片
图2 修改一个节点对B惭条曲线的影响
根据非均匀B惭条曲线基函数要求，密钥序列或密钥变形序列需满足数值非递减，且首尾数值为0和1的特征。在实际编程实现中，可通过以下两个步骤生成密钥：1）利用计算机时间获取函数GetSystemTime(&st)获取当前时间，时间包括年/月/日/时/分/秒；2）然后对获取的时钟进行变形，映射到N维数值串（Nб话闳8），且数值满足非递减，为了满足非递减可采取对应字符ASCII值累加，然后除以最大值；最后通过对密钥变形得到节点信息串U(u1,u1,…,un),且0=u1≤u2≤…≤un=1。И
2.2 基于间距的明文变异方法
通常明文是由一串字符组成，该字符串包括字母、数字标点符号或操作符，且字母区分大小写。为了能使明文信息转化为非均匀B惭条曲线的控制点，需要把字符串中的字符转化为坐标点信息(坐标点信息包括横纵坐标值),根据非均匀B惭条曲线的特性，为了构建比较光滑的曲线，控制点应该避免局部交叉，且能保证明文变异是一一对应关系的，从而本文提出的基于间距的明文变异方法是：
Ъ偕杳魑奈S=“dfFGE,2WE/Fat”,首先确定起始控制点坐标P0(x0,y0),依次求明文S中各字符对应的ASCII值tn=ASCII(Sn),则P1=(x1,y1)=(x0+t1,t1); P2=(x2,y2)=(x1+t2,t2),…,Pn=(xn,yn)=(xn-1+tn,tn)。使控制点在x轴方向上坐标值累加，避免局部交叉，在y轴方向上保持不变，保持原来的几何形态多变特征。从而明文到控制点数列的映射关系为(P1,P2,…,Pn)=F(S)。И
2.3 加密算法
由密钥组成非均匀B惭条曲线基函数的节点，0=u1≤u2≤…≤un=1；然后对明文进行基于间距的映射处理，使明文转化为控制点坐标值。根据非均匀B惭条基函数的定义：
Ni,0(u)=1,ui≤u≤ui+10,其他（2）
Ni,p(u)=u-uiui+p-uiNi,p-1(u)+ui+p+1-uui+p+1-ui+1Ni+1,p-1(u)В3）
利用随机生成密钥，并进行处理得到非均匀B惭条基函数，在本文中为了提高算法效率，可以设定基函数的次数为有限次（2~6次），并根据非均匀B惭条定义，可求得在该基函数和控制点约束下的非均匀B惭条曲线函数，从而可以从该曲线上获取有用的信息作为密文。根据非均匀B惭条曲线定义（式（1）），得到直角坐标系下x、yХ至可系姆匠涛：
x=∑ni=0xiNi,k(t)； 0≤t≤1（4）
y=∑ni=0yiNi,k(t)； 0≤t≤1В5）
由于该曲线是连续的，可以从该曲线上获取无限的坐标点作为密文，可以根据需求得到密文字符串长度，坐标点可根据t区间的等间距求得。首先获取密文长度L,计算间隔距离S=1/L;密文坐标点为C(xm,ym)=(x(S×m),y(S×m)),0≤m≤L;然后由密文坐标映射为字符，为了把密文字符串中的字符均匀分布，采用坐标求和然后整体缩放算法，缩放映射为PM,P为密文坐标点，0＜mВ74,其中0~74代表密文的表现形式（大写字母、小写字母和数字）;最后通过ASCII转化得到密文。
2.4 算法实现流程
本文提出的基于非均匀B惭条曲线的加密算法，属于散列加密算法范畴，能够广泛地应用于软件加密和身份认证领域，该算法可以根据应用领域不同而进行变形。如下给出算法实现流程及详细实现步骤,如图3所示。
1)输入明文，并对明文进行基于间距的明文变异。
2)根据明文变异信息，生成非均匀B惭条控制点序列。
3)根据时钟信息，随机获取密钥。
4)根据随机密钥生成非均匀B惭条基函数节点序列。
5)通过输入加密次数，构建非均匀B惭条函数，进行基于非均匀B惭条曲线的加密。
6)对曲线加密信息，进行基于坐标值缩放算法的密文处理，获得散列密文，并对密文进行输出。
图片
图3 基于非均匀B惭条曲线函数加密算法流程
3 加密强度分析
为了适应当前数字化时代对加密算法需要不断创新和更新的需求，本文提出的基于非均匀B惭条曲线加密算法有效地利用了样条基函数节点变化对曲线的形态变化影响和算法加密效率比较高的优点。它的加密强度依赖于对密钥的设置长度和对密文的输出长度信息。根据非均匀B惭条的局部性特征，密钥作为样条基函数节点信息的变形，密钥的长短势必影响到样条曲线的振荡敏感程度（每个局部都在变化），从而使样条曲线的形态随着密钥的长度增加而丰富。另外，密文作为非均匀B惭条曲线离散点的反映，密文的长度对应着离散点的数量，从而密文越长，越能表达曲线几何特征，也越能避免散列碰撞问题。由于该算法属于不可逆加密算法，在加密的过程中既要满足加密强度，也要考虑加密时间。
对密码的破解一般有两种方法，一种是穷举法，另一种是根据密文和加密算法的加密过程分析进行破译。由于该加密算法属于散列不可逆算法，从而使用穷举法是不可取的。只能在获得加密流程后，通过分析基于非均匀B惭条的加密算法的加密过程进行解密。基于非均匀B惭条加密算法的解密关键点在于控制点数及取控制点的规律、取样条次数（样条次数越高加密细节越深入，解密空间越大）、取密文长度以及取密文点规律。表1给出了根据几个关键点对解密时间复杂度的影响。从非均匀样条函数来看，影响加密时间的主要在于样条次数，在本算法中开放了样条次数的设置，理论上可以选取nТ畏蔷匀B惭条进行加密。通过实验表明样条次数控制在2到5之间，加密迅速，适应于软件加密或身份认证需求。表2给出在处理器为P43.0、内存512@M、Windows XP操作系统下进行加密时间测试结果，结果表明，加密效率比较高，适应于软件加密网络化需求。
表格(有表名)
表1 解密时间复杂度
明文こざM控制さ闶P密文こざL样条ご问N解密じ丛佣
O(2M)O(2P ×M/P)O(2L)O(N2)O(2(M+P)×N2×M/P)
表格(有表名)
表2 加密试验结果
明文控制さ闶密文こざ妊条ご问加密耗な/ms
dede8ao23fk41lkds6621.0
dede8ao23fk41lkds8839.7
defg3vere4bgbfg5bfdf43dffdas64hg1212436.4
4 结语
本文根据非均匀B惭条的几何特征，利用密钥埋置非均匀B惭条基函数节点信息，并通过明文生成控制点，从而得到形态丰富的样条曲线，并通过曲线抽取有效信息作为密文。该加密算法有效地利用了非均匀B惭条特征信息，并通过样条曲线丰富的特征信息进行加密散列，在增强加密强度的同时有效地保证了加密效率。该算法的可扩充性较强，可以通过修改基函数节点布局以及加密长度等信息对加密算法进行扩展，但关于算法散列强度还需进一步的验证和非均匀B惭条的特征信息有待进一步挖掘，从而才能够进一步提高加密强度和效率。
げ慰嘉南:
［1］
RIVEST R L, SHAMIR A, ADLEMA L. A method for obtaining digital signature and publickey[J]. Communications of the ACM, 1978, 21(2): 120-126.
［2］
WIESNER S. Conjugate coding[J]. ACM SIGACT News, 1983, 15(1): 78-88.
［3］
孟彦.椭圆曲线加密算法的研究与应用[D]. 合肥：合肥工业大学, 2007.
［4］
葛丽娜,贺忠华,江焯林.基于圆性质的加密算法[J].计算机工程, 2009, 35(4): 180-182.
［5］
李娟,冯勇,杨旭强. 压缩图像的三维混沌加密算法[J].光学学报, 2010, 30(2): 399-404.
［6］
SALOMON D. 数据保密安全[M]. 梁志敏,蔡建,译.北京: 清华大学出版社, 2005:145-173.
［7］
林柏钢.网络与信息安全教程[M].北京：机械工业出版社, 2004: 155-163.
［8］
孙家广.计算机图形学[M].3版.北京：清华大学出版社, 2002.
［9］
周阳花,林意.基于三次B样条曲线特征的身份认证系统研究[J].微计算机信息, 2006, 22(3): 69-70.
［10］
郭凤华,杨兴强.调整节点矢量对B样条曲线的影响[J].计算机工程与科学, 2005, 27(11):109-110.