密码学发展史及关键技术

第二课：应用密码学基础1概述古典密码分组密码与流密码公钥密码Hash函数数字签名密钥管理密码学发展简史基本概念古典密码1949年以前1949—1976年1976年以后现代密码公钥密码Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。密码学的历史源远流长，人类对密码的使用可以追溯到古巴比伦时代恺撒密码明文字母表：abcdefghijklmnopqrstuvwxyz密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC公元前一世纪恺撒用于军事通讯单字母代换密码把字母表中的每个字母用其后面第3个字母进行代换加密：c=E(p)=(p+k)mod(26)解密：p=D(c)=(c-k)mod(26)（恺撒密码中，k=3）结构简单，安全性完全取决于加解密算法。密钥空间小，只有25个可能的密钥k，适用于穷举密钥攻击。关键字密钥◦keyabcdefghijklmnopqrstuvwxyzKEYABCDFGHIJLMNOPQRSTUVWXZ◦spectacularabcdefghijklmnopqrstuvwxyzSPECTAULRBDFGHIJKMNOQVWXYZ◦相对于恺撒密码，关键字密码泄露给破译者的信息更少（英文字母表）任意代换的密钥空间：26！4x1026可能的key。公元九世纪的阿拉伯科学家阿尔－金迪提出了字母频率分析破译单字母代换密码的思想。英文字母频率统计表16世纪，法国外交官维热纳尔第一次系统阐明多表单字母代换密码的思想，即以两个以上的单字母代换密码表依次加密明文消息，并提出使用26个密码表的维热纳尔密码。维热纳尔密码能有效抗击字母频率分析，18世纪开始普及使用。明码表：abcdefghijklmnopqrstuvwxyz密码表1：FZBVKIXAYMEPLSDHJORGNQCUTW密码表2：GOXBFWTHQILAPZJDESVYCRKUHN明文：“hello”--》密文：“AFPAD”19世纪中叶，英国数学家和发明家巴比奇成功破解了维热纳尔密码。期间普鲁士军官卡西斯基也独立地发现了破解维热纳尔密码的技术（卡西斯基测试）。19世纪末，意大利物理学家马可尼发明了无线电技术。无线电技术的双重特性—易通信性和易拦截性，使得加密问题变得更为重要与紧迫。第一次世界大战中，法军破解德国军方的ADFGVX密码系统，导致德军进攻失败。齐默尔曼密码电报的破解，促使美国人决定放弃中立立场而加入了战争。一战史见证了一系列密码破译者的胜利。英军40号房。转子机（RotorMachine）恩格玛密码机工作原理与转子机类似，但设计更为复杂。1918年，德国人谢尔比斯发明恩格玛原型机。二战期间，德军广泛应用恩格玛密码机于军队秘密通信。其密钥空间大小可达1020量级以上。1931年，盟军得到恩格玛密码机的使用说明并试图复制恩格玛密码机。波兰人雷臼斯基的破译技术和（英国）图灵“炸弹”破译机，极大地促进了恩格玛密码的破译进程。英军破译恩格玛密码，德国海军、陆军陆续遭受重创，为二战战场形势的逆转立下汗马功劳。历史悠久，时间跨越了二三千年，直至1949年。广泛应用于军事、外交和情报领域。密码编码与密码破译之间的斗争不断推动着密码学的发展。古典密码主要特征◦基于字符。◦数据的安全基于算法的保密。里程碑：1949年Shannon发表“TheCommunicationTheoryofSecretSystems”。计算机使得基于复杂计算的密码成为可能。密码的安全基于密钥而不是算法的保密（如30年后的DES）明文P加密E解密D明文P密文C加密密钥Ke解密密钥Kd非安全信道里程碑：1976年Diffie&Hellman发表的“NewDirectionsinCryptography”首次提出了公钥密码体制的思想。1977年Rivest,Shamir&Adleman提出了RSA公钥算法。同年，美国国家标准局（NBS，即现在的国家标准与技术研究所NIST）正式公布实施了美国的数据加密标准（DataEncryptionStandard，DES），公开它的加密算法，并被批准用于政府等非机密单位及商业上的保密通信。近代密码学开启。90年代出现椭圆曲线等其它新型公钥算法。公钥密码特征：加解密算法公开；两个密钥，公钥用于加密，私钥用于解密。通信双方无须事先交换密钥就可建立保密通信。公钥密码算法广泛应用于实现保密性、数字签名、认证、密钥交换等安全功能。密码学发展简史密码学基本概念机密性（Confidentiality）：防止信息泄漏给未经授权的个人、实体或程序或为其所用。完整性（Integrity）：数据没有以未经授权的方式加以改变的特性。认证（Authentication）：向一个实体所声明的身份提供担保。不可否认（Non-repudiation）：防止参与通信的实体事后否认参与全部或部分通信过程。密码学基础机密性完整性认证不可否认性…密码学(Cryptology):是研究信息系统安全保密的科学。包括密码编码学和密码分析学。盾矛密码体制是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）（4）任意k∈K，有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x，这里x∈P。EekDdkCPek:PCdk:明文P加密E解密D明文P密文C密钥Ke密钥KdAlliceBobOscar（窃听者或恶意攻击者）密码体制五元组（P,C,K,E,D)非安全信道单钥(私钥或对称)密码体制：加密密钥Ke和解密密钥Kd相同或者本质上等同，即从其中一个容易推出另一个，其典型代表是美国的数据加密标准(DES)。明文P加密E解密D明文P密文C密钥Ke密钥Kd非安全信道Ke=Kd双钥(公钥或非对称)密码体制：加密密钥Ke和解密密钥Kd不相同，加密密钥可以公开，解密密钥由用户自己秘密保存。其典型代表是RSA体制。（Ke公开，Kd由接收者保密）明文P加密E解密D明文P密文C密钥Ke密钥Kd非安全信道单钥加密体制分为两类：分组密码和流密码（序列密码）。◦分组密码：先将明文分组(每组含有多个字符)，然后逐组地进行加密。我们通常所说的分组密码特指私钥分组密码。◦流密码（序列密码）：明文按字符逐位地被加密。Kerckhoffs密码分析假设（19世纪提出）：假定密码分析者已掌握密码算法及其实现的全部详细资料，密码系统的安全性完全寓于密钥之中。（已知加密E和解密D，未知Kd）明文P加密E解密D明文P密文C密钥Ke密钥Kd唯密文攻击：密码分析者只拥有若干密文串。已知明文攻击：密码分析者掌握一些明文和用同一密钥加密这些明文所对应的密文。明文P加密E解密D明文P密文C密钥Ke密钥KdOscar（窃听者或恶意攻击者）非安全信道选择明文攻击：密码分析者可获得加密机的访问权限，这样他能获得任意的明文串和对应的密文串。选择密文攻击：密码分析者可获得解密机的访问权限，这样他能获得任意的密文串和对应的明文串。明文P加密E解密D明文P密文C密钥Ke密钥KdOscar（窃听者或恶意攻击者）非安全信道Shannon保密系统的信息理论Simmons认证系统的信息理论算法复杂性理论（图灵机、NP问题）基础数学理论◦数论◦抽象代数（群、环、域）◦概率统计概述古典密码分组密码与流密码公钥密码Hash函数数字签名密钥管理古典密码一般特征古典密码分类古典密码的基本运算有两种：代换和置换。◦代换(Substitution)是指每一个或一组字符被另一个或一组字符所取代。如恺撒密码◦置换(Permutation)是不改变明文字符，而按一定规则重新安排字符的次序。如“iloveyou””youlovei”密码大都比较简单，可用手工或机械操作即能实现加解密。密码算法基于字符。安全主要依赖于算法的保密，整体安全性不高。单字母代换密码◦单表代换密码◦多表代换密码多字母代换密码单表代换密码：明文的一个字符用相应的一个密文字符代替。如移位密码：明密文字母表均为英文字母表，密钥k满足：0=k=25加密：y=x+k(mod26)解密：x=y-k(mod26)多表代换密码：以一系列（两个以上）代换表依次对明文消息的字母进行代换。如维吉尼亚（Vigenere）密码：明密文字母表均为英文字母表，m为一正整数，密钥K=(k1,k2……km)加密：yi=xi+ki(mod26)解密：xi=yi+ki(mod26)多字母代换密码：每次以L1个字母为单元进行代换。可以用矩阵变换方便地描述多字母代换密码，所以又称为矩阵变换密码。如Hill密码：这里密钥K可视为二阶可逆矩阵。加密：y1=11x1+3x2(mod26)y2=8x1+7x2(mod26)概述古典密码分组密码与流密码公钥密码Hash函数数字签名密钥管理概述DESIDEARC5AES工作模式两大设计准则：◦扩散：将明文及密钥的每一位数字的影响尽可能迅速地散布到输出密文的较多个数字中。◦混淆：使作用于明文的密钥和密文之间的关系复杂化。分组及密钥长度n要足够大，防止穷举攻击法凑效。加解密运算简单，易于软硬件的快速实现。密钥流生成器KiPi密钥流生成器KiCiPi差分密码分析：本质上是一种选择明文攻击方法，通过分析特定明文对的差值对密文对的差值的影响来恢复某些密钥比特。线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统。概述DESIDEARC5AES工作模式数据加密标准DES(DataEncryptionStandard)于1977年由美国公布。第一个公开绝大部分加密原理和算法细节并得到广泛应用的最具有代表性的分组密码体制。DES源于IBM的Lucifer算法，是一种对二元数据进行加密的方法。数据明文、密文分组长度均为64位，密钥长度56位（另含8位奇偶校验位）。DES算法的基本设计思想：通过循环或迭代，将简单的基本运算(例如左移、右移、模2加法等)和变换(选择函数、置换函数)构造成数据流的非线性变换(加密变换或解密变换)。DES的56位密钥已被计算证明是不安全的。目前攻击DES的主要方法有差分攻击、线性攻击和相关密钥攻击等，其中线性攻击方法最为有效。为加强安全，实际应用场合一般使用双密钥或三密钥的3重DES，有效密钥长度可达112位或168位。到目前为止，还没有人给出攻击三重DES的有效方法。概述DESIDEARC5AES工作模式IDEA(InternationalDataEncryptionAlgorithm)算法即国际数据加密算法。由XuejiaLai和JamesMassey于1992年提出。目前这个算法可抗拒差分密码分析和相关密钥密码分析，非常安全。应用于PGP。明密文块长度均为64比特，密钥长为128比特。三种基本运算：XOR(异或)、模216加(加法运算，溢出忽略)、模(216+1)乘(乘法运算，溢出忽略)。同一算法既可用于加密，又可用于解密，易于软硬件实现。概述DESIDEARC5AES工作模式RonRivest1994设计，1995公开。RC5版本：RC5-w/r/b，w为16/32/64位明文分组长度，r为加密轮数，b为密钥K长度（0—255位）。算法作者建议标定版本为RC5-32/12/16。适用于软件或者硬件实现，运算速度快。依赖于数据的循环移位，可增强抗攻击能力。概述DESIDEARC5AES工作模式AES（AdvancedEncrytionStandard）高级加密标准的基本要求是：比三重DES快、至少与三重DES一样