【精品】密码学基础知识精品ppt课件.ppt

《【精品】密码学基础知识精品ppt课件.ppt》由会员分享，可在线阅读，更多相关《【精品】密码学基础知识精品ppt课件.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、密码学基础知识密码学基础知识密码学基础知识密码学概述密码学概述传统的密码学传统的密码学对称密码对称密码公钥密码公钥密码序列密码序列密码密码学概述密码学概述通信保密通信保密通信保密通信保密（COMSECCOMSEC）：）：60-7060-70年代年代 信息保密信息保密计算机安全（计算机安全（计算机安全（计算机安全（COMPUSEC COMPUSEC COMPUSEC COMPUSEC）:60:60:60:60年代年代年代年代 机密性、访问控制、认证机密性、访问控制、认证机密性、访问控制、认证机密性、访问控制、认证,TCSECTCSECTCSECTCSEC标准标准标准标准信息安全信息安全信息安全信

2、息安全（INFOSECINFOSEC）：）：80-9080-90年代年代 机密性、完整性、可用性、不可否认性机密性、完整性、可用性、不可否认性 等等信息保障信息保障信息保障信息保障（IAIA）：）：9090年代年代-至今至今信息安全发展的四个阶段年代年代年代年代通信安全发展通信安全发展通信安全发展通信安全发展时期时期时期时期从有从有从有从有人类人类人类人类以来以来以来以来6060年年年年代中代中代中代中期期期期计算机安全发计算机安全发计算机安全发计算机安全发展时期展时期展时期展时期8080年年年年代中代中代中代中期期期期信息安全发展信息安全发展信息安全发展信息安全发展时期时期时期时期9090年

3、年年年代中代中代中代中期期期期信息安全保障信息安全保障信息安全保障信息安全保障发展时期发展时期发展时期发展时期 安安安安全全全全保保保保障障障障能能能能力力力力基本的通讯模型基本的通讯模型通信的保密模型通信的保密模型通信安全通信安全-60年代（年代（COMSEC）发方发方收方收方信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议发方发方收方收方敌人敌人信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议密码密码安全需求的多样性安全需求的多样性保密性保密性一致性一致性可用性可用性可靠性可靠性可认证，真实性可认证，真实性责任定位，审计性责任定位，审计性高性能高性能 实用性

4、实用性占有权占有权如何保证这些需求？美国人提出的概念:Information Assurance保护保护保护保护（P Protect）检测检测检测检测（D Detect）反应反应反应反应（R React）恢复恢复恢复恢复（R Restore）保护保护Protect检测检测Detect反应反应React恢复恢复Restore信息保障电子邮件电子邮件 自动提款机自动提款机电话卡电话卡:IP卡、卡、201电话卡电话卡银行取钱银行取钱信用卡购物信用卡购物密码从军事走向生活密码从军事走向生活密码学密码学(Cryptology):是研究信息系统安全保密是研究信息系统安全保密的科学的科学.密码编码学密码编码

5、学(Cryptography):主要研究对信息进主要研究对信息进行编码行编码,实现对信息的隐蔽实现对信息的隐蔽.密码分析学密码分析学(Cryptanalytics):主要研究加密消息主要研究加密消息的破译或消息的伪造的破译或消息的伪造.基本概念基本概念量子密码量子密码(单量子不可复制定理单量子不可复制定理)DNADNA密码密码化学密码化学密码密码新技术密码新技术消息被称为消息被称为明文明文(Plaintext)(Plaintext)。用某种方法伪装消息以。用某种方法伪装消息以隐藏它的内容的过程称为隐藏它的内容的过程称为加密加密(Encrtption)(Encrtption)，被加密，被加密的消

6、息称为的消息称为密文密文(Ciphertext)(Ciphertext)，而把密文转变为明文，而把密文转变为明文的过程称为的过程称为解密解密(Decryption)(Decryption)。对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员密码员(Cryptographer).(Cryptographer).密码算法密码算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密和解是用于加密和解密的数学函数。密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作密码员对明文进行加密操作时所采用的一组规则称

7、作加密算法加密算法(Encryption Algorithm).(Encryption Algorithm).所传送消息的预定对象称为所传送消息的预定对象称为接收者接收者(Receiver).(Receiver).接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法解密算法(Decryption Algorithm).(Decryption Algorithm).加解密过程示意图加解密过程示意图加密和解密算法的操作通常都是在一组密钥的加密和解密算法的操作通常都是在一组密钥的控制下进行的控制下进行的,分别称为分别称为加密密钥加密密钥(Encryption Key)和和

8、解密密钥解密密钥(Decryption Key).明文明文密文加密算法解密算法密钥密钥 密码学的目的密码学的目的：Alice和和Bob两个人在不安全的信道上进两个人在不安全的信道上进行通信，而破译者行通信，而破译者Oscar不能理解他们通信的内容。不能理解他们通信的内容。加密通信的模型加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk密码体制：密码体制：它是一个五元组（它是一个五元组（P,C,K,E,D)满足条件：满足条件：（1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间）（3

9、）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间）*（4）任意）任意k K,有一个加密算法有一个加密算法 和相应的解密算法和相应的解密算法 ，使得，使得 和和 分别为加密解密函数，满分别为加密解密函数，满足足dk(ek(x)=x,这里这里 x P。密码体制（系统）密码体制（系统）按照保密的内容分按照保密的内容分:受限制的（受限制的（restricted)算法算法:算法的保密性基于算法的保密性基于保持算法的秘密。保持算法的秘密。基于密钥（基于密钥（key-based)的算法的算法:算法的保密性基算法的保密性基于对密钥的保密。于对密钥的保密。-现代密码理论现代密码

10、理论密码算法分类密码算法分类-i基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：对称密码算法（对称密码算法（symmetric cipher)：又称：又称传统密码算法传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称或实质上等同，即从一个易于推出另一个。又称秘密秘密密钥算法密钥算法或或单密钥算法单密钥算法。非对称密钥算法（非对称密钥算法（asymmetric cipher):加密密钥和解密加密密钥和解密密钥不相同，从一个很难推出另一个。又称密钥不相同，从一个很难推出另

11、一个。又称公开密钥公开密钥算法（算法（public-key cipher)。公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密,而用另一个进行解而用另一个进行解密密.其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)，简称公钥，简称公钥.解密密钥必须保密解密密钥必须保密,又称私人密钥又称私人密钥（private key)私钥私钥.简称简称私钥私钥。密码算法分类密码算法分类-ii按照明文的处理方法：按照明文的处理方法：分组密码（分组密码（block cipher):将明文分成固定长度将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出

12、的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。也是固定长度的密文。流密码（流密码（stream cipher):又称又称序列密码序列密码.序列密序列密码每次加密一位或一字节的明文，也可以称为码每次加密一位或一字节的明文，也可以称为流密码。流密码。序列密码是手工和机械密码时代的主流序列密码是手工和机械密码时代的主流密码算法分类密码算法分类-iii对称密钥密码又可分为：对称密钥密码又可分为：分组密码分组密码 每次对一块数据加密每次对一块数据加密 多数网络加密应用多数网络加密应用 DES,IDEA,RC6,RijndaelDES,IDEA,RC6,Rijndael流密码流密码 每次对一

13、位或一字节加密每次对一位或一字节加密 手机手机 One-time One-time padding,Vigenre,Vernampadding,Vigenre,Vernam密码算法分类密码算法分类-iv公开密钥密码公开密钥密码:大部分是分组密码，只有概率密码体制属于大部分是分组密码，只有概率密码体制属于流密码流密码 每次对一块数据加密每次对一块数据加密 数字签名数字签名,身份认证身份认证 RSA,ECC,ElGamalRSA,ECC,ElGamal 加密解密速度慢加密解密速度慢密码算法分类密码算法分类-v三个阶段：三个阶段：19491949年之前年之前 密码学是一门艺术密码学是一门艺术1949

14、194919751975年年 密码学成为科学密码学成为科学19761976年以后年以后 密码学的新方向密码学的新方向公钥密码学公钥密码学密码学的起源和发展密码学的起源和发展-i密码学的起源密码学的起源隐写术隐写术(steganography):通过隐藏消息的通过隐藏消息的存在存在来保护消息来保护消息.a.隐形墨水隐形墨水b.字符格式的变化字符格式的变化c.图象图像图象图像 (象形文字的修改象形文字的修改)Modified Hieroglyphics,c.1900 B.C.密码学的第一个例子是对标准书写符号的修改密码学的第一个例子是对标准书写符号的修改example-i我去君留十载中爱无南北与西

15、东万株松树青山上洁白孤高生不同example-iiSpartan Scytale,c.500 B.C.斯巴达人用于加解密的一种军事设备斯巴达人用于加解密的一种军事设备 发送者把一条羊皮螺旋形地缠在一个圆柱形棒发送者把一条羊皮螺旋形地缠在一个圆柱形棒上上思想：置换（思想：置换（permutation)Polybius Checkerboard,205123 B.C.明文明文:POLYBIUS密文密文:3534315412244543 123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZexample-iiiCaesar Cipher,c.50 B.C.A B C D E F

16、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-iVNomenclator 代码本代码本 c.1400字母、符号、单词、短语字母、符号、单词、短语 代码代码代码代码 字母、符号、单词、短语字母、符号、单词、短语应用：应用：World War IIExample-VExample Cont网格加密法：中国网格加密法：中国例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞

17、一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日网格加密法：中国网格加密法：中国例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日明文：情报在雨伞把中。兽栏法：兽栏法：明文：System密文：ABCDEFGHIJ.K.LM.N.OP.Q.RS:T:UV:W:XY:Z:.：.密文字母表：古典实例古典实例双轨密码：双轨密码：18611865年年例：明文：DiscreteandSystem密文：DsrtadytmIceensse加密方法：DsrtadytmiceensseBeale密码密码

18、C=115732481837524917316265722715M=Ihavedeposited(1)When,in the course of human events,it becomes necessary(1)When,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

19、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

20、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 t

21、ruths 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 r

22、ights,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.例如：明文

23、例如：明文INTELLIGENT用密钥用密钥PLAY加密为：加密为：MINTE LLIG ENT KPLAY PLAY PLA Ek(M)XYTC AMIE TYT例 设设m6，且密钥字是，且密钥字是CIPHER,这相应于密钥。假定明文串是这相应于密钥。假定明文串是 this cryptosystem is not secure 首先将明文串转化为数字串，按首先将明文串转化为数字串，按6个一组分段，然后模个一组分段，然后模26“加加”上密上密钥字得：钥字得：使用Vigenre表可以方便地进行加密和解密。相应的密文串将是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类

24、似,不同的只是进行模26减,而不是模26加。古典密码（古典密码（7）通过一次加密一组字母来使密码分析更加困难。通过一次加密一组字母来使密码分析更加困难。Playfair密码：密码：Playfair密码是一个双字母组代替密码，用英国科学家LyonPlayfair的名字命名。Playfair密码的密钥是由一个25个字母（J视为I）的55矩阵给出：HARPSICODBEFGKLMNQTUVWXYZ加密规则加密规则对于矩阵中的每一对明文字母m1m2按如下规则加密（m1m2对应的密文为c1c2）若m1和m2在同一行，则c1和c2分别是m1和m2右边的字母，其中第一列认为是第五列的右边；若m1和m2在同一

25、列，则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-17 25-3-17电视剧：誓

26、言无声电视剧：誓言无声爱情誓言：爱情誓言：584584，1314 1314，880 88019491949年之前年之前:古典密码古典密码（classical cryptography)classical cryptography)密码学还不是科学密码学还不是科学,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段(substitution&(substitution&permutation)permutation)出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现密码学的起源和发展密码学的起源和发展-ii

27、1949194919751975年年:计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能19491949年年ShannonShannon的的“The Communication Theory of The Communication Theory of Secret Systems”Secret Systems”19671967年年David KahnDavid Kahn的的The The CodebreakersCodebreakers1971-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst Horst FeistelFeist

28、el等的几等的几篇技术报告篇技术报告Smith,J.L.,TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971Smith,J.L.,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.,CryptographyandComputerPrivacy,May1973数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密密码学的起源和发展密码学的起源和发展-iii19761976年以后年以后:1

29、9761976年年DiffieDiffie&HellmanHellman的的“New Directions New Directions in Cryptography”in Cryptography”提出了不对称密钥密码提出了不对称密钥密码19771977年年Rivest,ShamirRivest,Shamir&AdlemanAdleman提出了提出了RSARSA公公钥算法钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能保密通信成为可能！密码学的起源和发展密码学的起

30、源和发展-iv19761976年以后年以后:对称密钥密码算法进一步发展对称密钥密码算法进一步发展19771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“post DES”“post DES”算法算法,如如IDEA,RCx,CASTIDEA,RCx,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6,MARS,Twofish,SerpentRijndael,RC6,MARS,Twofish,Serpent等出等出现现20012001年年RijndaelRijndael成为成为DESDES的替代者的替代者

31、密码学的起源和发展密码学的起源和发展-v假设破译者假设破译者Oscar是在已知密码体制的前提下来是在已知密码体制的前提下来破译破译Bob使用的密钥。这个假设称为使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：原则。最常见的破解类型如下：1.唯密文攻击：唯密文攻击：Oscar具有密文串具有密文串y.2.已知明文攻击已知明文攻击:Oscar具有明文串具有明文串x和相应的密和相应的密文文y.3.选择明文攻击：选择明文攻击：Oscar可获得对加密机的暂时可获得对加密机的暂时访问，访问，因此他能选择明文串因此他能选择明文串x并构造出相应的密并构造出相应的密文串文串y。4.选择密文攻

32、击选择密文攻击:Oscar可暂时接近密码机可暂时接近密码机,可选可选择密文串择密文串y，并构造出相应的明文，并构造出相应的明文x.这一切的目的在于这一切的目的在于破译出密钥或密文破译出密钥或密文密码分析密码分析密码破译的原则密码破译的原则:遵循观察与经验遵循观察与经验方法方法:采用归纳与演绎采用归纳与演绎步骤步骤:分析、假设、推测和证实分析、假设、推测和证实三大要素：三大要素：语言的频率特征：语言的频率特征：e连接特征连接特征:q u,I e x,重复特征重复特征:th,tion,tious密码破译密码破译无条件安全（无条件安全（Unconditionally Unconditionally

33、securesecure）无论破译者有多少密文无论破译者有多少密文,他也无法解出他也无法解出对应的明文对应的明文,即使他解出了即使他解出了,他也无法验他也无法验证结果的正确性证结果的正确性.Onetime pad Onetime pad计算上安全（计算上安全（Computationally Computationally securesecure）破译的代价超出信息本身的价值破译的代价超出信息本身的价值破译的时间超出了信息的有效期破译的时间超出了信息的有效期.攻击方法的复杂性攻击方法的复杂性（1）数据复杂性（2）处理复杂性（3）存储复杂性 算法的实现：算法的实现：密码模式密码协议密码学数学基础

34、密码学数学基础熵熵-事件出现的平均不确定性事件出现的平均不确定性-一个事件平均所需的信息量一个事件平均所需的信息量中国剩余定理（孙子算经）中国剩余定理（孙子算经）熵熵例：例：X可能在下周某天去钓鱼。可能在下周某天去钓鱼。E=星期一星期一,星期二星期二,星期三星期三,星期四星期四,星期五星期五,星期六星期六,星期日星期日H（X）=?例：任意给定一个例：任意给定一个1-20的数，的数，猜多少次可以猜到猜多少次可以猜到该数。该数。熵熵例例：甲甲任任意意取取一一个个不不超超过过1010的的整整数数，由由乙乙来来猜猜，但但允允许许乙乙提提K K个个问问题题，甲甲只只回回答答“是是”或或者者“非非”，问问

35、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个重量完全一样，有一个重量完

36、全一样，有一个较轻的伪币，用无砝码的天平，试问要做多少次的比较，可以个较轻的伪币，用无砝码的天平，试问要做多少次的比较，可以找到这枚伪币？找到这枚伪币？解：事件解：事件V为找出伪币，可能有为找出伪币，可能有25个结论，他们是等概率，故：个结论，他们是等概率，故：H（V）=log225，事事件件U为为天天平平称称的的结结果果，可可能能有有3种种情情况况：1.左左右右平平衡衡；2.左左边边重重；3.右边重；故：右边重；故：H（U）=log23令令Ak=U1U2U3Uk为连续用为连续用k次天平的事件，次天平的事件，klog23 log225 k （log225）/log23=2.93故故 k最少为最

37、少为3次次熵熵问题修改为：如果问题修改为：如果25个硬币中有一枚假币，用个硬币中有一枚假币，用无砝码的天平，试问要做多少次的比较，可以无砝码的天平，试问要做多少次的比较，可以找到这枚假币，且是轻还是重找到这枚假币，且是轻还是重.中国剩余定理中国剩余定理定理：如果定理：如果n的素数因子分解式为的素数因子分解式为p1 p2 pt，则一组方程，则一组方程(x mod pi）=ai，其中，其中i=1,2,t，有唯一解，有唯一解x，其中，其中x小于小于n（其中某些（其中某些pi可能相等）。可能相等）。例：今有物不知其数，三三数之剩二，五五数例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问

38、物几何？之剩三，七七数之剩二，问物几何？xmod3=25*7*2=70mod3=1xmod5=33*7*3=63mod5=3xmod7=23*5*2=30mod7=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开

39、始一项保护计算机和通信数据的项目，其中一部分是要开发一个单独的标准保密算法。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宣布每隔

40、5年重新审议DES是否继续作为联邦标准,1988年(FIPS46-1),1993年(FIPS46-2),1998年不再重新批准DES为联邦标准.NBS公开征集标准加密算法的要求公开征集标准加密算法的要求算法必须提供高度的安全性算法必须提供高度的安全性算法必须有详细的说明算法必须有详细的说明,并易于理解并易于理解算法的安全性必须取决于密钥算法的安全性必须取决于密钥,不依赖于算法本身的保不依赖于算法本身的保密密算法必须必须对所有用户都适用算法必须必须对所有用户都适用算法必须适用于各种应用算法必须适用于各种应用算法必须能用电子设备经济地实现算法必须能用电子设备经济地实现算法必须使用效率高算法必须使用

41、效率高算法必须能被证实有效算法必须能被证实有效算法必须是可移植的算法必须是可移植的DES加加密密算算法法高级数据加密标准高级数据加密标准AES背景背景AES加密算法描述加密算法描述算法评价算法评价背景背景现代计算机速度的迅速提高，使得只有现代计算机速度的迅速提高，使得只有56bit密钥的密钥的DES算法的算法的安全性面临着极大的挑战。安全性面临着极大的挑战。1997年，年，NIST公开征求公开征求AES（Advanced Encryption Standard）作为作为2001年以后的数据加密标准。年以后的数据加密标准。1998年年8月，月，AES召开第一次候选会，确定召开第一次候选会，确定1

42、5个算法入围。个算法入围。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网的密码（如网的密码（如D

43、ES）不同，算法的）不同，算法的每一步都是可逆的。每一步都是可逆的。算法的明文块长可以为算法的明文块长可以为128bit，192bit或或256bit，密钥也可以分，密钥也可以分别为别为128bit，192bit或或256bit。算法有多圈相同的运算，每一圈包括算法有多圈相同的运算，每一圈包括4个步骤：个步骤：非线性代替（S-盒）行循环左移（ShiftRow）列混合变换（MixColum）与扩展密钥相异或每一圈的子密钥从扩展密钥中取出每一圈的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变换和循环左移密钥扩展过程同时应用了非线性变换和循环左移算法定义的所有运算都是在有限域算法定义的所有运算

44、都是在有限域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

45、，满满足足gcd（e,(N)）=1(即即e与与(N)互素互素)4.计算计算d，使得，使得ed 1 mod (N)公钥公钥=e,N；私钥；私钥=d,NRSA算法描述算法描述加密：加密：C=Me mod N,where 0MN解密：解密：M=Cd mod N 公钥为（公钥为（e，N），），私钥为（私钥为（d，N）安全性公钥公钥=e,N；私钥；私钥=d,N安全性在于由e和N来计算d是不可行的ed1mod(N)如果知道e和(N)，则容易求得d。那困难在哪里？(N)N)难求难求难求难求!(N)=？N=p*q(N)=(p-1)(q-1)最终的困难在于很难将N分解为两个素数之积。椭圆曲线密码介绍椭圆曲线密码

46、介绍1985年年Miller,Koblitz 独立提出独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点曲线上的点连同无穷远点O的集合的集合运算定义：运算定义：若曲线三点在一条直线上若曲线三点在一条直线上,则其和为则其和为OO用作加法的单位：用作加法的单位：O=-O;P+O=P一条竖直线交一条竖直线交X轴两点轴两点P1、P2，则，则P1+P2+O=O，于是于是P1=-P2如果两个点如果两个点Q和和R的的X轴不同，则画一连线，得到第三点轴不同，则画一连线，得到第三点P1，则，则Q+R+P1=O，即，即Q+R=-P12倍，一个点倍，一个点Q的两倍是，找到它的切线与曲线的另一个

47、的两倍是，找到它的切线与曲线的另一个交点交点S，于是于是Q+Q=2Q=-S 椭圆曲线密码示意图椭圆曲线密码示意图 有限域上椭圆曲线有限域上椭圆曲线有限域上椭圆曲线有限域上椭圆曲线y2 x3+ax+b mod p p是奇素数是奇素数,且且4a3+27b2 0 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)也

48、在也在Ep(a,b)中中如果如果P=(x1,y1)，Q=(x2,y2)，则则 P+Q=(x3,y3)为为x3=2-x1-x2(mod p)y3=(x1-x3)-y1(mod p)其中，其中，如果如果P Q，则则 =(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?