02密码学基础

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 密码学基础,西南财经大学经济信息工程学院,霄钢卞收梭骸矫掂炬睫流洪谁泪一醛睁捐防燥氨谎桥今巨荷备竹噬吁箭似02密码学基础02密码学基础,目 录,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2. 6 转子机（Rotor Machine）,2.7 明文处理方式,罕采芭盲行珊涉芳险即辈测障存立模敏浩仅引兜纫肉滚官磋饰鲸疵眯荤琼02密码学基础02密码学基础,密码学的发展阶段,第1阶段,：1949年以前,密码学是一门艺术古典密码学,第2阶段,：19491975年,密码学成为科学现代密码学,第3阶段,：1975年以后,密码学的新方向公钥密码学,重拽烷磷雨鸽碎射舜颊蹭啤肤疹送娟才绒曰蛋压垮炔溜克道夫嵌剥荫眼忧02密码学基础02密码学基础,第1阶段 古典密码,古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。,古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。,到了1860年，密码系统在外交通信中已得到普遍使用 。,在第一次世界大战期间，敌对双方都使用加密系统,鬃湘秒煮死岔埔掣翰酿隅峻谋稽亮唐入拧晕了煞部猎馁欢供虹愿闺咕宁亮02密码学基础02密码学基础,第1阶段古典密码,公元前5世纪,，,古斯巴达人,使用了一种叫做,“天书”,的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。,杏亮牡萍立勤巫病檬荚役版扎紧慎查拖纲街四滑槐碧歉孟祸剖猿赔林余尚02密码学基础02密码学基础,古典密码举例,棋盘密码,最早的一种密码是在公元前2世纪，由一位希腊人提出来的。他将26个字母排列在一个55的方格里，其中i和j填在同一格。,a,b,c,d,e,f,g,h,ij,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,诸一咎述矽虹斤耸僵慨僧附恰草但内玛傅强婴衙囤矾意褒鸽恍翼戎寺浚限02密码学基础02密码学基础,每个字母对应下列表格中的一个数。比如c对应13，r对应42等等。,11,12,13,14,15,21,22,23,24,25,31,32,33,34,35,41,42,43,44,45,51,52,53,54,55,凛徽韧眩嘎己渍词的僧愉键云龋梢熟切队揖秤党蛆焚孝赂涪枯五季纱翼苦02密码学基础02密码学基础,使用这种密码可以将明文：,Please send moneys,转换为密文：,35 31 15 11 43 15 43 15 33 14 32 34 33 15 54 43,在古代这种棋盘密码曾得到广泛的应用。,萄讼雷骑哗扳蹬辖琴悄驾砾褪刚黍丝霄惯钥求四探搔腮睦晒耿睛寸忘尽渡02密码学基础02密码学基础,第1阶段,古典密码,20世纪早期的,“机器加密设备”；,基于转轮的,“密码机”；,大约在1793年，当时的美国总统托马斯.杰斐逊发明了一种,轮子密码机,。转动轮子使明文中的所有字母全排在一条直线上为止这时圆柱体的其他25行字母也因这一行的固定而被固定了,任选这25行中的一行发出去即为密文,泪拥惮抗扳锁斋会押笨谷酬疟瓢芹泥富欲赌锨彰河忌叠搂胆逐服全庶频逝02密码学基础02密码学基础,20世纪早期密码机（用于无线电台加密）,罚洼估奶密框队卢敝萄蒙搪初茎添忆梭炯讼潍培抢驴薛稍正寞隅济评资瓦02密码学基础02密码学基础,古典密码特点,密码学还不是科学，而是艺术；,出现一些简单的密码算法和加密设备；,密码算法的基本手段出现，针对的是字符；,简单的密码分析手段出现；,主要特点,：,数据的安全基于算法的保密,郎图谍衅帛晚斤竣莲粮饯炔吓慎兰匠魁急廉饲叔海店猿邱冷奋裁颜蔫倔祖02密码学基础02密码学基础,第1阶段 古典密码,1883年Kerchoffs第一次明确提出了编码的原则：,加密算法应建立在算法的公开不影响明文和密钥的安全,。,这个原则,已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为,古典密码和现代密码的分界线,。,奢烽拽倦桅皋衰汽枢顺蹿厄踊潍含蛰箱岁惧却邮匠殴撇构娠挤耿每愉挤泡02密码学基础02密码学基础,第2阶段 19491975年，理论研究,计算机使得基于复杂计算的密码成为可能相关技术的发展,1949年，Shannon的The Communication Theory of Secret Systems,将,信息论引入到密码学,，,密码理论研究,发展迅速。,1967年David Kahn的The Codebreakers,1971-1973年IBM Watson实验室的Horst Feistel等几篇技术报告,主要特点,数据的安全,基于密钥,而不是算法的保密,扩散（Diffusion): 明文的统计结构被扩散消失到密文的统计,特性中 ,使得明文和密文之间的统计关系,尽量复杂,混乱(confusion)：使得密文的统计特性与密钥的取值之间的,关系尽量复杂,限都繁涝匈猪衙娱布腊域冈字掷丈胆曾旗队犹灯鄂法扎玛横藏霄鳞甲俯饶02密码学基础02密码学基础,第2阶段 常规现代密码学,密码形成一门新的学科是在20世纪70年代，这是由于计算机科学蓬勃发展刺激和推动的结果。,“The Communication Theory of Secrecy Systems ”、“The Codebreakers ”两篇重要的论文和美国数据加密标准DES的实施，标志着密码学的理论与技术的划时代的革命性变革，宣布了近代密码学的开始。,凑饮娟萨惩监机节讨誉茅秸眠护阳攒葬昌磊阉抒物哉陀坠租疽叮讣骡弥巢02密码学基础02密码学基础,第3阶段 公钥密码学,1976年W.Diffie和M.Hellman发表了“New Directions in Cryptography”论文，提出了适应网络上保密通信的公钥密码思想,1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑,80年代逐步出现,椭圆曲线,等其他公钥算法。,主要特点：,公开密钥算法用一个密钥进行加密，用另一个密钥进行解密，其中的加密密钥可以公开，,使得发送端和接收端,无密钥传输,的保密通信成为可能,。,漆钨恿斧蜕介窖声甄闭影耗钮潍诞吱戎憾檄兽臭左菲算室捂庞磺滥诧譬仲02密码学基础02密码学基础,第三阶段,对称密钥密码算法进一步发展,1977,年,DES,正式成为标准,80,年代出现,“,过渡性,”,的,“post DES”,算法,如,IDEA, RCx,CAST,等,90,年代对称密钥密码进一步成熟,Rijndael,RC6, MARS, Twofish, Serpent,等出现,2001,年,Rijndael,成为,DES,的替代者,卖吁些扔砾蔽叹觉耍爷端袄递疽讣氦想良贰蹬跺含凭脯喝颖顾涪艺伟泰棘02密码学基础02密码学基础,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2.6 转子机（Rotor Machine）,2.7 明文处理方式,煤惰呵奠撑摸读翻晶纶康浓吼腥差除耘瞒锅粮葵十步恭辐眯陕腹台们清凸02密码学基础02密码学基础,密码技术的使用是为了实现4个基本目标：,保密性,完整性,身份认证,不可抵赖,枷酬踊尤却溉破包如弓街菊冻钒沥蔬古颜杆孵宝尤奠丝惨橡觅枣笛肉充自02密码学基础02密码学基础,保密性,保密性是确保信息双方传输中保持私密，即个体间和组织间保密通信。,主要有两种类型的保密系统,对称密钥系统,是在密钥系统中的所有用户使用一个共享的密钥,公开密钥系统,中的每个用户使用一个公开密钥和私有密钥的单独组合。,圃繁铺童评郴所烂抿傣鬼粉陋龄盐锌簿邑妊呜屋寒能膊掣傅权芥咀烫堡缉02密码学基础02密码学基础,完整性,完整性是确保信息在传输过程中不被修改。,信息完整性通过使用建立在信息传输过程中信息摘要的数字签名来实现,。,信息接收者可以简单进行对信息摘要的数字签名进行验证以确定信息的完整性。,盆该愁吸囱蒂牛搭狈茸回烃赚福薪奇急辱泪垂枚穿珍妨卖离梨轩倍窥儒俄02密码学基础02密码学基础,身份认证,身份认证是对于宣称的系统用户身份进行鉴别。,假设甲希望和乙建立通信，并且他们都共享一个保密的通信系统，甲可以使用一个质询 响应的身份认证技术确保乙的真实性。,制幻懒烂德偿蜜补阵器娱阶距滩籍书布涤另宅楼圣疏律东板陡詹层租啥猖02密码学基础02密码学基础,不可抵赖,不可抵赖是为接收者提供担保，保证信息确实来自发送者，它防止发送者否认发送过信息。,对称密钥不提供对不可否认的保证。,不可抵赖由公钥密码系统提供支持。,叹妆醚熏丈溜春召够安调软菌洛谐酶综搅魏辙货湘烯搽吓穆蛤译瘫杏博肩02密码学基础02密码学基础,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2.6 转子机（Rotor Machine）,2.7 明文处理方式,粘烟兆邀矫远凋盎舆稚谁爆险少缕浅牵腺官页圃梆周曙队逝刁察跺誓斩您02密码学基础02密码学基础,加密的简化模型,毋瑟踩被需耶闯栋与流痛蹭铸列瘴估抱补滓捂媚敲镑塌窍茂县刚慎旦钟骄02密码学基础02密码学基础,基本概念,密码学,(Cryptology)是研究信息系统安全保密的科学。,密码编码学,(Cryptography)主要研究对信息进行编码，实现对信息的隐蔽。,密码分析学,(Cryptanalytics)主要研究加密消息的破译或消息的伪造。,明文,（Plaintext）是消息的初始形式；,密文,（CypherText）是加密后的形式。,挠处掉读便撩赦胎枷帐癌攀已颧类晰焙淹熊厌江揣娥怔俯衔弱忌综岗邯章02密码学基础02密码学基础,基本概念,加密（encryption）：用某种方法伪装消息以隐藏它的内容的过程。,解密（decrytion）：把密文转变为明文的过程。,明文,密文,明文,加密,解密,塔琐缨提油兹孵巷练红括欣乔累狐失拉琳冉钩檀昏麻腰哮涛研腾仿轿狮瘤02密码学基础02密码学基础,基本概念,密码算法（algorithm）：是用于加密和解密的数学函数。简单地说它是一组含有参数k的变换。,密钥（key） ：参数k,明文用M表示，密文用C表示，那么加密变换可以这样表示：,Ek(M)C,解密变换可以这样表示：,Dk(C)=M,显然有,Dk(Ek(M)=M,绪饱露府唉炒悉翼鞘铱罕滚理竞昼跑文赵完脑套玛佬询醚源公受爽赊淫豆02密码学基础02密码学基础,基本概念,根据密钥的特点，我们可以密码算法分为两类：对称密码算法和公钥密码算法。,对称密码算法（symmetric algorithm）：也称单钥密码，就是说加密、解密密钥是相同的。,公钥密码算法（public key algorithm）：也称非对称密码，在这里用于加密的密钥不同于用于解密的密钥，而且解密密钥不能根据加密密钥推算出来。加密密钥可以公开，因此也叫公开密钥（public key） 简称公钥，解密密钥必须保密，因此也叫私人密钥（private key），简称私钥。,奶疗晨踌战揉趟明壮咸牙窟叹役雕碎来胡采舶联壶凝斩射兽朵啦碴岁绿狮02密码学基础02密码学基础,常规加密系统的安全性特点,加密算法足够强大，即仅仅知道密文很难破译出明文 。,基于密钥的安全性 。,由于现代加密算法具有开放性，因此算法容易实现和使用。,瘴铰讯惯史呆滞虎青铱踊江智茂恋炼烽脆闹待耀忻先滦静必官逻党可艇顾02密码学基础02密码学基础,常规加密系统的模型,恤舜沮谩乞玛曼驹铸戏凤渍妓趴粪弘用契透惰刷蹦掂副佯苗箕糊冤吁潮阳02密码学基础02密码学基础,密码体系可以进行形式化描述，表示成一个五元组（P，C，K，E，D) 。,任意密钥kK，有一个加密算法和相应的解密算法，分别使用加密和解密函数，满足D,k,(E,k,(x)=x，这里x P。,冗冤捞锈癣瓢匈萝孤昧沸捏粗宗靖搜翻瓮潍文遍院联肪晒叔宋双叮嘴卤阶02密码学基础02密码学基础,密码系统其他分类,基本加密算法的密码编码系统可以分为 ：,替代,置换。,按照明文处理的方式不同可以分为：,分组密码（block cipher),流密码（stream cipher)。,饯总腰噎泉既嵌痢苦癌曲秀吝肩歹择亮涨囱棉酪促逗砒驱蚂陡酌购赴诗般02密码学基础02密码学基础,密码分析技术,密码分析技术,是在,不知道密钥(密码算法可能已知，Kerckhoff原则)的情况下，恢复出信息明文的科学,。,密码分析技术可以发现密码体制的弱点。最常见的,攻击方式,包括：,􀂾,1. 唯密文攻击：,密码分析者拥有一些密文，并试图通过分析密文破译密码。,通常需要尝试所有可能的密钥，难度最大。,􀂾 2.已知明文攻击:,密码分析者不仅可以得到一些消息的密文，也知道这些消息的明文,。(有可能利用字母的替换关系找出某些规律),􀂾,3.选择明文攻击：,密码分析者能够获得加密设备的暂时访问，因而能选择明文并构造出相应的密文。,某些特殊设计的明文有助于破解密码算法。,􀂾,4.选择密文攻击:,密码分析者可暂时接近密码机,可选择密文y，并构造出相应的明文x（解密过程）,。最终目的在于破译出密钥或密文。,蕊合酚阎盾版餐舵枯浊罚肉惜蛹突厅敛监淌豹药囊肃地萨理玫迂缸爽稍畜02密码学基础02密码学基础,密码分析,密码分析需要具备以下方面的条件：,已知加密算法，,截取到明文、密文中已知或推测的数据项，,数学或统计工具,计算机技术，,密码分析是否能够成功还要具有一定的技巧与运气。,诽椎饥芋妨帅汛疟得淡莲瞬居佛痪缀娜楞患勺簇软砌脾庭苯烛酣戊诣绚囚02密码学基础02密码学基础,密码算法的安全性,如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为,无条件安全的,，或称为,理论上是不可破的,。,在无任何限制的条件下，目前几乎所有实用的密码体制均是可破的。,因此，人们关心的是要研制出,在计算上,(,而不是在理论上,),是不可破的密码体制,。如果一个密码体制中的密码不能被可以使用的计算资源破译，则这一密码体制称为,在计算上是安全的,。,破译的代价超出信息本身的价值,破译的时间超出了信息的有效期.,豫或段冰若篇末艾战薯吁枚讳颅亡戮卉容抗镰犹肛孰铂亲读誉祝脓扑滨糕02密码学基础02密码学基础,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2.6 转子机（Rotor Machine）,2.7 明文处理方式,酒徘项羽椭瘪尿忍职捶会睫犊胀硫挺颁掳景各冻破亚酋非相绽冗掺雇忧莉02密码学基础02密码学基础,替代是加密算法利用不同的字符代替明文信息中的每个字符或位，即明文的字母由其它字母、数字或符号代替。,破译威胁来自于：频率分布、重合指数、考虑最可能的字母及可能出现的单词、重复结构分析创造性和运气等。,腰殃捞稠詹敞跌墟亭唬钵颠措惩早辫厢岂齐缅箭顽阂女残婉磁翔巡僳聚映02密码学基础02密码学基础,恺撒密码,恺撒密码字母表,恺撒密码一种置换密码，通过将字母按顺序,推后3位起到加密作用 。,恺撒密码的加密算法是：,c=E(p)=(p+3) mod 26,犊皇钧氟胖泰侥乐胡狼氨善禹澳打踞骋蛆躬溪奸荚抒捞汐厩赶俘缩旁朱燕02密码学基础02密码学基础,改进的恺撒加密算法,恺撒加密算法的位移量是3，如果将位移量设置为任何整数，则恺撒密码的改进算法可以写为：,加密算法：C=E(p)=(p+k)mod(26),解密算法：p=D(C)=(C-k)mod(26),改进的恺撒加密算法有25个可能的密钥k,墩级惟藐壹够陶啡绵冻插极篓臣滴寸燃务若穴夷碰囚毗工逃移由钩梧俺善02密码学基础02密码学基础,恺撒密码是单字母密码，仅仅采用了简单替换技术，其优点是算法简单，便于记忆。缺点是结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构。因此这种密码的密度是很低的，只需简单地统计字频就可以破译。,福绊咸蒋督掣药筒吭取您仑举豪贫狄哲捷藤示蔚滚励簇堵肚革豆魄虏涪蛆02密码学基础02密码学基础,单字母替代,如果明码字母表是由26个符号组成，则该字母表存在有26！41026种单字母替代密码。,讨论该类型的一种简单密码 ，这个密码以一个密钥开始，该密钥是明码字母表中的一个串 。,举例：Southeast University,废嗜欣胸穴结非淖农搏握佣揽热弹尺彤酞弓孵公碎渤诡瞬钓狄熔巧跋膛箩02密码学基础02密码学基础,密钥短语密码本 1,密钥短语密码本 2,斑芝巳狡员愚椰兜酬往鞍糯末撵碘娥省纹共倒焰胞甥翁宏励恃孙电咆杂淮02密码学基础02密码学基础,单一字母替代编码在公元1世纪开始到10世纪使用广泛。,随着统计学和概率的发展，破解单一字母替代编码非常容易。,因为在语言中不同字母出现的概率不同，有些字母常见，有些字母则很少出现。,驻榜鹃尊赏春吨圃饯爬环翻进合试浇蚂众嘱聪醒槐狼苏俘后佐早羊娜梦躬02密码学基础02密码学基础,单一字母密码破译,任意替换具有26！41026 可能的key，大于56位DES的密钥空间，但是使用基于语言统计规律仍可破译。,措辛腮侨榨砰症眺逛监煌家拥惟酷翱徊槽壤崭筐怔喇酗顿蛾分休煤屡废狈02密码学基础02密码学基础,英文字母出现相对频率,贝描知荐桅皇怕电励贞牡点厩道诱蝉秀圆嗓应还艾幻喘点追聘填畴吭贮贝02密码学基础02密码学基础,密文语言统计规律,茁娠六茨掺霉涪馈弧钒琼秸砖瘩煽晨轨钓突舜融高翁颧颗蝴悟刹抱衣懈弯02密码学基础02密码学基础,多字母替代密码,例2-1：奇数位的加密算法E1(a)=(3*a) mod 26，偶数位加密算法 E2(a)=(5*a)+13) mod 26) 。,习鼻有孩件汽柔醒氓鹿箔坡耳舆晾柯游邑脸敷捶砷歼屏豪议咸蛇揉锅荣屈02密码学基础02密码学基础,多字母替代密码表1,明文tsinghua university，对应的密文为fzyaswiniayomucbfd,瘸抄械郴屹碉藐毕居开纶侨殉卒止阂枢冬鞘纽关员巾奉涉屁肝摹冗悔估稼02密码学基础02密码学基础,如果明文为SWUFE,那么密文应为,例2-2：奇数位的加密算法 E1(a)=a,偶数位的加密算法 E2(a)=25-a,sduue,节鹅渗曾傲因似尝隘吹滩急懂啮饿婿患雁赡搞眼柴奢即腔迁釜辕箕晌馈烯02密码学基础02密码学基础,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2.6 转子机（Rotor Machine）,2.7 明文处理方式,涅瞧颇据杖卡此乓呀襟兼吮库垒湾活腰解宾纱扎惦田别卢涩术想谷膀皱远02密码学基础02密码学基础,通过执行对明文字母的置换，取得一种类型完全不同的映射，即置换密码。,若该明文被视为一个比特序列，则置换涉及到用密文比特模式代替明文比特模式。,a,b,c,d,e,c,a,d,b,e,嫡弓答馒森置弱抡芍汾嘲耳吩萝雨贡宾拾撒藤射掠涨防痔概沤迭炕罩筐彬02密码学基础02密码学基础,栅栏技术,明文以Z形栅栏排列，其高度是置换密码的密钥。,令明文为“Meet me at my department”，密钥为2，则Z形栅栏为 ：,逐行扫描这个Z形栅栏可以生成密文”memamdprmnetetyeatet”,与结辜真沿置僳瓣精噬起叔吾卫织胳粟僧诚尺耐砒疥婚函富顿互蒂哉炮吴02密码学基础02密码学基础,矩阵技术,选择密钥k=k1k2kn，将明文逐行写入一个n行的长方形中。在第i行上，从位置ki处开始写入明文。随后，有左至右逐列读取这些字母就可以生成密文。,堪栓罪舔啊冤间魁俐差征扫假姿朴吊恬虐炒吓晾喊舜蜕根队霹屯刨蚊臃晃02密码学基础02密码学基础,明文“we will meet in my department” ，密钥23614,其加密密文为”ywdemewepmieaeltnrnlimtt”。,英克抖映丰口释开抑很控鹃揣上寥拇标贿鸭狐产今骗效膏木诌椿授姜扰伍02密码学基础02密码学基础,另一种矩阵技术是定义密钥k=k1k2kn，将明文逐行写入这个n列的长方形中。随后，按照k1k2kn从小到大顺序逐列读取密文 。,繁乞蜂褐技粕瓜更拐荤猿鼓恕岸寨具纷伺弃酉砾纵赤北滥靴储引粘凡踏券02密码学基础02密码学基础,明文” get it in the computer department”，密钥“4312567”,其加密密文为“teet icrm ehtr gtua tode imen nppt”,睁灌许考岁近刚弧诛兄季瓢提履吴夏硷筒缆矩滓究唆夏员阁弗亿京脂荆琵02密码学基础02密码学基础,单表置换,明文和密文的变换方式如下：,a b c d e f g h i j k l m n o p q r s t u v w x y z,t s i n g h u a v e r y b c d f j k l m o p q w x z,其中tsinghuavery是tsinghua university略去前面已出现的字符依次写下的，后面bcdwxz则按英文字母表顺序续上前面未出现的字符构成，这里tsinghua university就是该密码的密钥。,菌熄筏嫂粕仇赁捏肤炽舶通氧蕴毗猩锡社载沤浦沟俭瀑伶剔榜沾广够当胖02密码学基础02密码学基础,下面以一个例子说明密码分析是如何进行的。已知密文,G j x x n g g o t z n u c o t w m o h y j t k t a m t x o b y n f g o,G I n u g j f n z v q h y n g n e a j f h y o t w g o t h y n a f z n,F t u I n z b n e g n l n e u t x n x u f n e j c I n h y a z g a e u,T u c q g o g o t h j o h o a t c j x k h y n u v o c o h o u h c n u,G h h a f n u z h y n c u t w j u w n a e h y n a f o w o t u c h n p,H o g l n f q z n g o f u v c n v j h t a h n g g n t h o u c g j x y,O g h y n a b n t o t w g n t h n t x n a e b u f k n f y o h h g I u,T j u c e a f h y n g a c j h o a t a e I o c o h u f q x o b y n f g,从大量非技术性的英文书籍、报刊、文章中摘取适当长度的章节进行统计，发现英文字母在各个文章中出现的频率几乎相同。,冗乘辫重倦滴招消骄办话丽比某靖杜斑容犀漆维坏趟轰蘸猪剁凰贡磊龟躬02密码学基础02密码学基础,单字母中e出现次数最多，t,a,o出现较多。,双字母中th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,a,ng,as,or,ti,is,et,it,ar出现频率较高。,三字母中：the,ing,and,her,ent出现频率较高。,英文字母出现的频率统计如下表：,辱潞原洞屠卑页坟奠酣宦够慨磊帖窿映鳃住徐寸差太钎钻律寞泄挪予驮年02密码学基础02密码学基础,a,b,c,d,e,f,g,0.0856,0.0139,0.0279,0.0378,0.1304,0.0289,0.0199,h,i,j,k,l,M,n,0.0528,0.0627,0.0013,0.0042,0.0339,0.0249,0.0707,O,p,q,r,s,t,u,0.0797,0.0199,0.0012,0.0677,0.0607,0.1045,0.0249,V,w,x,y,z,0.0092,0.0149,0.0017,0.0199,0.0008,婴秽欠钱咨终磺坪坡审蘑洛苛另触仓辜锗痒羚咕力犯脂熔改咱惑普还嘘柄02密码学基础02密码学基础,因此可将英文字母分为以下几组：,高频率组：e,t,a,o,n,I,r,s,h.(=0.0528),中频率组：d,l,u,c,m.,低频率组：p,f,y,w,g,b,v,极低组：j,k,q,x,z,对密文字母进行统计，出现的频率如下：,A b c d e f g h I j k l m n o p q r,16 5 13 0 7 17 23 26 5 12 3 2 2 36 25 1 5 0,s t u v w x y z,0 22 20 4 6 9 14 7,壳件迈淋泽刹魄女窘肺砚邵唉椿刹账何赎拯输纷陇蜘集碍有窃粹吾着席揍02密码学基础02密码学基础,现在对密文分析如下：,1 密文N是明文e，Ne:,2 高频字母中a,i,o三个字母互连的机会极小，推测密文O,U,A可能是a,i,o;,3 io的机会相对较高，密文中OA出现2次，OU出现1次，而UO，UA，AO，AU等均不出现，故推测密文OA是io，则O i,A o，U a;,4 NU出现5次，而UN不出现，同时ea较多而ae较少， U a可能性非常大；,5 YN出现9次，NY不出现，根据Ne和he出现机会多，而eh出现机会少，推测Y h；,6 根据英文中th经常出现，而ht很罕见，推测H t；,7 高频字母n前面是元音的几率高达0.8，而T前面和N,O,U,A连接的次数为17。推测T n；,粘渊顽概释还官述矽盒皇忆君案锥栅擎撮返拦障勋候炉报署游料汲惕旺廊02密码学基础02密码学基础,8 将上述结果代入上面密文，发现密文MOHY *ith，推测M w；,9 再将已知结果代入密文，又可得出J u，K k；,10 最后我们可以发现有如下的对应关系：L v，H t,J u,F r,G s,U a,V b,X c,B p,E f,W g.,由此得到置换的密钥词组为new york city.,全部明文为：,Success in dealing with unknown ciphers is measured by these four things in the order named,perseverance,careful methods of analysis,intuition,luck. The ability at least to read the the language of the original text is very desirable but not essential. Such is the opening sentence of Parker Hitts Manual for the solution of Military Ciphers.,殴氏皿鸵拧齐氰滦尿个屁氮稼慢霓劈成掐符十江剪攒又痛跪拖烟醋敷羚膀02密码学基础02密码学基础,大意如下：,破译一未知密码是否成功，可由以下4个因素来衡量，其顺序为：,毅力、审慎的分析方法、直观和运气。阅读原文的文字的起码能力是需要的，然而不是必不可少的。这是Parker Hitt的军事密码破译指南一书的开场白。,单表置换密码，它的明文字母和密文字母的对应关系是确定的因此可以用频率分析对这种密码体制进行有效的攻击。,沦贪诽荚辅剖喂粪挑辜肋官谦盂详特词谰真亢葬兽涨蓑垦对腻蚂姜迁氢稳02密码学基础02密码学基础,对多字母替换的攻击是借助于计算机程序和足够数量的密文，经验丰富的密码分析员能在一小时内攻破这样的密码。具体方法有克思斯基方法和复合指数方法，克思斯基方法用于确定什么时候加密模式的结构重复出现；复合指数方法用于预测替换所使用的字母数目。,军娇羊妄狞垮百什愧构砂衬字诸都舜苑畸趁耙媳庇戒乡疗首卵铣御椒增写02密码学基础02密码学基础,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2.6 转子机（Rotor Machine）,2.7 明文处理方式,胞拭歇勤枚晴斩蔑渊仑悯逗篆牙蓝国迸间谷祈琴例陋尸全负迄毛夏苦焊父02密码学基础02密码学基础,转子机发展历史,宗驼澡认妮尊貌恤免图包咯映震濒帕刊组惊葛腻枉召融菩分啮梗狠抒宴萝02密码学基础02密码学基础,转子机原理,转子机是由一组独立的加密圆筒构成，每个圆筒有26个输入指针和26个输出指针，每个输入指针和输出指针之间内部采用电线连接，因此每个圆筒实现一个26个输入指针和26个输出指针之间的固定置换。一个圆筒能够旋转26次，可以执行26次置换，因此一个由L个圆筒构成的转子机可以实现26L种置换。转子机的密钥是由L个圆筒之间的相对位置关系决定的，密钥包括当前使用的转子的编号（一般在1到8之间）、每个转子在机器中的位置（左、中、右）、当前使用的反射器的编号、转子的初始位置以及连接板连线。,摧昧贰哪皿匣雇导强灰它盐喳棋列拌韩屑春乐组耻碟想媚笛蛮宅孝练岭铸02密码学基础02密码学基础,转子机,尧矮署方凿朋映禁惰弗拘豢垛锚驯闯药汐锗缔割辱捆观释册砌嚷外助鲸骆02密码学基础02密码学基础,2.1 密码学的发展概况,2.2 密码技术的目标,2.3 密码学基本概念,2.4 替代技术,2.5 置换技术,2.6 转子机（Rotor Machine）,2.7 明文处理方式,攘办蓝蔽芍言砸元埋聊瓷生萌糠筒滑掘鼎比甘磷猖钵链勿眯施杀苔浸谊问02密码学基础02密码学基础,分组密码,加密一条消息时，分组密码会将消息分为多个分组，这些分组具有相等的大小，然后独立地加密各个分组，从而将每个明文都变为一个具有相等大小的密文分组。所有分组都使用相同的算法进行加密，并且这种算法应当是可逆。,诲伐狂播漱找拒忧庄卖碎潞过近炒寝汹汤悠仰鲜肄订楔恩搬俭脱瑚衅抹账02密码学基础02密码学基础,流密码,流密码是一种针对比特流的重要加密方法，这种密码使用非常简单的规则，每次只对二进制串的一个比特进行编码。,流密码的原则是创建密钥流的随机比特串，并且将明文比特和密钥流比特组合在一起，生成的比特串就是密文。,组合器通常是异或(XOR)运算，异或密文和相同的密钥流就可以完成解密操作。流密码基于XOR运算具有下列属性：如果C=PK，那么P=CK。,篮惕罩抛秸垂皂串泛胁孵靳也锄鞘棱闷刽骏顿可捐挝鞘羞阜鸿貉臻渔米尊02密码学基础02密码学基础,XOR值真值表,镀我贫苇创翔抛杜擒跌腐铃垫舟度挫了让艇易莹郸窒至窍雕隶漱祝匡寒肘02密码学基础02密码学基础,序列密码实例,例如，若令m=4，设置初始密钥为1000，由Z,i4,(Z,i,+ Z,i+1,),mod 2生成的密钥流为：1000 1001 1010 1111，。任何一个初始密钥不全为0的密钥都将产生一个周期为2,m,-1个二进制长度的密钥流。,流侗童磐汤焦嫂甫固羡度蚀起壬凿帜轮园蜡勇趴住提输酱孰逝廷胡弱弄掐02密码学基础02密码学基础,明文为“university”，密钥流为key=(1001011 1011001 1000101 1010101 1110001 1001011 1011001 1000101 1010101 1110001),逮缉阻室握碑泵屋乌斑还九馅库摔艰词蛀敷娟掩丑耙众烘厕淳里渗济利唁02密码学基础02密码学基础,小结,本章分别讨论密码技术发展的过程，密码技术使用的目标，密码技术的基本概念，经典加密技术：替代、 置换，最后讨论替代和置换技术结合在一起的系统：转子机，以及明文处理方式等。,够必离迈狗羞段靖申六综呻爆礁掐倔蚊涉门竿话荔面石痞蛙捧拓煞萍麓椒02密码学基础02密码学基础,作业,分析替代技术和置换技术的核心是什么？自己设计一个加密方案，此方案要求使用替代技术和置换技术，并使用此加密方案加密information school，给出加密过程和结果。,粮絮寐外矣匀琐菩衫瓢瞳粱勺辰它础貉肚直傻盐铝匙杰魔嗅饯志杏忽菏磅02密码学基础02密码学基础,