使用拟群的密码原语、差错编码和伪随机数改进方法

摘要

流密码，包括同步流密码(12)、自同步流密码(12)和完全异步流密码(12)，采用工作密钥和拟群变换，其中使用的拟群是基于初始秘密密钥(18)的。纠错(10)和伪随机数生成(24)改进器方法也采用拟群变换(24)。

说明书

技术领域

本发明的一般领域是信息传输。本发明更具体的领域是数据加密/解密。本发明另一更具体的领域是差错编码。本发明的再一更具体的领域是伪随机数。

背景技术

可以使用密码系统以为数据通信提供数据完整性和/或数据安全性。后者对于保护信道(包括有线和无线信道)上通信的数据可能是很重要的。一种加密类型利用流密码(stream cipher)。块密码(block cipher)的特征是响应于相同块输入产生相同块输出，与块密码相反，流密码可以响应于同样输入而在不同时间给出不同输出。流密码使用称为种子(seed)或密钥的输入，将输入串(如消息)转换成加密的输出串(如密文(ciphertext))，目的在于，没有该密钥的各方将看到加密的串为随机序列。加密的级别，以及在某种程度上为加密投入的资源，决定对于其他各方的安全性(或随机性)的级别。

由于缺少对特定输入的固定输出响应，因此流密码提供高于块密码的改善的安全性。在本领域中存在自同步(有时称为异步)和同步密码。在同步流密码中，来自解密的流的较后的输出不受在传输期间发生的差错(除了实际差错比特或比特组(块)上的差错)的影响。当差错影响解密的流时，采用自同步流密码。自同步密码流方法允许在差错引起错误地解码或传输多个块之后，正确解密流。

块和流密码、以及密码系统或传输方法一般而言利用一些重要的支持方法。作为实例，在密码中使用(伪)随机数生成。生成伪随机数，以便例如为加密和解密方法提供种子或基数。作为另一个实例，通常可以用来改善通信(特别是在噪声信道上)的纠错码，在密码方法中也可以提供益处。

发明内容

根据本发明的优选实施例，提供多种流密码，包括同步流密码、自同步流密码和完全异步流密码，其采用工作密钥和拟群(quasigroup)变换，其中使用的拟群是基于初始秘密密钥的。还提供纠错和伪随机数生成改进器方法，它们也采用拟群变换。

附图说明

图1是根据本发明的实施例的包括发送器和接收器的基本通信系统的框图。

具体实施方式

一般而言，在本发明的某些实施例中，提供具有可选择的密钥长度的同步流密码。在示例性实施例中，提供用于生成均匀分布的密钥流的步骤，该密钥流与明文(plaintext)数据流加性组合，以生成加密的输出流。密钥流生成步骤包括：基于秘密初始密钥确定工作拟群变换，并且使用该工作拟群生成密钥流。优选的同步流密码还对攻击提供了计算上不可行的屏障。密钥长度可以改变，以改进密码的安全性，而不用随着密钥大小增加，重新设计加密和解密的算法。对于足够小的密钥大小，运算可以在硬件或固件实现中流水线进行。

在本发明的其他实施例中，提供具有可变密钥长度的自同步流密码，也不需要随着密钥大小增加，重新设计加密和解密的算法。在自同步流密码的特定实施例中，通过基于秘密初始密钥确定工作拟群，以及作为工作密钥、工作拟群、以及要加密或解密的消息的固定数量的字母的函数，加密或解密消息，以执行加密和解密。与优选的同步流密码一样，优选的自同步流密码对于攻击是计算上不可行的，并且具有足够小的输入密钥，可以在硬件或固件实现中流水线进行。

在本发明的又一实施例中，提供一种新型的密码—完全异步流密码，其中生成输出流，作为工作密钥、基于初始密钥确定的工作拟群、和输入流的前面固定数量的字母的函数。这种类型的密码已被示出对于对手的各种攻击是安全的。同步密码、自同步密码和异步密码是可以使用拟群的、根据本发明的实施例实现的密码原语的例子。如这里使用的，术语“拟群”指拟群或者其任何等效代数对象。

本发明的其他实施例提供一种方法，通过将消息的块映射到码字，在二进制对称信道中纠错，其中映射是迭代的，并且对于任意码字，长度r的C的子串的分布是均匀的。根据优选实施例，使用拟群变换执行该映射。优选实施例提供低误比特率，例如，在几百比特的块的情况下，范围在10^-5内，与在几千比特的块的情况下，实现该误比特率的Turbo编码和LDPC相比，更加优越。

本发明的其他实施例提供改进器，用于改进伪随机数生成器的输出。通过改进器，解决了生成器中的输出弱点。改进实施例可以将伪随机串的周期增大到任何期望的长度。从可以使得各字母、各字母对、各三元组和广义的k元组的分布是均匀的意义上来说，可以使伪随机串均匀。优选的改进器不接替生成器的性质，并且即使在生成器产生琐碎输出(例如仅由字母串构成)时也能工作。优选的改进器考虑到拟群串变换中认识到的性质。复杂度是线性的(O(n))，其中n是输入伪随机串的长度，因此该改进器非常快速。它很灵活，并且可以在对于每个n＞1的n比特字母的字母表上工作。改进器的各实施例可以在例如小于1Kb的存储空间中实现。优选实施例的改进器接受低质量的伪随机串。使用可选阶的拟群变换该串，并且变换的次数也是可选择的。该改进器输出高质量的伪随机串。

参照附图，本发明的方法可以在通信系统14中使用的发送器10和/或接收器12中实现。发送器10从信息源18接收消息16，并且可以将该消息加密(或者改进该消息，如果使用差错编码或伪随机数改进)用于经由信道20进行信号传输。如本领域中将认识到的，信道20可以是有噪声的。接收器12接收信号(加密的消息、包含差错、伪随机数等的消息)，并且可以将该信号消息解密和/或纠正该信号中的差错，以产生解密或纠正的消息22，其被发送到目的地24。

预期可以配置发送器10和/或接收器12，以实现本发明的一个或多个方法。进一步预期可以使用计算机可读介质、芯片、传播信号、计算机等，以实现本发明的一个或多个方法或者导致其被实现。现在将讨论根据本发明的各方面的各种方法。

在本发明的第一类型的实施例中，提供具有可证明的安全性的、灵活的加性流密码，这里称为EdonX，它变换比特元组(tuples of bits)—优选地是半字节(nibble)(即，4比特元组)的输入流。EdonX的密钥长度是可变的，并且可以是n个半字节的任何串。通过使用拟群(quasigroup)串变换定义EdonX，并且其安全性基于拟群和拟群串变换的数学特性。在优选实施例中，EdonX使用可以用128字节存储的16阶拟群，并且连同内部存储器和可执行代码一起，它可以用小于1Kb实现。因此，在优选实施例中，EdonX适于在嵌入式系统中硬件实现。

一般而言，流密码使用随时间改变的加密变换，一次一个地加密明文消息的各个字符(通常是二进制位)，而块密码使用固定的加密变换，同时加密明文消息的字符组(group)。为了解决设计密码强大并且高质量的流密码的问题，公开了一种具有可证明的安全性、灵活的加性流密码EdonX，其变换半字节(即，4比特元组)的输入流。EdonX的密钥长度是可变的，并且可以是n个半字节的任何串，但出于安全的原因，我们建议n≥32。通过使用拟群串变换定义EdonX，并且其安全性基于拟群和拟群串变换的数学特性。EdonX的设计使用可以用128字节存储的16阶拟群，并且连同内部存储器和可执行代码一起，它可以用小于1Kb实现。因此，EdonX适于在嵌入式系统中硬件实现。

我们将简要地提及同步流密码的定义，如在A.Menezes，P.Van Oorschot和S.Vanstone的Handbook of Applied Cryptography，CRC Press，Inc.，1997中定义的。

定义1  同步流密码是这样的密码，其中密钥流独立于明文消息和密文生成。

同步流密码的加密处理可以通过以下等式描述：

σ_i+1＝f(σ_i，k)，z_i＝g(σ_i，k)，c_i＝h(z_i，m_i)

其中σ₀是初始状态，并且可以从密钥k确定，f是下一状态函数，g是产生密钥流z_i的函数，而h是输出函数，其将密钥流和明文m_i组合以产生密文c_i。

定义2  二进制加性流密码是这样的同步流密码，其中密钥流、明文和密文位是二进制位，并且输出函数h是XOR函数。

根据优选实施例的EdonX流密码是二进制加性流密码。通过使用拟群运算和拟群串变换定义EdonX。这里我们给出简要概述，要注意这里使用的术语“拟群”也可以指等效于拟群的代数对象。

定义3  拟群(Q，*)是满足以下规则的广群(groupoid)

这里我们将仅使用有限拟群，即，Q是有限集。与有限拟群密切相关的组合结构是所谓的拉丁方(Latin square)：

定义4基数IQI＝n的有限集Q上的拉丁方L，是具有来自Q的各元素的n×n矩阵，使得该矩阵的每行和每列是Q的置换(permutation)。

对于由其乘法表给出的任何有限拟群(Q，*)，它与拉丁方L相关联，该拉丁方L包括由该表的主体形成的矩阵，并且集合Q上的每个拉丁方L定义拟群(Q，*)。

两个拟群之间的合痕(isotopism)与自合痕(autotopism)的关系定义如下。

定义5如果存在从K到Q的双射(bijection)α，β，γ，使得对于每个x，y∈K，γ(x*y)＝α(x)·β(y)，则称为拟群(K，*)是对拟群(Q，·)的合痕。于是称三元组(α，β，γ)是从(K，*)到(Q，·)的合痕。

(K，*)的自合痕是(K，*)到其自身的合痕。我们用Autotope(K，*)表示由(K，*)通过一些自合痕获得的拟群。注意到，存在不超过|K|³个对(K，*)自合痕的拟群。如果α＝1和β＝1是恒等置换，并且γ是转置，则我们用γ(K，*)表示在自合痕(1，1，γ)下对(K，*)自合痕的拟群。

两个自合痕(α，β，γ)和(α′，β′，γ′)的乘法是以分量方式定义的，即，

(α，β，γ)(α′，β′，γ′)＝(αα′，ββ′，γγ′)

在证明EdonX的安全性方面，将使用下列性质：

命题1拟群(Q，*)的所有自合痕的集合Γ是在自合痕的乘法运算下的组。

在Denes，J.，Keedwell，A.D.：Latin Square and their Applications，EnglishUniver.Press Ltd.，1974中进一步说明了该性质。给定拟群(Q，*)，可以从运算*导出五个新运算，所谓的伴生(parastrophes)或伴随(adjoint)运算。我们将只需要用和/表示的下面两个(称为左伴生和右伴生)，并且定义为：

x*y＝zy＝xzx＝z/y

则代数集(Q，*，，/)满足恒等式

x(x*y)＝y，x*(xy)＝y，(x*y)/y＝x，(x/y)*y＝x，

并且(Q，)，(Q，/)也是拟群。

接着，我们定义拟群串变换的方法。考虑字母表(即，有限集)Q，并且用Q+表示由Q的各元素组成的所有非空词(word)(即，有限串)的集合。Q+的各元素将用a₁a₂...a_n表示，而不是(a₁，a₂，...，a_n)，其中a_i∈Q。令*为集合Q上的拟群运算，即，考虑拟群(Q，*)。对于每个a∈Q，我们定义两个函数e_a，*，d_a，*：Q+→Q⁺如下。

令a_i∈Q，α＝a₁a₂...a_n。则

e_a，*(α)＝b₁b₂...b_nb₁＝a*a₁，b₂＝b₁*a₂，...，b_n＝b_n-1*a_n，如该表中所示：

即，对于每个i+0，1，...，n-1，有b_i+1＝b_i*a_i+1，其中b₀＝a，，并且d_a，*(α)＝c₁c₂...c_nc₁＝a*a₁，c₂＝a₁*a₂，...，c_n＝a_n-1*a_n如该表中所示：

即，对于每个i＝0，1...，n-1，有c_i+1＝a_i*a_i+1，其中a₀＝a.。

函数e_a，*，d_a，*称为Q+基于具有首项a的运算*的e-和d-变换。

例如，取Q＝{0，1，2，3}，并且令拟群(Q，*)及其伴生(Q，)由下表中的乘法方案给出：

考虑串M＝00102300120010020003，并且选择首项0。然后通过变换e_0，*，我们将得到变换后的串C＝e_0，*(M)＝21023130113013002131，并且通过变换d_0，，我们将得到串D＝d_0，(M)＝22110202133211203223。

如果我们对串C应用变换d_0，，或者对串D应用变换e_0，*，则我们将得到初始串M。事实上，如Markovski，S.，Gligoroski，D.，Bakeva，V.：QuasigroupString Processing：Part 1，Maced.Acad.of Sci.and Arts，Sc.Math.Tech.Scien.XX 1-2，(1999)1328所讨论的，下面性质为真：

命题2对于每个串M∈Q⁺以及对于每个首项l∈Q，d_l，(e_l，*(M))＝M＝e_l，*(d_l，(M))，成立，即，e_l，*和d_l，是Q+的互逆置换。

优选地，EdonX对半字节运算，即，对4比特变量运算，因此它使用16阶拟群(Q，*)，以便对数据流进行拟群串变换。因此，对应拉丁方的各值用4比特表示。这对于存储在n个内部变量K_i(即，K＝K₀K₁...K_n-1)中的工作密钥的各值也成立，并且变量K_i具有范围{0，1，...，15}中的值。K的第i个值也将用K[i](＝K_i)表示。

EdonX在初始化阶段中，使用工作密钥K的初始秘密值K_in＝K_in[0]K_in[1]...K_in[n-1]。初始的16阶拟群(Q，·)可以是秘密的或公开的。通过存储在K_in中的秘密信息，EdonX对初始拟群(Q，·)以及对K_in的各值进行变换。在优选实施例中，EdonX也使用两个临时的4比特变量T和X，以及一个额外的整数变量Counter。EdonX的解密函数与加密函数相同。

EdonX加密(和解密)函数由下面的过程定义。运算*是通过从给出的初始拟群的运算·的自合痕而得到的拟群运算。运算是对半字节(即，4比特字母)的以比特方式的XOR运算。数m＝maxn，64表示工作密钥的长度，并且它取决于初始密钥的长度n，但是出于安全的原因，我们取m≥64。初始化阶段在下文通过单独的过程描述。

该算法非常重要的阶段是初始化阶段。它包括密码学算法中已经公知的技术，如填充(padding)、扩展和变换秘密共享的初始密钥K_in。然后，使用来自扩展和变换的密钥K_in的信息，以变换初始给出的拟群，以及设置工作密钥K的m个半字节的各初始值。初始密钥的长度n(以半字节为单位)可以是任何正整数，n越大，安全性越高(并且正如总是这样的情形，安全性的代价是系统的速度)；我们建议32≤n≤255。密钥选择的灵活性是EdonX的重要特征。

初始化阶段由下面算法描述：

  EdonX的初始化  阶段1初始密钥的输入1.输入：n-秘密密钥的初始长度(整数)和K_in＝K₀‖K₁‖...‖K_n-1(K_i是半字节)阶段2填充密钥2.设置K_in＝K_in‖n₁‖n₂其中n₁是n的最高有效半字节，而n₂是n的最低有效半字节。阶段3将密钥扩展到512个半字节3.设置K_ex＝K_in‖K_in‖...‖K_in‖K′其中K′包括K_in的头1个半字节，使得K_ex的总长度是512个半字节。阶段4用给出的16阶拟群(Q，·)变换K_ex4.For i＝0 to 511 dobeginSet leader＝K_in[i mod(n+2)]；K_ex←e_leader，·(K_ex)；K_ex←RotateLeft(K_ex)；end；阶段5变换(Q，*)←Autotope(Q，·)5.(Q，*)←(Q，·)；For i＝0 to 511 step 8 dobeginSet row₁＝K_ex[i]；Set row₂＝K_ex[i+1]；(Q，*)←SwapRows(Q，row₁，row₂)；Set column₁＝K_ex[i+2]；Set column₂＝K_ex[i+3]；(Q，*)←SwapColumns(Q，column₁，column₂)；Set γ＝(K_ex[i+4]，K_ex[i+6])；(Q，*)←γ(Q，*)；end；阶段6设置工作密钥K(K_ex的最后m个半字节)6.设置K＝K₀‖K₁‖...‖K_m-1＝K_ex[512-m]‖...‖K_ex[511]

我们应当阐明在初始化阶段中使用的若干运算和符号。首先，K_in表示初始密钥，K_ex表示扩展的密钥，并且符号II表示4比特字母的连接。然后，通知K_m[j]表示K_in的第j个半字节。函数RotateLeft(K_ex)循环旋转K_ex的各值，使得K_ex[i]←K_ex[i+1]，i＝0，1，2，...，510和K_ex[511]←K_ex[0]。函数SwapRows和SwapColumns的名字不言而喻，它们是交换拟群的各行或各列的函数。

在初始化阶段的最后，我们得到对手不知道的两个工作结构。即，第一未知结构是原始拟群Q(·)的自合痕—工作拟群(Q，*)，并且它是大约(16！)³≈2¹³²个自合痕中的一个，并且第二未知结构是替代原始初始秘密密钥K_in的、长度为4m比特(m个半字节)的工作密钥K。(然而，16阶拟群的自合痕类(autotopism class)的确切数量是未知的；最好的已知公共可得的结果是对于11阶拟群的。)

现在将用简化的(2-比特)EdonX呈现初始化、加密和解密运算的示例。该示例实现EdonX的原理，但为了简化说明，我们使用4阶拟群，而不使用16阶拟群。因此，我们用2比特字母(即，0、1、2和3)，而不用半字节。此外，我们不使用长度512的扩展的密钥，而将其缩短到长度16，并且我们还取m＝n。事实上，我们将EdonX的初始化阶段的阶段5改变为下面的简单形式：

  阶段5(示例)变换Transformation(Q，*)←Autotope(Q，·)5.(Q，*)←(Q，·)；For i＝0 to 16 step 4 dobeginSet row₁＝K_ex[i]；Set row₂＝K_ex[i+1]；(Q，*)←SwapRows(Q，row₁，row₂)；Set column₁＝K_ex[i+2]；Set column₂＝K_ex[i+3]；(Q，*)←SwapColumns(Q，column₁，column₂)；Setγ＝(K_ex[i+1]，K_ex[i+3])；(Q，*)←γ(Q，*)；end；

令初始拟群(Q，·)与前一示例中相同：

  ·  0 1 2 3  0123  2 1 0 33 0 1 21 2 3 00 3 2 1

设置初始值为半字节的K_in＝131。由于K_in的长度为3，并且由于用两个2比特字母对数字3的表示为0011＝00‖11)，因此我们填充K_in，并且得到K_in＝13103。然后通过连接K_in若干次，我们得到长度16的K_ex，即K_ex＝1310313103131031。然后通过e_l，·变换，变换扩展的密钥，我们得到K_ex的最终值，其中循环取首项l为填充的K_in的各值。在下面的表中，我们总结这些变形。

  Leader  K_ex1RotateLeft3RotateLeft1RotateLeft0RotateLeft3RotateLeft1RotateLeft3RotateLeft1RotateLeft0RotateLeft3RotateLeft1RotateLeft3RotateLeft1RotateLeft0RotateLeft3RotateLeft1RotateLeft  1 3 1 0 3 1 3 1 0 3 1 3 1 0 3 10 3 3 0 3 3 1 0 2 0 1 2 2 1 2 23 3 0 3 3 1 0 2 0 1 2 2 1 2 2 01 2 1 2 0 1 3 2 1 0 0 0 1 1 1 32 1 2 0 1 3 2 1 0 0 0 1 1 1 3 11 0 0 2 2 0 0 1 3 0 2 2 2 2 0 10 0 2 2 0 0 1 3 0 2 2 2 2 0 1 12 1 1 1 3 0 1 2 1 1 1 1 1 3 3 31 1 1 3 0 1 2 1 1 1 1 1 3 3 3 23 3 3 1 3 3 2 2 2 2 2 2 0 3 1 13 3 1 3 3 2 2 2 2 2 2 0 3 1 1 32 0 1 2 0 0 0 0 0 0 0 2 0 1 0 30 1 2 0 0 0 0 0 0 0 2 0 1 0 3 20 1 1 3 0 2 1 3 0 2 3 0 1 3 1 11 1 3 0 2 1 3 0 2 3 0 1 3 1 1 00 1 2 1 1 0 3 0 0 3 0 1 2 2 2 11 2 1 1 0 3 0 0 3 0 1 2 2 2 1 01 1 0 1 3 1 3 0 3 0 1 1 1 1 0 21 0 1 3 1 3 0 3 0 1 1 1 1 0 2 13 0 1 2 2 0 2 0 2 2 2 2 2 1 1 00 1 2 2 0 2 0 2 2 2 2 2 1 1 0 33 3 2 3 0 0 2 3 2 3 2 3 3 3 0 33 2 3 0 0 2 3 2 3 2 3 3 3 0 3 31 1 2 1 3 2 0 0 3 2 0 3 1 3 1 21 2 1 3 2 0 0 3 2 0 3 1 3 1 2 10 0 1 2 3 0 2 0 0 2 0 1 2 2 3 30 1 2 3 0 2 0 0 2 0 1 2 2 3 3 02 2 3 1 3 2 1 3 2 1 0 0 0 3 1 32 3 1 3 2 1 3 2 1 0 0 0 3 1 3 22 0 1 2 3 3 1 1 0 2 1 3 1 0 3 20 1 2 3 3 1 1 0 2 1 3 1 0 3 2 23 3 2 0 3 3 3 0 0 1 2 2 1 2 3 23 2 0 3 3 3 0 0 1 2 2 1 2 3 2 3

随着最后值K_ex＝3203330012212323，我们开始交替地交换各行、交换各列以及转置初始拟群(Q，·)的各元素，以便获得其自合痕。因此，首先我们交换行3和2，然后是列0和3，然后我们转置元素2和3，等等，如下各表中所示。

最后获得的拟群是将用于加密和解密的工作拟群(Q，*)：

  *  0 1 2 3  0123  1 3 0 22 0 3 13 1 2 00 2 1 3

工作密钥K取K_ex的最后n＝3个字母，并且成为K＝323。

现在，编码明文消息M＝30102300。用EdonX的优选实施例执行的计算如下表中所示。

    Counter＝0      Counter＝1  Counter＝2          Counter＝3  K  X  T  K  X  T  K  X  T  K  X  T  i  3  2  0  1  0  0  1  0  012  323  300  021  301  010  330  010  101  133  103  012  223  Input M  3  0  1  0  Output C＝XM  3  0  0  2      Counter＝4         Counter＝5         Counter＝6        Counter＝7  K  X  T  K  X  T  K  X  T  K  X  T  i  1  3  0  3  0  2  1  2  012  013  312  100  310  020  002  022  111  222  112  022  111  Input M  2  3  0  0  Output C＝XM  0  3  1  2

由于EdonX是二进制加性流密码，因此解密阶段的计算是相同的，并且唯一的差别将是在最后两行中(在这种情况下输入将为C，并且输出M＝XC)。

在开始，$$ >>Counter>=>0>,>p>=>[>>3>2>>]>=>1>,>>$$并且初始工作密钥K具有值K＝323＝3‖2‖3，X的值为X＝K[Counter mod 3]＝K₀＝3，并且T的值为T＝K[(Counter+p)mod 3]＝K₁＝2。然后，根据算法，如下我们获得X和T的各中间值以及密钥K的各新值。

对于i＝0，我们有X←X₀＝K₀*X＝3*3＝3，T←T₀＝T·X＝2·3＝1，K₀←X＝3，对于i＝1，我们有X←X₁＝K₁*X＝2*3＝0，T←T₁＝T·X ＝0·0＝2，K₁←X＝0，并且对于i＝2，我们有X←X₂＝K₂*X＝3*0＝0，T←T·X＝1·0＝1，K₂←X＝0。然后，我们将K₂的值改变为K₂←T＝1。通过这种方式，我们得到，对于Counter＝1的新工作密钥为K＝K₀K₁K₂＝X₀X₁T₂＝301，并且我们有输出值C₀＝XM₀＝03＝3。在上表中给出了对于Counter＝0，Counter＝1，...，Counter＝7的所有计算。因此，输入的明文串M＝3010230O被加密成密文串C＝30020312。

接着，我们将讨论和演示同步流密码EdonX的优选实施例的安全性益处。考虑安全性，我们假设初始秘密密钥K_in的长度n至少为32。我们还假设对手有可能选择明文/密文攻击，即，她/他可以选择明文并且可以获得对应的密文，并且假设初始拟群(Q，·)和初始密钥的长度n是公开的。此外，我们假设秘密密钥K_in的初始值以及密码的内部各状态：工作密钥K、工作拟群(Q，*)以及X和T的各值对于对手是未知的，并且她/他不能物理上访问它们。我们考虑到，如果对手将能够成功地重构工作密钥K、以及X和T的各值的一些部分，那么她/他将攻破EdonX。

我们已经能够示出，在不知道初始密钥K_in的情况下，不存在计算上可行的方法来知道工作拟群(Q，*)和工作密钥K的起始各值。我们将在下列步骤中给出证明：对手不能有效获得关于X和T的各值以及工作密钥K的一部分的信息。在下面的分析中，我们使用下列拟群串变换的性质：

命题3设(Q，*)为拟群，α为Q^*的任意串，并且e_l，*是首项为l的变换。如果我们对α应用e_l，*k次，则获得的串β＝(e_l，*)^k(α)具有各字母、各字母对、各字母的k-元组的均匀分布。

为了分析EdonX初始化阶段，按照我们的假设，密钥K_in的初始值可以具有至少128比特的长度。通过初始密钥有多长的信息而进行的K_in的填充，是其他公知的密码原语(cryptographic primitive)(如散列函数)中的标准过程。其作用是消除用两个不同初始密钥获得相同结果的可能性。例如，如果我们不进行填充，则初始密钥和将产生相同的工作密钥K。另一方面，填充向我们确保：对于不同初始密钥K_in，起始扩展的密钥K_ex将是不同的。扩展的密钥K_ex具有512个半字节的长度。它被公知的16阶拟群(Q，·)变换512次。由命题3，我们有下列推论：

推论1  密钥K_ex中的各字母、各字母对、各字母三元组、....的分布是均匀的。

密钥K_ex的分布的均匀性揭示了工作密钥K的分布的均匀性。由于K的长度至少为64个半字节，即，256比特，因此对手可以以不大于2^-256的概率猜出工作密钥。

作为推论1的结果，我们还有下列性质：

定理1  工作拟群(Q，*)是自合痕于初始拟群(Q，·)而随机获得的。

证明：在EdonX的初始化的阶段5中，在迭代处理期间，我们交换各行(row₁row₂)和各列(column₁column₂)，并且我们应用转置γ。这意味着在每个迭代步骤中，我们应用自合痕(α，β，γ)，其中，α＝(row₁row₂)，β＝(column₁column₂)，是在迭代的拟群上的置换，即，转置。因此，在阶段5中的每个迭代步骤之后，我们获得作为输入拟群的自合痕的拟群。通过命题1，工作拟群(即，阶段5的最终输出)是这样的拟群，即，在自合痕(α′，β′，γ′，)下的初始拟群的自合痕。α′，β′，γ′置换事实上是在阶段5期间分别获得的所有64个转置α＝(row₁row₂)β＝(column₁column₂)和γ的各乘积。由于在16元素集合上的每个置换可以表示为不超过15个转置的乘积，并且从随机密钥K_ex获得转置α，β，γ，因此我们有，α′，β′和γ′是可能的16！个置换中的任何置换。结果，我们得到，工作拟群可以是初始公开拟群的任何自合痕。

由于16阶拟群上存在大约16！³≈2¹³²个自合痕，因此我们发现，只能以大约2^-132的概率猜出工作拟群。

为了分析EdonX加密/解密阶段，从前面的部分我们得到，工作拟群(Q，*)和起始工作密钥K＝K₀K₁...K_n-1＝K_-1，0K_-1，1...K_-1，n-1对于对手是未知的。通过下述，我们为什么用K_-1，j表示K_j将会清楚。

设对手选择一对明文/密文串(M，C)＝((M₀M₁...)，(C₀C₁...))。此外，我们使用下面的符号：在Counter＝i的情况下，我们将使用符号K_i，j来代替符号K_j(j＝0，1，...，n-1)。对于变量X和T将使用相同的符号，即，符号X_i，j(T_i，j)意味着当Counter＝i在其第j次迭代时的变量X(T)。

因此，通过对于Counter＝i(i∈{0，1，2，...})的EdonX的加密/解密算法，对手可以获得下列方程系统(注意$$ >>p>=>[>>m>2>>]>>$$是常量)：

X_i，0＝K_i-1，0*K_{i-1，i mod m}

T_i，0＝K_{i-1，i+p mod m}·X_i，0

X_i，1＝K_i-1，1*X_i，0

T_i，1＝T_i，0·X_i，1

...

X_i，64＝K_i-1，64*X_i，63

T_i，64＝T_i，63·X_i，64

...

X_i，m-1＝K_i-1，m-1*X_i，m-2

T_i，m-1＝T_i，m-2·X_i，m-1

X_i，m-1M₀＝C₀

(4)

从上面的最后方程中，对手可以得到X_i，n-1＝C₀M₀的值，因为M₀、C₀是已知的。其余上述集合等效于下面的m+1，m≥64个拟群方程的系统，具有2m个未知的变量：K_i-1，0，...，K_i-1，m-1，...X_i，0，...，X_i，m-2，T_i，m-1

X_i，0＝K_i-1，0*K_{i-1，i mod m}

X_i，1＝K_i-1，1*X_i，0

.........

X_i，m-2＝K_i-1，m-2*X_i，m-3

M₀C₀＝K_i-1，m-1*X_i，m-2

T_i，m-1＝((...(K_{i-1，i+p mod m})·X_i，0)·...)·X_i，m-2)·(M₀C₀)

(5)

(即，

T_i，1＝T_i，0·X_i，1＝(K_{i-1，i+p mod m}·X_i，0)·X_i，1T_i，2＝T_i，1·X_i，2＝

((K_{i-1，i+p mod m}·X_i，0)·X_i，1)·X_i，2，...)

此外，对方不知道工作拟群(Q，*)，因此她/他应当定义集合{0，1，2，...，15}上的拟群运算*，然后求解该系统。事实上紧前面的系统是函数方程的系统，具有一个未知的拟群运算*，该运算包括具有2m个未知数的m+1个方程。我们有下面的定理，并且在其证明中使用上面恒等式。

定理216阶的任何拟群(Q，*)是下列函数方程的系统的解，其中Q＝{0，1，2，...，15}，

x₀＝y₀*y_i mod m

x₁＝y₁*x₀

x₂＝y₂*x₁

...

x_m-2＝y_m-2*x_m-3

a＝y_m-1*x_m-2

z＝((...(y_i+p mod m·x₀)·x₁)·...)·x_m-2)·a

(6)

有Q上的一个未知的拟群运算*和未知变量x₀，x₁，...，x_m-2，y₀，y₁，...y_m-1，^z，其中·是Q上的给定拟群运算，并且i(0≤i≤m-1)，$$ >>p>=>[>>m>2>>]>>$$和a∈Q是给定的。

证明：设*为Q上的任何拟群运算。我们考虑两种情况。

情况1：0≤i≤m-2(即0≤i mod m≤m-2)

对未知的y₀，y_i∈Q选择任意值。然后我们有x₀∈Q的唯一值，使得x₀＝y₀*y₁。对未知的y₁∈Q选择任意值。然后我们有x₁∈Q的唯一值，使得x₁＝y₁*x₀。继续这样，对未知的y_i-1∈Q选择任意值，然后我们有x_i-1∈Q的唯一值，使得x_i-1＝y_i-1*x_i-2。接着，我们计算x_i＝y_i*x_i-1∈Q的值，然后我们对未知的y_i+1∈Q选择任意值，并且计算x_i+1＝y_i+1*x_i∈Q的值，等等。通过这种方式，我们可以对未知的y₀，y₁，...，y_m-2选择任意值，并且我们可以由此计算未知的a＝y_m-1*x_m-2的(唯一)值。最后，从方程a＝y_m-1*x_m-2，我们有y_m-1＝a/x_m-2∈Q，然后我们可以计算z＝(y_i+p mod m·x₀)·x₁)·...)·x_m-2)·a∈Q。

情况2：i＝m-1(即，i mod m＝m-1)

在这种情况下，我们将以相反顺序重复情况1的过程。我们选择任意值y_m-1，∈Q，然后由方程a＝y_m-1*x_m-2，我们计算值x_m-2＝y_m-1a∈Q。然后，我们对于y_m-2，y_m-3，...，y₂，y₁∈Q选择任意值，并且在每次选择之后，我们计算值x_j＝y_j+1x_j+1∈Q，j＝m-3，m-2，...，0。最后，从方程x₀＝y₀*y_m-1，我们计算值y₀＝x₀/y_m-1，然后我们可以计算z＝(y_i+p mod m·x₀)·x₁)·...)·x_m-2)·a∈Q。

作为定理2的结果，我们有，为了找到(5)中变量K_i-1，j和x_i，j的合适的各值，对手将不得不选择16ⁿ≥2¹²⁸个可能的初始密钥之一、以及上面所示的函数方程的系统的16^m-2或(16^m-1)≥16⁶²＝2²⁴⁸个可能的解y_j之一。全部算在一起至少有2³⁷⁶种可能的选择。

接着，我们将示出，如果对手使用来自明文/密文串的若干连续半字节的信息，那么她/他不能在可行时间内攻破系统。即，我们将证明下面定理：

定理3为了以大于0.5的概率攻破系统EdonX，攻击者应当进行至少2¹⁹⁰次尝试。

不失一般性，定理3的证明的思路可以从Counter＝0 & Counter＝1& Counter＝2的情况中(即，当长度3的明文/密文流M₀M₁M₂/C₀C₁C₂已知时)看出。在该情况下，根据EdonX的加密/解密算法可以获得下面方程(其中也进行了如(5)中那样的简化)：

X_0，0＝K_-1，0*K_-1，0

K_0，0＝X_0，0

X_0，1＝K_-1，1*X_0，0

K_0，1＝X_0，1

...

X_0，m-2＝K_-1，m-2*X_0，m-3

K_0，m-2＝X_0，m-2

M₀C₀＝K_-1，m-1*X_0，m-2

T_0，m-1＝((...(K_{-1，0 mod m}·X_0，0)·...)·X_0，m-2)·(M₀C₀)

n_0，m-1＝T_0，m-1

(7)

X_1，0＝K_0，0*K_0，1

K_1，0＝X_1，0

X_1，1＝K_0，1*X_1，0

K_1，1＝X_1，1

...

X_1，m-2＝K_0，m-2*X_1，m-3

K_1，m-2＝X_1，m-2

M₁C₁＝K_0，m-1*X_1，m-2

T_1，m-1＝((...(K_{0，1+p mod m}·X_1，0)·...)·X_1，m-2)·(M₁C₁)

K_1，m-1＝T_1，m-1

(8)

X_2，0＝K_1，0*K_1，2

K_2，0＝X_2，0

X_2，1＝K_1，1*X_2，0

K_2，1＝X_2，1

...

X_2，m-2＝K_1，m-2*X_2，m-3

K_2，m-2＝X_1，m-2

M₂C₂＝K_1，m-1*X_2，m-2

T_2，m-1＝((...(K_{1，2+p mod m}·X_2，0)·...)·X_2，m-2)·(M₂C₂)

K_2，m-1＝T_2，m-1

(9)

注意，(7)对应于Counter＝0、(8)对应于Counter＝1、且(9)对应于Counter＝2。此外，我们有，X_0，m-1＝M₀C₀，X_1，m-1＝M₁C₁，X_2，m-1＝M₂C₂。为了清楚起见，我们将使用(7)、(8)和(9)中的未知量的下列替换：K_-1，i＝y_i，K_0，i＝z_i，K_1，i＝u_i，K_2，i＝v_i，X_0，i＝x_i，X_1，i＝x′_i，X_2，i＝x_i″，T_0，i＝t_i，T_1，i＝t_i，′T_2，i＝t_i″。于是，由(7)、(8)和(9)构成的方程系统可以被重写为：

x₀＝y₀*y₀

z₀＝x₀

x₁＝y₁*x₀

z₁＝x₁

.........

x_m-2＝y_m-2*x_m-3

z_m-2＝x_m-2

M₀C₀＝y_m-1*x_m-2

i_m-1＝((...(y_p·x₀)·...)·x_m-2)·(M₀C₀)

z_m-1＝t_m-1

x₀′＝x₀*z₁

u₀＝x₀′

x₁′＝z₁*x₀′

u₁＝x₁′

.........

x_m-2′＝z_m-2*x_m-3′

u_m-2＝x_m-2′

M₁C₁＝z_m-1*x_m-2′

t_m-1′＝((...(y_1+p·x₀′)·...)·x_m-2′)·(M₁C₁)

u_m-1＝t_m-1′

x₀″＝u₀*u₂

u₀＝x₀″

x₁″＝u₁*x₀″

u₁＝x₁″

.........

x_m-2″＝u_m-2*x_m-3″

u_m-2＝x_m-2″

M₂C₂＝u_m-1*x_m-2″

t_m-1″＝((...(y_2+p·x₀″)·...)·x_m-3″)·(M₂C₂)

u_m-1＝t_m-1″

(10)

在未知量x₀，...，x_m-2，x₀′，...x_m-2′，x₀″，...x_m-2″，t_m-1，t_m-1′，t_m-1″分别被z₀，...z_m-2，u₀，...u_m-2，v₀，...，v_m-2，z_m-1，u_m-1，v_m-1替代之后，我们获得等效于上面系统(10)的新的方程系统，如在下表中左手侧给出的。

  方程                  解  ((10)的等效系统)  选择  计算  z₀＝y₀*y₀z₁＝y₁*z₀z₂＝y₂*z₁.........z_m-2＝y_m-2*z_m-3M₀C₀＝y_m-1*z_m-2z_m-1＝((...(y_p·z₀)·z₁)·......)·z_m-2)·{M₀C₀)u₀＝z₀*z₁u₁＝z₁*u₀u₂＝z₂*u₁.........u_m-2＝z_m-2*u_m-3M₁C₁＝z_m-1*u_m-2u_m-1＝((...(z_1+p·u₀)·u₁)·......)·u_m-2)·(M₁C₁)v₀＝u₀*u₁v₁＝u₁*v₀v₂＝u₂*v₁.........v_m-2＝u_m-2*v_m-3M₂C₂＝u_m-1*v_m-2v_m-1＝((...(u_2+p·v₀)·u₁)·......)v_n-2)·(M₂C₂)  y₀y₁y₂.........y_m-2  z₀z₁z₂.........z_m-2y_m-1z_m-1u₀u₁u₂.........u_m-2检查点v_m-1v₀v₁v₂.........v_m-2检查点v_m-1

定理3的证明在证明期间，我们将使用上表。在方程系统(10)中，存在未知的拟群运算*、4m个未知变量和3m个方程。因此，对手将不得不为一些未知变量赋予任意值，然后尝试求解该系统。之前她/他将不得不选择集合Q＝{0，1，...，15}上的一些拟群运算*。设对手为未知量Y₀，Y₁，..，Y_m-2赋值(在列‘选择’中表示)。使用变量Y₀，Y₁，...，Y_m-2的给定值，她/他能够计算(10)的所有其他变量的各值。在列‘计算’上，表示变量Z₀，...，z_m-2，y_m-1，u₀，...的各值的计算顺序(自顶向下表示)。因此，她/他首先计算Z₀＝Y₀*Y₀(Y₀具有指定值)，然后z₁＝y₁*z₀(y₁具有指定值，并且z₀被计算出)，等等，直到计算出u_m-2的值。现在，由于z_m-1和u_m-2已经被赋值，因此她/他必需检查是否满足方程M₁C₁＝z_m-1*u_m-2，在上表中用检查点(Check Point)表示这种情况。检查点使得以下面方式攻击系统更加容易。对手选择拟群并为y₀，...，y_m-2赋值。然后她/他在每个检查点检查它们是否选择正确。当答案为“否”时，她/他将选择新数据攻击(新拟群运算*和/或Y₀，...，Y_m-2新的值)。答案为“是”并不意味着数据选择正确，因为它可能是偶然发生的。对手应当收集若干连续的答案“是”，以确保系统被攻破。

对手可能选择另一策略，即，她/他不为变量Y₀，...，Ym-2赋值，而是可以为一些其他变量赋值。然而，她/他将不得不为m-1个变量赋值，并且将获得同样数量的检查点(比计数器的数量少1)。

所有可以进行的可能尝试的次数是可能的拟群运算数量(大约2¹³²)与为Y₀，...，Ym-2赋值的数量的乘积，并且它是16^m-22≥16⁶²＝2²⁴⁸。因此，为了以大于0.5的概率攻破系统EdonX，攻击者应当进行至少0.5·2380＝2190次尝试。

如上所述，EdonX是加性同步流密码，其特征是许多其组成部分的灵活性和数学可证性。我们将指出这些事实的结果。

关于EdonX的灵活性，我们提到，EdonX的初始秘密密钥的长度n可以是任何正整数，并且我们建议32≥n≥256；事实上，我们在这些约束下提出我们的算法。对我们的算法更细致的观察将示出，上述约束是表面现象，并且除了使用512个半字节，我们也可以通过使用1024、2048、128或任何其他数量的半字节，以相同的方式设计该算法。这一事实的重要性在于，EdonX可以满足从平均到极端的不同安全性准则；因此，非常多疑的用户可以使用1K(或1M)个半字节(即，4K(或4M)比特)的秘密密钥。为了更高的安全性，应当选择更长的初始秘密密钥，但计算的数量线性依赖于密钥的长度。因此，通过预测可能的攻击者以及其计算能力，可以按照需要获得的安全性来设计EdonX的软件和/或硬件。

秘密密钥的长度的灵活性允许在设计阈值安全性中使用EdonX。让我们考虑一个小例子，当密钥在3个人A、B和C之间共享时，单独一个人没有完整的密钥，并且只有他们中任两个具有完整的密钥。然后，我们取192个半字节的秘密初始密钥K＝K₀‖...‖k₁₉₁，并且我们这样分配：A获得部分K＝K₀‖...‖k₁₂₇，B获得部分K＝K₆₄‖...‖k₁₉₁，而C获得部分K＝K₀‖...‖k₆₃，K＝K₁₂₇‖...‖k₁₉₁。每个人不知道秘密密钥的64个半字节，并且存在16⁶⁴＝2²⁵⁶种可能的完成该秘密密钥的变化。也可以定义对于p阈值系统的s输出的适当安全设计。

在我们对EdonX的安全性分析中，我们假设安全性的最坏的可能情况，即，当只有初始密钥是秘密的、并且对手可以认识到选择明文/密码攻击时。如果我们假设初始拟群和初始密钥的长度也是秘密的，则系统的安全性变得强很多。因此，如果初始拟群是秘密的，而不是大约(16！)³≈2¹³²个自合痕，那么对手不得不考虑所有16阶的拟群运算，并且这些运算的数量是未知的，但大于10¹²⁰≈2⁴⁰⁰。

我们可以取初始密钥的长度n也是秘密的。在这种情况下，攻击者需要检查若干长度n＝k，n＝k+1，n＝k+2，...其中k不大(我们可以选择例如k＝5并且在某些应用中也能获得适当的安全性)。如果攻击者具有EdonX的硬件或软件实现，并且因此有可能计算长度n，那么我们可以在EdonX的计算期间添加空循环。需要以空计算花费的时间为该额外安全付出代价。

在优选实施例中EdonX的设计特性是，它工作在4比特寄存器上，并且使用16阶拟群的两个固定的查找表，其可以以仅256字节存储。连同内部存储器和算法的执行代码一起，EdonX可以以小于1Kb实现。因此，EdonX适合硬件实现为芯片卡中的嵌入式系统，具有非常少量的存储器(即，小于1KB的存储器)。

密码本质上的主要区分之一是流密码和块密码的区分。块密码对于相同的明文输入块总是给出相同的块密文，这是因为它们使用固定的变换集合。另一方面，流密码对于相同的明文序列给出不同的输出，这是因为它们使用按每次迭代变化的变换。

在本发明的另一方面中，EdonY是基于拟群串变换性质的自同步的流密码，这也是为什么它的许多性能是数学上可证明的。在优选实施例中，EdonY提供密码强大和高质量的流密码。EdonY的重要优点是其设计的灵活性，因为它可以工作在任何n比特(n＝2，3，4....)字母字母表上。其5比特字母字母表的版本适用于嵌入式系统，因为它们可以以小于2Kb存储空间实现。

EdonY是灵活的自同步的流密码，具有变换(对于每个r≥5)r元组比特的输入流的可证明的安全性。EdonY的密钥长度是可变的，并且可以是n个r-元组的任何串，出于安全的原因，我们提出n≥32。通过使用拟群串变换定义EdonY，并且其安全性基于拟群和拟群串变换的数学性质。EdonY的设计使用2^r阶拟群，并且对于r＝5，EdonY适合在嵌入式系统中硬件实现。

如上面定义的，通过使用拟群元算和拟群串变换定义EdonY。与拟群定义等效的是消去律、以及(对于每个a，b∈Q)方程a*x＝b，y*a＝b的解x，y的存在的结合。

与EdonX一样，在证明EdonY的安全性中将使用上面命题1。

作为实例，取Q＝{0，1，2，3}，并且设拟群(Q，*)及其伴生(Q，)由下表中的乘法方案给出。

  *  0 1 2 3  0123  2 1 0 33 0 1 21 2 3 00 3 2 1  0 1 2 3  0123  2 1 0 31 2 3 03 0 1 20 3 2 1

考虑串α＝1021000000000112102201010300，并且选择首项0。然后，通过变换e_0，*和d_0，*，我们将获得下面变换的串e_0，*(α)和d_0，*(α)：

e_0，*(α)＝1322130213021011211133013130

d_0，*(α)＝1302322222222101230311313302.

我们在下表中提出e-变换的四个连续应用。

  leader  1021000000000112102201010300＝α  0000  1322130213021011211133013130＝e_0，*(α)1232202331322101122203012202＝e_0，*²(α)1123211201232210111131332300＝e_0，*³(α)1003222301123221010122032021＝e_0，*⁴(α)

现在，我们对最后获得的串β＝e_0，*⁴(α)应用四次变换d_0，，如下表所示。

  leader01003222301123221010122032021＝β  000  1123211201232210111131332300＝d_0，(β)1232202331322101122203012202＝d_0，²(β)1322130213021011211133013130＝d_0，³(β)1021000000000112102201010300＝d_0，⁴(β)

可以注意到，在α中的0，1，2和3的起始分布：16/28，7/28，4/28，1/28改变成e_0，*⁴(α)中的7/28，7/28，10/28，4/28，因此分布变得更均匀。此外，我们有α＝d_0，⁴(β)＝d_o，⁴(e_0，*⁴(α))。上面命题2也成立。

可以在集合Q上定义若干拟群运算，并且设*₁，*₂，...，*_k为这些运算的序列(不必要是不同的)。我们还选择首项l₁，l₂，...，l_k∈Q(也不必要是不同的)，然后映射的组成

分别称为是Q+的E-和D-变换。由命题2，E和D是置换，并且的逆是变换其中_i是运算*_i的对应伴生。

由于D°E＝1是恒等函数，因此可以使用E作为加密函数，而使用D作为解密函数，并且我们在EdonY的优选设计中将仅使用这些函数。

EdonY是自同步的证明将是下面定理的直接结果。

定理4令$$ >>E>=>>E>>>l>1>>>l>>n>,>*>1>*>n>>>>>>$$和$$ >>D>=>>D>>>l>>n>,>>>>l>>1>,>>n>.>>1>>>>>.>>$$假设对于某个固定i有E(b₁b₂...b_k)＝c₁c₂...c_k且d≠c_i。则

D(c₁...c_i-1dc_i+1...c_k)＝b₁...b_i-1d₁...d_n+1b_i+n+1...b_k，对于一些d₁，...，d_n+1∈A，

证明：为了简单起见，我们将取n＝2，即，$$ >>E>=>>E>>>l>1>>>l>>2>,>*>1>*>2>>>>>>$$且$$ >>D>=>>D>>>l>2>>l>1>,>>>2>>>1>,>>>.>>$$等式E(b₁b₂...b_k)＝c₁c₂...c_k意味着对于一些x₁，...，x_n∈A，我们有$$ >>>e>>l>>2>,>*>2>>>>>(>>b>1>>>b>2>>.>.>.>>b>k>>)>>=>>x>1>>>x>2>>.>.>.>>x>k>>>$$和$$ >>>e>>>l>>1>,>*>1>>>>>>>(>>x>1>>>x>2>>.>.>.>>x>k>>)>>=>>c>1>>>c>2>>.>.>.>>c>k>>.>>$$于是，通过e-变换的定义，我们有

l₂*₂b₁＝x₁，x₁*₂b₂＝x₂，x₂*₂b₃＝x₃，...，x_k-1*₂b_k＝x_k，    (4)

l₁*₁x₁＝c₁，c₁*₁x₂＝c₂，c₂*₁x₃＝c₃，...，c_k-1*₁x_k＝c_k.     (5)

对于某些z_j∈A.，令D(c₁...c_i-1dc_i+1...c_k)＝z₁...z_k。于是，存在y₁，...，y_n∈A，使得$$ >>>d>>l>>1>,>>1>>>>>(>>c>1>>.>.>.>>c>>i>->1>>>d>>c>>i>+>1>>>.>.>.>>c>k>>)>>=>>y>1>>.>.>.>>y>k>>>$$并且$$ >>>d>>l>>2>,>>2>>>>>(>>y>1>>.>.>.>>y>k>>)>>=>>z>1>>.>.>.>>z>k>>.>>$$通过d-变换的定义和(5)，我们有：

y₁＝l₁₁c₁＝T₁，...，

y_i-1＝c_i-21c_i-1＝x_i-1，

y_i＝c_i-11d，

y_i+1＝d₁c_i+1，

y_i+2＝c_i+11c_i+2＝x_i+2，...，

y_k＝c_k-11c_k＝x_k.

$$ >>>>>2>,>>2>>>>(>>y>1>>>y>2>>.>.>.>0>>y>k>>)>>=>>d>>>l>2>>,>>2>>>>(>>x>i>>.>.>.>>x>>i>->1>>>>y>i>>>y>>i>+>1>>>>x>>i>+>2>>>.>.>.>>x>k>>)>>,>->->->>(>4>)>>>$$

现在，$$ >>>z>1>>>z>2>>.>.>.>>z>k>>=>>d>>l>>2>,>>2>>>>>(>>y>1>>>y>2>>.>.>.>0>>y>k>>)>>=>>d>>l>>2>,>>2>>>>>(>>x>1>>.>.>.>>x>>i>->1>>>>y>i>>>y>>i>+>1>>>>x>>i>+>2>>>.>.>.>>x>k>>)>>,>>$$(4)和(6)意味着

z₁＝l₂₂x₁＝b₁，...，

z_i-1＝x_i-22x_i-1＝b_i-1，

z_i＝x_i-12y_i，

z_i+1＝y_i2y_i+1.

z_i+2＝y_i+12x_i+2，

z_i+3＝x_i+22x_i+3＝b_i+3，...

z_k＝x_k-13x_k＝b_k.

因此，串E(b₁b₂...b_k)中的一个差错传播到串D(E(b₁b₂...b_k))中的n+1＝2+1＝3个差错。当我们将讨论EdonY的安全性时，将使用函数E的下列特性。

命题3设(Q，*)是拟群，α是Q+的任意串，并且$$ >>E>=>>E>>l>>1>.>.>.>lk>,>*>1>·>·>·>*>k>>>>.>>$$则串β＝E(α)具有各字母、各字母对、各字母的k元组的均匀分布。

在EdonY的示例性结构中，我们使用32阶拟群(在5比特字母上定义)。然而，也可以使用64、128...阶拟群，其中应当对结构进行小的修改。事实上，可以使用适当大阶的任何拟群，并且安全性成比例地取决于拟群的阶。接着，我们取Q＝{0，1，2，...，31}，并且将使用Q上的拟群运算·进行构建。我们取(Q，·)是公共拟群。EdonY的秘密密钥K用n个内部变量K_i(即K＝K₀K₁...K_n-1)存储，并且变量K_i具有范围{0，1，...，31}内的各值。K的第i个值也将用K[i](＝K_i)表示。我们取密钥K的长度为n≥32，即，密钥具有至少160比特。正如总是这样的情形，较大的密钥长度意味着较高的安全性，付出的代价是较慢的系统性能；对于拟群的阶也是如此。我们强调，这种设计的灵活性是EdonY的最好的特性之一。

EdonY算法的主要步骤如下。通过使用密钥K的初始秘密值和拟群(Q，·)，我们产生(Q，·)的未知自合痕(Q，*)。我们如下逐字母地加密输入的消息，即，明文M＝M₀M₁M₂...，其中M_i是5比特的字母。首先，我们将M乘以K的各值，并且我们获得辅助明文B＝B₀B₁B₂...，其中$$ >>>B>i>>=>>M>i>>*>>K>>i>+>[>>n>2>>]>mod>n>,>>>i>=>0,1,2>,>.>.>.>.>>$$

然后我们对B应用E-变换并且获得的串C＝E(B)＝C₀C₁C₂...是M的密文。有了密文C，通过对C施加D-变换恢复辅助明文B，即，B＝D(C)。最后，逐字母地从辅助明文B＝B₀B₁B₂...获得原始明文消息M＝M₀M₁M₂...，作为$$ >>>M>i>>=>>B>i>>/>>K>>i>+>[>>n>2>>]>mod>n>,>>>i>=>0,1,2>,>.>.>.>.>>$$

如下表中所示，EdonY加密算法和解密算法由下面过程精确地定义，其中M＝M₀M₁M₂M₃...(C＝C₀C₁C₂C₃...)是加密算法的输入(输出)串，并且C＝C₀C₁C₂C₃...(M＝M₀M₁M₂M₃...)是解密算法的输入(输出)串。在解密算法中变量X和Y是辅助的5比特变量。

与EdonX一样，初始化阶段使用从秘密初始密钥和公开拟群(Q，·)、以及工作密钥K产生的秘密工作拟群(Q，*)。现在我们假设密钥的长度n(5比特字母的)由32≤n≤510约束，这是因为我们想要将数字n表示为两个5比特字母串b₉b₈b₇b₆b₅‖b₄b₃b₂b₁b₀＝n₁‖n₂，其中b₉b₈b₇b₆b₅b₄b₃b₂b₁b₀是n的二进制表示。这里‖表示串的连接。(当然，可以以简单了当的方式为任何长度n重新设计该算法。)

初始化阶段与对EdonX使用的类似，通过下面算法描述：

  EdonY的初始化  阶段1初始密钥的输入1.输入：n-秘密密钥的初始长度(32≤n≤510)和密钥的初始秘密值K＝K₀‖K₁‖...‖K_n-1(K_i是5比特字母)阶段2填充密钥2.设置K←K_in‖n₁‖n₂其中n₁是n的最高有效5比特字母，而n₂是n的最低有效5比特字母。阶段3将密钥扩展到512个5比特字母3.设置K_ex＝K‖K‖...‖K‖K′其中K’包括K_in的头l个5比特字母，使得K_ex的总长度是512个5比特字母。阶段4用给出的32阶拟群(Q，·)变换K_ex4.For i＝0 to 511 dobeginSet leader＝K[i mod(n+2)]；K_ex←E_{leader...leader，·...·}(K_ex)；K_ex←RotateLeft(K_ex)；end；阶段5变换(Q，*)←Autotope(Q，·)5.(Q，*)←(Q，·)；For i＝0 to 511 step 8 dobeginSet row₁＝K_ex[i]；Set row₂＝K_ex[i+1]；(Q，*)←SwapRows(Q，row₁，row₂)；Set column₁＝K_ex[i+2]；Set column₂＝K_ex[i+3]；(Q，*)←SwapColumns(Q，column₁，column₂)；Setγ＝(K_ex[i+4]，K_ex[i+6])；(Q，*)←γ(Q，*)；end；阶段6设置工作密钥K(K_ex的最后n个5比特字母)6.SetK＝K₀‖K₁‖...‖K_n-1＝K_ex[512-n]‖...‖K_ex[511]

函数RotateLeft(K_ex)，SwapRows和Swapcolumns如上面关于EdonX描述的那样工作。

在初始化阶段的最后，我们获得两个对于对手是未知的工作结构。即，第一未知结构是作为原始拟群Q(·)的自合痕的工作拟群(Q，*)，并且它是大约(32！)³≈2³⁵²个自合痕之一，并且第二未知结构是替代原始初始秘密密钥K的、长度5n比特的工作密钥K。(我们强调，32阶拟群的自合痕类的具体数量是未知的。)

由定理4得出，EdonY是自同步的，这是因为在密文C中的一个差错将在恢复的明文M’中传播n+1个差错，即，原始消息M和M’将有n+1个连续字母不同。如果在C中存在长度r的差错串，则恢复的明文中将具有r+n个差错。从示例1中可以看出EdonY加密和解密工作的处理方式。

现在将讨论EdonY的优选实施例的安全性。我们假设对手能够执行有选择的明文/密文攻击，即，她/他可以选择明文，并且可以获得对应的密文。我们进一步假设秘密密钥K的初始值以及密码的内部状态：工作密钥K、工作拟群(Q，*)、以及X和T的值，对于对手是未知的，并且她/他不能物理上访问它们。我们考虑到，如果对手将能够在可行时间内重构工作密钥K以及工作拟群(Q，*)，那么她/他将攻破EdonY。

我们现在将示出，在不知道初始密钥K_in的情况下，不存在计算上可行的方法，知道工作拟群(Q，*)和工作密钥K的起始值。下面，我们给出证明：对手无法有效获得关于工作密钥K和拟群(Q，*)的部分的信息。

关于初始化阶段，按照我们的假设，秘密密钥的初始值可以具有至少32个5比特字母—即160比特的长度。按照其长度信息填充初始密钥，如上所述，目的是消除用两个不同初始密钥获得相同结果的可能性。示例性扩展密钥K_ex具有512个5比特字母的长度。它被公知的32阶拟群(Q，·)变换512次。

与EdonX一样，可以示出，在EdonY中，密钥K_ex中的各字母、各字母对、各字母三元组....的分布是均匀的。密钥K_ex的分布的均匀性揭示了工作密钥K的分布的均匀性。由于K的长度至少为32个5比特字母，因此对手可以以不大于2^-160的概率猜出工作密钥。

此外，与EdonX一样，可以示出，工作拟群(Q，*)是随机获得的初始拟群(Q，·)的自合痕。由于32阶拟群上存在大约32！³≈2³⁵²个自合痕，因此我们发现，只能以大约2^-352的概率猜出工作拟群。

至于加密/解密阶段，我们确定工作拟群(Q，*)和起始工作密钥K＝K₀K₁...K_n-1对于对手是未知的，即，恢复它是计算上不可行的。由命题3，通过使用字母的s-元组的分布，统计型攻击也是计算上不可行的。下一定理揭示通过已知的密文攻击，恢复密钥和拟群是计算上不可行的，因此只能以低于2^-1000的概率猜出它们(32阶拟群的数量是未知的，但它远大于2¹⁰⁰⁰)。

定理5给出密文C，对于Q＝{0，1，...，31}上的每个拟群运算、以及每个密钥K＝K₀K₁...K_n-1，存在明文M，使得C是它的密文。

证明：设给出C＝C₀C₁C₂...，C_i∈Q，并且让我们选择Q上的任意拟群运算*和任意密钥K＝K₀K₁...K_n-1。EdonY的加密处理可以用下表表示(注意$$ >>p>=>>$ >>n>2>>$$$是常量)。

  M₀  M₁  M₂...  M₀/K_p M₁/K_1+p  M₂/K_2+p...  K₀K₁K_n-3K_n-2  T₀T₁T_n-3T_n-2  S₀S₁S_n-3S_n-2  R₀R₁R_n-3R_n-2............  K_n-1  C₀  C₁  C₂...

由于C_i、K_j是给出的，因此我们可以如下逐步地计算表的其他变量：

K_n-1*T_n-2＝C₀T_n-2＝K_n-1C₀

K_n-2*T_n-3＝T_n-2T_n-3＝K_n-2T_n-2

..................

K₁*T₀＝T₁T₀＝K₁T₁

K₀*(M₀/K_p)＝T₀M₀/K_p＝K₀T₀

现在我们有M₀＝M₀/K_p)*K_p，即，我们求出其加密是C₀的消息M的第一个字母。使用T_i的已知值，我们可以重复前面的计算，用于得到变量S_n-2＝C₀C₁，S_n-3＝T_n-2S_n-2，...的各值，利用由C₁加密的M₁的值产生。用同样的方式，我们可以求出M₂，M₃，...的值。

另一种可以在已知密文下对EdonY实现的可能的统计型攻击，是通过产生n+1元组的密文的字典，其中n是密钥长度。我们将使用下表，以说明如何实现这种类型的攻击，并且为了简单起见，我们取n＝3。我们假设对手具有密文C₀C₁...C_iC_i+1...。

...... ...  y₁y₂＝z₁  y₂y₃＝z₂.........C_iC_i+1＝x₁ x₁x₂＝y₁C_i+1C_i+2＝x₂  x₂x₃＝y₂C_i+2C_i+3＝x₃  x₃x₄＝y₃C_i+3C_i+4＝x₄C_iC_i+1 C_i+2  C_i+3  C_i+4

于是，可以首先计算x₁，x₂，...，然后是y₁，y₂，...，最后是z₁，z₂，...。因此，值z₁，z₂，z₃，...是由密文的子串c_ic_i+1c_i+2c_i+3，c_i+1c_i+2c_i+3c_i+4，c_i+2c_i+3c_i+4c_i+5，...唯一地确定的。这揭示，C中长度n+1＝3+1＝4的子串的分布与串B＝B₀B₁B₂，...中字母的分布相等，其中$$ >>>B>i>>=>>M>i>>/>>K>>i>+>[>>n>2>>]>mod>n>,>>>,>>$$并且可以由此提取一些明文M的分布知识。

因此，对手需要产生密文字母的n+1元组的字典。在n＝3的情况下该字典将包括32⁴＝2²⁰个词，并且可以被放置在存储器中。由于我们取n≥32，因此，EdonY的字典将需要至少32³³＝2¹⁶⁵个词，并且无法通过物理定律来实现它。因此我们证明了下面的定理。

定理6对EdonY的字典型的统计攻击是计算上不可行的。

接着，我们将证明，对EdonY的选择明文/密文攻击也是计算上不可行的。假设对手可以产生任意一对明文/密文串(M，C)＝((M₀M₁...)，(C₀C₁...))。于是她/他可以从下表提取信息，其中为了简单起见我们取n＝4。

  M₀  M₁  M₂  M₃  M₄  M₅...  M₀/K₂  M₁/K₃  M₂/K₀  M₃/K₁  M₄/K₂  M₅/K₃...  K₀K₁K₂  z₀y₀x₀  z₁y₁x₁  z₂y₂x₂  z₃y₃x₃  z₄y₄x₄  z₅y₅x₅.........  K₃  C₀  C₁  C₂  C₃  C₄  C₅...

变量K_i，x_i，y_i，z_i是未知的，并且我们可以推出下面的拟群方程系统，其中Q＝{0，1，2，...31}上的运算“.”是未知的：

K₀·(M₀/K₂)＝z₀，z₀·(M₁/K₃)＝z₁，z₁·(M₂/K₀)＝z₂，...

K₁·z₀＝y₀，y₀·z₁＝y₁，y₁·z₂＝y₂，...

K₂·y₀＝x₀，x₀·y₁＝x₁，x₁·y₂＝x₂，...

K₃·x₀＝C₀，C₀·x₁＝C₁，C₁·x₂＝C₂，...

可以从上述系统的方程C₀·x₁＝C₁，C₁·x₂＝C₂，C₂·x₃＝C₃，C₃·x₄＝C₄，...中推出的信息如下。由于可以任意选择明文M，因此密文C将包含所有可能的32²对子串ab，其中(a，b)∈Q²。从方程C_i·xx＝Cx，我们知道元素C_i+1被置于拟群(Q，·)的乘法表中第C_i行和第x_i+1列。换言之，如果(Q，·)中的乘法用i j＝q_i，j表示，则$$ >>q>>c>>i>,>>x>>i>+>1>>>>>=>>C>>i>+>1>>>.>>$$由此可见，我们具有(Q，·)的乘法表的各列的完全信息。例如，我们不知道x₁的值，但我们知道$$ >>>q>>0>,>>x>1>>>>=>0>·>>x>1>>,>>q>>1>,>>x>1>>>>=>1>·>>x>1>>,>>q>>2>,>x>1>>>=>2>·>>x>1>>,>.>.>.>>q>>31>,>x>1>>>=>31>·>>x>1>>>$$的值。通过这种方式，我们可以用(Q，·)的乘法表中的完成列提取32个不同的变量x_i0，...，x_i31。为了简单，让我们取i_j＝j，并且我们有下面(Q，·)的乘法表：

  x₀  x₁  x₂... x₃₁  01231  q₀，x₀q₁，x₀q₂，x₀q₃₁，x₀  q₀，x₁q₁，x₁q₂，x₁q₃₁，x₁  q₀，x₂q₁，x₂q₂，x₂q₃₁，x₂............... q₀，x₃₁q₁，x₃₁q₂，x₃₁q₃₁，x₃₁

由于x_i是未知的，因此(Q，*)的原始乘法表是(Q，·)的乘法表的各列的置换。让我们为未知量x₀，x₁，...，x₃1赋值。然后，由上面的方程系统，我们可以一步一步地计算未知量K₃＝c₀/x₀，y₁＝x₀x₁，，y₂＝x₁x₂，y₃＝x₂x₃，...，z₂＝y₁y₂，z₃＝y₂y₃，z₄＝y₃y₄，...的唯一确定的各值。现在可以通过K₁＝M₃/(z₂z₃)，K₂＝M₄(z₃z₄)，K₃＝M₅(z₄z₅)，K₀＝M₆/(z₅z₆)，K₁＝M₇(z₆z₇)计算密钥的各值。由于存在有穷的许多变量K_i(在该简化版本中，我们只有4个，但在EdonY的优选应用中，n≥32)，因此对手有机会检查x₀，x₁，...，x₃₁的赋值是否正确。即，如果它们正确，则等式M₃/(z₂z₃)＝M₇/(z₆z₇)(＝K₁)，M₄/(z₃z₄)＝M₈/(z₇z₈)(＝K₂)，...应当满足。如果它们不满足，则对手应当对未知量x₀，x₁，...，x₃₁给出另一赋值，并且再次检查它们是否正确，等等。由于存在32！≈2¹¹⁷个不同的可能的赋值，因此我们有下面定理：

定理7在选择明文/密文进攻下，恢复EdonY的密钥或拟群运算*是计算上不可行的。

如上所示，EdonY是自同步的流密码，其特征是许多其组成部分的灵活性和数学可证性。EdonY的自同步是定理4的结果。根据该定理，如果我们有长度n的密钥，则在解密处理中，密文中的差错将产生明文的n+1个连续差错。EdonY的加密和解密算法非常简单，并且是线性复杂度的，因此EdonY可以用于安全在线通信(如果需要的话，它可以以显而易见的方式并行来获得更快的通信)。

EdonY的示例性构造使用5比特字母字母表，但如何能为m比特字母字母表重新设计加密和解密算法应当是清楚的。设计的灵活性和选择期望的密钥长度的可能性是EdonY很重要的性质。因此，EdonY也可以被用于设计阈值安全性。让我们考虑一个小实例，当密钥在3个人A、B和C之间共享时，单独一个人没有完整的密钥，并且只有他们中任两个具有完整的密钥。然后，我们取长度192的秘密初始密钥K＝K₀‖...‖K₁₉₁，并且我们这样分配：A获得部分K＝K₀‖...‖K₁₂₇，B获得部分K＝K₆₄‖...‖K₁₉₁，而C获得K＝K₀‖...‖k₆₃‖K₁₂₇‖...‖K₁₉₁。每个人不知道秘密密钥的64个5比特字母K_i，并且存在32⁶⁴＝2³²⁰种可能的完成该秘密密钥的变化。也可以定义对于p阈值系统的s输出的适当安全设计。

由于32阶拟群可以以1Kb存储，因此EdonY的优选设计允许其在嵌入式系统中的硬件实现，具有很少的存储量，即，小于2Kb存储器。

我们注意到，如果初始的32阶拟群也是秘密的话，则可以获得额外的EdonY的安全性，因为这些拟群的数量远大于21000。

在本发明的另一方面中，我们引入了新型流密码的概念：完全异步流密码(TASC)，并且演示这些密码的若干益处。如上所述，按照流密码对在使用该流密码的双方之间的通信中接收的差错的作用方式，划分流密码。如果解密的流不遭受在传输期间出现的差错(除了实际的差错字节或字节块上的差错外)，那么我们说是同步流密码。另一方面，如果差错影响了解密的流，那么我们说是异步流密码。然而，字面上定义的所有异步密码都具有自同步的性质。即，在将被错误解密的若干传送的块之后，再次建立流的正确解密。从确保正确数据流重新开始流动的角度说，自同步是非常有用的性质。然而，同步和自同步流密码都遭受监视通信线路的对手更改数据的可能攻击(遭受所谓的动态攻击)。因此，当使用如流密码(同步或自同步)的密码原语时，可能需要使用额外的机制，用于确保数据完整性。

同步密码EdonX的一般性质可以用于提供密码，该密码无法从通信过程中引入的差错恢复，但仍具有重要性质—它的安全可证明性由对同步本版应用的相同数学定理保证。尽管完全异步流密码的性质可以被看作缺点，但这样的密码事实上存在若干有用的应用：可以保证数据完整性、认证(authentication)和纠错的可证明的安全流密码。

同步流密码上面被定义为：其中独立于明文消息和独立于密文生成密钥流的密码。另一方面，自同步或异步流密码，是其中作为密钥和前面密文固定位数的函数生成密钥流的密码。

自同步流密码的加密函数可以由方程描述：

σ_i＝(c_i-t，c_i-t+1，...，c_i-1)，z_i＝g(σ_i，k)，c_i＝h(z_i，m_i)

其中，σ₀＝(c_i-t，c_i-t+1，...，c_-1)是(非秘密)初始状态，k是密钥，g是生成密钥流z_i的函数，而h是将密钥流和明文m_i组合生成密文c_i的输出函数。

相反地，完全异步流密码被定义为：其中作为中间密钥和前面明文固定位数的函数生成密钥流的密码。

完全异步流密码的加密函数可以由方程描述：

k_i+1＝f(k_i，m_i)，c_i＝h(k_i，m_i)

其中k₀是密钥的初始秘密状态，f是密钥下一状态的函数，h是将密钥和明文m_i非线性组合生成密文c_i的输出函数。

完全异步流密码的解密函数可以由方程描述：

k_i+1＝f^-1(k_i，c_i)，m_i＝h^-1(k_i，c_i)

因此，从定义，很清楚的是，自同步和完全异步流密码在如何生成密钥流的方式上不同。对于自同步流密码来说，密钥流取决于前面密文固定位数，而完全异步流密码取决于前面明文固定位数。这里，可以提出至关重要的问题：如果从随机性的角度看，明文的源具有差的特性怎么办？如果明文流具有非常低的熵(在极端情况下熵为0)怎么办。如果完全异步流密码的定义被应用到使用移位寄存器技术和S-box的经典公知流密码，则这样的完全异步流密码的结果将是完全差的流密码，它生成具有短和可预测的周期的密钥流。因此，设计高质量的完全异步流密码的主要问题在于设计这样一种流密码，其密钥流取决于前面明文固定位数，但还不落入短的周期循环，并且不生成具有差随机特性的密钥流，即使当明文位的源具有熵0时。下面我们说明完全异步流密码。

我们给出使用拟群串变换的完全异步流密码的示例性可能实现。

给出上面提供的拟群和拉丁方的定义，并且给出上面提供的合痕和自合痕的关系，可以示出，拉丁方L的各列和各行上的任何置换都可以在下面引理中归纳：

引理：与拟群(Q，*)相关联的拉丁方L_n×n的各行和各列的任何置换，导致产生新拉丁方L_n×n′，其相关联的拟群Q，*′是原始拟群(Q，*)的自合痕。

作为该引理的直接结果，我们有：对于每个n阶拟群(Q，*)，存在多达(n！)²-1个对(Q，*)的不同自合痕拟群。

给出拟群(Q，*)，可以通过下面得出集合Q上的五个新运算*^-1，^-1*，^-1(*^-1)，(^-1*)^-1，*^*：

*^-1(x，y)＝zx*z＝y

^-1*(x，y)＝zz*y＝x

^-1(*^-1)(x，y)＝z*^-1(z，y)＝xz*x＝y

(^-1*)^-1(x，y)＝z^-1*(x，z)＝yy*z＝x

*^*(x，y)＝zy*x＝2

集合Par(*)＝{*，*^-1，^-1*，^-1(*^-1)，(^-1*)^-1，*^*}被称为*的伴生的集合。然后，对于每个g∈Par(*)，(Q，g)也是拟群，并且Par(*)＝Par(g)。通常，对于乘法表示的拟群(Q，*)，分别写成，/，来代替*^-1，^-1*，并且称其左伴生和右伴生，如上所述。于是

x*y＝zy＝xzx＝z/y

于是代数(Q，*，，/)满足恒等式

x(x*y)＝y，(x*y)/y＝x，x*(xy)＝y，(x/y)*y＝x

拟群串变换的方法如上所述。

与EdonX一样，EdonZ优选地工作在半字节，即4比特变量上。这是因为它优选地使用16阶拟群(Q，*)，用于对数据流进行拟群串变换。因此，相应的拉丁方的各值用4比特表示。对于密钥K的各值也是如此。它存储在n＝64个内部变量K_i中，即，K＝K₀K₁...K_n-1。变量K_i还具有范围{0，1，...，15}中的各值。

EdonZ为初始化阶段使用K_in的初始值。通过存储在K_in中的信息，EdonZ对初始拟群(Q，*)进行变换，并且还变换K_in的各值。K的值也将随着执行流处理而改变。EdonZ也使用两个临时的4比特变量T和X。EdonZ与同步EdonX的不同在于，如何设置变量X和T的初始值、以及如何完成X的最终计算的方式。然而，在解密阶段，EdonX不使用Q(*)的左伴生，因为它是二进制加性流密码，而EdonZ需要Qpar(*)。下面是示出说明EdonZ的优选运算的表。

表1：完全异步流密码

  阶段1初始化从长度n的初始密钥K_in，获得长度64的新工作密钥K和新拟群(Q，*)←Autotope((Q，*)) 加密输入：长度n的密钥k₀和消息M输出：消息C  解密输入：长度n的密钥k₀和消息C。输出：消息M 1)X ←InputNibble；2)T←0；3)For i＝0 to n-1 doX←Q[K_i，X]；T←TX；K_i←X；4)K_n-1←T；5)Output X；6)Go to 1；  1)X_iT←InputNibble；2)temp←K_n-1；3)For i＝n-1 downto 0 doX←Qpar[temp，X]；T←TX；temp←K_i-1；K_i-1←X；4)K_n-1←T；5)Output X；6)Go to 1；

运算是对4比特变量的异或(XOR)运算。

EdonZ算法的很重要的阶段是初始化阶段。优选地，与EdonX中相同，并且并入密码算法中已经公知的技术，如填充消息、扩展和变换扩展的消息。在这种情况下，消息是秘密共享的初始密钥K_in。来自扩展和变换的密钥的信息，然后被用于变换初始给出的拟群、以及设置工作密钥K的64个半字节(256比特)的各初始值。

在初始化阶段的最后，我们得到对手不知道的两个工作结构。即，第一未知结构是原始拟群Q(·)的自合痕—工作拟群(Q，*)，并且它是大约(16！)³≈2¹³²个自合痕中的一个，并且第二未知结构是替代原始初始秘密密钥K_in的、长度4m比特(m个半字节)的工作密钥K。

作为TASC，EdonZ的另一个非常重要的性质可以用下面的定理阐述：

定理8：设M＝M₁M₂...M_μ为M到子块M_i的表示，其中，

$$ >>>M>1>>=>>m>1>>.>.>.>>m>>l>1>>>,>>M>2>>=>>m>>>l>1>>+>1>.>.>.>>m>>i>2>>>>>,>>$$

等等，并且设(K_i，C_i)＝T(K_i-1，M_i)，其中K₀＝k₀是初始密钥。于是，对于M到子块的任何表示，得到的密文C＝c₁c₂...c_l＝C₁C₂...C_μ是相同的。

通过引入消息M的长度，证明是简单了当的。

上述定理确保：即使EdonZ是流密码，我们也可以用较小的部分(块)处理输入的明文，并且不管我们在加密之前选择怎么用块表示M，最后的密文都将是相同的。因此，块可以是1个字母、4个字母、或者甚至100个字母，并且得到的密文将是相同的。

接着，我们将描述将按EdonZ的原理工作的示例，但是为了说明简单起见，我们将继续使用4阶拟群来代替使用优选的16×16拟群。此外，我们将扩展的密钥的长度缩短到长度16，代替使用长度512的扩展的密钥。初始密钥可以具有从1到15的长度，因此将用两个连接的2比特字母(范围{0，1，2，3})表示它，并且工作密钥长度将为4。

让我们假设初始拟群Q(*)与上面EdonX示例1中给出的相同，即，拟群Q(*)为：

  Q(*)  0 1 2 3  0123  2 1 0 33 0 1 21 2 3 00 3 2 1

进一步，让我们设置初始值K_in＝131。由于K_in的长度为3，并且由于数字3用两个2比特字母的表示是03，因此我们将填充K_in，并且获得K_in＝13103。然后，通过连接K_in若干次，我们将获得长度16的K_ex，即，K_ex＝1310313103131031。然后，通过用e_l*变换来变换扩展的密钥，我们将得到K_ex的最终值，其中循环取首项l为填充的K_in的各值。在下面的表中，我们总结这些变换。

  Leader  K_ex  1 3 1 0 3 1 3 1 0 3 1 3 1 0 3 1  1RotateLeft3RotateLeftRotateLeft1RotateLeft  0 3 3 0 3 3 1 0 2 0 1 2 2 1 2 23 3 0 3 3 1 0 2 0 1 2 2 1 2 2 01 2 1 2 0 1 3 2 1 0 0 0 1 1 1 32 1 2 0 1 3 2 1 0 0 0 1 1 1 3 10 1 2 3 3 1 1 0 2 1 3 1 0 3 2 23 3 2 0 3 3 3 0 0 1 2 2 1 2 3 23 2 0 3 3 3 0 0 1 2 2 1 2 3 2 3

利用K_ex的最后各值，我们将开始交替地交换初始拟群Q(*)的各行和各列，以便获得其自合痕。因此，首先我们将交换行3和2，然后是列0和3，然后再次行3和3(在这种情况下没有交换)，等等。所有这些交换的最后结果将给出下面所示的拟群Q(*)(我们通过它还可以计算其左伴生Qpar(*))。

  Q(*)  0 1 2 3  0123  3 0 2 11 2 0 30 3 1 22 1 3 0  Qpar(*)  0 1 2 3  0123  1 3 2 02 0 1 30 2 3 13 1 0 2

工作密钥K将取K_ex的最后4个字母，并且为K＝2323。现在，让我们编码一些明文流。设明文消息为M＝{0，0，1，0，2，3，0，0，1，2，0，0，1，0，0，2，0，0，0，3}。EdonZ加密的步骤如下表中所示。

        M₀        M₁          M₂           M_a...  K  X  T  K  X  T  K  X  T  K  X  T  i  0  0  0  0  1  0  0  0...  0123  2323  0211  0332  0212  3200  3111  3201  1312  1231  1311  1120  1022  Output C＝X  1  0  2  0

X＝X₀的初始值是输入流半字节的值，并且T的初始值总是0。X＝X₃的最终值实际上是输出半字节。注意，我们对于处理密钥K的新的各值有同样的情况。即，总是K＝K₀K₁K₂K₃＝X₀X₁X₂T₃，其中T₃＝X₀X₁X₂X₃。

接着，将分析EdonZ的安全性。我们将假设对手知道一个或多个(plaintext，ciphertext)对。此外，我们还将假设密钥K_in的初始值以及密码的内部状态：工作密钥K、工作拟群Q(*)和Qpar(*)、以及X和T的各值对于对手是未知的，并且她/他不能物理上访问它们。如果对手通过只知道(plaintext，ciphertext)对、将处于成功重构工作密钥K的一些部分的境地，那么我们将认为她/他已经攻破EdonX。

在第一部分的分析中，我们将示出，在不知道初始密钥K_in的情况下，不存在有效的方法来知道工作密钥K和工作拟群Q(*)的起始值。然后，我们将进一步分析同步模式中和完全异步模式中的EdonX。

为了初始化阶段的安全性，由于它优选地与EdonX中的一样，因此我们可以说EdonZ的初始化阶段是密码安全的。关于EdonZ在完全异步模式中的安全性，我们将假设工作拟群Q(*)对于对手是未知的，除非她/他对原始给出的拟群Q(*)的自合痕的整个集合进行穷尽搜索，并且该搜索是2¹³²阶的。此外，我们将假设对手不知道长度64个半字节(即，256比特)的工作密钥的初始值。

为了证明EdonZ对于选择明文攻击是安全的，让我们假设对手知道(许多对中的)一对(plaintext，ciphertext(M，C)＝((M₀M₁...)，(C₀C₁...))。分别对于K中的半字节的第i生成以及X：K_i，j和X_i，j，我们将使用与同步流密码的情况中相同的通知。

对于第一对半字节(M₀，C₀)，对手可以获得下列拟群方程系统：

K_0，0*M₀＝X_0，0

K_0，1*X_0，0＝X_0，1

K_0，2*X_0，1＝X_0，2

...

K_0，62*X_0，61＝X_0，62

K_0，63*X_0，62＝X_0，63

X_0，63＝C₀

(4)

知道C₀＝X_0，63的值，对手可以尝试求解方程K_0，63*X_0，62＝X_0，63。该方程具有两个未知变量：K_0，63和X_0，62。由于拟群运算*也是未知的，因此对手可以猜所有256个可能的解中的任一个。设置这些值作为猜测，她/他可以继续向上，对K_0，62*X_0，61＝X_0，62(也可以具有256个可能的解中的任一个)求解，等等。最后，对手将到达第一方程K_0，0*M₀＝X_0，0，由此他/她将求出K_0，0的值。

这里，我们还有这样的情形，即，对手没有其他机制来知道：他/她是否对密钥K的各值和拟群运算Q(*)进行了正确的猜测，除非他/她将所有方程运行遍(除了第一个)，这又使猜测的总数成为2²⁵²×2¹³²＝2³⁸⁴。

预期EdonZ的用途将是实现安全性协议，用于检查通过通信的公共信道接收的数据的完整性，而无需使用两种类型的加密算法：流加密和消息认证代码(或安全散列函数)。TASC的概念具有这两个性质。EdonZ作为拟群流密码，与EdonX和EdonY一起，也具有下列性质：

灵活性：对EdonZ初始化阶段更仔细的观察将会示出，它不使用最大64个半字节的初始密钥，而是直接将该数字扩大到128、1024、2048或者任何其他数量的半字节。该事实的重要性在于，EdonZ可以满足从平均到极端的不同安全性准则；因此，非常多疑的用户可以使用1K(或1M)个半字节(即，4K(或4M)比特)的秘密密钥，而不需要重新设计该算法。为了更高的安全性，应当选择更长的初始秘密密钥，但计算的数量线性依赖于密钥长度。

额外的安全性：如果我们假设初始拟群和初始密钥长度也是秘密的，那么系统的安全性变得强很多。因此，如果初始拟群是秘密的、而不是大约(16！)³≈2¹³²个自合痕，那么对手不得不考虑所有可能的16阶的拟群运算，并且这些运算的数量是未知的，但大于10¹²⁰≈2⁴⁰⁰。

与EdonX一样，EdonZ的优选设计工作在4比特寄存器上，并且使用16阶拟群的两个固定的查找表，它们可以以仅256字节存储。连同内部存储器和算法的执行代码一起，EdonZ可以以小于1Kb实现。因此，EdonZ适合硬件实现为芯片卡中的嵌入式系统，具有非常少量的存储器(即，小于1KB的存储器)。

EdonZ或类似的TASC流密码的另一个潜在的用途是在纠错算法领域。现在将讨论示例性纠错算法，优选使用TASC(如EdonZ)。该方法是用于生成随机码的核心算法，即使接收的数据的相当一部分被差错损坏，也可以相对快速地解码该随机码。我们示出，存在通过拟群串变换生成的一类码，它们几乎是随机的，并且是有效的可解码的。初始数字实验表示，这些码的性能可能明显优越于Turbo和LDPC码。例如，对于SNR＝0.0dB，速率1/2以及仅288比特的块长度，这些码给出BER＝1.7×10^-4，而对于SNR＝-0.5dB，速率1/4和仅864比特的块长度产生BER＝4.1×10^-5。

有噪信道编码定理的非结构性的证明显示，对于任何有噪信道存在良好的块码，此外，几乎所有块编码都是好的。然而，写出像香农在他的开创性著作A Mathematical Theory of Communication中证明的那样好的、清楚和实用的编码器和解码器，仍然是未解的问题。

最近认识到，两类码—即turbo码和低密度奇偶校验(LDPC)码，以非常接近香农极限的速率执行。Turbo和LDPC码基于类似的原理：受约束的随机码总体，用某些固定的参数加随机性描述，使用迭代算法或消息传递解码器解码。

本发明的另外方面提供一类具有下面两个性质的纠错码：第一，对于任意码字C，长度r的C的子串的分布是均匀的，第二，编码是迭代的，这意味着它是在具有小长度的串上定义的映射的组成部分。第一个性质确保我们的码是几乎随机的。当然，随机码的解码是NP-完全问题。然而，第二个性质确保我们的码可以高效地解码。详细描述用拟群串变换实现的这些码的实例。我们的初步数字仿真显示，提出的码的性能明显优越于对应的turbo和LDPC码。

为了描述优选码，考虑信息的源产生符号流。该流被分成长度N_block的块。可能的22^Nblock个块中的每一个由编码器映射到长度N＞N_block的码字(即，比特序列)，并且通过信道传输。因此，纠错码被定义为映射$$ >>T>:>>>\{>0,1>\}>>>N>block>>>\to >>>\{>0,1>\}>>N>>.>>$$

根据本发明的实施例的码T定义如下。设M为N_block比特的块。首先，我们添加0比特，并且产生长度N的块L。其次，我们将L重写为L＝L₁L₂...L_p，其中每个L_i是s个比特的块(我们假设N＝sp)。再次，以下列方式利用双射将块L映射到块C＝C₁C₂...C_p。

设K_1，1，k_1，2，...，K_1，n为n个初始串，每个长度s。块L被如下映射到C：

$$ >\left(\begin{array}{}>>>For\; i>=>>>1,2>,>.>.>.>p>>>>>>>>b>>i>,>0>>>=>>L>i>>>>>>for>>=>>>1,2>,>.>.>.>n>>>>>>>>b>>i>,>J>>>=>f>>(>>k>>i>,>j>>>,>>b>>i>,>J>->1>>>)>>>>>>>>>k>>i>+>1>>>,>j>=>g>>(>>k>>i>,>j>>>,>>b>>i>,>J>->1>>>)>>>>>>End>>>>>>>>>>>C>i>>=>>b>>i>,>n>>>>>>>End\; i>>>>>\end{array}\right)>->->->>(>1>)>>>$$

其中f和g是适当运算。注意(1)唯一地定义了我们的码T。

如果我们写k⁽ⁱ⁾＝k_i，1，k_i，2...k_i，n，i＝1，2...p+1，则方程(1)还定义下面两个映射。第一，映射F：Aⁿ×A^p→Aⁿ×A^p，使得(k^(p+1)，C)＝F((l)，L)，其中A＝{0，1}^l是具有长度l的所有串的集合。第二，映射G₁：Aⁿ×A¹→Aⁿ×A¹，使得对于每个i＝1，2，...，p，(k⁽ⁱ⁺¹⁾，C_i)＝G₁(k⁽ⁱ⁾，L_i)。为此，我们说，我们的码是以两种方式替代的：(i)对于每个L_i，f被迭代n次以产生C_i；和(ii)k^(I)被迭代p次以给出k^(p+I)。

在下面我们将用映射G₄≡G工作，代替G₁。为了简单起见，我们仅假设p＝4r。于是方程(1)可以重写为

$$ >\left(\begin{array}{}>>>For>>=>>>1,2>,>.>.>.>T>>>>>>>>L>>(>l>)>>>=>>L>>4>l>->3>>>>L>>4>l>->2>>>>L>>4>l>->1>>>>L>>4>l>>>>>>>For\; i>=>>>4>l>->3,4>l>->2,4>l>->2,4>l>->1,4>l>>>>>>>>b>>i>,>0>>>=>>L>i>>>>>>For>>=>>>1,2>,>.>.>.>n>>>>>>>>b>>i>,>j>>>=>f>>(>>k>>i>,>j>>>,>>b>>i>,>j>->1>>>)>>>>>>>>>K>>i>+>1>,>j>>>=>g>>(>>k>>i>,>j>>>,>>b>>i>,>j>->1>>>)>>>>>>End>>>>>>>>>>>C>i>>=>>b>>i>,>n>>>>>>>End\; i>>>>>>>>>>>C>>(>l>)>>>=>>C>>4>l>->3>>>>C>>4>l>->2>>>>C>>4>l>->1>>>>C>>4>l>>>>>>>>End>>.>>>>>\end{array}\right)>->->->>(>2>)>>>$$

方程(2)定义了映射G：Aⁿ×A⁴→Aⁿ×A⁴，使得对于l＝1，2，...，r，k^(4l+1)，C^(l)＝G(k^(4l-3)，L^(l))。

此外，我们的码具有以下性质：该码是几乎随机的，这意味着对于每个$$ >>M>\in >>>\{>0,1>\}>>>N>block>>>,>>$$当N足够大时，长度k(1≤k≤n)的子串C＝T(M)∈{0，1}^N的分布是均匀的。

例如，拟群运算和拟群串变换的执行与EdonX、EdonY和EdonZ的类似。

考虑字母表(即，有限集)A，并且用A⁺表示由A的各元素形成的所有非空词(即，有限串)的集合。A⁺的各元素将用a₁a₂...a_n表示而不是用(a₁，a₂，...，a_n)表示，其中a₁∈A。设*是集合A上的拟群运算。对于每个l∈A，我们如下定义函数e_l，*：A⁺→A⁺。设a_i∈A，α＝a₁a₂...a_n。则

e_l，*(a)＝b₁...b_nb_i+1＝b_i*a₂₊₁                                   (3)

对于每个i＝0，1，...，n-1，，其中b₀＝I。函数e_l，*称为首项为I的、基于运算*的A+的e-变换。

在集合A上可以定义若干拟群运算，并且设*₁，*₂，...，*k是这些运算的序列(不必要不同)。我们还选择首项l₁，l₂，...，l_k∈A(也不必要不同)，于是映射的组成

被称为A⁺的E-变换。函数E_k实际上是置换，它具有许多有趣的性质。下面是很重要的一个性质：

定理9考虑任意串α＝a₁a₂...a_n∈A⁺，其中a_i∈A，并且设β＝E_k(α)。如果n是足够大的整数，则对于每个l：1≤l≤k，长度l的β的子串的分布是均匀的(对于l＞k，长度l的β的子串的分布可能不是均匀的)。

该编码具有两个总体部分。在这里提供的实例中，我们现在仅描述1/2速率的设计；对不同编码速率的普遍化是直接了当的。假设要发送的消息具有形式M＝m₁m₂...m₁₈，，其中m_i是半字节(4比特字母)。在第一部分中，我们添加冗余信息，并且获得L＝L⁽¹⁾L⁽²⁾L⁽³⁾L⁽⁴⁾L⁽⁵⁾L⁽⁶⁾L⁽⁷⁾L⁽⁸⁾L⁽⁹⁾，其中L⁽¹⁾＝m₁m₂m₃0₄，L⁽²⁾＝m₄m₅m₆0₄，L⁽³⁾＝m₇m₈m₉0₄，L⁽⁴⁾＝0₄0_4.0₄0₄，L⁽⁵⁾＝m₁₀m₁₁m₁₂0₄，L⁽⁶⁾＝m₁₃m₁₄m₁₅0₄，L⁽⁷⁾＝m₁₆m₁₇m₁₈0₄，L⁽⁸⁾＝0₄0₄0₄0₄，L⁽⁹⁾＝0₄0₄0₄0₄，其中0₄是4个零的串(零半字节)。因此，每个L⁽ⁱ⁾是16比特的串。由于我们添加18个零半字节，因此码速率是1/2。这在下表中示意性示出。

表I速率1/2和1/4的码

               Ratc1/2               Ratc1/4  m₁m₄m₇0m₁₀m₁₃m₁₆00  m₂m₅m₈0m₁₁m₁₄m₁₇00  m₃m₆m₉0m₁₂m₁₅m₁₈00  000000000  m₁m₃m₅0m₆m₈m₉00  m₂m₄00m₇0000  000000000  000000000

表II

我们在实验中使用的16阶拟群

  *  0 1 2 3 4 5 6 7 8 9 a b c d e f  0123456789abcdef  3 c 2 5 1 7 b 1 0 b d e 8 4 9 a0 3 9 d 8 1 7 b 6 5 2 a c f e 41 0 c c 4 5 f 9 d 3 6 7 a 8 b 26 b f 1 9 4 c a 3 7 8 0 2 c d 54 5 0 7 6 b 9 3 f 2 a 8 d c c 1f a 1 0 e 2 4 c 7 d 3 b 5 9 8 62 f a 3 c 8 d 0 b e 9 4 6 1 5 7e 9 c a 1 d 8 6 5 f b 2 4 0 7 3c 7 6 2 a f b 5 1 0 4 9 e d 3 8b e 4 9 d 3 1 f 8 c 5 6 7 a 2 09 4 d 8 0 6 5 7 e 1 f 3 b 2 a c7 8 5 c 2 a 3 4 c 6 0 d f b 1 95 2 b 6 7 9 0 c a 8 c f 1 3 4 da 6 8 4 3 e c d 2 9 1 5 0 7 f bd 1 3 f b 0 2 8 4 a 7 e 9 5 6 e8 d 7 b 5 c a 2 9 4 e 1 3 6 0 f

在该表中，我们还示出1/4速率码。对于该1/2码，我们也说它是(72，144)码(M的长度为72，L的长度为144)。

在编码的第二部分中，我们选择f为表2中定义的拟群预算，并且g为

k_i+1，j＝b_i，j if j＝1，...n-1

k_i+1，n＝b_i，1...b_i，n

在这里提供的数字实验中，我们使用码(144，288)。这是通过下面方式进行的。让L被重写为两个子模式L＝L₁0₄的连接，其中L₁＝L⁽¹⁾L⁽²⁾...L⁽⁸⁾。于是，码(144，288)可以被描述为L＝L₁L₂0₄0₄，其中L₂＝L⁽⁹⁾L⁽¹⁰⁾...L⁽¹⁶⁾。

我们将提供用288比特的块工作、并且具有1/4速率的示例。我们在编码和解码阶段中使用的TASC算法在下表中示出。

                    表III

                完全异步流密码

 加密T(k，M)＝(k_c，C)输入：长度n的密钥k和消息M输出：消息C  解密T^-1(k，C)＝(k_c，M)输入：长度n的密钥k和消息C输出：消息M  1)X←InputNible，2)T←0；3)For i＝0 to n-1 doX←Q[K₁，X]；T←TX；K_i←X；4)K_n-1←T；5)Output X；6)Go to 1；  1)X，T←InputNible；2)temp←K_n-1；3)For i＝n-1 downto 0 doX←Qpar[temp，x]；T←TX；temp←K_i-1；K_i-1←X；4)K_n-1←T；5)Output X；6)Go to 1；

在上述算法中，符号Q[K_i，X]表示拟群运算K_i*X，而运算是异或运算。符号Qpar[temp，X]表示我们使用拟群Q(*)的左伴生拟群运算。

发送的码字是C。由于噪声，接收到不同的符号序列D＝d₁d₂...d₃₆，其中d_i是半字节。解码问题是给出D、码的定义和噪声信道的特性，推出L。我们假设该信道是二进制对称信道。设H(h₁，h₂)是返回相同长度(比特的)的两个串h₁和h₂之间的汉明距离的函数。

                表IV

我们在我们的实验中使用的拟群Q(*)的左伴生Qpar()

  0 1 2 3 4 5 6 7 8 9 a b c d e f  0123456789abcdef  8 7 2 0 d 3 b 5 c e f 9 1 a b 40 5 a 1 f 9 8 6 4 2 b 7 c 3 c d1 0 f 9 4 5 a b d 7 c e 3 8 2 6b 3 c 8 5 f 0 9 a 4 7 1 d c 6 22 f 9 7 0 1 4 3 b 6 a 5 c c d 83 2 5 a 6 c f 8 e d 1 b 7 9 4 07 d 0 3 b c c f 5 a 2 8 4 6 9 1d 4 b f c 8 7 c 6 1 3 a 2 5 0 99 8 3 e a 7 2 1 f b 4 6 0 d c 5f 6 e 5 2 a b c 8 3 d 0 9 4 1 74 9 d b 1 6 5 7 3 0 c c f 2 8 aa c 4 6 7 2 9 0 1 f 5 d 8 b 3 c6 c 1 d c 0 3 4 9 5 8 2 a f 7 bc a 8 4 3 b 1 d 2 9 0 f 6 7 5 e5 1 6 2 8 d e a 7 c 9 4 b 0 f 3e b 7 c 9 4 d 2 0 8 6 3 5 1 a f

TASCECA算法由下列算法定义：

1)定义解码候选S₀＝{(k₀，λ)}的初始集。

2)for i＝1 to μ，do

(k，md″)＝f-1(k″，D″)，m′＝m″md″，，

$$ >>>s>i>>=>\{>>(>k>,>>m>\prime >>)>>|>\exists >>(>>k>>\prime >\prime >>>,>>m>>\prime >\prime >>>)>>\in >>s>>i>->1>>>,>>D>>\prime >\prime >>>,>H>>(>>D>>\prime >\prime >>>,>>D>\prime >>)>>\le >B>,>>>$$

$$ >>>(>k>,sup>>m>d>>\prime >\prime >sup>>)>>=>>f>>->1>>>>(>>k>>\prime >\prime >>>,>>D>>\prime >\prime >>>)>>,>>m>\prime >>=>>m>>\prime >\prime >>sup>>m>d>>\prime >\prime >sup>>,>>$$其中，md″

具有与M_i^j同样的冗余信息}

3)从最后集合S_μ，选择元素(k，m′)∈S_μ。

4)从m′获得消息M。

例如，假设我们想要用速率1/4且288比特块长度的TASCECA，通过二进制对称信道发送下面消息M＝4d616365646f6e6961。为了结果更易于表示，我们将使用小的值B_max＝3。这意味着对于每个接收的4字母字D_i(即，接收的16比特字D_i)，我们将搜索遍它的所有具有小于或等于3的汉明距离的邻居。这些相近的邻居的总数是$$ >>>(>>16>0>>)>>+>>(>>16>1>>)>>+>>(>>16>2>>)>>+>>(>>16>3>>)>>=>697>.>>$$根据上面的表，我们将消息M变换成下面的消息(表示为4字母字的拼接)

M′＝4d00 6100 6000 0000 3600 5000 6000 0000 4600 f600e000 0000 6900 6000 1000 0000 0000 0000。

注意，在这种情况下4字母字的总数为L＝18。让我们选择密钥k的长度为n＝5，并且k₀的初始值为k₀＝01234。如果我们用函数T和初始值k₀变换M’，则可以立即结束编码处理。如果我们这样做，那么我们将获得下面的对

(k，C)＝T(k₀，M′)＝

(98f91，26ab c306 b63b 50df 3965 39cbb564 5521 a059 6bOf611e 2700 239f 7c7c 6973 ge53 bd9a 5f26)。

然而，我们使用方程2来迭代表示下表中的编码处理。下表中的各值可以迭代地获得，即，(k₁，C₁)＝(15b40，26ab)＝T(k₀，M₁′)＝T(01234，4d00)，于是(k₂，C₂)＝(7fd9a，c306)＝T(k₀，M₂′)＝T(15640，6100)，等等。

在下面的迭代处理表中描述解码阶段。为了节省篇幅，集合S_i的各元素以(k，M′)的形式显示，与解码阶段的步骤2中描述的稍有不同。即，示出的M’被除去了冗余，即，没有冗余的0。此外，除了集合S_i的每个元素外，还存在具有最大汉明权重B_max＝3的粗体的4字母字。该字告诉我们，对接收的4字母字D_i进行了什么改变，使得当对改变后的字应用反函数T^-1时，结果具有需要的冗余信息的结构。因此，例如对于i＝1，行″(6803e，4e)，01a8″意味着(6803e，4e00)＝T^{-1(01234，24ab01a8)}，然后行″(15b40，4d)，0200″意味着(15b40，4dOO)＝T^-1(01234，24ab0200)，依此类推。接着，对于i＝2，行″(21a69，4ed1)，0460″意味着(21a6 9，d100)＝T^{-i(6803e，c3260460)}，依此类推。

                         表V

编码消息M’的迭代处理，与密钥k_i的中间值、以及D_i的各值一起显示，所述D_i的各值由于二进制对称信道引入的某些差错，与相应的C_i不相同

  i  M₁′  C_i  k_i  D_i  Errors  123456789101112131415161718  4d0061006000000036005000600000004600f600e0000000690060001000000000000000  26abc306b63b50df396539cbb5645521a0596b0f611e2700239f7c7c69739e53bd9a5f26  15b407fd9afb47cf45dc27de3c14df20107663fd6013d58dc3f0d95ffed335f2495b3895aebd3a8f7899598f91  24abc326b6bf54df396539cba5645520a0517a4fe17e2f08b39f7d7c69739e539d9bcf66  112100111332210023

                     二进制对称信道

  i＝0  i＝1，D₁＝24ab  i＝2，D₂＝c326(01234，λ)(6803e，4e)，01a8(15b40，4d)，0200(26e23，4c)，0620(6a632，67)，1500(eca98，e0)，4802(93261，cd)，9004  (21a69，4ed1)，0400(87180，4e82)，1120(7fd9a，4d61)，0020(1028d，4d67)，0280(e575d，4d95)，2082(faa5c，4deb)，8200(f9792，4c65)，0002(bb4bb，4ca2)，8802(ec036，67c8)，0081(cb9ff，e075)，0218(1e584，cd24)，1080  i＝3，D₃＝b6bf  i＝4，D₄＝54df  i＝5，D₆＝3965(fb47c，4d616)，0084(dbbc4，67c84)，010a(f45dc，4d616)，0400  (27de3，4d61636)，0000(0bdb1，4d61603)，2009(2578f，4d6166b)，4802(a264f，4d61615)，8080  i＝6，D₆＝39cb  i＝7，D₇＝a564  i＝8，D₈＝5520  (c14df，4d616365)，0000(e1eec，4d616367)，1108(d3498，4d6166be)，9000(95052，4d6166b2)，c010(20107，4d6163656)，1000(663fd，4d6163656)，0001  i＝9，D₉＝a051  i＝10，D₁₀＝7a4f  i＝11，D₁₁＝e17e(6O13d，4d6l6365646)，0008(176de，4d616365643)，0822(06677，4d616365696)，4001(ce416，4d616365655)，8c00(feae4，4d616365688)，9200  (58dc3，4d616365646f6)，1140(72a88，4d6163656469c)，4110(b8f4f，4d61636564616)，c008(b443b，4d616365643e9)，002c(21187，4d616365643e2)，0a02(8ce41，4d61636569644)，0040(7b86c，4d61636569684)，0181(34856，4d616365696f9)，1003(50597，4d616365696f3)，1801(66058，4d616365696d2)，2102(f4590，4d61636565528)，0c08(3c471，4d616365688e7)，0002(72831，4d61636568855)，0002(f1e2c，4d616365655280)，2240(47c11，4d61636568855c)，8001(f0d95，4d616365646f6e)，8060  i＝12，D₁₂＝2f08  i＝13，D₁₃＝b39f  i＝14，D₁₄＝7d7c(ffed3，4d616365646f6e)，0808  (b51ef，4d616365646f6e04)，0841(35f24，4d616365646f6e69)，9000  (f9f1c，4d616365646f6e041)，4008(95b38，4d616365646f6e696)，9000(b5a55，4d616365646f6e69e)，1028  i＝15，D₁₅＝6973  i＝16，D₁₆＝9e53  i＝17，D₁₇＝9d9b  (4d0e6，4d616365646f6e0419)，8012(95aeb，4d616365646f6e6961)，0000(c08bc，4d616365646f6e696a)，c010(d3a8f，4d616365646f6e6961)，0000(78995，4d616365646f6e6961)，2001  i＝18，D₁₈＝cf66  (98f91，4d616365646f6e6961)，9040

在解码的处理中，我们迭代解码4元组D_i＝d_jd_j+₁d_j+₂d_j+3，j＝1+4(i-1)，i＝1，2，...9，并且检查0₄是否是相对应的L_i的最后半字节，或者L₄，L₈，L₉是否仅是零的串。然而，由于D_i＝d_jd_j+₁d_j+2d_j+3，j＝1+4(i-1)，i＝1，2，...9，在一些比特上与相应的码字C_i＝c_jc_j+₁c_j+2c_j+3不同，因此在解码处理中，我们对离D_i的距离小于B比特的每个4元组解码。在一些字中：码字的解码是搜索这样的D_is的过程：即，D_is在解码时，最后半字节是4个0的串、并且L₄，L₈，L₉为仅是0的串。

很明显，该步骤是解码器的非常重要的迭代部分。在解码的处理中，所有可能的候选的集合S中的各元素数量可能急剧增长，因此使该数量受到控制是很重要的。如上面速率码表中所示，在L中放入冗余数据就是用于此目的，但也可以应用用于消除最不可能的候选的其他技术。在迭代解码的最后，最终S中的元素数量降低到1，意味着找到和纠正了所有差错。解码器还具有下列性质：如果从候选的集合S中由于某种原因消除了正确的候选，则进一步解码处理的若干步骤将最终产生空集合S，这表明做出了一些错误的解码判决。

此外，假设集合S中的元素数量受到控制，我们可以计算解码的BER的上界。即，对于具有差错概率p的二进制对称信道，假设接收的4元组D_i的最大汉明距离不大于B＝B_max，并且设K＝N/16为长度N的码字中的4元组的数量，则BER的上界可以通过下面表达式计算：

$$ >>BER>\le >>\Sigma >>i>=>1>>K>\left(\begin{array}{}>>>K>>>>>i>>>\end{array}\right)sup>>p>B>isup>>>>(>1>->>p>B>>)>>>K>->i>>>>$$

其中$$ >>>\rho >B>>=>>\Sigma >>i>>>>B>max>>>>>(>>16>i>>)>>>p>i>>>>(>1>->p>)>>>16>->i>>>>$$是在16比特的串中出现多于B_max个差错的概率。

我们对该码的实验显示出相对于Turbo和LDPC码的重大改进。例如，对于SNR＝0.0dB、速率1/2和仅288比特的块长度，优选的码给出BER＝1.7×10^-4，而对于SNR＝-0.5dB、速率1/4和仅864比特的块长度，产生BER＝4.1×10^-5。这些数字实验显示，在此时它的潜力远大于当前最好的纠错码的能力。

本发明的另一个方面提供伪随机数生成器(PRNG)的改进器，使得改进后的PRNG具有几乎不可测的周期、各字母、各字母对、各字母三元组(等等)的均匀分布，并且通过所有的随机性的统计测试。PRNG的优选改进器是通过使用拟群串变换设计的，并且其特性是数学上可证明的。它非常灵活：输入/输出串可以是2比特字母、4比特字母、字节、2比特字母，等等。此外，它的复杂度是线性的，在其2比特和4比特实现中需要不超过1Kb存储器，因此也适合在嵌入式系统中使用。

存在对伪随机数生成器和/或无偏的随机性的物理源上的(伪)随机数生成器(PRNG)构造的若干改进器。对PRNG的所有改进器的一般特性是，它们不使用源生成的每比特信息，或者它们的算法是指数性质的，因此应当涉及逼近(approximation)。在提出的PRNG的改进器的算法中，它们中的一些可以用计算上有效的方式实现，而对于它们中的另一些，提供对期望的性质的数学证明。

根据本发明的实施例，基于拟群串变换提供PRNG的改进器。优选的改进器使用信息源产生的每比特信息。此外，优选的改进器能够从只产生一个信号(例如，0)的固定源产生(高质量的)伪随机数序列。优选算法的复杂度是线性的，即，将由长度n的输入串以复杂度O(n)产生长度n的输出串。这意味着可以设计在计算上非常有效的改进器的软件和硬件实现。优选算法非常灵活：对于其字母包括2比特、4比特、字节、2字节的串，可以使用相同的设计，并且一般地，它可以为n比特字母字母表设计(n≥2)。

上面提供了拟群的定义。此外如上面提供的，拟群的定义揭示了消去律x*y＝x*zy＝z，y*x＝z*xy＝z，并且方程a*x＝b，y*a＝b对于每个a，b∈Q具有唯一解。如果(Q，*)是拟群，则*称为拟群运算。

可以定义若干拟群串变换，并且下面将说明我们感兴趣的那些。考虑字母表(即，有限集)A，并且用A⁺表示A的各元素形成的所有非空字(即，有限串)的集合。A⁺的元素将用a₁a₂...a_n表示而不用(a₁，a₂，...，a_n)表示，其中a₁∈A。设*是集合A上的拟群运算。对于每个l∈A，我们如下定义两个函数e_l，*，e_l，*′，：A⁺→A⁺。设a_i∈A，α＝a₁a₂...a_n。则

e_l，*(α)＝b₁...b_nb_i+1＝b_i*ax

e_l，*′(α)＝b₁...b_nb_i+1＝a_i+1*b_i。

对于每个i＝0，1，...，n-1，其中b₀＝l。函数e_l，*和e_l，*′称为首项为l的、基于运算*的A+的e-和e’-变换。下表中示出e-和e’-变换的图形表示。

图1：e-变换的图形表示

图2：e’-变换的图形表示

作为示例，取A＝{0，1，2，3}，并且设拟群(A，*)由下面示出的乘法方案给出。

考虑串α＝1021000000000112102201010300，并且选择首项0。然后，通过e_0，*和e_0，*′变换，我们将获得下面变换的串

e_0，*(α)＝1 322 1 302 1 302 1 0 1 1 2 1 1 1 330 1 3 1 30

以及

e_0，*′(α)＝3 3 0 3 3 3 3 3 3 3 3 332 1 2 1 1 233 2 0 3 3 1 1 1。

  0 1 2 3  0123  2 1 0 33 0 1 21 2 3 00 3 2 1

图3：拟群(A，*)

  1021000000000112102201010300＝α  0000  1322130213021011211133013130＝e_0，*(α)1232202331322101122203012202＝e_0，*³(α)1123211201232210111131332300＝e^0，*3(α)1003222301123221010122032021＝e_0，*⁴(α)1021000000000112102201010300＝α  0000  3303333333333212112332033111＝e_0，*′¹(α)0022222222222323212223313210＝e_0，*′²(α)2012301230123122323013100102＝e_0，*′³(α)1101332311013230013322111023＝e_0，*＇⁴(α)

图4：连续的e-和e’-变换

我们提供上表中的这些变换的四个连续应用。可以注意到，在α中的0，1，2和3的起始分布：16/28，7/28，4/28，1/28改变成e_0，*4(α)中的7/28，7/28，10/28，4/28以及e_0，*′⁴(α)中的5/28，10/28，5/28，8/28，因此分布变得更均匀。

可以在集合A上定义若干拟群运算，并且设*₁，*₂，...，*_k为这些运算的序列(不必要不同)。我们还选择首项l₁，l₂，...，l_k∈A(也不必要不同)，然后映射的组成

分别称为是A⁺的E-和E’-变换。函数E_k和E’_k具有许多有趣的性质，对我们来说最重要的特性如下：

定理10变换E_k和E’_k是A⁺的置换。

定理11考虑任意串α＝a₁a₂...a_n∈A⁺，其中a_i∈A，并且设β＝E_k(α)β＝E_k′(α)如果n是足够大的整数，则对于每个l：1≤l≤k，长度l的β和β’的子串的分布是均匀的(我们注意到，对于l＞k，长度l的β和β’的子串的分布可能不是均匀的)。

如果p是使得对于每个i≥0有a_i+1a_i+2...a_i+p＝a_i+p+1a_i+p+2...a_i+2p的最小的正整数，那么我们说串α＝a₁a₂...a_n∈A⁺(其中a_i∈A)具有周期p。设α，β，β′与定理10中相同，并且假设变换E_k和E’_k的首项a使得a*a≠a。于是我们有下面性质：

定理12串β和β’的周期至少按k线性增长。

我们应当注意，周期的增长取决于拟群运算，并且对于它们中的一些来说，它是指数的，即，如果α具有周期p，则β＝E_k(α)和β′＝E_k′(α)可以具有大于p^2k的周期。我们将更详细地对此讨论。

在下面的示例中，我们通常将仅使用E-变换，因为按照对称性，结果对E’-变换也将成立。

专门描述拟群PRNG改进器，假设我们有离散信息源SI，其从A⁺产生串，即，SI的字母表是A，其中A＝{a₀，a₁，...，a_s-1}是有限字母表。我们可以考虑，从SI输出的串是伪随机数，即，我们认为A的各元素是数字基(base)s中的各位，并且SI是PRNG。然后我们因此基于相应的E-和E’-变换，定义PRNG改进器的两个算法。我们称它们为E-算法和E’-算法。在算法中，我们使用若干内部变量b，L₁，...，L_n，算法的输入是拟群的阶s、s阶的拟群A，*、固定元素l∈A(首项)、给出变换e_l，*和e_l，*′的应用数量的整数n、以及从具有字母表A的一些信息源SI获得的伪随机串b₀，b₁，b₂，b₃，...。输出是改进的伪随机串。

E-算法阶段I初始化1.选择正整数s≥4；2.选择指数拟群(A，*)；3.设置正整数n；4.设置首项l，A的固定元素，使得l*l≠l；阶段II从源SI获得的伪随机串b₀b₁b₂b₃...，b_i∈A的变换5.For i＝1 to n do L_i←l；6.dob←RandomElement(SI)；L₁←L₁*b；For i＝2 to n do L_i←L_i*L_i-1；Output：L_n；loop；

E’-算法仅在步骤6中与E-算法不同：

E’-算法6′.dob ←RandomElement(SI)；L₁←b*L₁；For i＝2 to n do L_i←L_i-1*L_i；Output：L_n；loop；

我们需要说明指数拟群的含义，并且给出数s和n的合适的参数。事实上，数s某种程度上由信息源SI预定义，但不完全是。设SI的字母表为ASCII，包括所有8比特字母。于是我们有下面对A的选择：A＝{0，1，2，3}，A＝{0，1，2，...，7}，A＝{0，1，...，15}，A＝{0，1，...，31}，A＝{0，1，...，63}，A＝{0，1，2，...，127}。即，SI的输出串被认为是比特串，然后这些比特被分成两组、三组、等等。我们在这种情况下可以考虑，具有两字节字母、三字节字母等的字母表，但512或更高阶的拟群需要许多存储空间，并且通常计算较慢，这是不愿意看到的。数n应当按照‘对于较小的s选较大的n’的原则来选择，并且其选择取决于信息源SI。因此，如果SI给出恒定输出(例如，0)，则根据我们的经验，一条规则可以是′ns≥512&n＞8′。如果SI产生一种随机序列，则n可以小，有时n＝1就足够了。例如，在Pascal中使用的PRNG未通过电池中的统计测试[diehard]，但仅在应用e-变换一次以后它就通过它们全部。当然，对于较大的s，获得较好的输出伪随机串，但它应当由可用性能(算法速度、可存取的存储器等)来优化。所有提到的性质都基于定理11和定理12以及我们通过几百次实验获得的经验。

考虑了用于定义和改进PRNG的拟群的可能。从现有的研究可以得出结论，有限拟群的类可以分成两个不相交的子类：线性(或分形(fractal))拟群的类和指数(或均匀)拟群的类。存在若干划分这两个类的特性，并且对于我们的目的来说，这一个是很重要的。给出有限集Q＝{q₀，q₁，...q_s-1}，设(Q，*)是拟群，并且让我们从周期n的无限(即，足够长)的串α＝q₀q₁...q_s-1q₀q₁...q_n-1q₀q₁...q_s-1...开始。对α应用r次e_l，*变换，并且用α_r表示获得的串。然后，如果串α_r的周期是r的线性函数，则说拟群(Q，*)是线性的。在相反情况下，串α_r的周期是指数函数nr(对于某常数n：1＜n≤s)，则说拟群(Q，*)是指数的。数n称为指数拟群(Q，*)的增长(growth)周期(是否只存在两种有限拟群—线性和指数，这是个未解的问题)。

通过在Dimitrova，V.，Markovski J.：On quasigroup pseudo random sequencegenerator，Proc.of the 1-st Balkan Conference in Informatics，YManolopoulosand P.Spirakis eds.，21-23Nov.2004，Thessaloniki，pp.393-401中提供的统计结果显示，当拟群的阶增加时，线性拟群的百分比降低。此外，可以确定，‘坏’拟群(即，具有增长周期s≤2的线性拟群和指数拟群)的百分比随着拟群的阶指数下降。下表示出根据Dimitrova等人的对于4、5、6、7、8、9和10阶拟群的‘坏’拟群的百分比。

  拟群阶  4  5  6  7  8  9  10  ‘坏’拟群的百分比  34.7  1.1  1.0  0.6  0.38  0.25  0.15

我们需要注意，上述结果不是非常精确(除了4阶拟群获得了完整的分类外)，因为该结论是在仅应用7次e-变换时做出的。即，可能发生某些拟群在多于7次应用之后获得≥2的增长周期。

我们在106个随机选择的16阶拟群上进行下面实验。我们在对下面具有周期16的周期串：0，1，2，...，14，15，0，1，2，...，14，15，...，0，1，2，...，14，15，...应用5次每个拟群的e_l，*变换之后，计数增长周期。首项l的值不影响结果。获得的增长周期的分布在下表中提供。

  常数k 具有周期p＝2^k的拟群数量  常数k 具有周期p＝2^k的拟群数量  0.00≤k＜0.25  4  2.00≤k＜2.25 79834  0.25≤k＜0.50  23  2.25≤k＜2.50 128836  0.50≤k＜0.75  194  2.50≤k＜2.75 174974  0.75≤k＜1.00  686  2.75≤k＜3.00 199040  1.00≤k＜1.25  2517  3.00≤k＜3.25 175848  1.25≤k＜1.50  7918  3.25≤k＜3.50 119279  1.50≤k＜1.75  18530  3.50≤k＜3.75 45103  1.75≤k＜2.00  42687  3.75≤k≤4.00 4527

从该表可以看出，在应用5次e-变换之后，907个拟群具有＜2的增长周期。我们在对这些拟群的每一个应用6次之后，计数增长周期，并且我们得到，它们中只有15个具有＜2的增长周期。在应用7次之后，仅有1个拟群具有＜2的增长周期，但在应用10次e-变换之后，它获得2的增长周期。该实验显示，随机找到16阶的线性拟群并不容易。

优选实施例的PRNG改进器可以软件或硬件非常有效地实现。它们是线性复杂度的，并且如果使用≤16阶的拟群，则可以安装在小于1Kb的工作存储器中。因此，它们可以用在嵌入式系统中。算法的性能基于定理10、11和12。通过定理10，我们有E-算法和E’-算法是单射(injective)的，意味着从信息源SI获得的不同输入串将产生不同的输出串。定理11允许获得均匀输出随机串，其中各字母、各字母对、各字母三元组等的分布是均匀的。最后，定理12和统计结果示出，输出随机串的周期可以如我们期望的那样大(事实上它潜在地是无限的)。通过使用适合的(指数)拟群和参数s的适当选择，可以容易地获得输出随机串的期望特性。很明显，上述性质不足以获得好的伪随机串。我们通过使用可用的统计测试(Diehard)检查获得的伪随机串，并且它们通过了所有测试。

现在将提供定理11和12的证明。关于定理11，为了简化证明中的技术性，我们取字母表A为{0，...，s-1}，其中0，1，...，s-1(s＞1)是整数，并且*是A上的拟群运算。我们如下定义随机变量{Y_n|n≥1}的序列。让我们有字母0，1，...，s-1的概率分布(q₀，q₁，...，q_s-1)，使得对于每个i＝0，1，...，s-1有qi＞0且$$ >>>\Sigma >>i>=>0>>>s>->1>>>>q>i>>=>1>.>>$$考虑e-变换E并且设γ＝E(β)，其中β＝b₁...b_k，γ＝c₁...c_k∈A⁺(b_i，c_i∈A)。我们假设串β是任意选择的。于是我们用{Y_m＝i}表示随机事件—串γ中的第m字母恰好为i。由(1)给出的e-变换的定义揭示

P(Y_m＝j|Y_m-1＝j_m-1，...，Y₁＝j₁)＝P(Y_m＝j|Y_m-1＝j_m-1)，

这是因为γ中的第m成员的出现仅依赖于γ中的第(m-1)成员，而不依赖于第(m-2)，...，第1成员。因此，序列{Y_m|m≥1}是马尔可夫链，并且我们将其称为拟群马尔可夫链(qMc)。让p_ij表示串γ中字母j紧接着给定字母i出现的概率，即，

p_ij＝P(Y_m＝j|Y_m-1＝i)，i，j＝0，1，...，s-1

qMc的定义揭示了p_ij不依赖于m，因此我们有，qMc是齐次(homogeneous)马尔可夫链。p_ij的概率可以如下确定。设i，j，t∈A且设i*t＝j为拟群(A，*)中的真等式(true equality)。则

P(Y_m＝j|Y_m-1＝i)＝q_t，

因为方程i*t＝j对于未知的x具有唯一解。因此，对于每个i，j＝0，...，s-1，p_ij＞0，即，qMc的变换矩阵II＝(pij)是正则(regular)的。显然，如任何马尔可夫链中那样，$$ >>>\Sigma >>j>=>0>>>s>->1>>>>p>ij>>=>1>.>>$$但对于qMc，我们也有

$$ >>>\Sigma >>i>=>0>>>s>->1>>>>p>ij>>=>>\Sigma >>i>\in >A>\; >>q>i>>=>1>>$$

即，qMc的变换矩阵II是双随机(doubly stochastic)的。

II的正则性揭示，存在唯一固定的概率向量p＝(p₀，...，p_s-1)使得pII＝p，并且p的所有分量都是正的。此外，由于II还是双随机矩阵，因此可以检查是pII＝p的解。因此，$$ >>>p>i>>=>>1>s>>>(>i>=>0>,>.>.>.>,>s>->1>)>>.>>$$这样，我们有下列引理：

引理设β＝b₁b₂...b_k∈A⁺且γ＝E(1)(β)。则对于每个i∈A以及每个m＝1，2，...，k，字母i出现在串γ＝c₁...c_k的第m位置的概率大约是

该引理告诉我们，在通过qsp从足够大的串β获得的串γ＝E(β)中，字母的分布是均匀的。我们通过考虑串γ＝Eⁿ(β)(β＝b₁b₂...b_k∈A⁺)的子串c_i+1...c_i+l的分布来进行讨论，其中l≥1是固定的，并且i∈{0，1，...，k-l}。照例，我们说c_i+1...c_i+l是长度l的γ的子串。通过下面定义随机变量的序列$$ >>\{sup>>Z>m>>(>n>)>sup>>|>m>\ge >1>\}>>$$

$$ >sup>>Z>m>>(>n>)>sup>>=>t>\iff >\begin{array}{}>>sup>>Y>m>>(>n>)>sup>>=sup>>i>m>>(>n>)>sup>>,sup>>Y>>m>+>1>>>(>n>)>sup>>=sup>>i>>m>+>1>>>(>n>)>sup>>,>.>.>.>,sup>>Y>>m>+>l>->1>>>(>n>)>sup>>=sup>>i>>m>+>l>+>1>>>(>n>)>sup>>,>>>>>t>=sup>>i>m>>(>n>)>sup>>>s>>l>->1>>>+sup>>i>>m>+>1>>>(>n>)>sup>>>s>>l>->2>>>+>·>·>·>+sup>>i>>m>+>l>->2>>>(>n>)>sup>>s>+sup>>i>>m>+>l>->1>>>(>n>)>sup>>>>\; >>\end{array}$$

其中这里以及下面上标(n)表示这一事实，即，我们考虑通过en类型的变换从串β获得的串$$ >>\gamma >=sup>>i>1>>(>n>)>sup>sup>>i>2>>(>n>)>sup>>.>.>.sup>>i>k>>(>n>)>sup>>>$$的子串。因此，Y_m⁽ⁿ⁾仅是如前面定义的随机变量Y_m。映射是从A^l到{0，1，...，s^l-1}的双射，从而序列$$ >>\{sup>>Z>m>>(>n>)>sup>>|>m>\ge >1>\}>>$$被明确定义。序列$$ >>\{sup>>Z>m>>(>n>)>sup>>|>m>\ge >1>\}>>$$也是马尔可夫链(n-qMc)，因为γ中l个连续符号的子串i_m⁽ⁿ⁾i_m+1⁽ⁿ⁾...i_m+l-1⁽ⁿ⁾的出现仅依赖于前面的子串i_m-1⁽ⁿ⁾i_m⁽ⁿ⁾i_m+1⁽ⁿ⁾...i_m+l-2⁽ⁿ⁾。用t和t’表示下面的数：

$$ >>t>=sup>>i>m>>(>n>)>sup>>>s>>l>->1>>>+sup>>i>>m>+>1>>>(>n>)>sup>>>s>>l>->2>>>+>·>·>·>+sup>>i>>m>+>l>->2>>>(>n>)>sup>>s>+sup>>i>>m>+>l>->1>>>(>n>)>sup>>,>>$$

$$ >>>t>\prime >>=sup>>i>>m>->1>>>(>n>)>sup>>>s>>l>->1>>>+>>sup>>>i>\prime >>m>>(>n>)>sup>>s>>>l>->2>>>+>·>·>·>+sup>>>i>\prime >>>m>+>l>->3>>>(>n>)>sup>>s>+sup>>>i>\prime >>>m>+>l>->2>>>(>n>)>sup>>.>>$$

设Pt′t是在某一串γ＝E⁽ⁿ⁾(β)中，γ的子串i_m⁽ⁿ⁾...i_m+l-2⁽ⁿ⁾i_m+l-1⁽ⁿ⁾(从第m到第m+l-1位置)出现在γ的给定子串i_m-1⁽ⁿ⁾i′_m⁽ⁿ⁾......i′_m+l-3⁽ⁿ⁾i′_m+l-2⁽ⁿ⁾(从第m-1到第m+l-2位置)之后(带重叠)的概率。很显然，对于某j ∈{m，m-1，...，m+l-2}，如果$$ >sup>>i>j>>(>n>)>sup>>\ne sup>>>i>\prime >>j>>(>n>)>sup>>,>>$$则Pt′t＝0。在相反的情况下(当l-1个字母重叠时)我们有：

$$ >>>p>>t>\prime >t>>>=>P>>(sup>>Z>m>>(>n>)>sup>>=>t>|sup>>Z>>m>->1>>>(>n>)>sup>>=>>t>\prime >>)>>>$$

$$ >>=>P>>(sup>>Y>m>>(>n>)>sup>>=sup>>i>m>>(>n>)>sup>>,>.>.>.>,sup>>Y>>m>+>l>->1>>>(>n>)>sup>>=sup>>i>>m>+>l>->1>>>(>n>)>sup>>|sup>>Y>>m>->1>>>(>n>)>sup>>=sup>>i>>m>->1>>>(>n>)>sup>>,sup>>Y>m>>(>n>)>sup>>=sup>>i>m>>(>n>)>sup>>,>.>.>.>>>$$

$$ >>.>.>.>,sup>>Y>>m>+>l>->2>>>(>n>)>sup>>=sup>>i>>m>+>l>->2>>>(>n>)>sup>>)>>$$

$$ >>=>P>>(sup>>\cap >>j>=>0>>>l>->1>sup>>>(sup>>Y>>m>+>j>>>(>n>)>sup>>=sup>>i>>m>+>i>>>(>n>)>sup>>)>>|sup>>\cap >>j>=>0>>>l>->1>sup>>>(sup>>Y>>m>+>j>->1>>>(>n>)>sup>>=sup>>i>>m>+>j>->1>>>(>n>)>sup>>)>>)>>>$$

$$ >>=>>>P>>(sup>>\cap >>j>=>0>>lsup>>>(sup>>Y>>m>+>j>->1>>>(>n>)>sup>>=sup>>i>>m>+>j>->1>>>(>n>)>sup>>)>>)>>>>P>>(sup>>\cap >>j>=>0>>>l>->1>sup>>>(sup>>Y>>m>+>j>->1>>>(>n>)>sup>>=sup>>i>>m>+>j>->1>>>(>n>)>sup>>)>>)>>>>>>$$

$$ >>=>>>P>>(sup>>\cap >>j>=>0>>>l>->1>sup>>>(sup>>Y>>m>+>j>>>(>n>)>sup>>=sup>>i>>m>+>j>>>(>n>)>sup>>)>>)>|sup>>Y>>m>->1>>>(>n>)>sup>>=sup>>i>>m>->1>>>(>n>)>sup>>)>>>>P>>(sup>>\cap >>j>=>0>>>l>->2>sup>>>(sup>>Y>>m>+>j>>>(>n>)>sup>>=sup>>i>>m>+>j>>>(>n>)>sup>>)>>)>|sup>>Y>>m>->1>>>(>n>)>sup>>=sup>>i>>m>->1>>>(>n>)>sup>>)>>>>>>$$

通过使用拟群变换的数量n的归纳，我们将证明定理11，即，我们将证明其下面的版本：

设1≤l≤n，β＝b₁b₂...b_k∈A⁺且γ＝E⁽ⁿ⁾(β)。则长度l的γ的子串的分布是均匀的。

回忆符号A＝{0，...，s-1}。对于n＝1，我们有引理，并且设n＝r+1，r≥1。通过归纳性假说，对于γ′＝E^r(β)中l≤r的长度l的子串的分布是均匀的。首先，我们假设l≤r，并且我们考虑$$ >>\gamma >=>>E>>r>+>1>>>>(>\beta >)>>=sup>>i>1>>(>r>+>1>)>sup>>.>.sup>>>.>i>>k>>(>r>+>1>)>sup>>>$$的长度l的子串。我们取*_1，...，*_r+1为A上的拟群运算，并且回忆E^(r+1)＝E_r+1°E^(r)＝E_r+1°E_r°E^(r-1)＝....。由于(A，^*_r+1)是拟群，因此方程$$ >sup>>i>>j>->1>>*>>r>+>1>>>>>(>r>+>1>)>sup>>x>=sup>>i>j>>(>r>+>l>)>sup>>>$$对于每个j，2≤j≥k，具有x的唯一解，并且我们用$$ >>x>=sup>>i>j>>(>r>)>sup>>>$$表示它。用i₁^(r)表示方程$$ >>>a>>r>+>1>*>r>+>1>>>x>=sup>>i>1>>(>r>+>1>)>sup>>>$$的解，其中a_r+1∈A是E_r+1的定义中的固定元素。通过这种方式，而不是用γ的子串i_m^(r+1)i_m+1^(r+1)...i_m+d^(r+1)运算，我们可以考虑γ′＝E^(r)(β)的子串i_m^(r)i_m+1^(r)...i_m+d^(r)，对于任何d，0≤d≤k-m。拟群方程中的解的唯一性揭示我们也有

$$ >>P>>(sup>>\cap >>j>=>0>>dsup>>>(sup>>Y>>m>+>j>>>(>r>+>1>)>sup>>=sup>>i>>m>+>j>>>(>r>+>1>)>sup>>)>>)>|sup>>Y>>m>->1>>>(>r>+>1>)>sup>>=sup>>i>>m>->1>>>(>r>+>1>)>sup>>)>=>P>>(sup>>\cap >>j>=>0>>dsup>>>(sup>>Y>>m>+>j>>>(>r>)>sup>>=sup>>i>>m>+>j>>>(>r>)>sup>>)>>>)>>->->->>(>4>)>>>$$

这里，$$ >sup>>i>0>>(>r>+>1>)>sup>>=>>a>>r>+>1>>>.>>$$于是，由(3)和(4)(对于d＝l-1，d＝l-2和n＝r+1)，我们有

$$ >>>p>>>t>\prime >>t>>>=>>>P>>(sup>>\cap >>j>=>0>>>l>->1>sup>>>(sup>>Y>>m>+>j>>>(>r>)>sup>>=sup>>i>>m>+>j>>>(>r>)>sup>>)>>)>>>>P>>(sup>>\cap >>j>=>0>>>l>->2>sup>>>(sup>>Y>>m>+>j>>>(>r>)>sup>>=sup>>i>>m>+>j>>>(>r>)>sup>>)>>)>>>>>$$

其中1≤r。通过归纳性假说，我们有$$ >>p>>(sup>>\cap >>j>=>0>>>l>->1>sup>>>(sup>>Y>>m>+>j>>>(>r>)>sup>>=sup>>i>>m>+>j>>>(>r>)>sup>>)>>)>>=>>1>>s>l>>>,>>$$$$ >>P>>(sup>>\cap >>J>=>0>>>l>->2>sup>>>(sup>>Y>>m>+>J>>>(>r>)>sup>>=sup>>i>>m>+>J>>>(>r>)>sup>>)>>)>>=>>1>>s>>l>->1>>>>,>>$$即，$$ >>p>>t>\prime >>t>=>>1>s>>.>>$$因此，对于概率Pt′t，我们有

$$ >>>>p>>>t>\prime >>t>>>=>\begin{array}{}>>>0>>>ifsup>>>i>\prime >>j>>(>r>+>1>)>sup>>\ne sup>>i>j>>(>r>+>1>)>sup>>for\; some>>=>m>,>.>.>.>,>m>+>l>->2>>>>>>1>s>>>>ifsup>>>i>\prime >>j>>(>r>+>1>)>sup>>=sup>>i>j>>(>r>+>1>)>sup>>for\; each>>=>m>,>.>.>.>,>m>+>l>->2>>>\; >.>>\end{array}$$

这意味着在n-qMC的s^l×s^l-变换矩阵II的每列中，将存在正好s个等于的成员(对于$$ >sup>>>i>\prime >>j>>(>r>+>l>)>sup>>=sup>>i>j>>(>r>+>1>)>sup>>,>j>=>m>,>.>.>.>,>m>+>1>->2>>$$的那些)，其他成员将等于0，于是II的每列的成员之和等于1。因此，变换矩阵II是双随机的。它也是正则矩阵，因为矩阵II^l的每个元素是正的。这意味着系统pII＝p具有唯一的固定概率向量$$ >>p>=>>(>>1>>s>l>>>,>>1>>s>l>>>,>.>.>.>,>>1>>s>l>>>)>>>$$作为解。换句话说，长度l≤r的γ的子串的分布是均匀的。现在假设l＝r+1，并且设数t、t’以及概率pt′t如以前那样定义。于是对于pt′t，我们有，上面对于pt′t的方程也成立，即，

$$ >>>p>>>t>\prime >>t>>>=>>>P>>(sup>>\cap >>j>=>0>>rsup>>>(sup>>Y>>m>+>j>>>(>r>)>sup>>=sup>>i>>m>+>j>>>(>r>)>sup>>)>>)>>>>P>>(sup>>\cap >>j>=>0>>>r>->1>sup>>>(sup>>Y>>m>+>j>>>(>r>)>sup>>=sup>>i>>m>+>j>>>(>r>)>sup>>)>>)>>>>=>>>P>>(sup>>\cap >>j>=>0>>>r>->1>sup>>>(sup>>Y>>m>+>j>+>1>>>(>r>)>sup>>=sup>>i>>m>+>j>+>1>>>(>r>)>sup>>)>|sup>>Y>m>>(>r>)>sup>>=sup>>i>m>>(>r>)>sup>>>)>>>>P>>(sup>>\cap >>j>=>0>>>r>->2>sup>>>(sup>>Y>>m>+>j>+>1>>>(>r>)>sup>>=sup>>i>>>m>+>j>>+>1>>>(>r>)>sup>>)>|sup>>Y>m>>(>r>)>sup>>=sup>>i>m>>(>r>)>sup>>>)>>>>>$$

与以前使用的方式相同，通过利用方程$$ >sup>>i>>J>->1>*>u>>>(>u>)>sup>>x>=sup>>i>J>>(>u>)>sup>>>$$在拟群(A，_*u)中具有唯一解$$ >>x>=sup>>i>J>>(>u>->1>)>sup>>,>>$$其中u＝r，r-1，...，2，1的这一事实，我们可以考虑γ′＝E^(r)(β)，γ″＝E^(r-1)(β)，...，γ^(r)＝E⁽¹⁾(β)，γ^(r＝1)＝E⁽⁰⁾(β)＝β.的子串。于是，对于概率pt′t，通过反复使用方程(4)和(6)，我们将上标(r)减少到(r-1)，到(r-2)，...，到(1)，即，我们将有

$$ >>=>>>P>>(sup>>Y>>m>+>r>->1>>>(>1>)>sup>>=sup>>i>>m>+>r>->1>>>(>1>)>sup>>,sup>>Y>>m>+>r>>>(>1>)>sup>>=sup>>i>>m>+>r>>>(>1>)>sup>>)>>>>P>>(sup>>Y>>m>+>r>->1>>>(>1>)>sup>>=sup>>i>>m>+>r>->1>>>(>1>)>sup>>)>>>>>$$

$$ >>=>P>>(sup>>Y>>m>+>r>>>(>1>)>sup>>=sup>>i>>m>+>r>>>(>1>)>sup>>|sup>>Y>>m>+>r>->1>>>(>1>)>sup>>=sup>>i>>m>+>r>->1>>>(>1>)>sup>>)>>>$$

$$ >>=>P>>(sup>>Y>>m>+>r>>>(>0>)>sup>>=sup>>i>>m>+>r>>>(>0>)>sup>>)>>>$$

其中$$ >sup>>i>>m>+>r>>>(>0>)>sup>>\in >\beta >.>.>>$$由于$$ >>P>>(sup>>Y>>m>=>r>>>(>0>)>sup>>=sup>>i>>m>+>r>>>(>0>)>sup>>)>>=sup>>q>>m>+>r>>>(>0>)>sup>>,>>$$因此我们有

$$ >>>p>>>t>\prime >>t>>>=>\begin{array}{}>>>0>>>ifsup>>>i>\prime >>j>>(>r>+>1>)>sup>>\ne sup>>i>j>>(>r>+>1>)>sup>>for\; some>>=>m>,>.>.>.>,>m>+>r>->1>>>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>>>ifsup>>>i>\prime >>j>>(>r>+>1>)>sup>>=>\ne sup>>i>j>>(>r>+>1>)>sup>>for\; each>>=>m>,>.>.>.>,>m>+>r>->1>>>\; >>\end{array}$$

其揭示

$$ >>>\Sigma >>>t>\prime >>=>0>>>>s>>r>+>1>>>->1>>>>p>>>t>\prime >>t>>>=>>\Sigma >sup>>i>>m>->1>>>(>r>+>1>)>sup>>=>0>>>s>->1>>>>\Sigma >sup>>>i>\prime >>m>>(>r>+>1>)>sup>>=>0>>>s>->1>>>·>·>·>>\Sigma >sup>>>i>\prime >>>m>+>r>->2>>>(>r>+>1>)>sup>>=>0>>>s>->1>>>>p>>>t>\prime >>t>>>=>>\Sigma sup>>i>>m>->1>>>(>r>+>1>)>sup>>>s>->1>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>>$$

$$ >>=>>\Sigma >sup>>i>m>>(>r>)>sup>>=>0>>>s>->1>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>=>>\Sigma >sup>>i>>m>+>1>>>(>r>->1>)>sup>>=>0>>>s>->1>>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>=>·>·>·>>\Sigma sup>>i>>m>+>r>>>(>0>)>sup>>>s>->1>>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>=>1>>$$

我们应当注意方程

$$ >>>\Sigma >sup>>i>>m>->1>>>(>r>+>1>)>sup>>=>0>>>s>->1>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>=>>\Sigma >sup>>i>m>>(>r>)>sup>>=>0>>>s>->1>>sup>>q>>i>>m>+>r>>>>(>0>)>sup>>=>.>.>.>>$$成立，因为方程$$ >sup>>i>>j>->1>*>u>>>(>u>)>sup>>x>=sup>>i>j>>(>u>)>sup>>>$$对于每个u＝r+1，r，...，2，1，在拟群(A，_*u)中具有唯一解。

因此，变换矩阵II是双随机的，它是正则的(II^r+1具有正项)，意味着系统pII＝p具有唯一的固定概率向量$$ >>p>=>>(>>1>>s>>r>+>1>>>>,>>1>>s>>r>+>1>>>>,>·>·>·>,>>1>>s>>r>+>1>>>>)>>>$$作为解。

一般而言，在串γ＝E⁽ⁿ⁾(β)中对于l＞n的长度l的子串的分布不是均匀的。即，对于l＝n+1，以与前面证明的最后部分中相同的方式，可以示出$$ >>P>>t>\prime >>t>=>P>>(sup>>Y>>m>+>n>+>1>>>(>0>)>sup>>=sup>>i>>m>+>n>+>1>>>(>0>)>sup>sup>>>|>Y>>>m>+>n>>>(>0>)>sup>>=sup>>i>>m>+>n>>>(>0>)>sup>>)>>,>>$$于是(与上所示的揭示的求和一样)，我们有

$$ >>>\Sigma >>>t>\prime >>=>0>>>s>>n>+>l>->1>>>>pt>\prime >t>=>>\Sigma sup>>i>>m>+>n>>>(>0>)>sup>>>s>->1>>>P>>(sup>>Y>>m>+>n>+>1>>>(>0>)>sup>>=sup>>i>>m>+>n>+>1>>>(>0>)>sup>>|sup>>Y>>m>+>n>>>(>0>)>sup>>=sup>>i>>m>+>n>>>(>0>)>sup>>)>>>$$

当然，最后的和一定不能等于1，即，变换矩阵II一定不能是双随机的。对于l＝n+2，n+3，...也可以做出相同的考虑。

为了证明定理12，考虑s阶有限拟群(A，_*)，并且取固定元素a∈A使得a*a≠a。我们将在更极端的情况中证明定理12，因此我们取周期l的串α＝a₁...a_k，其中对于每个i≥1，a_i＝a。然后我们对α应用变换E＝e_a，*若干次。Eⁿ意味着E被应用n次，并且我们表示$$ >>>E>n>>>(>\alpha >)>>=sup>>a>1>>(>n>)>sup>>.>.>.sup>>a>k>>(>n>)>sup>>.>>$$下表中提供结果。由于a*a≠a，因此对于某p＞1，因此我们有a′_p＝a

  a  aa   a...  aaaa  a₁′a₁″a₁a₁⁽⁴⁾  a₂′a₂″a₂a₂⁽⁴⁾a_p-1′a_p-1″a_p-1a_p-1⁽⁴⁾   a_p′a_p″a_pa_p⁽⁴⁾............

并且a_i′∈A(所以我们有，p至少为s)，并且设p为具有该性质的最小整数。由此得出，串E(α)是周期性的，周期为p。由于类似的理由，我们有，每个串E(α)是周期性的。我们将示出，所有串E(α)有相同周期p是不可能的。如果我们假设它为真，那么对于每个n≥1，我们将有$$ >sup>>a>p>>(>n>)>sup>>=>a>.>>$$然后我们还将有，存在使得下面等式成立：

$$ >\begin{array}{}>>sup>>a>>p>->1>>>(>n>)>sup>>=>>b>>p>->1>>>>>for>>\ge >2>>>\; >\end{array}$$

$$ >\begin{array}{}>>sup>>a>>p>->2>>>(>n>)>sup>>=>>b>>p>->2>>>>>for>>\ge >3>>>\; >\end{array}$$



$$ >\begin{array}{}>>sup>>a>1>>(>n>)>sup>>=>>b>1>>>>for>>\ge >p>>>\; >\end{array}$$

于是我们有a*b₁＝b₁，并且揭示对于每个n≥1，$$ >sup>>a>1>>(>n>)>sup>>=>>b>1>>.>>$$我们得到a*a＝a*b₁＝b₁，揭示a＝b₁，与a*a≠a相矛盾。结果，我们有

$$ >sup>>a>1>>(>p>+>1>)>sup>>=>a>*sup>>a>1>>(>p>)>sup>>=>a>*>>b>1>>\ne >>b>1>>,sup>>a>2>>(>p>+>1>)>sup>>=sup>>a>1>>(>p>+>1>)>sup>>*>>b>2>>>$$

$$ >sup>>>\ne >>b>2>>.>.>.>,>a>>>p>->1>>>(>p>+>1>)>sup>>=sup>>a>>p>->2>>>(>p>+>1>)>sup>>*>>b>>p>->1>>>\ne >>b>>p>->1>>>,sup>>a>p>>(>p>+>1>)>sup>>=sup>>a>>p>->1>>>(>p>+>1>)>sup>>*>a>\ne >a>.>>$$

我们得出结论，串E_a^(p+1)(α)的周期不是p。

接下来我们示出，如果串β∈A⁺具有周期p，并且γ＝E(β)具有周期q，则p是q的因数。回想通过定理10的变换E是置换，因此存在反变换E^-1。现在，如果γ＝b₁...b_qb₁...b_q...b₁...b_q，则β＝E^-1(γ)＝c₁c₂...c_qc₁c₂...c_q...c₁c₂...c_q是周期≤q的周期性串。因此，p≤q，并且这揭示p是q的因数。

将前面结果组合，我们已证明定理12的下面版本：

设α是具有周期p₀的串。于是，串$$ >>\beta >=sup>>E>a>nsup>>>(>\alpha >)>>>$$是周期性的，其周期p_n是p₀的倍数。β的周期p_n满足不等式

对于每个n≥1，$$ >>>p>>p>>n>->1>>>>>>>p>>n>->1>>>.>>$$

尽管示出和描述了本发明的特定实施例，但应当理解，其他变形、替换和更改对于本领域的普通技术人员来说是明显的。可以做出这些变形、替换和更改，而不背离本发明的精神和范围，本发明的范围应当由权利要求书确定。

本发明的各种特征在权利要求书中阐述。

优先权声明

本发明依照35U.S.C.§119要求于2004年10月13日提交的美国临时专利申请No.60/618173的优先权。