1 基本概念和术语
密码学是网络安全的基础。
– 虽然网络安全技术多种多样，但最终都是要提供六种安全服务：机密性、鉴别、完整性、不可抵赖性、访问控制和可用性。
– 能支持这六种安全服务的安全机制，例如：数据加密、消息鉴别、身份认证、数字签名等等大多数都是基于密码学及其衍生。
（1）密码学(Cryptology)
密码学是研究信息系统安全保密的科学。分为密码编码学和密码分析学。
– 密码编码学(Cryptography)主要研究对信息进行编码，实现对信息的隐蔽。
– 密码分析学(Cryptanalytics)主要研究加密消息的破译或消息的伪造。
（2）保密通信模型
在不安全的信道上实现安全的通信是密码学研究的基本问题。
¨ 消息发送者对需要传送的消息进行数学变换处理，然后可以在不安全的信道上进行传送；
¨ 接收者在接收端通过相应的数学变换处理可以得到信息的正确内容；
¨ 而信道上的消息截获者，虽然可能截获到数学变换后的消息，但无法得到消息本身，这就是最基本的保密通信模型。
数字通信系统
¨ 其中发送者对消息进行数学变换的过程称为加密过程；
¨ 接收者相应的数学变换过程称为解密过程；
¨ 需要传送的消息称为明文；
¨ 经过加密处理后的消息称为密文；
¨ 信道上消息的截获者通常被称为攻击者、分析者或者搭线者。
¨ 下图就是一个最基本的保密通信模型：
（3）密码体制
¨ 一个密码体制（有时也称加密方案或密码系统）是一个使通信双方能进行秘密通信的协议。
¨ 一个典型的加密方案由发送者、接收者和分析者三方参与，其中包括两个算法：
– 一个称为加密算法，被发送方用来加密消息。
– 另一个称为解密算法，被接收方用来解密接收的消息。
¨为了发送一个消息（即明文），发送方首先用加密算法处理明文，得到密文并发送。收到密文后，接收方用解密算法将密文恢复为明文。
¨ 为使这一方案能提供秘密通信，通信双方（至少收方）必须知道某些搭线者不知道的东西，否则搭线者也能像收方一样地恢复明文。
¨ 这个外加知识的形式，可以是某些参数和（或）辅助输入，称这个外加知识为解密密钥。
¨ 相应的，发送者在加密过程中有加密密钥的概念。
¨ 典型密码体制方框图如下：
密码学基本概念
¨ 明文：需要秘密传送的消息。
¨ 密文：明文经过密码变换后的消息。
¨ 加密：由明文到密文的变换。
¨ 解密：从密文恢复出明文的过程。
¨ 破译：非法接收者试图从密文分析出明文的过程。
¨ 加密算法：对明文进行加密时采用的一组规则。
¨ 解密算法：对密文进行解密时采用的一组规则。
¨ 密钥：加密和解密时使用的一组秘密信息。
¨ 从数学上来说，密码体制是一个五元组（P，C，K，E，D），其中满足条件：
(1) P是可能明文的有限集，称为明文空间；
(2) C是可能密文的有限集，称为密文空间；
(3) K是可能密钥构成的有限集，称为密钥空间；
(4) 任意k∈K，有一个加密算法e∈E和相应的解密算法d∈D，且e：P->C和d：C->P分别为加、解密函数，满足d(e(x))=x，这里x∈P。
密码学的历史
发展史
早在4000多年以前，古埃及人就在墓志铭中使用过类似于象形文字那样奇妙的符号；
公元前约50年，凯撒密码－一种简单的字符替换－被认为是最早的正式算法；
传统密码学、现代密码学、量子密码学。
应用领域
军事、外交、情报
商业、个人通信
（4）密码体制分类
¨ 根据加密时对明文消息是否分组，密码体制分为流密码和分组密码。
– 流密码又称为序列密码，加密时对明文按比特进行加密；
– 分组密码将明文分成相同长度的明文组，对所有的明文分组使用同样方式进行加密。
¨ 从密码体制的数学定义来看，加密密钥和解密密钥是成对使用的。
¨ 一般意义下，在密码体制具体实现过程中，加密密钥与解密密钥是一一对应关系。
¨ 根据由加密密钥得到解密密钥的算法复杂度不同，密码体制分为私钥(对称）密码体制和公开密钥密码体制。
– 私钥密码体制的加解密密钥可以很容易的相互得到，更多的情况下，两者甚至完全相同，在实际应用中发送方必须通过一个可能的安全信道将密钥送到接收方；
– 公开密钥密码体制中，由加密密钥（公钥）得到解密密钥（私钥）很困难，所以实际应用中接收方可以将加密密钥公开，任何人都可以使用该密钥（公开密钥）进行加密，而只有接收者拥有解密密钥（私钥），这样只有接受者能解密。
单钥密码学（对称密码学）加密密钥和解密密钥相同；系统的保密性取决于密钥的安全性；如何分发密钥是难点。
双钥密码学（非对称密码学，公钥密码学）加密密钥和解密密钥不同；系统的安全保障在于要从公开钥和密文推出明文或私钥在计算上是不可行的；分发密钥简单。
（5）密码算法的安全性
¨要衡量一个密码算法的安全性，首先应了解密码分析攻击的类型。
¨一般假设密码破译者已知密码体制，目标是破译密钥或密文对应的明文。
¨下表根据破译者所知的信息量总结了各种密码分析攻击的类型
密码算法的安全性
¨ Kerckhoofs假设(荷兰人，19世纪）：
– 密码破译者已知密码体制，目标是破译密钥或密文对应的明文。
¨ 无条件安全：
– 无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性，则此加密方案是无条件安全的。
– 已知的密码算法中没有无条件安全的，只有一次一密（one-time pad）方案是个例外。
¨ 计算上安全：
– 满足以下准则的一个或两个：破译的代价超出信息本身的价值；破译的时间超出了信息的有效期。
2. 现代对称加密技术
（1）分组密码设计介绍
对称密码算法的加密过程
对称密码学概述
¨ 分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列，如下图所示：
设计思想
¨Shannon提出扰乱和扩散
– 扰乱（Confusion）：使得密文的统计特性与密钥的取值之间的关系尽量复杂。这是为了挫败密码分析者试图发现密钥的尝试
– 扩散（Diffusion）：明文的统计结构被扩散消失到密文中，使得明文和密文之间的统计关系尽量复杂。
– Shannon当时关心的是如何挫败基于统计分析的密码破译问题。
¨若明文的统计特性以某种方式反映在密文中，则密码分析者就可能推测出加密密钥，或部分密钥，或密钥的一个集合。
– 统计特征：在英文文献中，不同的字母出现的频率是不一样的。
? 字母e出现的频率最高。
? 字母：t、o、a、i、n、s、h、r次之。
¨在Shannon所称的理想的密码中，密文的所有统计特性都与所用的是哪个密钥没有关系。
¨Shannon建议了两种为统计分析制造障碍的方法：扩散和扰乱。
¨扩散（Diffusion）：明文的统计结构被扩散消失到密文中，使得明文和密文之间的统计关系尽量复杂。
– 做到这一点的方法是让明文的每个数字影响许多密文数字的取值，也就是说每个密文数字被许多明文数字影响。
– 在二进制分组密码中，扩散可以通过重复使用对数据的某种替代，并对替代结果再应用某个函数的方式来达到，这样做就使得原明文不同位置的多个比特影响到密文的一个比特。
¨扰乱（Confusion）：使得密文的统计特性与密钥的取值之间的关系尽量复杂。
– 这是为了挫败密码分析者试图发现密钥的尝试。
– 进行扰乱后，即使攻击者掌握了密文的某些统计特性，使用密钥产生密文的方式是如此复杂以至于攻击者难于从中推测出密钥。可以使用一个复杂的置换算法达到这个目的。
Shannon介绍:
¨ 克劳德·艾尔伍德·香农 Claude Elwood.Shannon （1916— 2001）– 1916年4月30日出生于美国密歇根州– 1936年毕业于密歇根大学并获得数学和电子工程学士学位，1940年获得麻省理工学院（MIT）数学博士学位和电子工程硕士学位。– 1941年他加入贝尔实验室数学部，工作到1972年。– 1956年他成为麻省理工学院（MIT）客座教授，并于1958年成为终生教授，1978年成为名誉教授。– 香农博士于2001年2月26日去世，享年84岁。
¨ 香农在普林斯顿高级研究所（The Institute forAdvanced Study at Princeton）期间，开始思考信息论与有效通信系统的问题。– 经过8年的努力，从1948年6月到10月，香农在《贝尔系统技术杂志》（Bell System Technical Journal）上连载发表了影响深远的论文《通讯的数学原理》。– 1949年，香农又在该杂志上发表了另一著名论文《噪声下的通信》。– 在这两篇论文中，香农解决了过去许多悬而未决的问题：阐明了通信的基本问题，给出了通信系统的模型，提出了信息量的数学表达式，并解决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。两篇论文成为了信息论的基础性理论著作。那时，他才不过刚刚三十出头。
¨ 香农的成就轰动了世界，激起了人们对信息论的巨大热情，它向各门学科冲击，研究规模象浪雪球一样越来越大。– 不仅在电子学的其他领域，如计算机、自动控制等方面大显身手，而且遍及物理学、化学、生物学、心理学、医学、经济学、人类学、语音学、统计学、管理学… … 等学科。– 它已远远地突破了香衣本人所研究和意料的范畴，即从香农的所谓“狭义信息论”发展到了“广义信息论”。¨ 香农一鸣惊人，成了这门新兴学科的寞基人。20世纪80年代以来，当人们在议论未来的时候，人们的注意力又异口同声的集中到信息领域。香农这个名字也飞出了专家的书斋和实验室，为更多的人所熟悉和了解。
¨按照国际一种流行的说法，未来将是一个高度信息化的社会。信息工业将发展成头号工业，社会上大多数的人将是在从事后息的生产、加工和流通。这时，人们才能更正确地估价香农工作的全部含义。信息论这个曾经只在专家们中间流传的学说，将来到更广大的人群之中。¨香农被尊称为是“信息论之父”。人们通常将香农于1948年10月发表于《贝尔系统技术学报》上的论文《通信的数学原理》作为现代信息论研究的开端。
Feistel密码结构
¨流行的现代常规加密算法都是基于Feistel分组密码的结构。
¨Feistel提出可以使用乘积密码的概念去近似理想分组密码系统。
– 乘积密码就是以某种方式连续执行两个或多个密码以使得所得到的最后结果比其任意一个组成密码都更强。
¨Feistel提出用替代和置换交替的方式构造密码。
– 实际上，这是Shannon的一个设想的实际应用，Shannon提出用扰乱（confusion）和扩散（diffusion）交替的方法构造乘积密码。
¨ Feistel密码结构如下图所示：(图5传统Feistel网络)
¨ 加密算法的输入是一个长度2w比特的明文分组和一个密钥K，明文分组被分为两个部分L0和R0。
¨ 数据的这两个部分经过n轮的处理后组合起来产生密文分组。
¨ 每一轮i以从前一轮得到的Li-1和Ri-1为输入，另外的输入还有从总的密钥K生成的子密钥Ki。
¨每一轮的结构都一样。¨对数据的左边一半进行替换操作，替换的方法是对数据右边一半应用round函数F，然后用这个函数的输出和数据的左边一半做异或。
¨Round函数在每一轮中有着相同的结构，但各轮的子密钥Ki并不相同。¨在替换完成后，算法做一个置换操作把数据的两个部分进行互换。
¨大部分常规密码算法是Feistel密码结构的具体实现，只不过是对下列参数和设计特点的选择不同：
– 1)分组大小：分组越大安全性越高，但加解密速度越慢。64比特的分组大小是一个折中的选择。
– 2) 密钥大小：密钥长度越长则安全性越高，但加解密速度也越慢。64比特或更小现在已经认为不够安全，128比特已经成为常用的长度。
– 3)循环次数：循环越多则越安全，但加解密速度越慢。DES采用16次循环。
– 4)子密钥产生算法：这个算法越复杂，密码分析越困难。
– 5) Round函数：复杂性越高则抗击密码分析的能力就越强。
– 6)快速的软件实现。
– 7)易于硬件实现。
– 8) 便于分析。
¨Feistel的解密过程与其加密过程实质是相同的，解密的规则如下：
¨以密文作为算法的输入，但是以相反的次序使用子密钥Ki，即第一轮使用Kn，最后一轮使用K1。
¨这个特性正是常规加密算法又称为对称加密算法的原因。
（2） 数据加密标准介绍
¨ DES的发展史
– 数据加密标准DES （Data Encryption Standard）是由IBM公司在1970年发展出的一个加密算法。
– DES已经有30多年的历史，1976年11月23日DES被采纳为联邦标准；DES是第一个得到广泛应用的密码算法； DES在1977年经过美国国家标准局（NBS）采用为联邦标准之后，已成为金融界及其它各种产业最广泛应用的对称密钥密码系统。
– DES是分组密码的典型代表,也是第一个被公布出来的标准算法。
– DES是一种分组加密算法，输入的明文为64bit，密钥为56bit，生成的密文为64bit。
– 1997年6月，许多台计算机并行工作，140天内破解了DES；1998年，DES在48天内被破解；1999年，几个小时内就能破解。
– DES已经过时，基本上认为16轮、56bit不再安全。
¨ 1977年，美国正式公布美国数据加密标准— —DES，并广泛用于商用数据加密。算法完全公开，这在密码学史上是一个创举。
¨ 计算机通信网络发展对信息安全保密的需求日益增长，大量敏感和机密信息、数据的传输和存贮都要求有密码保护，为了实现同一水平的安全性和兼容性，而提出了数据加密标准化。DES是这种需求的产物。
¨DES是一个典型的基于Feistel结构的密码体制。
– DES输入的是64bit明文分组；
– 使用56bit的密钥；
– 循环的轮数是16；
– 使用了8个S盒实现扰乱功能。
¨参见word版DES算法描述
其它对称密码体制
¨ 三重DES(3DES)
¨ 使用三（或两）个不同的密钥对数据块进行三次（或两次）加密。
¨ 三重DES的强度大约和112-bit的密钥强度相当
¨ 三重DES有四种模型
ü DES-EEE3 使用三个不同密钥顺序进行三次加密变换
ü DES-EDE3 使用三个不同密钥依次进行加密-解密-加密变换
ü DES-EEE2 其中密钥K1=K3 顺序进行三次加密变换
ü DES-EDE2 其中密钥K1=K3 依次进行加密-解密-加密变换
¨ 到目前为止还没有人给出攻击三重DES的有效方法。
¨ IDEA
International Data Encryption Algorithm；
Xuejia Lai和James Massey提出；
IDEA是对称、分组密码算法，输入的明文为64位，密钥为128位，生成的密文为64位；
IDEA是一种相对较新的算法，有坚强的理论基础，已被证明可对抗差分分析和线性分析；
PGP中已实现了IDEA；
来学嘉博士简介
¨ 来学嘉，瑞士籍华人。是中国和瑞士联合培养的国际级密码学家。
– 1978-1982，西安电子科技大学本科；
– 1982-1984，西安电子科技大学信息安全研究所硕士研究生；
– 1985到瑞士ETH Zurich, Signal and InformationProcessing Laboratory
– 1988-1992在该实验室攻读博士研究生并取得博士学位。
– 他的两位导师，是著名密码学家肖国镇教授和瑞士ETH的Massey教授。
– 1992年，来学嘉的博士论文“On the Design andSecurity of Block Ciphers”给出了IDEA 密码算法(International Data Encryption Algorithm)。
– 如今，这个“国际数据加密算法”已经成为全球通用的加密标准。
¨ 高级加密标准（AES）
¨ 1997年4月15日美国国家标准和技术研究所NIST 发起了征集AES算法的活动并成立了专门的AES工作组
– 目的是为了确定一个非保密的公开披露的全球免费使用的分组密码算法用于保护下一世纪政府的敏感信息并希望成为秘密和公开部门的数据加密标准
¨ 1997年9月12日在联邦登记处公布了征集AES候选算法的通告AES的基本要求是
– 比三重DES快或至少和三重DES一样
– 安全分组长度128比特，密钥长度为128/192/256比特
¨ 1998年8月20日NIST召开了第一次候选大会并公布了15个候选算法
¨ 1999年3月22日举行了第二次AES候选会议从中选出5个算法
– MARS RC6 Serpent Twofish Rijndael
¨ 2000年10月，美国国家技术标准委员会(NIST)选定“Rijndael”为AES
¨ Rijndael是迭代分组密码，其分组长度和密钥长度都是可变的；
¨ 为了满足AES的要求，分组长度为128bit，密码长度为128/192/256bit，相应的轮数r为10/12/14。
对称密码体制应用实例
¨NTFS格式下Windows操作系统自带的EFS的加密演示。
3 非对称密码体制
¨ 公开密钥（非对称）密码的起源:
– 试图解决常规加密面临的两个难题的过程中发展起来的。
? 其一，密钥分配问题：有的密码学家认为要信任第三方违反了密码学的本义：使自己的通信具有完全的保密能力。于是他们努力寻求不需要第三方而又能安全地进行密钥分配的方法。
? 其二，数字签名问题：也就是我们能不能设计一种方法防止数字报文的发送者抵赖，否认发送过此报文。也即使各参与方都信服地确认一个数字报文是由某个人发送的。
公钥密码学发展的重要事件
¨ 1976年，由Diffie和Hellman在其“密码学新方向”一文中提出了公开密钥的概念。
¨ 1978年，Rivest、Shamir和Adleman发表了RSA算法，公开密钥密码系统由理论走向实用。
Ronald L.Rivest brief introduction 简介
¨ He is also a founder of RSA Data Security (now merged with Security Dynamics to form RSA Security).
¨ Professor Rivest has research interests in cryptography,computer and network security, electronic voting, and algorithms.
公开密钥算法的特性
¨公开密钥算法与常规加密算法最显著的不同是用一个密钥进行加密，而用另一个不同但是相关的密钥进行解密：
– 加密：X->Y：Y = EKU(X)
– 解密：Y->X：X = DKR(Y) = DKR(EKU(X))
¨一般对两个密钥作出区分：
– KU是公钥，需要传递给对端B，B使用此密钥加密数据传给本端A；
– KR是私钥，本端A保留且不能为外人所知，A使用此密钥解密B用KU加密过的数据。
– KU和KR是相互联系的，必须成对出现。
¨公开密钥算法的另一个特性是仅仅知道密码算法和加密密钥而要确定解密密钥，在计算上是不可能的。
¨显然，KU和KR虽然相关，但是由KU不能推导出KR，否则将无安全性可言。
¨ 某些公钥加密算法，例如RSA，还具有一个非常有用的特性：
– 两个相关密钥中任何一个都可以用作加密而让另外一个用作解密。
¨ 此特性可以使公钥算法用于鉴别：本端A持有KR，加密数据后传送给对端B；B使用相应的KU进行解密，若解密成功，则可断定数据是由A发送的，因为只有A才有KR。
¨ 若有可信的第三方则可以演化为数字签名系统。
¨ 网络中的每个端系统都产生一对加密密钥KU（公开密钥）和解密密钥KR（私有密钥）。
¨ 每个系统都通过把自己的KU放进一个登记本或文件来公布它。
¨ 如果A想给B发送一个报文，他就用B的公开密钥KUB加密这个报文。B收到这个报文后就用他的私有密钥KRB解密报文。其他所有收到这个报文的人都无法解密，因为只有B才拥有他自己的KRB。
（1）RSA算法
¨RSA算法1977年由Ronald L Rivest、AdiShamir和Len Adleman发明，1978年正式公布。
¨RSA是分组加密算法，明文和密文在0~n-1之间，n是一个正整数，一般明文分组长度为k比特，则2 k<n<=2 k+1。
¨RSA已经是当今应用最广泛的公钥密码算法。
¨RSA算法描述如下：
¨1) 分组大小为k，2 k<n<=2 k+1；
¨公开密钥KU={e,n}，私有密钥KR=d，其中n为两个素数p和q的乘积，e与(p-1)(q-1)互素，ed＝1(mod(p-1)(q-1))；
¨加密: c=me mod n；
¨解密: m=cd mod n。
设n是两个不同奇素数之积，即n = pq，计算其欧拉函数值Φ(n)=(p-1)(q-1).随机选一整数e,1≤e<Φ(n), (Φ(n),e)=1.因而在模Φ(n)下,e有逆元d = e-1 mod(j(n)) 取公钥为n,e,秘密钥为d.(p,q不再需要，应该被舍
弃，但绝不可泄露)定义加密变换为Ek (x) = x emodn, x?Zn解密变换为D k( y) = ye (modn), y?Zn
¨解密算法的正确性验证如下：
¨ cd (mod n)= (me)d (mod n)= med(mod n)
¨ = m * mk(p-1)(q-1)(mod n)
¨ = m * 1(mod n)
¨ = m(mod n)
¨ 下面举例说明RSA算法的使用：
¨ 1) Bob寻找出两个大素数p=101和q=113；
¨ 2) Bob计算出n=pq=11413， (n)=(p-1)(q-1)=11200；Bob选择e=3533，与(n)互素；
¨ Bob用Euclidean算法将求得：d=e-1=6597 mod 11200；Bob在一个目录中公开n=11413和e=3533
¨ 现假设Alice想发送明文9726给Bob，她计算：97263533 = 5761 （mod 11413），把5761发送给Bob
¨ 当Bob接收到密文5761，他用私有密钥d=6597进行解密：57616597=9726 （mod 11413）。
¨ 注：9726等表示0、1串，是信息。指数模运算有快速算法。
其他公钥算法
¨Rabin密码算法
合数模下求解平方根的困难性
¨ElGamal密码算法
基于离散对数问题
¨椭圆曲线密码算法
代数几何中基于椭圆曲线的点集
两类不同算法的对比
? 对称密码算法
加/解密速度快，但密钥分发问题严重。
? 非对称密码算法
加/解密速度较慢，但无密钥分发问题。
|
|
密钥管理复杂性 |
计算速度 |
开发费用和成本 |
|
私钥体制 |
复杂 |
快 |
较小 |
|
公钥体制 |
简单 |
慢 |
较大 |
3 公钥密码技术应用（两类密码体制的混合使用、数字信封技术）
基于公钥的鉴别
¨若使用的公钥算法两个相关密钥中任何一个都可以用作加密而让另外一个用作解密，则可用于鉴别。
¨A准备给B发送一个报文，在传输前用A的私有密钥KRA对它进行加密。
¨B收到报文后可以用A的公开密钥KUA将这个报文解密。
¨该报文是用A的私有密钥加密的，只有A才可能发送这个报文，而且报文在传输途中受到加密保护不能被篡改，因此报文的发送者和报文的完整性同时得到了证实。
|
