CISP0201密码学基础

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,密码学基础,课程内容,2,密码技术,知识体,知识域,知识子域,密码学基础,非对称密码算法,密码学基础概念,对称密码算法,哈,希函数和数字签名,知识子域：密码学基础概念,了解密码学的发展阶段及各阶段特点,理解密码通信模型，理解密码学加密、解密、算法、明文、密文、密钥、密码编码学和密码分析学等概念,了解科克霍夫原则和影响密码系统的安全性的基本因素：复杂程度、密钥长度,掌握密码体制的分类和特点,理解,密钥,生命周期概念和密钥管理作用，了解密钥产生、分配、使用、更换和注销等过程的管理特点,3,密码学发展,第一个阶段是从古代到,19,世纪末,古典密码（,classical cryptography),第二个阶段从,20,世纪初到,1949,年,近代密码,第三个阶段从,C.E.Shannon,（,香,农） 于,1949,年发表的划时代论文“,The Communication Theory of Secret Systems,”开始,现代密码,第四个阶段从,1976,年,W. Diffie,和,M. Hellman,发表论文“,New Directions in Cryptography,”开始,公钥密码,4,古典,密码学,古典密码体制的安全性在于保持算法本身的保密性，受到算法限制。,不适合大规模生产,不适合较大的或者人员变动较大的组织,用户无法了解算法的安全性,古典密码主要有以下几种：,代替密码（,Substitution Cipher,）,置换密码（,Transposition Cipher,）,代替密码与置换密码的组合,5,代替密码,Vs.,置换密码,凯撒,密码,6,斯巴达,人,“,天书,”,密码,古典密码学分类,7,代替密码,置换密码,古典密码学,多字母代替,单字母代替,单表代替密码,多表代替密码,（流密码）,（分组密码）,Substitution cipher,Polygram Substitution cipher,Transposition Cipher,Monoalphabetic Substitution cipher,Ployalphabetic Substitution cipher,Stream cipher,Block cipher,举例：密码广播,代替？置换？,测试：余则成,接受广播呼叫所使用的密码本是（）,A,红楼梦,B,朱子家训,C,蝴蝶梦,D,康熙字典,8,近代密码学,20,世纪初到,1949,年：,主要标志是机械密码,/,机电密码，用机电代替手工。,近代密码体制是用机械或电动机械实现的，最著名的就是,转轮机（,Rotor Machine,）,。,9,转轮机,Germany: ENIGMA,（,1919,）,转轮密码机,ENIGMA,，由,Arthur Scherbius,于,1919,年发明,。在二次世界大战期间, Enigma,曾作为德国陆、海、空三军最高级,密码机。,10,转轮机,UK:TYPEX,/,US:M-209,英国的,TYPEX,打字密码机,德,3,轮,ENIGMA,的改进型,在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。,11,M-209,是哈格林对,C-36,改进后的产品，由,Smith-Corna,负责为美国陆军生产,一次一密乱码本（,1917,）,12,发明者：,Major Joseph Mauborgne,和,AT&T,公司的,Gilbert Vernam,在,1917,年发明。,应用于：,华盛顿,-,莫斯科“热线”,俄罗斯间谍,CIA,报文,s e c r e t,18 5 3 17 5 19,OTP + 15 8 1 12 19 5,7 13 4 3 24 24,g m d c x x,OTP,（,one-time pad,）从理论上是不可破的：,不重复使用乱码本（,VENONA,）,使用不可预知的随机数（物理源，如放射性衰减）,现代密码学,1949,1975,年：,1949,年,，,Shannon,的论文“,The Communication Theory of Secret Systems”,。,1967,年,，,David Kahn,的专著,The Code breakers,。,1971,年,1973,年,，,IBM Watson,实验室,的,Horst Feistel,等人发表的几篇技术报告。,1974,年,，,IBM,提交了算法,LUCIFER,，后来成为了,DES,。,新特点：数据的安全基于密钥而不是算法的保密。,13,Shannon,公钥密码学,1976,年以后：,1976,年,，,Diffie & Hellman,的“,New Directions in Cryptography”,提出了非对称密钥密码。,1977年,，,Rivest,Shamir & Adleman,提出了,RSA,公钥算法。,90,年代,，,逐步出现椭圆曲线等其他公钥算法。,公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！,14,Martin-Hellman,Whitfield_Diffie,什么是密码学,密码学基本概念,密码体制分类,密钥管理,15,密码编码学和密码分析学,密码通信模型,明文和密文,加密和解密,密码算法,16,密码学基本概念,密码学,17,密码学（,Cryptology,）,研究信息系统安全保密的科学。,由两个相互对立、相互斗争，而且又相辅相成、相互促进的分支科学所组成的，分别称为,密码编码学（,Cryptography,）,和,密码分析学（,Cryptanalysis,）,。,密码编码学,Vs.,密码分析学,18,密码编码学（,Cryptography,）,主要研究对信息进行编码，实现对信息的隐蔽。,密码分析学（,Cryptanalysis,）,主要研究加密消息的破译或消息的伪造。,密码编码学,（,1,）,密码编码学,是密码学的一个分支，研究与信息安全（例如：机密性、完整性、可鉴别性）有关的数学技术。,（,2,）,密码编码学,是包含数据变换的原理、工具和方法的一门学科，这种数据变换的目的是为了隐藏数据的信息内容，阻止对数据的篡改以及防止未经认可使用数据。,（,3,）,密码编码学,是论述使明文变得不可懂的密文，以及把已加密的消息变换成可懂形式的艺术和技巧。,19,密码分析学,（,1,）,密码分析学,是密码学的一个分支，它与另一个分支学科,密码编码学是两个相互对立、相互依存、相辅相成、相互促进的学科。,（,2,）,密码分析学,是企图挫败编码技术以及更一般说来的信息安全服务的数学技术学科。,（,3,）,密码分析学,是对密码体制、密码体制的输入输出关系进行分析，以便推出机密变量、包括明文在内的敏感数据。有时又称作,密码破译学,（,code breaking,）,20,密码通信模型,21,明文,vs.,密文,明文(,Plaintext),：,原始,消息,，,被隐蔽消息，未经加密的消息。,密文(,Ciphertext),或,密报(,Cryptogram),：,明文经密码变换而成的一种隐蔽形式。,加密员,或,密码员(,Cryptographer),：,对明文进行加密操作的人员。,22,加密,vs.,解密,加密（,Encryption,）,：将明文变换为密文的过程。,把可懂的语言变换成（人类,/,机器）不可懂的语言。,解密（,Decryption,）,：由密文恢复出原明文的过程。,加密,的逆,过程,即,把,不可懂的语言变换成可懂的语言。,23,加密算法,密钥,密文,明文,解密算法,密钥,密文,明文,加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为,加密密钥,(Encryption Key),和,解密密钥,(Decryption Key),。,密码算法,密码算法（,Cryptography Algorithm,）,：用于加密和解密操作的数学函数。,加密算法（,Encryption Algorithm,）,：发送者对明文进行加密操作时所采用的一组规则。,解密算法（,Decryption Algorithm,）,：接收者对密文进行解密操作时所采用的一组规则。,24,科克霍夫原则,Auguste Kerckhoff,在,1883,年发表了著作，探讨寻找一种新的、满足电报通信要求的密码编码体制。他认为，密码算法应该对外公开，仅需对密钥进行保密；如果一个密码系统需要保密的越多，可能的弱点也越多。,这种观点对于密码研究者和私营部门来说已经是一种常识。但同时，世界上大部分政府,、军事,部门都会使用,不对外,公开的算法。,25,科克霍夫,假设,：密码分析者知道双方使用的密码系统，包括明文的统计特性、加解密体制等，唯一不知道的是密钥。,在设计一个密码系统时，目标是在,科克霍夫原则,的前提下实现安全 。,密码算法安全性,密钥长度越长，加密数据越不容易被非法解密,26,摘自,应用密码学,，,P113,Bruce Schneier,公开密钥长度建议值,密码体制,所谓密码体制，是指由如下五部分组成的系统：,1,）明文集合,P,；,2,）密文集合,C,；,3,）密钥集合,K,；,4,）加密变换集合,E,及加密算法,e,；,5,）解密变换结合,D,及解密算法,d,。,e,k,: P-,C,和,d,k,:C-P,分别,为加密解密函数满足：,d,k,(,e,k,(m)=,m,这里,m,P,。,27,密码体制分类,（,1,）受限制的算法,vs.,基于密钥的算法,（,2,）对称密码,vs.,非对称密码,（,3,）分组密码,vs.,流密码,（,4,）代替密码,vs.,置换密码,28,受限制的算法,vs.,基于密钥的算法,受限制的（,restricted,）算法,：算法的保密性基于保持算法的秘密。,基于密钥（,key-based,）的算法,：算法的保密性基于对密钥的保密。,29,对称密码算法,vs.,非对称密码算法,对称密码算法（,Symmetric cipher,）,：加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称,传统密码算法（,Conventional cipher),、,秘密密钥算法,或,单密钥算法,。,DES,、,3DES,、,IDEA,、,AES,非对称密码算法（,Asymmetric cipher,）,：加密密钥和解密密钥不同，从一个很难推出另一个。又叫,公钥密码算法（,Public-key cipher),。其中,，,对外公开的密钥，称为,公开密钥（,public key),，简称,公钥,；必须保密的密钥，称为,私有密钥（,private key),，简称,私钥,。,RSA,、,ECC,、,ElGamal,30,非对称密码算法,上述运算中，,23,和7作为两个密钥，公开一个，另一个作为私钥即可。,例如：公钥为,7,，私钥为,23,，则即使攻击者知道7、187和密文11，但如果他不知道私钥,23,，那么他无论如何也算不出明文,88,。,数学是多么奇妙啊！,31,分组密码,vs.,流密码,分组密码（,Block cipher,）,：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。,DES,、,IDEA,、,RC2,、,RC5,序列密码（,Stream cipher,）,：又称,流密码,，序列密码每次加密一位或一字节的明文。,One-time padding,、,Vigenre,、,Vernam,32,分组密码模型,分组密码,是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为,n,的组（可看成长度为,n,的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。,33,流密码模型,34,代替密码,Vs.,置换密码,代替密码（,Substitution Cipher,）,：,就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。,置换密码（,Transposition Cipher,）,：明文的字母保持相同，但顺序被打乱了。,35,密钥管理,密钥管理：在,一种安全策略指导下密钥的产生、 存储、分配、删除、归档及,应用。,对称,密码体制和公钥,密码体制的密钥管理策略各有不同。,目的：,保护密钥不被泄露；,保护密钥不被非授权,使用。,36,密钥重要性：,所有,的密码技术都依赖于,密钥,科克霍夫,原则,:,安全性,的关键点,密钥生命周期,密钥生存周期：,授权使用该密钥的,周期,。,主要,阶段：,产生,、登记、存储、分发、注入、应用、更换和,销毁,。,原因：,1,限制密钥使用时间,时间分割,2,限制产生密文数量,数量分割,3,限制密码分析攻击的有效时间,4,降低已泄露密钥所造成的损失,37,所有密钥都有生命周期。,密钥的产生,在,安全环境中产生,密钥。,密钥长度,安全性考虑。,系统成本、计算开销考虑。,长度的选择与具体的应用有关，如加密数据的重要性、保密期限长短、可能破译者的计算能力等。,密钥产生的方式,集中式,分散式,38,密钥管理的其他阶段,密钥使用,注意内存的密钥泄露。私钥不出硬件设备（密码机、,USB Key,）。,不同用途使用不同的密钥。,密钥存储,硬盘存储或专用硬件存储，现更多存储在专用硬件中。,密钥更新,定期或不定期更换密钥。,从旧的密钥生成新的密钥,从新分配新的密钥。,39,密钥管理的其他阶段,密钥备份,可信第三方,托管,信赖问题。,智能卡或专用硬件存储,审计问题。,分片保管,恶意收集恢复。,密钥撤销,不再使用或怀疑泄露的密钥需要撤销。,声明撤销。,密钥销毁,物理上彻底粉碎,。,清除密钥的使用踪迹。,40,密码协议概念,协议,协议指的是双方或多方通过一系列规定的,步骤来,完成某项任务,。,协议的含义,至少需要两个参与者,通过,执行协议必须完成某项,任务，协议是完整的,有序,的过程，每,一步骤,必须依次,执行,协议每个步骤是明确的,41,密码协议概念,密码协议,使用密码的具有安全性功能的协议称为安全协议或密码,协议,举例,密钥分配,协议,密钥协商协议,实体鉴别,协议,抛硬币游戏,盲签名协议,秘密共享协议,42,算法,协议,信息安全,Diffie-Hellman,密钥交换算法,43,公开参数：,q,是一个素数,，,a, q,a,是,q,的一个,原根,.,选择一个私有的 ，,满足：,计算公开的 ：,选择一个私有的,满足：,计算公开的 ：,计算会话密钥,计算会话密钥,E,K,(m),Alice,Bob,第一个发表的公开密钥算法（,1976,）,用于通信双方安全地协商一个会话密钥,基于离散对数计算的困难性，主要是模幂运算：,a,p,mod n,小结,古典密码,近代密码,现代密码,密码学基本概念,密码体制分类,密钥管理,密码协议,44,对称,密码算法,理解,对称分组加密算法的优缺点和应用场合,理解,DES,、,3DES,、,AES,、,IDEA,的特点和历史背景,了解,DES,、,3DES,算法的工作原理,45,对称分组加密通信模型,加密目的,：,Alice,和,Bob,在不安全的信道上进行通信，而破译者,Oscar,不能理解他们通信的内容。,46,Alice,加密机,解密机,Bob,安全信道,密钥源,Oscar,明文,x,密文,y,密钥,k,明文,x,密钥,k,典型算法,DES,、,3DES,、,AES,、,IDEA,RC5,、,Twofish,、,CAST-256,、,MARS,数据加密标准（,DES,）,DES,是一种对称密钥算法，密钥长度为,56bits,（加上奇偶校验，通常写成,64bits,）。,分组加密算法，,64 bits,为一个分组。,基本思想：,混乱,（,Confusion,）,扩散,（,Diffusion,）,使用标准的算术运算和逻辑运算。,47,扩散,vs.,混乱,扩散（,Diffusion,）,：将每一位明文数字的影响尽可能地散布到多个输出密文数字中去，以更隐蔽明文数字的统计特性。,混乱（,Confusion,）,：使得密文的统计特性与明文、密钥之间的关系尽量复杂化。,Shannon,称：在理想密码系统中，密文的所有统计特性都与所使用的密钥独立。,48,DES,征集,1973,年,5,月,15,日，,NBS,开始公开征集标准加密算法，并公布了它的设计要求,:,(1),算法必须提供高度的安全性,(2),算法必须有详细的说明，并易于理解,(3),算法的安全性取决于密钥，不依赖于算法,(4),算法适用于所有用户,(5),算法适用于不同应用场合,(6),算法必须高效、经济,(7),算法必须能被证实有效,(8),算法必须是可出口的,49,DES,的产生和应用,1974,年,8,月，,NBS,第二次征集，,IBM,提交,LUCIFER,算法,发明人,：,IBM,公司,W. Tuchman,和,C.,Meyer,，（,1971-1972,）,基 础,：,1967,年美国,Horst Feistel,提出的理论,1976,年,11,月，采纳为联邦标准,批准用于,非军事场合的各种政府机构,。,1977,年,1,月,15,日，“数据加密标准”,FIPS PUB 46,发布。,1979,年，美国银行协会批准使用,DES,。,1980,年,，,ANSI,同意,DES,作为,私人,使用的标准，称之为,DEA,（,ANSI X.392,）,1983,年,，,ISO,同意,将,DES,作为国际标准，称之为,DEA-1,1998,年,12,月以后，美国政府不再将,DES,作为联邦加密标准,50,DES,加密过程,首先把明文分成以,64 bit,为单位的块,m,，对于每个,m,执行如下操作,DES(m)=IP,-1, T,16, T,15,. T,2, T,1, IP(m),IP,，,IP,-1,：初始置换,16,轮迭代,子密钥生成,51,DES,算法流程,52,输入,64,比特明文数据,初始置换,IP,在密钥控制下,16,轮迭代,初始逆置换,IP,-1,输出,64,比特密文数据,交换左右,32,比特,明文,IP,L0,R0,f,R1,L0 f,L1,R0,K,1,f,R2,L1 f,L2,R1,K,2,f,R16,L15 f,L16,R15,K,16,IP,1,密文,L15,R15,Initial Permutation,DES,解密过程,DES,解密过程与加密过程完全相似，只不过将,16,次迭代的子密钥顺序倒过来，即,m = DES,-1,(c) = IP,-1, T,1,T,2,.T,15, T,16, IP(c),可以证明，,DES,-1,(DES,(m) )=m,53,DES,的强度,密钥长度,= 56,比特,强力攻击,=,尝试 次,差分密码分析,=,尝试 次,线性密码分析,=,尝试 次,（但是后两种攻击是不实用的）,54,1976,年，耗资,2000,万美元的计算机，可以在一天中找到密钥。,1993,年，设计,100,万美元的计算机，,3.5,小时用穷举法找到密钥。,1998,年，,EFF,宣布破译了,DES,算法，耗时不到三天时间，使用的是,25,万美元的“,DES,破译机,”,。,三重,DES,（,3DES,）,三重,DES,加密，密钥长度为,168,比特, k=k,1,k,2,k,3,55,DES,DES,-1,DES,m,c,k,1,k,2,k,1,DES,-1,DES,DES,-1,m,c,k,1,k,2,k,1,双密钥三重,DES,加密，密钥长度为,112,比特, k=k,1,k,2,DES,DES,-1,DES,m,c,k,1,k,2,k,3,DES,-1,DES,DES,-1,m,c,k,3,k,2,k,1,国际数据加密算法（,IDEA,）,IDEA,国际数据加密算法,International Data Encryption Algorithm,1990,年，,Xuejia,Lai,和,James Massey,第一版，,PES,（,Proposed Encryption Standard,）,为对抗差分攻击，修改算法增加强度，称为,IPES,。,1992,年改名,IDEA,。,“依我看来，该算法是目前已公开的最好和最安全的分组密码算法”,应用密码学,，,p226,。,PGP,中集成了,IDEA,算法。,56,IDEA,算法,IDEA,算法用了三种数学运算：,模,2,16,异或算法，常用 表示；,模,2,16,加法，表示为,X+Y=Z mod(2,16,),；常用 表示；,模,2,16,+1,乘法，表示为,X*Y=Z mod(2,16,1),；常用 表示；,IDEA,分组长度,64,比特 ，分,4,组，每组长度为,16,比特，表示为：,X1,、,X2,、,X3,和,X4,密钥长度,128,比特,同一算法既可以加密，也可用于解密。,软件实现,IDEA,比,DES,快两倍,现在还没有资料证明它有什么弱点。,57,高级数据加密标准（,AES,）,1997,年,4,月,15,日，,NIST,征集高级加密标准（,Advanced Encryption Standard,，,AES,）算法,目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法,对,AES,的基本要求是,比三重,DES,快、至少与三重,DES,一样安全,数据分组长度,128,比特、密钥长度,128/192/256,比特,1998,年,8,月,12,日，指定了,15,个候选算法。,1999,年,3,月,22,日（第二,次,AES,会议），,候选名单减少为,5,个（,RC6,，,Rijndael,，,SERPENT,，,Twofish,和,MARS,）,58,AES,2000,年,10,月,2,日，,NIST,宣布获胜者,Rijndael,算法。,2001,年,11,月，,NIST,将,AES,定为联邦信息处理标准,FIPS PUB197,。用于保护政府部门敏感但不机密的信息（,sensitive but not classified,）,2002,年,5,月正式生效。,NIST,对,AES,的评判,标准,安全性因素,，包括,：抗攻击能力、数学基础和分析、与其他算法安全性比较,成本因素，包括运行速度、存储空间、知识产权,59,AES,特点,1,、数据分组长度,128bits,；,2,、密钥长度,128/192/256 bits,；,3,、,加密过程是在一个,44,的,字节矩阵（,state,）上实施,4,、能有效,抵抗目前已知的攻击算法,线性,攻击、差分攻击,60,对称密码算法的优缺点,优点：,效率高，算法简单，系统开销小,适合加密大量数据,明文长度与密文长度相等,缺点：,需要以安全方式进行密钥交换,密钥管理复杂,61,小结,DES,是应用最广泛的对称密码算法（由于计算能力的快速进展，,DES,已不再被认为是安全的）；,IDEA,在欧洲应用较多；,AES,将是未来最主要，最常用的对称密码算法。,62,非对称,密码算法,理解,非对称密码算法的优缺点和应用场合,理解掌握,RSA,非对称密码算法原理和特点,了解,DiffieHellman,、,ECC,等非对称密码算法的原理和特点,63,公钥密码体制的思想,不同,于以往的加密技术，公钥密码体制是建立在数学函数基础上的，而不是建立在位方式的操作上的,。,与,只使用单一密钥的传统加密技术相比，它在,加解密,时，分别使用了两个不同的密钥,：,一,个可对外界公开，称为“公钥”,；,一,个只有所有者知道，称为“私钥”,。,用,公钥加密的信息只能用相应的私钥解密，反之亦然,。,同时,，要想由一个密钥推知另一个密钥，,在计算上是不可能的,。,64,公钥加密模型,65,Mary,Rick,明,文,密文,明,文,加密操作,解密操作,公钥,私钥,加密,与解密由,不同,的密钥,完成,加密,:,X,Y: Y = E,KU,(X,),解密,:,Y,X: X = D,KR,(Y) = D,KR,(E,KU,(X),公钥密码的重要特性,加密与解密由不同的密钥完成,加密,:,X,Y: Y = E,KU,(X),解密,:,Y,X: X = D,KR,(Y) = D,KR,(E,KU,(X),知道加密算法，从加密密钥得到解密密钥在计算上是不可行的。,两个密钥中任何一个都可以用作加密而另一个用作解密（不是必须的）。,X = D,KR,(E,KU,(X) = E,KU,(D,KR,(X),66,常用的公钥密码算法,RSA (Rivest - Shamir Adleman,），,1977,在一个算法中实现签名和加密,私钥,:,签名和解密,公钥,:,签名检验和加密,ECC,（,Elliptic Cure Crytosystem,），,1985,基于有限域上椭圆曲线有理点群的密码系统,更快的具有更小密钥长度的公开密码系统,功能同,RSA,：数字签名，密钥管理，加密,67,RSA,公钥密码体制,1977,年由,R,on,R,ivest,、,Adi,S,hamir,和,Len,A,dleman,发明，,1978,年正式公布。,RSA,是一种分组加密算法。明文和密文在,0n-1,之间，,n,是一个正整数。,该算法的数学基础是初等数论中的,Euler,（欧拉,),定理，并建立在大整数因子的困难性之上。,目前应用最广泛的公钥密码算法。,68,(Left to Right: Ron,R,ivest, Adi,S,hamir, Len,A,dleman),2002,年图灵奖获得者,-RSA-2002,69,RSA,算法操作过程,密钥产生,1.,取两个大素数,p, q ,保密,;,2.,计算,n=pq,，,公开,n,;,3.,计算欧拉函数,(n) =(p-1)(q-1),；,4.,任意取一个与,(n),互素的小整数,e,，,即,gcd (e,(n) )=1; 1e(n),，,公开,e,，作为公钥用于加密（或签名验证）。,5.,寻找,d,，,使得：,de,1 mod (n),作为私钥保密，即,de =k(n) +1,。,70,RSA,算法加密,/,解密过程,密钥对,（,KU, KR,）,:,KU=e, n , KR=,d, n,加密过程：把待加密的内容分成,k,比特的分组，,k log,2,n,，并写成数字，设为,M,：,C = M,e,mod n,解密过程,M = C,d,mod n,71,RSA,加密过程举例,p=7,q=17, n=7*17=119,，,(n)=(7-1)(17-1)=96,选,e=5, gcd (e, (n) = gcd (5, 96)=1,;,计算,d,，,使得,ed,1 mod 96 ,即,ed= k*96+1,取,k=4,，,则,d= 77,公开,(e,n)=(5,119),，,将,d,保密,，,丢弃,p, q,。,明文,：,m=19,加密：,19,5,66 mod 119 , c= 66,解密：,66,77,mod 119 =?,72,RSA,算法的安全性和性能,攻击方法,蛮力攻击：对所有密钥都进行尝试。,数学攻击：等效于对两个素数乘积,(n),的因子分解。,大数的因子分解是数论中的一个难题。,73,运算速度,软件实现比,DES,慢,100,倍,硬件实现比,DES,慢,1000,倍,椭圆曲线密码体制,椭圆曲线上的离散对数问题,点,Q,和点,P,是有限域上的椭圆曲线的两个点，在等式,mP=P+P+P=Q,中，已知,m,和点,P,求点,Q,比较容易，反之已知点,Q,和点,P,求,m,却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。,椭圆曲线应用到密码学上最早是由,Neal Koblitz,和,Victor Miller,在,1985,年分别独立提出的。,椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强度最高的一种体制。,74,椭圆曲线密码体制,椭圆曲线加密,基于椭圆曲线的,ElGamal,公钥密码算法,基于椭圆曲线的,DSA,（,ECDSA,）,椭圆曲线密钥协商,基于椭圆曲线的密钥协商问题，即,ECC Diffie-Hellman,椭圆曲线签密,基于椭圆曲线密码体制的签密方案,基于椭圆曲线密码体制的（,t,n,）门限签密方案,75,ECC vs. RSA,76,MIPS,年,表示用每秒完成,100,万条指令的计算机所需工作的年数,ECC vs. RSA,77,ECC,应用,无线,Modem,的实现,对分组交换数据网加密，实现快速,Deffie-Hellman,密钥交换,Web,服务器的实现,可节省计算时间和带宽,集成电路卡的实现,ECC,无需协处理器即可在标准卡上实现快速、安全的数字签名，,RSA,难以实现,78,ECC,的小结,安全性能更高（,160,位等同,RSA,的,1024,位）,计算量小，处理速度快,存储空间占用小,带宽要求低,应用前景非常好，特别在移动通信、无线设备上的应用。,79,基于公钥密码的加密过程,80,Alice,Bob,基于公钥密码的鉴别过程,81,Alice,Bob,公钥密码体制的优缺点,优点：,解决密钥传递的问题,大大减少密钥持有量,提供了对称密码技术无法或很难提供的服务（数字签名）,缺点：,计算复杂、耗用资源大,非对称会导致得到的密文变长,82,对公钥密码算法的误解,公钥密码算法比对称密码算法更安全？,任何一种现代密码算法的安全性都依赖于密钥长度、破译密码的工作量，从对抗分析角度，没有一方更优越。,公钥密码算法使得对称密码算法成为了过时技术？,公钥密码算法计算速度较慢，通常用于密钥管理和数字签名。,对称密码算法将长期存在。,使用公开密钥加密，密钥分配变得非常简单？,密钥分配既不简单，也不有效。,83,小结,RSA,数学基础,: IFP(Integer Factorization Problem),加,/,解密、密钥交换、数字签名,使用,最广泛,ECC,密钥长度短,Diffie-Hellman,密钥,交换算法,84,哈希函数和数字签名,理解哈希函数,、数字签名,特点,和作用,了解,MD5,算法、,SHA-1,算法的工作原理和特点,理解消息鉴别码特点和作用，了解,MAC,、,HMAC,的原理和应用,理解数字签名的原理和应用，了解,DSA,和,RSA,签名方案,85,Hash,函数,Hash,函数,是将任意长度的消息映射成一个较短的,定长输出报文的函数,如下形式,:,h = H(M), M,是变长的报文,h,是定长的散列值,.,数学性质：对任意给定的,x, H(x),易于,(,软硬件实,现,),计算，且满足：,单向性,:,对任意给定的码,h,寻求,x,使得,H(x)=h,在计算上是不可行的,;,弱抗碰撞性,:,任意给定分组,x,寻求不等于,x,的,y,使得,H(y)= H(x),在计算上不可行,;,强抗碰撞性,:,寻求对任何的,(x, y),对,使得,H(x)=H(y),在计算上不可行,.,86,86,Hash,函数的特点,H,能够应用到任意长度的数据上。,H,能够生成大小固定的输出。,对干任意给定的,x,，,H,（,x,）的计算相对简单。,对于给定的散列值,h,，要发现满足,H,（,x,）,h,的,x,在计算上是不可行的。,对于给定的消息,x,，要发现另一个消息,y,满足,H,（,y,）,H,（,x,）在计算上是不可行的。,主要的,Hash,算法：,MD5,、,SHA-1,等,87,哈希运算,完整性,88,用户,A,用户,B,数据,数据,哈希值,哈希算法,数据,哈希值,哈希值,哈希算法,如果哈希值匹配，说明数据有效,用户,A,发送数据和哈希值给用户,B,b,Y,0,n,IV,f,b,Y,1,n,f,b,Y,L-1,n,CV,L-1,f,CV,1,n,n,IV =,初始值,CV =,链接值,Y,i,=,第,i,个输入数据块,f =,压缩算法,n =,散列码的长度,b =,输入块的长度,安全,Hash,函数的一般结构,CV,L,IV,= initial n-bit value,CV,i,=f(CV,i-1, Y,i-1,) (1,i,L),H(M) = CV,L,Hash,函数,89,MD5,算法,MD,：,Message Digest,，消息摘要,输入：任意长度的消息,输出：,128,位消息摘要,处理：以,512,位输入数据块为单位,MD5 (RFC 1321) developed by Ron Rivest (,“,R,”,of the RSA )at MIT in 90,s.,90,SHA-1,算法,SHA,（,Secure Hash Algorithm,，安全哈希算法,）由美国国家标准技术研究所,NIST,开发，作为联邦信息处理标准于,1993,年发表（,FIPS PUB 180,），,1995,年修订，作为,SHA-1(FIPS PUB 180-1),，,SHA-1,基于,MD4,设计。,输入：最大长度为,2,64,位的消息；,输出：,160,位消息摘要；,处理：输入以,512,位数据块为单位处理,.,91,比较,SHA1/ MD5,散列值长度,MD5 128bits,SHA1,160bits,安全性,SHA1,看来,好些，但是,SHA1,的,设计原则没有公开,速度,SHA1,慢些 （,openssl speed,md5/sha1,）,type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes,md5 5425.31k 19457.48k 55891.45k 104857.60k 143211.40k,sha1 5104.58k 16008.41k 37925.33k 57421.81k,68241.68k,92,消息鉴别码,93,在网络通信中，有一些针对消息内容的攻击方法,伪造消息,窜改消息内容,改变消息顺序,消息重放或者延迟,消息认证：对收到的消息进行验证，证明确实是来自声称的发送方，并且没有被修改过。,如果在消息中加入时间及顺序信息，则可以完成对时间和顺序的认证,消息认证的三种方式,Message encryption：,用整个消息的密文作为认证标识,接收方必须能够识别错误,Hash function：,一个公开函数将任意长度的消息映射到一个固定长度的散列值，作为认证标识,MAC,：,一个公开函数，加上一个密钥产生一个固定长度的值作为认证,标识,94,MAC: Message,Authentication Code,使用一个双方共享的秘密密钥生成一个固定大小的小数据块，并加入到消息中，称,MAC，,或密码校验和(,cryptographic checksum),用户,A,和用户,B，,共享密钥,K，,对于,消息,M，,MAC=C,K,(M),如果接收方计算的,MAC,与收到的,MAC,匹配，则,接收者可以确信消息,M,未被改变,接收者可以确信消息来自所声称的发送者,如果消息中含有序列号，则可以保证正确的消息顺序,MAC,函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少,95,MAC,的动机,为了鉴别而加密整个报文不够方便,对称加密整个报文是个浪费,即使同时为了保密，也有另外的办法和体制,用非对称加密速度太慢，每秒仅百来笔,后来引入了签名体制,鉴别和加密的分离带来灵活性,确实有时只要鉴别而不用,(,或不能,),加密,如法律文书、公开信、声明、公告、公证、鉴定等,如软件鉴别,/,防病毒、网络管理报文等,96,97,MAC,的用法,HMAC,把,HASH,值和一个,Key,结合起来,不需要可逆,目标,既能使用当前的,HASH,函数，又可容易升级为新的,HASH,函数，并能保持散列函数的安全性,简单，并易进行密码学分析,98,MAC,不能解决的问题,发送者否认发送过消息，声称是别人伪造。,接收者伪造消息，声称其由某发送者发送。,解决办法,不可否认,性,99,数字签名,传统签名的基本特点:,能与被签的文件在物理上不可分割,签名者不能否认自己的签名,签名不能被伪造,容易被验证,数字签名是传统签名的数字化,基本要求:,能与所签文件“绑定”,签名者不能否认自己的签名,签名不能被伪造,容易被验证,100,数字签名,抗抵赖性,用户,A,用户,B,数据,哈希值,哈希算法,用户,A,的私钥,数据,哈希值,用户,A,的公钥,哈希算法,哈希值,如果哈希值匹配，说明该数据由该私钥签名。,101,数字签名的要求,依赖性：数字签名必须依赖要签名消息的比特模式,(,不可分离性,),唯一性：签名者使用唯一的“消息”生成数字签名，以防伪造和否认,(,独特性,),可验证性 ：数字签名必须是在算法上可验证的。,抗伪造：伪造一个数字签名在计算上不可行,(,不可模仿性,),可用性：数字签名的生成和验证必须相对简单,.,102,两种数字签名方案,103,RSA,的数字签名,初始化：,m,：签名的消息,签名者的私钥：,d,；公钥：,(e,n),签名：,计算,m,的哈希值,H(m).,签名值,s=(H(m,）,),d,mod n,验证：,计算,H,1,=s,e,mod n,判断,H,1,=H(m),是否成立。,104,数字签名算法（,DSA,）,1991,年, NIST,提出了 数字签名算法（,DSA,）,并把它用作数字签名标准（,DSS,），招致大量的反对，理由如下：,DSA,不能用于加密或密钥分配,DSA,是由,NSA,研制的，可能有后门,DSA,的选择过程不公开，提供的分析时间不充分,DSA,比,RSA,慢（,10,40,倍）,密钥长度太小（,512,位）,DSA,可能侵犯其他专利,RSA,是事实上的标准,105,三,种算法的比较,算法,加,/,解密,数字签名,密钥交换,RSA,是,是,是,Dieffie-Hellman,否,否,是,DSS,否,是,否,106,加密,/,解密,数字签名,(,身份鉴别,),密钥交换,总结,107,密码学在信息安全中的占有,举足轻重,的地位,掌握明文、密文、密钥等密码学基础概念,重点掌握,DES,、,IDEA,和,AES,等对称密码算法,重点掌握,RSA,和,ECC,等非对称密码算法,熟悉,MD5,和,SHA-1,等哈希算法,谢谢，请提问题！,