浅谈密码存储简史

· · 算法·理论

序言

在生活中，密码几乎无处不在。小到你的洛谷账号，大到你家里的银行卡，都离不开密码的保护。而信息技术发展初期，密码还只是小巧玲珑的几位数字或是图案。如今的密码却复杂得无法想象。

很多人觉得，这样增加了记忆的难度。但在信息科技工作者的眼中，如何保护好你的密码，也是一门不小的学问。在这篇文章中，你将看到密码存储的简史，看见人们同邪恶黑客斗争的足迹，体会信息科技的迅猛发展。

1. 明文存储

设想一下，如果你开了一个网站，有很多人前来注册。那么，你就需要把他们的密码存储到数据库里。

如果一个用户的密码是 \texttt{kasumi714}，那么你可以直接将 \texttt{kasumi714} 存储到数据库中。等到他再次登录时，网站将直接比对。只要他输入的密码还是 \texttt{kasumi714}，就登录成功了。

像这样，将密码原封不动直接存入数据库的方式，叫做明文存储。

很显然，这种存储方式存在很大的安全隐患。网站的工作人员，以及某些邪恶黑客等不法分子，将直接知道这个账号的密码，从而利用其实施不法行径。

设想一个情境：

假如你的各种账号，包括 Youtube、INS、CSDN 等，密码全都是 \texttt{kasumi714}。如果 CSDN 发生了密码泄露事件，且这个网站用的正好是明文，那么你的密码就被泄露出去了。

但这还不够。某些不法分子还会用这个密码尝试登录其他平台，企图窃取你的所有信息。这样试图登陆其他平台窃取信息的攻击方式叫撞库攻击。也就是说，你的所有小秘密将一览无余。更可怕的是，不法分子还可以尝试登录你的银行账号，并将你的钱财洗劫一空。

总之，不论是明文存储，还是一套密码走天下，安全隐患都很巨大，势必将遭到 OIer 们的一致抵制。抵制明文存储，从你我做起。

2. 对称性加密

既然明文存储不可行，那么我们就要想办法给密码加密。早期一些网站加密的方式是对称性加密。为了引入这个主题，我们先从凯撒说起。

这位凯撒大帝将文件内容中的每一个字母向前（或向后）移动固定位数。如 \texttt{Caesar} 这个单词，如果每个字母向后移一位，那就变成了 \texttt{Dbftbs}。这就有了加密的效果。这个 1 也就成了这个密码的密钥。

也就是说，只要知道这个密钥，我们就能反推出原来的密码。同理，我们如果有一个密码字符串 S，就可以将密码中的每一个字符向后移动 n 个 ASCII 码位。这个 n 就是加密的密钥。可以用简单的代码这样实现：

// 以下 s 为密码字符串，n 为密钥
string caesar(string s, int n) { // 加密函数
    string res;
    for (int i = 0; i < s.length(); i++)
        res += s[i] + n; // 前移/后移 n 个 ASCII 码位
    return res;
}

string decode(string s, int n) { // 解密函数
    string res;
    for (int i = 0; i < s.length(); i++)
        res += s[i] - n; // 通过密钥反推原来密码
    return res;
}

/*
在上面的代码中，caeser(kasumi714, 1) 将返回 lbtvnj825，
而 decode(lbtvnj825, 1) 将解密回原来的 kasumi714。
*/

如果这个用户输入了密码，那么网站将把存储在里面的密文，通过密钥反推出明文，再与用户输入的内容比较。

像这样，通过一个密钥，将密码加密，而又用这个密钥将密文解密回明文的加密方式，叫做对称性加密。

通过这种方式衍生出的加密算法，有 DES、3DES（三重 DES）、AES 等。

但是，这样的加密方式仍然存在着缺陷。

加密、解密的过程中，密钥的维护可谓是重中之重。如果密钥被泄露出去，那这样就同明文存储没什么区别了。因此密钥通常由网站请求取得，且密钥也会被同步加密。

而且，你不可能让所有人公用一个密钥。这同样会造成惨重的密码泄露事件。于是你决定，每人生成一个随机密钥。但这样又大大增加了维护许多不同密钥的成本。

人类，是时候需要更好的加密方式了。

3. 非对称性加密

对称性加密的密钥，在加密解密过程中是恒定不变的，如果加密过程与解密过程的密钥不一样，那么这样的加密算法就是非对称加密。

其中，加密过程使用的密钥是公钥，任何人都能用公钥将密码加密。而解密过程使用的密钥是私钥。只有使用私钥才能将密码解密。

举一个例子：

假定你要加密一段文字，先随机找出两个素数 p,q，再计算公共模数 n = pq。接着约定函数 φ(n) = (p-1)(q-1)。选取一个满足条件的整数 e，使得 e\in(1,φ(n)) 且与 φ(n) 互素，作为公钥。再计算一个整数 d，使得 ed \equiv φ(n) \pmod{1}，作为私钥。

假定 p=11, q=17，则 n=pq=11 \times 17 = 187，φ(n)=(p-1)(q-1)=(11-1)(17-1) = 160。你选取 e = 59 作为公钥，发放给用户，然后再选取 d = 179 作为自己的私钥。

这个用户将 \texttt{kasumi714} 作为账号密码。现在对其进行非对称加密：

第一步：设密码 S 中第 i 个字符的 ASCII 码位号为 s_i，对于每一个整数 i \in (1,|S|)，计算 s_i^e \text{ mod } n 的值，存入数组中，实现加密；

第二步：设密文数组中第 i 个数为 a_i，对于每一个整数 i \in (1,|S|)，计算 a_i^d \text{ mod } n 的值，再转化为 ASCII 码对应码位的字符，完成解密。

需要注意的是，这一特性只有在 n>127 时成立。

以该密码为例，进行第一步之后，密码串变为：

\{62,159,174,162,65,24,132,9,18\}

这时再进行解密，就能变回原来的密码。

可以用代码这样实现：

ull ksm(ull a, ull b, ull m) { // 使用快速幂函数 
    a %= m;
    ull res = 1;
    while (b > 0) {
        if (b&1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res; 
}

vector <ull> en; // 密文库
vector <ull> de; // 解密后的明文库
const ull pub = 59, prv = 179, mod = 187;
// 这里公钥 = 59，私钥 = 179，公共模数 = 187
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++)
        en.push_back(ksm((ull)s[i], pub, mod)); // encrypt 加密
    for (int i = 0; i < en.size(); i++)
        de.push_back(ksm(en[i], prv, mod)); // decrypt 解密
    for (int i = 0; i < de.size(); i++)
        cout << (char)de[i] << ",";
    return 0;
}

由此衍生出的算法有 RSA、ECC 等。在数字签名等领域也有着广泛应用。但是，RSA 在实际应用时，p,q 往往非常大。一方面拖慢了运算效率，另一方面也增加了破解成本。

然而，非对称性加密也存在着致命弱点。

首先，非对称性加密仍然要加强对私钥的维护。其一，私钥不能由公钥推导出来。也就是说，私钥与公钥之间没有关联性。其二，如果私钥被泄露，那么密码泄露惨案仍会发生。

随着超级计算机技术的发展以及算力的不断提升，一些大数得以被分解素因数。如果私钥被超级计算机破解，那么，这将对 RSA 等算法造成毁灭性的打击。

有没有一种算法，能彻底抛弃密钥的束缚呢？

4. 哈希算法加密

4.1 引入哈希

上文提到的加密算法经历了加密和解密两个过程。但是，解密似乎是多余的存在。如果一个密码字符串经过许多次处理，变成了谁都不认识的神秘字符串，且这种字符串是基本唯一的。那就不需要再解密了。

于是，哈希算法加密诞生了。它通过巧妙的算法，将明文变为一串神秘的字符。并且这样的加密过程单向不可逆。你几乎不能再从这串神秘字符反推回原来的明文。

对此，我们首先要复习一下字符串哈希。

下面的情景出自洛谷 P3370 【模板】字符串哈希。

假设你有一个字符串集合 \{S_n\}，你需要找出这个集合里面有多少不同的字符串。

为了简便实现字符串查重，我们需要把字符串变成数字。常用的哈希方式是进制哈希，它通过一个进制数 b（通常为 131），计算下面这个式子的值：

H(x) = \sum_{i=1}^{|S|}S[i]\cdot b^{|S|-i} \mod {m}

这里的模数 m 一般为 2^{64}，由此计算出的这个值被称为哈希值。

通过哈希值，我们就能类比去重数字的方法间接去重字符串。它可以通过代码这样实现：

const ull b = 13331; // 这里模数比较大，防止哈希冲突
ull f(string s) { // 计算哈希值
    ull sum = 0;
    for (int i = 0; i < s.size(); i++)
        sum = sum * b + s[i]; // 这里不模 2^64 的原因是此处 ull 会自然溢出，达到取模的效果
    return sum; 
}

ull a[10001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, cnt=1; cin >> n;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        a[i] = f(s); // 此处计算哈希函数，将字符串变为数字
    }
    sort(a+1,a+n+1); // 排序，之后如果某一数字与它前面的一个不相等，则cnt加1
    for (int i = 1; i <= n-1; i++) {
        if (a[i] != a[i+1])
            cnt++;      
    }
    cout << cnt; 
    return 0;
}

这便是哈希算法的简单应用。

由此衍生出的哈希加密算法，有 MD5、SHA-256、Bcrypt 等。

但两个不同字符串的哈希值可能相同，这就发生了哈希冲突。哈希冲突无法避免，但可以防御。防御哈希冲突的方法有很多种。这里不再赘述。

密码哈希为了防御冲突，进制数 b 和返回值等往往会设置得非常大。如果你用 SHA-256 算法对 \texttt{kasumi714} 加密，返回的结果是这样的：

0x63e24625127e67c69f2d78224533fbc852df213f6f139d6d9cb0007c7a2ff6ee

这时就可以把这个值存进数据库中。当用户输入密码时，将用户输入的密码哈希加密，再用数据库中的哈希值比较即可。

而且这样复杂的字符串连黑客都看不懂，即使知道算法是什么，也没有能力反推出原始密码了。这便是哈希加密算法的抗原像性。同时，当你给出一个字符串，以及它经过算法处理后得到的哈希值，你很难推出另一种输入，使得这种输入得到的哈希值与给定字符串相同。这是哈希加密算法的抗次原像性。

另一方面，由于哈希加密算法具有很强的抗碰撞性，使得你很难找出一对哈希值一样的字符串。

但是，黑客们偷密码的方式多种多样，既然你用哈希算法加密，我就用你的哈希算法打一个大表，用这个表去猜密码。这样攻击的方式叫做彩虹表攻击。彩虹表中设置的密码。首先就是简单的 \texttt{password}、\texttt{qwerty}、\texttt{123456} 等等。使用这些密码的人群将最先受害。因此，不要把密码设置得太过于简单。

同时，一些哈希算法有被破解的风险。当黑客在 \mathcal{O}(2^n) 复杂度下不断尝试，总能找到这个哈希值的原像或是次原像。而基于生日悖论（在不少于 23 个人中至少有两人生日相同的概率大于 50\%）时，复杂度将进化为 \mathcal{O}(\sqrt{2^n})。哈希加密算法的抗原像性遭到威胁，因此还需要被进一步加强。

4.2 哈希算法的强化

为了强化哈希算法，我们通常在原密码后面加一些“盐”。这个“盐”指的是随机字符串。如果把 \texttt{kasumi714} 加上名叫 \texttt{andarisa} 的“盐”，再用 SHA-256 加密，就变成了：

0x572fffb7ad5904ca7a780d56d15f1235d1514dcbb0ff41e1e81e1990b9c85205

这时，我们再把这个值和加进去的“盐”一同存进数据库中。当用户输入密码时，将“盐”加在用户输入的密码后面，再重复 4.1 中的操作即可。

同时，也可以在哈希函数中加一个成本参数 cost，延长哈希加密的时间。对我们的影响是：原先等待 1 \mu\text{s}，现在等待 1 \text{ms}。而对黑客来说，时间开销将增加成百上千倍。

5. 密码安全与防范

密码安全仍然是人类面对的重要课题之一。一方面，人类正在不断加强加密算法；另一方面，黑客也在为偷取密码不择手段。黑客除了偷密码，还有更多手段。比如：

所以，为了保障你的密码足够安全，请谨记：

作为客户端，

作为服务端，

如果你担心你的密码遭到了泄露，你可以前往 Have I been pwned? 网站，输入你的电子邮箱进行验证。同时，该网站的“Who's been pwned”板块中，收录了许多密码泄露事件，并作了简要介绍。

例如：

结语

密码学是一个古老的技术科学，在古代就被应用起来。而今，随着计算机技术的发展，密码学在计算机领域中的地位不断提高，在生活中的应用也更加广泛。

当你看完密码存储发展的历程之后，你将会想到，曾经有许多信息学工作者继往开来，为你日常生活中密码的安全性增添一份保障。同时，你也要知晓，保护好密码也是我们的共同责任。

未来，密码学将继续努力，用他自己的方式同黑客作斗争，为计算机事业的发展保驾护航。