一种基于GF（ ）的流密码设计

舒景辰　张志佳　张丹

摘 要：为满足密码学安全领域对安全性和加密速度的需求，本文设计了一种高效流密码。本算法基于流密码体制进行设计，最小数据处理长度为128位，每次分组密钥长为560位。在数据加密过程中向明文混入无效信息，扩充密文数据量并能有效避免特殊数据带来的不安全隐患。算法的加、解密结构具有很大的相似性，易于进行并行计算以及在硬件上实现。针对真随机数发生器和伪随机数发生器两种方式产生的密钥给出不同的优化算法，降低存储代价。

关键词：流密码；分组结构；数据冗余；有限域GF（ ）

中图分类号：TP309.7 文献标识码 A 文章编号：2095-2163（2014）02-

An Algorithm of Stream Cryptography based on GF（ ）

SHU Jingchen，ZHANG Zhijia，ZHANG Dan

（School of Software， Shenyang University of Technology， Shenyang Liaoning， 110870， China）

Abstract： In order to satisfy the needs of security and efficiency of cryptography， this paper designed an algorithm， which is based on stream cipher. The minimum length of data processing is 128 bits and length of each grouping key is 560 bits. The plaintext data is mixed with invalid information in the process of encrypted， expands ciphertext data and effectively prevented hidden dangers that specific data brings. Encryption and decryption algorithm have a lot similarities in structure， which are easy to be implemented in parallel computing and hardware. Depending on the way to generate true-random number generator and pseudo-random number generator， different optimization algorithms are given to reduce storage costs.

Key words： Stream Cryptography；Block Structure；Data Redundancy；Finite Field GF（ ）

0引 言

密码学是信息安全技术的核心，主要由密码编码技术和密码分析技术两个分支组成[1]。密码学是在编码与破译的对抗实践中逐步发展起来的，并随着先进科学技术的应用，已日渐成为一门综合性的尖端技术科学。密码学是一门交叉学科，集语言学、数学、电子学、声学、信息论、计算机科学以及通信与信息系统等多学科于一体，涉及的内容非常广泛[2]。密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。早期密码仅是对文字或数字进行加、解密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、解密变换。现今信息网络的普及，给人们带来高效信息共享便利的同时，也带来了安全隐患，所以当今各国对密码学的编码和分析研究均表现了浓厚的兴趣，并给予了高度的重视。除了能够保证信息的机密性，密码技术还能完成数字签名、身份验证、系统安全等高级功能，从而在提供了安全性的同时又保证了信息的完整性[3]。

密码学理论主要有三大体制，即基于数学的公钥密码、对称密码和基于量子力学的量子密码[4]。从密码学的发展史来看，密码学经历了传统密码学和现代密码学两个阶段。现代密码学是建立在精确的安全假设基础上，通过使用安全证明的方法，可证明方案已达到精确陈述的安全要求。现代密码学的一个发展分支即是理论密码学，这一分支为现代密码学提供了理论基础和基本原则[5]。下面即对密码学理论的三大体质进行逐一地分析和阐述。

公钥密码体制主要有两类，一类基于大整数因式分解，另一类基于离散对数[6]。在公钥密码体制中，基于大整数因式分解的RSA应用最为广泛，是目前最有影响力的公钥密码。由于RSA基于一个简单的数论事实且又能抵抗已知的所有密码攻击，因而得到了广泛的应用。随着科学技术的发展，分解大整数的能力日益增强，768位模长的RSA密码体制已经面临威胁，而要保证RSA的安全性就要相应地增加模长。但是分组长度太大，密钥产生的运算代价会很高，由此而导致加密速度将比DES等传统密码的速度低得多，所以RSA只适用于较小文件[7]。

对称密码体制是密码算法的重要组成部分，不仅可用于数据加密，也可用于消息的认证。根据对明文消息加密方式的不同，对称密码可以分为分组密码和流密码两种，并广泛应用于商业和军事系统中[8]。关于分组密码分析的方法中最具影响的两个攻击方法就是差分分析和线性分析。在密码的破译方面，国内外的研究工作则主要集中在积分分析、功耗分析和代数攻击的方法上[9]。

流密码的分析和设计在军事和外交保密通信中有着重要价值，流密码的设计基本上都是保密的，国内外少有专门论述流密码学的著作，公开的文献也不多。尽管如此，由于流密码具有长度可灵活变化以及运算速度快等优点，业已成为国际密码应用的主流，其中基于伪随机序列的流密码则是当今最通用的密码系统[10]。

本文提出的基于GF（ ）的流密码借鉴了分组密码结构化明显及流密码加密速度快的特点，在现有算法的基础上加以改进，通过混入部分无效信息、有限域运算等方式增强了密文的安全性。该算法具有较强并行计算能力，易于软硬件实现。由于此技术的密钥空间庞大且运算简单，所以能对大文件进行快速加密，适用于数据传输及安全认证等方面。

1研究内容

本算法基于流密码体制进行设计，借鉴分组加密的处理结构，每次可处理256位数据，有较高的加解密速率，在64位机上的算法效率可达948KB/S。密钥可由伪随机数发生器和真随机发生器两种方式产生。使用伪随机数发生器产生密钥时只需存储种子，而且占用空间也很小。然而使用真随机数发生器产生密钥时却需要较大的存储空间，本算法对其存储进行了优化设计。算法还提供了对特殊数据处理的解决方案，能有效避免明文在全0、全1状态下所带来的安全隐患。每次分组密钥为560位，由三种密钥构成，分别实现了有限域运算、矩阵混淆以及异或操作的功能。在数据加密的过程中向明文混入无效信息，扩充密文数据量。算法加解密结构具有很大的相似性，因此代码实现简单，且易于开展并行计算。

2密码结构设计

2.1设计思路

在流密码体制中，产生密钥有两种方式。一种是基于物理信息的真随机数发生器，一种是基于数学函数的伪随机数发生器。本算法同时适用于两种密钥发生器，并对真随机发生器产生的密钥进行压缩。目前常用伪随机数发生器来生成易于保存的非主观的密钥[11]。根据伪随机数的性质，不同的种子将生成不同的随机序列。传统密码学是通过置换等方式改变位置，不能从根本上解决数据安全问题，而利用GF（ ）上的有限域计算则能提供更高级别的安全保障。同时，在数据的处理方面，进一步加入了与明文等长的冗余信息，数据量扩充一倍。

2.1.1 加解密流程

明文字节流进入处理机后，首先，与等长的随机二进制数据进行隔位混入；其次，对其进行GF（ ）上的乘法模运算；再次，写入矩阵进行混淆；最后，对前几阶段处理后的数据进行异或操作，实现对数据的三次加密。

解密是加密的逆序操作，首先，对密文先进行异或操作；其次，写入矩阵进行数据还原；再次，通过计算GF（ ）上的乘法逆元还原数据；最后，去除混入的随机二进制数。

2.1.2 密钥组成

系统共分为三种密钥，分别负责三种加密方式，均有不同的种子，这些种子分别是U1、U2、U3密钥。每次分组处理时密钥长度为560位，共分为3组，U1密钥（GF（ ）密钥，256位）对数据进行多项式模运算，U2密钥（矩阵混淆密钥，48位）对数据进行矩阵列混淆，U3密钥（异或密钥，256位）与256位数据进行异或。

2. 2无效信息混入

明文数据流进入密码系统后，每次分组128位获取，每隔一位插入一个随机二进制数。每次数据分组处理完成后，数据长度由128位扩展至256位，数据量扩大了1倍。由于伪随机数概率分布的稳定性，此时倘若无效信息是通过这种方式产生的，就能有效避免全0、全1等特殊数据的出现。

2.3在GF（ ）上的模运算

GF（ ）在现代密码学中有重要的意义，其计算原理是基于多项式有限域运算。在GF（ ）上进行的乘法模运算是封闭的，不会超出数据的取值范围。GF（ ）具有较高的生成效率，但不能对整字节进行计算。GF（ ） 能计算整字节数据，但由于其最大素数为251，不能在 范围内取值，造成空间浪费[12]。考虑到后者的整字节处理能力，本算法选用GF（ ）有限域进行计算。

无效信息混入处理后的数据按1字节分段，然后对其进行乘法模运算。式（1）中T为U1密钥，P为经无效信息混入处理后的1字节二进制数据。

本文定义‘ 符号为连接符，且数据右为高位，密钥左为高位。

， （1）

2.3.1 加密

加密进行最高次为8的乘法模运算，既约多项式为：

根据密钥计算和明文G（x）和F（X）：

对两函数求积并进行模运算，如式（2）所示：

（2）

将 拆分为二进制形式即为通过GF（ ）运算后加密的结果。

2.3.2 解密

利用扩展欧几里得算法可求出在GF（ ）上的乘法模运算逆元 。对相同次幂的系数进行异或，那么

（3）

即为解密后的数据[13]。

2.4矩阵混淆

本部分对U1密钥处理后的数据进行二次加工，数据按行方向写入矩阵，通过行位移后，利用16位全排列对矩阵进行列置换。

2.4.1 矩阵混淆加密

定义一个 的矩阵，将数据利用矩阵进行混淆。经过无效信息混入处理后的数据从128位扩增至256位，将其倒序按行方向写入矩阵，随后对第 行数据进行左移 位操作，处理后结果如图1所示（ 表示行， 表示列）。

图1 混淆矩阵

Fig.1 Chaotic matrix

倒序写入将不同分组的数据顺序打乱，行位移和列读取的混淆方式使每个分组中的数据从字节级别分散开。 为矩阵混淆密钥（U2密钥）， 为加密后的数据，具体操作方式遵循下列公式：

（4）

（5）

2.4.2 矩阵混淆解密

解密过程与加密相似，是加密的逆序。 为矩阵混淆密钥（U2密钥）， 为密文数据，密钥和明文的定义如下：

（6）

（7）

定义 为数据中间量，利用映射关系还原矩阵的列混淆，那么（ 表示矩阵中 行第 个元素）：

（8）

T为未经过行位移的数据。对第 行数据进行右移 位操作，完成了矩阵的还原。然后，再按行读取即完成了二位矩阵至一维向量的转换。

2.4.3 矩阵混淆密钥的产生

事实上，矩阵混淆密钥是16位数的全排列，每位均不同。本算法利用递减进制位法生成全排列序列，需借助递降辅助序列 [14]。规定

（9）

（10）

令 初值取15，每次取 ，进行 赋值，为一次操作。每次操作后， 值减1，至 为0止，快速生成了16位数的一种全排列，即为矩阵混淆密钥U2。

2.4.2 矩阵混淆密钥的压缩

使用真随机数产生密钥时，若直接存储将占用8字节，由于本算法密钥量大，需对其进行压缩。16！=20 922 789 888 000 小于248=281 474 976 710 656 ，因此可将排列数进行散列后存储在6字节空间内[15]。其中全排列

与常进制数相似，变进制数第 位的位权为 ，且满 进1[16]。可利用变进制计数法进行散列，其位权值为：

（11）

规定 是 的个数，将变进制数转为10进制数：

（12）

即为压缩后的矩阵混淆密钥U2，与直接存储相比，每个分组节省了2字节空间。

2.4.5 矩阵混淆密钥的解压

将 按权值展开后，得

（13）

那么逆序数 可得。解压过程同样需要借助递降辅助序列，设 初始值为15，每次进行 操作。每次操作后 高位数值逐次向低位补齐，经过15次操作，解压得到完整的矩阵混淆密钥。

算法如下：

for i ← 15 to 0 do

S[ i ] ← T[ Q[ i ] ]

for j ← Q[i] to i-1 do

T[ j ] ← T[ j + 1 ]

2.5异或处理

由于模运算无法生成251以上的数据，存在不安全因素。为此，对数据进行异或处理可使数据具有更高的安全性。这一部分对数据进行第三次加密，密钥为U3，密钥长度与数据长度相等。加密前数据为 ，那么加密后的数据 按如下公式计算：

（14）

解密只需将密文与密钥进行按位异或即可，公式如下：

（15）

2.6安全性分析

流密码结构因其具有较高的安全性，一直应用于军事系统中。本算法的安全性完全基于密钥安全，每次分组处理的密钥长为560位。其中256位为GF（ ）密钥，48位为矩阵混淆密钥，256位即为异或密钥。在加密与处理过程中混入了无效信息，数据量扩大1倍，杜绝了全0、全1事件的出现，在此基础上又进行了GF（ ）上的计算，使得密码系统具有较大的不稳定性，导致数据每改变一位，明文改变多位。

2.7效率分析

算法支持多线程编程，但使用单线程编程便于测算算法效率。经过对10MB大小的数据进行1 000次测试发现，得到的加密和解密时间非常相近。但当采用不同位宽生成伪随机数时，代码效率会有较大的差异。算法速率与伪随机数发生器位宽的关系如表1所示。

虽然算法位宽的增加，会使得算法效率提升，但算法效率不会无休止地面、增长。随着位宽的增加，其增长速率表现出递减的趋势。随机数位宽的扩大会减少随机数产生的次数，但同时也会增加数据拆分等相关工作的运算代价，由此造成的效率降低会更明显于随机数计算次数减少所带来的好处。本算法的结构化明显、原理简单，因而代码实现容易。在数据处理过程中，向明文添加冗余信息，能有效避免特殊值产生的不安全因素，增强了密文的安全性。

3结束语

该文设计了一款基于GF（ ）的流密码算法，能够满足密码学安全领域对安全性和加密速度的需求，具有一定的现实意义。该设计以流密码体制为理论基础，提出了无效信息混入的概念，结合了有限域封闭运算、矩阵混淆和异或的三种加密方式。这种设计思想既适合在软、硬件上高速实现，又能满足密码学安全应用的需求。

参考文献：

[1]冯登国.国内外密码学研究现状及发展趋势[J].通信学报，2002，23（05）：18-26.

[2]曾辉，张跃进.信息工程专业密码学课程理论教学研究： 2010年亚太地区信息论学术会议[C].西安：出版者不详，2010：69-72.

[3]吕彩霞.密码学技术在网络信息安全中的应用[J].科技广场，2011，（09）：104-107.

[4]林德敬，林柏钢.三大密码体制：对称密码、公钥密码和量子密码的理论与技术[J].电讯技术，2003，（03）.

[5]任伟.密码学与现代密码学研究[J]. 信息网络安全，2011，（08）：1-3.

[6]陈晓峰，王育民.公钥密码体制研究与进展[J].通信学报，2004，25（08）：109-118.

[7]王水勇，石冰心.基于RSA的安全应用及漏洞分析[J].计算机与数字工程，2005，33（3）：34-38.

[8]付安民，张玉清.对称密码算法暴力破解的研究现状和进展： 2006北京地区高校研究生学术交流会[C].北京：出版者不详，2006：2011-2017.

[9]肖国镇，白恩健，刘晓娟.AES密码分析的若干新进展[J].电子学报，2003，（10）：1549-1554.

[10]罗启彬，张健.流密码的现状和发展[J].信息与电子工程，2006，4（01）：75-80.

[11]胡涛，郭立，黄昊，刘军.一种新的混沌随机数生成器实现方案[J].电子技术应用，2006，（06）：51-53.

[12]STALLINGS W. Cryptography and Network Security[M].New York：Pearson，2010.

[13]蔡永泉，赵磊，靳岩岩.基于有限域GF（2～n）上圆锥曲线的公钥密码算法[J].电子学报，2010，（09）：1464-1468.

[14]李模刚.全排列生成算法在克莱姆法则中的应用[J].现代计算机（专业版），2010，（09）：13-15.

[15]周云才.利用排列的逆序数实现排列生成算法[J].信息科技，2006，（01）：151.

[16]李淑芝，王显珉.基于m-n变进制规则的动态图软件水印算法[J].计算机工程，2012，38（21）：17-21.