基于亚群上离散对数问题的密钥分配及加解密协议的方法

摘要

本发明提出了一种基于亚群上离散对数问题的密钥分配的方法，可用于公开信道上的密钥分配、信息加密。它是先构造一类只满足封闭性、非结合、非交换、无单位元、无逆元、对普通加法不满足分配律、且幂运算唯一满足指数交换律的亚群；并构造亚群的幂运算规则；运用构造的亚群及幂运算规则建立双方共享的密钥。本发明首次提出并实现了一类具有特殊性质的亚群，并将该亚群的幂运算规则构造成关于指数序列的非常复杂的迭代函数，使得利用周期特性求离散对数的传统分析方法和概念变得没有意义，密码破译只能归结为二叉树搜索，从而使公钥密码体制的安全性获得了实质性提高。

说明书

技术领域

本发明属于密码技术和信息安全技术领域，是一种利用数学上的困难问题，具体地说，是利用亚群上求解离散对数的困难性，来实现密钥分配协议的方法，以及加解密协议的方法。

背景技术

密码技术是研究加密和解密变换的一门科学技术。通常情况下，人们将可懂的文本称为明文；将明文变换成的不可懂的文本称为密文。把明文变换成密文的过程叫加密；其逆过程，即把密文变换成明文的过程叫解密。明文与密文的相互变换是可逆的变换，并且只存在唯一的、无误差的可逆变换。在计算机上实现的数据加密算法，其加密或解密变换是由一个密钥来控制的。密钥是由使用密码体制的用户随机选取的，密钥成为唯一能控制明文与密文之间变换的关键，它通常是一随机字符串。本发明就是完成密钥分配协议及加解密协议的方法。

公钥密码正式诞生的标志是1976年W.Diffie和M.Hellman发表的《密码学的新方向》。公钥密码使用两个密钥——一个公钥和一个私钥，这两个密钥在数学上是相关的。在公钥加密中，公钥可在通信双方之间公开传递，或在公用储备库中发布，但相关的私钥是保密的。只有使用私钥才能解密用公钥加密的数据。公钥密码由于有效地解决了密钥分配和信息识别验证问题而受到重视，是解决信息的保密性、真实性、完整性、抗抵赖性、可控性、有效性的关键技术，已成为开放系统环境下的基础加密机制和数字签名机制。二十多年来，它已由一种新颖的概念发展成为现代密码技术的一个重要方面，引起了信息安全领域的一场革命，是密码技术由封闭走向开放的主要标志。

评价一种公钥密码方案的应用价值的一般准则是：(1)具有足够的抗破译能力；(2)算法自由度较高，即算法足够复杂，有很大的设计空间；(3)具有足够的加解密速度；(4)明文、密文的分组长度较短，便于实现数据格式的标准化；(5)密钥长度较短，产生新密钥容易；(6)没有大的密文扩张。

目前国内外已发表了上百种公钥密码的实现方案，但绝大多数都已被攻破，只有极少数方案相对而言被认为是比较满意的，而安全性能得到严格数学证明的方案至今尚未出现。其中，分析最深入、技术最成熟、被认为有较强的安全性、已进入工程应用阶段的方案只有基于大数分解的RSA算法、基于求解有限域上离散对数问题的Diffie-Hellman算法、基于代数曲线上点的加法群性质的椭圆曲线算法等少数几种。

与传统的对称密码相比，上述几种公钥密码方案的共同缺点是算法复杂性和自由度明显偏低：只能在少数几种严格规定的数学结构下进行变换，而不能使用任意的迭代与置换。从破译的角度看，过于简单的密码往往容易导致简洁的破译算法，从而影响了它在关键核心部门的大量使用。尤其是在还目前没有任何一种公钥密码算法的安全性获得了严格证明的现实条件下，密码使用部门从信息安全的利益出发，总是慎之又慎，要求公钥密码达到尽可能高的复杂性和自由度。

探索理想的公钥密码方案相当困难。设计公钥密码需要一些特殊的数学技巧，不仅要把握当代数学前沿问题的进展，还要有丰富的实际编码经验和分析水平，对密码算法的规律和本质有深入的理解和体验，并有一定的工程实现能力。近年来，国内外密码学术界在提高公钥密码安全性与算法自由度方面的研究始终在进行，但一直没有出现本质性的重大突破。

以往国内外发表和使用的公钥密码方案，无论是比较成熟的RSA算法、Diffie-Hellman算法、椭圆曲线算法，还是未被广泛使用的其它算法，如Rabin算法、二次剩余算法、McEliece算法，以及CN1258051A(一种公开密钥加密体制和装置)、CN1251715A(有限域离散对数密码系统的割圆多项式结构)等专利算法，都以“群”作为其最基本的数学结构。例如：RSA算法采用由剩余类环中的原根组成的亚循环Abel群上的求幂运算，Diffie-Hellman算法采用有限域上的循环Abel群上的求幂运算，椭圆曲线算法采用有限域上2元3次方程中的点组成的Abel群的求幂运算。

群(group)是满足封闭性、结合律、有单位元、有逆元的二元运算结构，半群(semi-group)是满足封闭性、结合律的二元运算结构，而亚群(groupoid)(也叫做广群)则是只满足封闭性一条性质的二元运算结构。群是半群的子集，半群又是亚群的子集。

显然，对于设计公钥密码来说，亚群是比群更好的代数结构。首先，亚群与群相比，其外延更广泛、形式更一般、性质更复杂，在抗数学分析方面有天然的优势，由于可以不考虑结合律、单位元素、逆元素以及交换律、分配律等约束条件，使算法设计的灵活性和自由度大为增加。其次，当代数学对亚群的研究很不成熟，由于长期不被关注，文献资料很少，而群论的大量现有理论和结果又无法简单地直接推广到亚群，进一步增加了密码分析的困难性。鉴于亚群研究的空白现状，在现有技术中还从未出现过一种建立在亚群基础上的密钥分配及加解密方法。

发明内容

本发明的目的就是提供一种比基于群基础上的密钥分配和加解密方法在抗数学分析方面有更大的优势，而且设计的灵活性和自由度大为增加，密码分析十分困难的密钥分配方法，以及相关的加解密协议的方法。

为实现上述目的，本发明采用更适合于实现公钥密码的亚群，以及建立在亚群上的特殊的幂运算规则作为其基本代数结构，来实现密钥分配和加解密协议。当然，本发明的实现是建立在对亚群更为深入的研究的基础之上，正是因为本发明对亚群的研究填补了国内外对亚群研究的空白，才产生了本发明。

本发明的基于亚群上离散对数问题的密钥分配的方法的解决方案是：

a、构造一类只满足封闭性、非结合、非交换、无单位元、无逆元、对普通加法不满足分配律、且幂运算唯一满足指数交换律的亚群；

b、构造亚群的幂运算规则；

c、运用构造的亚群及幂运算规则建立双方共享的密钥：在亚群中取底数A，通信双方各以足够大的正整数L_a、L_b，分别计算 $>>>B>a>>=>>A>>L>a>>>,>>>$ >>>B>b>>=>>A>>L>b>>>>>，并传递给对方，双方分别计算$ >>>K>a>>=sup>>B>b>>L>a>sup>>,>>>$ >>>K>b>>=sup>>B>a>>L>b>sup>>,>>>K$$$$_a＝K_b，作为双方共享的密钥。

上述步骤a、b建立在对亚群和其幂运算规则的研究的基础之上。本发明认为，亚群可以通过这样几种方式构造出来：以有限交换环构造有零因子亚群、以有限非交换环构造有零因子亚群、以无零因子的有限交换群构造无零因子亚群。

1、以有限交换环构造有零因子亚群。

以有限交换环构造有零因子亚群的方法是：R代表有限交换环，#Rⁿ表示R上的n阶向量的集合，表示定义在#Rⁿ上的二元运算，通过下式构造了一个有零因子亚群：

          a″＝f(a₁，a₂，…，a_n)

A＝[a₁，a₂，…，a_n]，B＝[b₁，b₂，…，b_n]，C＝[c₁，c₂，…，c_n]

          A，B，C∈#Rⁿ，a_i，b_i，c_i，a″∈Rf()的构造方法是：用环R中的不等于0的元随机构造d×n阶阵列G：

          G＝[(g)_ij]_d×n∈R^d×n；

由初始状态a₁(0)，a₂(0)，…，a_n(0)，对于i＝1，2，…，d，依次计算：

…………

$>>>a>1>>>(>i>)>>=>>>[>>g>>i>,>1>>>>(>>a>1>>>(>i>->1>)>>+>>a>n>>>(>i>->1>)>>)>>]>>>e>i>>>>>$

$>>>a>2>>>(>i>)>>=>>>[>>g>>i>,>2>>>>(>>a>2>>>(>i>->1>)>>+>>a>1>>>(>i>)>>)>>]>>>e>i>>>>>$

$>>>a>n>>>(>i>)>>=>>>[>>g>>i>,>n>>>>(>>a>n>>>(>i>->1>)>>+>>a>>n>->1>>>>(>i>)>>)>>]>>>e>i>>>>>$

得至a″＝[a₁(d)+a₂(d)+…+a_n(d)]^h，其中n、d、h、e₁、e₂、…、e_d取大于1的正整数。

其中，有限交换环优选多重模运算下的一元多项式环，该环的构造方法包括：以整数剩余类环Z_m中的元为系数、以Z_m为定义域、以Z_m为值域，随机构造一个关于x的s次首1多项式u(x)，由m、u(x)构造一个Z_m上的多项式环R[u(x)]＝(#u(x)，+，·)，#u(x)＝{f(x)|f(x)＝f’(x)Mod m，u(x)}，f’(x)表示Z_m上的一般的整数多项式，“+”、“·”分别表示在双重模运算“Mod m，u(x)”下的多项式加法和多项式乘法，x∈Z_m，deg(u(x))＝s；然后每次分别以上一多项式环中的元素为系数、以上一多项式环为定义域、以上一多项式环为值域，随机构造一个若干次首1多项式，由m和所有出现过的首1多项式构造一个在上一多项式环上的新多项式R[α(β)]＝(#α(β)，+，·)，#α(β)＝{f(β)|f(β)＝f’(β)Mod m和所有出现过的首1多项式，f’(β)表示上一多项式环上的一般的多项式，“+”、“·”分别表示在m和所有出现过的首1多项式的多重模运算下的多项式加法和多项式乘法，这样一层一层扩展下去，直至达到需要的层次。

2、以矩阵环、λ矩阵环等有限非交换环构造有零因子亚群。

以有限非交换环构造有零因子亚群的方法是：R为有限非交换环，gi为有限非交换环的矩阵中的元素，#Rⁿ表示R上的n阶向量的集合，表示定义在#Rⁿ上的二元运算，通过下式构造了一个有零因子亚群：

其中，a″＝[g₁a₁(0)+g₂a₂(0)+...+g_na_n(0)]^h

A＝[a₁，a₂，...，a_n]，B＝[b₁，b₂，...，b_n]，C＝[c₁，c₂，...，c_n]

A，B，C∈#Rⁿ，a_i，b_i，c_i，a″∈R，n、h取大于1的正整数。

3、以无零因子的有限交换群构造无零因子亚群。

以无零因子的有限交换群构造无零因子亚群的方法是：R表示无零因子的有限交换群，选择大于1的正整数n、h、e，h≠e，随机选择g₀，g₁，...，g_n，g_i∈R且g_i≠0，#Rⁿ表示R上的n阶向量的集合，表示定义在#Rⁿ上的二元运算，通过下式构造了一个无零因子亚群：

A＝[a₁，a₂，...，a_n]，B＝[b₁，b₂，...，b_n]，C＝[c₁，c₂，...，c_n]

A，B，C∈#Rⁿ，a_i，b_i，c_i，g_i∈R。

通过这样的方式，就构造了亚群。它具有封闭性、非结合、非交换、无单位元、无逆元、对普通加法不满足分配律的性质，对于幂运算来说，它具有下面的性质：

    (D^a)^b＝(D^b)^a(指数交换律，注意这是最关键的性质)

    D^(a×b)≠(D^a)^b

    D^(a+b)≠D^aD^b

    D^aD^b≠D^bD^a

           a个D

        6447448

    D^a≠DD...D

然后，构造亚群的幂运算规则。其方法是：D属于有零或无零因子亚群，a为正整数，D在a的二进制序列控制下，运用及针对D的序列的不同结合顺序而进行乘法迭代运算：D^a＝f(D，a，，结合顺序)。在进行幂运算之前先构造一个幂运算规则表，该表的每个记录都是关于D的复杂的幂函数，进行幂运算的过程中对该表的内容进行伪随机地刷新。

本发明还公开了基于亚群上离散对数问题的加解密协议的方法，它的过程是：

a、构造一类只满足封闭性、非结合、非交换、无单位元、无逆元、对普通加法不满足分配律、且幂运算唯一满足指数交换律的亚群；

b、构造亚群的幂运算规则；

c、运用构造的亚群及幂运算规则实现加解密协议：在亚群中取底数A，解密方、加密方分别以足够大的正整数L_a、L_b，分别计算 $>>>B>a>>=>>A>>L>a>>>,>>>$ >>>B>b>>=>>A>>L>b>>>>>，加密方计算$ >>K>=sup>>B>a>>L>b>sup>>,>>>然后以K对明文M进行加密成密文C，然后将\{B$$$_b，C}传送给解密方，解密方计算 $>>K>=sup>>B>b>>L>a>sup>>,>>>以K将密文C解密成明文M。$

通过上面的分析可以看出来，本发明正是利用了亚群的幂运算的唯一的一条性质：(D^a)^b＝(D^b)^a得到一个共享的密钥，实现密钥分配及加解密协议，而对亚群来说，其他的性质都不满足，这样他人要想攻破就非常困难，比基于群基础上的密钥分配和加解密方法在抗数学分析方面有更大的优势。另外，由于亚群不满足结合律，其幂运算根据不同的结合顺序，就能得到不同的结果，这也是密码设计中所需要的，因为这样就可以通过设计不同的复杂的幂运算结合顺序来进行不同的密码设计，使得设计的灵活性和自由度大为增加。另外，从上面建立亚群和其幂运算规则的过程中可以看出，亚群有这样一个特点：求解幂运算时按照幂运算规则是容易做到的，但反过来已知底和幂运算结果求解对数是非常困难的，也就是说，其密码强度基于求解亚群上离散对数的困难性，因此，密码分析十分困难，密码强度非常高。由于亚群的幂运算规则可以构造成关于指数序列的非常复杂的函数，使得利用周期特性求离散对数的传统攻击手段变得没有意义，密码破译只能归结为二叉树搜索。通过这样的分析可以看出，本发明是非常巧妙的，它通过建立亚群，然后通过亚群一系列特殊的性质带来的优点，最后创造出了一种密码强度极高、设计自由度又极大的密钥分配及加解密协议的方法，而在加解密速度、分组长度、密钥产生、密文扩张等方面基本满足目前的工程应用和器件发展水平的需求。

附图说明

图1是本发明的层次框图。

图2是本发明的用有限交换环构造有零因子亚群的流程图。

图3是本发明的用有限非交换环(比如矩阵环、λ矩阵环)构造有零因子亚群的流程图。

图4是本发明的构造无零因子亚群的流程图。

图5是本发明利用亚群及其幂运算规则实现密钥分配协议的流程图(建立亚群及其幂运算规则部分略)。

具体实现方式

在图1中可以看到，本发明的技术方案由四个层次组成，分别是：

协议层：其功能是利用规则层提供的幂运算规则实现密钥分配协议、加密协议。

规则层：其功能是利用结构层提供的有零因子亚群S(或无零因子亚群T)的非结合性质，构造复杂的幂运算规则。

结构层：其功能是用利用子结构层提供的有限环或有限群R，构造有零因子亚群S、无零因子亚群T。

子结构层：其功能是构造有限环或有限群R。R可以采用有限交换环，也可以采用矩阵环、λ矩阵环类型的有限非交换环，但本发明提出并重点推荐的最佳设计实例是用多重模运算下的一元多项式环作为R。

上述设计有些类似于七层网络通信协议模型，其优点是方法描述清晰，功能划分明确：当较高层次的方法及数据调用低一层次的方法及数据时，只把低一层次的方法及数据看作一个整体，而并不考虑其内部的具体结构和具体实现过程。例如在构造幂运算规则时，我们并不考虑其结构层采用的是哪种类型的亚群，是S还是T；同样，在构造亚群S时，我们也并不考虑有限环R中的具体特征参数等细节问题。

下面从子结构层逐一往上谈起。

子结构层：可以采用有限交换环，也可以采用矩阵环、λ矩阵环类型等有限非交换环，以及有限交换群。一般的有限交换环和矩阵环、λ矩阵环、有限交换群等是本领域技术人员知悉的内容。着重讨论多重模运算下的一元多项式环R的构造方法，它是本发明所采用的有限交换环的最佳设计实施，如果采用它，本发明的任务会完成得更好，没有它，本发明的任务也能完成，但不如采用该环效果佳。

构造多重模运算下的一元多项式环R的步骤如下：

[第一步]用Z_m构造多项式环R[u(x)]。首先，构造整数剩余类环Z_m，然后，以Z_m中的元为系数、以Z_m为定义域、以Z_m为值域，随机构造一个关于x的s次首1多项式u(x)：

        u(x)＝(x^s+a_s-1x^s-1+...+a₁x+a₀)Mod m

我们用f’(x)表示Z_m上的一般的整数多项式，用“+”、“·”分别表示在双重模运算“Mod m，u(x)”下的多项式加法和多项式乘法，则由m、u(x)可构造一个Z_m上的多项式环：

           R[u(x)]＝(#u(x)，+，·)

      #u(x)＝{f(x)|f(x)＝f’(x)Mod m，u(x)}

           x∈Z_m，deg(u(x))＝s

[第二步]用R[u(x)]构造多项式环R[v(y)]。以R[u(x)]中的元素为系数、以R[u(x)]为定义域、以R[u(x)]为值域，随机构造一个关于y的k次首1多项式v(y)：

     v(y)＝(y^k+b_k-1y^k-1+...+b₁y+b₀)Mod m，u(x)

我们用f’(y)表示环R[u(x)]上的一般的多项式，用“+”、“·”分别表示在三重模运算“Mod m，u(x)，v(y)”下的多项式加法和多项式乘法，则由m、u(x)、v(y)可构造一个R[u(x)]上的多项式环：

         R[v(y)]＝(#v(y)，+，·)

    #v(y)＝{f(y)|f(y)＝f’(y)Mod m，u(x)，v(y)}

    x∈Z_m，y∈R[u(x)]，deg(u(x))＝s，deg(v(y))＝k

[第三步]用R[v(y)]构造多项式环R[w(z)]。以R[v(y)]中的元素为系数、以R[v(y)]为定义域、以R[v(y)]为值域，随机构造一个关于z的q次首1多项式w(z)：

    w(z)＝(z^q+c_q-1z^q-1+...+c₁z+c₀)Mod m，u(x)，v(y)

我们用f’(z)表示环R[v(y)]上的一般的多项式，用“+”、“·”分别表示在四重模运算“Mod m，u(x)，v(y)，w(z)”下的多项式加法和多项式乘法，则由m、u(x)、v(y)、w(z)可构造一个R[v(y)]上的多项式环：

          R[w(z)]＝(#w(z)，+，·)

     #w(z)＝{f(z)|f(z)＝f’(z)Mod m，u(x)，v(y)，w(z)}

          x∈Z_m，y∈R[u(x)]，z∈R[v(y)]

     deg(u(x))＝s，deg(v(y))＝k，deg(w(z))＝q

最后，用R[w(z)]作为R。

以上描述了对剩余类环Z_m进行R[u(x)]、R[v(y)]、R[w(z)]的三层非线性代数扩张，根据密码强度要求还可以任意增加或减少扩张的层次。实际上也可以是二层，甚至是一层。适当设置m、s、k、q等参数，可获得各种具体的有限交换环，例如：当q＝k＝s＝1，R[w(z)]是一般的整数剩余类环，其中当m是素数时，R[w(z)]是有限域F_P；当s＞1，q＝k＝1，R[w(z)]是模m、u(x)的多项式环；当s，k＞1，q＝1，R[w(z)]是模m、u(x)、v(y)的多项式环；当s，k，q＞1，R[w(z)]是模m、u(x)、v(y)、w(z)的多项式环；当m、u(x)、v(y)、w(z)全部采用素数或不可约多项式，R[w(z)]是多项式分裂域。

如果我们把以上的一元多项式环扩展到多元多项式环，即

x∈Z_m^r，y∈R[u(x)]^t，z∈R[v(y)]^p，r、t、p＞1

并且u(x)、v(y)、w(z)均采用不可约代数簇时，R[w(z)]还可以成为更加复杂的多元多项式分裂域。但由于R[u(x)]、R[v(y)]、R[w(z)]的不可约理想是一类非常复杂的对象，工程实现代价将迅速增加，按照目前的理论研究与器件发展水平，技术可行性很低。

结构层：利用上述子结构层提供的有限交换环或有限非交换环或有限交换群，构造有零因子亚群S、无零因子亚群T。

有零因子亚群S的构造方法：

1、运用有限交换环构造有零因子亚群S的方法，如图2所示：

[第一步]选择一个有限交换环R。R的实际可选范围很大，如有限域，整数剩余类环，乃至多元多项式环上的复杂的代数簇，等等。选用较复杂的R，可获得较强的抗数学分析能力，但工程实现代价也会随之迅速增加；反之则相反。

从密码强度与工程代价两方面考虑，作为R的最佳设计实例，本发明提出并重点推荐选用多重模运算下的一元多项式环。该环的产生方法上面已经介绍。

[第二步]选择大于1的正整数n、d、h、e₁、e₂、...、e_d。我们把R理解为一般意义的有限交换环，用#Rⁿ表示R上的n阶向量的集合，用“”表示定义在#Rⁿ上的二元运算，通过下式构造了一个有零因子亚群：

         a″＝f(a₁，a₂，…，a_n)

A＝[a₁，a₂，…，a_n]，B＝[b₁，b₂，…，b_n]，C＝[c₁，c₂，…，c_n]

         A，B，C∈#Rⁿ，a_i，b_i，c_i，a″∈R其中f()是关于左因子A的n个分量的非线性函数，其构造方法是：

<第一小步>，用环R中的不等于0的元随机构造d×n阶阵列G：

         G＝[(g)_ij]_d×n∈R^d×n

<第二小步>，运用环R的运算规则，由左因子A的初始状态a₁(0)，a₂(0)，…，a_n(0)，进行d级非线性变换。即对于i＝1，2，…，d，依次计算：

…………

$>>>a>1>>>(>i>)>>=>>>[>>g>>i>,>1>>>>(>>a>1>>>(>i>->1>)>>+>>a>n>>>(>i>->1>)>>)>>]>>>e>i>>>>>$

$>>>a>2>>>(>i>)>>=>>>[>>g>>i>,>2>>>>(>>a>2>>>(>i>->1>)>>+>>a>1>>>(>i>)>>)>>]>>>e>i>>>>>$

$>>>a>n>>>(>i>)>>=>>>[>>g>>i>,>n>>>>(>>a>n>>>(>i>->1>)>>+>>a>>n>->1>>>>(>i>)>>)>>]>>>e>i>>>>>$

得到a₁(d)、a₂(d)、…、a_n(d)。

<第三小步>，运用环R的运算规则，将左因子的n个分量合成：

      a″＝[a₁(d)+a₂(d)+…+a_n(d)]^h

通过这样的过程，就构造了一个亚群。

[定义]由集合#Rⁿ和二元运算“”，组成一个非结合、非交换、无单位元、无逆元、有零因子的亚群：

             S＝(#Rⁿ，)

2、运用矩阵环、λ矩阵环构造有零因子亚群S的方法，如图3所示：

把R理解为矩阵环或λ矩阵环类型的有限非交换环，设g_i为矩阵或λ矩阵中的元素，用“”表示定义在#Rⁿ上的二元运算，则构造有零因子亚群的方法是：

              S＝(#Rⁿ，)

              a″＝[g₁a₁(0)+g₂a₂(0)+...+g_na_n(0)]^h

A＝[a₁，a₂，...，a_n]，B＝[b₁，b₂，...，b_n]，C＝[c₁，c₂，...，c_n]

              A，B，C∈#Rⁿ，a_i，b_i，c_i，a″∈R

上述两类有零因子亚群S，对于A，B，C∈S，有以下性质：

A(B+C)＝(AB)+(AC)(关于环R的加法的左分配律)

(AB)C≠A(BC)

AB≠BA

(A+B)C≠(AC)+(BC)

当环R没有零因子时，亚群S仍然以一个确定的概率出现零因子，这是因为在上述构造亚群的过程中，出现了环上加法，在做环上加法的过程中，即使其每一个因子都是非零的，仍然可能出现结果为零的情况，其出现概率与R的元素数量有关，约为：

无零因子亚群T的构造方法，如图4所示：

首先，选择一个有限交换群R。例如R可采用有限域中的乘法群，或椭圆曲线上的点组成的群。

然后，选择大于1的正整数n、h、e，h≠e，随机选择g₀，g₁，...，g_n，g_i∈R∩g_i≠0。我们用#Rⁿ表示R上的n阶向量的集合，用“”表示定义在#Rⁿ上的二元运算：

A＝[a₁，a₂，...，a_n]，B＝[b₁，b₂，...，b_n]，C＝[c₁，c₂，...，c_n]

           A，B，C∈#Rⁿ，a_i，b_i，c_i，g_i∈R

通过上述过程，就建立了一个无零因子的亚群。

[定义]当有限交换群R没有零因子，由集合#Rⁿ和二元运算“”，组成一个非结合、非交换、无单位元、无逆元、无零因子的亚群：

           T＝(#Rⁿ，)

对于A，B，C∈T，有以下性质：

(AB)C≠A(BC)

AB≠BA

A(B+C)≠(AB)+(AC)

(A+B)C≠(AC)+(BC)

由于该无零因子的构造过程中没有出现环上加法，消除了相加为零的可能性，而R选择的是无零因子的有限交换群，最后产生的就是无零因子的亚群。

规则层：亚群的幂运算规则的构造方法

[定义]设D∈有零因子亚群S(或无零因子亚群T)，a为正整数，我们把亚群S(或T)上的幂运算规则规定为：底数D在指数a的二进制序列控制下，运用“”及专门设计的针对D的序列的不同结合顺序而完成的乘法迭代运算：

                 D^a＝f(D，a，，结合顺序)

显然，不同的结合顺序将得到不同的求幂结果，例如：

((DD)D)D≠(D(DD))D≠D(D(DD))≠....

由于亚群S(或T)的非结合、非交换性质，可以把幂运算规则设计成关于指数a、底D的非常复杂的迭代函数。例如，最基本的幂运算规则与普通乘法的幂运算规则是相同的，为：

     A＝D，B＝D

     Do while a＞0

        If(a mod 2)＝1 then A＝AB

        a＝a\2

        B＝BB

     Loop

     D^a＝A

这一段程序的意思是，先判断指数的奇偶性，如是奇数先提出一个D来，剩下的就是D的偶数次幂，将该偶数提出一个因子2，先计算提出一个2之后的部分，然后再将结果计算2次幂，比如D⁷＝(D²*D)²*D。与普通乘法的幂运算规则是相同的。

另一种稍微复杂的幂运算规则，就与普通乘法的幂运算规则完全不同，例如：

    A＝D，B＝D，C＝D

    Do while a＞0

       If(a mod 4)＝0 then A＝AB

      If(a mod 4)＝1 then A＝AC

      If(a mod 4)＝2 then A＝BA

      If(a mod 4)＝3 then A＝CA

      a＝a\2

      B＝((BA)(BA))C

      C＝((AC)(AC))B

    Loop

    D^a＝A

在上述过程中，是针对指数a模4的不同情况分组，分别施以不同的幂运算，并且在该过程中对B和C进行了伪随机的刷新。

具体地说，为了构造复杂的幂运算规则，应在进行幂运算之前先构造一个幂运算规则表，该表的每个记录都是关于D的复杂的幂函数，进行幂运算的过程中要对该表进行伪随机地刷新。

[第一步]建立幂规则表。设D∈S(或T)，a为正整数，在计算D^a之前，先按照L个事先给定的随机正整数c₀、c₁、…、c_L-1，计算

$>>\{>>A>0>>,>>A>1>>,>.>.>.>,>>A>>L>->1>>>\}>=>\{>>D>>c>0>>>,>>D>>c>1>>>,>.>.>.>,>>D>>c>>L>->1>>>>\}>>>$

并存放在一个有L个记录的幂规则表中。建立该表的计算过程可采用任意的幂规则，其目的是保证每个A_i都是关于D的复杂的幂函数。

[第二步]运用幂规则表进行求幂运算。在对D^a进行求幂的过程中，一方面要让幂规则表的内容参与计算，另一方面又要对该表的内容进行伪随机地刷新。例如，设L＝256，一个简单设计实例如下：

    A＝D，B＝D

    Do while a＞0

         If(a mod 2)＝1 then

              A＝AB

              j＝a mod 256

              A＝AA_i；让幂规则表参与计算

              A_j＝A_jBA；伪随机地修改幂运算表

         endif

         a＝a\2

         B＝BB

    Loop

    D^a＝A

上面的A＝AA_j一步是根据j模256的不同结果让不同的A_j参与进来，但由于实际的需要，往往A_j不可能是一成不变的，往往要根据构造的复杂幂运算的需要进行随时更新，A_j＝A_jBA的含义就是伪随机地修改幂运算表。

以上规定的有零因子亚群S(或无零因子亚群T)的幂运算有以下性质：

(D^a)^b＝(D^b)^a(指数交换律，注意这是最关键的性质)

D^(a×b)≠(D^a)^b

D^(a+b)≠D^aD^b

D^aD^b≠D^bD^a

    a个D  

    6447448

D^a≠DD...D

随机选择A∈S(或T)，对于正整数L，计算B＝A^L是容易的，而由A、B求离散对数L是困难的，即B＝A^L是单向函数。在后面的利用该幂运算实现密钥分配协议和加密协议时，就为破解制造了困难。应注意不同的亚群有不同特点：S具有更强的抗数学分析能力，T没有零因子。一般来说，使用有零因子亚群效果更好一些，在数据小时可以采用无零因子亚群。

协议层：运用亚群及幂运算规则实现密钥分配协议、加密协议的方法。

甲乙双方通过执行密钥分配协议，可以在事先没有任何秘密约定的条件下，在完全公开的信道上建立双方共享的密钥K，然后运用密钥K进行传统的对称密码保密通信。虽然试图破译K的第三方能获得甲乙双方之间的所有通信内容，但仍然无法得到K。

实现密钥分配协议之前，需由公证机构或通信双方，按照要求构造并向所有用户公开亚群S(或T)、A∈S(或T)、以及专门为该亚群而设计的幂运算规则。然后执行以下四步，如图5所示：

第一步：甲方随机地选择一个足够大的正整数L_a，计算 $>>>B>a>>=>>A>>L>a>>>,>>>并把B$_a传递给乙方；

第二步：乙方随机地选择一个足够大的正整数L_b，计算 $>>>B>b>>=>>A>>L>b>>>,>>>并把B$_b传递给甲方；

第三步：甲方收到B_b，计算密钥 $>>>K>a>>=sup>>B>b>>L>a>sup>>=>>>(>>A>>L>b>>>)>>>L>a>>>;>>>$

第四步：乙方收到B_a，计算密钥 $>>>K>b>>=sup>>B>a>>L>b>sup>>=>>>(>>A>>L>a>>>)>>>L>b>>>.>>>$

由于亚群幂运算的指数交换性质，甲乙双方可获得的相同的K，即：

$>>K>=>>K>a>>=sup>>B>b>>L>a>sup>>=>>>(>>A>>L>b>>>)>>>L>a>>>=>>>(>>A>>L>a>>>)>>>L>b>>>=sup>>B>a>>L>b>sup>>=>>K>b>>>>$

然后甲乙双方便可利用这个共享的K进行保密通信。第三方虽然知道A、B_b和B_a，但无法由 $>>>B>a>>=>>A>>L>a>>>>>和$ >>>B>b>>=>>A>>L>b>>>>>，得到L$$_a和L_b，获得K的代价则等价于亚群上的离散对数问题，即对于 $>>>B>a>>=>>A>>L>a>>>>>，已知A、B$_a求L_a的困难性(或对于 $>>>B>b>>=>>A>>L>b>>>>>，已知A、B$_b求L_b的困难性)。

加密协议与密钥分配协议的实现原理相同，但具体实现方法有所区别：在加密协议中建立对称密钥K的过程与用K加解密的过程是结合在一起进行的，而在密钥分配协议中这两个过程是分别进行的。

在实现加密协议之前，需由公证机构按照要求构造并向所有用户公开亚群S(或T)、A∈S(或T)、以及专门为该亚群而设计的幂运算规则。然后，每个用户都随机地选择一个属于自己的足够大的正整数L_a，并计算 $>>>B>a>>=>>A>>L>a>>>>>，则该用户的公开密钥是B$_a，私人密钥是L_a。最后，把网络上的所有用户的公开密钥象电话号码本那样集中管理，供所有人公开查询，而秘密密钥由用户自己秘密地、妥善地保存。

以下我们用“C＝D(M，K)”表示利用密钥K、对明文M进行对称密码加密、计算密文C的过程；用“M＝D^-1(C，K)”表示利用密钥K、对密文C进行对称密码解密、恢复明文M的过程。

当网络中任何一个用户要向某用户发送一个信息时，先查询到该收方用户的公开密钥B_a，然后通信双方执行以下的加密协议：

发方利用收方的公开密钥B_a，对明文M加密的过程是：随机选择一个足够大的正整数L_b，计算

$>>>B>b>>=>>A>>L>b>>>,>K>=sup>>B>a>>L>b>sup>>,>C>=>D>>(>M>,>K>)>>>>$

则加密后得到的密文为{B_b，C}，然后把该密文传送给收方。

收方收到密文{B_b，C)后，利用私人密钥La解密的过程是：计算

$>>K>=sup>>B>b>>L>a>sup>>,>M>=>>D>>->1>>>>(>C>,>K>)>>>>$

则M正是发方传送过来的明文信息。

本发明是密码技术和信息安全技术上的一次革命，因为：

1、它首次提出并实现了用亚群构造公钥密码的概念与方法，提供了一类非结合、非交换、无单位元、无逆元、无分配律、但满足指数交换律、特别适合于设计公钥密码的亚群。由于现有的在群、环、域上广泛使用的一大类数学分析手段和结果不能简单地推广到亚群，使公钥密码的抗数学分析能力明显提高。

2、本发明首次提出并实现了“亚群的幂运算规则”的概念与方法，使设计公钥密码算法的自由度得到本质性提高。由于亚群的幂运算规则可以构造成关于指数序列的非常复杂的函数，使得利用周期特性求离散对数的传统攻击手段变得没有意义，密码破译只能归结为二叉树搜索。

本发明提出的创新部分包括：多重模运算下的一元多项式环R的构造方法；有零因子亚群S的构造方法；无零因子亚群T的构造方法；亚群的幂运算规则的构造方法；运用亚群及幂运算规则实现密钥分配协议、加密协议的方法。

下面举几个构造有零因子亚群或无零因子亚群，来实现密钥分配协议的例子。

实施例1，用多重模运算下的一元多项式环R构造有零因子亚群S并实现密钥分配协议

一种采用二层非线性代数扩张，把R[v(y)]作为R的简单实例如下：

设参数：n＝2，d＝2，h＝3，e1＝e2＝2，s＝3，k＝2，m＝30967(m的素分解为173×179)

u(x)＝x³+10331x²+29191x+15575

v(y)＝y²+(22823x²+23508x+17188)y+(25335x²+15462x+8727)

第1层非线性变换使用的系数为

g_1，1＝(4973x²+23767x+18329)y+(23747x²+15427x+1693)

g_1，2＝(6007x²+9721x+24439)y+(8543x²+2267x+28909)

第2层非线性变换使用的系数为

g_2，1＝(1373x²+23053x+13331)y+(22273x²+17x+10771)

g_2，2＝(3989x²+24239x+10459)y+(19471x²+30631x+2837)

构造出有零因子亚群后，下面的过程是完成密钥分配：

底A＝{A₁，A₂}，分别为

A₁＝(29921x²+11833x+2411)y+(12343x²+22283x+22031)

A₂＝(5081x²+3137x+20011)y+(113x²+22271x+10313)

设L_a＝6160，L_b＝24757，采用最基本的幂运算规则，进行密钥分配的实验。

甲方计算A的L_a次幂：B_a＝{B_a1，B_a2}，分别为

B_a1＝(2556x²+27649x+7618)y+(10491x²+26203x+13013)

B_a2＝(6762x²+29443x+2214)y+(5590x²+2256x+13387)

乙方计算A的L_b次幂：B_b＝{B_b1，B_b2}，分别为

B_b1＝(16239x²+14538x+5376)y+(29288x²+2106x+3034)

B_b2＝(13990x²+16871x+18190)y+ (6836x²+13140x+16220)

甲方计算B_b的L_a次幂：K_a＝{K_a1，K_a2}，分别为

K_a1＝(26137x²+11815x+4884)y+(11677x²+13171x+18833)

k_a2＝(24741x²+21163x+9218)y+(27629x²+551x+18964)

乙方计算B_a的L_b次幂：K_b＝{K_b1，K_b2}，分别为

K_b1＝(26137x²+11815x+4884)y+(11677x²+13171x+18833)

K_b2＝(24741x²+21163x+9218)y+(27629x²+551x+18964)

可见，K_a和K_b的计算结果是相同的。

实施例2，用剩余类环Z_m上的矩阵环构造有零因子亚群S

设参数：n＝2，h＝5，模数m＝30967(素分解为173×179)，矩阵的维数s＝2，系数：g₁＝22908，g₂＝25701，底A＝{A₁，A₂}，分别为

A₁＝{14419，11240，

     19910，18552}

A₂＝{21901，19947，

     30530，5692}

设L_a＝13177，L_b＝8754。采用最基本的幂运算规则，进行交互式密钥分配的实验结果如下：

甲方计算A的L_a次幂：B_a＝{B_a1，B_a2}，分别为

 B_a1＝{17788，5679，

      185961，7429}

B_a2＝{4356，6364，

      30955，16037}

乙方计算A的L_b次幂：B_b＝{B_b1，B_b2}，分别为

B_b1＝{5000，4790，

      18803，14817}

B_b2＝{5063，20666，

      28003，30615}

甲方计算B_b的L_a次幂：K_a＝{K_a1，K_a2}，分别为

K_a1＝{7342，14422，

      8725，8580}

K_a2＝{3035，6574，

      30360，4795}

乙方计算B_a的L_b次幂：K_b＝{K_b1，K_b2}，分别为

K_b1＝{7342，14422，

      8725，8580}

K_b2＝{3035，6574，

      30360，4795}

可见，K_a和K_b的计算结果是相同的。

实施例3，用有限域F_p构造无零因子亚群T

设n＝4，h＝2，e＝3，F_p的特征P＝32749，底A＝{6469，21211，18047，13859}，系数g₀＝10739，g₁＝30403，g₂＝9479，g₃＝9461，g₄＝32189，采用最基本的幂运算规则，进行交互式密钥分配的实验结果如下：

设L_a＝51761，L_b＝45233。

甲方计算A的L_a次幂：B_a＝{25044，9122，1891，20748}；

乙方计算A的L_b次幂：B_b＝{18605，23601，11904，9278}；

甲方计算B_b的L_a次幂：K_a＝{25087，32180，20024，15618}；

乙方计算B_a的L_b次幂：K_b＝{25087，32180，20024，15618}。

可见，K_a和K_b的计算结果是相同的。

上面，已经参照各附图，对本发明的几个典型的实施例进行了详细描述，以便使本发明变得更清楚，而不应认为本发明仅仅限于上述的实施例。本领域的技术人员，通过上述各实施例的启迪，不难对本发明做出各种改进、改变或替换，因而这些改进、改变或替换，不应认为已脱离了本发明的构思，或权利要求书所限定的范围。