无线网络安全技术2011-2密码学概述.ppt

1、无线网络安全技术,秦中元东南大学信息科学与工程学院信息安全研究中心,2020/7/27,2,上节课内容,课程相关信息 第一章 概述 1.1 信息安全 1.2 网络安全 1.3 无线网络安全,2020/7/27,3,本次课内容,第二章 经典加密技术 2.1 密码学概述 2.2 古典密码 代替密码 置换密码,2020/7/27,4,2.1 密码学概述,密码学(Cryptology): 是研究信息系统安全保密的科学. 密码编码学(Cryptography): 主要研究对信息进行编码,实现对信息的隐蔽. 密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.,2020/7/2

2、7,5,2.1.1 基本术语,消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encryption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。 对明文进行加密操作的人员称作加密员或密码员(Cryptographer). 所传送消息的预定对象称为接收者(Receiver). 密码算法(Cryptography Algorithm):是用于加密和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm).接收者对密文解密所采用的一组规则称为解

3、密算法(Decryption Algorithm).,2020/7/27,6,加解密过程示意图,加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key).,2020/7/27,7,加密通信的模型,密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。,2020/7/27,8,2.1.2 密码学的起源和发展,三个阶段： 1949年之前 密码学是一门艺术 19491975年 密码学成为科学 1976年以后 密码学的新方向公钥密码学,2020/7/27,9,密

4、码学的起源,隐写术(steganography): 通过隐藏消息的存在来保护消息. 隐形墨水 图像信息,藏头诗,2020/7/27,10,2020/7/27,11,2020/7/27,12,密码学的起源和发展(1949年之前),古典密码（classical cryptography) 密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段(substitution &permutation)出现，针对的是字符 简单的密码分析手段出现 主要特点： 数据的安全依赖于算法是否保密；,2020/7/27,13,密码学的起源和发展(19491975),计算机使得基于复杂计算的密码成为

5、可能 1949年Shannon的“The Communication Theory of Secret Systems” 1967年David Kahn的The Codebreakers 1971-73年IBM Watson实验室的Horst Feistel等的几篇技术报告 Smith,J.L.,The Design of Lucifer, A Cryptographic Device for Data Communication, 1971 Smith,J.L.,An Expremental Application of Cryptogrphy to a remotely Accessed

6、Data System, Aug.1972 Feistel,H.,Cryptography and Computer Privacy, May 1973 数据的安全基于密钥而不是算法的保密,2020/7/27,14,密码学的起源和发展(1976年以后),1976年Diffie & Hellman的“New Directions in Cryptography”提出了不对称密钥密码 1977年Rivest,Shamir & Adleman提出了RSA公钥算法 90年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！,2020/7/27,15,2.1.3 密

7、码算法分类,1. 按照保密的内容分类: 受限制的（restricted)算法:算法的保密性基于保持算法的秘密。 基于密钥（key-based)的算法:算法的保密性基于对密钥的保密。,2020/7/27,16,密码算法分类,2. 基于密钥的算法，按照密钥的特点分类： 对称密码算法（symmetric cipher)：又称传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。 非对称密钥算法（asymmetric cipher)，又称公开密钥算法（public-key cipher)：加密密钥和解密密

8、钥不相同，从一个很难推出另一个。 公开密钥算法用一个密钥进行加密, 而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥。解密密钥必须保密,又称私人密钥（private key)私钥，简称私钥。,2020/7/27,17,密码算法分类,3. 按照明文的处理方法： 分组密码（block cipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 流密码（stream cipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。 流密码是手工和机械密码时代的主流。,2020/7/27,18,2.1.4

9、 密码分析,假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下： 1.唯密文攻击：Oscar具有密文串y. 2.已知明文攻击: Oscar具有明文串x和相应的密文y. 3.选择明文攻击：Oscar可获得对加密机的暂时访问， 因此他能选择明文串x并构造出相应的密文串y。 4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y，并构造出相应的明文x. 这一切的目的在于破译出密钥或密文,2020/7/27,19,密码算法的安全性,无条件安全（Unconditionally secure） 无论破译者有多少密文,他也无法解

10、出对应的明文,即使他解出了,他也无法验证结果的正确性. One time pad 计算上安全（Computationally secure） 破译的代价超出信息本身的价值 破译的时间超出了信息的有效期.,2020/7/27,20,穷尽密钥搜索所需的平均时间,热力学的角度,问题：多长的密钥是计算上安全的？ 方法：利用热力学第二定律进行求解。 解：信息的表达需要一定的能量。通过改变系统的状态，记录单独的1位所需要的能量不少于kT（T表示系统的绝对温度，k=1.38*10-16erg/K为Boltzman常数) 假设在宇宙中运行，宇宙的环境温度为3.2K，则计算机操作1位需消耗4.4*10-16er

11、g 太阳每年辐射的能量约为1.21*1041erg,可处理187位。假设连续提供32年，可处理192位。256位：1020年。 结论：对256位的密钥进行穷举攻击是绝对行不通的。,2020/7/27,22,本次课内容,第二章 经典加密技术 2.1 密码学概述 2.2 古典密码 代替密码 置换密码,2020/7/27,23,2.2 古典密码,古典密码总的来说是基于字符的密码 代替密码（substitution cipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。 置换密码(permutation cipher)，又称换位密码（transpos

12、ition cipher)：明文的字母保持相同，但顺序被打乱了。,2020/7/27,24,2.2.1 代替密码,简单代替密码（simple substitution cipher),又称单字母密码（monoalphabetic cipher):明文的一个字符用相应的一个密文字符代替。 多字母密码（polyalphabetic cipher)：明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。,2020/7/27,25,简单代替密码,单表代换密码 移位（shift ）密码、乘数（multiplicative)密码 仿射（affine ) 密码、多项式（Polynomial)密码 密钥

13、短语（Key Word)密码 多表代换密码 维吉尼亚（Vigenere)密码 博福特（Beaufort）密码 滚动密钥(running-key)密码 弗纳姆(Vernam)密码 转轮机(rotor machine),2020/7/27,26,多字母代换密码,可以用矩阵变换方便地描述多字母代换密码，有时又称其为矩阵变换密码。 Playfair cipher Hill cipher,2020/7/27,27,2.2.2 数学基础,同余的概念：给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r,0rq，其中商s=a/q,表示小于a/q的最大整数。定义r为a mod q的剩余，记为ra

14、mod q.若整数a和b有(a mod q)=(b mod q)，则称a与b在mod q下同余。 对于满足r=a|a=sq+r,sZ的整数集称为同余类。 模运算有下述性质： 若q|(a-b)，则ab mod q (a mod q)=(b mod q)意味ab mod q ab mod q等价于ba mod q 若ab mod q且bc mod q ，则ac mod q,2020/7/27,28,模算术（Modular Arithmatic),在mod q的q个剩余类集0，1，2，q-1上可以定义加法和乘法运算如下: 加法: (a mod q)+ (b mod q) mod q= (a+b) m

15、od q 乘法: (a mod q) (b mod q) mod q= (ab) mod q,2020/7/27,29,2.2.3 移位密码算法,数学描述：设P=C=K=Z，对k K，定义ek(x)=x+k (mod 26)=yC同时dk(y)=y-k (mod 26) 1：26个英文字母与模26剩余类集合0,.,25建立一一对应； 2.当k=3时，为Caesar密码，即 abcdefghijklmnopqrstuvwxyz DEFGHIJKLMNOPQRSTUVWXYZABC 例子: cipher = FLSKHU 实际算法为： 同时有，d3(y)=y-3 (mod 26),2020/7/2

16、7,30,移位密码算法分析,移位密码很容易受到唯密文攻击。 因为： 加解密算法已知 可能尝试的密钥只有26个 例如：给定加密的消息: PHHW PH DIWHU WKH WRJD SDUWB 通过强力攻击得到明文： meet me after the toga party.,2020/7/27,31,2.2.4 乘数密码算法,加密函数取形式为 ek(x)=kx (mod 26), kZ，要求唯一解的充要条件是gcd(k,26)=1 该算法的数学描述为：设P=C=Z， K=k Z|gcd(k,26)=1,对kK，定义ek(x)=kx (mod 26)和dk(y)=k-1(y)(mod 26)，x

17、,y Z 例子: k=9, ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 加密操作： cipher = SUFLKX,2020/7/27,32,乘数密码算法分析,密钥空间小。 对于乘数密码，当且仅当a与26互素时，加密变换才是一一映射的，因此a的选择有11种： a=3,5,7,9,11,15,17,19,21,23,25 可能尝试的密钥只有11个,2020/7/27,33,仿射密码,加密函数取形式为ea,b(x)=ax+b (mod 26), a,bZ，要求唯一解的充要条件是gcd(a,26)=1。 q=26时，可能的密钥是26*1

18、2-1=311个,2020/7/27,34,2.2.5 任意的单表代替密码算法,设P=C=Z，K是由26个符号0,1,25的所有可能置换组成。任意K，定义e(x)= (x)=y且d(y)=-1(y)=x, -1是的逆置换。 注： 1. 置换的表示： 2.移位密码、乘数密码、仿射密码算法都是替换密码的特例 3.密钥空间K很大，|k|=26! 41026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。,2020/7/27,35,单表替换密码的破译,通过字母的使用频率破译,2020/7/27,36,基于语言统计规律的破译,1 密文： UZQSOVUOHXMOPVGPOZPEVSGZWSZOPF

19、PESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 2 统计字母的相对频率；,3 猜测P Z可能是e和t； 4 统计字母的相对频率-双字母 5 猜测ZW可能是th，因此ZWP可能是the 6 经过反复猜测、分析和处理，明文： it was disclosed yesterday that serveral informal but direct contacts have been made with political representatives of the

20、 viet cong in moscow,2020/7/27,37,2.2.6 对抗频率分析的办法,多名代替密码 多表代替密码 多字母代替密码,2020/7/27,38,多名和多表代替密码,与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。需要较大的密文空间。 例如， A可能对应于5、13、25，B可能对应于7、9、31、42。 当对字母的赋值个数与字母出现频率成比例时。这是因为密文符号的相关分布会近似于水平线，可以挫败频率分析。 多表代替密码：是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。,2020/7/27,39,Vigenre cipher (

21、1858),是一种多表移位代替密码 例子：q=26, x=polyalphabetic cipher, K=RADIO 明文x=p o l y a l p h a b e t i c c i p h e r 密钥k=RAD I ORAD I ORA DI ORAD I O 密文y=GOOGOC P KTPN T LKQZP KM F,2020/7/27,40,Vigenre cipher的破译,依然保留了字符频率某些统计信息 重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。,一次一密,Vigenere密码的改进思路 Vigenere

22、密码的弱点：周期性 加长密钥长度-用一个和明文长度一样长的密钥 如果每次加密都用与明文一样长的真随机密钥，将是最安全的。 无法破解！ 缺点？,2020/7/27,42,2.2.7 多字母代替密码-Playfair,Playfair:将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。 55变换矩阵的构造: 先密钥，后字母顺序。I与J视为同一字符 加密规则:按成对字母加密 1) 相同对中的字母加分隔符(如x) balloon ba lx lo on 2) 同行取右边: heEC 3) 同列取下边: dm MT 4) 其他取交叉: kt MQ， OD TR,2020/7/27,43,Playfair举例,55变换矩阵,2020/7/27,44,Playfair密码分析,Playfair有26X26=676种