算法与数据结构无废话笔记（四）

  算法与数据结构是计算机专业学生的必修课，基础中的基础，所以快速上手，找到学习方向和感觉十分重要。我在学习过程中遇到一本好书，《我的第一本算法书》，把算法讲得很浅显易懂，所以基于这本书的内容，提炼出其中的精华，再加上个人的理解，旨在把最干的干货分享给大家。推荐大家去阅读原书！

安全和算法

通过互联网交换数据时，数据要经过各种各样的网络和设备才能传到对方那里。数据在传输过程中有可能会经过某些恶意用户的设备，从而导致内容被盗取。

因此，要想安全地使用互联网，安全技术是不可或缺的。本章将要学习的就是保障安全的 各种算法和利用了这些算法的机制。

这些问题不光发生在用户之间交流的时候，也有可能发生在用户浏览网页的时候。

“数字签名”技术存在“无法确认公开密钥的制作者”这一问题。要想解决这个问题，可以使用“数字证书”技术。

加密的基础知识

在现代互联网社会中，加密技术变得十分重要。给想要保密的数据加密。加密后的数据被称为“密文”。把密文发送给B。B收到密文后，需要解除加密才能得到原本的数据。把密文恢复为原本数据的操作就叫作“解密”。

计算机会用由 0 和 1 这两个数字表示的二进制来管理所有数据。如上图所示，数据虽然有文本、音频、图像等不同的形式，但是在计算机中都是用二进制来表示的。

对计算机来说，数据就是一串有意义的数字罗列。密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列。也就是说，加密就是数据经过某种运算后，变成计算机无法理解的数的过程。

在加密运算上会用到“密钥”。所以加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程。反过来，解密就是通过密钥进行数值计算，把密文恢复成原本数据的过程。

哈希函数！！！

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。输出的无规律数值就是“哈希值”。哈希值虽然是数字，但多用十六进制来表示。

六特征：

1. 输出的哈希值数据长度不变。
2. 输入相同则输出相同（同一个算法下）。
3. 输入相似的数据并不会导致输出的哈希值也相似。
4. 即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”。
5. 求哈希值的计算容易。
6. 反算不可能，不可能从哈希值反向推算出原本的数据。

共享密钥加密

共享密钥加密是加密和解密都使用相同密钥的一种加密方式。由于使用的密钥相同，所以这种算法也被称为“对称加密”。

我们先从整体上来了解一下共享密钥加密的处理流程。假设 A 准备通过互联网向 B 发送数据。由于有被窃听的风险，所以需要把想要保密的数据加密后再发送。A使用密钥加密数据。A将密文发送给B。B收到密文后，使用相同的密钥对其进行解密。这样，B就取得了原本的数据。只要是加密好的数据，就算被第三者恶意窃听也无须担心。

公开密钥加密

公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。

然后把公开密钥发送给A。A使用B发来的公开密钥加密数据。A 将密文发送给 B，B 再使用私有密钥对密文进行解密。这样，B就得到了原本的数据。

公开密钥和密文都是通过互联网传输的，因此可能会被 X 窃听。但是，使用公开密钥无法解密密文，因 此X也无法得到原本的数据！多人传输时，超级方便！

但是！！！道高一尺魔高一丈！

在B把公开密钥PB发给A的时候，X把公开密钥PB替换成自己的公开密钥PX， 于是公开密钥PX传到了A那里。

整个过程没有任何问题，B和A都不知道自己被假冒和窃听了。

这种通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击”（man-in-the-middle attack）。

混合加密

共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。

在混合加密中，要用处理速度较快的共享密钥加密对数据进行加密。不过，加密时使用的密钥，则需要用没有密钥分配问题的公开密钥加密进行处理。 就是频繁传输的数据，用共享密钥加密传输，但是第一次传密钥时，用公开密钥加密传输。

迪菲 - 赫尔曼密钥交换

迪菲 - 赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。很绝的一个方法

假设有一种方法可以合成两个密钥。使用这种方法来合成密钥P和密钥S，就会得到由这两个密钥的成分所构成的密钥P-S。这种合成方法有三个特征：

1. 即使持有密钥P和合成的密钥P-S，也无法把密钥S单独取出来。
2. 不管是怎样合成而来的密钥，都可以把它作为新的元素，继续与别的密钥进行合成。
3. 密钥的合成结果与合成顺序无关，只与用了哪些密钥有关。

流程：

首先由A生成密钥P。然后A把密钥P发送给B。接下来，A 和 B 各自准备自己的私有密钥SA和SB。A利用密钥P和私有密钥SA合成新的密钥P-SA。B也利用密钥P和私有密钥SB合成新的密钥P-SB。A将密钥P-SA 发送给B，B也将密钥 P-SB发送给A。A将私有密钥SA和收到的密钥P-SB合成为新的密钥SA-P-SB。同样地，B也将私有密钥SB和收到的密钥P-SA合成为新的密钥P-SA-SB。 于是A和B都得到了密钥P-SA-SB。这个密钥将作为“加密密钥”和“解密密钥”来使用。

消息认证码

消息认证码可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。

一句话说明白，还记得哈希函数吧，以共享密钥加密为例，将密文和密钥进行哈希运算得到一个数，叫做消息认证码（MAC），发送密文的同时带上MAC，因为双方密钥相同，所以对方收到密文后，也把密文和密钥进行哈希运算，若得到的数跟收到的MAC相同，则数据没有被篡改！

数字签名

首先由A准备好需要发送的消息、私有密钥和公开密钥。由消息的发送者来准备这两个密钥，这一点与公开密钥加密有所不同。A将公开密钥发送给B。A使用私有密钥加密消息。加密后的消息就是数字签名。A将消息和签名都发送给了B。B使用公开密钥对密文（签名）进行解密。B对解密后的消息进行确认，看它是否和收到的消息一致。流程到此结束。

数字证书

一句话，数字证书就是带有认证中心数字签名和发送者信息（包含公开密钥）的文件。其中数字签名就是认证中心使用自己私有密钥对发送者信息进行加密的结果。就是认证中心给你的发送的公开密钥盖了个章，证明这是你发的！！！

聚类

参考这篇文章哦。 无废话的机器学习笔记（七）（聚类: kmeans、GMM、谱聚类）

其他算法

欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数，被称为世界上最古老的算法。

素性测试（费马测试）

素性测试是判断一个自然数是否为素数的测试。素数（prime number）就是只能被 1 和其自身整除，且大于 1 的自然数。素数从小到大有 2、3、5、7、11、13……目前在加密技术中被广泛应用的 RSA 算法就会用到大素数，因此“素性测试”在该算法中起到了重要的作用。

网页排名

网页排名（PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法。 Google 因在搜索引擎中使用了这个算法而成为了世界知名的大企业是众所周知的事情。

浏览网页的人只是在不断重复着 “在有链接指向的页面之间移动几次之后，远程跳转到了完全不相关的网页这一过程！

汉诺塔

汉诺塔是一种移动圆盘的游戏，同时也是一个简单易懂的递归算法应用示例。

实际上，不管需要移动多少圆盘，这个游戏最终都能达成目标。




上一篇 ！加油！