密码学入门与实践

术语：

明文(plaintext or cleartext)：发送者想要传送给接收者的可理解消息

密码(ciphertext): 使用密码系统的明文加密生成无法理解的消息

加密(encryption): 将明文转换为密文的过程

解密(decryption): 将密文转换为明文的过程（加密反向）

传统密码学：

它也称为对称密钥或共享密钥加密。同一个密钥用于加密和解密消息。将下面这个例子视为传统加密：

你和你的室友都使用相同的钥匙来锁定/解锁你家的门。因此，您共享相同的密钥以保护房间。确实，你的室友可以有你的钥匙副本，这样他就可以在你工作时进入房间，反之亦然。

使用对称密钥的传统密码系统算法：数据加密标准（DES），高级加密标准（AES）

优点：快速。

缺点：不安全！

发送方和接收方必须就密钥达成一致，并阻止其他人访问密钥。(这样做)有一个大的问题，如果两者不在同一物理位置，该如何发布密钥。你在中国的时候怎么能把你的钥匙给你在美国的室友呢！

实用建议：对每条消息加密后都要更改对称密钥，以便在发生灾难时（密码分析，窃取等）只能泄漏一条消息。

密钥分发

在上一段中，我们讨论的了密码系统使用对称密钥，以及缺乏与室友安全共享密钥的有效方式。密钥分发有助于解决这个缺点。接下来，我们将解释如何通过不受信任的通信通道进行密钥交换。

Diffie-Hellman key exchange (Diffie-Hellman密钥交换)

这种密钥交换基于一种算法，该算法在数学上不能在合理的时间内轻松地计算大数的离散对数。在使用数字和抽象公式直接运行之前，我们将使用颜色概述算法。

1. 第1步：Alice和Bob达成了共同颜色的协议。

2. 第2步：Alice选择她不会告诉Bob的秘密颜色。鲍勃会做同样的事情。

3. 步骤3：Alice将共同颜色与秘密颜色混合，结果是混合物。Bob也将他的秘密颜色与普通颜色混合，并将会得到不同于alice的混合物。

4. 步骤4：Alice和Bob交换混合物。这是沟通中最关键的一步，因为”中间人攻击(man-in-the-middle)”可以访问这两种混合物。如果中间人有双方的混合物，这也将会是一个问题。

颜色分解是不可逆的。因此，找到两个秘密颜色的唯一机会是将所有可能的颜色与第一步中的常见颜色混合。此外，请记住，秘密颜色也可以是许多其他颜色的混合。

更新：Diffie-Hellman不会保护您免受中间人攻击。为了了解原因，想象一下攻击者从Alice接收所有消息并将其重播回Bob。

5. 步骤5：Alice将再次将她的秘密颜色添加到Bob发送给她的混合物中。鲍勃将遵循相同的步骤。

最后Alice和Bob将获得一个共同的秘密颜色。现在，Alice和Bob可以安全地交换我们在前一章中讨论的对称密钥，因为他们可以使用上述秘密颜色加密和解密任何消息（通过通信信道发送）。

数学来了，当我们没有足够的颜色时，总是关于数学。

步骤1：Alice和Bob达成了两个大数的协议：一个素数p（推荐至少512位）和一个基数g（p的原始根模量）。

步骤 2:Alice选择一个秘密的整数 a  。 Bob 选择一个秘密整数 b。

步骤3：Alice计算公共值x = g ^ a mod p。 Bob计算公共值y = g ^ b mod p，其中mod是模运算符。

步骤4：Alice和Bob交换x和y。

步骤5：Alice计算她的秘密密钥k_a = y ^ a mod p。Bob计算他的秘密密钥k_b = x ^ b mod p。在数学上可以证明k_a = k_b。 Alice和Bob现在有一个共同的密钥，用于加密和解密他们想要安全交换的明文

例子:

如果中间人知道秘密整数a = 6和b = 15，他可以找到用于通信的秘密密钥。方法如下：

优点：安全。避免中间人攻击。

缺点：您无法确定真正的'Bob'的实际身份。(无法确定’Bob’的真实身份)

也可以使用XOR（异或）运算符来解释Diffie-Hellman:

假设Alice想要将消息 ’M = Hello‘ 发送给Bob。消息M的二进制表示是B（M）= 0100100001100101011011000110110001101111。Alice用秘钥K = 1010101000101110100101010001110010101010加密消息。

加密消息L的明文的等效消息是âKùpÅ 。Bob收到âKùpÅ，并使用已经与Alice交换的相同的密钥K来解密消息。

公钥加密

安全密钥分发由公钥密码系统解决，因为它不需要您和室友之间进行安全的初始密钥协商。

公钥密码系统也称为非对称密钥加密 - 与对称密钥相反 - 使用一对密钥（两个独立的密钥）：用于加密的公钥和用于解密的私钥（也称为秘钥）。由公钥无法推导出私钥。

我们可以将非对称密钥密码系统与电子邮件帐户进行类比。任何人可以访问您的电子邮件地址（例如，任何人都可以通过[email protected]向您发送电子邮件），但您是唯一拥有登录密码的人（这意味着只有您可以阅读电子邮件的内容）。公钥是您的电子邮件地址，私钥是与您的电子邮件地址登录的密码。

它是如何运作的：

第1步：创建一对私钥 - 公钥（稍后我们将讨论生成密钥对）。

第2步：与朋友分享您的公钥。

第3步：发件人使用您的公钥加密明文（原始邮件+加密=密文）。

第4步：发件人向您发送密文。

第5步：使用您的私钥解密密文（密文+解密=原始消息）。

优点：增加了便利性和安全性。

 缺点：加密速度慢。所有公钥 - 私钥都容易受到暴力攻击（这可以通过选择加大密钥大小来避免）。您无法验证合作伙伴的身份（易受冒充）。

用法：由于增长密钥大小会产生过大的加密消息输出，因此加密和传输消息需要更长的时间。出于实践目的，公共密钥优先用于短消息加密，例如发送私钥或数字证书，而不是加密长消息。不方便的是，较短的密钥长度提供较低的安全性，但是在加密消息长度或传输时间方面，您是赢家。因此，密钥应经常更换。

RSA

RSA是以Rivest，Shamir和Adleman3人的首字母命名，是使用前一段中描述的Diffie-Hellman(密钥交换算法)方法，是公钥密码系统的下一步。该算法基于大整数难以分解的事实。

我会在我假设你喜欢数学之前逐步解释RSA算法:)

首先你应该知道mod（模运算）和互质整数。

欧拉定理(Euler’s theorem)：

其中phi（z）是欧拉函数( Euler's totient function)，z是正整数。

简而言之，欧拉函数将与z互质的个数记为phi（z）。如果z是素数，那么phi（z）= z-1（*）。

例子:

让我们继续欧拉定理:

使用数学归纳法我们可以证明：

这意味着数字x的指数幂为phi（z）+1时，结果是返回自身。

从（*）方程和欧拉定理，我们得到

到目前为止，我们对RSA一无所知。现在是时候把所有这些方程联系起来了。

我们假设两个素数p，q。用p * q替换z。

从等式（**）与K = 1和等式（***）我们得到：

这意味着只有当我们可以分解p * q数时，我们才能找到（p-1）*（q-1）+1。将x视为消息。我们可以选择一个随机素数E（加密密钥），它必须是（p-1）*（q-1）的互质。然后我们计算D（解密密钥）为：

其中D是mod的逆。

现在我们可以使用RSA算法，因为我们有公钥（E）和私钥（D）：

如果结果密文^ E <p * q，则存在针对RSA基于指数E和密文的短的弱点攻击。建议使用更长的密钥加密。

为什么这个算法很重要？因为像SSL，TLS，SSH，IPSec ,  PKI的协议，都使用Diffie-Hellman。

（未完待续）

（来源：格密链）