第4讲 密码学基本概念和基本编码技术

-,*,-,第4讲 密码学的基本概念和,基本编码技术,信息安全概论,课程幻灯片,主 要 内 容,一、密码学的基本目标,二、密码学中有关加密算法的一些基本概念,三、最基本的破译方法-穷举攻击,四、三个基本的编码原理,敌手的攻击方法:,A：,信源,B：,信宿,C：,敌手,公开信道,一、密码学的基本目标,（2）主动攻击：,不仅窃听，而且还改变传输的信息，,（1）被动攻击,(窃听),：,获取但不改变传输的信息,目的是实现伪造和欺骗。,(不考虑破坏信道的主动攻击),（1）对抗窃听的技术：,加密技术,A：,信源,B：,信宿,C：,敌手,加密,脱密,消息已变得面目全非,密码学要解决的第一个基本问题：,信息的机密性,问题-能解决信息的,传输保密,和,存储保密,问题。,（2）对抗主动攻击的技术：,认证技术,A：,信源,B：,信宿,C：,敌手,添加认证码,检验认证码,消息已经可以识别真伪,密码学 要解决的第二个基本问题：,信息的,真实性认证,问题（能检测出主动攻击）,(1)发方的身份；,(2)收方的身份；,(3)内容的真伪；,(4)时间的真伪,（3）对抗抵赖的技术,密码学要解决的第三个基本问题：,-,承诺的,不可否认性,问题,.,例:,如果我收到你给我的一份,定货合同,或者,电子借款收据,，但是:,-事后你不承认这份,定货合同,怎么办?,-谁来裁决这份定货合同的真伪?,-互不信任双方,的,认证问题-,公证机关、法官、法律,要求：,添加认证码后能让,所有人,都可识别承诺的真伪,B：,信宿,C：,敌手,添加认证码,检验认证码,A：,信源,（3）对抗抵赖的技术,-互不信任双方,的,认证问题-,承诺,密码学的基本目标就是解决信息安全的三个基本安全需求，即：,（1）信息的,机密性,保证；,（2）信息的,真实性,认证；,（3）承诺的,不可否认性,保证。,由加密算法完成,由认证算法和,配套的协议完成,由数字签名算法、配套的协议和仲裁机构完成,密码是确保军事信息安全的核心技术！,二、有关加密算法的一些基本概念,被加密保护的消息,对明文加密的结果,目的:,从密文中获取明文,发方,收方,密钥,该过程称为,密钥分配,破译者不知道,Kerckhoffs,假设:,-假设敌手知道,除密钥之外,的所有知识!,-即要求：,一切的秘密蕴于密钥之中!,对敌手攻击能力的基本假设：,-思想：假设敌手具有最强的攻击能力！,假设敌手知道:,(1)所使用的密码算法;,1.对敌手攻击能力的,Kerckhoffs,假设：,如此假设的原因:,(1)我们不能保证敌手得不到这些信息!,-绝对不能赌！,(2)如果在这么优越的条件下仍不可破译，说明密码算法在实际中将会更加安全!,包括5个方面：,(1)加密算法,E,k,(,m,),(2),脱密算法,D,k,(,c,),(3),明文空间,M,(4),密文空间,C,(5),密钥空间,K,E,k,：,M,C,(2)知道明文的概率分布规律;,(3)知道密钥的概率分布规律;,(4)知道所有可能的破译方法!,2.三类主要的攻击方法:,（,1,）,唯密文攻击,：,敌手除加密算法、明文和密钥的概率分布外，还知道很多由同一个密钥加密的密文。,（,3,）,选择明文,(,密文),攻击,：,敌手除具备已知明文攻击的条件外，还可任意,选择,对他有利的明文,(密文),并能得到相应的密文,(明文),（,2,）,已知明文攻击,：,敌手除具备唯密文攻击的条件外，还知道许多密文对应的明文。,分类方法：,按敌手可利用,知识的类别,分类,如果没有密钥会怎样?-谁都可脱密,!,如果可能的密钥太少会怎样,?,-,如果对每个可能的密钥都,逐个测试,，则一定可以碰到正确的密钥，利用它就可脱密,!,这就是穷举攻击方法！,穷举攻击,就是逐一利用每个可能的密钥对密文进行脱密测试，,三、最基本的破译方法-对密钥的穷举攻击,并将,脱密结果最合理,的那个密钥判断为正确密钥.,何为最合理？,与攻击者掌握的明文的信息最吻合！,如何区分真假密钥？,要想能抵抗穷举攻击，一个加密算法的可能密钥总数不能太少!,一个加密算法的可能密钥的总数称为该密码算法的,密钥变化量,。,目前，密钥变化量少于2,64,的密码算法不能对抗穷举攻击，因而是不安全的!,密钥变化量为2,128,的密码算法是能够对抗穷举攻击的!,为什么?,密钥变化量的安全界限：,假设,密钥的变化量,为2,128,.,现考查该加密算法抗,穷举攻击,的能力。,假设计算机每秒能检测2,30,个密钥。由,1年可检测3.1510,7,2,30,=2,55,个密钥,需要2,128,2,55,=2,73,10,22,年,即一百万亿亿年，才可能将所有可能密钥测试一遍。,即使,计算能力再增加10亿倍（10,9,），也需要10,11,年，即一千亿年，才可能将所有可能密钥测试一遍。,1年265243600秒 3.1510,7,秒,穷举攻击是最笨、但往往也是,最有效,的攻击方法。,例如：,用生日、电话号码当密码。,用攻击方法所需要的,计算量,、,存储量,、,已知的数据量,和,成功率,衡量,银行的对策：,限制试密码的次数。,密码算法设计的最理想境界就是让所有可能的破译方法都比穷举攻击更,无效,!,安全的密码算法应能够对抗所有可能的攻击方法。,-能让所有可能的攻击方法,失效,！,穷举攻击是,最笨,、但往往也是最有效的攻击方法。,用攻击方法所需要的,计算量,、,存储量,、,已知的数据量,和,成功率,衡量,-谁证之？,设计者应先给出证明。,四、密码算法的基本编码技术,四、密码算法的基本编码技术,1.信息加密的一般流程,消息,处理,数字,加密算法,脱密算法,数字,消息,还原,信源编码,信源编码,明文,密文,明文,加密密钥,脱密密钥,不属于密码学,基本编码技术的分类,(1)代替密码,利用预先设计的,代替规则,对明文,逐,字符,或,逐,字符组,进行代替的密码.,分为,单表代替,和,多表代替,两种,(2)移位密码,对各,字符,或,字符组,进行,位置移动,的密码,.,(3)加减密码,将明文,逐,字符,或,逐,字符组,与乱数,相加,或,相减,的密码.,利用预先设计的,固定,代替规则,对明文,逐,字符,或,逐,字符组,进行代替的密码.,2.单表代替密码,指代替规则只有一种，因而与,密钥,和被加密的明文字符的,序号,无关。,故,相同的,明文字符组一定产生,相同的,密文字符组。,称为一个代替单位,又称为,代替函数,、,代替表,或,S,盒,例1:汉字和符号的区位码(单表代替),00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,2200,丁,盯,叮,钉,顶,鼎,锭,定,订,丢,东,冬,董,懂,动,栋,侗,恫,冻,2220,洞,兜,抖,斗,陡,豆,逗,痘,都,督,毒,犊,独,读,堵,睹,赌,杜,镀,肚,2240,度,渡,妒,端,短,锻,段,断,缎,堆,兑,队,对,墩,吨,蹲,敦,顿,囤,钝,2260,盾,遁,掇,哆,多,夺,垛,躲,朵,跺,舵,剁,惰,堕,蛾,峨,鹅,俄,额,讹,2280,娥,恶,厄,扼,遏,鄂,饿,恩,而,儿,耳,尔,饵,洱,二,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,0100,、,。,“,”,0120,【,】,0140,0160,0180,由于上述,对应关系是,公开的,，而且,编码规律,很强,，因而它实际上是明码而不是密码。,例2,以,十进值数,为代替单位的,S,盒,则对明文“,晨五点总攻,”的加密可分两步：,（1）先将明文变换为区位码,1931,4669 2167 5560,1505,（2）,将编码结果加密成密文,4624 1996 8497 0095 4050,脱密时执行上述过程的逆过程即可。,单表代替的缺点：,明文字符时密文字符也相同。,明文 0 1 2 3 4 5 6 7 8 9,密文 5 4 8 2 1 0 9 7 3 6,即代替表为:,这是一种对,英文字母,逐字母加密的密码。,加密变换为,：,例4,Caesar,密码,(,凯撒密码,),将英文字母转化为数字的方法：,-转换为该字母的序号,英文,A B C D U V W X Y,Z,数字,0,1 2,3 ,20 21 22 23 24,25,被26除所得的非负余数,例：27,mod26=1;,26,mod26=0;,(-5),mod26=21,读作：,模26,加密变换为,：,例4,Caesar,密码,(,凯撒密码,),将英文字母转化为数字的方法：,-转换为该字母的序号,英文,A B C D U V W X Y,Z,数字,0,1 2,3 ,20 21 22 23 24,25,明文字母,A B,C D U V W X Y Z,密文字母,D E F G X Y Z A B C,例如：明文,cipher ,密文,flskhu,脱密变换为,：,即：,单表代替的缺点是：,只要两个明文字符组相同，则对应的密文字符组一定相同。,多表代替密码可以克服这个缺点。,3.多表代替密码,根据密钥的指示，来选择加密时使用的单表的方法，称为,多表代替,密码。,例4：,加密变换为,：,但,k,不是固定常数而是密钥。,加密算法：,明 文：,晨 五 点 总 攻,明文序列：,1931 4669 2167 5560 1505,密钥序列：4321 5378 4322 3109 1107,密文序列：5252 9937 6489 8669 2602,如果密钥序列是随机的,该密码称为,一次一密体制,，它就是,绝对安全,的，,不可破译,。,3.多表代替密码,因为即使密文已知，明文取每个值也都是等可能的。,随机,就是指序列的信号相互,独立,且,等概,分布,拉丁方变换,E(,k,i,m,i,),随机的,密钥序列,k,1,k,2,k,3,密文序列,c,1,c,2,c,3,明文序列,m,1,m,2,m,3,一次一密的密码体制的一般结构,f,(,k,m,),m,1,m,2,m,4,m,n,k,1,1,2,3,4,k,2,2,3,4,1,k,3,3,4,1,2,k,4,4,1,2,3,拉丁方变换的含义：,拉丁方表的各列、各行互不相同,即使密钥相同,不同的明文也被加密成不同的密文,即使明文相同,不同的密钥也将之加密成不同密文,意义:,例:,一次一密的密码体制的缺点,密钥序列是随机序列意味着：,（1）密钥序列不能周期重复；,（2）密钥序列必须与明文序列等长；,（3）这些密钥序列必须在通信前分配完毕.,（4）大量通信时不实用；,（5）分配密钥和存储密钥时安全隐患大。,解决方案：,密钥序列由少量真随机的数按固定的算法生成，只要它,很像,随机序列即可。这种序列称为,伪随机序列,。,求不出该序列不像随机的地方！,4.序列密码算法的基本结构,问题2：,与明密文无关,问题1：,描述不细致！,序列密码的一般结构（数学模型）,内部记忆,明文反馈,密文反馈,五、移位密码,移位密码,就是,对明文字符或字符组的进行,位置移动,的密码,例,：设,明文,为：,解放军电子技术学院,移位方式：,S9=2,5,7,3,4,8,9,1,6,即,:,第,i,个密文汉字就是第,S,i,-1,个明文汉字.,则,密文,为,放子术军电学院解技,移位是设计现代密码,常用,或,必用,的一种编码技术,移位密码与代替密码的优缺点对比：,1）移位密码的优点:,明文字符的位置发生变化,移位密码的缺点:,明文字符的形态没有改变,2）代替密码的优点:,明文字符的形态发生变化,代替密码的缺点:,明文字符的位置没有改变,优缺点互相弥补！,交替使用代替和移位形成的密码算法,S,1,S,2,S,8,S,3,S,4,S,5,S,6,S,7,逐字符移位变换,S,1,S,2,S,8,S,3,S,4,S,5,S,6,S,7,逐字符移位变换,S,1,S,2,S,8,S,3,S,4,S,5,S,6,S,7,逐字符移位变换,六、加减密码-一种特殊的代替密码,这里,k,可以是固定常数，也可以是密钥。,明文空间：0,1,2,9,