密码学概述

密码学是研究编制密码和破译密码的技术科学，使信息保密的技术和科学叫密码编码学，破译密文的科学与技术叫密码分析学

密码学是数学和计算机科学的分支，同时其原理大量涉及信息论。

著名的密码学者罗纳德•李维斯特——密码学是关于如何在敌人存在的环境中通信。

信息安全的基本模型

加密密码示意图

密码学的历史与发展

第一阶段（1949年前）古典密码发展阶段

隐写术，暗语、隐语、藏头诗等>
采用手工或机械变换的方式实现
单表代换密码：Caesar密码、仿射密码
多表代换密码：Vigenere、Hill密码等
转轮密码：Enigma、Red密码等

第二阶段：近代密码学阶段(1949~1976)

1949年，Shannon发表了《保密系统的通信理论》，用信息论的观点分析了密码学的基本原理，奠定了密码学的理论基础。
1967年David Kahn出版了《破译者》一书。

第三阶段：现代密码学阶段(1976~至今)

1976年，Diffie、Hellman发表《密码学新方向》，开辟了公钥密码学的新领域；
1976年，美国建立DES为联邦标准
现代密码学的主要方向
- 混沌密码学：混沌加密的基本原理是利用混沌系统产生混沌序列作为密钥序列，接收方用混沌同步的方法将明文信号提取出来实现解密。
- 量子密码学：量子密码学泛指利用量子力学的特性来加密的科学。任何试图尝试读取量子态的行动，都会改变量子态本身

密码体制分类

受限制的(restricted)算法：算法的保密性基于保持算法的秘密，
基于密钥(key-based)的算法：算法的保密性基于对密钥的保密。

优秀密码算法应该是基于密钥的保密，而非算法的保密。

现代密码学用密钥解决问题，密钥用K表示。K可以是很多值里的任意值,密钥K的可能值的范围叫做密钥空间(keyspace)。

如加密和解密都用一个密钥，加/解密函数变成：

E_K(M)=C
D_k(C)=M
D_k(E_k(M))=M

单钥体制，对称加密

加密密钥和解密密钥相同
流密码
分组密码

双钥体制，非对称加密

1976年，Diffie和Hellman首先引入
一对密钥：公钥和私钥

密码攻击概述

算法的安全性

如果破译算法的代价大于加密数据价值，那么加密算法是安全的。

如果破译算法所需的时间比加密数据保密的时间长，那么你可能是安全的。

编码与密码

编码基础

ASCII 编码

ASCII (American Standard Code for Information Interchange,美国信息交换标准代码)是基于拉丁字母的一套电脑编码系统，主要用于显示现代英语和其他西欧语言。

ASCII是现今最通用的单字节编码系统，并等同于国际标准ISO/IEC 646。

标准ASCI川码也叫基础ASCII码，使用7位二进制数（剩下的1位二进制为0）来表示所有的大写和小写字母，数字0到9、标点符号。

后128个称为扩展ASCII码。许多基于x86的系统都支持使用扩展ASCII。扩展ASCII码允许将每个字符的第8位用于确定附加的128个特殊符号字符、外来语字母和图形符号。

Unicode编码

ASC川因为只有8位长，只能表达256种字符。所以不能满足其它国家需求，Unicode是国际组织制定的可以容纳世界上所有文字和符号的字符编码方案。使用16位的编码空间。也就是每个字符占用2个字节。

**UTF-8(8-bit Unicode Transformation Format)**是一种针对Unicode的可变长度字符编码，在实际传输过程中，由于不同系统平台的设计不一定一致，以及出于节省空间的目的，对Unicode编码的实现方式有所不同，所以有UTF。UTF-8使用一至六个字节为每个字符编码

Base64

Base64是一种基于64个可打印字符来表示二进制数据的表示方法。每6个比特为一个单元，对应某个可打印字符除了A-Z,a-z,0-9共62个字符还有+、/，最后用=填充不能被3整除的空位。

古典密码学

主要考虑消息的保密性，对于完整性和不可否认性没有太多考虑

古典密码的加密是将明文的每个字母代换为字母表中的另一个字母，根据代换是对每个字母逐个进行还是对多个字母同时进行，古典密码又分为单表代换和多表代换

单表代换

通用特点：对每个字母逐个进行替换

凯撒密码

凯撒密码加密时将明文中的每个字母按字母表顺序向前或向后移动固定数目，作为密文。

如偏移量是左移3为例

明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文：DEFGHIJKLMNOPQRSTUVWXYZABC

移位密码

与凯撒密码类似，最早的凯撒密码是固定左移3位。

区别在于移位密码可以任意移动，后期不仅处理26个字母，还会处理数字和特殊字符。参照ASCII码表进行位移。

仿射密码

乘法逆元： a*a^-1(mod m) = 1

多表替换

加密方式使用多个表，解决单表加密的频率分析问题

Playfair

该算法基于5*5的字母矩阵，该矩阵使用一个关键词构造（即密钥），从左到右、从上到下顺序，填入关键词的字母（去除重复字母）后，将字母表其作余字母填入。(I=J)

将明文两个分为一组，若出现相同字母，则用X替代最后字母。

在每组中，查找矩阵替换：

若两个字母同行，则用右方字母替换若
两个字母同列，则用下方字母替换
若即不同行也不同列，则用矩阵对角字母替换

polybius

又称棋盘密码。将给定明文加密为两两组合的特征加密后结果只有5种字符,ADFGX密码是德军在一战中使用的栏块密码

1 2	明文：A T T A C K A T O N C E 密文：AF AD AD AF GF DX AF AD DF FX GF XF

vigenere

使用26个字母构成字母矩阵横行为明文列，纵向为密钥列

明文：come greatwall
密钥：crypto

扩充密钥与明文一样长：efktzferrltzn

其他类型密码

培根密码

用两种不同的字体，代表A和B，或者0和1，结合加密表进行加密。

明文：steganography
正常字体是A，粗体是B，加密结果如图

栅栏密码

把明文分成N个一组，然后每组的第1个字连起来，然后连第2个….

摩斯密码

对称加密

对称密码主要特征就是加密和解密使用相同的密钥，也叫单密钥加密

根据加密对象分为

流加密，每次加密都通过密钥生成一个密钥流，解密也是使用同一个密钥流明文与同样长度的密钥流进行异或运算得到密文，密文与同样的密钥流进行异或运算得到明文。典型算法RC4
块加密，块密码算法也叫分组密码算法，从字面意思就可以知道，它把加密和解密序列分成了一个个分组，最后把每一块序列合并到一起，形成明文或者密文。根据不同的分组加密方式，每个分组之间可以有联系，也可以没有联系。典型算法是DES和AES

RC4

RC4应用广泛，是典型的流加密算法。常见用于SSL/TLS,及802.11和WAP中。

流加密会逐字节加密数据，RC4本质是以密钥为种子(seed)产生的随机数来对明文进行逐字节异或，分组密码与流密码的区别就在于有无记忆性。

每次只加密明文中的一个字节，密钥长度可变，1-256字节

介绍RC4算法的几个关键变量：

密钥流：RC4算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文的长度是对应的，也就是说明文的长度是500字节，那么密钥流也是500字节。当然，加密生成的密文也是500字节，因为密文第i字节=明文第i字节^密钥流第i字节；
状态向量S：长度为256，S[0],S[1]…..S[255]。每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换；
临时向量T：长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，轮转地将密钥的每个字节赋给T；
密钥K：长度为1-256字节，注意密钥的长度keylen与明文长度、密钥流的长度没有必然关系，通常密钥的长度16字节（128比特）。

基本流程

初始化S和T
计算排列S,j从0到255
产生与明文等长的密钥流
加密运算

算法描述

S和T的初始状态： S中元素的值按升序被置为0-255，同时建立一个临时向量T。将密钥的值循环复制到T向量中。

S的初始置换，用T产生S的初始置换，伪代码如下

j=0
for (i = 0;i<256;i++){
    j = (j+S[i]+T[i]) mod 256;
    swap(S[i],S[j]);
}

密钥流生成伪代码

i,j = 0;
while(true){
    i = (i+1)mod 256
    j = (j+S[i]) mod 256;
    swap(S[i],S[j]);
    t = (S[i]+S[j]) mod 256;
    k = S[t];
}

DES

数据加密标准(data encryption standard,DES)是迄今为止世界上最为广泛使用和流行的一种分组密码算法,它的分组长度为64比特，密钥长度为56比特，由美国IBM公司研制

DES在1975年3月17日首次被公布在联邦记录中，经过大量的公开讨论后于1977年1月15日被正式批准并作为美国联邦信息处理标准

1998年5月美国EFF(electronics frontier foundation)宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56比特密钥的DES

DES介绍

明文分组长 64 bit

密钥 56 bit

明文处理：3个阶段

初始置换IP
16轮变换
逆初始置换1P^-1

密钥处理：

置换函数
左循环移位+置换->子密钥

F中的代换由8个S盒组成，每个S盒的输入比特为6bit，输出长为4bit，其变换关系由表定义，每个S盒给出了4个代换

密钥的产生：

56比特密钥首先经过一个置换运算，然后将置换后的56比特分为各为28比特的左、右两半，分别记为C0和D0。

在第i轮分别对C_i-1和D_i-1进行左循环移位，所移位数由表给出。

移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择2的输入。通过置换选择2产生的48比特的Ki,即为本轮的子密钥，作为函数F(R_i-1,K)的输入。其中置换选择2由表定义。

为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用，比如2DES、3DES

DES的加密模式

分组密码在加密时，明文分组的长度是固定的，而实际应用中待加密消息的数据量是不定的，数据格式可能是多种多样的。为了能在各种应用场合使用DES,美国在FIPS PUS74和81中定义了DES的4种运行模式

这些加密模式大都可以归类为两种，即ECB模式和CBC模式

ECB全称为Electronic CodeBook,是块加密中比较简单的加密模式。在ECB模式中，每一块明文数据都被独立地进行加密来生成加密块。这意味着如果你发现两个加密块有相同的内容，那么就可以确定这两个加密块的原文也是相同
CBC全称为Cipher-Block Chaining,算是最常见的块加密模式了。在CBC模式中，每个明文块都会在加密前被使用前一个明文块的秘文进行异或；解密过程侧正好相反。其中第一个明文块会使用V即初始化向量进行异或。

AES介绍

1997年4月15日，美国ANSl发起征集AES(advanced encryptionstandard)的活动，并为此成立了AES工作小组。

1998年8月，在首届AES候选会议上公布了AES的15个候选算法。

1999年3月，在第2届AES候选会议上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个。

2000年10月，NIST宣布Rijndael作为新的AES。至此，经过3年多的讨论，Rijndael终于脱颖而出。

Rijndael

Rijndael由比利时的Joan DDaemen和Vincent Rijmen设计，算法的原型是Square.算法，它的设计策略是宽轨迹策略。

宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界。

Rijndael密码的设计力求满足以下3条标准：

抵抗所有已知的攻击。
在多个平台上速度快，编码紧凑
设计简单。

优点：加解密速度快、安全性好、适合大量数据加密

密码分析

差分密码分析是迄今已知的攻击迭代密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。

线性密码分析是对迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡（有效）的线性逼近”

非对称加密

1976年以前，所有的加密方法都是同一种模式：加解密双方使用相同算法，相同密钥来进行运算得到结果。这种加密模式有一个最大弱点：甲方必须把加密规则与密钥告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。

公钥密码体制以非对称的形式解决单钥密码体制中最难解决的两个问题：密钥分配和数字签名

1976年，Diffie和Hellman提出公钥密码思想，可以在不直接传递密钥的情况下，完成解密。这被称为”Diffie-Hellman密钥交换算法”

RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。

公钥密码体制算法条件

产生一对密钥是计算可行的

已知公钥、明文，产生密文是计算可行的

利用私钥、密文，得到明文是计算可行的

利用公钥来推断私钥是计算不可行的

利用公钥、密文，得到明文是计算不可行的

RSA算法

密钥交换

公钥体制的密钥管理

公钥的分配方法：公开发布、公用目录表、公钥管理机构、公钥证书

公钥分配完成后，用户就可以使用公钥体制进行保密通信。但是公钥加密速度慢，进行通信时不太合适。此时更适合使用对称加密来通信。由此引申出对称加密的密钥分配管理问题。

Diffie-Hellman密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公钥密码算法，算法的惟一目的是使得两个用户能够安全地交换密钥，得到一个共享的会话密钥，算法本身不能用于加、解密。算法的安全性基于求离散对数的困难性。

Diffie-Hellman算法

单密钥加密体制密钥分配

在大量用户需要互相通信时，单密钥体制，会使用大量密钥。如有n个用户要互相通信，此时需要n(n-1)/2个密钥此时密钥管理是一个严重的风险问题。

引入KDC来解决这个问题，密钥分发中心KDC和每个终端用户都共享一对唯一的主密钥（用物理的方式传递，如U盾)。终端用户之间每次会话，都要向KDC申请唯一的会话密钥，会话密钥通过与KDC共享的主密钥加密来完成传递。

基于KDC的单密钥分配

建立一个共享的一次性会话密钥，可通过以下几步来完成：

A向KDC发出会话密钥请求。表示请求的消息由两个数据项组成，第1项是A和B的身份，第2项是这次业务的惟一识别符N1。
KDC为A的请求发出应答。应答是由KA加密的消息，因此只有A才能成功地对这一消息解密，并且A可相信这一消息的确是由KDC发出的。
A存储会话密钥，并向B转发E_KB[K_S ||ID_A]。因为转发的是由K加密后的密文,所以转发过程不会被窃听。B收到后，可得会话密钥K_S,并从ID_A可知另一方是A,而且还从E_KB知道K_S的确来自KDC。
B用会话密钥K_S加密另一个一次性随机数N2,并将加密结果发送给A。
A以f(N2)作为对B的应答，其中f是对N2进行某种变换（例如加1）的函数，并将应答用会话密钥加密后发送给B。

无KDC的密钥分配

两个用户A和B建立会话密钥需经过以下3步(A与B已经有共享主密钥)

A向B发出建立会话密钥的请求和一个一次性随机数N1。
B用与A共享的主密钥MKm对应答的消息加密，并发送给A。应答的消息中有B选取的会话密钥、B的身份、f(N1)和另一个一次性随机数N2。
A使用新建立的会话密钥Ks对f(N,)加密后返回给B。

公钥加密体制的密钥管理

基于公钥管理机构的公钥分配

用户A向公钥管理机构发送带时戳的消息，请求获取用户B的公钥。
管理机构作出应答，该消息由管理机构用自己的私钥SKAU加密，因此A能用管理机构的公开钥解密，并确认该消息的真实性。
A用B的公钥对一个消息加密发往B,这个消息有两个数据项：一是A的身份IDA,二是一个一次性随机数N1,用于惟一地标识这次业务。
B以相同方式从管理机构获取A的公开钥（与步骤①、②类似）。这时，A和B都已安全地得到了对方的公钥，所以可进行保密通信。
B用PKA对一个消息加密后发往A,该消息的数据项有A的一次性随机数N1和B产生的一个一次性随机数N2。因为只有B能解密③的消息，所以A收到的消息中的N1可使其相信通信的另一方的确是B。
A用B的公开钥对N2加密后返回给B,可使B相信通信的另一方的确是A。

基于公钥证书管理公钥

用户通过公钥证书来互相交换自己的公钥而无须与公钥管理机构联系。公钥证书由证书管理机构CA(certificate authority)为用户建立，其中的数据项有与该用户的秘密钥相匹配的公开钥及用户的身份和时戳等。

所有的数据项经CA用自己的秘密钥签字后就形成证书，即证书的形式为：CA=E_SKCA[T,ID_A ,PK_A]

ID_A是用户A的身份，PK_A是A的公钥，T是当前时戳，SK_CA是CA的秘密钥，CA即是为用户A产生的证书

哈希算法

哈希函数也可以称为杂凑函数
哈希函数H是公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M),称函数值H(M)为杂凑值、哈希值或消息摘要。

哈希算法的条件

哈希函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，哈希函数应满足以下条件：

函数的输入可以是任意长。
函数的输出是固定长。
已知x,求H()较为容易，可用硬件或软件实现。
已知h,求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(X)为单向杂凑函数。
已知x,找出y(y≠x)使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为弱单向杂凑函数。
找出任意两个不同的输入X、y,使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为强单向杂凑函数。

第⑤和第⑥个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。

MD5算法

MD5算法采用迭代型杂凑函数的一般结构。算法的输入为任意长的消息，分为512比特长的分组，输出为128比特的消息摘要。

MD5的处理步骤

对消息填充，使得其比特长在模512下为448。
附加消息的长度用步骤①留出的64比特以little-endian方式来表示消息被填充前的长度。如果消息长度大于264，则以264为模数取模。
对MD缓冲区初始化算法使用128比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器（A,B,C,D）
以分组为单位对消息进行处理每一分组都经一压缩函数HMD5处理。H_MD5是算法的核心。

MD5的安全性

目前对MD5的攻击已取得以下结果

对单轮MD5使用差分密码分析，可在合理的时间内找出具有相同杂凑值的两个消息。
可找出一个消息分组和两个相关的链接变量（即缓冲区变量ABCD)，使得算法产生出相同的输出。
对单个512比特长的消息分组已成功地找出了碰撞，即可找出另一个消息分组，使得算法对两个消息分组的128比特长的输出相同。

数字签名和电子证书

数字签名的性质

能够验证签字产生者的身份，以及产生签字的日期和时间
能够用于证实被签消息的内容
数字签字可由第三方验证，从而能够解决通信双方的争议

数字签名的要求

为了实现上述的3个性质，数字签名应该满足以下要求：

签字的产生必须使用发方独有的一些信息以防伪造和否认。

签字的产生应较为容易。

签字的识别和验证应较为容易。

对已知的数字签字构造一新的消息或对已知的消息构造一假冒的数字签字在计算上都是不可行的。

数字签名标准

数字签字标准DSS(Digital Signature Standard)是由美国NIST公布的联邦信息处理标准FIPS PUB186,其中采用了上一章介绍的SHA和一种新的签字技术，称为DSA(Digital Signature Algorithm)。DSS最初于1991年公布，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版。

DSS与RSA
RSA算法既能用于加密和签名，又能用于密钥交换
DSS使用的算法只能提供数字签字功能

DSA步骤

p g q为全局公开钥,x为用户私钥,y为用户公钥,k为用户秘密选取的随机数。最终签名为(r,s)，r由一系列公钥算出，s由消息原文算出。r可用于第三方验证s用于完整性与真实性

X.509证书

X.509是密码学里公钥证书的格式标准

X.509证书己应用在包括TLS/SSL在内的众多Intenet协议里

X.509证书里含有公钥、身份信息（比如网络主机名，组织的名称或个体名称等）和签名信息

X.509的格式

X.509有多种常用的扩展名。但具有这个扩展名的文件可能并不是证书，比如说可能只是保存了私钥

.pem DER编码的证书再进行Base64编码后存放在”—BEG引NCERTIFICATE—“和”—END CERTIFICATE—“之中
.cer,.crt,.der 通常是DER二进制格式的，也可Base64编码。
.p7b,.p7c PKCS#7是签名或加密数据的格式标准，不包含数据
.p12 PKCS#12格式，包含证书的同时可能还有带密码保护的私钥
.pfx PFX,PKCS#12之前的格式（通常用PKCS#12格式，比如那些由IIS产生的PFX文件）

X.509申请过程

组织机构通过发起证书签名请求(CSR)来得到一份签名的证书。

CSR包含有请求发起者的身份信息，用来对此请求进行验真的的公钥以及所请求证书专有名称。

CA对这个专有名称发布一份证书，并绑定一个公钥。

组织机构可以把受信的根证书分发给所有的成员（现在操作系统、浏览器都已内置了知名的CA根证书）

SSL/TLS

X.509证书广泛应用在SSL/TLS协议中，即我们常见的HTTPS站点

client hello
客户端发起请求，以明文传输请求信息，包含版本信息，加密套件候选列表，压缩算法候选列表，随机数，扩展字段等信息，支持的最高TSL协议版本version,从低到高依次SSLv2 SSLv3 TLSv1 TLSv1.1 TLSv1.2
客户端支持的加密套件cipher suites列表，每个加密套件对应四个功能的组合：认证算法Au(身份验证)、密钥交换算法KeyExchange、对称加密算法和信息摘要Mac
随机数random C,用于后续的密钥的生成
server_hello+server_certificate+sever_hello_done
server_hello,服务端返回协商的信息结果
server_certificates,服务器端配置对应的证书链，用于身份验证与密钥交换；
server_hello_done,通知客户端server hello信息发送结束；
证书校验
客户端验证证书的合法性，如果验证通过才会进行后续通信，否则根据错误情况不同做出提示和操作，合法性验证包括如下：
- 证书链的可信性trusted certificate path,方法如前文所述；
- 证书是否吊销revocation,有两类方式离线CRL与在线OCSP,不同的客户端行为会不同；
- 有效期expiry date,证书是否在有效时间范围：
- 域名domain,核查证书域名是否与当前的访问域名匹配；
client_key_exchange+change_cipher_spec+encrypted_handshake_message
change_cipher_spec+encrypted_handshake_message
握手结束
加密通信
服务器也可以要求验证客户端，即双向认证，可以在过程2要发送client_certificate_request信息。在4中回复信息。