复旦信息安全课件第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),满足x≠y而f(x)=f(y)是难的。•密码技术将研究探讨容易，难的的数学描述，建立量化表示。•电话掷币•1.Alice选择一个大随机数x，并计算f(x);然后通过电话告诉Bobf(x)的值；•2.Bob告诉Alice自己对x的奇偶猜测；•3.Alice告诉Bobx的值；•4.Bob验证f(x)并查看所做猜测是否正确。•在开放的计算机和通信网络中保证安全通信，采用密码技术是有效且是唯一可行的方法。•电子商务，事务处理，等信息系统对安全的需求，导致了很多密码系统和协议的产生。2.1信息加密的基本概念•密码学分为密码编码学和密码分析学两个分支。•密码编码学是对信息进行编码实现隐蔽信息的一门学问•密码分析学则是研究分析破译密码的学问•两者互相对立，又互相促进向前发展。•密码学(Cryptology)一字源自希腊文“kryptós”及“logos”两字，直译即为“隐藏”及“讯息”之意。•密码学的起源追溯到人类刚刚出现，并且尝试去学习如何通信的时候。•寻找方法确保他们的通信的机密。•由于战争指挥与传递情报的需要，据文字记载，早在战国时期（公元前403～前221年）我国就开始使用秘密通信方法。•如战国中、后期成书的军事著作《六韬》中的《阴符》和《阴书》就记载了当时秘密通信的具体形式与方法。•“阴符”就是一种符节，双方事先约定好，多长的符节各代表什么意思。•“阴书”就是一封竖写的完整的秘密信件或情报，拦腰截成3段，派3个人各持一段，于不同的时间、路线分别出发送给收信人。收信者收齐3段信，即可知晓全部内容。万一途中某一个送信者被截获，对方也难以解读全信内容。•秦汉以后，在秘密通信中出现了各种暗语、暗号、密诗、符号等形式，不易为外人破解，还有的将密信用蜡密封或火漆、封泥密封，以防泄密，一旦泄露，即可立即发觉，采取补救措施，或将计就计，改变对策。•宋代军用密码•北宋时期，北宋仁宗庆历四年(1044年)，由枢密使曾公亮、枢密副使丁度奉诏主编的《武经总要》(40卷)是对宋代国防建设和军事教育都有指导性的综合性军事教程，也是研究北宋以前学术发展和北宋军事理论及实践的重要历史资料。•《武经总要》记载，宋代出现的传递情报的密码叫作“字验”。•“字验”，就是将各种情报，如请粮料、请添兵、请固守、被贼围、将士叛、将领病、贼退军、贼进军等40项，用40个字的一首诗来表示，把不含重复的40字诗与这些情报内容依次相对并具体搭配，编上相应的数字代号，从1至40。密码本只能由军中主将掌握，每次使用时，可根据所需传递情报内容，在新抄写的这首诗应加符号的字下面，加上规定的符号即可。对方收到这首诗后，查对密码本就能译出情报内容。这种密码本即使落入敌手，也不会被敌人破译，即使送信人投降叛变，也无法帮助敌人破译出所传递的情报。•例如通信双方选定一首五言诗，共40个字，作为解码密钥。诗文如下：•望洞庭湖赠张丞相•八月湖水平，涵虚混太清。•气蒸云梦泽，波撼岳阳城。•欲济无舟揖，端居耻圣明。•坐观垂钓者，徒有羡鱼情。•统兵将领根据战场形势可随时与主帅联络。•敌军占据优势，无法实施进攻，统兵将领请求固守阵地时，先查出“请固守”是密本中的第19个术语，而诗中的第19个字是“阳”。就在信上写上“阳”字，并在该字上盖上印章。主帅接到信后，马上可以破译出统兵将领来函的意图。如果他同意下属的意见，就重新写下这个字并加盖自己的官印；如不同意，印章就不盖在那个字上。•这样统兵将领与主帅可随时保持联络。•这种通信方式具有极强的保密性。•密写技术•在13世纪初，“密写”也是广泛应用传递情报的手段之一。•1216年，蒙古军队围攻太原府，金宣抚使兼左副元帅乌古论礼，派遣间谍携带用明矾水密写的书信，抄近沿偏僻小道星夜兼程赶往金国京城汴京告急，诏发援兵，不久解围，乌古论礼遂官升两级。•直至近代中国，这种“密写”方法也还是传递情报的常用方法之一。•罗马的军队用凯撒密码进行通信。•当年凯撒大帝行军打仗时用这种方法进行通信，因此得名。•“ThisisCaesarCode”。用凯撒密码加密后字符串变为“vjkukuEcguctEqfg”。•看起来似乎加密得很“安全”。把这段很难懂的东西每一个字母换为字母表中前移2位的字母，结果出来了。凯撒密码的字母对应关系：Abcdefghi…xyzCdefghIjk…zabek(x)=x+k(mod26)k=3•dk(y)=y-k(mod26)•单字母的替换。•密码学的发展可以分为两个阶段。第一个阶段是计算机出现之前的，这是传统密码学阶段，基本上靠人工对消息加密、传输和防破译。第二阶段是计算机密码学阶段。•传统方法的密码学阶段，解密是加密的简单逆过程，两者所用的密钥是可以简单地互相推导的，因此无论加密密钥还是解密密钥都必须严格保密。这种方案用于集中式系统是行之有效的。•现代计算机密码学阶段包括两个方向：一个方向是公开密钥密码（RSA），另一个方向是传统方法的计算机密码体制，秘密密钥密码，如数据加密标准（DES）。•对信息进行编码可以隐蔽和保护需要加密的信息，使未授权者不能提取信息。•被隐蔽的信息称为明文，•编码后明文变换成另一种隐蔽形式，称为密文。•这种变换过程称为加密•其逆过程，即由密文恢复成原明文的过程称为解密。•对明文进行加密时所采用的一组规则称为加密算法•对密文进行解密时所采用的一组规则称为解密算法。•加密和解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。•密钥是密码体制安全保密的关键，它的产生和管理是一个重要研究课题。•在一个密码体制中，如果加密密钥和解密密钥相同，或从一个易得到另一个，就称其为单钥密码体制或对称密码体制。•如果在密码体制中，加密密钥和解密密钥不同，且从一个难于推出另一个，则称为双钥密码体制或非对称密码体制，•1976年由Diffe和Hellman等人所开创的新体制•采用双钥体制的每个用户都有一对选定的密钥：一个是可以公开的，另一个则是秘密的。•公开的密钥可以进行注册公布，因此双钥密码体制又称为公钥密码体制。•其主要特点是将加密和解密能力分开，从而实现多个用户加密的信息只能由一个用户解读，或只能由一个用户加密信息而使多个用户解读。•在信息传输和处理系统中，除了确定的接受者外，还有非授权者•他们通过各种办法（如搭线窃听、电磁窃听、声音窃听等）来窃取机密信息。•他们虽然不知道系统所用的密钥，但通过分析可能从截获的密文推出原来的明文，这一过程称为密码分析。•研究如何从密文推出明文、密钥或解密算法的学问称为密码分析学。•为了保护信息的保密性，抗击密码分析，信息加密系统应满足如下要求：•(1)系统至少为实际上不可破，即，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的•(2)系统的保密性只依赖于密钥的保密。•(3)加密和解密算法适用于所有密钥空间中的元素。•(4)系统便于实现和使用方便。•为了防止信息被篡改、删除、重放和伪造，就要求系统具有对发送的信息验证的能力，使接收者或第三者能够设别和确认信息的真伪。•实现这类功能的系统称为认证系统。•信息认证要求能保证任何不知密钥的人不能构造出一个密文，使确定的接收者脱密成一个可理解的信息。•信息的完整性，它表示在干扰条件外，系统保持恢复信息和原来发送信息一致性的能力，实际中常借助于检错和纠错技术来保证信息的完整性。•信息系统安全的中心内容是保证信息的保密性、认证性和完整性。2.2单表代换密码•2.2.1代换密码概述•令A表示明文字母集，它有q个字母或字符，可以抽象地用Zq={0,1,2,…,q-1}来表示。•在加密时，将明文分成长为L的信息单元，称为明文组，用m表示，即m=(m0m1…mL-1)(mi∈Zq)。•通常称m为L-报文，它是定义在ZqL上的随机变量(ZqL是Zq上的L维向量空间)。明文空间M={m|m∈ZqL}。•令A'表示密文字母集，它有q'个字母或字符，可用Zq'={0,1,2,…,q'-1}来表示。密文单元为c=(c0c1…cL'-1)(ci∈Zq')。c是定义在Zq’L’上的随机变量（Zq’L’是Zq'上的L'维向量空间）。密文空间C={c|c∈Zq’L’}.当A=A'时，有C={c|c∈ZqL’}，即明文和密文由同一字母表构成。•加密变换是由明文空间到密文空间上的映射•f:M→C(m∈M，c∈C)•当f是一一对应映射时，存在逆映射f-1，使)C,M()()(11cmmmffcf•加密变换通常是在密钥控制下变化的，即•c=f(m,k)=Ek(m)•其中k∈Y，Y为密钥空间。•一个密码系统就是在f作用下由M→C的映射，或以C中的元素代替M中的元素，在此意义下称这类密码为代换密码。•当L=1时，称为单字母代换，L1时，称为多字母代换。•一般选择A=A'，即明文和密文字母表相同。•若L=L'，则映射f可以构造成一一对应，密码没有数据扩展。•若LL'，则有数据扩展，可使映射f为一对多的，即明文组可能找到多于一个密文组来代换，称为多名代换密码。•若LL'，则明文数据将被压缩，此时每个明文组无法找到唯一的只与它相对应的密文组，映射f是不可逆的，从密文无法完全恢复成明文信息•在信息加密时必须是L≤L'。•而LL'的变换可用在数据认证系统。2.2.2几种代换密码•在代换密码中，当A=A',q=q',L=L'时，如果明文的所有字母都用一个固定的明文字母表到密文字母表的映射，即f：Zq→Zq，则称这种密码为单表代换。•令明文m=m0m1…，则其相应密文为：•c=E(m)=c0c1…=f(m0)f(m1)…•若明文字母表A=Zq={0,1,…,q-1}，则相应的密文字母表为A‘={f(0),f(1),…f(q-1)}，A’是A的某种置换。•如何控制？密钥•昀直观的是与密钥加，或乘，但关键是否都能从密文恢复为明文？•1.加法密码•加法密码表达式为：•Ek(i)=(i+k)≡jmodq0≤i,jq,Y={k|0≤kq}•其中密钥空间元素个数为q•k=0为恒等变换。•解密变换为：•Dk(j)=Eq-k(j)≡j+q-k≡i+k-k≡imodq•密文字母表是将明文字母表循环左移k位•由于k只能取25个不同数字（除去k=0的恒等变换），故安全性极差。•例2.1：对英文26个采用加法密码，选定密钥为k=5，则有代换表：•A：abcdefghijklmnopqrstuvwxyz•A'：FGHIJKLMNOPQRSTUVWXYZABCDE•明文m=Thisisaprivateconversation•密文c=YMNXNXFUWNAFYJHTSAJWXFYNTS•2.乘法密码•乘法密码