F's Blog

博客 收藏夹
密码技术

18 Jun 2015

此文主要是读《图解密码技术》的笔记,另加入自己的实践。

平时我们使用的登录密码其实是 pin 或 password,而这里的密码是 cryptography,即安全传送消息的方法,通常包括密码算法和密钥等部分。

密码学家的六个重要工具:

密码与信息安全常识

对称密码(共享密钥密码) —— 用相同的密钥进行加密和解密

异或(XOR)

听着名字很玄乎,其实算法就是相加。

而且符合加法的交互律和结合律。

在图形上理解就是反转了。硬币最开始都是正面0,反转一次是1,再反正就是0了又。

亦或的这种负负得正的性质很适合加解密。

一次性密码本加密

原理是将明文与一串随机的比特序列进行XOR运算。因为在暴力过程中,不仅会有明文出来,还会有其它类似明文的信息出来,从而无法判断哪一个才是正确的。

如加密的明文是“one”,暴力破解的结果中一定会有“one”出来,可是也会有“two”,“onl”等等。

DES

Data Encryption Standard,已经可以在有限时间内被暴力破解了,新的3DES也只能延长寿命。

其使用Feistel轮进行加密和解密。

AES

Advanced Encryption Standard,取代DES的标准。

使用Rijndeal轮。

分组密码的模式 —— 分组密码是如何迭代的

分组密码是每次只能处理特定长度的一块数据的一类密码算法。如DES分组长度是64 bit,AES可以是128 bit,192 bit或256 bit。而流密码对数据流进行连续处理,如一次密码本。

对分组密码算法迭代的方法就是模式。主要有:

模式的名字即生成密文的方式,或生成密钥,如CBC。或使用相同的密钥,如ECB、CFB、OFB和CTR,生成了一次密码本里的密钥,在做XOR。然后对每块再进行DES或AES加密或解密。

这些模式是对一次性密码本加密的实用化。

公钥密码 —— 用公钥加密,用私钥解密

终于到了神奇的非对称加密!

公钥密码(public-key cryptography)中,密钥分为加密密钥和解密密钥。它们不能单独生成。

mod——模运算

和12的最大公约数为1的数(5、7、11),在数学上成为“和12互质的数”。

RSA

在RSA中,明文、密钥和密文都是数字。

加密

密文 = 明文^E^ mod N

求E次方的mod N。

E和N的组合就是公钥。

解密

明文 = 密文^D^ mod N

球D次方的mod N。

D和N的组合就是私钥。

生成密钥对

即求E、D和N过程。

首先明白质数:质数(prime number)又称素数,是一个大于1的自然数,除了1和它本身外,不能被其他自然数整除。

用伪随机数生成器求p和q,p和q都是质数。N = p * q

L = lcm(p-1, q-1) # L是p-1和q-1的最小公倍数。

1 < E < L

gcd(E,L) = 1 # E和L的最大公约数为1(E和L互质)

1 < D < L

E * D mod L = 1

按照以上过程,我们举个例子:

  1. p=5,q=11: N=p*q = 55
  2. L=lcm(p-1,q-1)=lcm(4,10) = 20
  3. gcd(E,20) => E = 7
  4. 7*D mod 20 = 1 => D = 3

所以这对密钥为E=7,D=3,N=55.

测试一下,明文为4,那么:

加密:rsa(4) = 4^7^ mod 55 = 16384 mod 55 = 49

解密:dersa(49) = 49^3^ mod 55 = 4

正确!

隐隐之中感觉到之所以能这么着,和mod的循环脱不了干系,看看那不停在转的时钟吧,“嘀嗒嘀嗒嘀嘀嗒,时钟它不不停在转动;嘀嗒嘀嗒嘀嘀嗒,小雨它拍打着水花…”

吐曹一下:小学一年级学的最小公倍数和最大公约数现在才用到!!!

混合密码系统 —— 用对称密码提高速度,用公钥密码保护会话密钥

用RSA配送对称密码的密钥,明文用对称密码加密。

会话密钥是对称密码的密钥,同时也是公钥密码的明文。

在这个系统中,接收者先将自己的公钥发给发送者,发送者按照上面过程加密,生成包含用公钥密码加密的会话密钥和用对称密码加密的消息的密文,发给接受者。

接受者收到密文后,将密文分离出加密的会话密钥和加密的消息,首先用私钥解密出会话密钥,然后用会话密钥解密加密的消息从而得到消息。

其中会话密钥是用伪随机数生成的,频率可以每次会话都换。

著名密码软件PGP、SSL/TLS都使用了混合密码系统。

单向散列函数 —— 消息的“指纹”

单向散列函数(one-way hash function)有一个输入和一个输出,其中输入成为消息,输出称为散列值。

散列值的长度和消息的长度无关。无论消息是1 bit,还是100MB,甚至100GB,单向散列函数都会计算出固定长度的散列值。以SHA-1单向散列函数为例,它所计算的散列值的长度永远是160 bit(20字节)。

两个不同的消息产生同一个散列值的情况称为碰撞(collision)。

难以发现碰撞的性质称为抗碰撞性(collision resistance)。

MD4、MD5、SHA-1、SHA-256、SHA-384、SHA-512,这些都是常用的散列函数,其中MD4、MD5和SHA-1已早被攻破。

生成SHA-1的基本流程:

(1) 填充

对消息进行填充处理,使其长度为512 bit的整数倍。这里的512 bit为一个输入分组。

(2) 计算W,,0,, ~ W,,79,,

根据输入分组的512 bit计算出80个32 bit的值。

(3) 分组处理

对输入分组依次进行80个步骤的处理,计算出5个32 bit的值(A~E)作为SHA-1的内部状态。

(4) 单步处理

根据上面生成的所有(A~E)生成最终的160 bit散列值。

消息认证码 —— 消息被正确传送了吗

消息认证码(Message Authentication Code)是一种确认消息完整性并认证的技术。而常用的 HMAC 是 Keyed-hash Message Authentication Code 的缩写。

MAC 的输入包括任意长度的消息和一个发送者与接受者直接共享的密钥,它可以输出固定长度的数据,这个数据称为 MAC 值。

注意这里的共享秘钥,只有一个,而不是像 RSA 那样成对出现的。所以就导致了并不能通过 MAC 来验证消息的不可抵赖性,因为别人也有你的密码。

消息认证码是一种与密钥相关联的单向散列函数。密钥的配送可以使用公钥密码。

消息的完整性通过对消息生成 MAC 实现,消息的认证通过共享密钥实现,只有这两个输入都正确,才可以输出正确的 MAC 值。

消息认证码(MAC)是对消息摘要的补充,消息摘要只能保证消息的完整性,MAC 不仅能够保证完整性,还能够保证真实性。比如客户端 A 想给服务端 B 发送一条消息,A 需要把消息内容和对应的消息摘要都发给 B;B 通过同样的摘要算法,自然可以知道消息是否被篡改。比如攻击者 C 将 A 发送的原始消息和摘要,都篡改成新的消息和摘要,那么这个消息对B来说也是完整的,只不过不是A发的。因为 MAC 含有秘钥(只有 A 和 B 知道),如果 A 将消息内容和 MAC 发给 B,虽然C是仍然可以修改消息内容和MAC,但是由于C不知道秘钥,所以无法生成与篡改后内容匹配的MAC。

下面是一段生成的验证 HMAC 的 Ruby 代码:

require 'base64'
require 'openssl'

def verify_webhook(data, hmac_header)
  digest  = OpenSSL::Digest::Digest.new('sha256')
  calculated_hmac = Base64.encode64(OpenSSL::HMAC.digest(digest, SHARED_SECRET, data)).strip
  calculated_hmac == hmac_header
end

重放攻击

正确的消息,被多次发送。如向我汇款100块,这个数据被我截获了,那么我重复1000次呢?所以要防止。

那么需要在消息里加入一个不会重复的字符串,作为生成MAC值的一部分,方案有:

前两种是双方约定的,第三方虽然可以抓包和预测新加入的验证数据,但是没有密钥,生成不了新的MAC值。

nonce 是接收者先向发送者发送的,更安全,连用户自己也不能进行重放。典型应用有网络游戏的服务端,这样被抓包也不怕了,有密钥也不怕,反正 nonce 是 server 发送的,使用一次后就过期了。

有时序号和时间戳也是通过 nonce 这个名字传的,因为它的意思就是“现时,目前”。

数字签名 —— 消息到底是谁写的

逻辑上它和公钥密码相反,数字签名里签名者用私钥签名(加密),认证者用公钥认证(解密)。而在公钥密码里,私钥是用来解密,公钥是用来加密发送的消息的。这里的公是公开,私是私有,不管它们的功能是加密还是解密。

回顾公钥密码,组成密钥对的两个密钥之间存在严密的数学关系,无法拆散。用公钥加密的密文,只能用与改公钥配对的私钥才能解密。

相比 MAC 不能保证消息的不可抵赖性,而数字签名可以保证。因为数字签名使用的是公钥密码体制,私钥只有你自己才知道;而 MAC 使用对称加密,既然一方能够验证你的 MAC,就能够伪造你的 MAC,因为发送方和接收方的秘钥是一样的。当然如果你在 MAC 中绑定一些关键信息,并通过某些手段,让一方只能生成 MAC,另一方只能验证 MAC,其实也是可以实现签名效果的。

可见数字签名包含了消息验证。

使用 RSA 时,公钥私钥对,一方加密,另一方就可以解密。

数字签名的方法:

拿对消息的散列值签名说明签名的过程:

那么如何验证签名呢?

Android 发布 apk 的签名就是对散列值签名。签了名后,就说明这个应用就是你独自的了,别人起相同的包名也不能够覆盖更新安装。

为了能够确定自己得到的公钥是否合法,我们需要使用证书。所谓证书,就是将公钥当作一条消息,由一个可信的第三方对其签名后所得到的公钥。

证书 —— 为公钥加上数字签名

公钥证书(Public-Key Certificate, PKC)就像由权威机构发的VIP卡,有你的身份信息及属于你的公钥,并由认证机构(Certification Authority,CA) 加上数字签名。CA的签名如果公章,别人看到就应相信这里的内容。

公钥证书简称证书,主要内容有:

这样当其他人接受到被认证人的证书时,首先用认证机构的公钥来核对认证机构的签名,正确的话说明证书里的内容是真的,然后就可以取出并使用被认证人的公钥了。

证书目前使用大多使用X.509规范,包括以下三部分内容:

认证机构还有一个证书作废清单(Certificate Revocation List,CRL),当用户使用证书前,首先要下载最新的CRL来确定自己所使用的证书没有作废。

在我们的电子邮件软件和Web浏览器中,已经包含了一些有名的认证机构的证书,比如CNNIC的。

密钥 —— 秘密的精华

Diffie-Hellman密钥交换

使用这种算法,通信双发仅通过交换一些可以公开的信息就能够生成出共享的秘密数字,而这一秘密数字就可以被用作对称密码的密钥。

基于口令的密码(PBE)

PBE,Password Based Encryption,根据口令生成密钥并用该密钥jinx加解密。

加密包括3个步骤:

1. 生成KEK

伪随机数生成器会生成一个被成为盐(salt)的随机数。将盐和输入的口令一起输入Hash函数,得到的散列值就是用来加密密钥的密钥(KEK)。

2. 生成会话密钥并加密

使用伪随机数生成器生成会话密钥。会话密钥是用来加密消息的密钥(CEK)。

CEK需要用1步骤中生成的KEK进行加密,并和盐一起保存在安全的地方。会话密码加密后,KEK就会被丢弃,因为它可以通过盐和口令算出来。

3. 加密消息

用上步生成的CEK加密消息。

可见,PBE加密后有3个输出:

这里盐的作用是用来防御字典攻击的。

因为使用的是对称密钥,所以解密的逻辑也很简单:

伪随机数 —— 不可预测的源泉

随机数在密码技术中扮演着是否重要的角色:

它有下面三个特点:

随机性 —— 不存在统计学偏差,是完全杂乱的数列。

不可预测性 —— 不能从过去的数列推测出下一个出现的数。

不可重现性 —— 除非将数列本身保存下来,否则不能重现相同的数列。

具备了这一性质,就是真随机数了。

但仅靠软件是无法生成具备不可重复性的随机数列的。软件只能生成伪随机数列,因为运行软件的计算机本身仅具备有限的内部状态。 而在内部状态相同的条件下,软件必然只能生成相同的数。

要生成具备不可重现性的随机数列,需要从不可重现的物理现象中获取信息,比如周围的温度和声音变化、手机的摇动、键盘的输入间隔等。

伪随机数生成器(Pseudo Random Number Generator,PRNG)

PRNG具有“内部状态”,根据外部输入的“种子”来生成伪随机数列。

生成PRNG的方法:

杂乱的方法

杂乱无章的算法实现,但再复杂也有周期短的缺陷,而且复杂到自己不能验证。

线性同余法

这是一种使用很广泛的伪随机生成器算法。然而,不能用于密码技术,因为它可以被预测。

假如生成的伪随机序列是R0,R1,R2…,过程如下:

R0 = (A*种子 + C) mod M

R1 = (A*R0 + C) mod M

R(n+1) = (A*Rn + C) mod M …

这里A、C、M都是常量,但A和C小于M。

最近一次生成的随机数的值就是内部状态,伪随机数的种子被用来对内部状态进行初始化。

单向散列函数法

计数器的初始值相当于种子,counter的值相当于内部状态。

counter = 计数器初始值
while (true) {
  伪随机数 = SHA1(counter)
  输出伪随机数
  counter++
}

密码法

key = 密码的密钥
counter = 计数器的初始值
while (true) {
  伪随机数 = 用key加密counter
  输出伪随机数
  counter++
}

ANSI X9.17

算是对密码法的改良,加入了掩码的概念。

while (true) {
  掩码 = 用key加密当前时间
  伪随机数 = 用key加密(内部状态 XOR 掩码)
  输出伪随机数
  内不状态 = 用key加密(伪随机数 XOR 掩码)
}

总结

以上生成伪随机数,除了杂乱法,其它的思想都是要画个圈。

同余法是用上次生成随机数做新的内部状态,这样简单,但可预测。

剩下的每次基于初始状态改变内部状态,加一或用流动的掩码,然后生成单向的随机数。总之不能用上次的输出作为输入。

还有,说起来很复杂的过程,用代码表示就很清晰了。

实践

上面讲了那么多理论,下面是实战环节。

PGP —— 密码技术的完美组合

PGP(Pretty Good Privary),1990年左右由Philip Zimmermann个人编写的密码软件。功能几乎包括所有现代密码的功能:

访问www.pgp.com,会转到赛门铁克,看来已被收购。但是有万能的自由软件:

Gnu版:https://gnupg.org/index.html,这里还有中文说明书

说实话,程序员真的很大方,把自己辛苦劳动拿出来免费用,甚至还开源。

在Linux下默认安装,命令为gpggpg2,全程是Gnu Privary Guard.

下面是简单的使用教程:

# 生成密钥
gpg --gen-key

# 查看密钥,里面就有刚才生成的
gpg --list-keys

# 导出公钥, 这里 UID 可以是模糊的字段,gpg 会找到你想导出的
# -a 选项来把钥匙输出可读 ASIC 编码,而不是一个二进制文件
gpg -a --export [UID] > out.pub
# 导出一个私钥
gpg --export-secret-keys keyIDNumber > exportedKeyFilename.asc

# 修改,使用 sign 命令的化可以对公钥进行签名
gpg --edit-key UID

# 产生一份取消钥匙证书,导入这个证书相应的公钥就过期不能用了
gpg --gen-revoke

# 删除公钥
gpg --delete-key UID
# 删除私钥
gpg --delete-secret-key


# 加密,就会生成一个 file.gpg 的加密后的文件。-r 选择加密的公钥
gpg -e file -r [UID]
# 解密,会提示输入私钥的密码
gpg [-d] file.gpg [-o outfile]


# 签名,输出一个签名的数据。这样做的时候,同时数据也被压缩。也就是说,最终结果是无法直接读懂的。
# -u 选择签名的私钥
gpg -s -u [UID] file
# 签名生成一个可读的签名文件,会生成一个 file.asc
gpg --clearsign file
# 将签名写进另一个文件,推荐这样做,尤其是对二进制文件签名,它将生成一个 file.sig 的签名文件
gpg -b file
# 加密且签名, --armor 会输出可读的编码
gpg [-u Sender] [-r Recipient] [--armor] --sign --encrypt [Data]
# 验证签名,当然,只有当你有讯息发出者的公钥时,这才起作用
gpg [--verify] [Data]

gpg 2.1 和 gpg 是兼容的,只是密钥存放的地方不同,所以需要重新导入:

gpg --export-secret-keys [key-id] | gpg2 --import

使用 gpg 2.1 时,用 gpg2 命令即可。一般个人使用用 gpg2,server 用 gpg。

邮件加密

使用 Thunderbird 客户端 和 它的 Enigmail 插件。后者可以很方便的生产公钥,并在发送邮件时选择是否使用。

使用加密邮件,会发送自己的公钥,目的是让对方发给我们的邮件被加密,而不是加密我们发出去的邮件。

邮件正文以及附件。收件人、发件人、邮件主题都是无法被保护的。

注意:只有PGP/MIME才可以保护邮件附件(包括文件名);内嵌PGP不可以。

文件加密

使用 VeraCrypt

认证方式:

通过上面的认证方式,生成的是 Header Key,而 Header Key 能够解密出 Master Key,它们都在加密盘的头里。而用 Master Key 能够解密出加密盘里的数据文件。

Header Key 和 Master Key 分离的一个好处就是修改密码时不需要对数据再重新加密。

虚拟加密盘

就是创建一个文件,然后对它格式化后作为加密盘,可以被挂载到系统里。

物理加密盘

直接加密一个物理分区或 U 盘。

SSl/TLS —— 为了更安全的通信

TLS(Transport Layer Security,传输层安全)算是SSL(Secure Socket Layer,安全套接层)的后续升级。 前者由Netscape设计,后者由IETF在前者3.0的基础上设计。

CA 证书

CA(Certificate Authority),即证书授权中心。

总结

密钥技术就是“压缩”技术,生成一个短小的数据来解密或验证,从而提高效率,不用保密或验证全部明文。

参考

本文由 付豪 创作,采用署名 4.0 国际(CC BY 4.0)创作共享协议进行许可,详细声明