1. 链一财经首页
  2. 资讯

科普 | 密码学极速入门(Part-1)

作者: Leo Whitehead

翻译 &校对: IAN LIU & 阿剑

来源:以太坊爱好者

科普 | 密码学极速入门(Part-1)-广受欢迎的加密通讯工具——OpenSSL,其中的部分代码-

关于密码学的内在原理,一直被认为是少数专家或数学家才能涉足的领域,其中的技术细节在大多数人看来就像变魔术一样。考虑到现代密码学的复杂程度,我们可以理解为什么很多人对密码学存在这些误解;但不了解密码学,可能会做出很多弊大于利的决定,比如英国的加密禁令提案(Encryption Ban),澳大利亚的援助和访问法案(Assistance and Access Bill)等。

在本篇指南中,我们会帮助大家掌握学习密码学所需的入门知识、对不同密码学体系的发展历程进行简介,并对当前三个最流行的密码学领域——流密码、分组密码、公钥密码,进行快速上手指导。

密码(Ciphers)“密码”(Cipher)指的是对消息进行加密或解密的算法,也是密码学的基石。加密算法 (E) 使用密钥 (k) 对消息 (m) 进行加密,并生成密文 (c);类似地,解密算法 (D) 使用密钥 (k) ,对密文 (c) 进行解密。如下列所示:

科普 | 密码学极速入门(Part-1)

-加密算法 ‘E’ 及解密算法 ‘D’ –

上述过程也意味着,一种算法要想被称为”密码”(算法),还必须满足以下的一致性方程特性,确保密文可以被解密。

科普 | 密码学极速入门(Part-1)

式子表明着如果你使用密钥 K 对消息进行加密,也能使用密钥 K 对密文进行解密,并得到与原来消息一摸一样的输出。

其中一种最古老、最简单的密码就是凯撒密码(Caesar Cipher)——直接从字母表中选取特定位置,替换掉原消息中的字符。

科普 | 密码学极速入门(Part-1)

-凯撒密码出现于公元 50 年,凯撒大帝使用字母表跳三位的字来替换原来的消息内容,用于军事通讯-

下面的例子就是经过后三位字符替换过后的密文形式(上面一行为原文,下面一行为密文):

科普 | 密码学极速入门(Part-1)

凯撒密码可以用下列式子表示:

科普 | 密码学极速入门(Part-1)

虽然这种做法符合我们对密码的定义,但是它非常不安全。只要攻击者知道密文是以这种方式加密,就能通过尝试另外 25 种组合进行破译;即使攻击者不知道密文使用了凯撒密码,他们也能够观察到密文中的规律进行破译。

虽然这种做法符合我们对密码的定义,但是它非常不安全。只要攻击者知道密文是以这种方式加密,就能通过尝试另外 25 种组合进行破译;即使攻击者不知道密文使用了凯撒密码,他们也能够观察到密文中的规律进行破译。

在进一步介绍更安全的加密算法之前,我们得先聊聊什么是 Xor 运算。

XOR(异或运算)

Xor运算,又称为”异或门”,是一种布尔变量逻辑判断,能接收 1 或 0 作为输入:如果输出 1 则表示两个输入不同;输出 0 则表示两个输入相同。下图的真值表列出了经过异或运算后,所有可能的输入输出组合:

科普 | 密码学极速入门(Part-1)

异或运算也经常用符号 ⊕ 来表示:

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

关于异或逻辑,以下有几点重要的特性:

异或运算结合律:a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c 对自身进行异或运算结果为 0 : a ⊕ a = 0 对 0 求异或,结果为自身:a ⊕ 0 = a 根据上述异或运算的规则,我们知道 a ⊕ b ⊕ a 等同于 a ⊕ a ⊕ b,也等于 0 ⊕ b,运算结果为 b。要注意的是,这些异或运算特性只适用在 1 和 0 ,因此对不同进制的数字进行异或运算之前,需要先将其转换为二进制。例如:

87 ⊕ 73 = 1010111b ⊕ 1001001b = 0011110b = 30

接着,我们可以开始介绍第一种安全密码了。

一次性密码Frank Miller 在1882 年提出了一次性密码(One-time pad)的概念——加密:将消息和私钥进行异或运算得到密文;解密:将密钥和密文进行异或运算得到原消息,这个过程类似于前面提到的 a ⊕ b ⊕ a = b 。一次性密码的定义如下所示:

科普 | 密码学极速入门(Part-1)

该密码的一致性方程也很容易证明:

科普 | 密码学极速入门(Part-1)

一次性密码非常容易上手,假设我们要加密一串字段”Message”,首先可以通过 ASCII 字符集将”Message”转换为二进制数据(由 1 和 0 组成)。

科普 | 密码学极速入门(Part-1)

现在,我们需要一组56位随机二进制数(私钥)来对明文进行异或运算,该私钥随机程度越高越好!

科普 | 密码学极速入门(Part-1)

-从 random.org 生成的随机数-

我们将明文和私钥的每一位进行异或运算。

科普 | 密码学极速入门(Part-1)

运算后的结果就是我们的密文了!要解开密文也很简单,我们只需要将密文和刚才生成的私钥进行异或运算,并转码回 ASCII ,就能得到原消息。

科普 | 密码学极速入门(Part-1)

这种密码简单易用,而且还有个很有意思的特点。一次性密码具有所谓的完全保密性,这意味着从数学角度来说,攻击者不可能从密文(m⊕k 的结果)推得任何原消息的内容,当然也不可能破译。

既然我们已经有了简单易用,且不可能破译的密码,为什么我们还会想用其他的密码呢?根本原因在于,一次性密码虽然很有效,但是他有一些重大的缺陷。

第一个缺陷是,不论我们想要加密什么样的消息,都需要有和原消息一样长或是更长的私钥用于加解密。而且为了让密文接收者能够解密密文,需要有绝对安全的通信方法把私钥给到接收者;这就形成一个悖论,如果有这种安全通道,那不如直接把原消息发过去得了。

第二个缺陷可以从 “一次性密码” 的名称中发现。针对不同消息,同一个私钥每回只能使用一次;如果对多个消息重复使用同一个私钥,其引发的问题可以从数学推导上看出。

假设我们有两条消息 m1 和 m2 ,分别使用相同的私钥 k 进行加密(使得我们的系统变成 “二次性密码”)。通过异或运算,我们会得到以下密文:

科普 | 密码学极速入门(Part-1)

从上图,我们可以从密文C1⊕C2得到m1⊕m2 。对于攻击者来说,他们就能基于这种关联性,通过各种统计分析、频率分析、模式匹配,或是使用 2006 年提出的自然语言处理方法,来获得原消息的内容。我不会深入解释存在这种关联性具体造成的危害(感兴趣的可以看 这里 深入了解),这里只是形象的说明当同一个私钥被使用的次数越多(”三次”、”四次”……?),密码的安全性就越低。

现在我们已经具备 XOR 加密和一次性密码的基础知识,是时候了解其他更实用的加密方法了。

流密码(Stream Ciphers)

一次性密码具有非常好的安全性,这意味着手上只有密文的情况下,攻击者不可能进行破译。但是好的安全性基于长度大于等于原消息的私钥,这使得一次性密码并不实用,因为如果加解密双方有很好的方法来传递消息和私钥,他们直接传递消息就好,没必要进行加密。

为了让一次性密码更加实用,我们引入 “流密码” 的概念。流密码的核心思想是——以”伪随机”密钥替代一次性密码中的 “随机” 密钥,伪随机密钥产生自密码学安全伪随机数生成器(CSPRNG,Cryptographically Secure Pseudo-random number generator )。要注意的是,CSPRNG 不同于一般的伪随机数生成器,因为 CSPRNG 产生的数据必须和真实随机数看起来没有区别才行。CSPRNG 是一种算法(或函数),能产生一长串数字,类似于随机数的性质。因为随机数很难生成,所以 CSPRNG 要依靠种子(seed)来决定初始状态及将来产生的数;CSPRNG 从相对较小的起始种子生成海量的随机数(例如从 128 bit 的种子生成几 GB 的随机数)。如果起始种子是已知的,则随后产生的所有数都是已知的,也就是说 CSPRNG 具有确定性;这也导致CSPRNG 产生的数,其随机程度完全取决于种子的随机程度。为了让一次性密码更加实用,我们可以根据所需长度,使用伪随机数生成器的输出替换原来的私钥;这样的话只要传递初始种子就可以了。因为 CPRNG 具有确定性,使用相同种子能得到相同输出(也就能得到相同的 key 用来加解密)。

为了更好理解,我们先看看原来的一次性密码:

科普 | 密码学极速入门(Part-1)

使用伪随机数生成器的输出 G(K),替换原来的私钥 K:

科普 | 密码学极速入门(Part-1)

(注:图例中只是其中一种流密码,称为同步流密码。还有一种方法称为 “自同步流密码”,使用密文中的前几位数计算出密钥中的每一位。)

替换后的私钥可以远远短于要加密的消息,使得分配及管理私钥更为方便,进一步改善了一次性密码不实用的问题。但这种做法也带来了新的问题:

将原来完全随机的私钥替换为安全随机数生成器的输出,会导致私钥长度比原消息短,使得我们的密码不再具有完全保密性。因此流密码的安全性取决于我们的伪随机数生成器的不可预测性。如果可以预测 CSPRNG 的输出,则可以获得明文消息。以下是大家熟知的一些使用弱流密码的密码系统:

802.11b WEP:WEP 是一种给 WiFi 数据做加密的算法,它使用的流密码称为 RC4 。因为流密码中不能一直使用同个密钥,所以长期使用的密钥包含一个每次都会变动的值 “IV”;然而 “IV”只有 24 位,也就是说加密超过 5000 条消息后,就会有五成的概率出现相同的密钥。

CSS:DVD Forum 使用内容扰乱系统(CSS, Content Scramble System)来管理 DVD 的数字版权,使得仅有获得授权的应用才能访问 DVD 内容。CSS 使用 40 位的密钥,而 40 位的密钥空间较小,可以相对快速地暴力破解。(尽管密钥是 40 位,但考虑到 CSPRNG 的技术特点,只要猜出 17 位组合后,系统便可能被完全破解。)

现在我们也掌握了流密码的知识,可以进一步讨论下一个密码系统——分组密码。

分组密码(Block Ciphers)

分组密码是另一种能用于加解密数据的方法。分组密码包含两种算法:E用于加密,D用于解密,同时也用到了密钥 K 。

科普 | 密码学极速入门(Part-1)

分组密码的核心在于,要加密的明文和输出的密文长度始终相同,为一固定量。该固定量称为 “block size”(译者注:不要与区块链语境下的 “block size” 搞混哦;后文将该词译为 “消息大小”),大小取决于所使用的分组密码算法。另外,私钥 K 的长度被称为密钥大小,也是固定量。常见的两种分组密码分别是 3DES 及 AES —— 3DES 具有 64 位的消息大小和 168 位的密钥;AES 具有 128 位的消息大小和 128 、192 或 256 位的密钥。

因为分组密码把可能的区块映射到其他的每一个区块,所以也被称为 “用密钥完成的置换”(Keyed Permutations) 或是 “伪随机置换”(Pesudorandom Permutations)。非常重要的一点是,私钥决定了输入的区块和相关密文区块的映射关系,而且是一对一排列的,所以只要知道私钥就能解密密文。

第一个比较重要的分组密码是 1970 年代 IBM 开发的数据加密标准( DES ),但 DES 并不安全,很快就被 3DES 取代;紧接着 3DES 又被 1997 年开发的高级加密标准( AES )所取代。AES 是在国家标准与技术研究所( National Institute of Standards and Technology )的要求下制定的标准化分组密码。AES 是当今使用的最常见的分组密码,重要性大大超过 DES 和 3DES ,所以我将着重介绍 AES 。

在我解释 AES 到底是怎么运作之前,先提醒一下我会跳过很多技术细节,如果有人对这深入这方面领域有兴趣,可以从这里获得你想要的。

AES 及大部分分组密码,都是通过迭代进行运作的,输入的文本消息会使用连续的密钥以迭代的方式进行加密。第一步是获得一个密钥 K,密钥一般是 128 位、192 位或 256 位的,在这里我们只演示 128 位的 AES;然后拿该密钥推导出一系列的 Round Keys 来加密我们的消息。

科普 | 密码学极速入门(Part-1)

上图例子中,我们输入 128 位(16 字节)的密钥,并通过 Rijndael 密钥方法 将密钥扩展成 11 个 16 字节的子密钥。接着,AES 将原消息放入轮次函数 R(kn , m) 进行独立加密计算,每次计算把扩展出来的轮次密钥 kn 及消息状态 m 作为输入,总共进行 10 次。

因为 AES 只能用在 128 位的消息上,因此我们把输入的消息 m 表示成 4×4 矩阵的单字节单元,同时也能把轮次密钥表示成 4×4 的矩阵,这样就可以对消息及其中间状态进行异或运算了。

科普 | 密码学极速入门(Part-1)

首先,输入的消息和第一个轮次密钥进行 XOR ,再通过字节替代(ByteSub)、行位移(ShiftRows)、列混淆(MixColumns)等运算,输出转变后的消息状态作为结果(这些步骤会在后面做解释)。接着我们使用不同的轮次密钥重复上述这些步骤 10 次,唯一的不同点在于最后一次的计算不包含列混淆( MixColumns )。最终的消息状态和第十一个轮次密钥(k10)进行异或计算,得到最后的输出。下面简述了每一轮次的计算中包含的三种步骤:

字节替代( ByteSub ):根据替换表,将消息状态矩阵中的每一个字节,替换为相应的字节。

科普 | 密码学极速入门(Part-1)

-在 AES 使用的替换表中,每一个字节单元以 16 进制表示。如,字节 9a 会替换为 b8 –

行位移( ShiftRows ):定量移动每一行。第一行不移动,第二行左移一位,第三行左移两位,第四行左移三位。

科普 | 密码学极速入门(Part-1)

列混淆( MixColumns ):对消息状态中每一列进行线性变换。目前为止,我们已经能使用 AES 来加密数据。然而,你可能很快能发现 AES 的局限性——没办法在只用一次 AES 的情况下,对超过 128 位(或 16 字节)的消息进行加密。要对超过 16 字节的消息进行加密,我们需要引入模式加密( Modes of operation )概念。

(未完)

发文时比特币价格: ¥65767.01特别声明

原文来源:https://medium.com/dataseries/a-crash-course-in-everything-cryptographic-50daa0fda482

免责声明:本文不代表巴比特立场,且不构成投资建议,请谨慎对待。

根据国家《关于防范代币发行融资风险的公告》,大家应警惕代币发行融资与交易的风险隐患。

本文来自LIANYI转载,不代表链一财经立场,转载请联系原作者。

发表评论

登录后才能评论

联系我们

微信:kkyves

邮件:kefu@lianyi.com

时间:7x24,节假日bu休息

QR code