密码学概论

密码学是什么

密码学是对安全通信技术的研究，要能够有效的防范潜在攻击

概念

密码学最基础的几个概念是加密，解密，密文和密钥。比如 Alice 有一段数据要传递给 Bob ，就要首先运行加密算法把数据转换成密文，密文就是一些看起来不知所云的内容。密文到了 Bob 机器上，Bob 运行对应的解密算法，就可以把密文再转换成数据。那么什么是密钥呢？其实在加密和解密运算过程中有两个要素，一个是算法，另外一个是密钥，英文叫 key 。key 就是参与加密解密运算过程的一小段数据。

理论基础

首先，当代密码学是“互联网上的密码学”。历史上，从凯撒年代，就有秘密通信的概念，所以也诞生了凯撒密码这样的加密方式。后来电气革命兴起，人们也发名了专门用于加密的硬件器材。但是真正密码学的大发展其实是计算机兴起之后。尤其是互联网到来后，所有的信息都是在公共区域进行传输，任何人都可以截取我们的数据，于是在数据传输之前进行加密就显得尤其重要，当代的密码学也是在这个情景下来发展的。

第二，我们要记住，没有不可破解的密码。理论上，任何密码至少都可以通过暴力搜索的方式来破解。互联网上的加密算法都是公开的，所以 key 的一些特征也是明确的，例如总共多少位。对于计算机来说，一个个去猜，也就是用暴力搜索的方式去破解，也是一种很容易想到的攻击方式。所以这就给加密算法的设计者提出了一个基本要求，那就是算法一定是要保证足够的计算难度。从而保证虽然理论上可以算出 key 来，但是实际中用当前的硬件需要花费的时间是不可接受的，例如一万年。当然，数学理论一直在发展，计算机的处理速度也一直在提升，所以密码学本身也是一个不断进化的学科。

公钥加密的核心地位

当代密码学一直以来是分两套系统：对称加密和非对称加密。其中非对称加密也被叫做公钥加密，密码学的最核心技术。

对称加密和非对称加密是如何区分的呢？刚刚咱们提过，加密和解密过程中都是要有 key 参与，如果加密和解密使用同一个 key ，这就是对称加密技术，否则则是非对称加密技术。非对称加密略有一些反直觉。具体做法是首先生成一对 key ，其中一个是公钥，Public Key ，公钥是可以公开给任何人的，另外一个是私钥，Private Key ，要严格保密。发送方首先拿到接收方的公钥，用公钥把信息加密，接收方收到密文后，用私钥解密获得信息。

之所以公钥和私钥能够这样配合工作，是因为它们两个天生就是一对儿，有着天然的数学联系。具体的联系方式就跟使用的具体的加密算法有关了。非对称加密中最著名的算法有两种，一个是 RSA ，这是用三个作者的名字的缩写命名的算法， 另外一个是 ECC ，也就是椭圆曲线算法。RSA 是非对称加密技术的开山鼻祖。ECC 是更高效的一种加密算法，比特币就是使用了这种加密算法。

对称加密在发送方和接收方使用相同的 key ，所以建立安全通信的前提是双方先要有共享的 key ，那么没有加密通道的情况下，key 应该如何安全的传递给对方呢？这个在互联网上是非常有挑战性的。相对比之下，公钥加密技术要分享的是公钥，不用担心泄露问题，相对要安全一些，另外公钥加密技术也衍生出了数字签名技术。

当然，公钥加密技术也需要考虑如何确认公钥所有人等技术问题，所以就有了 CA 也就是发证机构，以及 PKI 公钥基础设施等等这些的概念，这里我们就不展开了。

密码与信息安全常识

使用密码的场合都是要求信息安全的，那使用密码需要注意些什么？

1.不要使用自创的加密算法

公开的密码算法都是被数学家证明过的不公开的密码算法早晚都会公诸于世

2.使用低强度密码不如不使用密码

低强度密码很可能造成假传圣旨、损失巨大

3.任何密码总有一天都会被破解

时间无限大时，密码总是会被破解的

4.密码只是信息安全的一部分

加密只是信息传递的一环，有时黑客会利用社会工程学拿到密码，那信息就会被泄露，信息安全是一个体系，密码只是其中一环

小结

在信息时代的今天，信息安全已上升到国家层面，我们要保障信息安全，需要做到以下几点：

1.使用密码算法对信息进行合理的加密

2.密码算法很多，每种算法都有其对应的应用场景

对称加密、非对称加密、数字签名、数字证书、数字水印

3.在信息传递过程中，防止信息窃听，密码盗取等措施都需要很好的把控才可以。

历史上的密码

凯撒密码

凯撒密码是一种相传尤利乌斯 凯撒曾使用过的密码

​ 凯撒与公园前100多年左右诞生与古罗马，是一位著名的军事统帅，凯撒密码被用于军事信息通信中

原理：平移算法

简单替换密码

​ 凯撒密码是通过将明文中所使用的字母表平移来生成密文的

​ 如果将26个字母打乱，和26个字母本身建立1对1的关系，那无论哪一种对应关系都可以作为密码

​ 凯撒密码也属于这种简单密码替换的一种

维吉尼亚密码

这是一种来掩盖字母使用频率的古老方式，因为除了暴力破解，查看一条信息的字母使用频率时是破解密码最常用的方法

原理：明文会对应一串密钥，根据密钥在维吉尼亚表中生成密文

例：

​ 加密：hacker

​ 密钥：hello

查看生成密钥，在表中找到明文横坐标与密钥纵坐标交叉点为密文

h a c k e r
h e l l o h
o e n v s y

小结

历史上的密码最初是在军队上传递信息时使用

随着时代的发展，密码也在不断发展，从最初的凯撒密码发展到二战时的Enigma密码机

Base64编码

Base64编码特点

​ 由64个Ascii码表组成，包括A-Z、a-z、0-9、+、/64个字符表示64中状态

原理：

​ 3个字节拆成4个字节

​ 每个字节再根据值在Base64表中获取字符

例：

文本 M a n
ASCLL 77 97 110

拆成四字节

二进制位 010011 010110 000101 101110
索引 19 22 5 46
base64编码 T W F u

如果不足三个字节的特殊情况

​ 1一个字节区前6位，剩余2位用0补齐6位

​ 不够4个字节，后面都补上等号（=）

例

文本 A a n
二进制 01000001

拆除四字节

二进制 010000 010000
Base64 Q Q = =

对称密码

DES

DES是1977年灭国联邦信息处理标准（FIPS）中采用的一种对称密码，一直以来被美国以及其他国家的政府或和银行等广泛使用

直到后来DES的密文可以在短时间内破译，除了用来解密之前的密文，现在基本都不在使用了。

DES是一种将64bit的明文加密成64bit的密文的对称密码算法，虽然DES密钥长度是64bit，但每隔7bit会设置一个用于错误检查的bit，因此实质上密钥长度是56bit.DES每次只能加密64bit，如果加密的明文比较长，就需要对DES加密进行迭代，而代的具 体方式称为模式

DEs的结构（Feistel网络，典型的分组密码结构）

DEs的基本结 HorstFeistel构是由设计的，简称（Feistel网络）

在 Feistel网络中，加密的各个步骤称为轮整个加密过程就是进行若干次轮的循环。DES是一种16轮循环的 Feistel网络。

Feistel网络的加密一轮循环

Feistel网络的加密一轮循环

1.输入数据分为左右两部分

2.将输入的右侧发送到输出的右侧

3.将输入的右侧发送到轮函数

4.轮函数根据右侧数据和子密钥，计算出一串看上去是随机的bit序列

5.将上一步得到的bit序列与左侧数据进行XOR运算，并将结果作为加密后

的左侧。

发现：右侧没有加密，因此需要用不同的子密钥对一轮的处理重复若干次，并在每两轮处理之间将左侧和右侧数据对调，保证所有数据都被加

Feistel网络的加密多轮循环

第一轮加密左侧

第二轮加密右侧

第三轮加密左侧

注意：每轮加密的子密钥是不一样的

Feistel网络的解密一轮循环

输入部分数据分为左右两给部分

将输入的右侧发送到输出的右侧

将输入的右侧发送到轮函数

轮函数根据右侧数据和子密钥，计算出一串看上去是随机的bit序列

将上一步得到的bit序列与左侧数据进行XOR运算，并将结果作为加密后的左侧

注意：加密和加密完全一样，使用相同的子密钥即可完成解密

Feistel网络的解密多轮循环

第一轮解密左侧

使用子密钥3

第二轮解密右侧

使用子密钥2

第三轮解密左侧

使用子密钥1

Feistel网络的密码算法特点

加密的轮数可以任意增加

加密时无论使用任何函数作为轮函数都可以正常解密

解密和解密可以用完全相同的结构来实现

同样使用Feistel网络分组算法实现的密码算法

MARS

RC6

Twofish

DES算法的实现

1、输入的64bit数据，经过置换IP表顺序打乱

2、左侧加密公式

​ 左侧+轮函数（右侧，子密钥）

3、左侧和右侧都经过16轮加密，每次使用的密钥都不同

4、子密钥的获取

5、最后输出前的64bit数据经过尾置换IP表2替换位置

3DES

3DES即三重DES，是为了增加DES强度，将DES重复3次所得到的一种密码算法机制

类型

1、DES密钥1和DES密钥3相同，DES密钥2不同，称DES=EDE2

2、DES密钥1、2、3都不同，称DES-EDE3

3、DES密钥都相同，与DES一样

AES

AES是取代前任标准（DES）而成为新标准的中对称密码算法。AES是一种标准，其实现算法是2000年评定的 Ri jndael算法。

Ri jndael算法是由比利时密码学家 Joan Daemen与 Vincent Ri jmen设计的分组密码算法。

Ri jndael的分组长度为128位，密钥长度可以以32位为单位在128位到256位的范围内进行选择

密钥长度在AES标准中只有128、192、256。 Rijndael算法的加密步骤分为4步：分组进行 SubBytes处理（置换）接着进行 ShiftRows处理（乱序）接着进行 MixColumns处理（移位）接着进行 AddRoundKey处理（异或）

SubBytes处理

以每个字节的值（0-255中任意值）为索引，从一张拥有256个值的替换表（S Box）中查找出对应值的处理，也就是说将一个1字节的值替换成另一个1字节的值。

ShiftRows处理

将 SubBytes的输出以字节为单位进行打乱处理。

MixColumns处理

对一个4字节的值进行位运算，将其变为另一个4字节值

AddRoundKey处理

与轮密钥进行XOR重复轮数

需重复10-14轮

Rijndael算法解密步骤分为4步

AddRoundKey处理

InvMixColumns处理

InvShiftRows处理

InvSubBytes处理

小结

使用一种密钥长度够长，且在算法上没有弱点的对称密码，就可以通过密文来确保明文的

机密性。

足够长的密钥能够抵御暴力破解，算法上没有弱点可以抵御其他类型的攻击。

然而，用对称密码通信的安全核心就是密钥配送问题，即如何将密钥安全地发送给接收者。解决这个问题需要公钥密码。DEs和三重DES的分组长度都是64位

AES的分组长度可以是128位、192位、256位。

公钥密码

简介

公钥密码技术是为了解决对称密码技术中最难解决的两个问题而提出的一是对称密码技术的密钥分配问题二是对称密码不能实现数字签名

DiffieHellmna和于1976年在《密码学的新方向》中首次提

出了公钥密码的观点，标志着公钥密码学研究的开始1977年 Rviest由， Shmair和 Adl mena提出了第一个比较完善

的公钥密码算法，即RSA算法。从那时候起，人们基于不同的计算问题提出了大量的公钥密码算法

公钥密码（public-key- cryptography）中，密钥分为加密密

钥和解密密钥两种。

发送者用加密密钥对消息加密接收者用解密密钥对密文解密

不难发现：

发送者只需要加密密钥接收者只需要解密密钥

解密密钥不可以被窃听者获取加密密钥被窃听者获取也没问题加密密钥，可以被公开，称公钥解密密钥，不可以被公开，称私钥公钥和私钥组成密钥对

举例：

Bob与 Alice的通信

1.Bob生成密钥对

2.Bob将公钥 Alice发给

  1. Alice将消息

使用Bob的公钥加密

  1. Alice将密文发送给Bob

5.Bob将密文使用私钥解密读取明文消息

公钥密码原理

从 Alice和Bob的通信模型中我们可知

公钥密码安全的核心在于在知晓公钥之后，很难求出私钥

成立条件：密文=明文与公钥计算

明文=密文与私钥计算

目标是：正向计算很简单，逆向计算非常难-》数学问题数学中的运算：加\减\乘\除\模设明文为12：

加减法：12-5=712=7+5；

乘除法：12*8=9612=96/8

模运算：12%5=212=？12=2*5+2模运算也成时钟运算，模表示：mod

数字：质数、素数、合数

质数：能够被1以及本身整除的数，1不是质数

素数：同上

合数：不是质数的数

倒数：5的倒数就是1/5

约数：因数，1的约数是1，4的约数是1，2，4

倍数：10的倍数是10，20，30

公约数：10和4的公约数是1，2

公倍数：10和4的公倍数是20，40，60

最大公约数：10和4的最大公约数是2

最小公倍数：10和4的最小公倍数是20

对数：乘方的逆运算称为对数。

7²=49; Log₇⁴⁹=2;

离散对数：模运算中的对数称为离散对数

7² mod 13=? 49 mod 13 = 10

特点：单向运算，正向计算很容易，逆向计算很困难

7﹖ mod 13 = ？ 求乘方是很难逆向计算的如果从0开始尝试

7⁰mod13=1

7¹mod13=7

7²mod13=10

7³mod13=5

7⁴mod13=9

7⁵mod13=11

7⁶mod13=12

7⁷mod13=6

7⁸mod13=3

7⁹mod13=8

那如果7足够大，且不能被化解，？号将更难求出。这就是公钥密码算法RSA的原理。

RSA密码

RSA是一种公钥密码算法，它的名称是由其三位开发者的姓氏组合

RSA可被用于公钥密码和数字密码签名

RSA加密过程

密钥对 公钥 数E和数N
私钥 数D和数N
加密 密文=明文E mod N 明文的E次方除以N的余数
解密 明文=密文D mod N 密文的D次方除以N的余数

由于E和N是公钥，D和N是私钥，因此求E，D，N这三个数就是

生成密钥对。

生成步骤：

1.求N

2.求L（L是仅在生成密钥对的过程中使用的数）

3.求E

4.求D

1.求N

N=pXq，而p和q是很大的质数，因为如果数太小，密码会变的容易破解，且质数不能被分解。

2.求L

L是在生成密钥对时出现，L是p-1和q-1的最小公倍数。最小公倍数（least common multiple，1cm）

公式：L=1cm（p-1，q-1）（L是p-1和q-1的最小公倍数）

3.求E

E是一个比1大，比L小的数。此外，E和L的最大公约数必须为最大公约数（greatest common divisor，gcd）

公式：gcd（E，L）=1 1<E<L E和L的最大公约数是1（E和L互质）要找出gcd（E，L）=1的数，需要以下几步：

1.使用伪随机数生成器生成1<E<L范围内E的候选数

2.判断是否满足gcd（E，L）=1的条件

3.循环判断1和2直到条件成立

求最大公约数可使用欧几里得的辗转相除法

简单来说，满足gcd（E，L）=1条件能保证存在解密的数D

4.求D

数D是由数E计算得到的。D，E，L之间必须具备以下关系：

1<D<L

E X D mod L= 1

只要数D满足上述条件，则通过E和N进行加密的密文，就可以

通过D和N进行解密。

简单来说， E X D mod L=1保证了对密文进行解密时能够得到原来的明文。

公式总结

求N 求E
N = pxq，用伪随机数生成器求p和q，p和q都是质数 gcd（E，L）=1，1<E<L ,E和L的最大公约数时1（E和L互质）
求L 求D
L=1cm（p-1，q-1），（L是p-1和q-1的最小公倍数） 1<D<L,E X D mod L = 1

实例

1.求N

N pxq，p=17，q=19，（17，19都是质数），N=17X19=323

2.求L

L是p-1和q-1的最小公倍数

L=lcm(p-1,q-1)=1cm(16,18)=144

3.求E

E和L的最大公约数必须是1，即gcd（E，L）=1

满足条件的有：5，7，11，13，17，19，23，…

选择E=5

4.求D

E X D mod L=1 ->5 X D mod 144=1

D=29

1.生成密钥对

公钥：E=5，N=323

私钥：D=29，N=323

2.使用公钥加密明文，明文必须小于N

设明文=123

加密：密文=明文E次方 mod N

密文=123⁵ mod 323 = 28153056843 mod 323 =225

3.使用私钥解密明文

解密：明文=密文D次方 mod N

明文=225²²⁹ mod 323 = 123

1.通过密文获取明文

公式：明文=密文D次方 mod N

明文=密文modD次方 N

求密文D次方等于求对数

求密文D次方 mod N等于求离散对数这是世界难题！

2.暴力破解

求出D就可以解密，但如果D足够大，是很难暴力破解的。

3.通过E和N求出D

加密：密文=明文E次方 mod N

N如果能进行分解，求出p和q，D就能求出大整数进行质因数分解，也是世界难题！

p和q是伪随机数生成器生成的，如果伪随机数生成器算法很差能够碰撞成功也可以破解。