（基础数学专业论文）代理签名方案的分析与探索.pdf

摘要 面对飞速发展的信息产业，信息安全不容忽视，五花八门的病毒 侵袭，防不胜防的黑客进入，都会使你的计算机在顷刻问受到破坏或 信息被盗。轻者计算机程序破坏，重做程序，影响正常工作和计算机 内原有的部分信息有可能丢失，重则导致国家安全受到严重的威胁， 造成不可估量的损失。信息安全的核心技术足密码学，其r f l 公钥密码 由于其具有传统密码无法比拟的一些优势，扮演着越来越重要的角 色。以公钥密码为基础的数字签名作为手写签名在数字文件中的合法 模拟物将广泛应用。各种各样的应用背景对数字签名提出了多种多样 的要求。面对这些要求，具有各种特性的数字签名方案相续提出，形 成了多个值得关注的研究方向，而代理签名就是其中典型的一种。代 理签名就是原始签名人将签名权利授权代理签名人，代理签名人根据 授权代表原始签名人产生一个有效的代理签名，代理签名的接收方验 证代理签名的同时验证授权信息。 数字签名的安全性一直困扰着密码学家，如何设计一个安全的数 字签名方案不仅对数字签名的研究还是对国家安全都有重要的意义。 本文就是研究代理签名方案的分析与探索。主要工作如下： 1 、阐述了数字签名在信息安全中的重要地位，介绍了数字签名的 基本性质及安全性条件，攻击类型。 2 、介绍了盲签名和代理签名，然后重点介绍盲签名和代理签名的 综合体代理盲签名。谷利泽等人提出了一个代理盲签名方案。在本文 中，我们指出这个代理盲签名方案不安全，原始签名人可以对这个方 案进行伪造攻击，进而冒充代理签名人对用户的信息进行签名，从而 侵犯了代理签名人的利益。而且这个方案不满足不可链接性。 3 代理多重盲签名是代理盲签名的延伸和扩展，被授权的代理签 名者代替多个原始签名者进行签名。陆荣幸等人提出了一个不需要安 全渠道的代理多重盲签名方案。本文提出了针对此方案的安全性分 析，其中采用了构造方法证明了这个方案不安全，不满足不可伪造性 和不可链接性，不能用于电子商务，电子货币，电子投票等系统。否则 系统是不安全的。 关键词信息安全，密码学，数字签名，代理签名，代理盲签名， 代理多重签名 1 1 a bs t r a c t i nt h ef a c eo f r a p i dd e v e l o p m e n t o fi n f o r m a t i o n i n d u s t r y , i n f o r m a t i o ns e c u r i t yc a nn o tb ei g n o r e d ，t h ep r o l i f e r a t i o no fv i r u sa t t a c k s ， h a r dt op r e v e n th a c k e ra c c e s st oy o u rc o m p u t e rw i l lb ee n g r a v e di nt h e t i l tb e t w e e nt h ed a m a g e do ri n f o r m a t i o nt h e f t l i g h tb yac o m p u t e r p r o g r a md e s t r u c t i o n ，r e d op r o c e d u r e s ，a f f e c tt h e n o r m a lw o r ka n dt h e c o m p u t e r sw e r eo r i g i n a l l yp a r to ft h ei n f o r m a t i o nm a yb em is s i n g ，e v e n r e s u l t i n g i ns e r i o u st h r e a t st on a t i o n a l s e c u r i t y , r e s u l t i n g i na n i m m e a s u r a b l el o s s c r y p t o g r a p h yi st h ec o r eo fi n f o r m a t i o ns e c u r i t y t e c h n o l o g y p u b l i c k e yc r y p t o g r a p h yp l a y sa ni n c r e a s i n g l yi m p o r t a n tr o l e b e c a u s eo fi t sa d v a n t a g e s b e i n gal e g a lr e p l a c e m e n tf o rh a n d w r i t t e n s i g n a t u r e s ，d i g i t a ls i g n a t u r ew h i c hi sb a s e do np u b l i c - k e yc r y p t o g r a p h yi s s u r et ob em o r ee x t e n s i v e l yu s e di nt h ec o m i n gy e a r s u n d e rt h ev a r i o u s a p p l i c a t i o nb a c k g r o u n d s ，m a n ys p e c i a ld i g i t a ls i g n a t u r e sw e r ep r o p o s e d a n ds e v e r a lr e s e a r c hd i r e c t i o n sc o m ei n t ob e i n g p r o x ys i g n a t u r ei sa t y p i c a lo n e t h ep r o x ys i g n a t u r ei sas i g n a t u r es c h e m et h a ta no r i g i n a l s i g n e rd e l e g a t e sh i so rh e rs i g n i n gc a p a b i l i t yt oap r o x ys i g n e r , a n dt h e n t h ep r o x ys i g n e rc r e a t e sav a l i ds i g n a t u r eo nb e h a l f o ft h eo r i g i n a ls i g n e r t h er e c e i v e ro ft h es i g n a t u r ev e r i f i e st h es i g n a t u r ei t s e l fa n dt h eo r i g i n a l s i g n e r sd e l e g a t i o nt o g e t h e r s of a r , m a n yp r o x ys i g n a t u r es c h e m e sa n d c r y p t o g r a p h yp r o t o c o l sb a s e do nt h e mh a v eb e e np r o p o s e d t h es e c u r i t y o fd i g i t a ls i g n a t u r eh a sb e e nt r o u b l i n gc r y p t o g r a p h e r s h o wt od e s i g na s e c u r i t yd i g i t a ls i g n a t u r ep l a y sa ni m p o r t a n tr o l en o to n l yi nt h er e s e a r c h o fd i g i t a l s i g n a t u r e b u ta l s oi nt h e s e c u r i t y o fo u rc o u n t r y t h i s d i s s e r t a t i o nm a i n l ys t u d yt h ea n a l y s i sa n dd e s i g no fd i g i t a ls i g n a t u r e o u r c o n t r i b u t i o n ： 1t h i sd i s s e r t a t i o ns u r v e y st h ei m p o r t a n ts i g n i f i c a n c eo fd i g i t a l s i g n a t u r e i nt h ei n f o r m a t i o n s e c u r i t ys y s t e m sa n d i n t r o d u c e st h e p r o p e r t i e sa n dr e q u i r e ds e c u r i t i e s ，a t t a c k i n gt y p e s 2 t h r o u g hr e s e a r c h i n g t h e t h e o r yo fp r o x ys i g n a t u r ea n db l i n d s i g n a t u r e ，w eg e tp r o x yb l i n ds i g n a t u r e ap r o x yb l i n ds i g n a t u r es c h e m e i sas i g n a t u r ew h i c hc o m b i n e st h ep r o p e r t i e so fp r o x ys i g n a t u r ea n db l i n d s i g n a t u r e r e c e n t l y ，g ue ta 1 p r e s e n t e dap r o x yb l i n ds i g n a t u r e i nt h i s p a p e r ，w ep o i n to u tt h a tt h i ss c h e m ei sn o ts e c u r ea n dt h eo r i g i n a ls i g n e r c a nf o r g et h es c h e m e t h eo r i g i n a ls i g n e rc a ng i v eav a l i ds i g n a t u r ef o r m e s s a g e s oo r i g i n a ls i g n e ri n t r u d et h er i g h t so ft h ep r o x ys i g n e r a n dt h e s c h e m ec a n n o tr e s i s tl i n k a b i l i t ya t t a c k 3 a p r o x y b l i n d m u l t i - s i g n a t u r ei s ae x t e n s i o no fp r o x yb l i n d m u l t i s i g n a t u r e ，w h i c ha ll o wt h ed e s i g n a t e dp r o x ys i g n e rt og e n e r a t ea s i g n a t u r eo nb e h a l fo fs e v e r a lo r i g i n a ls i g n e r s r e c e n t l y , l ue ta 1 p r o p o s e dap r o x yb l i n dm u l t i s i g n a t u r es c h e m ew i t h o u tas e c u r ec h a n n e l i nt h i sp a p e r w eg i v et h es e c u r i t ya n a l y s i so ft h ep r o x yb l i n ds i g n a t u r e s c h e m ew i t ht h em e t h o do fc o n s t r u c t i o n i nt h ee n d w es h o wt h a tl ue t a 1 p r o x y b l i n ds i g n a t u r es c h e m ei sn o ts e c u r e t h es c h e m ed o e sn o t s a t i s f yt h ep r o p e r t i e so fu n f o r g e a b i l i t ya n du n l i n k b i l i t y s ot h ep r o x y b l i n ds i g n a t u r ec a nn o tb ea p p l i e dt oe c o m m e r c e ，e c a s ha n de - v o t i n g s y s t e m o t h e r w i s e ，t h es y s t e mi sn o ts e c u r e k e yw o r d si n f o r m a t i o ns e c u r i t y , c r y p t o g r a p h y , d i g i t a ls i g n a t u r e ， p r o x ys i g n a t u r e ，p r o x ys i g n a t u r e ，p r o x yb l i n dm u l t i s i g n a t u r e ； i v 硕+ 学位沦文第一章绪论 1 1 研究背景 第一章绪论 目前，随着整个社会信息化的飞速进程，安全问题日益凸显：每年由各类安 全事件造成的损失数以亿计，其中既包括来自外部的威胁，例如蠕虫、黑客、问 谍软件、网上欺诈的攻击，也包含内部人员的违规操作或者恶意破坏，对于事关 国计民生的政府机关来说，这些安伞威胁已经严重影响到当自订的经济以及社会的 稳定，而且会影响深远，甚至危及国家安全。而信息安全也已经形成个巨大的 产业，不过，由于信息安全行业的发展时问还比较短，因此还存在着这样那样的 问题，另一方面，商业公司掌握着信息安全的最自订沿技术，因此只注重商业竞争， 忽略了安全管理。从企业的观点来看，安全就是安全产品的不断升级，而从整个 产业的角度来看，安全产品无论如何升级都只能起到缩小安全边界的作用，并不 能杜绝安全隐患，而要想实现真j 下意义上的安全，就要出台相应的安全管理规范， 实行进行自下而上的安全管理。信息安全技术涉及信息论、计算机科学和密码学 等多方面知识，它的主要任务是研究计算机系统和通信网络内信息的保护方法以 实现系统内信息的安全、保密、真实和完整，其中，信息安全的核心是密码技术， 密码技术除了提供信息的加密解密外，还提供对信息来源的鉴别、保证信息的完 整和不可否认等功能，而这三种功能都是通过数字签名来实现的。 数字签名一种以电子形式存储的信息签名方式，所以签名之后的消息能通过 计算机网络的传输。随着科技的发展和社会的进步，计算机已经广泛应用到社会 的各个领域，从而促进了网络通信技术的产生和发展。网络通信虽然促进和加速 社会信息化的发展，但是网络环境下的信息安全并不令人乐观，由于技术原因和 人为攻击等因素，网络通信的安全性受到严重的威胁，信息在传输的过程中有可 能被删除、篡改和重放，给人们的生活和工作造成了许多麻烦。j 下是在这种情况 下，数字签名技术便应运而生了，手写签名是所签署文件的物理部分，数字签名 的算法是以某种形式将签名“附加”到所签的电子文件之上。数字签名作为一种 保障信息安全的有效手段，它可以保证信息完整性、鉴别发送身份真实性和不可 否认性，同时还具有加密的功能。数字签名必须满足手写签名的五个特性：无法 硕十学位沦文第一章绪论 伪造性、真实性、不可重用性、不可修改性和不可抵赖性。 无法伪造性就是只有合法签名者能够实际签署电子文件。真实性就是电子文 ： 档的接受者能确信文档来自签名者。不可重用性就是要求签名只能属于一个电子 文档，而不能用于其他任何电子文档。不可修改性是要求电子文档被签署之后不 能被修改。最后，不可抵赖性就是签名者不能在以后声明她或他未曾签署的文件。 但是在现实中，如果公司的老板去国外旅游，暂时无法对各种文件进行签名： 董事会希望董事会秘书就其公司的业务的问题代表董事会的成员进行签名：繁忙 的行政官员希望办公室主任代替他为众多的文件进行签名等等。这些情况将面临 签名的伪造，真实性的考虑，抵赖性的考虑等等问题。而传统的手写的签名是不 能解决这些问题的。于是就要求我们设计安全有效的数字签名方案，即是代理签 名。 于是，要解决以上的这些问题，就要求我们设计出一种安全有效的数字签名 方案。这对信息化产业的进程和社会的和谐发展有重大的意义。 1 2 本文的主要内容 第一章：主要介绍了主要介绍了数字签名的研究背景。 第二章：主要介绍了相关数学基础 第三章主要介绍了密码学概论。 第四章：主要介绍了数字签名中的代理盲签名体制。分析了几种典型的代理 签名并进行了安全性分析。谷利泽等人3 1 提出了一种代理盲签名方案，并声称他 的方案满足不可伪造性和不可链接性。本章指出这个方案不安全，不满足不 可伪造性和不可链接性。原始签名人可以进行伪造攻击，代理签名人可以进行链 接性攻击。 第五章：主要介绍了多重代理盲签名的机制。陆荣幸等人【7 1 提出了一个多重 代理盲签名方案，并声称这个方案满足不可伪造性和不可链接性，本文受到了方 案随1 对方案9 1 和方案1 9 1 对方案【1 0 1 的攻击方式的启发，采用了构造的方法证明了这 个方案不安全，不满足不可伪造性和不可链接性，不能用于电子商务，电子货币， 电子投票等系统。 硕十学位沦文第二章数学预螽知识 2 1 大整数分解问题 第二章数学预备知识 定义2 1 ( 大整数分解问题1 1 2 1 ) 给定整数玎，找出它的素因子即对n 进行 因式分解门= p l e l p 2 “p 唧，其中p ，是互不相同的素数，e ，是正整数。 在现有的计算能力下，已知若干不同的素数p ，p 2 ，p ，求这些素数 的乘积在计算上是可行的，是一个多项式时间算法，反之，已知聆，求它的素因 子是困难的。 定义2 2( 欧拉函数) 设玎是一个证整数，矽( 门) 的值等于序列1 ，2 ，3 ， , 一1 中与，2 互素的整数的个数，若门的因子分解已知，则很容易计算痧( 门) ，但当 胛很大时，若玎的因子分解未知，则很难计算矽( 门) 。 2 2 离散对数问题 离散对数问题1 1 3 , 1 4 1 是公钥密码体制的一个基本问题，它的安全性决定了很多 密码算法和方案的安全性。在密码学中，许多方案1 1 4 - 1 8 1 都是基于这个问题的， 如数字签名标准1 1 9 - 2 1 1 、e i g a m a l 型签名体制及其变形等。 定义2 3 设g 是一个有限循环群，且g g 是g 的一个生成元，元素 口g ，整数x ( 0 x o r d ( g ) ) 满ea = g 。，则称x 为a 的以g 为底数的离散对 数。用l o g g 口表示。离散对数有以下的性质： 设g = 是阶为，z 的有限循环群，a ，b ，c g ( 1 ) l o g ga b = l o g ga + l o g gb ( m o d n ) ， ( 2 ) l o g 葺a 。= x l o g 譬a ( m o d n ) ，v x z 。 ( 3 ) 若h 是g 的另一个生成元，则l o g 。口= l o g 口一譬l - l ( m o d n ) ，其中 硕十学位沦文 第二章数学预备知识 l o g gh = 1 0 9 g 】l ( m o d n ) 二定义2 4 ( 离散对数问题d l p ) 对于一个有限循环群g = 和元素 a g ，寻找x ( 0 x o r d ( g ) ) ，使a = g 。成立。 2 3 二次剩余 定义2 5 ：( 素数和合数) 若一个大于1 的j f 整数p ，只能被1 和它本身整除， 不能被其他的币整数整除，则称这样的正整数p 为素数或质数。把不是质数的讵 整数叫做合数。 定理：大于1 的整数疗都可以分解为素数的乘积。 定义：( 互素) 如果口和6 的最大公因数是l ，即g c d ( b ，c ) = l ，则称口和6 互素。 定义2 6 ( 二次剩余t h eq u a d r a t i cr e s t d u o s i t y ) 设胛是两个素数p ，g 的 乘积，且y 乙，若存在整数x ，使得x 2 = y m o d n 成立，则y 是模，? 的二次剩 余( 平方剩余) ；若不存在整数x 使得x 2 = y m o d n 成立，则y 是模 的二次非剩 余。 定义2 7 二次剩余问题( t h eq u a d r a t i er e s i d u o s i t yp r o b l e m ) 给定整数疗与y ，( 0 y 功，判定是否存在整数x ( 0 x 0 ，重复使用带余除法， 即用每次的余数为除数去除上一次的除数，直至除数为零，这样可得下面的方程： b = c q l + ，0 c ，c = r t q 2 + r 2 ，0 r 2 ，= r 2 q 3 + r 3 ，0 r 3 r 2 ，：，一l = 0 9 j + 1 最后的一个不为零的余数，就是b 和c 的最大的公因数g c d ( b ，c ) 。 2 5 陷门单向函数 单向函数就是求逆困难的函数，而陷门单向函数是在不知道陷门信息的条件 下求逆困难的函数。当知道陷门信息时，求逆是易于实现的。 定义：陷门函数是满足下列条件的函数厂： ( 1 ) 给定x ，计算y = 厂( x ) 是容易的。 ( 2 ) 给定y ，计算x ，使y = f ( x ) 是困难的。 ( 3 ) 存在万( 陷门) ，已知万时，对给定的任何y ，若对应的x 存在，则计 算x 使y = f ( x ) 是容易的。 ( i ) 仅满足( 1 ) ( 2 ) 的函数叫单向函数，第三条是陷门性，万称为陷门信息。 ( i i ) 当用陷门函数厂作为加密函数时，可将厂公开，这相当于公开加密 密钥。此时加密密钥称为公钥，记为以。函数的设计者将万保密，用作解密 硕十学位沦文 第二章数学预备知识 密钥，此时万称为私钥，记作s k 。由于加密函数是公丌的，任何人都可以将信 息x 加密y = ( 石) ，然后送给函数的设计者( 当然可以不通过安全通道传输) ，由 于函数的设计者拥有解密密钥s k ，他可以对收到的密文y 解密得到明文 x = f 一1 ( j ，) 。 ( iii ) 第二条性质表明窃听者有截获的密文y = f ( x ) 推测x 是不可行的。 6 硕十学位沦文 第三章密码学概论 第三章密码学概论 密码学研究的是如何保证信息的安全。它以认识密码变换的本质、研究密码 保密与破译的基本规律为对象。主要以可靠的数学方法和理论为基础，对解决信 息安全中的机密性、数据完整性、认证和身份识别，信息的可控性，以及不可抵 赖性等提供系统的方法和技术。 密码体制即密码系统是一个五元组( 尸，c ，足，e ，d ) ，其中尸称为明文空间，是 所有可能的明文构成的空间，c 是密文空间，是所有的密文构成的空问。k 是密 钥空间，是所有可能的密钥构成的空间。e ，d 和分别是可能的加密算法和解密 算法构成的空问。 密码体制的安全性：把对密码系统的攻击分为四种基本类型：唯密文攻击， 在这种攻击中，密码分析者仅有一些截获的密文；已知明文攻击，这种攻击中， 分析者拥有一定数量的密文及其对应的明文；选择明文攻击，分析者可以选择一 些他认为对攻击有利的特定的明文，并获得相应的密文；选择密文攻击，分析者 可以选择一些他认为对攻击有利的特定的密文，并获得相应的明文。 经典密码学包括既对立又统一的分支：密码编码学和密码分析学。研究密码 变化的规律并用之于编制密码以保护信息安全的科学，称之为密码编码学。研究 密码变化的规律并用之于密码以获取信息情报的科学，称之为密码分析学。 根据加解密的是否使用相同的密钥，将密码体制分为对称和非对称密码体 制。对称密码体制也叫单钥或者秘密密钥密码体制，而非对称密码体制也称为双 钥或公钥密码体制。在对称密码体制中，加密密钥和解密密钥是完全相同或彼此 容易相互推导。在公钥密码体制中，加密密钥和解密密钥是不同的，除了解密密 钥的拥有者外，其他人难以推导解密密钥。因此公钥体制将加密和解密能力分 开。 根据加密方式又将密码体制分为流密码和分组密码。在流密码中，明文信息 按一定的长度( 长度较小) ，然后用相关但不同的密钥对各组进行加密产生相应的 密文。相同的明文分组因为在明文序列的中的位置不同而对应于不同的密文分 组。在分组密码中，对明文信息也是按一定的长度( 长度较大) ，每组都是用相 7 硕十学1 1 ：) = 沦文第三章密码学概论 同的密钥加密产生相应的密文，相同的明文分组不管处在明文序列的什么位置都 是对应相同的密文分组。 j 另外，按照在加密过程中是否除了使用密钥和明文外的随机数，又将密码体 制分为概率密码体制和确定性密码体制。 3 1 分组密码 分组密码是现在密码学的重要组成部分，因为加密速度较快，安全性能好， 以及得到许多密码芯片的支持，所以发展很快。 所谓的分组密码也叫块密码，它是将明文消息经编码表示后的二进制序列划 分成若干固定长度的组，各组分别在密钥的控制下转换成长度为的密文分组。其 本质是一个从明文空间到密文空问的映射，该映射由密钥确定。 3 1 1 分组密码设计准则 分组密码设计准则，分组密码一般采用代换置换网络的结构，这种结构的典 型代表是f e i f t e l 密码结构，而且现在大量的对称分组密码算法中不少采用了这 种结构模型，其中最具代表性的是数据加密标准d e s 。f e i f t e l 密码结构的密码算 法的基本思路是采用“扩散和混乱”两种主要思想。( 1 ) 混乱是指明文与密钥以 及密文之间的统计关系尽可能地复杂化，是破译者无法理出相互之间的依赖关 系，从而加强隐蔽性。( 2 ) 扩散是指明文中的每一位( 或者是密钥的每一位) 直接 或问接影响到密文的许多位，或者让密文中的每一位受制于输入明文以及密钥的 若干位，以便达到隐蔽明文的统计特性。密码学中的重要指标“雪崩效益”讲的 就是迅速扩散的概念。 3 1 2 数据加密标准d e s 3 1 2 1 d e s 简介 数据加密标准源于2 0 世纪6 0 年代末i b m 公司的f e i s t e l 领导的密码小组研 制的l u c i f f e r 密码算法。1 9 7 1 年i b m 公司请w a l t e rt u c h m a n 和c a r lm e y e r 在此 基础上作进一步的研究，最终完成了在商用范围使用的数据加密标准( d e s ) 的研 硕+ 学位沦文第三章密码学概论 制工作。 d e s 在超期服役的2 0 年问( 当时规定d e s 的使用期是1 0 年) ，确实发挥了数 据加密不可替代的作用。进入2 0 世纪9 0 年代以后，由于d e s 密钥长度偏短等 缺陷，不断受到差分密码分析和线性密码分析等各种攻击的威胁，使其的安全性 受到严重的挑战，而且不断的传出被攻击和破解的进展情况，于是在1 9 9 8 年美 国n i s t 决定不在使用d e s 来保护官方的机密。后来d e s 被a e s 所代替。但是 d e s 的出现分组密码的理论的研究。起到了促进分组密码的发展的重要作用。 3 1 2 2d e s 的密钥 d e s 用一个6 4 位的密钥来加密每个块长6 4 位的明文，并生成每个块长6 4 位的的密文。是一个包含了1 6 个阶段替换一置换加密法。d e s 加密机制如下图 所示，每轮的结构完全一样。整个过程有三个阶段来完成：初始置换，乘积变换 和逆初始置换。 图3 1d e s 简化示意图 尽管d e s 密钥有6 4 位长，但用户只提供5 6 位。其余的8 位由算法提供，分别放 在8 、1 6 、2 4 、3 2 、4 0 、4 8 、5 6 、6 4 位上。结果是每个8 位的密钥包含了用户提 供的7 位和d e s 确定的1 位。添加的位是有选择的，以便使每个8 位块都有奇数 个校验位( 即1 的个数为奇数) 。 1 6 个阶段中的每个阶段都使用一个4 8 位的密钥，该密钥是从最初的6 4 位派 生而来的。该密钥要穿过p c 一1 块。p c 一1 块( p e r m u t e d c h o i c el ，交换选择1 ) 负 9 硕十学位沦文 第三章密码学概论 责取出由用户提供的5 6 个位。这5 6 个位分成左右两半。每一半都左移1 或2 位( 视每个阶段的情况不同，第1 、2 、9 、1 6 阶段是左移1 位；剩下的阶段都是 左移2 位) 。新的5 6 位用p c 一2 ( p e r m u t e dc h o i c e2 ，交换选择2 ) 压缩，抛弃8 位后 为每个阶段生成4 8 位的密钥。该过程如下图所示： 3 i 2 3d e s 算法 图3 - 2d e s 密钥的初始阶段示意图 d e s 的每个阶段使用的都是不同的子密钥和上一阶段的输出，但执行的操作 相同。这些操作定义在三种“盒( b o x ) ”中，分别称为扩充盒( e x p a n s i o nb o x ，e 盒) 、替换盒( s u b s t i t u t i o nb o x ，s 盒) 和置换盒( p e r m u t a t i o nb o x ，p 盒) ，在d e s 的每个阶段，这三个盒的应用顺序如图所示： l o 硕+ 学位沦文 第三章密码学概论 图3 - 3d e s 的某一个阶段示意图 当一个6 4 位块( 都是由0 和1 组成的) 通过d e s 的某个阶段时，左边3 2 位保留， 以用于该阶段的最后一个操作，右边3 2 位作为e 盒的输入。通过复制一些输入 位，e 盒将3 2 位的输入扩充为4 8 位。 下一步的操作是将e 盒的输出与4 8 位的子密钥进行x o r 逻辑运算。该操作 输出一个新的4 8 位块，该块作为s 盒的输入。s 盒是d e s 强大的功能源泉。这 些盒定义了d e s 的替换模式。有8 种不同的盒。每个s 盒接收一个6 位的输入， 输出一个4 位的输出，一个s 盒有1 6 列和4 行，它的每一个元素是一个4 位的 块。于是就生成3 2 位的块，这3 2 位的块就是p 盒置换的输入。最后的操作是将 初始的右半边的3 2 位作为左半边，而初始左半边的3 2 位与p 盒的3 2 位进行x o r 运算，并将运算结果作为右半边的3 2 位。 3 1 2 4d e s 安全性分析 d e s 安全性分析：d e s 算法的密钥扩展算法有缺陷。密钥扩展存在弱密钥和 半弱密钥的情形，所谓的弱密钥就是指墨= k 2 = k l 。时，满足 d e s k ( m ) = d 砜一( 聊) 或者d e s k ( d e s k ( m ) ) = m 的密钥k 就是弱密钥。d e s 当 ，d o 的位模式为全0 或全l 时存在4 中弱密钥。所谓的半弱密钥就是指，若存 硕十学位沦文第二章密码学概论 在k 或k 使得d e s k ( d e s k ，( 聊) ) = m ，则后7 ，k 就成对构成半弱密钥。d e s 至少有 1 2 个半弱密钥存在，半弱密钥将导致把明文加密成相同的密文，通过密钥k 能 够破解出密钥k 加密的消息：d e s 的s 盒的质疑。d e s 的安全性依赖于非线性模 块的s 盒。然而从d e s 算法公布以来，s 盒的设计准则至今没有公布，许多密码 学家担心s 盒的设计存在“陷门”，会给d e s 带来不必要的麻烦；d e s 有效密钥 位数的缺陷。在d e s 的安全性争议中，其中批评较多的是针对d e s 密钥密钥长 度偏短的问题。另外，d e s 迭代次数1 6 轮偏少问题，也是批评之一。这些问题 在很多的改进的d e s 方案中得到不同程度的提高。比如，三重d e s ，还可以在 一般的商片j 的密码上使用。 3 1 3 高级加密标准a e s 3 1 3 1a e s 简介 高级加密标准a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 是在d e s 不断受到攻击威 胁的情况下推出的。2 0 0 0 年n i s t 宣布蹦n d a e l 数据加密算法为高级数据加密算 法。并与两年后生效。a e s 算法具有良好的有限域及有限环数学理论基础，算 法随机性好，能高强度隐蔽信息，同时又保证了算法的可逆性，很好的实现了加 解密的需求。 3 1 3 2r i j n d a e l 算法原理 图左边为加密算法结构，右边是加密算法的一轮，整个算法是由1 0 轮组成， 加密过程满足可逆性。每轮有四个不同部件：字节替换( s u b b y t e s ) 、行移位 ( s h i f t r o w s ) 、列混合( m i x c o l u m n s ) 和轮密钥j j h ( a d d r o u n d k e y ) ，最后一轮略有不 同，没有列混合。 尽管r i j n d a e l 算法的安全性还在讨论中，但迄今为止，对a e s 的安全性分析 普遍认为，该算法有较好的安全性。目前还没有发现攻击a e s 的有效方法。 1 2 硕十学位沦文第二章密码学概论 图3 4 a e s 算法结构 3 2 流密码 3 2 1 流密码简介 图3 5 一轮a e s 结构 k i l 流密码是非常重要的密码体制，又称为序列密码。在流密码中，将明文消息 按一定的长度分组( 长度较小) ，然后用相关的但不同的密钥进行加密，产生相应 的密文，相同的明文分组会因为在明文的序列不同而对应于不同的密文分组。相 对于分组密码而言，流密码主要有一下的优点：( 一) 在硬件设施上，流密码的速 度一般比分组密码快，而且不需要很复杂的硬件电路。( 二) 在某些情况下，当缓 存不足或对收到的字符进行逐一处理时，流密码显得更加必要和恰当。( 三) 流密 码有较理想的数学分析工具，如频谱理论和技术，代数方法等。 3 2 2 流密码的原理 在流密码中，明文按一定的长度分组后被表示成一个序列，称为明文流，序 列中的一项称为一个明文字。加密时，现有主密钥产生一个密钥流序列，该序列 硕士学位沦文 第三章密码学概论 的每一项和明文字具有相同的比特长度，称为一个密钥字。然后依次把明文流和 密钥流中的对应项输入加密函数，产生相应的密文字，产生密文流。 设明文流为：m = m t m 2 m ，密钥流：k = k l k 2 毛 则加密算法为：c = t i c 2 q = e ( 聊。) 色，( 历2 ) 乓( 以) 解密算法为：m = m 。m 2 以= q ( q ) 协，( c 2 ) 峨( q ) 用流密码进行保密通信的原理如图所示： 图3 6 流密码保密通信原理图 说明：流密码与分组密码在对明文的加密方式上是不同的。分组密码在对明文的 处理上，明文分组较大。所有的明文分组都是用相同的函数和密钥来加密的。而 流密码在对明文的处理时，采用较小的分组长度( 一个分组称为一个字或一个字 符) ，对明文流中的每个字用相同的函数和不同的密钥来加密。 3 3 公钥密码体制 3 3 1 公钥密码体制简介 d i f f i e 和h e l l m a n 于1 9 7 6 年在“密码学新方向”一文中首次提出公丌密钥密 码体sj j ( 简称公钥体制) 的思想。它使密码学产生了第二次飞跃，丌创了密码学新 纪元。传统的密码体制是加密，解密都是相同的密钥。每对用户之问都需要一个 1 4 硕十学侮沦文第二章密码学概论 专用密钥。当保密通信的用户较多的，密钥的产生，分配和管理是一个严重的问 题。公钥密码体制改变了传统的做法，将加密，解密密钥甚至加密，解密函数分 开。用户只保留解密密钥，将加密密钥和加密函数公布于世。任何人都可以加密， 但是只有掌握解密密钥的用户才能解密。由于公钥密码体制不仅能完成加密和解 密的功能。而且还具有数字签名、认证、鉴别等多项功能，于是是密码学研究的 热点。 自从公钥密码体制的思想提出后，国际上已经出现了多种密码体制。例如基 于大整数分子分解问题的r s a 体制和r a b i n 体制；基于有限域上的离散对数问 题的d i 衔e h e l l m a n 公钥体制和e i g a m a l 体制；基于椭圆曲线上的离散对数问题 的d i f f i e h e l l m a n 公钥体制和e i g a m a l 体制：基于背包问题的m e r k l e h e l l m a n 体 制和c h o r - r i v e s t 体制：基于代数编码理论的m c e l i e c e 体制。目前比较流行的密 码体制主要有两类：一类是基于大整数因子分解问题的，其中最典型的是r s a 体制：另一类是基于离散对数问题的，如e i g a m a l 公钥密码体制和影响比较大的 椭圆曲线密码体制。由于分解大整数的能力同益增强，因此为保证r s a 体制的 安全性要不断的增加模长。目前认为r s a 需要1 0 2 4 位以上的模长才有安全保障， 但是增加模长会大大降低加解密的速度，硬件的实现也变得越来越困难，从而应 用范围受到了制约。而基于离散对数问题的公钥密码在目前的技术下5 1 2 比特模 长就能保证其安全性。特别是基于椭圆曲线的离散对数的计算要比有限域上的离 散对数计算更困难，目前技术只要1 6 0 比特的模长即可保证其安全性，适合于智 能卡的实现。因而受到国际上的广泛的关注。 公钥密码体制的优点是可以适用网络的开放性要求，与对称密码体制相比， 密钥管理要简单的多，尤其可以方便的实现数字签名和认证。公钥密码体制并没 有完全替代对称密码体制，这是因为公开密钥的算法较复杂，加解密速度低。在 实际应用中，这两种密码体制结合使用，即加解密用对称密码体制，密钥管理用 公钥密码体制。 3 3 2 公钥密码体制的原理 3 3 2 1 公钥密码体制的模型 公钥密码体制在加密和解密使用不同的密钥，即加密功能和解密功能分开。 1 5 硕十学位沦文第三章密码学概论 这样通信双方无须预先交换密钥就可以建立保密通信，克服了对称密码体制中通 信双方必须使用一个安全信道预先约定密钥的缺点。在公钥密码体制中，每一个 j 用户保存一对密钥，即公钥p k 和私钥s k ，p k 是公开信息，不需要保密。虽然 公钥密码体制的密钥是成对出现的，但是给定公钥，要确定私钥在计算上是不可 行的。持有公钥的任何人都可以加密明文产生密文，只有持有私钥的人才能解密。 公钥密码体制有两种基本的模型，一种是加密模型，一种是认证模型，如下 图所示： 图3 - 7i k - i r 模型 在加密模型中：用接受者的公钥作为加密密钥，用接受者的私钥作为解密密钥， 即只有接受者- a 能解密密文才能得到明文。在认证模型中：发送者用自己的私钥 对消息进行变换，产生签名，把消息一签名对发给接受者。接受者用发送者的公 钥进行验证以确定签名是否有效。只有拥有私钥的发送者才能对消息产生有效的 签名，任何人都可以用签名人的公钥来检验签名的有效性。 1 6 硕十学位沦文 第三章密码学概论 3 3 2 2 公钥密钥体制的基本原理 公钥密码体制抽象来说就是一种陷门单向函数。一个单向函数是满足下列条 件的函数：它是定义域到值域的映射，同时满足下列条件：计算函数值是容易的， 而从函数值计算原像足不可行的。所谓的陷门单向函数就是这样的单向函数，存 在这样的一个附加信息，当不知道附加信息时，由函数值计算原像是困难的。当 知道附加信息时，从函数值到原像的计算就容易了。即陷门单向函数在附加信息 未知时是单向函数，当附加信息已知时不是单向函数。通常把附加信息叫做陷门 信息。公钥密码体制就是按照这一基本原理设计的。利用一个陷门单向函数，将 它作为公开密钥，而将陷门信息作为秘密密钥，其安全强度依赖于它所依据的问 题计算的复杂度。 3 4 数字签名概述 3 4 1 数字签名产生 随着科技的发展和社会的进步，计算机已经广泛应用到社会的各个领域，从 而促进了网络通信技术的产生和发展。越来越多的文件书信需要以数据串的形式 通过网络快速传递，这些数据串的来源和完整性都需要认证，而且这些认证常常 需要在以后的一段时期内多次重复，这就需要手写签名的电子替代物数字签 名( d i g i t a ls i g n a t u r e ) 。 网络通信虽然促进和加速社会信息化的发展，但是网络环境下的信息安全并 不令人乐观，由于技术原因和人为攻击等因素，网络通信的安全性受到严重的威 胁，信息在传输的过程中有可能被删除、篡改和重放，给人们的生活和工作造成 了许多麻烦。数字签名由公钥密码发展而来，是提供认证性、完整性和不可否认 性的重要技术。在电子商务活动同益盛行的今天，数字签名技术已受到人们的广 泛关注和认可，各国对数字签名( 又可称为电子签名) 的使用已颁布了相应的法 案，如美国国会在2 0 0 0 年6 月通过电子签名全球与国内贸易法案。按该项法 案规定，电子签名将与普通合同签字在法庭上具有同等的法律效力。2 0 0 4 年8 月，第十届全国人大常委会通过了中华人民共和囤电子签名法，该法已于2 0 0 5 年4 月起施行，它将对我国电子商务，电子政务的发展起到及极其重要的促进作 1 7 硕七学位沦文第二章密码学概论 用。数字签名的算法是以某种形式将签名“附加”到所签的电子文件之上。数字 签名作为一