密码学基础教程ppt课件.ppt

信息安全信息安全Information Security武汉大学计算机学院武汉大学计算机学院 武汉大学信息安全研究所武汉大学信息安全研究所傅建明博士Jmfu_密码学基础知识密码学基础知识 密码学概述密码学概述 传统的密码学传统的密码学 对称密码对称密码 公钥密码公钥密码 序列密码序列密码密码学概述密码学概述（COMSECCOMSEC）：）：60-7060-70年代年代 信息保密信息保密（INFOSECINFOSEC）：）：80-9080-90年代年代 机密性、完整性、可用性、不可否认性机密性、完整性、可用性、不可否认性 等等（IAIA）：）：9090年代年代- -至今至今 基本的通讯模型基本的通讯模型 通信的保密模型通信的保密模型通信安全通信安全-60年代（年代（COMSEC）发方发方收方收方信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议发方发方收方收方敌人敌人信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议密码密码 信息安全的三个基本方面信息安全的三个基本方面 保密性保密性 Confidentiality即保证信息为授权者享用而不泄漏给未经授权者即保证信息为授权者享用而不泄漏给未经授权者 完整性完整性 Integrity 数据完整性，未被未授权篡改或者损坏数据完整性，未被未授权篡改或者损坏 系统完整性，系统未被非授权操纵，按既定的功系统完整性，系统未被非授权操纵，按既定的功能运行能运行 可用性可用性 Availability即保证信息和信息系统随时为授权者提供服务，而即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况。不要出现非授权者滥用却对授权者拒绝服务的情况。信息安全的含义信息安全的含义(80-90年代年代) 信息安全的其他方面信息安全的其他方面 信息的不可否认性信息的不可否认性Non-repudiation ： 要求无论发送方还是接收方都不能抵赖所进要求无论发送方还是接收方都不能抵赖所进行的传输行的传输 鉴别鉴别Authentication 鉴别就是确认实体是它所声明的。适用于用鉴别就是确认实体是它所声明的。适用于用户、进程、系统、信息等户、进程、系统、信息等 审计审计Accountability 确保实体的活动可被跟踪确保实体的活动可被跟踪 可靠性可靠性Reliability 特定行为和结果的一致性特定行为和结果的一致性安全需求的多样性安全需求的多样性 保密性保密性 一致性一致性 可用性可用性 可靠性可靠性 可认证，真实性可认证，真实性 责任定位，审计性责任定位，审计性 高性能高性能 实用性实用性 占有权占有权 如何保证这些需求？Information Assurance（ rotect）（ etect）（ eact）（ estore）保护保护Protect检测检测Detect反应反应React恢复恢复Restore信息保障 电子邮件电子邮件 自动提款机自动提款机 电话卡电话卡: IP卡、卡、201电话卡电话卡 银行取钱银行取钱 信用卡购物信用卡购物密码从军事走向生活密码从军事走向生活 密码学密码学(Cryptology): 是研究信息系统安全保密是研究信息系统安全保密的科学的科学.密码编码学密码编码学(Cryptography): 主要研究对信息主要研究对信息进行编码进行编码,实现对信息的隐蔽实现对信息的隐蔽.密码分析学密码分析学(Cryptanalytics):主要研究加密消主要研究加密消息的破译或消息的伪造息的破译或消息的伪造.基本概念基本概念 量子密码量子密码( (单量子不可复制定理单量子不可复制定理) ) DNADNA密码密码 化学密码化学密码 密码新技术密码新技术 消息被称为消息被称为明文明文( (Plaintext)Plaintext)。用某种方法伪装消息以。用某种方法伪装消息以隐藏它的内容的过程称为隐藏它的内容的过程称为加密加密( (EncrtptionEncrtption) )，被加密，被加密的消息称为的消息称为密文密文( (CiphertextCiphertext) )，而把密文转变为明文，而把密文转变为明文的过程称为的过程称为解密解密( (Decryption)Decryption)。 对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员密码员( (Cryptographer).Cryptographer). 密码算法密码算法( (Cryptography Algorithm):Cryptography Algorithm):是用于加密和解是用于加密和解密的数学函数。密的数学函数。 密码员对明文进行加密操作时所采用的一组规则称作密码员对明文进行加密操作时所采用的一组规则称作加密算法加密算法( (Encryption Algorithm).Encryption Algorithm). 所传送消息的预定对象称为所传送消息的预定对象称为接收者接收者(Receiver).(Receiver). 接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法解密算法( (Decryption Algorithm).Decryption Algorithm). 加解密过程示意图加解密过程示意图 加密和解密算法的操作通常都是在一组密钥的加密和解密算法的操作通常都是在一组密钥的控制下进行的控制下进行的,分别称为分别称为加密密钥加密密钥(Encryption Key) 和和解密密钥解密密钥(Decryption Key). 明文明文密文加密算法解密算法密钥密钥 密码学的目的密码学的目的：Alice和和Bob两个人在不安全的信道上进两个人在不安全的信道上进行通信，而破译者行通信，而破译者Oscar不能理解他们通信的内容。不能理解他们通信的内容。加密通信的模型加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk 密码体制：密码体制：它是一个五元组（它是一个五元组（P,C,K,E,D)满足条件：满足条件： （1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间） *（4）任意）任意k K,有一个加密算法有一个加密算法 和相应的解密算和相应的解密算法法 ，使得，使得 和和 分别为加密解密分别为加密解密函数，满足函数，满足dk(ek(x)=x, 这里这里 x P。EekDdkCPek:PCdk:密码体制（系统）密码体制（系统） 按照保密的内容分按照保密的内容分:受限制的（受限制的（restricted)算法算法:算法的保密性基于算法的保密性基于保持算法的秘密。保持算法的秘密。 基于密钥（基于密钥（key-based)的算法的算法:算法的保密性基算法的保密性基于对密钥的保密。于对密钥的保密。-现代密码理论现代密码理论密码算法分类密码算法分类-i 基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类： 对称密码算法对称密码算法（symmetric cipher)：又称：又称传统密码算传统密码算法（法（conventional cipher)，就是加密密钥和解密密钥，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又相同，或实质上等同，即从一个易于推出另一个。又称称秘密密钥算法秘密密钥算法或或单密钥算法单密钥算法。 非对称密钥算法（非对称密钥算法（asymmetric cipher):加密密钥和解密加密密钥和解密密钥不相同，从一个很难推出另一个。又称密钥不相同，从一个很难推出另一个。又称公开密钥公开密钥算法（算法（public-key cipher) 。 公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密, 而用另一个进行解而用另一个进行解密密.其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)，简称公钥，简称公钥.解密密钥必须保密解密密钥必须保密,又称私人密钥又称私人密钥（private key)私钥私钥.简称简称私钥私钥。密码算法分类密码算法分类-ii 按照明文的处理方法：按照明文的处理方法：分组密码（分组密码（block cipher):将明文分成固定长度将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。也是固定长度的密文。流密码（流密码（stream cipher):又称又称序列密码序列密码.序列密序列密码每次加密一位或一字节的明文，也可以称为码每次加密一位或一字节的明文，也可以称为流密码。流密码。 序列密码是手工和机械密码时代的主流序列密码是手工和机械密码时代的主流密码算法分类密码算法分类-iii 对称密钥密码又可分为：对称密钥密码又可分为：分组密码分组密码 每次对一块数据加密每次对一块数据加密 多数网络加密应用多数网络加密应用 DES,IDEA,RC6,RijndaelDES,IDEA,RC6,Rijndael流密码流密码 每次对一位或一字节加密每次对一位或一字节加密 手机手机 One-time padding,Vigenre,VernamOne-time padding,Vigenre,Vernam密码算法分类密码算法分类-iv 公开密钥密码公开密钥密码: : 大部分是分组密码，只有概率密码体制属于大部分是分组密码，只有概率密码体制属于流密码流密码 每次对一块数据加密每次对一块数据加密 数字签名数字签名, ,身份认证身份认证 RSA,ECC,ElGamalRSA,ECC,ElGamal 加密解密速度慢加密解密速度慢密码算法分类密码算法分类-v三个阶段：三个阶段： 19491949年之前年之前 密码学是一门艺术密码学是一门艺术 1949194919751975年年 密码学成为科学密码学成为科学 19761976年以后年以后 密码学的新方向密码学的新方向公钥密码学公钥密码学密码学的起源和发展密码学的起源和发展-i密码学的起源密码学的起源隐写术隐写术(steganography): 通过隐藏消息的通过隐藏消息的存在存在来保护消息来保护消息.a. 隐形墨水隐形墨水b. 字符格式的变化字符格式的变化c.图象图像图象图像 (象形文字的修改象形文字的修改)Modified Hieroglyphics, c. 1900 B.C. 密码学的第一个例子是对标准书写符号的修改密码学的第一个例子是对标准书写符号的修改example-i我去君留十载中 爱无南北与西东 万株松树青山上 洁白孤高生不同 example-ii Spartan Scytale, c. 500 B.C. 斯巴达人用于加解密的一种军事设备斯巴达人用于加解密的一种军事设备 发送者把一条羊皮螺旋形地缠在一个圆柱形发送者把一条羊皮螺旋形地缠在一个圆柱形棒上棒上思想：置换（思想：置换（permutation) Polybius Checkerboard , 205123 B.C. 明文明文:POLYBIUS 密文密文:3534315412244543 123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZexample-iii Caesar Cipher, c. 50 B.C. A B C D E F G X Y Z D E F G H I J A B C 明文明文:Caesar cipher is a shift substitution 密文密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQexample-iV Nomenclator 代码本代码本 c.1400字母、符号、单词、短语字母、符号、单词、短语 代码代码代码代码 字母、符号、单词、短语字母、符号、单词、短语应用：应用：World War IIExample -VExample Cont 网格加密法：中国网格加密法：中国 例：密文：王先生： 来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。 弟：李明 2001年11月7日 网格加密法：中国网格加密法：中国 例：密文：王先生： 来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。 弟：李明 2001年11月7日明文：情报在雨伞把中。 兽栏法：兽栏法： 明文：System 密文： ABCDEFGHIJ.K.LM.N.OP.Q.RS:T:UV:W:XY:Z:.：.密文字母表：古典实例古典实例 双轨密码：双轨密码：18611865年年例：明文：Discrete and System 密文：Dsrtadytm Iceensse加密方法： D s r t a d y t m i c e e n s s eBeale密码密码C= 115 73 24 818 37 52 49 17 31 62 657 22 7 15M= I have deposited (1) (1) When, in the course of human events, it becomes necessaryWhen, in the course of human events, it becomes necessary(11) For one people to dissolve the political bands which have (11) For one people to dissolve the political bands which have (21) Connected them with another, and to assume among the Powers(21) Connected them with another, and to assume among the Powers(31) Of the earth the separate and equal station to which (31) Of the earth the separate and equal station to which (41) The Laws of Nature and of Natures God entitle them,(41) The Laws of Nature and of Natures God entitle them,(51) A decent respect to the opinions of mankind requires that(51) A decent respect to the opinions of mankind requires that(61) They should declare the causes which impel them to the(61) They should declare the causes which impel them to the(71) separation. We hold these truths to be self-evident, that(71) separation. We hold these truths to be self-evident, that(81) All men are created equal, that they are endowed by(81) All men are created equal, that they are endowed by(91) Their Creator with certain unalienable rights, that among(91) Their Creator with certain unalienable rights, that among(99) These are Life, Liberty, and the pursuit of Happiness.(99) These 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 首先将明文串转化为数字串，按首先将明文串转化为数字串，按6个一组分段，然后模个一组分段，然后模26“加加”上上密钥字得：密钥字得：86252315211747158217218871915222182301747158224181419152491219191211747158218812419181982582215174715822418191413192522158241720使用Vigenre表可以方便地进行加密和解密。相应的密文串将是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类似,不同的只是进行模26减,而不是模26加。明文A B C D E F G H I J K L M N O P Q R S T U V W X Y ZA A B C D E F G H I J K L M N O P Q R S T U V W X Y ZB B C D E F G H I J K L M N O P Q R S T U V W X Y Z AC C D E F G H I J K L M N O P Q R S T U V W X Y Z A BD D E F G H I J K L M N O P Q R S T U V W X Y Z A B CE E F G H I J K L M N O P Q R S T U V W X Y Z A B C DF F G H I J K L M N O P Q R S T U V W X Y Z A B C D EG G H I J K L M N O P Q R S T U V W X Y Z A B C D E FH H I J K L M N O P Q R S T U V W X Y Z A B C D E F GI I J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK K L M N O P Q R S T U V W X Y Z A B C D E F G H I JL L M N O P Q R S T U V W X Y Z A B C D E F G H I J KM M N O P Q R S T U V W X Y Z A B C D E F G H I J K LN N O P Q R S T U V W X Y Z A B C D E F G H I J K L MO O P Q R S T U V W X Y Z A B C D E F G H I J K L M NP P Q R S T U V W X Y Z A B C D E F G H I J K L M N OQ Q R S T U V W X Y Z A B C D E F G H I J K L M N O PR R S T U V W X Y Z A B C D E F G H I J K L M N O P QS S T U V W X Y Z A B C D E F G H I J K L M N O P Q RT T U V W X Y Z A B C D E F G H I J K L M N O P Q R SU U V W X Y Z A B C D E F G H I J K L M N O P Q R S TV V W X Y Z A B C D E F G H I J K L M N O P Q R S T UW W X Y Z A B C D E F G H I J K L M N O P Q R S T U VX X Y Z A B C D E F G H I J K L M N O P Q R S T U V WY Y Z A B C D E F G H I J K L M N O P Q R S T U V W XZ Z A B C D E F G H I J K L M N O P Q R S T U V W X Y密钥古典密码（古典密码（7） 通过一次加密一组字母来使密码分析更加困难。通过一次加密一组字母来使密码分析更加困难。 Playfair密码：密码： Playfair密码是一个双字母组代替密码，用英国科学家Lyon Playfair的名字命名。 Playfair密码的密钥是由一个25个字母（J视为I）的55矩阵给出：HARPSICODBEFGKLMNQT UVWXYZ加密规则加密规则对于矩阵中的每一对明文字母m1m2按如 下规则加密（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 SEND 第一次世界大战期间，德国使用字典编写密码第一次世界大战期间，德国使用字典编写密码 25-3-1725-3-17 电视剧：誓言无声电视剧：誓言无声 爱情誓言：爱情誓言：584584， 13141314， 880880 19491949年之前年之前: : 古典密码古典密码（classical cryptography)classical cryptography) 密码学还不是科学密码学还不是科学, ,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段( (substitution & substitution & permutation)permutation)出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现密码学的起源和发展密码学的起源和发展-ii 1949194919751975年年: : 计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能 19491949年年ShannonShannon的的“The Communication Theory of The Communication Theory of Secret Systems” Secret Systems” 19671967年年David KahnDavid Kahn的的The CodebreakersThe Codebreakers 1971-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst FeistelHorst 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数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密密码学的起源和发展密码学的起源和发展-iii 19761976年以后年以后: : 19761976年年Diffie & HellmanDiffie & Hellman的的“New Directions “New Directions in Cryptography”in Cryptography”提出了不对称密钥密码提出了不对称密钥密码19771977年年Rivest,Shamir & AdlemanRivest,Shamir & Adleman提出了提出了RSARSA公公钥算法钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能保密通信成为可能！密码学的起源和发展密码学的起源和发展-iv 19761976年以后年以后: : 对称密钥密码算法进一步发展对称密钥密码算法进一步发展19771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“post DES”“post DES”算法算法, ,如如IDEA,RCxIDEA,RCx,CAST,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, TwofishRijndael,RC6, MARS, Twofish, Serpent, Serpent等出等出现现20012001年年RijndaelRijndael成为成为DESDES的替代者的替代者密码学的起源和发展密码学的起源和发展-v 假设破译者假设破译者Oscar是在已知密码体制的前提下来是在已知密码体制的前提下来破译破译Bob使用的密钥。这个假设称为使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：原则。最常见的破解类型如下：1.唯密文攻击：唯密文攻击：Oscar具有密文串具有密文串y.2.已知明文攻击已知明文攻击: Oscar具有明文串具有明文串x和相应的密和相应的密文文y.3.选择明文攻击：选择明文攻击：Oscar可获得对加密机的暂时可获得对加密机的暂时访问，访问， 因此他能选择明文串因此他能选择明文串x并构造出相应的并构造出相应的密文串密文串y。4.选择密文攻击选择密文攻击:Oscar可暂时接近密码机可暂时接近密码机,可选可选择密文串择密文串y，并构造出相应的明文，并构造出相应的明文x. 这一切的目的在于这一切的目的在于破译出密钥或密文破译出密钥或密文密码分析密码分析 密码破译的原则密码破译的原则: 遵循观察与经验遵循观察与经验 方法方法:采用归纳与演绎采用归纳与演绎 步骤步骤:分析、假设、推测和证实分析、假设、推测和证实 三大要素：三大要素： 语言的频率特征：语言的频率特征： e 连接特征连接特征: q u, I e x, 重复特征重复特征: th, tion , tious密码破译密码破译无条件安全（无条件安全（Unconditionally secureUnconditionally secure） 无论破译者有多少密文无论破译者有多少密文, ,他也无法解出他也无法解出对应的明文对应的明文, ,即使他解出了即使他解出了, ,他也无法验他也无法验证结果的正确性证结果的正确性. . Onetime pad Onetime pad计算上安全（计算上安全（Computationally secureComputationally secure）破译的代价超出信息本身的价值破译的代价超出信息本身的价值破译的时间超出了信息的有效期破译的时间超出了信息的有效期. .攻击方法的复杂性攻击方法的复杂性（1） 数据复杂性（2） 处理复杂性（3） 存储复杂性 算法的实现：算法的实现： 密码模式密码协议密码学数学基础密码学数学基础 熵熵-事件出现的平均不确定性事件出现的平均不确定性-一个事件平均所需的信息量一个事件平均所需的信息量 中国剩余定理（孙子算经）中国剩余定理（孙子算经）熵熵例：例：X可能在下周某天去钓鱼。可能在下周某天去钓鱼。 E=星期一星期一, ,星期二星期二, ,星期三星期三, ,星期四星期四, , 星期五星期五, ,星期六星期六, ,星期日星期日H（X）=?例：任意给定一个例：任意给定一个1-20的数，的数，猜多少次可以猜到猜多少次可以猜到该数。该数。 熵熵例：甲任意取一个不超过例：甲任意取一个不超过1010的整数，由乙来猜，但允许的整数，由乙来猜，但允许乙提乙提K K个问题，甲只回答个问题，甲只回答“是是”或者或者“非非”，问，问K K多大多大时可以确定猜到该数。时可以确定猜到该数。 解：若令猜想作为事件解：若令猜想作为事件V，V可能有可能有10种结果，假定种结果，假定这这10种结果是等概率的，种结果是等概率的，V的熵为：的熵为：H（V）= log210=3.32令事件令事件Ak=U1U2U3Uk为提问为提问k个问题，但个问题，但Ui的熵不超过的熵不超过log22=1，（因为只有，（因为只有“是是”或者或者“非非”），故），故Ak的熵的熵为不超过为不超过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个硬币中有一枚假币，用个硬币中有一枚假币，用无砝码的天平，试问要做多少次的比较，可以无砝码的天平，试问要做多少次的比较，可以找到这枚假币，且是轻还是重找到这枚假币，且是轻还是重.中国剩余定理中国剩余定理 定理：如果定理：如果n的素数因子分解式为的素数因子分解式为p1 p2 pt，则一组方程，则一组方程 (x mod pi）= ai，其中，其中i = 1,2,t，有唯一解，有唯一解x，其中，其中x小于小于n（其中某些（其中某些pi可能相等）可能相等）。 例：今有物不知其数，三三数之剩二，五五数例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？之剩三，七七数之剩二，问物几何？ x mod 3 = 2 5*7*2=70 mod 3=1 x mod 5 = 3 3*7*3=63 mod 5=3 x 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范围内有公共解范围内有公共解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日被宣布为联邦标准，允许在非保密的政府通信中使用。标准的官方描述在1977年1月15日颁布，6个月后生效。 1984年9美国总统签署145号国家安全决策令(NSDD),命令NSANSA着手发展新的加密标准,用于政府系统非机密数据和私人企事业单位. NSA宣布每隔5年重新审议DES是否继续作为联邦标准,1988年(FIPS46-1),1993年(FIPS46-2),1998年不再重新批准DES为联邦标准. NBS公开征集标准加密算法的要公开征集标准加密算法的要求求 算法必须提供高度的安全性算法必须提供高度的安全性 算法必须有详细的说明算法必须有详细的说明,并易于理解并易于理解 算法的安全性必须取决于密钥算法的安全性必须取决于密钥,不依赖于算法本身的不依赖于算法本身的保密保密 算法必须必须对所有用户都适用算法必须必须对所有用户都适用 算法必须适用于各种应用算法必须适用于各种应用 算法必须能用电子设备经济地实现算法必须能用电子设备经济地实现 算法必须使用效率高算法必须使用效率高 算法必须能被证实有效算法必须能被证实有效 算法必须是可移植的算法必须是可移植的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 Daemen和和Vincent Rijmen提交的提交的Rijndael算法作为算法作为AES。2001年夏天，年夏天，NIST颁布新的信息处理标准（颁布新的信息处理标准（FIPS），将），将Rijndael算法作为算法作为AES。加密算法概述加密算法概述AES算法与以往的基于算法与以往的基于Feistel网的密码（如网的密码（如DES）不同，算法的）不同，算法的每一步都是可逆的。每一步都是可逆的。算法的明文块长可以为算法的明文块长可以为128bit，192bit或或256bit，密钥也可以分，密钥也可以分别为别为128bit，192bit或或256bit。算法有多圈相同的运算，每一圈包括算法有多圈相同的运算，每一圈包括4个步骤：个步骤： 非线性代替（S-盒） 行循环左移（ShiftRow） 列混合变换（MixColum） 与扩展密钥相异或每一圈的子密钥从扩展密钥中取出每一圈的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变