计算机工程与科学COMPUTERENGINEERINGSCIENCE：1007730X(勿00)04・0004』2基于最大秩距离码的Niederreiter公钥密码系统TheNiederreiterPublic-KeyCryptosystemBasedonMaximumRankDistanceCodes(西安电子科技大学综合业务网国家亶点实验室)(NationalKeyLabofIntegratedServiceNetworksXidianUniversity)摘要：本文基于最大联距离码.提出了一种新的Niederreiter公钥密码系统•讨论了它的可行性及安全性并予以证明。Abstract:AnewkindofNiederreiterpublic-keycryptosystembasedonmaximumrankdistancecodesisproposed・Thefeasibilityandsecurityofthisschemearediscussedandprovedf关键词：业愛空迪密畸釦安全性血述押免益尺化Keywords:rankdistancecode；error-correctingcode；cryptosystem；security：TP302.8文献标识码：ADu1引言文献［1］提出了秩距离码及最大秩距离码的理论.对最大秩距离码进行了分类.文献［2］基于一般纠错码提出了一种公钥密码系统，称之为Niederreiter公钥密码系统：文献［3］对其安全性进行了分析。本文基于这种最大秩距离码提岀了—种新的Niederreiter公钥密码条统。由于秩及秩距离码的待点.可以通过选取较小的参数获得比较大的工作因子、从而可以減少密钥的存储空间・此外.已知的各种攻击方法及译码方法、不适于新的Niederreiter公钥密码系统，这样可保证此方案的可行性和安全性.2有关的定义及定理令X-表示域GF(qT上的n维向量空间・这里g为素数的幕。下面引入秩及秩距离码的槪念。定义I(1)设g…，工WGF(qf如果V+•••+©£=0蕴含c=C=・・・=G=0,则称xj,•••，工,在上线性无关：否则祢它们在GF(g)上线性相关.如果s，・y.€GF(qN)中有厂个在GF(q)上线性无关且任何厂+1个在GF(q)上都线性相关.则称X=Qi•…，N)在GF(g)上的秩为厂,X的秩标为厂(X)"(2)两个元索X,YEX-之间的秩距离d(X；Y)定义为:J(X；Y)：=r(X-Y).<3)X-的子集CH0称作码长为”的码，如果C是X•的维线性子空间,则称C是CM)线性码，码长为”・维数为八最小秩距离为N的线性码称作线性码。引理I⑴对任意线性码•秩距离满足d^n—及+1«,定义2⑴满足〃=总一及+1的线性［n.k.d'］*收稿日期:1999-11-SF修订日期：2000-01-06基金项目；高尊学松博士学科点专顶基金资助谍题(98070W4)作者筒介：杜伟章<1965-；-女・變士生、讲师.研社方两为通信与密码学，主要从事认证码与扶距离码的研究.通讯地址：710071映西省西安市两安电子科技大学综合业务网国家重点实验室^€1:(029)8207576Address:NationalKeyLabofIntegratedServiceNetworks.XidianUniversity.XiraaShaanxi710071R.China码称为谥大秩距离码。码的校验矩阵.而GFy)上”X”阶非奇异矩阵3方案的构造下面基于最大秩距离码.提出一种新的Niederreiter公钥密码系统。令C为GF0*)上一线性最大秩距离[宀氣d]码.它存在有效的译码算法。令H为码C的一个｛n-k)Xn阶校验矩阵。加密矩阵为E=SHP.其中S为GFlq"上随机的S—切X5—小阶非奇异矩阵、p为随机的阶置换矩阵。3.1加密满足条件r^)<LW-l)/2j的明文工WGF加密成密文$€GFWn它们之间满足，=琢32解密首先由y(ST)-1234=xPTHT解密密文刃其次.应用C的译码算法获得向量工“丁;最后通过计算UPT)F得出明文工，3、3密钥公钥为码的最小秩距离d和加密矩阵E以及y和？^私钥为矩阵S和"以及码C的校验矩阵4方案的可行性及安全性分析此方案的时间复杂性主要取决于(ST"的计算.(ST)7的计算需0(—次运算,与基于纠错码的Niederreiter公钥密码系统的时间复杂性一致.而密钥存储空间取决于(n-kyXn阶加密矩阵E的存储，也与文献[2]中的一致，所以此方案是可行的。下面考虑方案的安全性。首先■GFg)上G-QX(n-k)阶非奇异矩阵的总数为?匸处严右9一]片而GF(Q上•-1-k)阶非奇异矩阵的总数为-1],此数比/-I1(上揍第3页)捉考文献：2刘建就•聂于CA的公开寄钥管理惬架：[映七学位论文][D].南京；东南大学,19993IETFPKTXWG・InternetX.509PublicKeyInfrastructureRoadmap[ZJ.draftietf-pkix-xoadmap-OO.txt.1998.94IETFPKIXWG.InternetX.509PublicKeyInfrastructureCertificateandCRLProfile[ZJdrafr-ietf-ipkiartl-08.txt.1998.6El]IETFPKIXWG・Certif...