History

恺撒密码

恺撒密码其实就是把明文字母表平移若干个字母实现的
原理清晰简单,解密反向平移若干位即可
而破译者只需要尝试至多25次即可解密

简单替换密码

简单替换密码是吧明文字母表中每一项对应另外一个字母,映射关系形成一张表,加密与解密都基于该映射表
原理也十分简单,而尝试暴力破解却不可行,因为映射关系相当与26个字母的全排列:26! 即使每秒遍历10亿个密钥,也需要超过120亿年的时间

如何破译 - 频率分析法

因为人类自然语言中26个字母的使用频率是不相同的,据统计,一般英语文章中频率最高的字母是e那么我们就可以在密文中将频率最高的字母对应为e然后结合英文词汇前缀后缀不断尝试就可以逐步破译. 对于专业并经验丰富的密码破译者来说,破译该密码并不难,因为可以分析的线索较多,不光频率最高是线索,频率最底也是线索,单词的固定出现也是线索,等等.

密码算法与密钥

在密码算法中必然存在可变的部分,而这些可变的部分就相当于密钥,当密码算法和密钥都确定的时候,加密的方法也就确定了.
如果每次加密都产生一个新的密码算法,那就没有了可重复性,所以对于开发出的密码算法,我们希望能够重复使用,这样就自然的把密码算法和密钥分开来,密码算法是需要重复使用的,而重复使用算法过程中,该算法被破译的可能性也在增大,因此我们需要可变的密钥.
解决了希望重复使用,但重复使用会增加风险这个难题.

出乎意料的原则

不要使用保密的密码算法
我们正常的想法是,我自己设计开发出一个密码算法,并且把这种密码算法保密,那就可以保证安全,实际上这种想法是错误的,我们应该使用公开的,被公认为强度高的密码算法

原因

• 密码算法秘密早晚会被公开
  逆向工程可以进行分析,找到漏洞破解
• 开发高强度密码算法实际上是十分困难的 一般人设计的密码强度在外行看来是牢不可破的,但是在专业密码破译者眼里,几乎是手到擒来

试图通过对密码算法本身进行保密来确保安全的行为,称为隐蔽式安全性,这种行为是危险的

对称密码

对称密码其实就是 加密和解密过程中使用的密钥是同一个.

XOR

异或操作就是最简单的对称算法
text xorcipher xorcipher = text
因为两个相同的数进行xor结果一定为0 而text和0进行异或仍是text

无法被破译的密码

将明文和一串随机的比特序列进行xor 得到的密文 无论如何也不可能被暴力破解
听起来十分的意外,对吗?
关键在于: 无法判断它是否为正确的明文
当我们尝试破解时,会尝试所有可能的比特组合,而这样,xor后得到的值其实是整个解空间的所有序列,我们就无法判断它是不是明文,所以它是无条件安全的,在理论上是无法破译的.

为什么平常不使用

• 密钥配送 接收者想要解密,必须获得相同的密钥,密钥的长度和明文相同,那这就产生了一个矛盾,如果有一种方法可以将密钥安全发送出去,干嘛发送密钥,直接发送明文就可以
• 密钥保存 一样的,如果可以安全保存等长密钥,没有必要使用该加密手段
• 密钥不可重用
• 密钥生成必须是无重现性的随机数

何时使用

机密性超过一切,花费大量财力人力配送密钥,例如大国之间的热线,特工承担配送密钥任务,直接将比特序列送到对方手中

DES

Data Encryption Standard. (des现在已经可以暴力破解)

算法

• 64 bit明文 --> 64 bit密文 密钥长度64(每隔7位一个错误检测,实际56bit)
• 分组加密 使用feistel网络
• 输入的64bit 分为左32bit 和右 32bit
• 右侧32bit 和子密钥 输入一个轮函数f 生成一个输出
• 输出与左侧32bit xor运算 结果为密文左侧
• 右侧32bit不变 直接成为密文右侧
• 这样右侧根本没有加密,所以使用不同的子密钥对上述处理重复若干次
• 每次重复处理之间,左侧和右侧数据对调

解密

• 按照相反的顺序使用子密钥就可以了,加密解密完全相同

特点

• 轮函数可以是任意的,轮函数可以设计得任意复杂,即使没有反函数也可以

triple-DES

由于DES可以在现实时间内暴力破解,所以设计了3重DES
就是将DES重复三次,称为TDEA或3DES
它是向下兼容DES的,只要3次使用的密钥是同一个,那么相当于只做了一次

算法

明文 --> DES加密(密钥1) --> DES解密(密钥2) --> DES加密(密钥3) --> 密文

AES

AES是为了取代DES成为新的标准设计的,最终选定算法是Rijndael
在AES规格中,分组长度固定为128bit,密钥长度可以是128,192,256三种

算法

由多个轮构成,每一轮分为SubBytes ShiftRows MixColumns AddRoundKey 4个步骤
输入分组为128bit 即16字节

• SubBytes
  一张256值的替换表(S-Box)对16字节每一个值替换为另外一个值,就是个简单替换密码(相当于256个字母)
• ShiftRows
  将16个字节以4个字节为单位的行,按照规则向左平移,并且每一行平移的字节数是不同的
  就是恺撒密码的思想
• MixColumns
  行操作完了,该列了 对每一列4字节的值参与一个矩阵运算,变成另外一个4字节列
• AddRoundKey
  将16个字节分别与轮密钥xor

特点

所有bit在一个轮中都会加密,其中操作多以字节,行,列单位,可以并行计算
目前没有出现针对AES有效的攻击

解密

从后往前,逐一做逆运算

分组密码的模式

前面提到的DES,AES实际上都是分组密码,每次只能处理固定长度明文,如果加密任意长度的明文,就需要迭代,迭代方式就是所谓的模式

ECB

就是最容易想到的,将明文分组,每个分组分别加密,结果直接组合成密文

为什么不好

因为破译者无需破译密码就可以操纵明文, (可以对调分组,篡改顺序!)

CBC

分组链接模式,将明文分组与前一个密文分组进行xor运算然后再进行加密,需要一个初始化向量
应用广泛,SSL/TLS使用的就是CBC

More…还有支持并行的CTR等等

密钥配送

上面介绍了对称密码,不知道你是否注意到一个十分重要的问题,密钥如何安全保密地送达另一方
因为只有同时将密钥给另一方,另一方才能完成解密

解决方案

• 事先共享密钥
  顾名思义,事先将密钥交给对方,可以是物理途径
• 密钥中心分配
  配置一台充当密钥分配中心的计算机,计算机中有数据库,保存着每个人的个人密钥

1. Alice向密钥分配中心发送希望和Bob通信请求
2. 密钥分配中心随机生成一个会话密钥,就是Alice和Bob通信使用的临时密钥
3. 密钥中心取出Alice密钥和Bob密钥
4. 密钥中心用Alice密钥对会话密钥加密交给Alice
5. 密钥中心同样加密Bob密钥,给Bob
6. 各自解密,获得会话的密钥,使用该密钥加密通信
7. 删除临时会话密钥

• Diffie-Hellman密钥交换
• 使用公钥密码

公钥密码

公钥密码(Public-key cryptography) 密钥分为加密密钥和解密密钥两种
发送者用加密密钥对消息进行加密,接收者用解密密钥对密文进行解密

特点:

• 发送者只需要加密密钥
• 接收者只需要解密密钥
• 解密密钥不可以被窃听者获取
• 加密密钥被窃听者获取也无妨

加密密钥一般是公开的,成为公钥,解密密钥不可公开自己使用,称为私钥
显然,公钥和私钥是一一对应的,一对公钥和私钥称为密钥对(key pair),密钥对的两个密钥之间具有非常密切的数学关系
未解决问题:

• 公钥认证 (判断得到的公钥是否正确合法)
• 处理速度是对称密码的几百分之一

RSA

RSA是公钥密码的代表
在RSA中,明文,密钥和密文都是数字
以下公式展示了RSA的加密过程
cipher = text^^E mod N
即密文是对代表明文的数字的E次方mod N的结果 所以(E,N)就是公钥
一下公式展示了RSA的解密过程
text = cipher^^D mod N
即对密文的数字的D次方求mod N就可以得到明文 所以(D,N)就是私钥,由于公钥含有N,也可以说D是私钥

原理

参见 RSA原理

生成密钥对算法

• 求N(p*q)

准备两个很大的素数p q(假设512bit,相当于155位十进制数字,如果素数小, 很容易破译)
要想求出这么大的质数,一般素数筛不行,正确的思路是,随机生成一个512bit的数,然后判断是不是素数,一直> 重复至确实是素数
判断是不是素数的方法也不能用试除法,使用米勒-拉宾测试法(一种概率算法,并不保证准确,但是算的快,openssl迭代64次测试,不是素数的概率也降到2^^-128之下),也有准确的多项式复杂度的算法,但是还是太慢)

• 求L(中间数)

L = lcm(p-1,q-1) 最小公倍数lcm

• 求E

E和L互质(最大公约数1),1 < E < L 要求得E,也是生成(1,L)范围内的随机数,然后判断是否满足gcd(E,L) =1 可以用辗转相除法求gcd

• 求D

D由E计算得到,1< D< L 且 E*D mod L = 1

破解

对N进行质因数分解 但是大数质因数分解依旧是个目前难以计算的问题,所以当pq选取足够大时,RSA安全
若能N分解求得pq,自然可以算的解密密钥

疑惑

人们都不断生成质数对,难道不会用光吗? 不会,实际上512 bit包含的质数,已经超过了宇宙原子数,不会用光的

单向散列函数

所谓的’指纹’,根据一个输入消息产生一个散列值(hash value) 可用于检查完整性

性质

• 根据任意长度的消息计算出固定长度的散列值
• 快速计算
• 消息不同,散列值也不同
  碰撞(两个不同的消息产生同一个散列值)
• 抗碰撞性好 难以认为构造一个跟原散列值相同的输入
• 单向性,无法通过散列值反推输入

常用散列函数

• md4 被攻破
• md5 被攻破 山东大学王小云教授团队(强抗碰撞性)
• sha1 被攻破 同上
• sha2 尚未攻破
• sha3 新标准 keccak算法

攻击

• 暴力破解, 试图破解弱抗碰撞性攻击,改变信息值(如添加冗余数据),直到散列相同
• 生日攻击, 试图破解强抗碰撞性攻击 (王小云提出sha-1仅需要2^^63次尝试) 寻找散列值相同的两条消息

随机数

性质

• 随机性
• 不可预测性
• 不可重现性

生成

• 硬件设备(根据噪音,电流真正的随机)
• 软件 伪随机

伪随机方法

• 线性同余法 广泛使用,不能用于密码技术
  就是将当前的伪随机数乘以A再加上C然后将除于M得到的余数作为下一个为随机数 不具备不可预测性,可以获得下一个值,甚至不需要seed
• 单项散列

cnt = 计数器初始值
while(1)
{
伪随机数 = 单项散列函数求得cnt的散列值
输出伪随机数
cnt++;
}

可以看出,伪随机数生成器内部状态是通过密码保护的

• other algorithm

SSL/TLS

这是当今使用最为广泛的安全传输协议,工作在http,smtp,pop3等下层,相当于密码工具箱,然后组合成了密码套件,协议十分复杂,

思想

假设Alice 通过http想要和Bob秘密通信
则需要一下三点:

• 发送信息不被窃听
• 发送信息过程不能被篡改
• 确认通信的对方是真正的Bob

其实这三点对应: 机密性,完整性,认证

确保机密性,可以使用对称密码,密钥由伪随机数生成器生成,密钥发送给对方用公钥面膜或者Diffie-Hellman密钥交换

确保完整性,防止篡改可以使用消息认证码,认证码由单项散列函数生成

确保认证,对公钥加上数字签名生成的证书

最后

以上就是如意发夹为你收集整理的密码学学习笔记History密码算法与密钥出乎意料的原则对称密码分组密码的模式密钥配送公钥密码单向散列函数随机数SSL/TLS的全部内容，希望文章能够帮你解决密码学学习笔记History密码算法与密钥出乎意料的原则对称密码分组密码的模式密钥配送公钥密码单向散列函数随机数SSL/TLS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。