（通信与信息系统专业论文）基于编码理论的密码技术分析与设计.pdf

j ，王 口 ， r _ 了 j 1 ll l ii l ll ll ui i i ii ii 17 9 8 3 3 7 a n a l y s i sa n dd e s i g nf o rcr y p t o g r a p h i ct e c h n i q u eb a s e d o n e r r o rc o r r e c t i n gc o d e s d i s s e r t a t i o ns u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h ed e g r e eo f d o c t o ro fe n g i n e e r i n g b y ， z h a n gy i n g ( c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m ) d i s s e r t a t i o ns u p e r v i s o r ：p r o f e s s o ry u ed i a n w u a p r i l ，2 0 1 0 弋k y r t 0 ， ， 二 z 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士学位论文“基于编码理论的密码技术分析与设计 。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：为代缏 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密( 请在以上方框内打“，) 论文作者签名： 豕鬏 导师签名舞殿斌 日期：，汐d 年石月2 7 日 r t 创新点摘要 创新点摘要 纠错码与密码的结合一直都受到国内外通信与信息理论研究人员的重视。本 论文根据近年来加密与纠错码相结合的国内外研究进展与发展趋势，分别深入探 讨了纠错码在构造公钥密码体制、私钥密码体制、数字签名、秘密分享方案及认 证码等方案中的应用。论文主要创新点如下： 1 在m 公钥体制及其诸多变型的基础之上，提出一种利用代数几何码构造公 钥密码体制的新方法。新体制是一种由加密与纠错相结合的加密纠错体制。分析 表明，新体制在安全性、传信率、纠错能力以及正确解密概率等方面具有一定的 优势。 2 针对r a o - n a m 私钥密码体制修正案不具有纠错能力，传信率低，以及密钥 过长的缺点，提出了改进方案。新方案不仅增加了纠错功能，而且较好地解决了 传信率低以及长密钥等问题。此外，新方案同修正案相比，在安全性、有扰信道 的正确解密概率方面均有较大提高。 3 对邓仰明提出的基于纠错码的一种新数字签名方案进行分析，证明该方案 存在安全漏洞：任何人仅利用签名用户的公钥就可以破译部分私钥，从而成功的 实现伪造签名。然后以x i n - m e i 和e c p s 2 签名方案为例指出具有类似公钥构成的 数字签名体制都可以仅凭借公钥获取部分私钥。隆永红曾就这两个方案的安全性 进行过讨论，本文还指出该讨论中存在的两个错误认识。 4 在h w a n g 提出的基于r s a 的一个( f ，玎) 门限代理签名方案的基础之上，针 对该方案存在的安全弱点，提出一个新的改进方案。尽管该方案的若干改进方案 已经提出，然而安全弱点仍然存在。分析表明，新的改进方案能克服这些安全弱 点，因而更具安全性。此外，纠错能力的增加使该方案更有效。 5 对一般接入结构上的秘密分享方案进行研究，基于m d s 码提出了一类可 验证动态多重秘密分享方案的构造方法。该方案取消了分配中心，可有效防止秘 密分发者的欺骗。传输秘密时，可有效防止未授权方窃听；恢复秘密时，可有效 防止分享者欺诈。而且，可在一组分享者中同时分享多个秘密。此外，该方案有 效地解决了秘密的更新问题，效率高而且实用。 r 一 ， 臼 中文摘要 摘要 1 9 7 6 年，d i f f i e 与h e l l m a n 在一篇题为“密码学的新方向”的论文中，首次提 出了“公钥密码”的概念，从而为现代密码学的产生和发展树立了里程碑。1 9 7 8 年，b e r l e k a m p 等人证明了一般线性码译码是n p c 难题。基于这一事实以及g o p p a 码的特点，m c e l i e e e 首次利用纠错码构造出一类公钥密码体制，即m 公钥体制， 从而开创了纠错码在现代密码学中的新的研究领域。如今，如何将加密技术与纠 错技术进行有效结合已成为现代密码学研究的的一个重要课题。本文主要探讨了 纠错码在现代密码学中的五个方面的应用。具体研究工作如下： 1 基于纠错码的公钥密码体制的研究工作主要包括： ( 1 ) 现有代数几何码的译码算法主要集中于一点代数几何码，为此，x i n g 针 对广义r s 码给出译码算法。本文在x i n g 工作基础之上给出几何g o p p a 码的一种 译码算法。同一点代数几何码译码相比该译码算法更为一般，且算法简单，便于 理解与实现。 ( 2 ) x i n g 提出用来选择特殊除子的条件，任何人依据此条件能得到获得g v 界的代数几何码。本文通过构造一个线性方程组，计算范德蒙矩阵的逆，以及解 决两个计数问题，将上述条件改进，结果能得到更多的获得g v 界的代数几何码。 ( 3 ) 提出一种利用代数几何码构造公钥密码体制的新方法，该体制是一种由 加密与纠错相结合的加密纠错体制。经过分析，该方法同m 公钥体制及其诸多变 型相比，在安全性、传信率、纠错能力以及正确解密概率等方面具有一定的优势。 2 基于纠错码的私钥密码体制的研究工作主要包括： 针对r a o n a m 私钥密码体制修正案进行分析及推广。首先考虑密文通过有扰 信道的情况下，对修正案进行推广，提出了加密与纠错相结合的加密纠错体制。 其次利用错误图样携带附加信息的方法提高了修正案的传信率。分析表明该推广 方案同修正案相比，在安全性、纠错能力、传信率、有扰信道的正确解密概率以 及长密钥问题等方面均有很大的改进。 3 基于纠错码的数字签名的研究工作主要包括： ( 1 ) 邓仰明等对基于纠错码构造的x i n - m e i 修正方案提出了一种新的数字签 中文摘要 名方案。本文首先证明该方案存在安全漏洞：即任何人仅利用签名用户的公钥就 可以破译部分私钥，从而成功的实现伪造签名。然后以x i n - m e i 和e c p s 2 签名方 案为例指出具有类似公钥构成的数字签名体制都可以仅凭借公钥获取部分私钥。 隆永红对上述两个方案的安全性进行过讨论，并提出一种伪造签名的办法，本文 还指出该讨论中存在两个错误认识。 ( 2 ) h w a n g 基于r s a 提出一个o ，押) f - j 限代理签名方案。然而该方案存在安 全弱点。尽管该方案的改进方案已经提出，然而上述安全弱点仍然存在。为了克 服这些弱点，本文提出一个改进的门限代理签名方案，分析表明本文方案同其它 方案相比更安全，更有效。而且，该方案可灵活选择纠错能力来适应不同应用环 境的需要。 4 基于纠错码的秘密分享方案的研究工作主要包括： 对一般接入结构上的秘密分享方案进行研究，基于m d s 码给出了一类可验证 动态多重秘密分享方案的构造方法。该方案取消了分配中心，可有效防止秘密分 发者的欺骗。传输秘密时，可有效防止未授权方窃听；恢复秘密时，可有效防止 分享者欺诈。该方案可在一组分享者中同时分享多个秘密。此外，该方案有效地 解决了秘密的更新问题，这使得该方案更高效更实用。 5 c a r t e s i a n 认证码的研究工作主要包括： 利用有限域上向量空间构作了一类简易c a r t e s i a n 认证码，并且计算了它们的参 数。在假设编码规则是按均匀概率分布选取条件下，计算了模仿攻击成功的概率p t 和替换攻击成功的概率r 。 关键词：纠错码；公钥密码体制；私钥密码体制；数字签名；秘密分享方案； c a r t e si a n 认证码 _ ， 英文摘要 a b s t r a c t i n19 7 6 ，d i f f i ea n dh e l l m a n f i r s t l yp r o p o s e d t h e c o n c e p t p u b l i c - k e y c r y p t o s y s t e m i nap a p e re n t i t l e d n e wd i r e c t i o n si nc r y p t o g r a p h y ，w h i c hp l a y sa n i m p o r t a n tr o l ei nt h ee m e r g e n c ea n dd e v e l o p m e n to fm o d e mc r y p t o g r a p h y i n19 7 8 ， b e r l e k a m ps h o w e dt h a tt h ed e c o d i n go f t h eg e n e r a ll i n e a rc o d e si san p ch a r dp r o b l e m i nt h es a m ey e a r , a c c o r d i n gt o t h i sf a c ta n dt h ec h a r a c t e r i s t i c so fg o p p ac o d e s ， m c e l i e c ep r o p o s e dt h ef i r s tp u b l i c - k e yc r y p t o s y s t e m ( t h em c e l i e c es c h e m e ) b a s e do n a l g e b r a i cc o d i n gt h e o r y ，w h i c hu n c o v e r st h ea p p l i c a t i o np r o s p e c t so fe r r o rc o r r e c t i n g c o d e si nm o d e r nc r y p t o g r a p h y c o n s i d e r i n gt h ed e v e l o p m e n tt e n d e n c ya n di m p o r t a n c e f o rt h ec o m b i n a t i o ne n c r y p t i n gw i t ht h ec a p a b i l i t yc o r r e c t i n ge r r o r ，t h i sd i s s e r t a t i o n g i v e ss e v e r a li m p o r t a n ta p p l i c a t i o n so fe r r o rc o r r e c t i n gc o d e si nm o d e mc r y p t o g r a p h y d e t a i l e dc o n t e n t sa r el i s t e da sf o l l o w s ： 1 r e s e a r c h e so np u b l i c k e yc r y p t o s y s t e mb a s e do ne r r o rc o r r e c t i n gc o d e si n c l u d e ： ( 1 ) e x i s t i n gd e c o d i n ga l g o r i t h m so fa l g e b r a i c g e o m e t r i cc o d e sm a i n l yf o c u s e do n o n e p o i n ta l g e b r a i c - g e o m e t r i cc o d e ，t h e r e f o r e ，x i n gg a v e ad e c o d i n ga l g o r i t h mo f g e n e r a l i z e dr sc o d e s b a s e d o nx i n g sw o r k , a na l g o r i t h mo fd e c o d i n gg o p p a g e o m e t r i cc o d e si so b t a i n e d i nt h i sd i s s e r t a t i o n d i f f e r e df r o mt h et r a d i t i o n a ld e c o d i n g a l g o r i t h r no fo n e - p o i n ta l g e b r a i c - g e o m e t r i cc o d e s ，t h i sd e c o d i n ga l g o r i t h mi sm o r e g e n e r a l m o r e o v e r , t h ed e c o d i n ga l g o r i t h mi se a s yt ou n d e r s t a n da n di m p l e m e n t ( 2 ) b yc o n s t r u c t i n gas y s t e mo fl i n e a re q u a t i o n s ，c o m p u t i n gt h ei n v e r s eo f v a n d e r m o n d em a t r i c e sa n ds o l v i n gt w oc o u n t i n gp r o b l e m s ，ac o n d i t i o no fx i n gu s e dt o c h o o s es p e c i f i cd i v i s o r s ( u s i n gw h i c ho n ec a ng e tg o p p ag e o m e t r i cc o d e sa c h i e v i n gt h e g i l b e r t v a r s h a m o vb o u n d ) i si m p r o v e d c o n s e q u e n t l y ，m o r eg o p p ag e o m e t r i cc o d e s a c h i e v i n gt h eg i l b e r t v a r s h a m o vb o u n dc a nb eo b t a i n e d ( 3 ) ap u b l i c - k e yc r y p t o s y s t e mb a s e do na l g e b r a i cg e o m e t r i cc o d e si sp r o p o s e d t h ec r y p t o s y s t e mi sap u b l i c - k e ys y s t e mc o m b i n e dw i t he r r o rc o r r e c t i n gc a p a b i l i t y c o m p a r e dw i t hmp u b l i c - k e ys y s t e ma n ds o m ev a r i a n t s ，t h ep e r f o r m a n c eo ft h e p u b l i c k e yc r y p t o s y s t e mi sa n a l y z e d i ti ss h o w nt h a tt h es e c u r i t y , i n f o r m a t i o nr a t e ， e r r o rc o r r e c t i n gc a p a b i l i t y , a n dp r o b a b i l i t yo fc o r r e c td e c i p h e ra r ei m p r o v e d 2 r e s e a r c h e so np r i v a t e k e yc r y p t o s y s t e mb a s e do ne r r o rc o r r e c t i n gc o d e si n c l u d e ： t h er e v i s e ds c h e m eo fr a o n a m sp r i v a t e - k e y c r y p t o s y s t e mi s 觚a 1 ) ，z c da n d g 锄e r a l i z e d w h e nt h e c i p h e r t e x ti st r a n s m i t t e dt h r o u g hi n t e r f e r e n c ec h 锄1 e l s t h e r e v i s e ds c h e m ei s g e n e r a l i z e da n dap r i v a t e - k e yc r y p t o s y s t e mw i t he n o r c 0 玎e “n g c a p a b i l i t yi sp r o p o s e d i na d d i t i o n ，t h e i m p r o v e du s i n gt h ea d d e de r r o rv e c t o rt o i n f o r m a t i o nr a t eo ft h er e v i s e ds c h e l l l ei s c a r r ya d d i t i o n a li n f o r m a t i o n i ti ss h o w nt h a t t h eg e n e r a l i z e ds c h e m ei sb e t t e rt h a nt h eo r i g i n a lr e v i s e ds c h e r n ei nm e s e c u n t v 锄r c o 盯e c t i n gc a p a b i l i t y , i n f o r m a t i o nr a t e ，p r o b a b i l i t yo f c o r r e c td e c i p h e r ，a n di o n gk e ：y s 3 r e s e a r c h e so nd i g i t a ls i g n a t u r es c h e m e b a s e do ne r r o rc o 揪t i n gc o d e si n c l u d e ： ( 1ja i m i n ga tt h em o d i f i e ds c h e m eo fx i n m e i s i g n a t u r es c h 锄eb a s e do n 锄r c o 玎e c t i n gc o d e s ，d e n gy a n g m i n g p r e s e n t san e wd i g i t a ls i 盟a t u r es c h e i i l e i i lt h i s m s s e n a t i o n ，i ti ss h o w nt h a tt h e r ee x i s t sal e a ki nt h i sd i g i t a ls i g n a t u r es c h 锄e ：a 1 1 v o n e c 觚o b 觚p a r t i a ls e c r e tk e yo n l yr e s o r t i n gs i g n a t o r y 。p u b l i ck e y , t h e r e f o r e h em a v s u c c e s s f u l l yf o r g eas i g n a t u r e t h e n ，a sa l le x a m p l eo fx i n - m e ia n de c p s 2s i 蛆a t u r e s c n 锄e s ，1 tp o i n t so u t ，f o rt h ed i g i t a ls i g n a t u r es c h e m e sw h o s e d e s i g no fp u b l i ck e yi s s l m i l a rt ot h ea b o v ep r o p o s e ds c h e m e , a n y b o d y c a l la c h i e v ep a r t i a ls e c r e tk e yi u s tb y 眦p l o y i n gp u b l i ck e y l o n gy o n g h o n gh a dd i s c u s s e da b o u tt h es e c u 】研o ft h e 咖 s c n 锄e s ，a n dp r o p o s e dam e t h o df o rf o r g i n gs i g n a t u r e i nt h i sd i s s e r t a t i o i l ，w ei n d i c a t e t h a tt h e r ea let w o w r o n gc o g n i t i o n si nt h i sd i s c u s s i o n h w a n ge ta l p r o p o s e dap r a c t i c a l o ，刀) t h r e s h o l dp r o x ys i 印a t u r es c h 锄e b a s e do nt h er s a c r y p t o s y s t e m h o w e v e r ，t h es c h e m eh a ss e v e r a ls e c 嘶锣w e a k - n t 藩s e s p o i n t e do u tb yw a n ge ta l i no r d e rt oo v e r c o m et h es e c u r i t yi s s u e s o ft h ee x i s t i n g 姐e s n o j dp r o x ys i g n a t u r es c h e m e s ，w ep r o p o s ea n i m p r o v e do ，玎) t h r e s h o l dp r o x v s l g n a t u r es c h e m e , a n dd e m o n s t r a t et h a to u rs c h e m ei sm o r es e c u r e 觚de 仃e “v e 、池e 1 1 c o m p 删t oh w a n g 。s c h e m ea n do t h e r s m o r e o v e r , t h ep r o p o s c ds c h 锄eh a sa 1 1 o p t i o n a lc a p a b i l i t yo ff a u l tt o l e r a n c et ob a l a n c et h es c a l a b i l i t yu n d e r d i 佰溯1 ts i n l a t i o n s 4 r e s e so ns e c r e ts h a r i n gs c h e m eb a s e d o ne r r o r c o r r e c t i n gc o d e si n c l u d e ： s e c r e ts h a n n go n g e n e r a la c c e s ss t r u c t u r e sw a ss t u d i e d am e t h o do fe o n s t n j c t i n g g 朗酬i z e d v e r i f i a b l e 。d y n a m i cm u l t i s e c r e t s h a r i n gw a s 酉v 髓n es c h 锄e 锄u l s d e 引e r , a n dt h u si tc a l lp r e v e n tt h ed e a l e rf r o mc h e a t i n g w h e i lt h es e c r e t w a sb e i n g 蚴哩s m l t t e d ，t h es c h e m ec a np r o t e c tt h es e c r e tf r o ml i s t e n e ra t t a c k i n 舀a i l dt h es u p p l yo f t a i s es n 羽n e smt h ep r o c e s so fs e c r e tr e c o v e r yc a l lb ep r e v e n t e d i nt h es c h 锄e m u l t i p l e ， 白 英文摘要 s e c r e t sc a i lb es h a r e da tt h es a m et i m ei nag r o u po fs h a r e h o l d e r s i na d d i t i o n ，t h e s c h e m ee f f i c i e n t l yr e s o l v e st h ep r o b l e mo fs e c r e tr e n e w i n g t h u si ti se f f i c i e n ta n d p r a c t i c a l 5 r e s e a r c h e so nc a r t e s i a na u t h e n t i c a t i o nc o d e si n c l u d e ： o n ec o n s t r u c t i o no fc a r t e s i a na u t h e n t i c a t i o nc o d e sf r o mv e c t o rs p a c eo v e rf i n i t e f i e l d si sp r e s e n t e da n di t ss i z ep a r a m e t e r sa r ec o m p u t e d u n d e rt h ea s s u m p t i o nt h a tt h e c h o s e no fe n c o d i n gr u l e sa n ds o u r c es t a t e s0 b e yu n i f o r mp r o b a b i l i t yd i s t r i b u t i o n , t h e p r o b a b i l i t i e s a n db o fas u c c e s s f u l i m p e r s o n a t i o na t t a c k a n das u c c e s s f u l s u b s t i t u t i o na t t a c ko ft h e s ec o d e sa r ea l s oc o m p u t e dr e s p e c t i v e l y k e yw o r d s ：e r r o rc o r r e c t i n gc o d e s ；p u b l i c - k e yc r y p t o s y s t e m ；p r i v a t e - k e y c r y p t o s y s t e m ；d i g i t a ls i g n a t u r e ；s e c r e ts h a r i n g ；c a r t e s i a na u t h e n t i c a t i o nc o d e s - ，饵 目录 目录 第l 章绪论1 1 1 引言1 1 2 密码学概述2 1 2 1 系统模型。2 1 2 2 密码体制和密码系统模型3 1 2 3 密码分析4 1 2 4 保密系统的保密性5 1 3 纠错码概述6 1 3 1 码的生成矩阵、校验矩阵与对偶码6 1 3 2h a m m i n g 重量、距离及码的纠错能力7 1 3 3 线性分组码的性能限8 1 3 4 纠错码理论中的n p c 问题9 1 4 论文的研究目的与意义l o 1 5 本文的结构安排和研究内容1 0 第2 章基于纠错码的公钥密码体制1 3 2 1 引言13 2 2 代数几何码的译码。1 4 2 2 1 代数曲线的基本概念1 4 2 2 2 代数几何码15 2 2 3 代数几何码的译码1 6 2 3 更多的获得g i l b e r t v a r s h a m o v 界的代数几何码2 0 2 3 1 有理除子数量的精确值2 1 2 3 2 代数几何码参数的重新估计2 5 2 3 3 主要结果2 9 2 4 基于代数几何码的公钥密码体制3 0 2 4 1 代数几何码的编码、译码方法3 0 2 4 2 基于代数几何码的公钥密码体制3 1 2 4 3 安全性分析3 2 2 4 4 性能分析3 7 2 5 本章小结3 9 目录 第3 章基于纠错码的私钥密码体制4 1 3 1 引言4 1 3 2r a o n a m 私钥密码体制修正案的推广4 2 3 2 1r a o n a m 私钥密码体制方案及其修正方案4 2 3 2 2r a o - n a m 私钥密码体制修正案的推广4 3 3 2 3r a o - n a m 私钥密码体制推广方案的性能分析4 3 3 3 本章小结一5 1 第4 章基于纠错码的数字签名体制5 3 4 1 引言5 3 4 2 基于纠错码的一种数字签名的分析一5 4 4 2 1 基于最大秩距离码的一类数字签名方案5 4 4 2 2 基于最大秩距离码的数字签名方案的分析5 5 4 2 3 基于x i n m e i 和e c p s 2 签名方案的分析5 8 4 3 具有容错功能的( f ，刀) 门限代理签名方案6 0 4 3 1 基于r s a 的门限代理签名方案6 2 4 3 2 基于r s a 的具有容错功能的数字签名方案6 3 4 3 3 具有容错功能的( ，n ) f - j 限代理签名方案6 6 4 3 4 对新方案的安全性和性能进行分析7 3 4 4 本章小结。7 8 第5 章基于纠错码的秘密分享方案7 9 5 1 引言7 9 5 2 基于m d s 码的广义可验证动态多重秘密分享方案8 0 5 2 1 基于线性码的秘密分享8 0 5 2 2 广义密钥分享系统8 1 5 2 3 基于m d s 码的广义可验证动态多秘密分享方案8 2 5 2 4 安全性及性能分析8 4 5 3 本章小结8 5 第6 章简易c a r t e s i a n 认证码的构造8 7 6 1 引言8 7 6 2 构作有限域上向量空间中的一类简易c a r t e s i a n 认证码8 7 6 2 1 构造简易c a r t e s i a n 认证码8 8 6 2 2 计算模仿攻击概率和替换攻击概率8 9 6 3 本章小结9 3 、 目录 第7 章总结与展望9 5 7 1 全文总结9 5 7 2 未来工作展望。9 6 参考文献9 7 附录av a n d e r m o n d e 矩阵的求逆计算1 0 5 攻读学位期间公开发表论文10 9 至| 【谢。11 1 ， 基丁编码理论的密码技术分析与设计 第1 章绪论 1 1 引言 随着通信技术的发展和互联网的普及，信息共享应用日益广泛和深入，但同 时信息安全问题也日渐突出和复杂。一些非常重要的信息在传输过程中不仅要有 很好的保密性，还要有一定的容错性能。 文件的密码保护和认证【3 ，4 】，图像编码【5 】， 例如在生物特征数据保护【1 捌，数字生成 移动代理【6 】，在线服务【7 】，离线服务【8 】， 医疗服务【9 】等系统中。信息系统的安全性和可靠性是信息化顺利发展的两大关键问 题，因为安全性和可靠性对整个系统的正常运行、管理和发展都起着至关重要的 影响。传统上，我们可以先对信息加密，再将加密信息送到编码器，经纠错编码 使密码具有容错能力。但是，这种分两步操作的方法，一方面增加了系统的复杂 性，另一方面会产生一定的时延。为了克服上述不利因素，纠错密码技术应运而 生。将编码和加密结合成一个基元( p r i m i t i v e ) 至少有以下优点【l o 1 1 】：1 ) 分开执行编 码和加密对于许多无线终端设备而言( 如p d a ，手机) 可能被证明计算过于集中， 而结合成一个基元能改善这种现象；2 ) 由于加密和编码可在数据链路层进行操作， 所以设计一个容加密和纠错于一体的单一操作会更有效，这样纠错和加密可在同 一层执行( 如在无线网络中的链路层) ；3 ) 在有噪声媒介( 如无线网络) 中，纠 错和加密的个联合设计比起传统的独立操作方法能获得一个更好的系统级操作 点( s y s t e ml e v e lo p e r a t i n gp o i n t ) ，这对于日益流行的资源受限的设备来说可望从中 获益。4 ) 能提供有效而安全的通信以及成本很低的信息存贮。 目前公认的有三种加密纠错实现方法【1 2 】：第一种是利用g o p p a 码的m c e l i e c e 公钥密码体制，第二种是利用d 一序列的k a k 加密纠错码，第三种是最近发展起来 拟群随机纠错码( q u a s i g r o u pr a n d o me r r o r c o r r e c t i n gc o d e s ) 。而其中对第一种的研究 最为广泛。1 9 7 8 年，m c e l i e c e 利用一般线性码的译码问题是一个n p c 问题【1 3 】和 g o p p a 码有快速译码算法的特点最早提出了一个基于纠错码的公钥密码体制【l 4 1 。 利用纠错码建立密码体制有以下优点：1 ) 具有快速加解密的优点；2 ) 纠错码都 已经存在于通信设备中，因而从实现的角度，可以利用通信系统，计算机系统中 第1 章绪论 现有的纠错码编、译码器，经过参数的适当调整，便可用来构造公钥、私钥体制， 实现对密钥的分散管理或对消息的认证，因此利用码字作为一个密码的建构基础 是明智的；3 ) 基于纠错码的密码体制大多是概率型体制，即对同一明文可以对应 许多完全不同的密文，从而能极大提高已知密文明文对攻击的难度。从此以后， 国内外很多学者利用纠错码的特点和理论构造了各种各样的公钥密码体制，数字 签名方案，秘密共享方案，认证码等，纠错码和密码相结合的研究得到了迅速的 发展。从而开创了纠错码在现代密码学中的应用前景。 1 9 8 6 年，英国的数学与应用协会主办了一次“密码学与编码”会议1 5 】。英国、 德国及美国的学术界、工业、政府部门的第一流的研究人员为会议撰写了2 0 篇论 文。本次会议旨在将对密码学和编码理论进行研究的数学家们聚集到一起。尽管 这两个应用需要的工具和技术是相似的，但他们倾向于作为不同学科。在许多应 用场合，将这两步处理结合起来具有许多优点。在本次会议上发表的论文是实现 这些目标的开始。1 9 9 7 年，美国国家科学基金会认识到将两个研究团体结合的必 要性，为了面对密码和编码的共同问题，来自这两个领域的最杰出的研究学者们 组建成一个工作组。针对纠错和密码结合的几个场景作了工作报告【1 6 】。近年来， 越来越多的学者开始关注这个问题【1 7 , 1 8 , 1 9 2 0 2 1 2 2 1 。 本文根据近年来加密与纠错码相结合的国内外研究背景及进展，探讨了纠错码 在现代密码学，尤其是在构造公钥、私钥密码体制，数字签名，秘密分享方案及 认证码等方案中的一系列重要应用，最后指出了几个有待继续研究的课题。 1 2 密码学概述 1 2 1 系统模型 所有信息传输、存储系统如通信以及计算机通信网中的信息传输以及计算机 的内外存储系统和内部运算等，都可归结成如图1 1 所示的数字通信系统模型【2 3 1 。 基于编码理论的密码技术分析与设计 图1 1 数字通信系统模型 f i 9 1 1d i g i t a lc o m m u n i c a t i o ns y s t e mm o d e l 信息传输目的是要把收方不知道的信息及时、可靠、完整、安全而又经济地 传送给指定的收方。图1 1 中所描述的整个系统的各个部分就是为了完成上述目 的。如何设计图1 1 所示的通信系统中的各部分，使整个系统达到最佳，这是系 统设计者所关心的重要问题。通常情形是对系统的各个部分单独设计的。但自7 0 年代中期以来，人们开始注意把通信系统的几个部分看成一个整体进行综合设计， 以使系统达到最佳。如信源编码与纠错码相结合的设计，尤其是纠错码与调制相 结合的t c m 技术等。那么，是否可以将纠错码与密码结合在一起考虑，以便设计 出一种既能保护信息的可靠性，又能保护信息完整性与安全性的系统呢? 这也正 是本文所考虑的问题。 1 2