破解HFEM公钥密码方案

古春生

(1. 江苏理工学院 计算机工程学院，江苏 常州 213001；2. 中国科学技术大学 计算机科学与技术学院，安徽 合肥 230027；3. 常州市云计算与智能信息处理重点实验室，江苏 常州 213001）

1 引言

由于计算数论上的因式分解问题、离散对数问题和椭圆曲线对数问题存在多项式时间量子算法[1,2]，因此，研究既能抵抗经典密码分析技术，又能抵抗量子密码分析技术的公钥密码方案是公钥密码学发展中的重要问题。目前设计抗量子计算的公钥密码方案成为密码学研究的热点之一。当前密码学界认为能抗量子计算的公钥密码方案主要有基于散列问题的公钥密码、基于编码问题的公钥密码、基于格问题的公钥密码、基于多变量问题的公钥密码等[3]。在这些公钥密码方案中，基于多变量的公钥密码因其计算速度快，密码膨胀率低的特点而成为“后量子密码学”研究的重要方向。近年来，设计构造基于遍历矩阵性质的密码原语已经引起了研究人员的广泛关注[4～9]。文献[4～6,8]研究了GF(2k)上的遍历矩阵性质，并给出了其在加密数据、生成伪随机数、生成信息摘要、Shamir三次传递协议等密码学上的应用，文献[10～12]利用遍历矩阵研究了公钥密码协议的半群作用问题。文献[13]构造了基于有限域上遍历矩阵的双侧幂乘问题的公钥加密方案。文献[14]基于BMQ问题(bisection multivariate quadratic equation problem)的困难性提出了隐藏域上遍历矩阵的公钥密码方案。尽管文献[14]证明了有限域上BMQ问题是NP完全，但并没有证明基于隐藏域上公钥密码方案的安全性。本文主要构造破解文献[14]中 HFEM(hidden field ergodic matrices)公钥密码方案的多项式时间算法。

本文多项式时间破解算法非常简单，即根据文献[14]的方案公钥中隐藏的遍历矩阵性质求出一个等价私钥，然后利用这个私钥对密文直接解密。具体说即通过分析发现文献[14]的公钥矩阵具有形式WB1, WB2，并且W可逆，矩阵 B1、 B2属于同一个遍历矩阵E的生成集，即，因而能够计算出矩阵根据遍历矩阵性质，矩阵 B0属于遍历矩阵E的生成集。然后，本文利用 B0依次求出 HFEM公钥密码方案的一个等价私钥。

2 赵永哲等人的HFEM公钥密码方案

为完整性，本节自适应地引用文献[14]中相关问题的定义和基于HFEM的公钥密码方案。

q遍历矩阵生成元，记

定义 1 BMQ-问题：S为 Fq上有m个方程和2n个变量的方程组，其每个方程形式可表示为

为易于证明，笔者自适应地引用文献[14]中基于HFEM的公钥密码方案如下。

密钥生成如下。

1) 随机选择矩阵集(A, B)。这里 A = { A1,… ,，要求满足A线性无关，且B是遍历矩阵E生成矩阵集 Fq[ E ]的基；

2) 随机选择变换矩阵 R ∈ GL2n( Fq)，并计算

3) 由RAB生成2n个BMQ多项式：[ρ1( x , y),…,

加密算法如下。

解密算法如下。

1) 给定私钥sk和密文C，计算 T = ( R-1×C)

2) 给定私钥sk和T，解出方程组 E ( A, B,T )的

3) 根据(x, y)与(α, β)等价，计算输出明文P=x⊗ y = α ⊗ β 。

根据文献[14]，方程组 E ( A, B ,T )定义为：这里定义，注意等式左边符号系符号混用，仅表示矩阵符号，目的是与文献[14]中原文一致，并不表示矩阵 A , B相乘后再将AB的元素按行排列后所对应列向量。在已知(A, B)的情况下，方程组 E ( A, B ,T )易于求解。

3 破解HFEM公钥密码方案

尽管文献[14]证明了BMQ问题是NP难的(定理1)，但文献[14]并没有归约HFEM公钥密码方案的安全性到求解BMQ问题。通过分析上述HFEM公钥密码方案，笔者知道破解公钥方案的关键是求出 VS(B)的一个基。为此，首先给出与遍历矩阵相关的2个引理。

证明 因 f (λ)=|λ I-E|，故f(λ)为次数为n的多项式。用反证法，假定 f (λ)是可约的，则 f (λ)或者是不可约多项式的幂，或者可以表示成2个互素多项式的积。下面分别证明它们是矛盾的。

1) f(λ)可表示成2个互素多项式的乘积。

不失一般性，设 f ( λ) = g1( λ)g2(λ)，deg(g1(λ))=k，1≤k＜n，deg(g2(λ))=n - k 和 g cd(g1(λ),g2(λ) ) = 1。

因E为遍历矩阵，故 f(0)=|E |≠0，所以g1(0) ≠ 0,g2(0) ≠ 0。

由deg(g1(λ))=k和g1(0)≠0，可知剩余类环Fq[λ]/(g1)只包含qk-1个非零元素，所以剩余类集合{λi|i = 0,… ,qk-1}中存在2个非零元素λr, λs满足 λr≡ λsm od g1(λ)，即存在正整数 0 ＜e1≤qk-1满足 λe1≡1mod g1(λ)。

同理可证存在正整数 0 ＜e ≤qn-k-1，满足2λe2≡1mod g2(λ)。

由gcd(g1( λ),g2(λ)) = 1，得并且 0 ＜ e e ＜ qn-1。12

因|Fq[ E ] |= qn-1和 f (λ)为遍历矩阵E的特征多项式，故满足 λe≡1modf(λ)的最小正整数是e = qn-1。

所以 ( qn- 1 )|(e1e2)，矛盾。

2)f(λ)是不可约多项式的幂，即f(λ)=g(λ)r,r≥ 2 。因 g (λ)为不可约多项式，且 g ( 0) ≠ 0 ，则e = qn/r-1是满足 λe≡1modg(λ)的最小正整数。故f(λ) = g(λ)r|(λqn/r-1- 1 )r。

因 Fq为有限域，故 Fq中元素个数一定是某个素数的幂。设素数p是 Fq的特征，则 Fq有 pk个元素，这里k是 Fq在素域 Fp的扩张次数。设v是满足pv≥r的最小正整数。因为，则

又因 e = qn-1是满足 λe≡1modf(λ)的最小正整数，所以 ( qn-1)|( pv( qn/r- 1 ))。因λ≥2，矛盾。

根据遍历矩阵特征多项式的不可约性可以得到有限域 Fq上模 f (λ)的多项式 Fq[λ]产生多项式的有限域，与遍历矩阵同构。

引理2 假定E为遍历矩阵且|Fq[ E ] |= qn-1，f(λ)为E的特征多项式，则矩阵集 B ={E0,E1,… ,En-1}为遍历矩阵集 Fq[E]的基。

证明 由引理1知， f(λ)为次数n的不可约多项式，因此，剩余类环 Fq[λ]/(f)中任意元素对应次数小于n的多项式 r(λ)，即又因Ek与有限域 F上次数小于n的 r (λ) = λkm od f(λ)

q一一对应，即在有限域Fq上矩阵 Ek等于 r(E)。而r(E )中所有E的次数小于n，即 Fq[E]中任意元素可以用B表示。同理可以证明，由B生成的元素也属于 Fq[E]∪ { 0}。

因 f (λ)为E的不可约特征多项式，故 f (E)为关于矩阵E满足 g ( E ) =0的多项式中最小次数的多项式。故矩阵集B线性无关。因此，B是 Fq[E]的基。

q个基。

因为 R ∈ GL2n( Fq)，A线性无关，由文献[15]可知：

rank(R) + r ank(A) - 2 n ≤ ra nk(R A) ≤ min(rank(R),rank(A) ) 。

因此，rank(RA)=n。不失一般性，设W1∈GLn( Fq)，即在有限域 Fq上 W1可逆。

又因为 B1∈GLn( Fq)，知W1B1可逆。故可以计算因此，可以计算得到和根据定理1可知 B '是 Fq[E]的基。

显然，易于证明上述求解 B ', A'算法所需时间是多项式时间算法。因为使用高斯消元法计算 B1的逆矩阵需要时间为 O ( n3)；计算 B '中矩阵乘积Bi，i=2,…, n 需要时间为(n-1)× O ( n3)= O ( n4)；计算 A '需要时间为2× O ( n3)= O ( n3)。这里假定 Fq上任意一次算术运算需要时间为1个单位时间。

证明 根据定理 2，可以在多项式时间内求解B', A'，且 B '也是 Fq[E]的基。

3)求解该方程组 E ( x, z)得一组非零解(x, z)

元法求逆得b。

6) 由(x, y)求出 E ( A', B ', C)的全部(q - 1 )个相互等价的解

7) 根据 HFEM 公钥密码方案，计算输出明文P = x ⊗ y 。

4 破解HFEM公钥密码方案举例(n=3，q=5)

本节通过实例演示破解HFEM公钥算法。首先生成 HFEM公钥；然后根据公钥求解基 B '和A'；最后根据 HFEM公钥密码方案对密文进行解密。

4.1 生成HFEM公钥

根据定理1可知，选择B只要为 Fq[ E ]的基即可，易于验证上述选择的B符合条件。计算输出公钥为

4.2 求解基 'B和 'A

现根据定理 2，使用公钥RAB计算 Fq[ E]的基B'和 A '如下。

2)计算13W B逆

4.3 加密算法

给定公钥RAB，设明文为 P =α⊗β=（4 2 3）⊗（2 3 1）。计算密文如下

4.4 解密算法

1) 根据文献[14]和求解的基 B '和 A '可列方程组 E ( A', B',C)

3) 求解该方程组E( x, z)得一组非零解x=（3 4 1）,z= （ 1 0 2） 。

6) 输出明文 P ' = x ⊗ y 。易于验证明文 P = P '。

5 结束语

利用遍历矩阵的性质，本文给出从HFEM公钥密码方案的公钥直接求解其等价私钥的多项式时间算法，从而破解了文献[14]设计的HFEM公钥密码方案。最后，通过计算示例演示HFEM公钥密码方案的破解过程。

[1] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5)：1484-1509.

[2] PROOS J, ZALKA C. Shor's discrete logarithm quantum algorithm for elliptic curves[J]. Quantum Information and Computation, 2003,3(4)：317-344.

[3] BUCHMANN J, DING J T. Post-quantum cryptography[A]. The Second International Workshop, PQCrypto 2008[C]. Cincinnati, USA, 17-19.

[4] 赵永哲, 黄声烈, 姜占华. GF(2k)上的遍历矩阵及其特性分析[J].小型微型计算机系统, 2005, 26 (12)：2135-2139.ZHAO Y Z, HUANG S L, JIANG Z H. Ergodic matrix over GF (2k)and its properties[J]. Mini-micro Systems, 2005, 26 (12)：2135-2139.

[5] ZHAO Y Z, WANG L O, ZHANG W. Information-exchange using the ergodic matrices in GF(2)[A]. 2nd International Conference, ACNS 2004[C]. Amsterdam： Icisa Press, 2004. 388-397.

[6] 赵永哲, 裴士辉, 王洪军等. 利用有限域上的遍历矩阵构造动态加密器[J]. 小型微型计算机系统, 2007, 28 (11)： 2010-2014.ZHAO Y Z, PEI S H, WANG H J, et al. Using the ergodic matrices over finite field to construct the dynamic encryptor[J]. Mini-Micro Systems, 2007, 28 (11)：2010-2014.

[7] PEI S H, ZHAO H W, ZHAO Y Z. Public key cryptography based on ergodic matrices over finite field[J]. Wuhan University Journal of Natural Sciences, 2006, 11(6)：1525-1528.

[8] 赵永哲，姜占华，黄声烈. 基于F2上遍历矩阵的Shamir三次传递协议的实现[J]. 小型微型计算机系统, 2006, 27(6)：986-991.ZHAO Y Z, JIANG Z H, HUANG S L. Implementation of Shamir’s three pass protocol based on ergodic matrix over finite field[J]. Mini-Micro Systems, 2006, 27(6)：986-991.

[9] 孙永雄，赵永哲, 杨永健等. 基于遍历矩阵的单向(陷门)函数的构造方案[J]. 吉林大学学报： 信息科学版, 2006, 24(5)：555-560.SUN Y X, ZHAO Y Z, YANG Y J, et al. Scheme to construct one-way (trapdoor) functions based on ergodic matrices[J]. Journal of Jilin University： Information Science Edition, 2006, 24(5)：555-560.

[10] MONICO C. Semirings and Semigroup Actions in Public-Key Cryptography[D]. Notre Dame： University of Notre Dame, 2002.

[11] MAZE G. Algebraic Methods for Constructing One-Way Trapdoor Functions[D]. Notre Dame： University of Notre Dame, 2003.

[12] 黄华伟.半群作用问题在密码学中的应用[D]. 西安： 西安电子科技大学, 2008.HUANG H W. Cryptographic Applications of Semigroup Action Problem[D]. Xi’an： Xidian University, 2008.

[13] 裴士辉,赵永哲,赵宏伟. 基于遍历矩阵的公钥加密方案[J]. 电子学报, 2010, 38(8)：1908-1913.PEI S H, ZHAO Y Z, ZHAO H W. Public key encryption scheme based on the ergodic matrices[J]. Chinese Journal of Electronics, 2010,38(8)：1908-1913.

[14] 赵永哲,赵博,裴士辉等. HFEM 公钥密码方案的设计与实现[J]. 通信学报,2011,32(6)：24-31.ZHAO Y Z, ZHAO B, PEI S H, et al. Design and implement on the HFEM public key scheme[J]. Journal on Communications, 2011,32(6)：24-31.

[15] HORN R A, JOHNSON C R. Matrix Analysis[M]. Cambridge University Press, 2005.