一个让你查看你的文件哈希值，以确定它不是恶意文件，并且确实来自真实来源的图形界面程序。有人给你发送了一个文件，你怎样来证实它是给你的原件？你怎样来确定它没有被篡改过？同时，你怎么证实这个文件是来自一个原始的真实来源。这就是加密哈希的重要作用所在。如果用来验证一个文件，诸如 SHA-1 之类的哈希功能就是一个校验值。这能够帮助你确认文件是否已经被修改。如果你感到好奇，你可以参考我们的 在 Linux 中验证校验值的指南。对每个信息 / 文件来说，它们有一个唯一的哈希值（或者叫校验和）。所以，即使文件有一点点的改动，整个哈希值就会发生变化。它主要用于加密中，每个文件 / 信息以哈希值安全的存储。假设一个攻击者掌握了存储哈希值（而不是真实信息）的数据库，他们也不能够知道其意义。加密可以使存储更加安全。虽然讨论哈希超出了这篇文章的范围，但是了解它在验证文件完整性上是很有意义的。Collision：迅速的验证文件并发现恶意文件如果没有图形界面，你就得用终端去生成哈希值来比对 / 验证。Collision 使它变的非常容易，不需要打开终端或者生成文件的校验值。如果你不了解的话，我们的 在 Linux 中验证校验值的指南 可以帮助到你。当使用 Collision 时, 你只需要添加你要生成哈希值或者验证所需的文件即可。你只需点击几下便能够保护自己免受恶意或篡改文件的攻击。我在截图中显示了个文本文件，你的文件在发送给其他人之前，你可以验证各种类型文件或为你的文件生成一个哈希值。你可以通过发给收件人分享你生成的哈希值，让他们验证你的文件。这是一款简单的开源应用，它只帮你做两件事情：生成哈希值（SHA-1、MD5、SHA-256、SHA-516）通过直接使用文件或者校验值验证一个项目Collision 是怎么工作的给你举个例子，我修改原来的文本文件，为其添加一个字母，然后尝试验证它。下面是它的过程：首先，你需要打开你要比对的原文件或者有校验值的原文件。打开原文件生成哈希值，然后去验证区查看修改后的文件。你会注意到，它们俩个不是相同的：如果你在按校验值检查文件，首先，你要打开你要验证的文件（这儿是我们已经修改后的文件）。然后，输入文件的原始真实校验值。当然我们已经知道我们测试的是修改后的文件，结果是我们所期望的，即，验证文件完整性失败。在 Linux 安装 CollisionCollisions 主要是一个为 GNOME 定制的程序，但是它也适用于其他发行版上。你可以使用 Flatpak 可用软件包 来安装它，或者浏览 GitHub 网页，从源码中编译它。如果你是 Linux 新手，你可以参考我们的 Flatpak 指南 来得到帮助。如果你喜欢使用终端来安装，键入以下命令来安装：flatpak install flathub dev.geopjr.Collision 你也可以访问它的官方网站。Collisionvia: https://itsfoss.com/collision/作者：Ankush Das 选题：lujun9972 译者：hwlife 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
硬核观察 #460 哈希表理论突破提升数据存储效率
哈希表理论突破提升数据存储效率哈希表是最常用的组织和存储数据的方法之一。线性探测哈希表于 1954 年引入，是当今可用的最古老、最简单和最快的数据结构之一。在线性探测哈希表中，可存储信息的位置位于一个线性数组中。几乎每个使用线性探测哈希表的人都认为，如果你让它们变得太满，那么长长的、被占据的位置就会聚集在一起形成“集群”，结果找到一个空位所花费的时间会急剧增加。但是这个已有半个多世纪、一直不利于高负载率的原则已被 三名研究人员的工作 彻底颠覆。他们发现，对于插入和删除数量大体相等的应用程序，线性探测哈希表可以在不牺牲速度的情况下以高存储容量运行。老王点评：果然只有数学理论的突破才能真正突破硬件的升级幅度。英特尔发布了检测漏洞的 AI英特尔上个月开源了 ControlFlag，今天 发布了 1.0。在该版本中，他们宣传说已经完全支持 C 语言编程，并特别针对 C 程序的 if 条件语句做了调整。ControlFlag 的方法是在 C/C++ 开源代码库中挖掘模式，然后在开发者的代码库中检测异常模式。他们在 6000 多个 GitHub 存储库的超过 10 亿行代码中进行了训练。英特尔表示，他们已经成功地在他们的软件中使用了它，包括应用程序和固件。老王点评：以后看来不但写程序不用程序员，就连程序员的 bug 也不用程序员找了。英特尔开发下一代固件平台英特尔 发布 了 通用可扩展固件（USF） 的规范草案。USF 建立在现有的行业标准上，如 UEFI 和 ACPI。USF 在 SoC、平台和操作系统之间引入了新的抽象和领域界限。USF 打算将其范围扩大到不仅仅是系统固件，还计划让英特尔的独立图形处理器使用。USF 的目的是“开放”，但英特尔承认它由外部行业规范和他们的内部规范组成。据估计，英特尔或将使 USF 成为一个完全开源的固件堆栈。老王点评：虽然已经有了一些开源固件解决方案，但是如果 USF 能真正开源，那对开放硬件应该是一件好事。
硬核观察 #369 ImageNet 库被发现哈希碰撞的真实图像
ImageNet 库包含了一对 NeuralHash 哈希碰撞的真实图像NeuralHash 是苹果 CSAM 扫描系统使用的感知哈希算法，它通过输入图像返回 96 位的哈希值，如果两个图像有相同的哈希那么这两个图像应该是相同的。然而实际上并非如此，NeuralHash 产生的哈希相同并不意味着图像相同，这就是哈希碰撞。研究人员已经演示了对 NeuralHash 的原像攻击，创造出两个哈希一样但两幅完全不同的图像。该图像是人为制造出来的，那么有没有哈希相同的自然图像？图像数据库 ImageNet 被发现包含了两对 NeuralHash 哈希相同的图像。哈希碰撞其实并不算稀奇，但是能在原生图像上发现碰撞，说明 NeuralHash 这个算法比较差劲。Debian 11 比上一个版本性能整体提升 8-10%根据 Phoronix 进行的测试，Debian 11 能够更好地发挥硬件的性能。Phoronix 共测试 73 项基准测试，注意到从 Debian 10.10 到 Debian 11 的整体改进约为 8 ~ 10%。然而，在某些测试中，提升的幅度更大，性能提升甚至超过了一倍。我觉得提升幅度这么大，与 Debian 比较保守的升级速度有关。谷歌安全团队又披露了微软未在 90 天内修复的漏洞由于微软并没有在限定的 90 天时间内修复漏洞，谷歌的 Project Zero 团队近日披露了存在于 Windows 系统中的权限提升（EoP）漏洞。这个漏洞是因为 Windows 过滤平台（WFP）的默认规则允许可执行文件连接到 AppContainers 中的 TCP 套接字，这导致了 EoP。Project Zero 团队运行机制是这样的：发现漏洞后报告给厂商，并给予 90 天的时间进行修复。如果厂商没有在限期内进行修复，那么团队就会公开披露。自然，根据所需修复的复杂性，团队有时还会以宽限期的形式提供额外的时间。这不是第一次了，估计微软的工程师也躺倒认锤了。
硬核观察 #345 “不再索取赎金” 项目的免费解密工具节省了 10 亿美元
“不再索取赎金” 项目的免费解密工具节省了 10 亿美元“不再索取赎金” 项目提供了 121 个免费的勒索软件解密工具，可以解密 151 个勒索软件家族。他们已经帮助 600 多万勒索软件受害者免费恢复了他们的加密文件。该网站允许用户上传加密文件，以帮助确定他们成为哪种形式的勒索软件的受害者，然后在有免费解密工具的情况下将他们引向该工具。它建议，尽管勒索软件攻击造成了破坏，但受害者不应该屈服和支付。这不仅是因为没有理由相信犯罪分子会提供合法的解密密钥，而且支付赎金只是表明勒索软件的作用，鼓励进一步的攻击。这是一个非常有意义的措施，而且已经看到了很好的效果。谷歌搜索返回的 PHP 教程一半含有 SQL 注入漏洞在谷歌上搜索 PHP 编程问题，返回的结果包含了教程、技巧和代码片段，但绝大部分结果包含了有缺陷的数据库语句。据研究，30 个结果中有 16 个含有 SQL 注入漏洞。如果搜索者将这些代码包含在其编写的程序中，那么最后产生的程序将是不安全的。可能很多刚刚学习编程的人都有过 “ICP”（互联网复制与粘贴）编程阶段，但是这应该只是一个提示思路的方法，而不是编程方法。BLAKE3 哈希算法发布，比 SHA 算法更快更安全去年宣布的 BLAKE3 是基于其前身 BLAKE2 的加密哈希函数，现在其官方实现发布了 1.0 版本。BLAKE3 比 BLAKE2 快得多，也比 SHA-1/SHA-2/SHA-3 甚至 MD5 等快得多，同时更加安全。它在如今拥有 SIMD 指令集扩展和高核数的 CPU 上是高度可并行的。虽然比 SHA 哈希更好，但是得到推广依然需要 SHA 像 MD5 一样逐渐被淘汰才行。
关于哈希（散列）函数你应该知道的东西
从输出的哈希值反推回输入，这从计算的角度是不可行的。无论安全从业人员用计算机做什么，有一种工具对他们每个人都很有用：加密 哈希（散列） hash 函数。这听起来很神秘、很专业，甚至可能有点乏味，但是， 在这里，关于什么是哈希函数以及它们为什么对你很重要，我会作出一个简洁的解释。加密哈希函数，比如 SHA-256 或者 MD5，接受一组二进制数据（通常是字节）作为输入，并且对每个可能的输入集给出一个 希望唯一 hopefully unique 的输出。对于任意模式的输入，给定的哈希函数的输出（“哈希值”）的长度都是一样的（对于 SHA-256，是 32 字节或者 256 比特，这从名字中就能看出来）。最重要的是：从输出的哈希值反推回输入，这从计算的角度是 不可行的 implausible （密码学家讨厌 “ 不可能 impossible ” 这个词）。这就是为什么它们有时候被称作 单向哈希函数 one-way hash function 。但是哈希函数是用来做什么的呢？为什么“唯一”的属性如此重要？唯一的输出在描述哈希函数的输出时，“ 希望唯一 hopefully unique ”这个短语是至关重要的，因为哈希函数就是用来呈现完全唯一的输出。比如，哈希函数可以用于验证 你 下载的文件副本的每一个字节是否和 我 下载的文件一样。你下载一个 Linux 的 ISO 文件或者从 Linux 的仓库中下载软件时，你会看到使用这个验证过程。没有了唯一性，这个技术就没用了，至少就通常的目的而言是这样的。如果两个不同的输入产生了相同的输出，那么这样的哈希过程就称作“ 碰撞 collision ”。事实上，MD5 算法已经被弃用，因为虽然可能性微乎其微，但它现在可以用市面上的硬件和软件系统找到碰撞。另外一个重要的特性是，消息中的一个微小变化，甚至只是改变一个比特位，都可能会在输出中产生一个明显的变化（这就是“ 雪崩效应 avalanche effect ”）。验证二进制数据哈希函数的典型用途是当有人给你一段二进制数据，确保这些数据是你所期望的。无论是文本、可执行文件、视频、图像或者一个完整的数据库数据，在计算世界中，所有的数据都可以用二进制的形式进行描述，所以至少可以这么说，哈希是广泛适用的。直接比较二进制数据是非常缓慢的且计算量巨大，但是哈希函数在设计上非常快。给定两个大小为几 M 或者几 G 的文件，你可以事先生成它们的哈希值，然后在需要的时候再进行比较。通常，对哈希值进行签名比对大型数据集本身进行签名更容易。这个特性太重要了，以至于密码学中对哈希值最常见的应用就是生成“数字”签名。由于生成数据的哈希值很容易，所以通常不需要有两套数据。假设你想在你的电脑上运行一个可执行文件。但是在你运行之前，你需要检查这个文件就是你要的文件，没有被黑客篡改。你可以方便快捷的对文件生成哈希值，只要你有一个这个哈希值的副本，你就可以相当肯定这就是你想要的文件。下面是一个简单的例子：$ shasum -a256 ~/bin/fop 87227baf4e1e78f6499e4905e8640c1f36720ae5f2bd167de325fd0d4ebc791c /home/bob/bin/fop 如果我知道 fop 这个可执行文件的 SHA-256 校验和，这是由供应商（这个例子中是 Apache 基金会）提供的：87227baf4e1e78f6499e4905e8640c1f36720ae5f2bd167de325fd0d4ebc791c 然后我就可以确信，我驱动器上的这个可执行文件和 Apache 基金会网站上发布的文件是一模一样的。这就是哈希函数难以发生碰撞（或者至少是 很难通过计算得到碰撞）这个性质的重要之处。如果黑客能将真实文件用哈希值相同的文件轻易的进行替换，那么这个验证过程就毫无用处。事实上，这些性质还有更技术性的名称，我上面所描述的将三个重要的属性混在了一起。更准确地说，这些技术名称是： 抗原像性 pre-image resistance ：给定一个哈希值，即使知道用了什么哈希函数，也很难得到用于创建它的消息。 抗次原像性 second pre-image resistance ：给定一个消息，很难找到另一个消息，使得这个消息可以产生相同的哈希值。 抗碰撞性 collision resistance ：很难得到任意两个可以产生相同哈希值的消息。抗碰撞性 和 抗次原像性 也许听上去是同样的性质，但它们具有细微而显著的不同。抗次原像性 说的是如果 已经 有了一个消息，你也很难得到另一个与之哈希值相匹配的消息。抗碰撞性 使你很难找到两个可以生成相同哈希值的消息，并且要在哈希函数中实现这一性质则更加困难。让我回到黑客试图替换文件（可以通过哈希值进行校验）的场景。现在，要在“外面”使用加密哈希算法（除了使用那些在现实世界中由独角兽公司开发的完全无 Bug 且安全的实现之外），还有一些重要且困难的附加条件需要满足。认真的读者可能已经想到了其中一些，特别需要指出的是：你必须确保自己所拥有的哈希值副本也没有被篡改。你必须确保执行哈希算法的实体能够正确执行并报告了结果。你必须确保对比两个哈希值的实体确实报告了这个对比的正确结果。确保你能满足这些条件绝对不是一件容易的事。这就是 可信平台模块 Trusted Platform Modules （TPM）成为许多计算系统一部分的原因之一。它们扮演着信任的硬件基础，可以为验证重要二进制数据真实性的加密工具提供保证。TPM 对于现实中的系统来说是有用且重要的工具，我也打算将来写一篇关于 TPM 的文章。via: https://opensource.com/article/20/7/hash-functions作者：Mike Bursell 选题：lujun9972 译者：Yufei-Yan 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
由于我刚刚提交了最后一个改进 PostgreSQL 11 哈希索引的补丁，并且大部分哈希索引的改进都致力于预计下周发布的 PostgreSQL 10（LCTT 译注：已发布），因此现在似乎是对过去 18 个月左右所做的工作进行简要回顾的好时机。在版本 10 之前，哈希索引在并发性能方面表现不佳，缺少预写日志记录，因此在宕机或复制时都是不安全的，并且还有其他二等公民。在 PostgreSQL 10 中，这在很大程度上被修复了。虽然我参与了一些设计，但改进哈希索引的首要功劳来自我的同事 Amit Kapila，他在这个话题下的博客值得一读。哈希索引的问题不仅在于没有人打算写预写日志记录的代码，还在于代码没有以某种方式进行结构化，使其可以添加实际上正常工作的预写日志记录。要拆分一个桶，系统将锁定已有的桶（使用一种十分低效的锁定机制），将半个元组移动到新的桶中，压缩已有的桶，然后松开锁。即使记录了个别更改，在错误的时刻发生崩溃也会使索引处于损坏状态。因此，Aimt 首先做的是重新设计锁定机制。新的机制在某种程度上允许扫描和拆分并行进行，并且允许稍后完成那些因报错或崩溃而被中断的拆分。完成了一系列漏洞的修复和一些重构工作，Aimt 就打了另一个补丁，添加了支持哈希索引的预写日志记录。与此同时，我们发现哈希索引已经错过了许多已应用于 B 树索引多年的相当明显的性能改进。因为哈希索引不支持预写日志记录，以及旧的锁定机制十分笨重，所以没有太多的动机去提升其他的性能。而这意味着如果哈希索引会成为一个非常有用的技术，那么需要做的事只是添加预写日志记录而已。PostgreSQL 索引存取方法的抽象层允许索引保留有关其信息的后端专用缓存，避免了重复查询索引本身来获取相关的元数据。B 树和 SQLite 的索引正在使用这种机制，但哈希索引没有，所以我的同事 Mithun Cy 写了一个补丁来使用此机制缓存哈希索引的元页。同样，B 树索引有一个称为“单页回收”的优化，它巧妙地从索引页移除没用的索引指针，从而防止了大量索引膨胀。我的同事 Ashutosh Sharma 打了一个补丁将这个逻辑移植到哈希索引上，也大大减少了索引的膨胀。最后，B 树索引自 2006 年以来就有了一个功能，可以避免重复锁定和解锁同一个索引页——所有元组都在页中一次性删除，然后一次返回一个。Ashutosh Sharma 也将此逻辑移植到了哈希索引中，但是由于缺少时间，这个优化没有在版本 10 中完成。在这个博客提到的所有内容中，这是唯一一个直到版本 11 才会出现的改进。关于哈希索引的工作有一个更有趣的地方是，很难确定行为是否真的正确。锁定行为的更改只可能在繁重的并发状态下失败，而预写日志记录中的错误可能仅在崩溃恢复的情况下显示出来。除此之外，在每种情况下，问题可能是微妙的。没有东西崩溃还不够；它们还必须在所有情况下产生正确的答案，并且这似乎很难去验证。为了协助这项工作，我的同事 Kuntal Ghosh 先后跟进了最初由 Heikki Linnakangas 和 Michael Paquier 开始的工作，并且制作了一个 WAL 一致性检查器，它不仅可以作为开发人员测试的专用补丁，还能真正提交到 PostgreSQL。在提交之前，我们对哈希索引的预写日志代码使用此工具进行了广泛的测试，并十分成功地查找到了一些漏洞。这个工具并不仅限于哈希索引，相反：它也可用于其他模块的预写日志记录代码，包括堆，当今的所有 AM 索引，以及一些以后开发的其他东西。事实上，它已经成功地在 BRIN 中找到了一个漏洞。虽然 WAL 一致性检查是主要的开发者工具——尽管它也适合用户使用，如果怀疑有错误——也可以升级到专为数据库管理人员提供的几种工具。Jesper Pedersen 写了一个补丁来升级 pageinspect contrib 模块来支持哈希索引，Ashutosh Sharma 做了进一步的工作，Peter Eisentraut 提供了测试用例（这是一个很好的办法，因为这些测试用例迅速失败，引发了几轮漏洞修复）。多亏了 Ashutosh Sharma 的工作，pgstattuple contrib 模块也支持哈希索引了。一路走来，也有一些其他性能的改进。我一开始没有意识到的是，当一个哈希索引开始新一轮的桶拆分时，磁盘上的大小会突然加倍，这对于 1MB 的索引来说并不是一个问题，但是如果你碰巧有一个 64GB 的索引，那就有些不幸了。Mithun Cy 通过编写一个补丁，把加倍过程分为四个阶段在某个程度上解决了这一问题，这意味着我们将从 64GB 到 80GB 到 96GB 到 112GB 到 128GB，而不是一次性从 64GB 到 128GB。这个问题可以进一步改进，但需要对磁盘格式进行更深入的重构，并且需要仔细考虑对查找性能的影响。七月时，一份来自于“AP”测试人员的报告使我们感到需要做进一步的调整。AP 发现，若试图将 20 亿行数据插入到新创建的哈希索引中会导致错误。为了解决这个问题，Amit 修改了拆分桶的代码，使得在每次拆分之后清理旧的桶，大大减少了溢出页的累积。为了得以确保，Aimt 和我也增加了四倍的位图页的最大数量，用于跟踪溢出页分配。虽然还是有更多的事情要做，但我觉得，我和我的同事们——以及在 PostgreSQL 团队中的其他人的帮助下——已经完成了我们的目标，使哈希索引成为一个一流的功能，而不是被严重忽视的半成品。不过，你或许会问，这个功能可能有哪些应用场景。我在文章开头提到的（以及链接中的）Amit 的博客内容表明，即使是 pgbench 的工作负载，哈希索引页也可能在低级和高级并发方面优于 B 树。然而，从某种意义上说，这确实是最坏的情况。哈希索引的卖点之一是，索引存储的是字段的哈希值，而不是原始值——所以，我希望像 UUID 或者长字符串的宽键将有更大的改进。它们可能会在读取繁重的工作负载时做得更好。我们没有像优化读取那种程度来优化写入，但我鼓励任何对此技术感兴趣的人去尝试并将结果发到邮件列表（或发私人电子邮件），因为对于开发一个功能而言，真正关键的并不是一些开发人员去思考在实验室中会发生什么，而是在实际中发生了什么。最后，我要感谢 Jeff Janes 和 Jesper Pedersen 为这个项目及其相关所做的宝贵的测试工作。这样一个规模适当的项目并不易得，以及有一群坚持不懈的测试人员，他们勇于打破任何废旧的东西的决心起了莫大的帮助。除了以上提到的人之外，其他人同样在测试，审查以及各种各样的日常帮助方面值得赞扬，其中包括 Andreas Seltenreich，Dilip Kumar，Tushar Ahuja，Alvaro Herrera，Micheal Paquier，Mark Kirkwood，Tom Lane，Kyotaro Horiguchi。谢谢你们，也同样感谢那些本该被提及却被我无意中忽略的所有朋友。via：https://rhaas.blogspot.jp/2017/09/postgresqls-hash-indexes-are-now-cool.html作者：Robert Haas 译者：polebug 校对：wxy本文由[LCTT]（[https://github.com/LCTT/TranslateProject）原创编译，[Linux中国]（https://linux.cn/）荣誉推出](https://github.com/LCTT/TranslateProject%EF%BC%89%E5%8E%9F%E5%88%9B%E7%BC%96%E8%AF%91%EF%BC%8C%5BLinux%E4%B8%AD%E5%9B%BD%5D%EF%BC%88https://linux.cn/%EF%BC%89%E8%8D%A3%E8%AA%89%E6%8E%A8%E5%87%BA)
听说过时间表，但是你是否知道“哈希表”
探索 哈希表 hash table 的世界并理解其底层的机制是非常有趣的，并且将会受益匪浅。所以，让我们了解它，并从头开始探索吧。哈希表是许多现代软件应用程序中一种常见的数据结构。它提供了类似字典的功能，使你能够在其中执行插入、删除和删除等操作。这么说吧，比如我想找出“苹果”的定义是什么，并且我知道该定义被存储在了我定义的哈希表中。我将查询我的哈希表来得到定义。它在哈希表内的记录看起来可能像："苹果" => "一种拥有水果之王之称的绿色水果"。这里，“苹果”是我的关键字，而“一种拥有水果之王之称的水果”是与之关联的值。还有一个例子可以让我们更清楚，哈希表的内容如下："面包" => "固体" "水" => "液体" "汤" => "液体" "玉米片" => "固体" 我想知道面包是固体还是液体，所以我将查询哈希表来获取与之相关的值，该哈希表将返回“固体”给我。现在，我们大致了解了哈希表是如何工作的。使用哈希表需要注意的另一个重要概念是每一个关键字都是唯一的。如果到了明天，我拥有一个面包奶昔（它是液体），那么我们需要更新哈希表，把“固体”改为“液体”来反映哈希表的改变。所以，我们需要添加一条记录到字典中：关键字为“面包”，对应的值为“液体”。你能发现下面的表发生了什么变化吗？（LCTT 译注：不知道这个“面包奶昔”是一种什么食物，大约是一种面包做的奶昔，总之你就理解成作者把液体的“面包奶昔”当成一种面包吧。）"面包" => "液体" "水" => "液体" "汤" => "液体" "玉米片" => "固体" 没错，“面包”对应的值被更新为了“液体”。关键字是唯一的，我的面包不能既是液体又是固体。但是，是什么使得该数据结构与其他数据结构相比如此特殊呢？为什么不使用一个数组来代替呢？它取决于问题的本质。对于某一个特定的问题，使用数组来描述可能会更好，因此，我们需要注意的关键点就是，我们应该选择最适合问题的数据结构。例如，如果你需要做的只是存储一个简单的杂货列表，那么使用数组会很适合。考虑下面的两个问题，两个问题的本质完全不同。我需要一个水果的列表我需要一个水果的列表以及各种水果的价格（每千克）正如你在下面所看到的，用数组来存储水果的列表可能是更好的选择。但是，用哈希表来存储每一种水果的价格看起来是更好的选择。//示例数组 ["苹果", "桔子", "梨子", "葡萄"] //示例哈希表 { "苹果" : 3.05, "桔子" : 5.5, "梨子" : 8.4, "葡萄" : 12.4 } 实际上，有许多的机会需要使用哈希表。时间以及它对你的意义这里有篇对时间复杂度和空间复杂度的一个复习。平均情况下，在哈希表中进行搜索、插入和删除记录的时间复杂度均为 O(1) 。实际上，O(1) 读作“大 O 1”，表示常数时间。这意味着执行每一种操作的运行时间不依赖于数据集中数据的数量。我可以保证，查找、插入和删除项目均只花费常数时间，“当且仅当”哈希表的实现方式正确时。如果实现不正确，可能需要花费很慢的 O(n) 时间，尤其是当所有的数据都映射到了哈希表中的同一位置/点。构建一个好的哈希表到目前为止，我们已经知道如何使用哈希表了，但是如果我们想构建一个哈希表呢？本质上我们需要做的就是把一个字符串（比如 “狗”）映射到一个哈希代码（一个生成的数），即映射到一个数组的索引。你可能会问，为什么不直接使用索引呢？为什么要这么麻烦呢？因为通过这种方式我们可以直接查询 “狗” 并立即得到 “狗” 所在的位置，String name = Array["狗"] // 名字叫拉斯。而使用索引查询名称时，可能出现的情况是我们不知道名称所在的索引。比如，String name = Array[10] // 该名字现在叫鲍勃 - 那不是我的狗的名字。这就是把一个字符串映射到一个哈希代码的益处（对应于一个数组的索引而言）。我们可以通过使用模运算符和哈希表的大小来计算出数组的索引：index = hash_code % table_size。我们需要避免的另一种情况是两个关键字映射到同一个索引，这叫做哈希碰撞，如果哈希函数实现的不好，这很容易发生。实际上，每一个输入比输出多的哈希函数都有可能发生碰撞。通过下面的同一个函数的两个输出来展示一个简单的碰撞：int cat_idx = hashCode("猫") % table_size; //cat_idx 现在等于 1 int dog_idx = hashCode("狗") % table_size; //dog_idx 也等于 1 我们可以看到，现在两个数组的索引均是 1 。这样将会出现两个值相互覆盖，因为它们被写到了相同的索引中。如果我们查找 “猫” 的值，将会返回 “拉斯” ，但是这并不是我们想要的。有许多可以解决哈希碰撞的方法，但是更受欢迎的一种方法叫做链接。链接的想法就是对于数组的每一个索引位置都有一个链表，如果碰撞发生，值就被存到链表中。因此，在前面的例子中，我们将会得到我们需要的值，但是我们需要搜索数组中索引为 1 的位置上的链表。伴有链接的哈希实现需要 O(1 + α) 时间，其中 α 是装载因子，它可以表示为 n/k，其中 n 是哈希表中的记录数目，k 是哈希表中可用位置的数目。但是请记住，只有当你给出的关键字非常随机时，这一结论才正确（依赖于 SUHA）。这是做了一个很大的假设，因为总是有可能任何不相等的关键字都散列到同一点。这一问题的一个解决方法是去除哈希表中关键字对随机性的依赖，转而把随机性集中于关键字是如何被散列的，从而减少矛盾发生的可能性。这被称为……通用散列这个观念很简单，从 通用散列 universal hash 家族集合随机选择一个哈希函数 h 来计算哈希代码。换句话来说，就是选择任何一个随机的哈希函数来散列关键字。通过这种方法，两个不同的关键字的散列结果相同的可能性将非常低（LCTT 译注：原文是“not be the same”，应是笔误）。我只是简单的提一下，如果不相信我那么请相信数学。实现这一方法时需要注意的另一件事是如果选择了一个不好的通用散列家族，它会把时间和空间复杂度拖到 O(U)，其中 U 是散列家族的大小。而其中的挑战就是找到一个不需要太多时间来计算，也不需要太多空间来存储的哈希家族。上帝哈希函数追求完美是人的天性。我们是否能够构建一个完美的哈希函数，从而能够把关键字映射到整数集中，并且几乎没有碰撞。好消息是我们能够在一定程度上做到，但是我们的数据必须是静态的（这意味着在一定时间内没有插入/删除/更新）。一个实现完美哈希函数的方法就是使用 2 级哈希 2-Level Hashing ，它基本上是我们前面讨论过的两种方法的组合。它使用通用散列来选择使用哪个哈希函数，然后通过链接组合起来，但是这次不是使用链表数据结构，而是使用另一个哈希表。让我们看一看下面它是怎么实现的：但是这是如何工作的以及我们如何能够确保无需关心碰撞？它的工作方式与生日悖论相反。它指出，在随机选择的一堆人中，会有一些人生日相同。但是如果一年中的天数远远大于人数（平方以上），那么有极大的可能性所有人的生日都不相同。所以这二者是如何相关的？对于每一个链接哈希表，其大小均为第一级哈希表大小的平方。那就是说，如果有两个元素被散列到同一个点，那么链接哈希表的大小将为 4 。大多数时候，链接哈希表将会非常稀疏/空。重复下面两步来确保无需担心碰撞：从通用散列家族中选择一个哈希函数来计算如果发生碰撞，那么继续从通用散列家族中选择另一个哈希函数来计算字面上看就是这样（这是一个 O(n^2) 空间的解）。如果需要考虑空间问题，那么显然需要另一个不同的方法。但是值得庆幸的是，该过程平均只需要进行两次。总结只有具有一个好的哈希函数才能算得上是一个好的哈希表。在同时保证功能实现、时间和空间的提前下构建一个完美的哈希函数是一件很困难的事。我推荐你在解决问题的时候首先考虑哈希表，因为它能够为你提供巨大的性能优势，而且它能够对应用程序的可用性产生显著差异。哈希表和完美哈希函数常被用于实时编程应用中，并且在各种算法中都得到了广泛应用。你见或者不见，哈希表就在这儿。via: http://www.zeroequalsfalse.press/2017/02/20/hashtables/作者：Marty Jacobs 译者：ucasFL 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
Python 3 的标准库中没多少用来解决加密的，不过却有用于处理哈希的库。在这里我们会对其进行一个简单的介绍，但重点会放在两个第三方的软件包：PyCrypto 和 cryptography 上。我们将学习如何使用这两个库，来加密和解密字符串。哈希如果需要用到安全哈希算法或是消息摘要算法，那么你可以使用标准库中的 hashlib 模块。这个模块包含了符合 FIPS（美国联邦信息处理标准）的安全哈希算法，包括 SHA1，SHA224，SHA256，SHA384，SHA512 以及 RSA 的 MD5 算法。Python 也支持 adler32 以及 crc32 哈希函数，不过它们在 zlib 模块中。哈希的一个最常见的用法是，存储密码的哈希值而非密码本身。当然了，使用的哈希函数需要稳健一点，否则容易被破解。另一个常见的用法是，计算一个文件的哈希值，然后将这个文件和它的哈希值分别发送。接收到文件的人可以计算文件的哈希值，检验是否与接受到的哈希值相符。如果两者相符，就说明文件在传送的过程中未经篡改。让我们试着创建一个 md5 哈希：>>> import hashlib >>> md5 = hashlib.md5() >>> md5.update('Python rocks!') Traceback (most recent call last): File "<pyshell#5>", line 1, in <module> md5.update('Python rocks!') TypeError: Unicode-objects must be encoded before hashing >>> md5.update(b'Python rocks!') >>> md5.digest() b'\x14\x82\xec\x1b#d\xf6N}\x16*+[\x16\xf4w' 让我们花点时间一行一行来讲解。首先，我们导入 hashlib ，然后创建一个 md5 哈希对象的实例。接着，我们向这个实例中添加一个字符串后，却得到了报错信息。原来，计算 md5 哈希时，需要使用字节形式的字符串而非普通字符串。正确添加字符串后，我们调用它的 digest 函数来得到哈希值。如果你想要十六进制的哈希值，也可以用以下方法：>>> md5.hexdigest() '1482ec1b2364f64e7d162a2b5b16f477' 实际上，有一种精简的方法来创建哈希，下面我们看一下用这种方法创建一个 sha1 哈希：>>> sha = hashlib.sha1(b'Hello Python').hexdigest() >>> sha '422fbfbc67fe17c86642c5eaaa48f8b670cbed1b' 可以看到，我们可以同时创建一个哈希实例并且调用其 digest 函数。然后，我们打印出这个哈希值看一下。这里我使用 sha1 哈希函数作为例子，但它不是特别安全，读者可以随意尝试其他的哈希函数。密钥导出Python 的标准库对密钥导出支持较弱。实际上，hashlib 函数库提供的唯一方法就是 pbkdf2\_hmac 函数。它是 PKCS#5 的基于口令的第二个密钥导出函数，并使用 HMAC 作为伪随机函数。因为它支持“ 加盐 （ salt ） ”和迭代操作，你可以使用类似的方法来哈希你的密码。例如，如果你打算使用 SHA-256 加密方法，你将需要至少 16 个字节的“盐”，以及最少 100000 次的迭代操作。简单来说，“盐”就是随机的数据，被用来加入到哈希的过程中，以加大破解的难度。这基本可以保护你的密码免受字典和 彩虹表 （ rainbow table ） 的攻击。让我们看一个简单的例子：>>> import binascii >>> dk = hashlib.pbkdf2_hmac(hash_name='sha256', password=b'bad_password34', salt=b'bad_salt', iterations=100000) >>> binascii.hexlify(dk) b'6e97bad21f6200f9087036a71e7ca9fa01a59e1d697f7e0284cd7f9b897d7c02' 这里，我们用 SHA256 对一个密码进行哈希，使用了一个糟糕的盐，但经过了 100000 次迭代操作。当然，SHA 实际上并不被推荐用来创建密码的密钥。你应该使用类似 scrypt 的算法来替代。另一个不错的选择是使用一个叫 bcrypt 的第三方库，它是被专门设计出来哈希密码的。PyCryptodomePyCrypto 可能是 Python 中密码学方面最有名的第三方软件包。可惜的是，它的开发工作于 2012 年就已停止。其他人还在继续发布最新版本的 PyCrypto，如果你不介意使用第三方的二进制包，仍可以取得 Python 3.5 的相应版本。比如，我在 Github (https://github.com/sfbahr/PyCrypto-Wheels) 上找到了对应 Python 3.5 的 PyCrypto 二进制包。幸运的是，有一个该项目的分支 PyCrytodome 取代了 PyCrypto 。为了在 Linux 上安装它，你可以使用以下 pip 命令：pip install pycryptodome 在 Windows 系统上安装则稍有不同：pip install pycryptodomex 如果你遇到了问题，可能是因为你没有安装正确的依赖包（LCTT 译注：如 python-devel），或者你的 Windows 系统需要一个编译器。如果你需要安装上的帮助或技术支持，可以访问 PyCryptodome 的网站。还值得注意的是，PyCryptodome 在 PyCrypto 最后版本的基础上有很多改进。非常值得去访问它们的主页，看看有什么新的特性。加密字符串访问了他们的主页之后，我们可以看一些例子。在第一个例子中，我们将使用 DES 算法来加密一个字符串：>>> from Crypto.Cipher import DES >>> key = 'abcdefgh' >>> def pad(text): while len(text) % 8 != 0: text += ' ' return text >>> des = DES.new(key, DES.MODE_ECB) >>> text = 'Python rocks!' >>> padded_text = pad(text) >>> encrypted_text = des.encrypt(text) Traceback (most recent call last): File "<pyshell#35>", line 1, in <module> encrypted_text = des.encrypt(text) File "C:\Programs\Python\Python35-32\lib\site-packages\Crypto\Cipher\blockalgo.py", line 244, in encrypt return self._cipher.encrypt(plaintext) ValueError: Input strings must be a multiple of 8 in length >>> encrypted_text = des.encrypt(padded_text) >>> encrypted_text b'>\xfc\x1f\x16x\x87\xb2\x93\x0e\xfcH\x02\xd59VQ' 这段代码稍有些复杂，让我们一点点来看。首先需要注意的是，DES 加密使用的密钥长度为 8 个字节，这也是我们将密钥变量设置为 8 个字符的原因。而我们需要加密的字符串的长度必须是 8 的倍数，所以我们创建了一个名为 pad 的函数，来给一个字符串末尾填充空格，直到它的长度是 8 的倍数。然后，我们创建了一个 DES 的实例，以及我们需要加密的文本。我们还创建了一个经过填充处理的文本。我们尝试着对未经填充处理的文本进行加密，啊欧，报了一个 ValueError 错误！我们需要对经过填充处理的文本进行加密，然后得到加密的字符串。（LCTT 译注：encrypt 函数的参数应为 byte 类型字符串，代码为：encrypted_text = des.encrypt(padded_text.encode('utf-8'))）知道了如何加密，还要知道如何解密：>>> des.decrypt(encrypted_text) b'Python rocks! ' 幸运的是，解密非常容易，我们只需要调用 des 对象的 decrypt 方法就可以得到我们原来的 byte 类型字符串了。下一个任务是学习如何用 RSA 算法加密和解密一个文件。首先，我们需要创建一些 RSA 密钥。创建 RSA 密钥如果你希望使用 RSA 算法加密数据，那么你需要拥有访问 RAS 公钥和私钥的权限，否则你需要生成一组自己的密钥对。在这个例子中，我们将生成自己的密钥对。创建 RSA 密钥非常容易，所以我们将在 Python 解释器中完成。>>> from Crypto.PublicKey import RSA >>> code = 'nooneknows' >>> key = RSA.generate(2048) >>> encrypted_key = key.exportKey(passphrase=code, pkcs=8, protection="scryptAndAES128-CBC") >>> with open('/path_to_private_key/my_private_rsa_key.bin', 'wb') as f: f.write(encrypted_key) >>> with open('/path_to_public_key/my_rsa_public.pem', 'wb') as f: f.write(key.publickey().exportKey()) 首先我们从 Crypto.PublicKey 包中导入 RSA，然后创建一个傻傻的密码。接着我们生成 2048 位的 RSA 密钥。现在我们到了关键的部分。为了生成私钥，我们需要调用 RSA 密钥实例的 exportKey 方法，然后传入密码，使用的 PKCS 标准，以及加密方案这三个参数。之后，我们把私钥写入磁盘的文件中。接下来，我们通过 RSA 密钥实例的 publickey 方法创建我们的公钥。我们使用方法链调用 publickey 和 exportKey 方法生成公钥，同样将它写入磁盘上的文件。加密文件有了私钥和公钥之后，我们就可以加密一些数据，并写入文件了。这里有个比较标准的例子：from Crypto.PublicKey import RSA from Crypto.Random import get_random_bytes from Crypto.Cipher import AES, PKCS1_OAEP with open('/path/to/encrypted_data.bin', 'wb') as out_file: recipient_key = RSA.import_key( open('/path_to_public_key/my_rsa_public.pem').read()) session_key = get_random_bytes(16) cipher_rsa = PKCS1_OAEP.new(recipient_key) out_file.write(cipher_rsa.encrypt(session_key)) cipher_aes = AES.new(session_key, AES.MODE_EAX) data = b'blah blah blah Python blah blah' ciphertext, tag = cipher_aes.encrypt_and_digest(data) out_file.write(cipher_aes.nonce) out_file.write(tag) out_file.write(ciphertext) 代码的前三行导入 PyCryptodome 包。然后我们打开一个文件用于写入数据。接着我们导入公钥赋给一个变量，创建一个 16 字节的会话密钥。在这个例子中，我们将使用混合加密方法，即 PKCS#1 OAEP ，也就是最优非对称加密填充。这允许我们向文件中写入任意长度的数据。接着我们创建 AES 加密，要加密的数据，然后加密数据。我们将得到加密的文本和消息认证码。最后，我们将随机数，消息认证码和加密的文本写入文件。顺便提一下，随机数通常是真随机或伪随机数，只是用来进行密码通信的。对于 AES 加密，其密钥长度最少是 16 个字节。随意用一个你喜欢的编辑器试着打开这个被加密的文件，你应该只能看到乱码。现在让我们学习如何解密我们的数据。from Crypto.PublicKey import RSA from Crypto.Cipher import AES, PKCS1_OAEP code = 'nooneknows' with open('/path/to/encrypted_data.bin', 'rb') as fobj: private_key = RSA.import_key( open('/path_to_private_key/my_rsa_key.pem').read(), passphrase=code) enc_session_key, nonce, tag, ciphertext = [ fobj.read(x) for x in (private_key.size_in_bytes(), 16, 16, -1) ] cipher_rsa = PKCS1_OAEP.new(private_key) session_key = cipher_rsa.decrypt(enc_session_key) cipher_aes = AES.new(session_key, AES.MODE_EAX, nonce) data = cipher_aes.decrypt_and_verify(ciphertext, tag) print(data) 如果你认真看了上一个例子，这段代码应该很容易解析。在这里，我们先以二进制模式读取我们的加密文件，然后导入私钥。注意，当你导入私钥时，需要提供一个密码，否则会出现错误。然后，我们文件中读取数据，首先是加密的会话密钥，然后是 16 字节的随机数和 16 字节的消息认证码，最后是剩下的加密的数据。接下来我们需要解密出会话密钥，重新创建 AES 密钥，然后解密出数据。你还可以用 PyCryptodome 库做更多的事。不过我们要接着讨论在 Python 中还可以用什么来满足我们加密解密的需求。cryptography 包cryptography 的目标是成为“ 人类易于使用的密码学包 （ cryptography for humans ） ”，就像 requests 是“ 人类易于使用的 HTTP 库 （ HTTP for Humans ） ”一样。这个想法使你能够创建简单安全、易于使用的加密方案。如果有需要的话，你也可以使用一些底层的密码学基元，但这也需要你知道更多的细节，否则创建的东西将是不安全的。如果你使用的 Python 版本是 3.5, 你可以使用 pip 安装，如下：pip install cryptography 你会看到 cryptography 包还安装了一些依赖包（LCTT 译注：如 libopenssl-devel）。如果安装都顺利，我们就可以试着加密一些文本了。让我们使用 Fernet 对称加密算法，它保证了你加密的任何信息在不知道密码的情况下不能被篡改或读取。Fernet 还通过 MultiFernet 支持密钥轮换。下面让我们看一个简单的例子：>>> from cryptography.fernet import Fernet >>> cipher_key = Fernet.generate_key() >>> cipher_key b'APM1JDVgT8WDGOWBgQv6EIhvxl4vDYvUnVdg-Vjdt0o=' >>> cipher = Fernet(cipher_key) >>> text = b'My super secret message' >>> encrypted_text = cipher.encrypt(text) >>> encrypted_text (b'gAAAAABXOnV86aeUGADA6mTe9xEL92y_m0_TlC9vcqaF6NzHqRKkjEqh4d21PInEP3C9HuiUkS9f' b'6bdHsSlRiCNWbSkPuRd_62zfEv3eaZjJvLAm3omnya8=') >>> decrypted_text = cipher.decrypt(encrypted_text) >>> decrypted_text b'My super secret message' 首先我们需要导入 Fernet，然后生成一个密钥。我们输出密钥看看它是什么样儿。如你所见，它是一个随机的字节串。如果你愿意的话，可以试着多运行 generate\_key 方法几次，生成的密钥会是不同的。然后我们使用这个密钥生成 Fernet 密码实例。现在我们有了用来加密和解密消息的密码。下一步是创建一个需要加密的消息，然后使用 encrypt 方法对它加密。我打印出加密的文本，然后你可以看到你再也读不懂它了。为了解密出我们的秘密消息，我们只需调用 decrypt 方法，并传入加密的文本作为参数。结果就是我们得到了消息字节串形式的纯文本。小结这一章仅仅浅显地介绍了 PyCryptodome 和 cryptography 这两个包的使用。不过这也确实给了你一个关于如何加密解密字符串和文件的简述。请务必阅读文档，做做实验，看看还能做些什么！相关阅读Github 上 Python 3 的 PyCrypto WheelsPyCryptodome 的 文档Python’s 加密 服务Cryptography 包的 官网via: http://www.blog.pythonlibrary.org/2016/05/18/python-3-an-intro-to-encryption/作者：Mike 译者：Cathon 校对：wxy本文由 LCTT 原创翻译，Linux中国 荣誉推出
最近一个新闻说，原本各大浏览器厂商推动在 HTTPS 中放弃支持 SHA-1 算法，但是由于 Facebook 等公司认为尚有少部分用户采用老式的 SHA-1 算法，而建议延长支持期。姑且不论浏览器厂商和应用厂商的做法谁更合理，那么这里提到的 SHA-1 算法是什么呢？它有什么风险么？密码学里面有一类算法叫做 哈希 hash 算法，也称作散列算法、摘要算法，通常用于对一段信息的取样。当你给它一段 信息 （ message ） 时，可以用特定算法生成一段 信息摘要 （ message digest ） ，通常摘要的长度更短。 摘要 （ digest ） 可以表示这段信息的某种特征——就如同指纹一样，所以这个特征也叫做 指纹 （ fingerprint ） 、 校验和 checksum 。这种算法包括我们经常听说的 MD5 、SHA-1 等算法。它通常用于加密体系的信息摘要，以建立一个可靠、安全的数据交互通道。而现在，随着对加密技术的研究和计算能力的提升，不断发现摘要算法中的缺陷和攻击方法，因此，对于涉及到数据安全的算法方面，建议每过一个阶段就更换一次摘要算法。理想情况下，哈希算法应该有四个重要特性：不可逆：不能从摘要生成其原始信息无冲突：不同的信息具备不同的摘要易计算：对任意信息容易计算其摘要特征化：信息修改后其摘要一定变化当然，实际上，前两个特性在应用中有一些不成立的情况。虽然算法可以做到不可完全逆转，但是存在找到生成相同摘要的两段或更多信息的可能性。这是因为摘要信息的域值范围有限，只能表现有限种类的信息，在用来表示无限的信息时，肯定存在冲突。而在摘要算法的应用场景中，往往并不要求使用具体的原始信息，只要你能生成同样的摘要就可以了，因此，也出现了类似彩虹表这样的数据库，供根据摘要信息查询原始信息。而且由于算法本身可能会存在的缺陷，就有可能通过算法找到两个具有相同摘要的信息。比如 2004 年，山东大学的王小云教授就率团队突破了 MD5 算法，可以找到具备相同的 MD5 摘要的两段信息，从而为 MD5 算法的死亡盖上了“核准”印章。那么我们就来看看，包括 MD5 在内的这些哈希算法们，都活着怎么样？据 valerieaurora.org 的跟踪，当前的摘要算法们的生存状况如下：从上图可以看到，SHA-2 之前的算法，除了 RIPEMD-160 外，都已经被攻破或存在可实现的碰撞算法了，因此，再将其应用到产品中，就存在了各种风险。所以，尽快升级你的加密策略吧。