2024-3-15 14:44:26

数据结构

二叉树

树的表示方法：
双亲表示法
孩子表示法
孩子兄弟表示法

完全二叉树

编号1~n

左孩子 2*i，右孩子在2*i+1

满二叉树

最后一层都满了

层数：1…k
结点数量和为2^k-1

BST 二叉排序树|二叉搜索树

中序遍历是有序的

			4 2  			6
1 			3   5			7

AVL 平衡二叉树

平衡因子的绝对值不超过1
左右子树深度差

B树 多路平衡查找树

多路：不只二叉
平衡：平衡
查找：查找

B+树

信息只存储在叶子节点上

红黑树

特殊的二叉树

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )
4. 如果一个节点是红色的，则它的两个孩子结点是黑色的
5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

哈夫曼树

变长编码
前缀编码：任何符号的编码不能是其他编码的前缀

构造过程：
计算频度
找出最小的两项结点，合并为新结点
继续找

散列

开放定址法
线性探测再散列：F=i+k
二次探测再散列：F=-1² 1² -2² 2²,…

链地址法
HashMap

再散列
布隆过滤器

计算平均查找长度

操作系统面试题

期末复习【操作系统】

操作系统复习【面试】

操作系统笔记【面试】

面试之八股文——计算机网络和操作系统

并行和并发

并发：单核CPU宏观上同时执行多个任务，微观上是分时交替执行多个任务；类似于时间片轮转算法
并行：多核CPU同时执行多个任务

什么是进程？进程和程序的区别？

进程是程序的一次执行

进程是动态的，程序是静态的

进程创建需要CPU的资源，分配内存，进程控制块

进程的基本状态

就绪，执行，阻塞

创建，终止

什么是线程？线程和进程的区别？

进程是操场系统资源拥有的最小单位
线程是操作系统调度的最小单位

进程控制块：PCB
线程控制块：TCB

TCB比PCB小
有程序计数器…等等线程私有的东西

哪些是线程的私有资源

在一个进程中，线程之间可以共享以下资源：

内存空间：线程共享相同的地址空间，也就是说它们可以访问相同的全局变量和静态变量。

文件描述符：每个线程都可以访问进程打开的文件。

代码段：所有线程都可以访问进程的代码段，也就是说它们执行相同的指令。

而线程有一些私有的资源，包括：

栈空间：每个线程都有自己的栈空间，用于存储局部变量、函数调用信息和返回地址等。

寄存器：每个线程有自己的寄存器集，用于存储正在执行的指令和相关的数据。

线程上下文：线程上下文包括线程的状态信息，例如程序计数器、寄存器值和栈指针等。

栈指针：每个线程都有自己的栈指针，指向线程的栈顶。

需要注意的是，线程共享的资源需要进行同步和互斥操作，以避免数据竞争和并发访问的问题。常用的同步机制包括互斥锁、条件变量和信号量等。

操作系统中线程的状态

三个基本状态：执行、就绪、阻塞

创建，终止

Java中线程的状态

1. 新建状态(New): 线程对象被创建后，就进入了新建状态。例如，Thread thread = new Thread()。

2. 就绪状态(Runnable): 也被称为“可执行状态”。线程对象被创建后，其它线程调用了该对象的start()方法，从而来启动该线程。例如，thread.start()。处于就绪状态的线程，随时可能被CPU调度执行。

3. 运行状态(Running): 线程获取CPU权限进行执行。需要注意的是，线程只能从就绪状态进入到运行状态。

4. 阻塞状态(Blocked): 阻塞状态是线程因为某种原因放弃CPU使用权，暂时停止运行。直到线程进入就绪状态，才有机会转到运行状态。阻塞的情况分三种：

   • (01) 等待阻塞 – 通过调用线程的wait()方法，让线程等待某工作的完成。
   • (02) 同步阻塞 – 线程在获取synchronized同步锁失败(因为锁被其它线程所占用)，它会进入同步阻塞状态。
   • (03) 其他阻塞 – 通过调用线程的sleep()或join()或发出了I/O请求时，线程会进入到阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态。

5. 死亡状态(Dead): 线程执行完了或者因异常退出了run()方法，该线程结束生命周期。

进程的同步

信号量进制
整型信号量
记录型信号量
AND型信号量
信号量集

管程机制

线程通信

共享内存机制和消息传递机制两种

• 共享存储器系统
  基于共享数据结构的通信方式 基于共享存储区的通信方式
• 消息传递系统
  直接通信方式 间接通信方式
  消息 邮箱
• 管道通信系统
  连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。
• 客户机—服务器系统
  套接字、远程过程调用和远程方法调用

三种调度

低级调度：进程调度

中级调度：页面置换

高级调度：作业调度

进程调度算法

第三章 处理机调度和死锁【操作系统】：2.作业与作业调度

第三章 处理机调度和死锁【操作系统】：3.进程调度

• 先来先服务调度算法
• 最短作业优先调度算法
• 高响应比优先调度算法
• 时间片轮转调度算法
• 最高优先级调度算法
• 多级反馈队列调度算法

什么是死锁

第三章 处理机调度和死锁【操作系统】：5.死锁概述

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程就是死锁的(Deadlock)。

产生死锁的原因

竞争资源
进程间推进顺序非法

死锁的必要条件

(1) 互斥条件

(2) 请求和保持条件

(3) 不可抢占条件

(4) 循环等待条件

怎么处理死锁

处理死锁的方法

(1) 预防死锁
破坏死锁的必要条件：
1.摒弃“请求和保持条件”：进程在开始运行之前，都必须一次性的申请其在整个过程中所需的全部资源
2.摒弃“不可剥夺”条件：当一个已经保持资源的进程，提出新的资源申请而没有得到满足时，必须释放它已经保持了的所有资源，待以后再重新申请
3.摒弃“环路等待”条件：为所有资源按类型进行线性排队，并赋予不同序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出。

(2) 避免死锁
1银行家算法
2安全性算法

(3) 检测死锁
1资源分配图
2死锁定理
资源分配图是不可完全简化的
(4) 解除死锁
1剥夺资源
2撤销进程

Mysql的死锁检测：超时检测
解除：回滚执行花费少的事务

动态分区分配算法

基于顺序搜索的动态分区分配算法

顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。

1.首次适应（first fit，FF）算法

2.循环首次适应（next fit，NF）算法

3.最佳适应（best fit，BF）算法

4.最坏适应（worst fit，WF）算法

基于索引搜索的动态分区分配算法

1.快速适应算法

2.伙伴系统

3.哈希算法

虚拟存储

物理上扩容很简单，加内存条
逻辑上扩容，采用虚拟存储

实现方式：页面的调入调出

目的是：用磁盘来代替内存，降低成本

页面置换算法

第五章 虚拟存储器【操作系统】：5.3 页面置换算法

• 最佳页面置换算法（OPT）
• 先进先出置换算法（FIFO）
• 最近最久未使用的置换算法（LRU）
• 时钟页面置换算法（Lock）

 简单Clock置换算法，为每一页设置一位访问位A，内存中所有页面构成循环队列，被访问时访问为置为1。淘汰时，检查访问位，为0直接换出，为1，重新将它置0，暂不换出，而给该页第二次驻留内存的机会。检查到最后时仍为1，再返回队首重新检查也称为最近未用NRU算法改进型Clock置换算法：还有考虑M置换代价
A=0，M=0 最佳淘汰页
1）从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，
将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，
寻找 A=0 且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。
在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，
并已将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，
此时就一定能找到被淘汰的页。
该算法与简单 Clock 算法比较，
可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页，
可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。

• 最少使用置换算法（LFU）

对I/O设备的控制方式

1. 使用轮询的可编程I/O方式

2. 使用中断的可编程I/O方式

3. 直接存储器(DMA)访问方式

4. I/O通道控制方式

磁盘调度算法

第六章 输入输出系统【操作系统】：6.8 磁盘存储器的性能和调度

• 先来先服务算法
• 最短寻道时间优先算法
• 扫描算法
• 循环扫描算法
• NStepSCAN与 FSCAN 算法

计算机组成原理

---

导航【计算机组成原理】

期末复习【计算机组成原理】

---

CPU缓存：L1 L2 L3

CPU缓存【笔记】

---

主从与cache的地址映射

1.全相连映射方式
这种方法可使主存的一个块直接拷贝到cache中的任意一行上，非常灵活。
　它的主要缺点是比较器电路难于设计和实现，因此只适合于小容量cache采用。

2.直接映射方式
直接相连映射方式的优点是硬件简单，成本低。缺点是每个主存块只有一个固定的行位置可存放,容易产生冲突。因此适合大容量cache采用。

3.组相连映射方式
组相联映射方式中的每组行数v一般取值较小，这种规模的v路比较器容易设计和实现。而块在组中的排放又有一定的灵活性,冲突减少。

---

I型 R型 J型指令设计

计算机系统结构

---

导航【计算机系统结构】

期末复习【计算机系统结构】

---

系统加速比

Amdahl定律

加速比=1/[(1-可改进比例)+可改进比例/部件加速比]

Cache

期末复习【计算机系统结构】：第5章 存储系统

映像规则

1. 全相联映像
   主存中的任一块可以被放置到Cache中的任意一个位置。
   特点：空间利用率最高，冲突概率最低，实现最复杂

2. 直接映像
   主存中的每一个块只能被放到Cache中唯一一个位置。
   特点：空间利用率最低，冲突概率最高，实现最简单

3. 组相联映像
   Cache被等分成若干组，每组由若干个块构成。主存中的每一块可被放到Cache中唯一一个组的任何一个位置。组的选择常采用位选择算法：

Cache性能分析

平均访存时间＝命中时间＋不命中率×不命中开销
所以可以从三个方面来改进Cache的性能：降低不命中率、减少不命中开销、减少命中时间

降低Cache不命中率

三种不命中：强制性不命中 容量不命中 冲突不命中
增加Cache块的大小
增加Cache块的容量
提高相联度
伪相联Cache
硬件预取
编译器控制的预取
编译优化
牺牲Cache

减少Cache不命中开销

采用两级Cache
让读不命中优先于写
写缓冲合并
请求字处理技术
非阻塞Cache技术

减少命中时间

容量小、结构简单的Cache
虚拟Cache
Cache访问流水化
踪迹Cache
Cache优化技术总结

计算机网络

计算机网络笔记【面试】

计算机网络面试题【面试】

期末复习【计算机网络】

计算机网络的层次划分

OSI七层网络：物理层、数据链路层、网络层、运输层、会话层、表示层、应用层

TCP\IP四层网络：网络接口层、网际层IP、运输层、应用层

教学原理五层网络：物理层、数据链路层、网络层、运输层、应用层

输入URI的一个过程

2.2 键入网址到网页显示，期间发生了什么？

---

应用层 从应用到应用
没有连接到网络：ERR_INTERNET_DISCONNECTED
连接到：DHCP 分配IP地址

HTTP（TCP）
DNS（UDP）
访问默认的DNS服务器：8.8.8.8|114.114.114.114
域名->IP

---

运输层 从端到端
TCP
连接管理 流量控制 拥塞控制

---

网络层 从路由器到路由器
IP
ICMP：ping traceroute
ARP：IP转为MAC地址
目的IP和本机IP是否在同一网络：目的IP&掩码==网络前缀
不在就是间接交付，访问默认网关

路由器的配置：RIP BGP

---

数据链路层 从交换机到交换机
封装成帧 透明传输 差错检测
MAC地址 交换机逆向学习源地址
转发异网帧 过滤本网帧 广播未知帧

---

物理层 从线路到线路
传输bit流

---

UDP

UPD是用户数据报协议

报文格式：UDP首部+数据

UDP首部（8）：目的端口（2）、源端口（2）、长度（2）、校验和（2），单位是字节

特点：
无连接 尽最大努力交付 面向报文 没有拥塞控制 支持一对多，多对一，多对多 首部开销小

应用场景：
对实时要求高的，不允许丢失要求不高的
语音、视频通话 游戏
DHCP DNS都是基于UDP的

TCP

TCP 是面向连接的、可靠的、基于字节流的传输层通信协议。

报文格式：TCP首部+数据

TCP首部格式目的端口、源端口、序号、确认号、标志位（SYN ACK FIN）、选项（窗口扩大 时间戳 选择确认）、填充、等等

固定20字节，最大60字节

特点：
面向连接的运输层协议 一对一（端到端） 可靠交付 全双工 面向字节流

应用场景：
对实时要求不高的，不允许丢失要求高的
文件传输
HTTP FTP就是基于TCP的

TCP的流量控制

用滑动窗口来实现流量控制的

发送窗口，不能大于接受方的接受窗口

防止上一次发送方接受到0窗口通知，但是后续的窗口扩大了，因为网络问题，接收不到

造成死锁，发送方发送不了数据，接收方有在等待发送数据

设置持续计时器，当收到零窗口通知时，启动计时

发送零窗口探测报文（仅携带1字节数据），如果后续还接收到0窗口通知就不发送，否则就开始发送，不超过其接受窗口

问题：如何控制发送报文段的时机：
不是收到一个确认，就发送下一个报文段
Nagle（纳格尔）算法：
先发送一个数据字节，然后把后续到来的数据字节缓存起来，收到确认，就把缓存中的全部发送出去，继续缓存后续字节

问题：糊涂窗口综合征
应用进程每次在接受缓存中处理一个字节，导致每一次发送的接受窗口大小都是1字节
解决：可以让接收方等待一段时间，使得或者接收缓存已有足够空间容纳一个最长的报文段，或者等到接收缓存已有一半空闲的空间。只要出现这两种情况之一，接收方就发送确认报文，和通知接受窗口的大小

上述两种方法可配合使用。使得在发送方不发送很小的报文段的同时，接收方也不要在缓存刚刚有了一点小的空间扰急忙把这个很小的窗口大小信息通知给发送方。

TCP的拥塞控制

慢开始：从1开始，每收到一个确认，拥塞窗口（cwnd）就加一（每一个RTT就加倍），直到门限值

拥塞避免：门限值之后，每一个传输轮次（RTT）加一，到超时0，就把新门限值设置为当前的拥塞窗口的一半，重新慢开始

快重传：当收到三个ack相同的报文，发送方就会快速发送这个序号的数据包

快回复：当收到三个ack相同的报文，引起的网络阻塞，不是进行慢开始，而是直接开始拥塞避免，从新门限开始

加法增大、乘法减小（AIMD）

TCP的连接管理

红蓝问题：没有完全可靠的网络传输协议

三次握手

客户端A主动打开连接，服务端B被动打开连接

开始时，服务端开启端口，接受请求，进入接听（Listen）状态

A：发送[SYN]包，SYN=1，seq=x，进入 SYN-SEND（同步已发送）状态

B：发送[SYN，ACK]包，SYN=1，ACK=1，seq=y，ack=x+1，进入SYN-RCVD（同步收到）状态

A：发送[ACK]包，ACK=1，sqq=x+1，ack=y+1，进入已建立连接（ESTABLISHED）状态；B收到后也进入已建立连接（ESTABLISHED）状态

为什么是三次握手，而不是两次或四次

四次的话，就是原先第二次握手，SYN ACK分开发送，但是有点浪费资源，能一次发送的

两次的话，就是删掉第三次握手。可能会已失效的连接请求报文段，重新建立连接

比如：A第一次发送SYN包，但是被网络拥塞了；之后又发送了SYN包，建立了链接，然后又释放了。
但是这是A第一次发送SYN包，又到了B，B接受了，处于连接状态了，但是A是不会给其发送数据的，使得B在苦等

四次挥手

客户端，服务器都可以先发送

A：发送[FIN]包，FIN=1，seq=u，主动关闭，进入FIN-WAIT-1（终止等待1）状态

B：发送[ACK]包，ACK=1，ack=u+1，被动关闭，进入CLOSE-WAIT（关闭等待）状态；A收到了进入FIN-WAIT-2（终止等待2）状态

此时，已关闭A->B的数据连接，TCP连接处于半关闭状态。
B->A，B仍可以发送数据，A依然接受
TCP是全双工的

B：发送[FIN]包，FIN=1，seq=v，进入LAST-ACK（最后确认）状态

A：发送[ACK]包，ACK=1,seq=v+1，进入TIME-WAIT（时间等待）状态，等待2MSL之后，如果没有再次接受，就CLOSE状态；B收到就进入CLOSE状态

MSL：最长报文寿命，2分种

问题：为什么，要等待2MSL？
为了保证A最后一次ACK达到B，使得B正确关闭；如果B没有收到此报文，将快速重传，让A发送。

问题：为什么是四次挥手，而不是三次
三次挥手，就是把第四次挥手删掉；
防止已失效的连接再次建立

保活计时器：没收到一个数据，就重新计时；当客户端意外故障关闭了，在2小时之后发送10个探测报文，没有响应就关闭连接

协议

ARP协议：
根据IP地址出MAC地址
ARP请求，广播发送
ARP响应，单播发送

ICMP协议
ping：ICMP询问报文
tracerouter：ICMP差错报告报文

DNS
域名解析协议
域名换成IP地址

递归查询：
主机->本地域名服务器->根域名服务器->顶级域名服务器->权限域名服务器；
权限域名服务器->顶级域名服务器->根域名服务器->本地域名服务器；
本地域名服务器->主机

迭代查询：（指路不带路）
主机->本地域名服务器；
本地域名服务器->根域名服务器；
本地域名服务器->顶级域名服务器；
本地域名服务器->权限域名服务器
本地域名服务器->主机；

DHCP（客户端68 服务器67）
动态获取IP地址，有租期的
dhcp release，主动解约
dhcp renew，主动解约

补充

tcp三次握手为什么不是两次

TCP三次握手是为了建立可靠的通信连接，确保双方都能够正常收发数据。三次握手的过程如下：

1. 客户端向服务器发送一个连接请求报文段（SYN）。
2. 服务器收到请求后，如果同意连接，则会发送一个确认报文段（SYN+ACK）作为回应。
3. 客户端收到服务器的确认后，再次向服务器发送一个确认报文段（ACK）。

为什么不是两次握手呢？主要有以下两个原因：

1. 可靠性：通过三次握手，可以确保客户端和服务器都确认了对方的存在和能力，避免了因为网络延迟或其他原因引起的错误连接。

   • 在两次握手的情况下，如果客户端的连接请求报文段丢失，服务器将无法确认客户端的请求，从而无法建立连接。
   • 在三次握手的情况下，即使客户端的连接请求报文段丢失，服务器能够发送自己的确认报文段，客户端收到后也能够确认服务器的存在。

2. 防止已失效的连接请求报文段重复发送导致的问题：考虑这样一种情况，客户端发送了一个连接请求报文段，但是由于网络问题或其他原因导致客户端没有收到服务器的回应。如果客户端再次发送一个连接请求报文段，但是第一个连接请求报文段在网络中延迟到达，这时服务器就会误认为客户端新发送的连接请求，从而建立了两个连接。为了避免这种情况，引入了第三次握手，确保服务器收到客户端的确认报文段后，才正式建立连接。

主要还有syn,ack标志位的同步来解决历史重复连接的问题

综上所述，通过三次握手可以更好地保证通信连接的可靠性和防止错误连接的发生。

如果TCP是两次握手应该怎么发送两次握手包

如果TCP只进行两次握手，发送两次握手包的过程可以这样描述：

1. 客户端发送一个连接请求报文段（SYN）给服务器。
2. 服务器收到请求后，如果同意连接，则立即发送一个确认报文段（SYN+ACK）给客户端。
3. 客户端收到服务器的确认后，建立连接，此时连接已建立。

在这种情况下，没有第三次握手，建立连接的过程相对简单。然而，这样的连接建立方式存在一些问题：

1. 不可靠性：在两次握手的情况下，如果客户端的连接请求报文段丢失，服务器将无法确认客户端的请求，从而无法建立连接。
2. 安全性问题：由于没有第三次握手，可能会有恶意主机发送大量的伪造连接请求，导致服务器资源被耗尽，也称为SYN洪泛攻击。

因此，为了确保连接的可靠性和安全性，TCP采用三次握手来建立连接。第三次握手是为了确保服务器收到客户端的确认报文段，从而避免了错误连接和资源浪费的问题。

TCP三次握手，怎么解决历史重复连接的

TCP三次握手可以解决历史重复连接的问题。具体过程如下：

1. 客户端发送连接请求报文段（SYN）给服务器。
2. 服务器收到请求后，如果同意连接，则发送确认报文段（SYN+ACK）给客户端，并为该连接分配资源。
3. 客户端收到服务器的确认后，发送确认报文段（ACK）给服务器，建立连接。
4. 连接建立后，双方可以开始进行数据传输。

在三次握手的过程中，服务器会为每个连接分配一个唯一的标识符，称为序列号（Sequence Number）。客户端发送的连接请求报文段中会包含一个初始的序列号，服务器在确认报文段中会回复一个确认序列号。

历史重复连接指的是客户端发送的连接请求报文段在网络中滞留，导致服务器延迟收到该请求，而客户端认为连接已建立，重新发送了连接请求。这样就会出现服务器收到重复的连接请求。

TCP通过使用序列号来解决历史重复连接的问题。服务器在收到重复的连接请求后，会检查该连接请求的序列号和已分配的序列号进行比较。如果两者一致，则说明该连接请求是历史重复连接，服务器会忽略该请求。如果不一致，则说明该连接请求是新的请求，服务器会重新处理并建立连接。

通过使用序列号来识别和处理历史重复连接，TCP确保了连接的可靠性和可用性。

Http

HTTP2.0的优化，HTTP3.0的优化 ，HTTP3.0前向纠错，HTTP3.0如何保证可靠性

https://juejin.cn/post/6995109407545622542

HTTP/1.1、HTTP/2、HTTP/3 演变

HTTP/1.1 相比 HTTP/1.0 提高了什么性能？

HTTP/1.1 相比 HTTP/1.0 性能上的改进：

使用长连接的方式改善了 HTTP/1.0 短连接造成的性能开销。
支持管道（pipeline）网络传输，只要第一个请求发出去了，不必等其回来，就可以发第二个请求出
去，可以减少整体的响应时间。
但 HTTP/1.1 还是有性能瓶颈：

请求 / 响应头部（Header）未经压缩就发送，首部信息越多延迟越大。只能压缩 Body 的部分；
发送冗长的首部。每次互相发送相同的首部造成的浪费较多；
服务器是按请求的顺序响应的，如果服务器响应慢，会招致客户端一直请求不到数据，也就是队头阻
塞；
没有请求优先级控制；
请求只能从客户端开始，服务器只能被动响应。

HTTP/2 做了什么优化？
TTP/2 协议是基于 HTTPS 的，所以 HTTP/2 的安全性也是有保障的。
那 HTTP/2 相比 HTTP/1.1 性能上的改进：
头部压缩
二进制格式
并发传输
服务器主动推送资源

HTTP/2 有什么缺陷？
HTTP/2 通过 Stream 的并发能力，解决了 HTTP/1 队头阻塞的问题，看似很完美了，但是 HTTP/2
还是存在“队头阻塞”的问题，只不过问题不是在 HTTP 这一层面，而是在 TCP 这一层。

HTTP/3 做了哪些优化？

QUIC 有以下 3 个特点。

无队头阻塞
更快的连接建立
连接迁移

计算机网络安全

---

导航【网络安全】

期末复习【网络安全】

---

安全攻击

被动攻击：
消息内容泄露攻击和流量分析攻击

主动攻击：
假冒、重放、改写消息和拒绝服务。

被动攻击：窃听
主动攻击：篡改、恶意程序、拒绝服务

对称加密

明文:这是原始消息或数据，作为算法的输入。
加密算法:加密算法对明文进行各种替换和转换。
秘密密钥:秘密密钥也是算法的输入。算法进行的具体替换和转换取决于这个密钥。
密文:这是产生的已被打乱的消息输出。它取决于明文和秘密密钥。对于一个给定的消息,两个不同的密钥会产生两个不同的密文。
解密算法:本质上是加密算法的反向执行。它使用密文和同一密钥产生原始明文。

DES、3DES、AES

安全散列函数

散列函数的目的是为文件、消息或其他数据块产生“指纹”。为满足在消息认证中的应用,散列函数H必须具有下列性质:
(1)H可适用于任意长度的数据块。
(2)H能生成固定长度的输出。
(3)对于任意给定的x，计算H(x)相对容易，并且可以用软/硬件方式实现。
(4)对于任意给定值h，找到满足H(x)=h的x在计算上不可行。满足这一特性的散列函数称为具有单向性,或具有抗原像攻击性。

(5)对于任意给定的数据块x，找到满足H(y)=H(x)的y≠x在计算上是不可行的。满足这一特性的散列函数被称为具有抗第二原像攻击性，有时也称为具有抗弱碰撞攻击性。
(6)找到满足Hx)= H(y)的任意一对(x，y)在计算上是不可行的。满足这一特性的散列函数被称为抗碰撞性,有时也被称为抗强碰撞性。

前三个性质是使用散列函数进行消息认证的实际可行要求。第四个属性，抗原像攻击性，是单向性:给定消息容易产生它的散列码，但是给定散列码几乎不可能恢复出消息。如果认证技术中使用了秘密值（见图3.2（c))，则单向性很重要。秘密值本身并不会传输;然而，假如散列函数不是单向的，而攻击者能够分析或截获消息M和散列码C=H(S_ABlIM)，则攻击者很容易发现秘密值。攻击者对散列函数取逆得到S_AB||M=H¹( C)。因为这时攻击者拥有M和S_ABllM，所以他们可以轻而易举地恢复S_AB。

抗第二原像攻击性质保证了对于给定的消息，不可能找到具有相同散列值的可替换消息。利用加密的散列码可防止消息被伪造(见图3.2（a）和图3.2(b))。如果该性质非真，则攻击者可以进行如下操作:第一，分析或截获消息及其加密的散列码;第二，根据消息产生没有加密的散列码;第三，生成具有相同散列码的可替换消息。

满足上面前5个性质的散列函数称为弱散列函数。如果还能满足第6个性质则称其为强散列函数。第6个性质可以防止像生日攻击这种类型的复杂攻击。生日攻击的细节超出了本书的范围。这种攻击把m比特的散列函数的强度从2^m简化到2^m/2。详细内容可参考[STAL11]。

除提供认证之外,消息摘要还能验证数据的完整性。它与帧检测序列具有相同的功能:如果在传输过程中,意外地篡改任意比特,消息摘要则会出错。

SHA

非对称加密

公钥密码方案由6个部分组成（见图3.9(a)）:

• 明文:算法的输入,它是可读的消息或数据。
• 加密算法:加密算法对明文进行各种形式的变换。
• 公钥和私钥:算法的输入，这对密钥如果一个密钥用于加密，则另一个密钥就用于解密。加密算法所执行的具体变换取决于输入端提供的公钥或私钥。
• 密文:算法的输出，取决于明文和密钥。对于给定的消息，两个不同的密钥将产生两个不同的密文。
• 解密算法:该算法接收密文和匹配的密钥，生成原始的明文。

公钥密码系统的应用

在广义上可以把公钥密码系统分为如下三类。

• 加密/解密:发送方用接收方的公钥加密消息。
• 数字签名:发送方用自己的私钥“签名”消息。签名可以通过对整条消息加密或者对消息的一个小的数据块加密来产生，其中该小数据块是整条消息的函数。
• 密钥交换:通信双方交换会话密钥。这可以使用几种不同的方法，且需要用到通信一方或双方的私钥。

RSA算法

基本的RSA加解密 对于某明文块M和密文块C加密和解密有如下的形式:
C=M^emod n
M=C^d mod n=(M^e)^d mod n = M^ed mod n
发送方和按牧方那必须知道和e的值，并且只有接收方知道d的值。RSA公钥密码算法的公钥KU={e,u}私钥KR={d,n}。为使该算法能够用于公钥加密，它必须满足下列要求:
(1)可以找到e、d、n的值， 使得对所有的M<n，M^edmod n=M成立。
(2)对所有满足M<n的值， 计算M^e和C^d相对容易。
(3)给定e和n,不可能推出d。
前两个要求很容易得到满足。当e和n取很大的值时，第三个要求也能够得到满足。

要计算n的欧拉函数值Φ(n)。Φ(n)表示小于n且与n互素的正整数的个数。然后选择与Φ(n)互素的整数e(即e和Φ(n)的最大公约数为1)。最后，计算e关于模d(n)的乘法逆元d，d和e具有所期望的属性。

TLS 传输层安全

TLS体系结构

TLS记录协议

TLS握手协议

• 第一阶段:客户端发起建立连接请求.建立安全连接请求.包括协议版本、会话ID、密码套件、压缩方法和初始随机数
• 第二阶段:服务器认证和密钥交换。服务器发送证书、密钥交换数据和证书请求．最后发送hello消息阶段的结束信号
• 第三阶段:客户端认证和密钥交换。如果有证书请求，客户端发送证书。之后客户端发送密钥交换数据，也可以发送证书验证消息
• 第四阶段:完成。变更密码套件和结束握手协议

HTTPS RSA 握手解析

---

HTTPS RSA 握手解析

---

TLS 握手过程

HTTP 由于是明文传输，所谓的明文，就是说客户端与服务端通信的信息都是肉眼可见的，随意使用一个抓包工具都可以截获通信的内容。

所以安全上存在以下三个风险：

窃听风险，比如通信链路上可以获取通信内容，用户号容易没。
篡改风险，比如强制植入垃圾广告，视觉污染，用户眼容易瞎。
冒充风险，比如冒充淘宝网站，用户钱容易没。

HTTPS 在 HTTP 与 TCP 层之间加入了 TLS 协议，来解决上述的风险。

TLS 协议是如何解决 HTTP 的风险的呢？

信息加密： HTTP 交互信息是被加密的，第三方就无法被窃取；
校验机制：校验信息传输过程中是否有被第三方篡改过，如果被篡改过，则会有警告提示；
身份证书：证明淘宝是真的淘宝网；
可见，有了 TLS 协议，能保证 HTTP 通信是安全的了，那么在进行 HTTP 通信前，需要先进行 TLS 握手。TLS 的握手过程，如下图：

上图简要概述了 TLS 的握手过程，其中每一个「框」都是一个记录（record），记录是 TLS 收发数据的基本单位，类似于 TCP 里的 segment。多个记录可以组合成一个 TCP 包发送，所以通常经过「四个消息」就可以完成 TLS 握手，也就是需要 2个 RTT 的时延，然后就可以在安全的通信环境里发送 HTTP 报文，实现 HTTPS 协议。

所以可以发现，HTTPS 是应用层协议，需要先完成 TCP 连接建立，然后走 TLS 握手过程后，才能建立通信安全的连接。

事实上，不同的密钥交换算法，TLS 的握手过程可能会有一些区别。

这里先简单介绍下密钥交换算法，因为考虑到性能的问题，所以双方在加密应用信息时使用的是对称加密密钥，而对称加密密钥是不能被泄漏的，为了保证对称加密密钥的安全性，所以使用非对称加密的方式来保护对称加密密钥的协商，这个工作就是密钥交换算法负责的。

接下来，我们就以最简单的 RSA 密钥交换算法，来看看它的 TLS 握手过程。

RSA 握手过程

请看RSA 握手过程