密码学笔记

1. 概述

1.1 计算机安全概念

网络和Internet安全领域涉及阻止、防止、检测和纠正信息传输中出现的安全违规欣慰的措施。

1.2 OSI安全框架

OSI安全框架主要关注：
安全攻击：任何危机信息系统安全的行为。
安全机制：用来检测、阻止攻击或者从攻击状态恢复到正常状态的过程。
安全服务：加强数据处理系统和信息传输的安全性的一种处理过程或通信服务。
安全在信息系统的范围很广
信息安全
网络安全
计算机安全
数据库安全
软件安全

1.3 安全攻击

四种类型

阻断：使系统被破坏或者无法使用。对可用性的攻击。
破环硬件
切断通信线路
禁用文件系统
DOS/DDOS (拒绝服务)
窃听：未经授权的一方访问信息。对保密性的攻击。
窃听以捕获网络中的数据
非法复制文件/程序
修改：未经授权的一方不仅可以访问还可以修改信息。对完整性的攻击。
更改文件中的数据
改变一个程序
修改消息的内容
伪装：未经授权的一方将假冒的对象插入到系统中。对真实性的攻击。
在网络中插入虚假信息
将记录添加到文件中
改变程序

两种类型

主动攻击：对数据流进行修改或者伪造数据流。难以绝对地预防但容易检测。
伪装
重放
篡改
拒绝服务
被动攻击：对传输进行窃听和检测。**难以检测但可以预防。

泄密
流量分析

1.4 安全服务

保密性：确保隐私或者秘密信息不向非授权者泄露，也不被非授权者所使用。
真实性：信息和信息的来源是正确的，能够验证用户的身份。
完整性：防止信息被不恰当修改或破坏。
可用性：确保信息的及时和可靠的访问和使用。
防止抵赖：防止发送方或者接收方否认传输或者接受过某条消息。
可控性：限制和控制那些通过通信连接对主机和应用进行访问。(eg. 读写权限)

1.5 安全机制 P14 表1.3

1.6 网络安全模型

## 2. 传统加密技术 ### 2.1 密码学概念 ##### 密码学 - 密码编码学 - 密码分析学

基本概念

明文 P：原始可理解的消息或数据，加密算法的输入。
加密算法 E：加密算法对明文进行各种代替和变换。
密钥 K：加密算法的输入。
密文 C：加密算法的输出。
解密算法 D：本质上是加密算法的逆运算。输入密文和密钥，输出原始明文。

古典加密技术

置换：置换符号的位置。eg. SPARTAN SCYTALE(密码棒)
棱柱侧面的数量{x}
算法：明文一维数组->多维数组-行列变换->密文一维数组密文
评价：统计
替换：将明文字母替换成其他字母、数字或符号的方法。eg. Caesar密码
移位的长度 {S}
字符编码后的加法运算
缺点：密钥长度太短
多表代替密码
Auto-key Cipher
Playfair密码：密文仍然完好地保留了明文语言的大部分结构特征。
Vigenère密码：破译能否取得进展取决于能否判定密钥词的长度。
Hill密码：基于线性代数 P30。优点是完全隐藏了单字母频率特性。

2.2 密码学概述

几个概念

Kerckhoff准则：密码系统的安全性不在于算法的保密，而在于当对手获知了算法和密文后分析出密钥或明文的难度。
混淆：尽可能使密文和加密密钥间的统计关系更加复杂，以阻止攻击者发现密钥。
扩散：明文的统计特征消散在密文中。
雪崩效应：明文或密钥的某一位发生变化会导致密文的很多位发生变化。

分组密码与流密码

分组密码：将明文分组作为整体加密并且通常得到的是与明文等长的密文分组。
流密码：每次加密数据流的一位或者一个字节。

密码破解/分析 P23

唯密文攻击
最容易防范的，攻击者拥有的信息量较少。
需要获取更多密文进行分析
已知部分明文攻击
可能词攻击
选择明文攻击
分析者通过某种方式获取信源系统，让发送方在发送的信息中插入一段由他选择的信息。
选择密文攻击
选择文本攻击
蛮力攻击：在一个密文中尝试每个可能的密钥直到获得翻译成可理解的明文。一般需要尝试所有可能密钥的一半。

加密算法的安全

无条件安全：无论有多少可使用的密文，都不足以唯一确定密文所对应的明文。
计算上安全：加密体制满足下面两条中任意一条：
破译密码的代价超出密文信息的价值。
破译密码的时间超出密文信息的有效生命期。
可证明安全：破译密码的难度与数学上某个困难问题的难度相同。
实际安全：包括可证明安全和计算安全

隐写术 / 信息隐藏

隐写术：隐藏信息的存在。
密码学：通过对文本信息的不同转换而实现信息的对外不可读。

3. 分组密码原理

3.1 分组密码和数据加密标准(DES)

乘积密码

P-box(置换)
直接的P-box是可逆的，压缩和扩张的P-box不可逆。
S-bos(替换)
m x n的替换单元，m与n不一定相同。
XOR
相同为0不同为1
A XOR B XOR B = A
循环移位
交换
是循环位移的一个特例，k = N / 2
分离/合并

Feistel密码

Feistel密码是对称加密算法在块加密结构中使用的一种密码结构。
基于可逆的乘积密码。Feistel密码解密是加密的逆过程。
实现了Shannon的S-P net 概念。
Feistel密码的属性：
分组长度
密钥长度
迭代轮数：多轮加密可以取得很高的安全性。
子密钥生成算法
轮函数F：提供“混乱”，非线性，雪崩效应
快速软件加 / 解密
简化分析难度

数据加密标准 DES

DES加密过程：是由2个P-box 初始置换和最终置换、16轮Feistel加密组成。即，除了初始和末尾的置换，DES的结构与Feistel密码结构完全相同。
初始置换和末尾置换是互逆的
DES的核心是DES函数，他将一个48位的轮密钥加到32位的左半/右半部分并得到32位的输出。扩展后的右部分和轮密钥都是48位长度，且轮密钥仅在该轮使用。
DES使用了8个P-box来扩展，每个P-box有4位的输入和6位的输出
S-box做了真正的混淆。DES使用了8个S-box，且每个都有6位的输入和4位的输出
DES解密过程
与加密过程算法相同
使用k₁ -> k₁₆加密
使用k₁₆ -> k₁解密
DES密钥的生成和扩展
64位随机数，丢弃8位重新排列成56位
轮密钥生成器在56位密钥中生成一个48位的轮密钥
16个子密钥由56位密钥分裂成两半，左右两部分各占一半，然后压缩置换他们，为48位的轮密钥。
DES的弱点：
P-box的弱点
S-box的弱点
密钥的弱点：56位密钥有 256 = 7.2×1016，随着计算机的发展，蛮力破解能越来越快地破解DES的密文。
DES的密码分析
微分密码分析
线性密码分析
相关密钥攻击

多重DES

双重DES：2个密钥k₁，k₂
C = E_k₁(D_k₂(E_k₁(P)))
P = D_k₁(E_k₂(D_k₁(C)))
三重DES：3个密钥k₁，k₂，k₃
C = E_k₃(D_k₂(E_k₁(P)))
P = D_k₁(P_k₂(D_k₃(P)))
比DES更安全，但成本更高。

3.2 高级加密标准 AES

数学基础：有限域算术

有限域：Galois域GF(2⁸)
任何一个字节f(x)可以表示为多项式：f(x) = b₇x⁷ + b₆x⁶ + b₅x⁵ + b₄x⁴ + b₃x³+b₂x² + b₁x + b₀
1100101 —> x⁷ + x⁶ +x³ + 1
eg. 91_hex = (1001 0001)_bin = x⁷ + x^{4</sup + 1}
加法运算：：a⊕b（XOR）
封闭性：a∈F，b∈F => a⊕b∈F
交换律：a⊕b=b⊕a
结合律：a⊕（b⊕c）=（a⊕b）⊕c
单位元：0，使得a⊕0 = a
加法逆元：a⊕（-a）= 0（a = -a）
乘法运算：a=f(x), b=g(x), m=m(x), a⊙b=f(x)×g(x) mod m(x)
封闭性：a∈F, b∈F => a⊙b∈F
交换律：a⊙b= b⊙a
结合律：a⊙(b⊙c)= (a⊙b)⊙c
分配率：a⊙(b⊕c)= (a⊙b)⊕(a⊙c)
单位元：1 => a ⊙1=a
乘法逆元：a⊙a-1= 1 mod m
GF(2⁸)模乘法运算；m(x) = x⁸ + x⁴ + x³ + x + 1
{01} ⊙ { b₇b₆b₅b₄b₃b₂b₁b₀ } = { b₇b₆b₅b₄b₃b₂b₁b₀ } 被乘数不发生变化
{02} ⊙ { b₇b₆b₅b₄b₃b₂b₁b₀ } = { b₆b₅b₄b₃b₂b₁b₀ } b7 = 0 的情况
{02} ⊙ { b₇b₆b₅b₄b₃b₂b₁b₀ } ={ b₆b₅b₄b₃b₂b₁b₀ } ⊕ (00011011) b7 = 1 的情况
{03} ⊙ {xx } ={xx} ⊕( {02} ⊙ {xx} )
GF(2⁸)模乘法运算 eg.
{02} ⊙ {2B} = {02} ⊙ { 0010 1011} = { 0101 0110}
{02} ⊙ {91} = {02} ⊙ {1001 0001} = {0010 0010} ⊕ {00011011} = 00111001
{03} ⊙ {6E} = {6E} ⊕( {02}⊙{6E} ) = {0110 1110} ⊕ {10111100} = 10110010

AES的评价标准

NIST于1997年发出了AES的请求，NIST定义的选择AES的标准氛围三个方面：安全、成本、实施。
1998年6月接受了15名候选人。
1999年5个被选入名单：
MARS􏰥IBM􏰦(IBM):􏱪􏲨 扩展Feistel密码， 􏰁􏰂􏰏128位分组，􏱉􏰚􏰷􏰏128-1248位密钥。复杂、快速，安全系数高。
RC6􏰥(USA)：􏰦􏱠128位分组，􏱉􏰚􏰷􏰏128-256位密钥。非常简单、快速，安全系数低。 􏱉􏰁􏰝􏰢􏳹􏰶􏲻􏲇􏰏􏳹􏰶􏳶􏰢􏰆􏰇􏰃􏰻􏳺􏰢 􏱉􏰁􏰝􏰢􏱨􏱩􏲕􏳶􏳷􏰢􏰆􏰇􏰃􏰻􏳸􏰢 􏱉􏰁􏰝􏰢􏱨􏱩􏲕􏳶􏳷􏰢􏰆􏰇􏰃􏰻􏳸􏰢
Rijndael􏰥(Belgium􏰦)：􏱠128位分组，􏱉􏰚􏰷􏰏128 - 256位密钥。干净、快，安全系数良好。
Serpent􏰥(Euro)：复杂、干净，安全系数非常高。
Twofish(􏰥USA􏰦􏱠􏱨􏱩􏲕􏳹􏰶􏳶􏰢􏰆􏰇􏰃􏰻􏳸􏰦􏱠􏳽􏲕􏳻􏳼􏰢􏰆􏰇􏰃􏰻􏳹􏰶􏳸􏰢)：复杂、非常快，安全系数高。

AES算法加密过程

明文分组长度：128位 / 16字节
密钥长度：16字节(128位)，24字节(192位)或32字节(256位)。
轮数：10 / 12 / 14
轮密钥长度：128位
在第一轮开始前添加轮密钥
在最后一回合没有列混淆
加密和解密算法的输入是一个128位分组，这个分组被描述为4 * 4 的字节方阵。这个分组被复制到状态数组，并在加密或解密的各个阶段被修改。
四个不同的阶段
字节替换：加密S盒，解密S盒^-1，S盒必须是可逆的。S盒不是自逆的。 P103 S盒的构造
行移位(以字节为单位)：第1行：不移，第2行：左移1字节，第3行，左移2字节，第4行：左移3字节。
列混淆：
轮密钥加：加密过程中，每轮的输入与轮密钥异或一次（当前分组和扩展密钥的一部分进行按位异或）；因为二进制数连续异或一个数结果是不变的，所以在解密时再异或上该轮的密钥即可恢复输入。轮密钥加是自逆的

AES算法解密过程

是加密过程的逆。
字节变换：加密S盒，解密S盒^-1
列混淆：矩阵C进行加密，矩阵C^-1解密。
反向轮密钥。

AES密钥扩展

AES使用密码扩展算法创建每一轮的轮密钥。如果轮数为Nr，密钥扩展算法会为一个128位(= 16个字节 = 4个字)的加密密钥输出 Nr+1 个轮密钥。
AES密钥扩展算法的输入值是4个字(16字节)，输出是44个字组成的一维线性数组。

AES的实现

AES可以在软件，硬件和固件中实现。实现可以使用表查找过程或使用明确定义的代数结构的例程。
AES中使用的算法非常简单，可以使用廉价的处理器和最少的内存来轻松实现。

AES的安全性

AES是在DES之后设计的。大多数针对DES的已知攻击已经在AES上进行了测试。
蛮力攻击：由于密钥较大，AES肯定比DES更安全。
统计攻击：许多测试未能成功对密文进行统计分析。
差分和线性攻击：目前还没有对AES的差异和线性攻击。

3.3 分组密码的工作模式

更先进的对称密码

IDEA: International Data Encryption Algorithm
1992, Lai Xuejia (来学嘉)
64位分组大小，128位密钥, 8轮
Blowfish
Bruce Schneier, 1993
Feistel密码结构
64位分组大小，32–448位密钥, 16轮
继承者: Twofish
Key Generator
complex
RC5
可变分组大小（32,64或128位），可变密钥大小（0到2040位）和可变轮次数（0到255）。
最初建议的参数选择是块大小为64位，128位密钥和12轮。
继承者：RC6
高级分组密码的特点
可变性：密钥长度，分组大小，轮数，S盒，圆函数
复杂的轮函数生成
执行密钥的更多角色：S盒，圆形移位

分组密码的操作模式

对称加密模式可以使用现代分组密码完成。
操作模式已经被设计以使用DES或AES加密任何大小的文本。
实质上，工作模式是一项增强密码算法或者使算法适应具体应用的技术。

电子密码本 ECB

一次处理一组明文分块，每次使用相同的密钥加密。
ECB评价
消息中若有几个相同的明文组，那么密文也将出现几个相同的密文分组。
􏲒􏰍􏳿􏴀􏱺􏱮􏳾􏰅􏴁􏱅􏴂􏴃􏲒􏰍􏳿􏴀􏱺􏱮􏳾􏰅􏴁􏱅􏴂􏴃无法阻止长消息的修改攻击，
无错误传播：传输中的单个错误可能会在相应块的多个位中产生错误。但该错误对于其他块没有任何影响。（why：因为ECB一次处理一个明文分块，每个明文块使用相同的密钥独立编码。）
ECB适用于：
单个数据的安全传输
eg. 加密密钥，口令

密码分组链接模式 CBC

为了克服ECB的弱点，我们需要将重复的明文文组加密成不同的密文分组。
CBC的输入是当前明文组的上一个密文组的异或，使用的密钥是相同的。
IV 初始向量：为了产生密文的第一个密文块，初始向量IV与第一个明文块进行异或。
IV必须为收发双方共享，但第三方不能预测。为了最大限度的安全。IV不能不经授权而修改。
CBC的加密和解密是互逆的。
CBC方式要求如果最后的分组不是完整的分组，则需要填充至b位的满分组。
P_i = D_K(C_i)⊕C_i-1= D_K(E_K(P_i⊕C_i-1))⊕C_i-1 = P_i⊕C_i-1⊕C_i-1
CBC适用于：
面向分组的通用传输
消息鉴别 / 认证

密码反馈模式 CFB

实时地传输长消息。
解密与加密使用相同的办法，只有一点不同：将收到的密文单元与加密函数的输出异或得到明文单元。这里使用的是加密函数而非解密函数。
与明文异或的位流是与明文相关的。
CFB：错误传播
消息认证
在可靠的信道
CFB适用于：
面向数据流的通用传输
认证

输出反馈模式 OFB

没有错误传播：传输过程中某位上发生的错误不会影响其他位。OFB作为流密码，可以在不可靠信道使用。
不需要将明文填充到长度是分组长度的整数倍。
缺点：抗消息流篡改攻击能力不如CFB
OFB适用于
噪声信道上的数据流传输，瑞卫星通信

计数器模式 CTR

没有反馈。
密钥流的伪随机用计数器来实现。
CTR适用于
面向分组的通用传输，属于数据流的传输
用于高速需求

4. 流密码

4.1 流密码概述

一个典型的流密码每次加密一个字节的明文，产生伪随机密钥流，与明文流的每个字节进行按位异或运算，得到一个密文字节。
“一次一密”使用的是真正的随机数流，而流密码使用的是伪随机数流。
流密码的随机性完全破坏了消息中的统计的性质。
不能重复使用流密码，否则能够恢复消息。而分组密码可以重复使用密钥。
一些需要考虑的方面：
长时间没有重复
统计学上随机
取决于足够大的密钥的线形复杂性
正确设计，可以像具有相同大小密钥的分组密码一样安全，但通常更简单、快速。
流密码：使用分组密码模式——OFB

RC4算法

RC4概述

RC4是流密码，RC5是分组加密算法
RC4是一个面向字节的流密码，其中明文的一个字节与一个密钥字节进行X-存储，以产生一个密文字节。
RSA DSI的私有的密码
另一个是Ron Rivest设计于1987年，简单、有效：
可变长度的密钥，面向字节的流密码
广泛使用（网络SSL / TLS，无线WEP）
密钥形成所有8位数的随机排列，使用该排列来搅乱一次处理一个字节的输入信息

RC4算法

基本描述
可变长度密钥K：1-256个字节(8-2048位)。密钥K的长度keylen与明文长度、密钥流长度无关，通常取16字节(128bits)
状态向量S：256个字节，S的元素记为S[0], S[1], … , S[256]。从始至终置换后的S包含从0-255的8位数，只不过位置发生了变化
临时向量T：256个字节，每个单元也是一个字节。如果密钥K的长度是256字节，则直接把密钥的值赋给T，否则轮转地将密钥的每个字节赋给T。
密钥流：密钥流的长度和明文的长度是对应的(相等)
RC4算法具体描述：
初始化S和T
S的初始置换
密钥流的生成
加密时将k的值与明文的下一字节异或；解密时将k的值与密文的下一个字节异或。
RC4的安全性
声称可以抵御已知攻击
有一些分析，没有实际意义
结果是非线性
由于RC4是流密码，因此不能用重复的密钥
关注WEP，但由于是密钥处理而不是RC4本身

RC4 3bits

是RC4算法的一个变体。
可变长度的密钥：3位 - 24位
24位的状态向量S的元素：S[0], S[1], … , S[8]
eg.
明文：(7 2 5 1 5)_oct = {111 010 101 001 101}_bin
密钥：(7 4 3 2)_oct = {111 100 011 010}_bin (密钥长度 = 4*3bit=12)
初始化：
初始置换：
密钥流的生成：

5. 密钥管理和分发

密钥分发历史

在第二次世界大战期间，德国高级司令部不得不将其每月的日记账分发给其所有谜运营商。而且，U型船往往需要长时间远离开基地，不得不以某种方式获得定期供应的钥匙。
美国政府的密钥由COMSEC管理和分发。在20世纪70年代，COMSEC负责每天运输大量的钥匙。当携带COMSEC材料的船舶进入码头时，密码管理机构将在船上行进，收集成堆的卡片，纸带，软盘，然后将它们交付给目标收件人。

密钥分发模型 P319

A选择一个密钥后以物理的方式(安全)传递给B。
第三方选择密钥后物理地传递给A和B。
如果A和B先前或者最近使用过一个密钥，则一方可以将新密钥用旧密钥加密后发送给另一方。
如果A和B到第三方C有加密连接，C可以在加密连接上传送密钥给A和B。
第三方加密：**密钥分发中心(KDC)**负责根据用户的需要来分发密钥。

密钥分发中心 KDC

密钥分发中心是基于密钥层次体系的，最少需要两个密钥层。
会话密钥：用于持续时间的逻辑连接，如帧的转发或传输连接，然后随着连接的断开而丢弃。
主密钥：用户和KDC共享的唯一的主密钥。用于会话密钥的加密分发。
主密钥的分发可以通过一些不加密的方式完成，如物理传递
评价：
在两个人可以交换秘密之前，他们必须已经分享了一个秘密。
大量的会话密钥通过互联网进行分发。

密钥分配方案

Needham/Schreoder 认证协议：KDC P321
Denning认证协议 : timestamps
Neuman协议：

层次密钥控制

对于大型网络，需要建立KDC的层次体系。
同一个本地域的各个实体相互通信，由本地KDC负责密钥分发。
两个实体在不同域，由两个相对应的本地KDC通过全局KDC协商产生共享密钥。
层次策略使得主密钥分发的开销最小化。

会话密钥的生命周期

会话密钥交换得越频繁就越安全。密钥分发会延迟交换的开始时间，增加网络负担。
对于面向连接的协议，在会话的整个生命周期中使用同一个会话密钥。
对于无连接的协议，没有明确的连接初始和终止。最安全的方法是每次都使用新的会话密钥，但开销变大。

控制密钥的使用

数据加密密钥，用于网络中通用通信
PIN加密密钥，用于电子资金过户的销售点应用的个人识别码(PIN)
文件加密密钥：用于存储可公开访问的加密文件。

6. 密钥交换

6.1 Diffie-Hellman 密钥交换

加密和解密的密钥不同。(私钥和公钥)
相比对称加密的密钥分发，不用等待获取会话密钥，然后才能加密和发送消息。
基于一个单向函数：K = ( Y_B )^X_A mod q = ( Y_A )^X_B mod q
Diffie-Hellman算法的有效性建立在计算离散对数是很困难的这一基础上。
算法流程： P218 具体计算
缺点：不能抵抗所谓的中间人攻击。

6.2 RSA算法

数论

数论的核心问题：质数
因子分解定律：任何大于1的整数a都可以被这样分解：a = p₁^a₁ x p₂^a₂ x … x p_k^a_k，p₁ > p₂ > … > p_k
eg. 11011 = 7 x 11² x 13
**素数有无限多个 **
同模：两个整数如果a mod n = b mod n，则称a与b同模
eg. 73 mod 23 = 4, 73 = 4 mod 23，则称4与73同模。
模运算的性质：
定义：a mod n = b mod n → a ≡ b mod n
交换律：a ≡ b mod n → b ≡ a mod n
传递律：a ≡ b mod n & b ≡ c mod n → a ≡ c mod n
有前提条件的消除律：如果a与n互质，则a x b ≡ a x c mod n → b ≡ c mod n
**gcd(a, b)**：表示a和b的最大公约数。
a与b互质，则gcd(a, b) = 1
模乘的逆：
定义Z_n为正整数小于n的集合：Z_n = {0, 1, …, (n-1)}
模乘的逆w^-1 ：对于每个w ∈ Z_p，ョz，w * z ≡ 1 mod p ，称z为w^-1
费马定理 / 费马小定理：
p是一个质数，a是一个不能被p整除的正整数，则a^p-1 = 1 mod p
eg. a = 6, p = 7, 6^7-1 ≡ 1 mod 7
另一种形式：p是一个质数，a是一个正整数。则a^p = a mod p
eg. a = 3, p = 5, 3⁵ = 243 ≡ 3 mod 5
欧拉函数
定义 φ(n) 为小于n且与n互质的正整数。
如果p为一个素数，那么φ(p) = p - 1
如果n = p₁^a₁ p₂^a₂ … p_k^a_k 是素数分解的n，那么
欧拉定理
对于任何互质的a和n，a^φ(n) ≡ 1 mod n，或者 a^φ(n)+1 ≡ a mod n
欧拉定理的推论
给定两个素数p和q，以及整数n = pq，且0 < m < n
m^φ(n)+1 = m^{(p - 1)(q - 1) + 1} ≡ m mod n
对任意整数k有：[m^φ(n)]^k ≡ 1 mod n 或 m^kφ(n) ≡ 1 mod n
m^kφ(n)+1 = m^{k (p - 1)(q - 1) + 1} ≡ m mod n

RSA算法描述

对于明文分组M和密文分组C，加密和解密过程如下：
C = M^e mod n (加密)
M = C^d mod n = (M^e)^d mod n = M^ed mod n (解密)
其中，收发双方均已知n，发送方已知e，且只有接收方已知d，因此公钥加密算法的公钥PU = { e, n }，私钥PR = { d, n }
必须满足以下条件：d 和 e 是模 φ(n) 的乘法逆元。即 d 与 φ(n) 互质（因此 e 也与 φ(n) 互质）
ed = kφ(n)+1
ed ≡ 1 mod φ(n)
d ≡ e^-1 mod φ(n)
gcd( φ(n), d) = 1 ），gcd( φ(n), e) = 1 ）

RSA密钥产生

选择(大)质数p, q（私有）
计算 n = p * q
计算 φ(n) = ( p - 1 )( q - 1 )
选择 e：gcd( φ(n), e) = 1 ）1 < e < φ(n)
计算 d ≡ e^-1 mod φ(n)（如何计算d -> 扩展欧基里德算法）
公钥PU = { e, n }，私钥PR = { d, n }

RSA的安全性

给定n确定p和q是不可行的
给定e和d确定d是不可行的
因子分解问题：对于有大素数因子的数字n，因式分解是个难题。
RSA密钥非常大所以很安全： 1024 / 2048 位
1994年，彼得肖尔表明，量子计算机可以将多项式时间（多项式时间）考虑在内，从而打破了RSA。如果n是300位或更短，则可以在个人计算机上在几个小时内计算出来截至2008年，通用分解算法考虑的最大（已知）数量是663位长（参见RSA-200），使用最先进的分布式实现。下一个记录可能是768位模数
RSA 秘密研制于上个世纪60年代初，用于控制战略导弹的发射. 70年代被麻省理工学院等高校的教授独立发明，建立在数论，特别是很难对大素数之积进行因式分解的基础之上。
一旦量子计算机投入实用，将给目前的公共加密技术带来极大威胁。

公钥算法与对称加密

从最早开始到现代，虚拟（事实上）所有加密系统都基于替代和排列的基本工具。
公钥算法基于数学函数而不是替换和置换。
公钥密码可用于
加密/解密
电子签名
密钥交换/管理
应该提到一些关于PKC的常见误解（误解）：
PKC比对称密钥加密更安全(✕)
PKC是一种通用技术，传统密码已经过时(✕)
使用PKC时，密钥分发没有意义(✕)

7. 消息认证

7.1 安全服务

对称密钥密码：使用相同的会话密钥K_s进行/解密。
使用非对称密钥密码（RSA）来传递会话密钥K_s。
已经被提出的5种信息攻击/安全问题
泄露
流量分析
冒充
篡改：内容 / 顺序 / 时间篡改
拒绝服务 / 推诿
解决方法：
信息保密：泄露，流量分析
数字签名：拒绝服务/推诿
消息认证：冒充，篡改

7.2 消息认证

消息认证

消息认证：验证所受到的消息确实是来自真正的发送方，且是未被修改的消息，也可以验证消息的顺序和及时性。
数字签名是消息认证机制之一。
不同级别的消息认证：消息身份验证的两个基本级别部署机制
基础 - 低级别：身份验证
消息加密
消息认证码(MAC)
Hash函数
应用 - 高级别：身份认证协议
PGP ( Pretty Good Privacy)
Kerberos
对于对称加密，提供：
保密
消息认证(eg. CBC模式)
对于公钥加密，提供：
消息认证：发送方用自己的私钥给消息加密，它提供了数字签名。
保密：发送方用接收方的公钥给已加密的消息再次加密，提供了保密性。

消息认证码

利用密钥来生成一个固定长度的短数据块，并将该数据块附加在消息之后。
假设A和B共享一个密钥，当A向B发送消息时：
A计算MAC，它是消息和密钥的函数：MAC = C_K(M)
消息和MAC一起发送给接收方B
当接收到消息后，B用同样的方式计算出MAC，并与接收到的MAC进行比较：MAC’ = C_K(M)
如果MAC = MAC’ 则消息得到认证。
MAC函数与加密类似，但是MAC算法不要求可逆性，而加密算法必须可逆。
MAC函数不能提供数字签名机制。MAC使用对称加密，既然一方能够验证你的MAC，就能够伪造你的MAC，因为发送方和接收方的秘钥是一样的。
消息摘要与MAC的区别
消息摘要只能保证消息的完整性。攻击者可以将原始消息和摘要都篡改成新的消息和摘要。而MAC由于是消息和密钥的函数，攻击者无法生成与篡改后内容匹配的MAC。
MAC不仅能够保证完整性，还能够保证真实性

Hash函数 P239

发送者根据待发送的消息使用Hash函数计算一组Hash值，然后将Hash值和消息一起发送过去。
使用Hash函数的原因：
加密软件速度慢
加密硬件成本不容忽视
加密硬件的优化通常是针对大数据的
加密算法可能受专利保护
加密算法受美国出口管制
哈希函数的要求 P245

H（x）可以应用于任何大小的数据块x
H（x）产生固定长度的输出
3.对于任何给定的x，H（x）相对容易计算，使得硬件和软件实现都是现实的。
单向性：对于任何给定的代码h，它是计算上的不可能找到x使得H（x）= h。
弱碰撞阻力：对于任何给定的x，找到y≠x -> H(y) = H(x)在计算上是不可行的。
6.强抗碰撞性：找到任何（x，y）使得H（x）= H（y）在计算上是不可行的。

两个简单的Hash函数：
最简单的Hash函数是每个块的逐位异或：C_i = b_i1 ⊕ b_i2 ⊕ … ⊕ b_im
Hash算法包括重复地使用一个压缩函数f：输入为链接变量(上一步的n位输入)和一个b位的块，产生一个n位的输出。P248
Hash函数的应用
消息摘要
密码/口令保护
防止重放攻击：用户和Auth Sever秘密共享一个seed，Hash^{N-x(seed)，N是一个很大的初始值，x是登录验证的次数。(重放攻击是指攻击者发送一个目的主机已接收过的包，来达到欺骗系统的目的，主要用于身份认证过程，破坏认证的正确性。)}

安全Hash算法 SHA

SHA-1 来自 MD4
SHA-2 family：SHA-224, SHA-256, SHA-384和SHA-512

消息摘要

MD5消息摘要算法
MD5消息摘要算法由1990年麻省理工学院的Ron Rivest创建
它将任意长度的消息(但会分成512bits一组)作为输入并产生128位消息摘要作为输出。

8. 数字签名

8.1 数字签名简介

数字签名

数字签名或数字签名方案是用于证明数字消息或文档的真实性的数学方案。
有效的数字签名使接收方有理由相信该消息是由已知接收方创建的，并且该邮件在传输过程中未被更改。
数字签名通常用于软件分发，金融交易，以及其他情况需要检测修改的情况。

数字签名的特征

能验证签名者、签名日期和时间
能认证被签的消息内容
签名应能由第三方仲裁，以解决争执

数字签名需求

签名必须是与消息相关的二进制串
签名必须使用发送方某些独有的信息，以防伪造和否认
产生、识别和验证数字签名比较容易
伪造数字签名在计算上是不可行的
保存数字签名副本是可行的

数字签名过程 P300

数字签名需要公钥系统。
签名者用他的私钥签名，验证者使用签名者的公钥进行验证。

数字签名提供的安全服务

消息验证
消息完整性
防止抵赖
消息完整性

8.2 数字签名方案

RSA数字签名方案 P305

8.3 用户认证协议 P348

Kerberos

Kerberos概述：
Kerberos是一种计算机网络认证协议，它允许通过非安全网络进行通信的节点以安全的方式相互证明其身份。
它也是麻省理工学院出版的一套免费软件，它实现了这个协议。
麻省理工学院开发了Kerberos来保护Project Athena提供的网络服务
存在多种版本的协议; 版本1-3仅在麻省理工学院内部发生。
版本4发表于20世纪80年代后期
版本5在1993年作为RFC 1510出现
一个全方位服务的Kerberos环境包括：
1个Kerberos服务器
多个客户端
多个应用服务器
Kerberos环境要求：
Kerberos服务器必须具有该用户ID和密码
Kerberos服务器必须与每一个服务器共享密钥

这种环境被称为领域

X.509

X.509是用于单点登录（SSO）和权益管理基础设施（PMI）的公钥基础设施（PKI）的ITU-T（国际电信联盟）标准。
X.509除其他外指定了公钥证书，证书撤回列表，属性证书和证书路径确认算法的标准格式。
有关X.509的详细信息，请参阅第14.2节或维基百科

8.4 PGP P445

PGP概述

Pretty Good Privacy（PGP）是一种提供加密隐私和身份验证的计算机程序。
PGP通常用于签名，加密和解密电子邮件，以提高电子邮件通信的安全性。
它由Philip Zimmermann于1991年创建。
PGP和其他类似产品遵循OpenPGP标准（RFC 4880）来加密和解密数据。
PGP-用户认证：P448
PGP-保密：
PGP-保密且认证