主要介绍了第一个我们接触到的密码系统OTP密码和必须要懂的基本知识密码系统

喵。

密码系统

引言

经常在网上看到这样的问题:

密文:<~k_l(pLoKL*^#cE*kEMV$Xh3Z+V#~>

求破解?

遇到这种一串大小写混杂、各种特殊字符、以及各种奇怪字形的密文(先姑且叫做密文吧),可能是因为破解的过程实在太过有趣,很多人就会马上拿出纸笔,开始写写划划。

但是,慢着:上面这一串玩意,是密文吗?

为什么这么说?

因为它当然不是啊!(///ω///)

emoji

上面给出的密文示例,仅仅是使用Online ASCII85 encoder将一串中文字符的编码结果而已。

但是,这种加密方式仍然符合表达式:$E(m)\longleftrightarrow D(m)$啊, 为什么说它不是一种密码呢?

这就要引入密码系统了。

(注:这里所指的“密文”,是“密码系统”中的“密文”)

密码系统的定义

通常来说,我们所指的密码系统,由一个三元组 $ (\mathscr K,: \mathscr M,: \mathscr C)$构成:

我们可以用这个三元组唯一地定义一个密码的环境

而密码本身,由一对高效的算法 $(E,:D)$(没错,你们熟悉的 $E$ 和 $D$ 又来了)组成:

但是,是不是任意一个 $E$ 和 $D$ ,都能构成密码呢?

当然不是的啦!(///ω///)

img

一致性原则

对上文提到的 $E$ 和 $D$ ,必须满足一个要求(也是唯一的要求):

对于任意给定的消息(明文) $m$ 和密钥 $k$ ,该组算法要能保证将该消息加密得到密文,再将密文解密后能得到原消息 $m$ 。

用符号来表示,就是:

这就得到了密码学中非常重要的一致性方程(等式)

虽然该方程表述的东西是显而易见的,但还是要指出:一个密码只有满足一致性方程,才能保证解密的正常进行。

特性

除了一致性原则之外,算法 $E$ 和 $D$ 还有一个特性:

(关于随机化算法和确定化算法的解释请见你好,密码学(2):离散概率(速成课)

在上述解释中特别强调了通常一定,因为对于加密算法,是否随机化关系到的仅仅是密码的强度(虽然这也很重要了);而对于解密算法,是否确定化却关系到密码是否满足一致性方程,也就关系到“密码”是否是密码。

因此,本文开头提到的“密码”不是密码的原因,就在于其不存在密钥,所以也就没有密码的环境了。

第一个密码:One Time Pad(一次性密码本)

因对于”One Time Pad”这一英文对应的译法较多(“一次性密码本”,“一次一密”,“一次性便签密码”),故在以后表述此密码时,均采用其英文表达One Time Pad或其缩写OTP。

定义

使用先前对于“密码系统”的说明,我们来定义一下这个密码的环境(密码系统):

所以,三元组中的每个部分都是:所有$n$位的二进制字符串。、哈哈。

而密钥则是一个与密文等长的随机二进制字符串

然后,我们再来定义一下密码自身:

为了使这个密码成为密码而不是“密码”,我们需要证明它满足一致性方程:

(上述表达式中的$\oplus$表示异或运算,关于异或运算的详细解释请见你好,密码学(3):离散概率(速成课)(续)

好处

但是… …

OTP密码是不可能实现哒!

OTP密码是不可能实现哒!

OTP密码是不可能实现哒!

emoji

怎么样!惊不惊喜意不意外!

为什么呢?

因为

该密码要求,在发送方传输消息的第一位之前,就必须传输和明文一样长的密钥。但是,若发送方和接收方之间有一条安全的途径能够传输这一和明文一样长的密钥,那两方之间完全可以传输和密钥一样长的明文,也就不需要这个密码进行加密和解密了。

emoji

但是,即便如此,今后我们也能看到OTP密码的思想实际上是很有用的。

最后,让我以一个密码或“密码”,结束本节关于密码系统、一致性方程和OTP密码的讨论:

81311012714191810278

密码的安全性

定义和阐释

在对OTP密码的讨论中,我们提到了其安全性极强。因此这就有一个问题:用什么来衡量密码的安全性呢?

在这里,我们就必须~~祭~~请出著名的信息论之父:克劳德·香农

Claude-Elwood-Shannon

图片引自维基百科 - 克劳德·香农

“1948年,香农发表了划时代的论文——通信的数学原理,奠定了现代信息论的基础。”(引自维基百科 - 克劳德·香农) 在这篇论文中,香农讨论了密码的安全性并分析了OTP密码。

他认为,一个密码要满足以下条件,就是绝对安全的:

给定密文,但无法得到与明文有关的任何信息;也就是说,密文不透露有关明文的任何信息。

用另一种方式描述,就是对于任意一组随机选取的一个密钥$k$和两个消息$m_1, \; m_2$,使用该加密算法加密$m_1$得到密文$c$的概率和加密$m_2$得到密文$c$的概率是相同的。

下面给出该定义的符号描述:

(其中$k \overset{R} \longleftarrow K$表示“ $k$ 是在 $m$ 上的随机均匀变量”,详见你好,密码学(2):离散概率(速成课)

该描述表明:

对于一个完美安全的密码,如果攻击者截获来任意一段密文,该密文来自任意一段明文的可能性均相等。即不可能知道其来自那一段明文。

即:

但是(没错又是但是),一个完美安全的密码并不是牢不可破的。因为完美安全的定义描述了一个完美安全的算法“免疫”任何针对密文的攻击。但攻击一个密码的方式不止针对密文攻击一种。(比如旁路攻击)

“OTP密码具有完美安全性”

要证明一个密码具有完美安全性,只要证明它满足上面的等式就好了: 因此,这就证明了“OTP密码具有完美安全性”。

没有证明OTP密码绝对安全,因为还存在唯密文攻击以外的攻击方式。

<完>

完成于2017.7.27 最后修订于2018.1.25

赞 赏