复旦大学信息安全课件第2章密码学概论
第第2章 密码学概论章 密码学概论 随着计算机病毒所带来危害的日益加剧,计算机犯罪事件不断的增加,黑客攻击的日益频繁随着计算机病毒所带来危害的日益加剧,计算机犯罪事件不断的增加,黑客攻击的日益频繁,信息安全已成为人们不得不面对的问题。信息安全已成为人们不得不面对的问题。 互联网的广泛使用,全世界都在自投入网,如果不加强网络安全,则将被一网打尽。互联网的广泛使用,全世界都在自投入网,如果不加强网络安全,则将被一网打尽。 无论是信息安全本身,还是系统本身的安全,都需要密码技术。无论是信息安全本身,还是系统本身的安全,都需要密码技术。 作为信息安全的核心技术作为信息安全的核心技术密码技术成为人们研究和关注的重点。密码技术成为人们研究和关注的重点。 有关信息加密技术的研究,特别要注意重视自主开发。有关信息加密技术的研究,特别要注意重视自主开发。 对于对于DES算法加密产品,美国中央情报局对密钥位在算法加密产品,美国中央情报局对密钥位在20多年前曾作过预测和比较:多年前曾作过预测和比较: 40bit 位位 56bit 位位 400 美元美元 5 小时小时 38 年年 300 万美元万美元 24 秒秒 10 天天 1 千万美元千万美元 7 秒秒 13 小时小时 1 亿美元亿美元 0.2 秒秒 12 秒秒 美国政府作出限制密钥为美国政府作出限制密钥为56bit位的产品出口,而位的产品出口,而2000年开始放宽出口限制,但其背景是什么呢?对密钥为年开始放宽出口限制,但其背景是什么呢?对密钥为56bit位位DES只要化只要化25万美元,在不到万美元,在不到3天就可破译。天就可破译。 密码技术涉及哪些内容?密码技术涉及哪些内容? 下面通过简单例子来引入。下面通过简单例子来引入。 Alice和和Bob想在晚上一起出去,但定不下来是去电影院还是歌剧院,他们达成协议,通过掷硬币来决定想在晚上一起出去,但定不下来是去电影院还是歌剧院,他们达成协议,通过掷硬币来决定 如果他们是通过电话来执行上述协议,显然无法公平实现,因为一方无法验证对方掷硬币的结果。如果他们是通过电话来执行上述协议,显然无法公平实现,因为一方无法验证对方掷硬币的结果。 如果在协议中加入密码技术,可形成适合在电话上工作的形式。如果在协议中加入密码技术,可形成适合在电话上工作的形式。 把密码技术看成函数把密码技术看成函数f(x):Z到到Z,且具有性质:且具有性质: (1)对任意函数,由对任意函数,由x计算计算f(x)是容易的是容易的,而给出而给出f(x),要找出对应的,要找出对应的x是难的;是难的; (2)找出一对整数找出一对整数(x, y),满足满足xy而而f(x)=f(y)是难的。是难的。 密码技术将研究探讨容易,难的的数学描述,建立量化表示。密码技术将研究探讨容易,难的的数学描述,建立量化表示。 电话掷币电话掷币 1.Alice 选择一个大随机数选择一个大随机数x,并计算,并计算f(x);然后通过电话告诉然后通过电话告诉Bob f(x)的值;的值; 2.Bob告诉告诉Alice自己对自己对x的奇偶猜测;的奇偶猜测; 3.Alice告诉告诉Bob x的值;的值; 4.Bob验证验证f(x)并查看所做猜测是否正确。并查看所做猜测是否正确。 在开放的计算机和通信网络中保证安全通信,采用密码技术是有效且是唯一可行的方法。在开放的计算机和通信网络中保证安全通信,采用密码技术是有效且是唯一可行的方法。 电子商务,事务处理,等信息系统对安全的需求,导致了很多密码系统和协议的产生。电子商务,事务处理,等信息系统对安全的需求,导致了很多密码系统和协议的产生。2.1 信息加密的基本概念信息加密的基本概念 密码学分为密码编码学和密码分析学两个分支。密码学分为密码编码学和密码分析学两个分支。 密码编码学是对信息进行编码实现隐蔽信息的一门学问密码编码学是对信息进行编码实现隐蔽信息的一门学问 密码分析学则是研究分析破译密码的学问密码分析学则是研究分析破译密码的学问 两者互相对立,又互相促进向前发展。两者互相对立,又互相促进向前发展。 密码学密码学(Cryptology)一字源自希腊文一字源自希腊文“krypts”及及“logos”两字,直译即为两字,直译即为“隐藏隐藏”及及“讯息讯息”之意。之意。 密码学的起源追溯到人类刚刚出现密码学的起源追溯到人类刚刚出现,并且尝试去学习如何通信的时候。并且尝试去学习如何通信的时候。 寻找方法确保他们的通信的机密。寻找方法确保他们的通信的机密。 由于战争指挥与传递情报的需要,据文字记载,早在战国时期(公元前由于战争指挥与传递情报的需要,据文字记载,早在战国时期(公元前403前前221年)我国就开始使用秘密通信方法。年)我国就开始使用秘密通信方法。 如战国中、后期成书的军事著作六韬中的阴符和阴书就记载了当时秘密通信的具体形式与方法。如战国中、后期成书的军事著作六韬中的阴符和阴书就记载了当时秘密通信的具体形式与方法。 “阴符”就是一种符节,双方事先约定好,多长的符节各代表什么意思。“阴符”就是一种符节,双方事先约定好,多长的符节各代表什么意思。 “阴书”就是一封竖写的完整的秘密信件或情报,拦腰截成“阴书”就是一封竖写的完整的秘密信件或情报,拦腰截成3段,派段,派3个人各持一段,于不同的时间、路线分别出发送给收信人。收信者收齐个人各持一段,于不同的时间、路线分别出发送给收信人。收信者收齐3段信,即可知晓全部内容。万一途中某一个送信者被截获,对方也难以解读全信内容。段信,即可知晓全部内容。万一途中某一个送信者被截获,对方也难以解读全信内容。 秦汉以后,在秘密通信中出现了各种暗语、暗号、密诗、符号等形式秦汉以后,在秘密通信中出现了各种暗语、暗号、密诗、符号等形式,不易为外人破解,还有的将密信用蜡密封或火漆、封泥密封,以防泄密,一旦泄露,即可立即发觉,采取补救措施,或将计就计,改变对策。不易为外人破解,还有的将密信用蜡密封或火漆、封泥密封,以防泄密,一旦泄露,即可立即发觉,采取补救措施,或将计就计,改变对策。 宋代军用密码宋代军用密码 北宋时期,北宋仁宗庆历四年北宋时期,北宋仁宗庆历四年(1044年年),由枢密使曾公亮、枢密副使丁度奉诏主编的武经总要,由枢密使曾公亮、枢密副使丁度奉诏主编的武经总要(40卷卷)是对宋代国防建设和军事教育都有指导性的综合性军事教程,也是研究北宋以前学术发展和北宋军事理论及实践的重要历史资料。是对宋代国防建设和军事教育都有指导性的综合性军事教程,也是研究北宋以前学术发展和北宋军事理论及实践的重要历史资料。 武经总要记载,宋代出现的传递情报的密码叫作“字验”。武经总要记载,宋代出现的传递情报的密码叫作“字验”。 “字验”,就是将各种情报,如请粮料、请添兵、请固守、被贼围、将士叛、将领病、贼退军、贼进军等“字验”,就是将各种情报,如请粮料、请添兵、请固守、被贼围、将士叛、将领病、贼退军、贼进军等40项,用项,用40个字的一首诗来表示,把不含重复的个字的一首诗来表示,把不含重复的40字诗与这些情报内容依次相对并具体搭配,编上相应的数字代号,从字诗与这些情报内容依次相对并具体搭配,编上相应的数字代号,从1至至40。密码本只能由军中主将掌握,每次使用时,可根据所需传递情报内容,在新抄写的这首诗应加符号的字下面,加上规定的符号即可。对方收到这首诗后,查对密码本就能译出情报内容。这种密码本即使落入敌手,也不会被敌人破译,即使送信人投降叛变,也无法帮助敌人破译出所传递的情报。密码本只能由军中主将掌握,每次使用时,可根据所需传递情报内容,在新抄写的这首诗应加符号的字下面,加上规定的符号即可。对方收到这首诗后,查对密码本就能译出情报内容。这种密码本即使落入敌手,也不会被敌人破译,即使送信人投降叛变,也无法帮助敌人破译出所传递的情报。 例如通信双方选定一首五言诗,共例如通信双方选定一首五言诗,共40个字,作为解码密钥。诗文如下:个字,作为解码密钥。诗文如下: 望洞庭湖赠张丞相望洞庭湖赠张丞相 八月湖水平,涵虚混太清。八月湖水平,涵虚混太清。 气蒸云梦泽,波撼岳阳城。气蒸云梦泽,波撼岳阳城。 欲济无舟揖,端居耻圣明。欲济无舟揖,端居耻圣明。 坐观垂钓者,徒有羡鱼情。坐观垂钓者,徒有羡鱼情。 统兵将领根据战场形势可随时与主帅联络。统兵将领根据战场形势可随时与主帅联络。 敌军占据优势,无法实施进攻,统兵将领请求固守阵地时,先查出“请固守”是密本中的第敌军占据优势,无法实施进攻,统兵将领请求固守阵地时,先查出“请固守”是密本中的第19个术语,而诗中的第个术语,而诗中的第19个字是“阳”。就在信上写上“阳”字,并在该字上盖上印章。主帅接到信后,马上可以破译出统兵将领来函的意图。如果他同意下属的意见,就重新写下这个字并加盖自己的官印;如不同意,印章就不盖在那个字上。个字是“阳”。就在信上写上“阳”字,并在该字上盖上印章。主帅接到信后,马上可以破译出统兵将领来函的意图。如果他同意下属的意见,就重新写下这个字并加盖自己的官印;如不同意,印章就不盖在那个字上。 这样统兵将领与主帅可随时保持联络。这样统兵将领与主帅可随时保持联络。 这种通信方式具有极强的保密性。这种通信方式具有极强的保密性。 密写技术密写技术 在在13世纪初,“密写”也是广泛应用传递情报的手段之一。世纪初,“密写”也是广泛应用传递情报的手段之一。 1216年,蒙古军队围攻太原府,金宣抚使兼左副元帅乌古论礼,派遣间谍携带用明矾水密写的书信,抄近沿偏僻小道星夜兼程赶往金国京城汴京告急,诏发援兵,不久解围,乌古论礼遂官升两级。年,蒙古军队围攻太原府,金宣抚使兼左副元帅乌古论礼,派遣间谍携带用明矾水密写的书信,抄近沿偏僻小道星夜兼程赶往金国京城汴京告急,诏发援兵,不久解围,乌古论礼遂官升两级。 直至近代中国,这种“密写”方法也还是传递情报的常用方法之一。直至近代中国,这种“密写”方法也还是传递情报的常用方法之一。 罗马的军队用凯撒密码进行通信。罗马的军队用凯撒密码进行通信。 当年凯撒大帝行军打仗时用这种方法进行通信,因此得名。当年凯撒大帝行军打仗时用这种方法进行通信,因此得名。 “This is Caesar Code”。用凯撒密码加密后字符串变为“。用凯撒密码加密后字符串变为“vjku ku Ecguct Eqfg”。 看起来似乎加密得很“安全”。把这段很难懂的东西每一个字母换为字母表中前移看起来似乎加密得很“安全”。把这段很难懂的东西每一个字母换为字母表中前移2位的字母,结果出 来 了 。 凯 撒 密 码 的 字 母 对 应 关 系 :位的字母,结果出 来 了 。 凯 撒 密 码 的 字 母 对 应 关 系 :AbcdefghixyzCdefghIjkzabek(x)=x+k(mod26) k=3 dk(y)=y-k(mod26) 单字母的替换。单字母的替换。 密码学的发展可以分为两个阶段。第一个阶段是计算机出现之前的,这是传统密码学阶段,基本上靠人工对消息加密、传输和防破译。第二阶段是计算机密码学阶段。密码学的发展可以分为两个阶段。第一个阶段是计算机出现之前的,这是传统密码学阶段,基本上靠人工对消息加密、传输和防破译。第二阶段是计算机密码学阶段。 传统方法的密码学阶段,解密是加密的简单逆过程,两者所用的密钥是可以简单地互相推导的,因此无论加密密钥还是解密密钥都必须严格保密。这种方案用于集中式系统是行之有效的。传统方法的密码学阶段,解密是加密的简单逆过程,两者所用的密钥是可以简单地互相推导的,因此无论加密密钥还是解密密钥都必须严格保密。这种方案用于集中式系统是行之有效的。 现代计算机密码学阶段包括两个方向:一个方向是公开密钥密码(现代计算机密码学阶段包括两个方向:一个方向是公开密钥密码(RSA),另一个方向是传统方法的计算机密码体制,秘密密钥密码,如数据加密标准(),另一个方向是传统方法的计算机密码体制,秘密密钥密码,如数据加密标准(DES)。)。 对信息进行编码可以隐蔽和保护需要加密的信息,使未授权者不能提取信息。对信息