基于4阶正交拉丁方组实际基本密码系统设计

田传俊

深圳大学电子与信息工程学院，广东深圳518060

当前，密码学已成为数字信息安全领域的一门重要基础理论，其中，SHANNON创立的保密通信理论是现代密码学中最重要的基础理论之一[1-5]．2018年，笔者对SHANNON保密通信理论的部分内容进行了重新解释[6-7]，利用无限完善保密系统概念建立了比现有完善保密系统更一般的数学模型，丰富了实用流密码系统的设计方法．文献[6]将密码算法设计分为基本密码系统和应用系统两个相对独立的设计步骤．为使整个应用密码(或保密通信)系统具有完善保密性，可利用正交拉丁方组设计相关基本密码系统中的理论密钥空间，但这会使相关的实际密钥空间及其加解密变换的设计更加复杂．因此，研究基于拉丁方组的密钥空间的设计方法十分必要．考虑到文献[6]并未对实际基本密钥空间与加解密变换设计进行深入细致的研究，本研究提出基本实际密码模型的具体设计方法，以便为设计应用保密通信系统打下部分基础．

常用的基本密码系统都是利用1 bit明密文空间上的线性函数设计的[6-9]．因此，利用2 bit或多bit明密文空间上的非线性函数来设计基本密码系统就是全新的方法，可作为序列密码算法的重要组成部分．若将加密看成置乱编码，则1 bit加密是标量置乱编码，而多bit加密是矢量置乱编码，矢量编码比标量编码要复杂得多．当前对2 bit明密文空间上相关的多比特密钥空间设计的研究还未充分展开．因此，本研究拟讨论一类长度为2 bit或4元(明密文空间)非线性基本实际密码模型的设计问题，该方法易于推广到更多bit基本密码系统中．

由文献[6]可知，在1 bit(明密文)空间中，现有流密码系统常用的基本密码系统，是利用一个2阶拉丁方来设计其中关键的理论密钥空间的，而在2 bit明密文空间中，利用4阶拉丁方组可设计出更多的新基本密码系统．考虑到利用4阶及其以上阶拉丁方组比利用2阶拉丁方来设计基本密码系统或其理论密钥空间要复杂得多，本研究重点研究基于4阶正交拉丁方组的基本实际模型设计的问题．

1 记号和概念

参照文献[6-7]，将基本密码系统的理论模型表示为(M,C,T)或(M,C,T,T-1)，并将与之对应的实际模型表示为(M,C,K,E,D)．其中，M和C为(基本)明文和密文空间；T为基本理论加密密钥空间；K为实际密钥空间；E为(基本)加密变换；D为解密变换．在实际应用中，对于某个基本密码系统，设计的基本理论(密码)模型(M,C,T)和相应的基本实际(密码)模型(M,C,K,E,D)应满足如下关系：T可利用(K,E)来实现或表示，但T可利用多种不同形式的K和E来实现，逆变换T-1类似．

用小写字母表示基本明文和密文与实际密钥空间的元素或单元，如m∈M， 则对明文m加密可表示为c=T(m)=E(k,m)=Ek(m)∈C， 解密也类似表示．

参照文献[2-6]和计算机实际应用现状，通常将M和C设计为由某个长度的(所有)不同bit(向量或序列)组成的同一个集合，因而其设计会很简单．设计基本密码系统就是设计理论或实际密钥空间和加解密函数．为便于应用，K通常会被设计为一个较短消息组成的集合，而E和D会被设计为一组易于计算机实现的规则或运算，且最好做到E和D相同．K最好能设计为由某个长度的所有不同比特向量组成的集合，正如数据加密标准(data encryption standard, DES)算法中的实际密钥空间是由(几乎)所有不同的56 bit向量组成的集合一样．

设计基本密码系统的实际模型(M,C,K,E,D)要基于理论模型(M,C,T)，并利用正交拉丁方组设计该理论模型[6]．为设计出与理论模型对应的实际模型，先解释一下理论模型中每个理论密钥可逆变换的表示方法和正交拉丁方组的基本知识．

(1)

需要强调的是，每个Z22或Zn={0,1,…,n-1}上可逆变换的函数计算式都不是唯一的，但其表格式和矩阵式都是唯一的(在不管排序的情况下)，其中，n=2,3,…． 同一个可逆变换的函数计算式形式不同，其计算量也不同．因此，在实际应用中计算量最少或容易实现的计算式更会受到关注．表格式和矩阵式的唯一性有利于描述和研究变换或函数的一些本质特性，在理论研究中具有重要作用．尽管表面上函数计算式的多样性和灵活性会给理论研究带来不少困惑和麻烦，但因具有适于计算机应用等特点常被用于实际应用中．同时，函数计算式的实用性也易导致在实用的密码算法设计中只注重设计算法的实际模型，难见用“先理论模型、后实际模型”(或“理论与实际模型”并重)方法设计常用密码算法．因此，本研究基于文献[6]利用“理论与实际模型”并重的方法设计几种新的基本密码系统．

设A=(aij)n×n和B=(bij)n×n都是由数集Zn={0,1,…,n-1}中的数字构成的n阶矩阵，将A和B构成的矩阵对(A,B)记为

(2)

下面给出拉丁方及其正交组的相关概念．

定义1设n∈{2,3,4,5,…}， 若Zn上所有不同的数字在n阶方阵L的每行和每列中都出现，则称L为n阶拉丁方．

由定义1和定义2，可验证式(1)中的3个矩阵都是两两正交的4阶拉丁方，且2阶拉丁方仅两个，但它们并不正交．为便于叙述，本研究将由一个拉丁方组成的矩阵集合称为正交拉丁方组．

利用正交拉丁方组设计基本密码系统能在理论上保证整个保密通信系统在一定条件下具有完善保密性[6]．不过，每个正交拉丁方组都只能用于直接设计密码系统的理论密钥变换空间，相应的实际密钥空间及其加解密变换的设计方法却是复杂多样的．下面将对这一问题展开研究．

2 基本实际密码模型的设计方法

以式(1)中的正交拉丁方组所决定的理论密钥空间为例，设计相应的实际密钥空间．本研究设计方法可推广到其他类型的正交拉丁方组．

将式(1)中的3个拉丁方所决定的所有可逆变换按照从上到下、从左到右的顺序依次记为{T1,T2,T3,T4}，{T5,T6,T7,T8}和{T9,T10,T11,T12}． 甚至将明文省略，则T1,T2, …,T12可用向量表示为T1=(0,3,1,2)，T2=(1,2,0,3)，…，T12=(2,3,1,0)．

利用函数计算式表示上述可逆变换．对任意m1，m2∈Z2和m=m1m2∈Z22， 可逆变换T1为

(3)

采用类似方法，可得其他可逆变换的代数式为

c=T2(m)=(m2×m-m1+1)mod 4

c=T3(m)= (m2×m-m1+3)mod 4

c=T5(m)= (m2m1+3)mod 4

c=T6(m)= (m+m1+m2+2)mod 4

c=T7(m)= (m+m1+m2)mod 4

c=T8(m)= (m2m1+1)mod 4

c=T10(m)=[(2×m2-1) ×m1+m2]mod 4

c=T12(m)=(m2×m-m1+2)mod 4

需要注意的是，对任意x,y∈Z2，xy和x×y意义并不相同．可见，式(1)中的每个拉丁方都可利用“非统一形式”的非线性代数计算式表示．

按照上述方式，Z22中的每个可逆变换都能利用代数式表示，在此不再赘述．不过，3 bit或4 bit等所确定的集合Z8或Z16等的所有可逆变换或拉丁方数量会非常多，难以全部列举，导致相关代数式也难以全部列出．Z22中每个可逆变换或拉丁方实际中都能明确写出其代数式的特点会在理论密钥变换空间设计时发挥特殊作用．

然后，考虑基本实际密钥空间K和加解密函数E与D的设计．与1 bit基本密码系统的密钥空间具有唯一性不同，2 bit基本密码系统的密钥空间呈多样性，且密钥数量随正交拉丁方组数量的变化而变化．若与应用密钥流序列空间特性结合，还能提出新的研究方向．下面将详述把K设计为长度为2、3和4 bit时的设计方法．

2.1 基本实际密码系统实际密钥空间K1由2 bit组成

T11(m)+(k1∧k2)×T12(m)]mod 4

(4)

2)基本解密变换D1： 对任一密文c=c1c2∈Z22和密钥k=k1k2∈Z22， 其中，c1,c2，k1,k2∈Z2， 将D1设计为

(5)

2.2 基本实际密码系统实际密钥空间K2由3 bit组成

1) 加密变换E2： 对任一2 bit明文m=m1m2∈Z22和任意3 bit密钥k=k1k2k3∈Z2， 其中，m1,m2,k1,k2,k3∈Z2， 将E2设计为

(k1∧k2∧k3)×T8(m)]mod 4

(6)

2)解密变换D2： 对任一2 bit密文c=c1c2∈Z22和任意3 bit密钥k=k1k2k3∈Z23， 其中，c1,c2,k1,k2,k3∈Z2， 将D2设计为

(k1∧k2∧k3)×T3(c)+

(7)

2.3 实际基本密码系统实际密钥空间K3由4 bit组成

1)加密函数E3： 对任一2 bit明文m=m1m2∈Z22和任意4 bit密钥k=k1k2k3k4∈Z24， 其中，m1,m2,k1,k2,k3,k4∈Z2， 可利用如下统一代数式将加密变换c=E3(k,m)设计为

(8)

由式(8)可见，只要调整好各自的应用密钥流序列的统计特性，利用有重复和无重复拉丁方组所设计的基本密码系统构造出的两种保密通信系统就会是等价的．

2)解密函数D3： 对任一2 bit密文c=c1c2∈Z22和任意4 bit密钥k=k1k2k3k4∈Z24， 其中，c1,c2,k1,k2,k3,k4∈Z2， 可将解密变换m=D3(k,c)设计为

(9)

上述3种2 bit(明密文空间)基本密码系统都是非线性的[6]，而重复利用2次常见的逐个bit异或运算所设计的2 bit基本密码系统是线性的，因而可认为利用这3种非线性新基本密码系统来设计流密码算法将完全不同于现有常见的流密码算法，且(加解密或被攻击或破解的)计算量会更大．

为说明上述基本密码系统能用于设计完整的流密码算法，结合JK触发器所产生的密钥流序列设计了一个简单流密码算法，对1个短英文文本文件进行加密，得到的加密文件为乱码．算法代码、原文件及加密文件请扫描论文末页右下角二维码查看图S1、S2和S3．

结 语

本研究基于文献[6]，利用1个4阶正交拉丁方组设计3种不同的4元或2 bit(明密文空间)非线性基本密码系统．本研究具有以下特点：

1)在现有流密码算法中，通常采用标量置乱编码方式的模2加法线性基本密码系统，它等价于利用2阶正交拉丁方设计基本密码系统，该方法的单一性决定了现有基本密码系统的研究缺乏技巧性和丰富性．本研究利用矢量置乱编码方式的4阶正交拉丁方组设计基本密码系统，高阶正交拉丁方组及其代数式构造灵活多样，丰富了基本密码系统的设计方法．

2)所提出4阶正交拉丁方组的非统一代数计算式构造方法，有利于推广到更高阶拉丁方组的构造上．通过对拉丁方组所决定的理论密钥变换进行统一的代数式设计，建立3种基本密码系统的实际模型，可用于新的序列密码算法设计．这种综合考虑基本密码系统理论模型和实际模型的设计方法，可为现有序列密码算法设计提供参考．利用理论密钥变换更利于分析密钥变换的性能，而利用实际密钥及其加密变换更利于在计算机实现．因此，理论与实际密码模型并重的设计方法对单钥密码算法设计都具有启发意义．

综上，4阶拉丁方组的构造方法对高阶拉丁方组的构造具有一定的指导作用，有利于进一步研究设计基本密码系统及其流密码系统．