任何密码都可以用穷举推算出来,只是时间问题。如果是这样的话,那不是很不安全吗?

任何密码都可以用穷举推算出来,只是时间问题。如果是这样的话,那不是很不安全吗?

知乎用户,杂七杂八都懂一些的菜鸡程序员

一个月以前被邀请回答这个问题,觉得太简单就没答,评论了一句“这可能是知乎密码学话题下最萌的问题吧”。

然而今天我再次刷到了这个问题,下边的答案却没有一个让我满意的,大多数答案的概念都是混淆的。所以还是决定简单说说。

首先要搞清楚概念:什么是密码方案?什么是密码标准?

一个完整的密码方案由三个算法组成:密钥生成算法、加密算法和解密算法。其中密钥生成算法是一个随机算法,输入一个安全参数,它会给出合法的加密密钥和对应的解密密钥;加密算法的输入是待加密的明文和加密密钥,输出是加密后的密文;解密算法的输入是密文和解密密钥,输出是明文。

一个成熟的密码方案,以上所说的所有算法都是公开的,其安全性全部来自于密钥。那么这个安全性如何体现呢?这里要简单地提两个概念:图灵机及其时间复杂度。

图灵机是一种计算机器:给定输入,它会按照内置的规则进行计算,最后停机并给出一个输出(这里不纠结纸带等概念)。比如说我可以设计一个图灵机,它可以计算输入的二倍。那么我就打印输入,并在最后加一个 0 (二进制数乘 2 就在末位添一个 0)。

而时间复杂度是说,对于一个特定的图灵机,输入长度为 n 时,停机所需的基本运算的次数

。这里的基本运算涉及对纸带的操作,大家理解为对二进制的一位进行一次操作即可。

说清楚了这两个概念,我们现在就可以谈安全性的定义了。在定义中我们引入了“敌手”这个概念。一个敌手可以理解为一个图灵机,它拥有我们的密文,可能还拥有一些其他的信息或能力。不过一般情况下,我们只允许它拥有多项式时间的能力,也就是说这台“图灵机”的时间复杂度

必须总小于某一个多项式。我们把这种敌手称为 P.P.T. (概率多项式时间)的敌手。

此外,我们还需要定义“可忽略函数”。一个可忽略函数是一个正值函数,它下降的速度比任何多项式的倒数都快。也就是说,一个函数

是一个可忽略函数,当且仅当对任意的多项式

,

.

这样,我们就可以定义一个密码方案的安全性了:

一个密码方案是安全的,当且仅当对任意的 P.P.T 敌手,攻破方案的概率是一个可忽略函数。

当然,这个定义是很不严谨的,因为“攻破”这个词没有被很好地定义。在实际的研究中,我们会考虑不同的敌手能力和不同的“攻破程度”。但最基本的考虑仍是:P.P.T. 的敌手能不能以大于可忽略函数的概率搞定。

比如说最著名的公钥加密方案 RSA ,如果只能穷举

较小的素因子

,那么平均需要枚举的数量级是

。而输入

的话,长度是

级别的。也就是说,敌手枚举的次数至多是

的多项式级别的。而对于任何一个

的多项式,它在

时与

的比值的极限都是

,因此破解的概率就是一个可忽略的函数,这样 RSA 加密方案就是安全的。

如果以后有一天,我们可以确定私钥的每一个比特,那么破解 RSA 的时间就是输入长度的线性函数,那么运行线性时间就可以确定私钥,自然破解的概率就不是可忽略的。如果那样,RSA 就不再安全了。

而密码标准则是根据最新的计算机计算能力和密码方案的研究制定的实际应用密码学方案的实现准则。比如说三四十年前,512 比特的 RSA 方案就能抵抗当时世界上最快的计算机(我没有查,只是举个例子),那么密码标准可能就是密钥长度为 512 比特。再过 20 年,计算机的计算能力提高了,那就变成 1024 比特。

当然了,密码标准可不仅仅是密钥长度,它包括了实现密码方案每一个细节的要求,每一个要求都是密码学专家总结出的可能的漏洞。而且密码标准也会随着最新的研究成果不断更新,以保证按照标准进行实现时方案的安全性。

回到题主的问题:我们现实生活中所用到、接触到的各种密码系统,都是对安全的密码方案,按照密码标准实现出来的(当然也有大意的程序员不按照标准做,它们通常得到了系统被攻破的后果 23333),这两者就是密码安全性的保障。如果没有意外情况(比如说你自己在家琢磨出了确定 RSA 每一位私钥的算法并且没有公开),那么按照标准设计的系统,即使使用最先进的计算机,其破解时间往往都是不可承受的。当计算机的计算能力发展时,密码标准会相应地进行修正,以保证这个不可承受性成立。

正是在这种情况下,我们才能放心地享受信息技术带给我们的种种便利。

9.1 补充:评论区注意到了两个值得一提的问题。

@以琛 提到,密码的安全性是相对的,只要破解代价远远超过密文价值即可。

事实上不是这样的。我举个例子:山东三男子投 18 万造假币 仅造出 16 万枚 1 元假硬币

大家显然认为,这样的行为是很蠢的。但是注意到新闻中有这么一句话:

中央财经大学中国银行业研究中心主任郭田勇教授分析认为,山东制贩假币的犯罪团伙投入 18 万元只造出 16 万元假硬币的主要原因,在于购买模具设备和材料的成本较高。

购买模具和材料的成本高,因此只造出 16 万。但是模具已经买了,所以再继续造的话,每造一枚硬币的成本肯定低于一元了。如果他们持续制造,最后同样会获取暴利。

密码安全和这个问题有类似之处:破解一台价值一元的计算机的漏洞可能需要花费一千元,但破解之后编写程序,放那跑一天,说不定就攻破了三千台有这个漏洞的计算机。可能你的信息不值钱,不会有人专门盯着你去破解,但是有可能有人随手写的爬虫包含了你的网页,你又恰好有这个漏洞,你的信息一样是被非法获取了的。

@池塘里的鱼 提到,我们可以在输入密码的时候采取输错三次就冻结这样的手段,防止暴力破解。

事实上,这种情形已经不是所谓的“密码学”所研究的了。这不是一种加密机制,而是一种在线验证机制。我们所说的密码学,说的是我将一个信息用一个密钥进行处理,得到的密文可以被拥有解密密钥的人轻易地解密,得到消息;而对没有这个密钥的敌手,则很难解密。也就是说,敌手能够获取到密文并对其进行离线处理,比如暴力破解等等。而我答案里所说的一切,都是在这个模型下讨论的。