安全算法
概论
用互联网传输数据时可能会发生的四个主要问题
1.窃听：
A向B发送的消息在传输途中被X偷看
2.假冒：
A以为向B发送了信息，但B可能是X冒充的
B以为A收到了信息，A可能是X冒充的
3.篡改:
B确实收到了A发送的信息，但可能在途中被X篡改或者数据在传输过程中损坏
4.事后否认：
B从A那里收到了消息，但作为消息发送者A对B抱有恶意，在事后称”这不是我发送的消息”，这种情况会使互联网上的商业交易或合同签署无法成立
解决这些问题的安全技术
| 问题 | 解决方法 |
|---|---|
| 窃听 | 加密 |
| 假冒 | 消息认证码or数字签名 |
| 篡改 | 消息认证码or数字签名 |
| 事后否认 | 数字签名 |
加密方法分为两种：加密和解密都使用相同密钥的”共享密钥加密“，分别使用不同密钥加密的”公开密钥加密“
共享密钥加密
A使用密钥将数据加密，然后将密钥和密文发送给B，B再使用相同密钥解密得到数据。
优点
- 解密速度相对较快
问题
1.密钥和密文都有被第三者窃听的风险：
解决方法：使用公开密钥加密或迪菲-赫尔曼密钥交换方法使密钥安全送出
2.篡改
解决方法：消息认证码
3.事后否认
解决方法：数字签名
4.无法确定信息的发送者（中间人攻击）
解决方法：数字证书
5.密钥的需求数量会随着发送人数的增多而急剧增多，5个人要10个，100个人要4950(n(n-1)/2)个
公开密钥加密
公开密钥加密是加密和解密使用不同密钥的一种加密方法，由于使用密钥的不同，这种算法也被称为“非对称加密”。加密使用的密钥叫做”公开密钥”，解密用的叫做“私有密钥”，由接收方生成公开密钥和私有密钥。
优点
- 即使X窃听了A发送给B的密文和公开密钥，依旧无法解密，安全性更高
- 多个人给一个人传输数据时可以把公开密钥放在网上，比较方便，且需要的密钥数量较小。
缺点
1.公开密钥可靠性问题：当A把公开密钥发送给B时，被X的公开密钥掉包，由于公开密钥无法显示自己是由谁生成的，所以A和B不会发现自己收到的公开密钥已经被人替换，此时当B向A发送用X的公开密钥加密后的密文时，X可以窃听此密文，然后用自己X的私钥进行解密得到数据。这种通过中途替换公开密钥来攻击的方法叫做”中间人攻击”
解决方法：数字证书
2.公开密钥的加密和解密都比较耗时，所以这种方法不适用发送零碎数据的方法
解决方法：混合加密
3.篡改
解决方法：消息认证码
4.事后否认
解决方法：数字签名
5.无法确定信息的发送者（中间人攻击）
解决方法：数字证书
混合加密
发送消息者使用共享密钥对数据进行加密(共享密钥的加密速度加快)，然后使用公开密钥对共享密钥进行加密。
接收消息者用私有密钥对共享密钥进行解密，然后用共享密钥对数据进行解密(共享密钥的解密速度加快)。
优点
在安全性和处理速度上都有优势
缺点
1.中间人攻击：
解决方法：数字证书
3.篡改
解决方法：消息认证码
4.事后否认
解决方法：数字签名
迪菲-赫尔曼密钥交换
原理
P和S两个密钥可以通过一种方法合成密钥P-S
特点
- 只能合成，密钥P-S不能分解成P和S
- 合成后的密钥可以继续作为新的元素与别的密钥进行合成
- 密钥的合成结果与合成顺序无关，只与用了哪些密钥有关，比如密钥A-B-C和密钥B-A-C是一样的。
过程
由A生成密钥P，A把密钥P发送给B，A和B各自用自己的私有密钥SA,SB生成PSA,PSB，A将密钥PSA发送给B，B也将密钥PSB发送给A，A和B利用私有密钥PSA,PSB合成PSBSA，PSBSA这个密钥将作为”加密密钥“和”解密密钥“来使用。在此过程中，即使X窃听到了所有过程中传输的密钥，由于他没有A和B的私有密钥，无法合成最后的密钥PSBSA。
用数学表示这种密钥交换法
公开密钥P用P,G两个整数来表示，P是一个非常大的素数，G是素数P对应的生成元或其中一个。
首先,A准备素数P和生成元G，这两个数公开也没有关系，然后A将这两个数发送给B。接下来A和B各自准备秘密数字X和Y，X和Y都必须小于P-2。A和B分别计算（G的各自秘密数字(x/y)次方)mod P，此处的运算等同于概念意义上的合成，A和B将各自的计算结果发给对方，A和B收到对方的计算结果后，先计算这个值的秘密数字次方，然后再mod P，最后A和B会得到相同的结果。
优点
安全性：使用迪菲-赫尔曼密钥交换，通信双方仅通过交换一些公开信息就可以实现密钥交换，但实际上双方并没有交换密钥，而是生成了密钥。该方法又被叫做”迪菲-赫尔曼密钥协议”
缺点
1.中间人攻击：
解决方法：数字证书
2.篡改
解决方法：消息认证码
3.事后否认
解决方法：数字签名
消息认证码
消息认证码可以实现”认证”和”检测篡改”两个功能。
A生成一个用于制作消息认证码的密钥，然后使用安全方法将密钥发送给B，然后A用密钥和密文生成一个值，这个值就是消息认证码(简称MAC)，我们可以把这个值想象成哈希值，然后A将MAC和密文一起发送给B，B也需要使用密钥生成MAC，若两个MAC相同，则消息没有篡改。
优点
即使X为了让他对密文的篡改得合理而篡改了MAC，因为X没有计算MAC的密钥，无法使篡改后的MAC变的合理，只要B计算出MAC值发现不同就可以确认发生的篡改。
缺点
1.AB双方都可以对消息加密并且算出MAC，无法证明原本的信息是A发送的还是B发送的，即事后否认问题
解决方法：数字签名
2.中间人攻击
解决方法：数字证书
数字签名
数字签名只有发信者才可以产生，因此使用他就能确定谁是消息的发送者。
A将公开密钥发送给B，A使用私有密钥加密消息，用公有密钥加密数据，私有密钥加密后的消息就是数字签名，A将数据，消息和签名都发送给B，B使用公开密钥对签名密文进行解密，用私有密钥对数据进行解密，对解密后的签名进行确认，如果一致就是A发送的。
公开密钥的加密和解密都比较耗时，为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值再对哈希值进行加密，然后将其作为签名进行使用。
优点
只能由持有私有密钥的A来加密，但只要由公开密钥，谁都可以解开的密文作为密码没有任何意义，但从另一个角度讲，他可以保证密文的制作者只能是A，并且由于B只有公开密钥无法生成A的签名，预防了事后否认的问题
不是所有的公开密钥加密具有这个性质，但RSA加密算法是可以的
缺点
2.中间人攻击
解决方法：数字证书
数字证书
防止中间者攻击，保证公开密钥的正确性。
A有公开密钥PA和私有密钥SA，现在想将公开密钥发送给B，首先他需要向认证中心（CA）申请发行证书证明密钥确实由A自己生成，认证中心保管着他们自己的PC和SC，A将PA和包含邮箱信息的个人资料发送给认证中心，认证中心进行确认后用私有密钥SC对A的资料进行数字签名，然后将数字签名和资料放进同一个文件中，把这个文件发送给A，这个文件就是A的数字证书。A将作为公开密钥的数字证书发送给B，B收到数字证书后确认证书里的邮件地址确实是A的地址，然后B获取认证中心CA 的公开密钥PC对证书内的签名进行校验，判断他是否为认证中心给出的签名，最后再从证书中取得PA。
优点
由于X没有A的邮箱地址，无法获得A的证书。
可能存在的缺点
B得到的公开密钥Pc可能不是来自认证中心，X可能冒充认证中心。但认证中心的公开密钥也是以数字证书的形式交付的，会有更高级别的认证中心(最高的是根认证中心RCA)对这个认证中心进行署名，类似树形结构。
交付公开密钥不只存在于个人与个人之间，他还存在于网站之间的通信，用于网站通信的证书叫做”服务器证书“，服务器证书与域名信息相对于，就像个人的证书会与他的邮箱信息相对应一样。
数字证书就像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被称为”公钥基础设施“（PKI）
聚类
聚类就是在输入为多个数时，将相似的数据分为一组的操作，1各组叫1个蔟。
根据数据类型的不同，定义该数据是否相似的标准也不同，具体来说，是要根据两个数据之间的差距来定义，可以用两点间的之前距离来表示差距（距离的定义方法有很多）
在定义好数据间的差距之后，聚类的方法根据设定的条件（如蔟的数量和每个蔟的数据量）也有很多种。其中最基本最有代表性的聚类算法是”K-means“算法。
K-means算法
根据事先给定的蔟的数量进行聚类。
随机选择三个点最为蔟的中心点，计算各个数据分别和三个中心点的哪一个点最接近，将数据分到相应的蔟中，这样，就完成了第一次聚类。然后计算各个蔟的重心，将蔟的中心点移到这个位置，安照以上步骤重新进行聚类，不断重复前面的步骤直到中心点不再发生变化位置。
如果设定的数据不合理，运行的结果可能不符合我们的需求，因此可以事先对数据进行分析推算出一个合适的数量，并且即使蔟的数量相同，如果随机设置的最初的中心点最初的位置不同，聚类的结果也会发生变化，因此我们可以通过改变随机设定的中心点位置来不断尝试k-means算法，从中选择最合适的聚类结果。
层次聚类算法
一开始每个数据都自成一类，不需事先给定蔟的数量。
在一开始有n个数据会形成n个蔟，然后重复执行“将距离最近的两个蔟合并成一个”，这样的操作重复n-1次，没执行一次，蔟就会减少一个，执行n-1次后，所有数据都被分到了一个蔟之中。在这个过程中，每个阶段的蔟的数量都不同，对应的聚类结果也不同，只要从中选择最为合理的一个结果即可。
比较
| 数据结构 | 二叉树 | 堆 |
|---|---|---|
| 特点 | 每个结点的值大于其左子树任意一个结点的值，小于其右子树任意一个结点的值 | 父结点大于子节结点 |
| 查找 | 从顶端开始不断与顶点大小进行比以决定往左还是往右寻找 | 最上面的顶点是最小 |
| 添加 | 从顶点开始，不停与结点比较决定是往左移还是往右移 | 往右下添加数据，如果一行满了就新起一行加在最左端，最后再不断与父结点比较以决定是否往上移 |
| 删除（有子节点） | 在被删除的子树上寻找最大结点然后将最大结点往上移到被删除的节点位置上，如果移动的节点还有子节点就递归执行前面的操作。 | 根据堆的特点进行操作 |
| 优势 | 如果树的形状较为均衡，比较大小和移动的次数最多为logn（树的高度） | 在不断需要计算最小值的算法中可以优化时间复杂度，如排序。 |
- 树删除有节点的子树移动右子树的最小节点也没问题，只需要保持树的特点就行。
- 有很多以二叉查找树为基础扩展的树形结构，如平衡二叉查找树，另外，节点数可以自己设定。
- 在堆中，无论数据量多大，取出最小值的时间复杂度为O(1)，在取出之后需要将最后的数据移到最顶端，然后比较他与子节点的数据一边往下移动，所以取出数据需要的运行时间与树的高度成正比，由于树的高度为logn，所以重构树的时间复杂度为logn
- 在此列表中的前提是每个结点都不相同
| 图的遍历 | 广度优先 | 深度优先 |
|---|---|---|
| 特点 | 从起点开始顺着边搜索直到达到指定顶点 | 沿着一条路径不断向下直到不能继续为止再折返 |
| 选哪一个顶点作为下一个顶点的基准 | 离起点最近的顶点（FIFO) | 最新成为候补的顶点（LIFO） |
| 数据结构 | 队列 | 栈 |
| 思想 | 递归 |
- 有闭环的图算法也是一样的
| 排序 | 冒泡 | 选择 | 插入 | 堆 |
|---|---|---|---|---|
| 时间复杂度(最糟糕的情况下) | n^2^/2=O(n^2^) | n^2^/2=O(n^2^) | n^2^/2=O(n^2^) | O(nlogn) |
| 简单解释 | 从左至右不断进行数字比较和交换（两个for循环），将最大的数一个个依次滚动到最后 | 使用线性查找每次找出最小值然后与第一个位置进行交换，依次类推 | 假设最左已排好序，从未排好序区域（除最左以外的区域）与排好序的区域进行比较往左插入，依次类推。最糟糕的情况是要将数据从小到大排序时，输入数据是从大到小的。 | 一开始需要将n个数据存进堆里，时间复杂度为O(nlogn)【重构一次要O(logn)，需要重构n次】每次取出最大的数据并重构dO(logn) |
- 堆排序其实相当于把堆嵌入到包含序列的数组中，强行在数组中使用了堆结构
- 快速排序和归并的复杂度也是O(nlogn)
- 归并分割序列花费的时间不算在运行时间内(当作序列本来就是分割好的)，在合并两个已排好的序列中，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列相应的运行时间，完成一行归并所需的运行时间取决于这一行的数据量。设每一行的数据量为n，对半分割后可分成logn行，每行要比较n次
- 快速排序中可用到递归思想，不断选取基准点，将基准点小的往左移大的往右移直到只有1个数或者0个数或者以排完序不需要移动为止
网页排名（佩奇排名）
以前的搜索引擎是根据关键词和网页内容的关联性来决定搜索结果的排列，这种方法没有考虑网页是否含有效内容，因此搜索精度较低。
而网页排名是利用网页之间的链接结构算出网页价值的算法，有链入页面的网页权重是其链入页面的权重之和，如果一个网页链向多个页面，那么其链向的所有页面将平分他的权重，在网页排名中链入的页面越多则其价值就越高。
但出现环状的链接结构的情况下呢？
使用随机游走模型，假设有一个人在随机浏览网页，根据他的浏览计算每个网页的浏览概率，并将其概率当成网页的权重来使用
用游走模型计算的加权结果和网页排名算出来的值几乎是一样的。
事实上 一般不会用模拟而用更高效的算法来计算，但无论使用哪种计算，计算结果几乎都是相同的。
