漫谈密码

这篇文章主要介绍一些常见的编码算法, Hash算法, 对称加密算法, 非对称加密算法, 它们基础是个什么样子, 以及如何选择它们. 如果已经熟悉相关内容, 对大家的帮助应该就不大了.

常见编码算法

在传输过程中, 常常有小片断二进制编码需要在JSON/XML中传输这类需求, 这时候就需要一种 编码算法, 将二进制内容编码为可打印的字符(Printable Characters), 这就是所谓编码算法. 常见的有 Base64, Hex 等.

Base64

Base64 将二进制内容编码为64个可打印字符组成的信息, 故名. 64个字符能够使用8bit编码6bit长度的信息, 因此 Base64 编码后长度会使信息增加 \(\frac{1}{3}\)长度.

求得8与6的最小公倍数为24, 因此Base64的基本编码过程, 就是每3字节原文, 编码为4字节Base64.

Base64中包含字符 ‘/’ 和 ‘+’, 因此并不算适合放在URL中作为一部分.

使用 Bash 命令进行编解码:

encoded=`echo -n 'Hello World' | base64`
echo $encoded
echo -n $encoded | base64 -d

Base64也拥有一些变种, 可以使用不同字符集进行编码.

Hex

Hex 将二进制内容编码为16进制. 十六进制编码能够使用8bit编码 4bit 长度的信息, 因此 Hex 编码会导致长度增加一倍.

Base64 和 Hex 都不能作为加密算法, 只能算作编码算法, 因为在知道算法的情况下, 发送方与接收方不需要了解任何其他信息, 就可以获取到明文.

其它编码算法, 如针对图像和视频的编码. 这类编码的优先目的, 是减少信息冗余, 缩减信息的体积, 因此对其作压缩往往不能取得良好效果.

常见Hash算法

Hash算法, 国内也称消息摘要算法,哈希算法, 杂凑算法. 目前常见的有MD和SHA两族, 国内则有SM-3等. 除了出于安全性考虑外, 在特殊场合下也需要考虑法律法规, 选择特定的算法族.

Hash算法是一种单向函数, 即给定任意长度明文 x, 通过函数 F , 输出固定长度的摘要:

$$ F(x) \Rightarrow z$$

以MD5为例, 即使是输入1Gb长度的信息, 也只会输出 128bit 长度的摘要, 因此单独获得摘要, 并不可能逆推出原文. 因此, 哈希算法不可能作为一种加密算法, 因为它不可能有对应的解密算法.

Hash一般用做信息的"指纹", 验证信息的完整性, 以确保信息没有发生丢失. 针对它的攻击, 主要是为了信息篡改, 即找到信息 x’, 使 F(x’) = F(x). 从数学上讲, 这是可行的. 一段长达200kb的信息, 必然存在若干不同的消息片段X和X’, 存在 F(X) = F(X’). 如果我们能够了解明文X, 就有一定几率在不严重破坏X基本结构的前提下, 篡改其内容, 例如在正常软件中隐藏木马病毒.

如果存在不同的明文x和x’, 能够产生相同的摘要 (F(x)=F(x’)), 则称x’是x的一个碰撞(Collision).

Hash的另一个使用场景是比对用户密码. 用户的明文密码通常隐含了用户自身的一些密码使用习惯以及隐私,一旦数据库遭到泄露, 受害范围将不会仅仅是这一个数据库以及它的系统, 用户在其它系统的账号密码也将容易被推断出来. 因此在数据库中存储明文密码, 是极其不明智的. 在欧洲和美国的一些法律中, 会规定禁止存储用户的明文密码. 由于相同的明文能够产生相同的信息摘要, 而反之使用摘要则不能反推明文, 因此系统数据库中通常会存储用户密码明文若干轮后的摘要:

$$Hash(x)^n=digest$$

如果是许多年前, 那么只经过一轮Hash还是比较安全的. 然而随着时间的推移, 攻击者已经针对简单密码建立了各种各样的数据库, 只经过一轮Hash的摘要存在被攻击者从数据库中找到碰撞的可能.

那么我们姑且设n=3000, 这就安全了吗? 攻击者了解到这一点后, 只要针对弱密码建立字典, 那么就有几率从中找到碰撞, 从而发现一个用户的明文密码. 要知道, Hash函数都被设计的非常之快, 正向建立一个字典是非常快的. 如果我们为其增加一段固定的文本 y:

$$Hash(x+y)^n=digest$$

那么攻击者只要了解到y的值, 仍能建立字典并进行碰撞, 这并没有带来任何安全性提升. 此外, 当有两个用户正好使用了相同的密码时, 攻击者将发现, 他们的摘要值相等, 只要推断出一个, 就等于获得了另一个.

因此, 实际数据库存储密码摘要时, 为每个记录使用不同的文本, 这就是所谓的"盐(Salt)":

$$Hash(x+salt_x)=digest$$