《密码学基础教程ppt课件.ppt》由会员分享，可在线阅读，更多相关《密码学基础教程ppt课件.ppt（74页珍藏版）》请在三一办公上搜索。
1、信息安全Information Security,武汉大学计算机学院 武汉大学信息安全研究所,傅建明博士,Jmfu_,密码学基础知识,密码学概述传统的密码学对称密码公钥密码序列密码,密码学概述,通信保密（COMSEC）：60-70年代 信息保密计算机安全（ COMPUSEC）:60年代 机密性、访问控制、认证, TCSEC标准信息安全（INFOSEC）：80-90年代 机密性、完整性、可用性、不可否认性 等信息保障（IA）：90年代-至今,信息安全发展的四个阶段,年代,通信安全发展时期,从有人类以来,60年代中期,计算机安全发展时期,80年代中期,信息安全发展时期,90年代中期,信息安全保障发
2、展时期,安全保障能力,基本的通讯模型通信的保密模型通信安全-60年代（COMSEC）,发方,收方,信源编码信道编码信道传输通信协议,发方,收方,敌人,信源编码信道编码信道传输通信协议密码,信息安全的三个基本方面保密性 Confidentiality 即保证信息为授权者享用而不泄漏给未经授权者。完整性 Integrity数据完整性，未被未授权篡改或者损坏系统完整性，系统未被非授权操纵，按既定的功能运行可用性 Availability 即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况。,信息安全的含义(80-90年代),信息安全的其他方面信息的不可否认性No
3、n-repudiation ： 要求无论发送方还是接收方都不能抵赖所进行的传输鉴别Authentication 鉴别就是确认实体是它所声明的。适用于用户、进程、系统、信息等审计Accountability确保实体的活动可被跟踪可靠性Reliability特定行为和结果的一致性,安全需求的多样性,保密性一致性可用性可靠性可认证，真实性,责任定位，审计性高性能 实用性占有权,如何保证这些需求？,美国人提出的概念:Information Assurance保护（Protect）检测（Detect）反应（React）恢复（Restore）,保护Protect,检测Detect,反应React,恢复Re
4、store,信息保障,电子邮件 自动提款机电话卡: IP卡、201电话卡银行取钱信用卡购物,密码？,密码从军事走向生活,密码学(Cryptology): 是研究信息系统安全保密的科学.密码编码学(Cryptography): 主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.,基本概念,量子密码(单量子不可复制定理)DNA密码化学密码,密码新技术,消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过
5、程称为解密(Decryption)。 对明文进行加密操作的人员称作加密员或密码员(Cryptographer).密码算法(Cryptography Algorithm):是用于加密和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm).所传送消息的预定对象称为接收者(Receiver).接收者对密文解密所采用的一组规则称为解密算法(Decryption Algorithm).,加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Ke
6、y).,密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。,加密通信的模型,Alice,加密机,解密机,Bob,安全信道,密钥源,Oscar,x,y,x,k,密码体制：它是一个五元组（P,C,K,E,D)满足条件： （1）P是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间） *（4）任意k K,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数，满足dk(ek(x)=x, 这里 x P。,密码体制（系统）,按照保密的内容分:受限制的（restricte
7、d)算法:算法的保密性基于保持算法的秘密。 基于密钥（key-based)的算法:算法的保密性基于对密钥的保密。-现代密码理论,密码算法分类-i,基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetric cipher)：又称传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetric cipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-key cipher) 。公开密钥算法用一个密钥进行加密, 而用另一个进行解密
8、.其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥.解密密钥必须保密,又称私人密钥（private key)私钥.简称私钥。,密码算法分类-ii,按照明文的处理方法：分组密码（block cipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（stream cipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。 序列密码是手工和机械密码时代的主流,密码算法分类-iii,对称密钥密码又可分为：分组密码 每次对一块数据加密 多数网络加密应用 DES,IDEA,RC6,Rijndael流密码 每次对一位
9、或一字节加密 手机 One-time padding,Vigenre,Vernam,密码算法分类-iv,公开密钥密码: 大部分是分组密码，只有概率密码体制属于流密码 每次对一块数据加密 数字签名,身份认证 RSA,ECC,ElGamal 加密解密速度慢,密码算法分类-v,三个阶段：1949年之前 密码学是一门艺术19491975年 密码学成为科学1976年以后 密码学的新方向公钥密码学,密码学的起源和发展-i,密码学的起源,隐写术(steganography): 通过隐藏消息的存在来保护消息.隐形墨水字符格式的变化图象图像,(象形文字的修改)Modified Hieroglyphics, c.
10、 1900 B.C. 密码学的第一个例子是对标准书写符号的修改,example-i,我去君留十载中 爱无南北与西东 万株松树青山上 洁白孤高生不同,example-ii,Spartan Scytale, c. 500 B.C. 斯巴达人用于加解密的一种军事设备 发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation),Polybius Checkerboard , 205123 B.C. 明文:POLYBIUS密文:3534315412244543,example-iii,Caesar Cipher, c. 50 B.C. A B C D E F G X Y Z D E
11、F G H I J A B C 明文:Caesar cipher is a shift substitution 密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQ,example-iV,Nomenclator 代码本 c.1400字母、符号、单词、短语 代码代码 字母、符号、单词、短语应用：World War II,Example -V,Example Cont,网格加密法：中国例：密文：王先生： 来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。 弟：李明 2001年11月7日,网格加密法：中国例：密文：王先
12、生： 来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。 弟：李明 2001年11月7日,明文：情报在雨伞把中。,兽栏法：明文：System密文：,密文字母表：,古典实例,双轨密码：18611865年例：明文：Discrete and System 密文：Dsrtadytm Iceensse加密方法： D s r t a d y t m i c e e n s s e,Beale密码,C= 115 73 24 818 37 52 49 17 31 62 657 22 7 15,M= I have deposited,(1) When, in
13、the course of human events, it becomes necessary(11) For one people to dissolve the political bands which have (21) Connected them with another, and to assume among the Powers(31) Of the earth the separate and equal station to which (41) The Laws of Nature and of Natures God entitle them,(51) A dece
14、nt respect to the opinions of mankind requires that(61) They should declare the causes which impel them to the(71) separation. We hold these truths to be self-evident, that(81) All men are created equal, that they are endowed by(91) Their Creator with certain unalienable rights, that among(99) These
15、 are Life, Liberty, and the pursuit of Happiness.,古典密码,古典密码（6）,Vigenre密码是一种基于移位字母表的周期代替密码，它的密钥K由一个字母序列来指定：kk1kd。其中：ki（i1，d）给出了第i个字母表的移动位数，即fi(a)(a+ki) mod n.例如：明文INTELLIGENT用密钥PLAY加密为： MINTE LLIG ENT KPLAY PLAY PLA Ek(M)XYTC AMIE TYT,例 设m6，且密钥字是CIPHER,这相应于密钥。假定明文串是 this cryptosystem is not secure 首先
16、将明文串转化为数字串，按6个一组分段，然后模26“加”上密钥字得：,使用Vigenre表可以方便地进行加密和解密。,相应的密文串将是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类似,不同的只是进行模26减,而不是模26加。,古典密码（7）,通过一次加密一组字母来使密码分析更加困难。Playfair密码：Playfair密码是一个双字母组代替密码，用英国科学家Lyon Playfair的名字命名。Playfair密码的密钥是由一个25个字母（J视为I）的55矩阵给出：,HARPSICODBEFGKLMNQT UVWXYZ,加密规则,对于矩阵中的每一对明文字母m1m2
17、按如 下规则加密（m1m2对应的密文为c1c2）若m1和m2在同一行，则c1和c2分别是m1和m2右边的字母，其中第一列认为是第五列的右边；若m1和m2在同一列，则c1和c2分别是m1和m2右边的字母，其中第一行认为是最后一行的下边； 若m1和m2在不同的列，则c1和c2是以m1和m2为顶点的矩形的另两个顶点，其中c1和m1在一行， c2和m2在一行；若m1m2，则在m1和m2之间插入一个无效字符（例如X）后重新分组；若明文有奇数个字符，则在末尾加上一个无效字符。,Example Cont,古玩店的商品价格：$5321.00 EPMO 最简单的密码：DNES PLEH 倒过来：HELP SEN
18、D 第一次世界大战期间，德国使用字典编写密码 25-3-17电视剧：誓言无声爱情誓言：584， 1314， 880,1949年之前: 古典密码（classical cryptography) 密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段(substitution & permutation)出现，针对的是字符 简单的密码分析手段出现,密码学的起源和发展-ii,19491975年: 计算机使得基于复杂计算的密码成为可能1949年Shannon的“The Communication Theory of Secret Systems” 1967年David Kahn的T
19、he Codebreakers1971-73年IBM Watson实验室的Horst Feistel等的几篇技术报告 Smith,J.L.,The Design of Lucifer, A Cryptographic Device for Data Communication, 1971Smith,J.L.,An Expremental Application of Cryptogrphy to a remotely Accessed Data System, Aug.1972 Feistel,H.,Cryptography and Computer Privacy, May 1973数据的安
20、全基于密钥而不是算法的保密,密码学的起源和发展-iii,1976年以后: 1976年Diffie & Hellman的“New Directions in Cryptography”提出了不对称密钥密码1977年Rivest,Shamir & Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！,密码学的起源和发展-iv,1976年以后: 对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟 Rijndae
21、l,RC6, MARS, Twofish, Serpent等出现2001年Rijndael成为DES的替代者,密码学的起源和发展-v,假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：1.唯密文攻击：Oscar具有密文串y.2.已知明文攻击: Oscar具有明文串x和相应的密文y.3.选择明文攻击：Oscar可获得对加密机的暂时访问， 因此他能选择明文串x并构造出相应的密文串y。4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y，并构造出相应的明文x. 这一切的目的在于破译出密钥或密文,密码分析,密码破译的原
22、则: 遵循观察与经验方法:采用归纳与演绎步骤:分析、假设、推测和证实三大要素：语言的频率特征： e连接特征: q u, I e x, 重复特征: th, tion , tious,密码破译,无条件安全（Unconditionally secure） 无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性. Onetime pad计算上安全（Computationally secure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期.,攻击方法的复杂性,（1） 数据复杂性（2） 处理复杂性（3） 存储复杂性,算法的实现： 密码模式密码协议,密码学数学基础,
23、熵-事件出现的平均不确定性-一个事件平均所需的信息量中国剩余定理（孙子算经）,熵,例：X可能在下周某天去钓鱼。 E=星期一,星期二,星期三,星期四, 星期五,星期六,星期日H（X）=?例：任意给定一个1-20的数，猜多少次可以猜到该数。,熵,例：甲任意取一个不超过10的整数，由乙来猜，但允许乙提K个问题，甲只回答“是”或者“非”，问K多大时可以确定猜到该数。 解：若令猜想作为事件V，V可能有10种结果，假定这10种结果是等概率的，V的熵为：H（V）= log210=3.32令事件Ak=U1U2U3Uk为提问k个问题，但Ui的熵不超过log22=1，（因为只有“是”或者“非”），故Ak的熵为不超
24、过k比特，则：log210 klog22 =k， k 3.32 故 k=4,熵,例：有25个外表完全相同的硬币，其中24个重量完全一样，有一个较轻的伪币，用无砝码的天平，试问要做多少次的比较，可以找到这枚伪币？解：事件V为找出伪币，可能有25个结论，他们是等概率，故：H（V）= log225，事件U为天平称的结果，可能有3种情况：1.左右平衡；2.左边重；3.右边重；故：H（U）= log23令Ak=U1U2U3Uk为连续用k次天平的事件， klog23 log225 k （log225）/ log23=2.93故 k最少为3次,熵,问题修改为：如果25个硬币中有一枚假币，用无砝码的天平，试问
25、要做多少次的比较，可以找到这枚假币，且是轻还是重.,中国剩余定理,定理：如果n的素数因子分解式为p1p2 pt，则一组方程 (x mod pi）= ai，其中i = 1,2,t，有唯一解x，其中x小于n（其中某些pi可能相等）。例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？x mod 3 = 2 5*7*2=70 mod 3=1x mod 5 = 3 3*7*3=63 mod 5=3x mod 7 = 2 3*5*2=30 mod 7=2,中国剩余定理,定理：令d1，d2，,dt为两两互素，并令n=d1d2dt，则 x mod di xi (i=1, t)在0，n-1
26、范围内有公共解x：x= mod n其中：mi=n/di，yi=mi-1 mod di,数据加密标准算法DES,背景DES是20年来全世界通用的标准算法。20世纪70年代初期，非军事性的密码处于一种无序状态。1972年，美国国家标准局NBS开始一项保护计算机和通信数据的项目，其中一部分是要开发一个单独的标准保密算法。1973年5月15日，NBS公开征集标准加密算法，并公布了设计要求，未果。1974年8月，NBS第二次征集算法，收到一份可选方案：基于IBM在20世纪70年代初开发的LUCIFER算法的算法。1976年，NBS指派两个工作组来评价该标准。DES在1976年11月23日被宣布为联邦标准
27、，允许在非保密的政府通信中使用。标准的官方描述在1977年1月15日颁布，6个月后生效。1984年9美国总统签署145号国家安全决策令(NSDD),命令NSA着手发展新的加密标准,用于政府系统非机密数据和私人企事业单位. NSA宣布每隔5年重新审议DES是否继续作为联邦标准,1988年(FIPS46-1),1993年(FIPS46-2),1998年不再重新批准DES为联邦标准.,NBS公开征集标准加密算法的要求,算法必须提供高度的安全性算法必须有详细的说明,并易于理解算法的安全性必须取决于密钥,不依赖于算法本身的保密算法必须必须对所有用户都适用算法必须适用于各种应用算法必须能用电子设备经济地实
28、现算法必须使用效率高算法必须能被证实有效算法必须是可移植的,DES加密算法,高级数据加密标准AES,背景AES加密算法描述算法评价,背景,现代计算机速度的迅速提高，使得只有56bit密钥的DES算法的安全性面临着极大的挑战。1997年，NIST公开征求AES（Advanced Encryption Standard）作为2001年以后的数据加密标准。1998年8月，AES召开第一次候选会，确定15个算法入围。1999年3月， AES召开第二次候选会，有5个算法入围（MARS, RC6, Rijndael, Serpent和Twofish）。2000年10月，NIST选出由比利时的Joan Da
29、emen和Vincent Rijmen提交的Rijndael算法作为AES。2001年夏天，NIST颁布新的信息处理标准（FIPS），将Rijndael算法作为AES。,加密算法概述,AES算法与以往的基于Feistel网的密码（如DES）不同，算法的每一步都是可逆的。算法的明文块长可以为128bit，192bit或256bit，密钥也可以分别为128bit，192bit或256bit。算法有多圈相同的运算，每一圈包括4个步骤：非线性代替（S-盒）行循环左移（ShiftRow）列混合变换（MixColum）与扩展密钥相异或每一圈的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变换和循环左移
30、算法定义的所有运算都是在有限域GF(28)上进行的,AES的演示,演示,RSA算法,由MIT的 Rivest, Shamir & Adleman 在 1977 提出最著名的且被广泛应用的公钥加密体制 明文、密文是0到n-1之间的整数，通常n的大小为1024位二进制或309位十进制数可用于数字签名,RSA算法描述,1.取两个素数p和q（保密，如p=5,q=11）2.计算N=pq（N公开），(N)=(p-1)(q-1)保密3.随机选取整数e，满足gcd（e, (N)）=1 (即e与(N)互素)4.计算d，使得ed 1 mod (N)公钥=e,N；私钥=d,N,RSA算法描述,加密： C=Me mo
31、d N, where 0MN解密： M=Cd mod N 公钥为（e，N）， 私钥为（d，N）,安全性,公钥=e,N；私钥=d,N安全性在于由e和N来计算d是不可行的ed 1 mod (N)如果知道e和(N)，则容易求得d。那困难在哪里？(N)难求!(N)=？ N=p*q(N)=(p-1)(q-1)最终的困难在于很难将N分解为两个素数之积。,椭圆曲线密码介绍,1985年Miller,Koblitz 独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合运算定义：若曲线三点在一条直线上,则其和为OO用作加法的单位：O = -O; P+O = P一条竖直线交X轴两点P1、
32、P2，则P1+P2+O=O，于是P1 = -P2如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S,椭圆曲线密码示意图,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p针对所有的0= x p，可以求出有效的y，得到曲线上的点(x,y)，其中x,y p。记为Ep(a,b)Ep(a,b)中也包括O加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在E
33、p(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则 P+Q=(x3,y3)为x3=2-x1-x2 (mod p)y3=(x1-x3)-y1 (mod p)其中，如果PQ，则 = (y2-y1)/(x2-x1) 如果P=Q，则 = (3x12+a)/(2y1),椭圆曲线用于加密,找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm=kG,Pm+kP)如果k使得kG或者kP为O，则要重新选择k.解密Cm: (Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有扩张,序列密码-A5算法,Question?,
