2024现代密码学简介.docx

提供PDF版现代密码学简介2023目录第一章结论21.1 什么是密码学21.1.1 密钥21.2 密眄体制的基本要素31.2.1 弱密钥与半弱密例51.3 经典密码51.3.1 基础概念51.3.2 单表代换密码61.3.3 单表代换密码的破解71.3.4 多表代换密码81.3.5 一次一密101.4 加密系统的安全性10第二章流密码与伪随机数发生器132.1 数学上的基本概念132.1.1 GF上的加法与乘法132.1.2 GF上的多项式142.2 流密码的基本概念162.3 基于1.FSR的伪W1.机比特发生器172.3.1 伪叨机比特发生器的线性郃分172.3.2 伪Ia机比特发生器的非线性部分202.4 BBS产生器212.5 ANS1.X9.17伪1.¾机数发生器222.5.1 准备阶段222.5.2 122第三章分组声码233.1 设计密码系统的方法233.1.1 扩散与1233.1.2 与代233.2 分组密码的定义233.3 分处密码的设计方法243.3.1 费斯妥密码243.3.2 SP网络253.4 分红I密码的运行模式263.4.1 电码本模式（ECB）263.4.2 密码分组链接模式（CBC）273.4.3 密码反馈模式（CrB）283.4.4 输出反馈模式（OFB）283.4.5 计数器模式（CTR）293.5 DES293.5.1 算法与代码303.5.2 多重DES403.5.3 结构特性403.6 IDEA413.6.1 符号说明413.6.2 轮结构423.6.3 加密过程423.7 AES433.7.1 隘人与黝出433.7.2 轮函数443.7.3 密蝌端排算法483.7.4 总的加解密过程503.7.5 数学基础52第四章公钥密码574.1 简介574.2 RSA密码584.2.1 基本框架584.2.2 舞法细节594.2.3 RSA的数学脸证654.2.4 RSA的安全性664.3 E1.GamaI密码664.3.1 数学基础664.3.2 基本框架664.3.3 正确性证明674.3.4 EIGamaI密眄的安全性674.3.5 模整数乘法群上的EIGamaI684.3.6 椭硼曲线684.3.7 椭圆曲线上的EIGamaI69第五章哈希眸法715.1 消息认证715.2 定义715.3 应用725.4 MerkIeQam猫rd结构735D服从MD结构的埴充函数735.4.2 单向压缩函数735.4.3 算法745.5 MD57455,1充比aafttatt75552亍Cti765.5.2 初始化变量765.5.3 处理消息775.5.4 总过程815.6 SIIA-256825.6.2 1.比特825.6.3 填充长度825.6.4 初始化变锻835.6.5 处理消息855.6.6 总过程87第六章消息脸证码896.1 简介896.2 基于分组密码的MAC算法906.2.1 CBC-MAC906.2.2 CMAC906.3 基于哈布函数的MAC算法916.4 基于全域哈布的MAC算法926.4.1 Po1.y1305926.5 认证加密956.5.1 先加密再MAC956.5.2 加密同时MAC956.5.3 先MAC再加密956.5.4 认证加密模式95第七章数字签名967.1 简介967.2 数字签名的执行方法967.2.1 直接方式(DirCCtdigi1.aIsignatures)977.2.2 仲裁方式(Arbi1.nHCddigita1.SignatUrCS)977.3 基于公的密码的数字签名的基本步骤977.3.1 密钥生成算法977.3.2 锭名算法977.3.3 蕤证签名算法977.3.4 讨论977.4 数字签名算法DSA987.4.1 密钥生成算法987.4.2 签名算法997.4.3 5金证签名律法99第八章安全协议IW8.1 为什么要安全协议1008.2 安全协议记号1008.3 密W协议1018.3.1 对称密码的密的分RIOI8.3.2 公钥密码体系的安全协议1048.3.3 基于公钥密码的殳话密钥分配协议1058.3.4 秘密共享107第一章绪论1.1 什么是密码学如果我们要求一个从未接触过密码学的人处理一段文字，把这段文字尽可能地加密，让别人无法皱解,咫么，大多数人在深思熟虑之后，总能提出一些加密修法。这时候，一般人的思路可能会有几个方向。有的人的方向是把这段文字中的字母之间通过各种更杂的运算进行组合.比如说.把要加密的文字中每两个字母在字母表中的位置诳行相加，形成密码.比如说,“Ciyp(OgraPhy”中，“cr变成了3+18=2变成了25+16=41,"crypiograph尸对应的密码就是24135252133“。但这样的密码，显然忽略了一点：密码的可解密性，我们之所以要进行加密，是为了安全地传递信息.但接收信息者必须要仃解密的方法.但这种加密方式则没有对应的解密方法.所以说.这不是一个合格的加密方式。这时，足终聪明的人，则考虑到了解密的方法。他们想出了一-些类似于古代使用的加密方法。比如说,著名的凯嫩密码：把一段H1.英文字母组成的谱句,每个字母都在字母表中往后移3个位置.-ventvidiMCir也就变成了“yhq1.y1.g1.y1.t.这种密码的解密方法,也就是每个字母在字母表中向箭移动3个位置,当何起这种玄码体制里最IR要的是什么，大部分人都会说是加密算法。如果把加密算法告诉了别人，那这种密码就相当于被破解了。如果进而问起一个密码体制的组成,大部分人的答,就是加密算法.也许有些自用比普通人聪明一点的人，还会加上一个解密算法，也就是，将处理过后的密码变为正常文字的算法.如果用阳代如要彼加雷的文字,C代表被加密出来的密码,EO代表加密算法,DO代表解率算法，那么大多数人理解的密码学，本质就是以下这两个式子：c=E(n)in=D(c)1.1.1 密钥但是,我们考虑一下实际的侍况。根据我们之前的常识.会发现,如果要用密码来传递信息.首先通信的双方必须要在一个安全信道中传递一些额外的信息.比如说，告诉接收者加密的方式.或者更n接施，告诉攵不解密算法。不存在种和密的方式，能不出先通过安全信道传递信息，而使得只有接收者能的解密。那么，为了使通信更加安全，通信双方对安全信道的使用应该尽可能少,如果A1.iCC和Bob使用凯撒定码进行通信,而A1.iCe事先在安全信道中要对BOb说“我的这种加密方式是把一段由英文字母组成的语句，每个字母那在字母衣中往后移3个位置.”这段话是如此之长，而如果考虑是在战场上，由通信员用摩尔斯电码发送，那么花戏的这么长的时间显然是不合叫!的。再者,现代的通信方式一般都是把信息编码成二进制进行传递，那么，相比把段话娟眄成二进制.不如找一些数字来代表这个定码.在我们的这段思想博弈中，一个重要的概念呼之欲出.京凯楸密码为例，在其加密算法中，还有一个关键的H：3.试想，如果通信双方A1.iCe和Bob.A1.ice在场的所有人她用的是凯嫩密码的加率方式加密她的话，又在安全信道中告诉Bob-4,意味着她使用的凯撤密码里，是将每个字母在字母衣的位跣上向后移动4个位置.«么，即使在场有人能偷听到A1.iCe给Bob的密码，也无法破斛Ake想说的是什么，只彳j掌握了规则“向后移动4个位置”的Bob.才能正确地破解密码.如果还是按照之前的说法,一个密码体制包括加密霓法和解密算法,那么向后移动3个位置的凯嫩密码和向后移动4个位置的凯撤密码，就成了两个密码体制。但是，这两种加密方式是极其类似的,差别也就只在于一个向后移动3个位置.一个向后移动4个位置.我们对于这些密码的研究,也许也就十分类似.因此，把这两种加密方式归类为同一种梏码体制.似乎是更好的选择，因此，密钥就应运而生了，所谓密钥，我们可以粗略地理解成加密算法、斛密驾法中的参数,也就是我们之前说的3、4.通过一个密码体制通信的双方，需要首先在保密信道中确定密鼓而一个密码体制,也就可以由加密。法、解密算法和密钥构成.W1.1.t.如果以J1.代表密钥，加么之前的式子就变成了c=Ek(m，”=Dfc(C)这也就是现在通用的衡码学。那么我们思考几个问瑜：在一次加密通信过程中，加密獴法和解密算法中使用的密倒是否必须要相同？密钥是否只能是一个数？可不可以没有密例？针时第一个问跑，确实存在某些高端的技巧使得加密修法和解密算法使用的密铀是不同的。M实上，在宓码学领域中，根据加雷豫法和解密算法使用的密铝是否相同，人们将加雷方式分为对称加密与非时称加酸，分别对应使用同一密钥和使FH不同密钥，非对称加密方式也许雄以理解,我们也会在充分学习对称加密后再介绍非对称加密.所以,我们接下来讨论的对称加密过程中，请大家记住，加容算法和解密算法使用的是相同的名彷.此外，对于对称加密算法，密钥也并不一定是一个数。比如说，加密算法Eab(m)=am+b其密钥为胡),但我们仍认为我使用单一济钥，也就是说.把(Gb)看作一个密钥.此外，可不可能不存在密钥呢？确实有这样的密码体制，但这样却也十分不安全，比如说,加密算法E(m)=/H就是一个无密钥的加密算法.1.2 密码体制的基本要素根据之前的讨论.我们就可以得出一个密眄体制的基本要素： 明文空间M所有可以被加密算法加密的元索组成的集合,加密算法的定义城.明文空间的元素叫做明文dieM.例如，在凯撤密码中，明文空间就为所有由英文字母祖成的字符申“ 密文空间C所有可以由加密算法输出的元素纲成的集合，加密算法的做域。密文空间的元素叫做宓文ceC.我们需要注意到的是,这里的伯域，可以理解成二元函数E(1,")的值域.比如说.对于加密非法Ek(/W)=nr+Ir其密文空间为0.+8)而非F,+oo). 密钥空间K所有密钥组成的集合。密钥空间的元素叫做密钥JteK.在非对称加密中，密的空间分为加密密钥空间和解密密钥空间.加密算法Efc(ZM)根据密钥生成的特定豫法，将明文转化为密文， 解密"法Da©根据密钥生成的特定算法，将密文转化为明文.对于时称加格算法，也就是只使用一个密切的加密体制，解密算法与加密豫法湎足Dk(Ejc(m)=m在我打讨论密码体制的一些性质时，密仍生成算法有时也是必要的.什么是密钥生成算法呢？回忆之前A1.iCe和Bob的例子，凭什么A1.ice选择的密钥是4而不是25呢？这就涉及到了密钥牛.成算法，在这个例子中，率倒生成算法就是A1.ice自己想到哪个密钥就输出哪个密91.但是.从严格意义上来讲.密钥生成算法是一种概率算法.所谓概率算法,就是在算法的步骡中涉及到了某些概率.比如说，在某个密钥生成算法中，在。I)中等慨率随机生成一个数，,而生成的密钥大满足1I(0.5,1)k=0/=0.5-16(0,0.5)这就是一个典型的概率律法.其特点就是在两次运行中输出的结果不一定相同.因此，我们称一个加密方案包含一:个要素：加密算法E,解密算法D.密钥生成算法G根据定义，我们可以说，一个密码体制由一个加密方案(E,D,G)及一个明文空间M完全定义，因此，A1.ie和BOb的一次加密通信的过程包括：1.A1.ice根据梆仍生成算法G生成密的kK.2 A1.ice通过安全信道将k告诉Bob.3 A1.iCC将想要传达的明文meM根据加密究法加密成裕文C=Ek(，)告诉Bob.4 Bob根据之前AIiCe告诉自己的k、密文C及解密算法得出明文E=D1.c(C)原么，在一个密码体制中，哪个最通要呢？是不是之前我们说的加密匏法呢？这里，就不得不提Kerckhof1.s原则'用现代的语言来说，KerckhofYs原则匍述的是：提化1安全性不能建立在对算法的保密上.也就是说,我们如果要证明一个加密体制的安全性,不能指型算法的保密性.我们应默认加解密算法可以被所有人知道(事实上也确实如此)，也就是说，我正值得保密的.是密仍.如果潜在的敌手获得南朝，那么根据公开的解密算法，那么他就可以从物得的密文中获得明文。1.2.1 弱密钥与半弱密钥在我们构造密码体系的时候，有的人会S!,利用己行的密码体系加的两次怎么样？即：Ek(Efc(zn)或者EH(EfcS(，)的安全性如何？这里提出了弱密钥与半弱密钥的概念：定义1.1.肘于加密:方式Ekg),若密钥Jt使得对于任意mGM,书Ek(Ek(M)=m则称A为朋密钥.若密钥ki.kz若密钊k使得对于任意mM.有Efc1(Ek3(m)=m则称八心为一对半弱密的.由上述定义可知,如果我们想鬟利用已有的密码体系加密两次，那么一定要避开的就是弱密钥与半弱密钥.1.3经典密码1.3.1 基础概念我们讨论了密码体制的基本要素之后，就可以介绍一些经典的密码，让大家更好地理解这些术语了.值得指出的是,这些密码都是古代欧洲人的研究成果,当时并没有如今“数字化”的概乐因此，这些密码，都是针对拉丁字母诳行的加密，因此，我们首先要引入一些概念：函数CR”)将拉丁字母m映射到它在字母表中的位置上，比如C（八）=1,C(2)=26.函数/(”)格位于I和26之间的数字映射到字母表中相应位置的拉丁字母上，比如/(1)=a./(26)=z.在讨论经典密码时，一些极共基础的数论记号及知识可以让我们更加方便、更加简洁地叙述、理解这些经典密码。我们用gcd(a.b)表示。与的最大公因数.用“mod6表示整数“除以匕后的余数(取值范树为0到b-1).比如说15mod6=3,12mod6=0.(-4)mod6=2.若。mod=0,即能整除b,我们则记为f1.ft1.24,3t4.若(。一切IC1我们则称。与Z>模c同余，记作«三b(mod<-).如16三23(mod7).对于整数«.b.若存在整数<使得ac三1(modb),则称。为。在模/»时的逆，记作小,并非所有的整数怖力逆,如在模4的情况下，整数2就没有逆.对于整数九在模b时存在逆的充分必要条件为gcd()=1.1.3.2 单表代换密码单表代换密码的典型，就是凯撤密码，如果用我们上述的记号来表示凯撒密码的过程，加么如果设明文为字符串'Em加”,密文为字符串“egC1.T,，,<,均代表一个拉丁字母。凯微密码的加密算法Ci=E(110=C(mi)+3)mod26)(1.1)解密算法w»r=D(Cr)=C(/(Ci)-3)mod26)(1.2)它通过对字母表中集个字母进行固定的代换，得到密码。单表杵换密码则是凯撒密码的推广，引入了密钥。从数学意义上，可以作如下定义:设明文为字符串''mmi2mn'密文为字符串FC2c,MCI均代表一个拉丁字母.如果把整数对(a>)作为密钥，其中H=O,那么其加密算法Ci=Ea.b(mi)=C(“/，”»+b)mod26)解密算法()HU-D<,.b(Ci)-C<r1.(/(Ci)-Z>)mod26其中G为“模26的逆.事实上如果我们令m=I(m¢,ci=1.(Eab("一).ei=1.(EQQFtij),出=/(Ddb(Ea1.b(mJ).那么qt三atii+b(mod26)故d(三i®-b)三<r1.(ai+b-b)三tn(no<1.26)也就是说./(D0,b(E,>(M三m(mod26)故Dab(Ea.h(m,)=nh这也就证明了这个加密算法是正确的舞法.让我们不要再纠结于繁琐的数学符号,我们来从直观上看一看这个加密尊法.任意取一个密的，比如说,a=3,。=7,就会对应的生成一张加密友和解密表:衣1.1:“=3/=7时的力I密衣明文密文ahbkCndqCtfWgZhCifJikI1Omr明文nOPMrStUVWXyZ密文UXadgJmPsVybC我1.2:a=3,b=7阵的解密表密文abCdCfrhijk1m明文PyhqZirajSbkt密文nOPqr、CUVWXyZ明文CIUdmenWfOXg承么我们根据这张表.就可以很快地进行加密和解密的工作r.我们再回到之前所说的加密体制的基本要素：其明文空间M为由拉丁字母组成的任意长度的字符串组成的集合,密文空间C=M.密钥空间K=(4.力Ia.beZgcd.26)=1.(这里gcd(a,26)=1的条件是因为解誉算法中要求“模26的逆存在.).1.33单表代换密码的破解上述的单表代换密码看似十分安全但是如果用来加密由拉丁字母组成的用语有逻辑形成的句话时，却有个致命的弱点。虽然这些密码不会真接关沃明文，但却会暴“明文中各个字母出现的频率。我们知道，在任何一门由字母组成的语言文字中，悔个字母出现的频率在i普句十分长时是趋向于一个定值的.比如说.在英文中,有一个著名的短语：“ETAOINSHRD1.Ui'.这个短语是英文中出现频率最高的12个字母,从高到低排列.根据这些频率，就可以找到破解这种密码的方法。为什么暴露明文出现的领率就会使加密系统不安全呢？我们可以用一个例子来说明：我Q利用单表代换密码的原理.加密东南大学的校徽：图1.1:单表代换加密前图1.2:单表代换加密后显而易见,加密效果近似于无。利用这个原理，右两种最常用的方法：频率分析法与巧合指数法.频率分析法假设利用堆衣代换密码加密的哈古为英文，原么根据统计学家的知识，英文字母出现的频率从高到低依次是“ETAOINSHRD1.U".如果我们可以统计H1.个相当长的南文中各个字理出现的柒率,那么极有可能出现频率最高.的字母对应的就是明文中的“E”.这就是频率分析法的茶本思想.巧合指效法巧合指数法的想法非附直接：对于段文字，任意取两个字母，这两个字母相同的概率除为巧合指数1C。可以证明，对于一段长度为N的文字，共有C个字母，每个字母出现的次数为rtfci=1.Z.c.那么巧合指数的值为Mr(He-1)(1.3)1-1N(N-I)如果这段文字充分长,那么我们有ni(m-1)Jj-(1-4)N(/V-1)N2如果记0=表示第i个字母在这段文字中出现的物率，那么N返2i(1.5)aP而我们先前提到，统计学家已经统计出在英文文本中各个字母出现的频率,因此，带入上述式子可以得出英文文本的巧合指数IC«0.0686.接着我们统计加密过后的税文的巧合指数,假设密钥为心我们对K=0,125依次去试，如果出现了解密后的文本的巧合指数接近于0.0686.就说明这个A有很大可能是密钥，13.4多表代换密码为了迸一步提高安全性，古代的人们想到也许一张表并不足够安全，不妨使用多张表。因此,多表代换密码应运而生.假设一共有t张加密友，人们是怎么做的呢？从明文的第一个字符开始，第一个字符使用第一张加声表iS行加密，第二个字符使用第：张加密表进行加密，以此类推，第r个字符使用第，张加率表进行加密.到了笫，+I个字符则又回到第一张加密衣进行加密，用数学的语言怎么叙述这件事呢？对于明文字符申W=Wg1.Wm我们要求其长度湎足n=tp我们将明文字符串等分成个列向IitAI,必，.M),其中M='m*","iiM2%-g"对密文字符中C也作同样的划分C1.C1.Cp.取能钥为0.B),其中矩阵A为r*r的可逆矩阵，旦满足gcd(4,26)=1.8为，雒列向最.那么多表代换密码的加定算法为Ci=E4,B(fi)=C(A(Af1)+B)mod26)(1.6)解带算法为M1.=D,b(CD=CA',(C-B)mod26(1.7)其中A-'满足'11mxJ26=我们可以用一个具体的例子来理斛这些抽象的公式：假设我们一共有三张表，分别使用第钥为(1.D.(33).(57)的单表替换密码生成。明文字符出(M=“小小的长度11=姑我们将其等分为P个列向量：A%.M?.,”,其中M=m.m.m.对于密文字符串。也作同样的划分C.C.C.tp(/-Hp<f->*2X<-HI2p取1OOIA=030,B=30057为密钥，僚么其加密算法为CKi1.100Ic¾:2005=Cf=E.b(Mi)=03()Mi+3mod26,9tp(I-1)*1+13加1.-2+3mod265Cp(I-1>j+7其解密算法为1001Mi=DAB(G)=090G-3mod2600217那么我们可?看到，从明存的第一个字符开始，每隔三个字符的第一个字符使f的加密方)法为QX1.=%xn1.mod26.笫：个字符使用的加密方法为QXi-I).2=3wptr-)*2÷3mod26.第三个字符使用的加密方法为CmFQ=%，”川7).3+7)mod26.这也就是我们设计多表代换密眄的原意.我们发现，在上述例子中,密钥里的A似乎有许多0的位置。但是，我们之前在数学上严格定义多表代换密眄的时候,并没有要求这些位置一定要是0.事实上,这些位置如果不是0,就意味者密文中特定位徨的字符并不是由明文中对应位混的字符确定，而是明文中对应位置与前后位置的字符一起确定。这也是可行的，多表代换密码也是不安全的。我IH利用多表代换密码同样加密上面提到的东南大学校徽，得到的结果也很不理想：图1.3:多衣代换加密前图1.4:多表代换加密后1.3.5一次一密之前我In说道.单表代换密码可以根据每个字母出现的频率求破解,其实多表代换密码的破解也很类似.那么.有没有什么方法能使密文不显示明文中每个字母出现的领率呢？一次一密的方法就是答案。为了加密某个长度为"的字符我们取另一个长度为n的字符*作为密钥，所得的密文就是明文每个字符在字母衣中的位置与密的每个字符在字母衣中的位盥相加.由密文得到明文也就是密文中每个字符在字母友中的位置与密钥每个字符在字母式中的位也相减.这种方式之所以称为一次一密，是因为同一舟密切只能使用一次。试想如果有人窃得了用同一耶率胡加密的两个密文C1.C2.将这两个字符中中的母个字符按其在字母表中的位置相减,那么如果出现0.那么对应位置就就有可能是出现频率比较高的几个字母.当然,更叩逆的论证可以用之后提到的概率论的方式证明，朵后,值得一提的是，现代使用的量:子加率中,最常用的加密机制就是一次一密.1.4加密系统的安全性为了从数学上定义加密系统的安全性，我们必须引入一些和概率有关的定义，这时，清回忆一下之前定义的加密方案(E.D.G).H,E代表加定算法.D代表解定算法.G代表密钥生成算法.此外，还有明文空间M,密文空间C,密钥空间K.对于MeM.M为表示明文的随U1.变Jk用Pr”=刈发示明文为树的概率.这一定义看似难以理解，为什么明文会出现概率呢？从某种醺义上，"J以理解成假想的敌手在没有仔何信息的情况下旃测明文的概率.比如说,在没有任何信息的情况下,一个敌手可旎会假定明文为"attacktomorrow"或"don'tattack”.I1.敌手认为明文为''attacktontrrow"的概率为0.6.明文为“don'tauack”的概率为0.4.对于kEK.K为表示密阴值的随机变量,用PrIK=向表示随机算法G输出A的概率(由常识可知,K与M是独立的)对于CWC,C为我示密文的1.¾机变fit,用PrIC=<,我示密文为。的概率.由于密文是完全由明文及密钥确定的，所以我In可以知道：PrC=Cj=Pr=,"JPrK=同(1.8)dkm)我们定义完善保密(perfectsecrecy):定义1.2.时于明文空间为M的加密方案(E.D.G”若时M上的任何概率分布,任何明文，"£M、任何榭文CWCJ1.PrC=C有PrM=mIC=c=PrM=11j(1.9)则称加密方案(ED.G)是完善保密.用一句通俗的话来U1.就是故于在初取楞文之后并不会对明文有任何知识.而用概率论的说法,则是随机变mAf与C是独立的。我们可以通过一些概率论上的技巧，证明“一次一密”的加密方式是完善保密。但是,完善保密也有其胶柱鼓瑟之处：定理1.1.若明文空间为M的加密方案(E.D.G)是完善保密，则KM,CM(IIO)如果用通俗的语言解择说定理，则是说：要想实现完善保密，则密钥至少要和明文一样长,而密文则也至少要和明文一样长.我们之前说过，要想实现加密迪信，通信双方一定要事先在安全信道中沟通密伪.如果密物至少和明文一样长，那与其沟通密钥，不如宜接把明文告诉时方了。此外，生成的密文也至少和明文一样长.这也是I分浪费通信资源的手段。因此我们可以看到，完善保密确实是一个难以实现的目标.对于那兴鲤的同学，我们可以介绍-,个判断个加密方案是否是完善保密的简单方法，即乔农定理：定理1.2.对于明文空间为M的加密方案(E,D,G),若K=M=Ia则当且仅当下列条件成立时，此方案是完善保诙加密；由G产生的任意密例keK的概率都是K2对任意明文，eM和任意密文¢6C,只存在唯一的密钥人K使得C=E*("，).关于完善保密，我们的讨论就告一段落.最后，介绍一下对加密系统安全性的分类.对加密系统安全性的分类，现在主流学界习惯上以敌手的筋力及时间进行灯分： 无条件安全如果假设攻击者在无限优源的前提下，也无法破译加密算法，就认为相应的密码体制是无条件安全的，这里的无限资源，可以包括无照算力和无限时间.可以把无条件安全的加密方式理解成完美加宙， 计算安全使用目前以好的方法攻破它所需要的计算远远超出攻击者的计算资源水平，则可以定义这个密码体制是计算安全的。比如说，如果要岐解某个加密能法街要用当今以好的计算机连续工作一万年，那么我们就可以认为这个密码体制是计算安全的. 可证明安全如果破译某加雷算法的困潍性与破解某些困难教学命SS的困理性相同(如大整数的因数分斛)，则可以定义这个格玛体制是UJ证明安全的。值得指出的是，关于加密系统的安全性，尽管我们使用日常的诺古叙述的这些概念，但这些概念实际上都是有严格的教学定义的。鉴于我们日前的教学水平有限，在这里引入这些数学概念是不适合的.，因此，我们仅从序性上理的这些概念即可。第二章流密码与伪随机数发生器2.1 数学上的基本概念从这章开始，我们就不再拘泥于古代的加密拉丁字母的加密方式，而开始转向数字化得我们知道，在现代和廿支中，密码学坦常应用的领域就是计算机领域，而计算机领域则是由：进制的0.1申构成。因此，在接下来的讨论中,我们都将明文空间及密文空间看作由U和1构成的二进制串编成的集合.因此,为了接下来能更顺畅地进行关于流密码的讨论，这里先介绍一些数学上关于这方面的地础知识。2.1.1 GF(2)上的加法与乘法由于我们讨论的仅是U和1及它们的运算.因此,我们定义一个有限域GF=O.I.行限域GF上的加法被定义成逻辑I.的异或.也可以理解成模2加法.以下为GF(2)上的加法我:表2.1:GF(2)上的加法表+01如果我们定义一个集合中元泰。的加法逆元-满足a+(-«)=(-)+«=0则GF0)上的加法逆元表为:表2.2:GF(2)上的加法逆元表Q0I一”01而GF(2)上的减法则可以定义成与加法逆兀的加法,即a-b=a+(-b)GF上的乘法则被定义成r逻辑上的与“以下为GF(2)上的乘法表:表2,3:GF上的乘法丧根据上述的定义，我们可以得出以卜GF上常用的运算规则：*V.vGF(2).+.v=0(2.2)V.yGF(¾,->=y-.V=X+>>(2.3)*VGF(2),.r=x(2.4)212GFQ)上的多项式此外,还有一个我们未的接触过的知识：GF(2)上的多J式.为此,不妨先介绍一下多项式理论.对于友达式Xanxn+an-xn'+a)x+«<i=a1.X(2.5)r-O我们称其系数为小m.an.其系数翼S为如Q的取值范围。当时.称该多项式为S上的”次多项式.比如说.如果其系数的以俄仅限于0和1.则称这个多项式为GF2上的多项式.值褥指出的是，我们研究把项式理论时，多项式在我们眼中仅仅是一个表达式，我们并不需要去对堤一个X的取值进行多项式的求值,它就相当于一个集合的元索，一个多项式就是一个最小的单位.其加、履、乘、除就应该像我们定义更数集那样重新地进行定义.也就是说,我们通过定义来确定多项式/+R=九而不是通过Vx,(x)=Z()+()来定义多项式之和.尽管结果确实如此，但这应该理解为白治的定义，而非推导.多项式的加法两个多项式之和的多项式的系数，等于其对应系数之和。即：若m”,JW名支宅£(IiXt+bjj=(i1.k+i>k)Xk+UiXt(2.6)*-O>-OXi-rw1.其中OA+bk的加法应理解成系数集S上的加法.用更形象的方法来说,我们不妨考虑次数集上的多项式/=+1与&=/+X2,那么其和我们可以类似于小学时的竖式来计算:但是，我们这里也需要注意到刚刚说的，砒十8的加法应理解成系数第S上的加法.比如说还是刚刚的两个多项式，但其在GF上的加法为：f=A-+1g=Xi+X2+i/+g=XJ这里2/与2之所以不见了，是因为在GF上，1+1=0.多项式的减法类似于多项式的加法的定义，两个多项式之差的系数，等于其对应系数之差.在GF(2)上的多项式之差的例子：f=X2+1g=.?+X2+1f-g=JTj这里是山于(O-1)j=(0+1)=j,(1-1)-=0,1-I=O.多项式的乘法我们可以形式上地用乘法分配律进行计并且约定XiV=a.下面演示一下GF(2)上多项式的乘法运算：s+S+|)=XV+(t+1)X+1=X1+1注意到在GF(2)±,(I+1.).v=0.同时,我们记/=T多项式的用除对于多项式/和©如果存在多项式力,使得=g九则称g整除，i单Za/；同时£=.注意这仍是在系数集S上的.比如说.在GF（三）中,我们行1+JI(X+1)2此外，若一个多项式,是不可约的，则说明不存在两个多项式&九使得ga=/且的次数均小于/的次数.GF上的常用等式加法交换律+/(2.7)加法结合律(2.(8)(2.(9)(2.(10)(2.(11)(2.(12)+g)+=r+(g+)乘法交换律fg=nf乘法结合律()h=f)乘法对加法的分配律/(S+)=+4等比数列求和公式：对于多项式/和m=r,/+«/-+y2+11-*=,=i-g总结在GF这个有限域上的运算和我们在实数集J1.的运算很不一样,所以在后文中我们应该岩羽注意运算是定义在GF上的还是定义在实数集上的.同时，我们也该清也定理叙述的是多项式之间的关系还是值之间的关系。2.2 流密码的基本概念之前我们讲到“一次一密”的加诙方式是完善保密，同时，“一次一密”的跳点也十分显著：密倒过长.那么有什么办法能规避这样的缺点呢？事实上,“一次一密”的加密方式之所以是完善保密的.最重要的一点是每次密钥的字符串足时机生成的.通过之前讲的香农定理我们可以知道，饵个密钥字符申生成的概率均是相等的，如果我们可以降低一点这种Ia机性的要求，那也许就能实现短密钥+强保密的目标。为此,我们引入伪随机数序列的概念.由于这个概念的严格定义需要高超的概率论及尊法知识，我们只需要感性地理解伪机数序列为一种，由确定的徵法产生的(即相同的初始条件下的输出是相同的)，马式Ia机数序列性质几乎一样的序列，那么源密码的工作模式可以筒单地看作：对于给定长度的一串明文W=W,也"E.我们输入密钠长通过某种算法产生一个同样长庆的伪骸机序列Z=MW二”作为密物流.输出结果Y=yy2-以为明文中与伪随机序列按位异或的结果=加,由的取据之前在GF(2)上的讨论，解密算法也是将留文申与密钥流进行按位界或，即m1=>,21.根据上述的定义，流率玛与一次一密的区别就在于，在与明文率进行按位异或的过程中，一次一密使用的是其随机序列.波密码使用的是伪Mi机序列,如何能使伪陋机序列的表现足幡像真随机序列，则是流密码安全性的关键,因此，对流密码的研究,主要就在于产生仍随机序列的算法上。设/也“1)为一个能产生伪随机序列的算法，其中人为输入的密钥，6为当前时刻系统的状态.在每个时刻.，件"。输出一个伪随机数.同时系统状态改变为“i.常把一个用于加密幻法的伪随机序列称为密钥流,产生伪随机序列的系法称为密的潦生成器.之前在讲到密钥流生成器的时候，我们提到了系统当前的状态,.这里的状态，是根据当前的输入和输出而变化的.每输入一个数，密钥流生成器祗输出一个数，当前系统的状态就发生了变化.之后会介绍一些具体的例子让大家更加理解“系统的状态1的含义.在这里,我们将流密码分为同步流密码和自同步流密码.如果密钥流生成器中的状态与怆入的明文有关.则称为自同步流带码，反之则称为同步流密码。同步流密码中，伪随机序列与明文无关，因此,可以独立出来作为单独的部件,其称为伪防机比特发生推(PRBG).对于自同步波密码.可以参看之后分组密码的CFB模式.那么流密码的过程