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

无线网络安全技术秦中元

东南大学信息科学与工程学院

信息安全研究中心

zyqin@2024/7/92上节课内容课程相关信息第一章概述1.1信息安全1.2网络安全1.3无线网络安全2024/7/93本次课内容第二章经典加密技术2.1密码学概述2.2古典密码代替密码置换密码2024/7/942.1密码学概述密码学(Cryptology):是研究信息系统安全保密的科学.密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.2024/7/952.1.1基本术语消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encryption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。对明文进行加密操作的人员称作加密员或密码员(Cryptographer).所传送消息的预定对象称为接收者(Receiver).密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm).接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm).2024/7/96加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).2024/7/97加密通信的模型密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。2024/7/982.1.2密码学的起源和发展三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学2024/7/99密码学的起源隐写术(steganography):通过隐藏消息的存在来保护消息.隐形墨水图像信息藏头诗2024/7/9102024/7/9112024/7/912密码学的起源和发展(1949年之前)古典密码（classicalcryptography)密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段(substitution&permutation)出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全依赖于算法是否保密；2024/7/913密码学的起源和发展(1949～1975)

计算机使得基于复杂计算的密码成为可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson实验室的HorstFeistel等的几篇技术报告Smith,J.L.,TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971Smith,J.L.,…,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.,CryptographyandComputerPrivacy,May1973数据的安全基于密钥而不是算法的保密2024/7/914密码学的起源和发展(1976年以后)1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不对称密钥密码1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！2024/7/9152.1.3密码算法分类1.按照保密的内容分类:受限制的（restricted)算法:算法的保密性基于保持算法的秘密。基于密钥（key-based)的算法:算法的保密性基于对密钥的保密。2024/7/916密码算法分类2.基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetriccipher)，又称公开密钥算法（public-keycipher)：加密密钥和解密密钥不相同，从一个很难推出另一个。 公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥。解密密钥必须保密,又称私人密钥（privatekey)私钥，简称私钥。2024/7/917密码算法分类3.按照明文的处理方法：分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。 流密码是手工和机械密码时代的主流。2024/7/9182.1.4密码分析假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：1.唯密文攻击：Oscar具有密文串y.2.已知明文攻击:Oscar具有明文串x和相应的密文y.3.选择明文攻击：Oscar可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y，并构造出相应的明文x.这一切的目的在于破译出密钥或密文2024/7/919密码算法的安全性无条件安全（Unconditionallysecure）无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.Onetimepad计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期.2024/7/920穷尽密钥搜索所需的平均时间热力学的角度问题：多长的密钥是计算上安全的？方法：利用热力学第二定律进行求解。解：信息的表达需要一定的能量。通过改变系统的状态，记录单独的1位所需要的能量不少于kT（T表示系统的绝对温度，k=1.38*10-16erg/K为Boltzman常数)

假设在宇宙中运行，宇宙的环境温度为3.2K，则计算机操作1位需消耗4.4*10-16erg

太阳每年辐射的能量约为1.21*1041erg,可处理187位。假设连续提供32年，可处理192位。256位：1020年。结论：对256位的密钥进行穷举攻击是绝对行不通的。2024/7/922本次课内容第二章经典加密技术2.1密码学概述2.2古典密码代替密码置换密码2024/7/9232.2古典密码古典密码总的来说是基于字符的密码代替密码（substitutioncipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码(permutationcipher)，又称换位密码（transpositioncipher)：明文的字母保持相同，但顺序被打乱了。2024/7/9242.2.1代替密码简单代替密码（simplesubstitutioncipher),又称单字母密码（monoalphabeticcipher):明文的一个字符用相应的一个密文字符代替。多字母密码（polyalphabeticcipher)：明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。2024/7/925简单代替密码单表代换密码移位（shift）密码、乘数（multiplicative)密码仿射（affine)密码、多项式（Polynomial)密码密钥短语（KeyWord)密码多表代换密码维吉尼亚（Vigenere)密码博福特（Beaufort）密码滚动密钥(running-key)密码弗纳姆(Vernam)密码转轮机(rotormachine)2024/7/926多字母代换密码可以用矩阵变换方便地描述多字母代换密码，有时又称其为矩阵变换密码。PlayfaircipherHillcipher2024/7/9272.2.2数学基础同余的概念：给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r,0≤r<q，其中商s=[a/q],表示小于a/q的最大整数。定义r为amodq的剩余，记为r≡amodq.若整数a和b有(amodq)=(bmodq)，则称a与b在modq下同余。对于满足{r}={a|a=sq+r,s∈Z}的整数集称为同余类。模运算有下述性质：若q|(a-b)，则a≡bmodq(amodq)=(bmodq)意味a≡bmodqa≡bmodq等价于b≡amodq若a≡bmodq且b≡cmodq，则a≡cmodq2024/7/928模算术（ModularArithmatic)在modq的q个剩余类集{0，1，2，…，q-1}上可以定义加法和乘法运算如下:加法:((amodq)+(bmodq))modq=(a+b)modq乘法:((amodq)×(bmodq))modq=(a×b)modq2024/7/9292.2.3移位密码算法数学描述：设P=C=K=Z，对k∈K，定义ek(x)=x+k(mod26)=y∈C同时dk(y)=y-k(mod26)1：26个英文字母与模26剩余类集合{0,….,25}建立一一对应；2.当k=3时，为Caesar密码，即abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例子:cipher=>FLSKHU实际算法为：同时有，d3(y)=y-3(mod26)2024/7/930移位密码算法分析移位密码很容易受到唯密文攻击。因为：加解密算法已知可能尝试的密钥只有26个例如：给定加密的消息: PHHWPHDIWHUWKHWRJDSDUWB通过强力攻击得到明文：

meetmeafterthetogaparty.2024/7/9312.2.4乘数密码算法加密函数取形式为ek(x)=kx(mod26),k∈Z，要求唯一解的充要条件是gcd(k,26)=1该算法的数学描述为：设P=C=Z，K={k∈Z|gcd(k,26)=1},对k∈K，定义ek(x)=kx(mod26)和dk(y)=k-1(y)(mod26)，x,y∈Z例子:k=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR加密操作：

cipher=>SUFLKX2024/7/932乘数密码算法分析密钥空间小。对于乘数密码，当且仅当a与26互素时，加密变换才是一一映射的，因此a的选择有11种：

a=3,5,7,9,11,15,17,19,21,23,25可能尝试的密钥只有11个2024/7/933仿射密码加密函数取形式为ea,b(x)=ax+b(mod26),a,b∈Z，要求唯一解的充要条件是gcd(a,26)=1。q=26时，可能的密钥是26*12-1=311个2024/7/9342.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!≈4×1026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。2024/7/935单表替换密码的破译通过字母的使用频率破译2024/7/93602468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ频率密文字母频率基于语言统计规律的破译 1密文：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ2统计字母的相对频率；3猜测PZ可能是e和t；4统计字母的相对频率-双字母5猜测ZW可能是th，因此ZWP可能是the6经过反复猜测、分析和处理，明文：

itwasdisclosedyesterdaythatserveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow2024/7/9372.2.6对抗频率分析的办法多名代替密码多表代替密码多字母代替密码2024/7/938多名和多表代替密码与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。需要较大的密文空间。 例如，A可能对应于5、13、25，B可能对应于7、9、31、42。当对字母的赋值个数与字母出现频率成比例时。这是因为密文符号的相关分布会近似于水平线，可以挫败频率分析。多表代替密码：是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。2024/7/939Vigenérecipher(1858)是一种多表移位代替密码例子：q=26,x=polyalphabeticcipher,K=RADIO明文x=polyalphabeticcipher密钥k=RADIORADIORADIORADIO密文y=GOOGOCPKTPNTLKQZPKMF2024/7/940Vigenérecipher的破译依然保留了字符频率某些统计信息重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。一次一密Vigenere密码的改进思路Vigenere密码的弱点：周期性加长密钥长度-〉用一个和明文长度一样长的密钥如果每次加密都用与明文一样长的真随机密钥，将是最安全的。无法破解！缺点？？2024/7/9422.2.7多字母代替密码-PlayfairPlayfair:将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。5×5变换矩阵的构造:先密钥，后字母顺序。I与J视为同一字符加密规则:按成对字母加密

1)相同对中的字母加分隔符(如x) balloon→balxloon 2)同行取右边:he→EC 3)同列取下边:dm→MT 4)其他取交叉:kt→MQ，OD→TR2024/7/943Playfair举例5×5变换矩阵2024/7/944Playfair密码分析Playfair有26X26=676种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息2024/7/9452.2.8Hill密码(1929)基于矩阵的线性变换:将明文与密文都视作m元的向量（x1,x2

，…,xm)；(y