基于最大秩距离码的两种公钥密码系统  

Two Kinds of Public-key Cryptosystem based on Maximum Rank Distance Codes

作　　者：邓仰明[1] 杜伟章[1] 

机构地区：[1]湖南大学计算机与通信学院,湖南长沙410082

出　　处：《湖南大学学报（自然科学版）》2003年第3期102-104,107,共4页Journal of Hunan University:Natural Sciences

摘　　要：基于最大秩距离码,提出了两种新的McEliece公钥密码系统,明文x加密成xE+z,其中E=SGP,G为最大秩距离码C的生成矩阵,S为非奇异矩阵,在方案1中,P为置换矩阵,在方案2中,P为非奇异矩阵,z取自一给定的向量集合Z,公钥为Z和E.对方案1而言,解密过程约需O(k3)次运算,而需k×n×N·lnq/ln2比特存储空间;而对方案2而言,解密过程约需O(k3)+O(n3)次运算,需k×n×N·lnq/ln2比特存储空间.由于可取较小的k,n,所以这两个方案是可行的.攻击方案1和方案2的工作因子近似为k3·qt(k+n)-t2,n通过参数的选取,此数比攻击McEliece公钥密码系统的工作因子βk3k大得多.k/n-t所以这两个方案比基于纠错码构造的McEliece公钥密码系统更安全.Based on maximum rank distance codes,two new kinds of McEliece publickey cryptosystem are proposed.In the two schemes,a plaintext x is encrypted as xE+z,where E=SGP,G is a generator matrix of the maximum rank code C,S is a k×k invertible matrix,in the first scheme,P is a permutation matrix,in the second scheme,P is an invertible matrix,z is randomly chosen from Z, the public key is Z and E.For the first scheme,about O(k3) operations are wanted in the decrypt process,about k×n× N·lnq/ln2 bits are wanted for key storage.For the second scheme,about O(k3)+O(n3) operations are wanted in the decrypt process,about k×n× N·lnq/ln2 bits are wanted for key storage.Being able to use smaller k,n,the two schemes are feasible.The work factor for attacking the two schemes is about k3·qt(k+n)-t2,by selecting parameters,this number is far bigger than the work factor βk3nk/n-tk for attacking the McEliece publickey cryptosystem.Therefore,the two schemes are more secure than the McEliece publickey cryptosystem based on errorcorrecting codes.

关 键 词：秩距离码 纠错码 密码系统 安全性 

分 类 号：TP302.8[自动化与计算机技术—计算机系统结构]