每个程序员都应该知道的 40 个算法（三）（4）

每个程序员都应该知道的 40 个算法（三）（3）https://developer.aliyun.com/article/1506359

了解数据的敏感性

了解数据的机密性很重要。我们还需要考虑数据泄露的后果有多严重。数据的分类有助于我们选择正确的加密算法。根据信息的敏感性，有多种分类数据的方式。让我们看看数据分类的典型方式：

• 公共数据或未分类数据：任何对公众可用的数据。例如，在公司网站或政府信息门户上找到的信息。
  
• 内部数据或机密数据：虽然不适合公开，但将这些数据暴露给公众可能不会造成破坏性后果。例如，如果员工的投诉经理的电子邮件被曝光，这可能会让公司尴尬，但可能不会造成破坏性后果。
  
• 敏感数据或机密数据：不应该公开的数据，如果暴露给公众，对个人或组织会造成破坏性后果。例如，泄露未来 iPhone 的细节可能会损害苹果的业务目标，并给三星等竞争对手带来优势。
  
• 高度敏感数据：也称为绝密数据。这是如果泄露将对组织造成极大损害的信息。这可能包括客户社会安全号码、信用卡号码或其他非常敏感的信息。绝密数据通过多层安全保护，并需要特别许可才能访问。
  

一般来说，更复杂的安全设计比简单的算法要慢得多。在安全性和系统性能之间取得正确的平衡非常重要。

了解密码的基本设计

设计密码是为了想出一种算法，可以混淆敏感数据，使恶意进程或未经授权的用户无法访问它。尽管随着时间的推移，密码变得越来越复杂，但密码基于的基本原理保持不变。

让我们从一些相对简单的密码开始，这将帮助我们理解加密算法设计中使用的基本原理。

呈现替换密码

替换密码在各种形式上已经使用了数百年。顾名思义，替换密码基于一个简单的概念——以预定的有序方式用其他字符替换明文中的字符。

让我们看看其中涉及的确切步骤：

1. 首先，我们将每个字符映射到一个替代字符。
   
2. 然后，通过替换映射，将明文编码并转换为密文，用密文中的另一个字符替换明文中的每个字符。
   
3. 解码时，使用替换映射将明文还原。
   

让我们看一些例子：

• 凯撒密码：

在凯撒密码中，替换映射是通过用右边的第三个字符替换每个字符来创建的。这个映射在下图中描述：

让我们看看如何使用 Python 实现凯撒密码：

import string
rotation = 3
P = 'CALM'; C=''
for letter in P:
   C = C+ (chr(ord(letter) + rotation))

我们可以看到我们对明文CALM应用了凯撒密码。

让我们用凯撒密码加密后打印密文：

据说凯撒密码曾被朱利叶斯·凯撒用来与他的顾问交流。

• 旋转 13（ROT13）：

ROT13 是另一种基于替换的加密。在 ROT13 中，替换映射是通过用右边的第 13 个字符替换每个字符来创建的。以下图表说明了这一点：

这意味着如果ROT13()是实现 ROT13 的函数，那么以下内容适用：

import codecs
P = 'CALM'
C=''
C=codecs.encode(P, 'rot_13')

现在，让我们打印C的编码值：

• 替换密码的密码分析：

替换密码很容易实现和理解。不幸的是，它们也很容易破解。替换密码的简单密码分析表明，如果我们使用英语字母表，那么我们需要确定的是破解密码的旋转量。我们可以逐个尝试英语字母表的每个字母，直到我们能够解密文本。这意味着需要大约 25 次尝试才能重构明文。

现在，让我们看另一种简单密码—置换密码。

理解置换密码

在置换密码中，明文的字符被置换。让我们看一下其中涉及的步骤：

1. 创建矩阵并选择置换矩阵的大小。它应该足够大，以适应明文字符串。
   
2. 通过横向写入字符串的所有字符来填充矩阵。
   
3. 在矩阵中垂直读取字符串的所有字符。
   

让我们看一个例子。

让我们以Ottawa Rocks明文(P)为例。

首先，让我们对P进行编码。为此，我们将使用一个 3 x 4 的矩阵，横向写入明文：

read过程将垂直读取字符串，这将生成密码文本—OwctaktRsao。

德国人在第一次世界大战中使用了一种名为 ADFGVX 的密码，它同时使用了置换和替换密码。多年后，它被 George Painvin 破解。

因此，这些是一些密码类型。现在，让我们看一些当前使用的密码技术。

理解密码技术的类型

不同类型的密码技术使用不同类型的算法，并在不同的情况下使用。

广义上，密码技术可以分为以下三种类型：

• 散列
  
• 对称
  
• 非对称
  

让我们逐个来看。

使用密码哈希函数

密码哈希函数是一种数学算法，可以用来创建消息的唯一指纹。它从明文中创建一个称为哈希的固定大小的输出。

从数学上看，这看起来是这样的：

C[1] = hashFunction(P[1])

这是解释如下的：

• P[1] 是表示输入数据的明文。
  
• C[1] 是由密码哈希函数生成的固定长度哈希。
  

这在下图中显示。可变长度数据通过单向哈希函数转换为固定长度哈希：

哈希函数具有以下五个特征：

• 它是确定性的。相同的明文生成相同的哈希。
  
• 唯一的输入字符串应该生成唯一的输出哈希值。
  
• 无论输入消息如何，它都具有固定长度。
  
• 明文中的微小变化会生成新的哈希。
  
• 它是一个单向函数，这意味着无法从密码文本C[1]生成明文P[1]。
  

如果我们遇到每个唯一消息没有唯一哈希的情况，我们称之为碰撞。也就是说，如果我们有两个文本P[1]和P[2]，在碰撞的情况下，意味着hashFunction(P[1]) = hashFunction(P[2])。

无论使用的哈希算法如何，碰撞都是罕见的。否则，哈希将毫无用处。然而，对于一些应用，不能容忍碰撞。在这些情况下，我们需要使用一个更复杂但生成碰撞哈希值的可能性更小的哈希算法。

实现密码哈希函数

密码哈希函数可以通过使用各种算法来实现。让我们深入了解其中的两种。

理解 MD5 容忍

MD5 是由 Poul-Henning Kamp 于 1994 年开发的，用来替代 MD4。它生成 128 位哈希。MD5 是一个相对简单的算法，容易发生碰撞。在不能容忍碰撞的应用中，不应使用 MD5。

让我们看一个例子。为了在 Python 中生成 MD5 哈希，我们将使用passlib库，这是一个最流行的开源库之一，实现了 30 多种密码哈希算法。如果它还没有安装在您的设备上，请在 Jupyter 笔记本中使用以下代码安装它：

!pip install passlib

在 Python 中，我们可以按照以下方式生成 MD5 哈希：

请注意，MD5 生成 128 位的哈希。

如前所述，我们可以将生成的哈希用作原始文本的指纹，原始文本是myPassword。让我们看看如何在 Python 中实现这一点：

请注意，对myPassword字符串生成的哈希与原始哈希匹配，生成了一个True值。但是，一旦明文更改为myPassword2，它就返回了False。

现在，让我们来看另一个哈希算法——安全哈希算法（SHA）。

理解 SHA

SHA 是由国家标准与技术研究所（NIST）开发的。让我们看看如何使用 Python 来创建 SHA 算法的哈希：

from passlib.hash import sha512_crypt
sha512_crypt.using(salt = "qIo0foX5",rounds=5000).hash("myPassword")

请注意使用一个名为salt的参数。加盐是在哈希之前添加随机字符的过程。

运行这段代码将给我们带来以下结果：

请注意，当我们使用 SHA 算法时，生成的哈希是 512 字节。

加密哈希函数的应用

哈希函数用于在复制文件后检查文件的完整性。为了实现这一点，当文件从源复制到目的地（例如，从 Web 服务器下载时），相应的哈希也会被复制。这个原始哈希，h[original]，充当了原始文件的指纹。复制文件后，我们再次从复制的文件版本生成哈希，即h[copied]。如果h[original] = h[copied]—也就是说，生成的哈希与原始哈希匹配—这验证了文件没有改变，并且在下载过程中没有丢失任何数据。我们可以使用任何加密哈希函数，比如 MD5 或 SHA，来为此目的生成哈希。

现在，让我们来看对称加密。

使用对称加密

在密码学中，密钥是一组数字，用于使用我们选择的算法对明文进行编码。在对称加密中，我们使用相同的密钥进行加密和解密。如果用于对称加密的密钥是K，那么对称加密的等式如下：

EK = C

这里，P是明文，C是密文。

对于解密，我们使用相同的密钥K将其转换回P：

DK = P

这个过程在下面的图表中显示：

现在，让我们看看如何在 Python 中使用对称加密。

编写对称加密

在本节中，我们将使用 Python 的cryptography包来演示对称加密。它是一个全面的包，实现了许多加密算法，比如对称密码和不同的消息摘要。第一次使用时，我们需要使用pip命令来安装它：

!pip install cryptography

安装完成后，我们现在可以使用该包来实现对称加密，如下所示：

1. 首先，让我们导入我们需要的包：

import cryptography as crypt
from cryptography.fernet import Fernet

1. 让我们生成密钥：

1. 现在，让我们打开密钥：

file = open('mykey.key', 'wb')
file.write(key) 
file.close()

1. 使用密钥，现在让我们尝试加密消息：

file = open('mykey.key', 'rb')
key = file.read() 
file.close()

1. 现在，让我们使用相同的密钥解密消息：

from cryptography.fernet import Fernet
message = "Ottawa is really cold".encode()
f = Fernet(key)
encrypted = f.encrypt(message)

1. 让我们解密消息并将其赋给一个名为decrypt的变量：

decrypted = f.decrypt(encrypted)

1. 现在让我们打印decrypt变量，以验证我们是否能够得到相同的消息：

让我们看一些对称加密的优势。

对称加密的优势

尽管对称加密的性能取决于所使用的确切算法，但一般来说，它比非对称加密快得多。

对称加密的问题

当两个用户或进程计划使用对称加密进行通信时，它们需要使用安全通道交换密钥。这引发了以下两个问题：

• 密钥保护：如何保护对称加密密钥。
  
• 密钥分发：如何将对称加密密钥从源共享到目的地。
  

现在，让我们看一下非对称加密。

非对称加密

在 20 世纪 70 年代，非对称加密被设计出来以解决我们在前一节中讨论的对称加密的一些弱点。

非对称加密的第一步是生成两个看起来完全不同但在算法上相关的不同密钥。其中一个被选择为私钥，K[pr]，另一个被选择为公钥，K[pu]。在数学上，我们可以表示如下：

EKpr = C

这里，P是明文，C是密文。

我们可以按以下方式解密：

DKpu = P

公钥应该被自由分发，私钥由密钥对的所有者保密。

基本原则是，如果使用其中一个密钥进行加密，解密的唯一方法是使用另一个密钥。例如，如果我们使用公钥加密数据，我们将需要使用另一个密钥来解密它，即私钥。现在，让我们看一下非对称加密的一个基本协议——安全套接字层（SSL）/传输层安全性（TLS）握手，它负责使用非对称加密在两个节点之间建立连接。

SSL/TLS 握手算法

SSL 最初是为 HTTP 添加安全性而开发的。随着时间的推移，SSL 被更高效、更安全的协议 TLS 所取代。TLS 握手是 HTTP 创建安全通信会话的基础。TLS 握手发生在两个参与实体——客户端和服务器之间。此过程如下图所示：

TLS 握手在参与节点之间建立了安全连接。以下是涉及此过程的步骤：

1. 客户端向服务器发送一个“客户端 hello”消息。消息还包含以下内容：

• 所使用的 TLS 版本
  
• 客户端支持的密码套件列表
  
• 一个压缩算法
  
• 一个由byte_client标识的随机字节字符串
  

2. 服务器向客户端发送一个“服务器 hello”消息。消息还包含以下内容：

• 服务器从客户端提供的列表中选择的密码套件
  
• 一个会话 ID
  
• 一个由byte_server标识的随机字节字符串
  
• 包含服务器公钥的服务器数字证书，由cert_server标识
  
• 如果服务器需要客户端身份验证的数字证书或客户端证书请求，客户端服务器请求还包括以下内容：
  
• 可接受的 CA 的可区分名称
  
• 支持的证书类型
  

3. 客户端验证cert_server。
   
4. 客户端生成一个随机的字节字符串，由byte_client2标识，并使用服务器通过cert_server提供的公钥进行加密。
   
5. 客户端生成一个随机的字节字符串，并用自己的私钥进行加密。
   
6. 服务器验证客户端证书。
   
7. 客户端向服务器发送一个使用秘密密钥加密的“完成”消息。
   
8. 为了从服务器端确认这一点，服务器向客户端发送一个使用秘密密钥加密的“完成”消息。
   
9. 服务器和客户端现在建立了一个安全通道。他们现在可以交换使用共享秘密密钥对称加密的消息。整个方法如下所示：
   

现在，让我们讨论如何使用非对称加密来创建公钥基础设施（PKI），PKI 是为了满足组织的一个或多个安全目标而创建的。

公钥基础设施

非对称加密用于实现 PKI。PKI 是管理组织加密密钥的最流行和可靠的方式之一。所有参与者都信任一个名为 CA 的中央信任机构。CA 验证个人和组织的身份，然后为他们颁发数字证书（数字证书包含个人或组织的公钥副本和其身份），验证与该个人或组织相关联的公钥实际上属于该个人或组织。

它的工作方式是 CA 要求用户证明其身份，对个人和组织遵循不同的标准。这可能涉及简单地验证域名的所有权，也可能涉及更严格的过程，包括身份的物理证明，这取决于用户试图获得的数字证书的类型。如果 CA 确信用户确实是他们声称的人，用户随后通过安全通道向 CA 提供他们的公共加密密钥。CA 使用这些信息创建包含用户身份和他们的公钥信息的数字证书。该证书由 CA 数字签名。用户随后可以向任何想要验证其身份的人展示其证书，而无需通过安全通道发送它，因为证书本身不包含任何敏感信息。接收证书的人不必直接验证用户的身份。该人只需验证证书是否有效，验证 CA 的数字签名，以验证证书中包含的公钥实际上属于证书上命名的个人或组织。

组织的 CA 的私钥是 PKI 信任链中最薄弱的环节。例如，如果冒名顶替者获取了微软的私钥，他们可以通过冒充 Windows 更新在全球数百万台计算机上安装恶意软件。

示例-部署机器学习模型时的安全问题

在第六章中，无监督机器学习算法，我们看了CRISP-DM（跨行业标准数据挖掘过程）生命周期，该生命周期指定了训练和部署机器学习模型的不同阶段。一旦模型被训练和评估，最后阶段是部署。如果这是一个关键的机器学习模型，那么我们希望确保它的所有安全目标都得到满足。

让我们分析部署这样一个模型时面临的常见挑战，以及如何使用本章讨论的概念来解决这些挑战。我们将讨论保护我们训练好的模型免受以下三个挑战的策略：

• 中间人（MITM）攻击
  
• 冒充
  
• 数据篡改
  

让我们逐个来看。

中间人攻击

我们希望保护我们的模型免受的可能攻击之一是中间人攻击。中间人攻击发生在入侵者试图窃听假定为私人通信的情况下，部署训练好的机器学习模型。

让我们尝试使用一个示例场景来顺序理解中间人攻击。

假设鲍勃和爱丽丝想要使用 PKI 交换消息：

1. 鲍勃使用{Pr[Bob]，Pu[Bob]}，爱丽丝使用{Pr[Alice]，Pu[Alice]}。鲍勃创建了消息M[Bob]，爱丽丝创建了消息M[Alice]。他们希望以安全的方式彼此交换这些消息。
   
2. 最初，他们需要交换他们的公钥以建立彼此之间的安全连接。 这意味着鲍勃在发送消息给艾丽斯之前使用Pu[Alice]加密M[Bob]。
   
3. 假设我们有一个窃听者X，他正在使用{Pr[X]，Pu[X]}。 攻击者能够拦截鲍勃和艾丽斯之间的公钥交换，并用自己的公共证书替换它们。
   
4. 鲍勃将M[Bob]发送给艾丽斯，使用Pu[X]而不是Pu[Alice]进行加密，错误地认为这是艾丽斯的公共证书。 窃听者X拦截了通信。 它拦截了*M[Bob]消息并使用Pr[Bob]*解密。
   

这种中间人攻击显示在以下图表中：

现在，让我们看看如何防止中间人攻击。

如何防止中间人攻击

让我们探讨如何通过引入 CA 来防止中间人攻击到组织中。 假设这个 CA 的名字是 myTrustCA。 数字证书中嵌入了它的公钥，名为Pu[myTrustCA]。 myTrustCA 负责为组织中的所有人，包括艾丽斯和鲍勃签署证书。 这意味着鲍勃和艾丽斯的证书都由 myTrustCA 签署。 在签署他们的证书时，myTrustCA 验证他们确实是他们声称的人。

现在，有了这个新的安排，让我们重新审视鲍勃和艾丽斯之间的顺序交互：

1. 鲍勃正在使用{Pr[Bob]，Pu[Bob]}，艾丽斯正在使用{Pr[Alice]，Pu[Alice]}。 他们的公钥都嵌入到他们的数字证书中，由 myTrustCA 签名。 鲍勃创建了一条消息M[Bob]，艾丽斯创建了一条消息M[Alice]。 他们希望以安全的方式互相交换这些消息。
   
2. 他们交换他们的数字证书，其中包含他们的公钥。 只有在证书中嵌入的公钥由他们信任的 CA 签署时，他们才会接受这些公钥。 他们需要交换他们的公钥以建立彼此之间的安全连接。 这意味着鲍勃将使用Pu**[Alice]来加密M**[Bob]，然后将消息发送给艾丽斯。
   
3. 假设我们有一个窃听者X，他正在使用{Pr[X]，Pu[X]}。 攻击者能够拦截鲍勃和艾丽斯之间的公钥交换，并用自己的公共证书*Pu[X]*替换它们。
   
4. 鲍勃拒绝X的尝试，因为坏人的数字证书没有被鲍勃信任的 CA 签名。 安全握手被中止，尝试的攻击被记录下来，并且引发了安全异常。
   

在部署训练好的机器学习模型时，不是艾丽斯，而是一个部署服务器。 鲍勃只有在建立安全通道后才能部署模型，使用先前提到的步骤。

让我们看看如何在 Python 中实现这一点。

首先让我们导入所需的包。

from xmlrpc.client import SafeTransport, ServerProxy
import ssl

现在让我们创建一个可以验证证书的类。

class CertVerify(SafeTransport): 
    def __init__(self, cafile, certfile=None, keyfile=None): 
    SafeTransport.__init__(self) 
    self._ssl_context = ssl.SSLContext(ssl.PROTOCOL_TLSv1) 
    self._ssl_context.load_verify_locations(cafile) 
    if cert: 
        self._ssl_context.load_cert_chain(certfile, keyfile) 
    self._ssl_context.verify_mode = ssl.CERT_REQUIRED 
def make_connection(self, host): 
    s = super().make_connection((host, {'context': self._ssl_context})) 
    return s
# Create the client proxy
s = ServerProxy('https://cloudanum.com:15000', transport=VerifyCertSafeTransport('server_cert.pem'), allow_none=True)

让我们看看我们部署的模型可能面临的其他漏洞。

避免伪装

攻击者X假装成授权用户鲍勃，并获得对敏感数据的访问权限，这在这种情况下是训练模型。 我们需要保护模型免受任何未经授权的更改。

保护我们训练模型免受伪装的一种方法是使用授权用户的私钥对模型进行加密。 一旦加密，任何人都可以通过解密授权用户的公钥来读取和利用模型，这在他们的数字证书中找到。 没有人可以对模型进行任何未经授权的更改。

数据和模型加密

一旦模型部署，提供给模型作为输入的实时未标记数据也可能被篡改。训练好的模型用于推断并为这些数据提供标签。为了防止数据被篡改，我们需要保护静态数据和通信中的数据。为了保护静态数据，可以使用对称加密进行编码。可以建立基于 SSL/TLS 的安全通道来传输数据，以提供安全的隧道。这个安全隧道可以用来传输对称密钥，并且数据可以在提供给训练好的模型之前在服务器上解密。

这是保护数据免受篡改的更有效和可靠的方法之一。

在将模型部署到服务器之前，也可以使用对称加密对模型进行加密。这将防止在部署之前未经授权访问模型。

让我们看看如何使用以下步骤在源处使用对称加密加密训练好的模型，然后在目的地解密它，然后再使用它：

1. 让我们首先使用鸢尾花数据集训练一个简单的模型：

import cryptography as crypt
from sklearn.linear_model 
import LogisticRegression 
from cryptography.fernet 
import Fernet from sklearn.model_selection 
import train_test_split 
from sklearn.datasets import load_iris 
iris = load_iris() 
X = iris.data 
y = iris.target    
X_train, X_test, y_train, y_test = train_test_split(X, y) 
model = LogisticRegression() 
model.fit(X_train, y_train)

1. 现在，让我们定义将存储模型的文件的名称：

filename_source = 'myModel_source.sav' 
filename_destination = "myModel_destination.sav" 
filename_sec = "myModel_sec.sav"

请注意，filename_source 是将在源处存储训练好的未加密模型的文件。filename_destination 是将在目的地存储训练好的未加密模型的文件，filename_sec 是加密的训练好的模型。

1. 我们将使用 pickle 将训练好的模型存储在文件中：

from pickle import dump dump(model, open(filename_source, 'wb'))

1. 让我们定义一个名为 write_key() 的函数，它将生成一个对称密钥并将其存储在名为 key.key 的文件中：

def write_key():
     key = Fernet.generate_key()
     with open("key.key", "wb") as key_file:
         key_file.write(key)

1. 现在，让我们定义一个名为 load_key() 的函数，它可以从 key.key 文件中读取存储的密钥：

def load_key():
    return open("key.key", "rb").read()

1. 接下来，让我们定义一个 encrypt() 函数，它可以加密和训练模型，并将其存储在名为 filename_sec 的文件中：

def encrypt(filename, key):
     f = Fernet(key)
     with open(filename_source,"rb") as file:         
         file_data = file.read() 
     encrypted_data = f.encrypt(file_data)
     with open(filename_sec,"wb") as file:
         file.write(encrypted_data)

1. 我们将使用这些函数生成对称密钥并将其存储在文件中。然后，我们将读取此密钥并使用它将我们的训练好的模型存储在名为 filename_sec 的文件中：

write_key()
encrypt(filename_source,load_key())

现在模型已经加密。它将被传输到目的地，在那里将用于预测。

1. 首先，我们将定义一个名为 decrypt() 的函数，我们可以使用它来使用存储在 key.key 文件中的密钥将模型从 filename_sec 解密到 filename_destination：

def decrypt(filename, key):
     f = Fernet(key)     
     with open(filename_sec, "rb") as file:                
         encrypted_data = file.read()        
     decrypted_data = f.decrypt(encrypted_data)     
     with open(filename_destination, "wb") as file:         file.write(decrypted_data)

1. 现在让我们使用这个函数来解密模型并将其存储在名为 filename_destination 的文件中：

decrypt(filename_sec,load_key())

1. 现在让我们使用这个未加密的文件来加载模型并用于预测：

请注意，我们已经使用对称加密对模型进行了编码。如果需要，可以使用相同的技术来加密数据。

摘要

在本章中，我们学习了加密算法。我们首先确定了问题的安全目标。然后讨论了各种加密技术，还研究了 PKI 基础设施的细节。最后，我们研究了不同的方法来保护训练好的机器学习模型免受常见攻击。现在，您应该能够理解用于保护现代 IT 基础设施的安全算法的基本原理。

在下一章中，我们将研究设计大规模算法。我们将研究设计和选择大型算法涉及的挑战和权衡。我们还将研究使用 GPU 和集群来解决复杂问题。