你好,密码学(4):密码系统、OTP密码和密码的安全性

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

喵。

密码系统

引言

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

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

求破解?

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

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

为什么这么说?

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

没想到吧

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

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

这就要引入密码系统了。

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

定义

通常来说,我们所指的密码系统,由一个三元组$\mathscr{(K,\: M,\: C)}$(贴心地告诉你:这三个看不清的花体是$(K, \: M, \:C)$)构成:

  • $\mathscr K$:Key,所有可能密钥组成的集合。
  • $\mathscr M$:Message,所有可能明文组成的集合。
  • $\mathscr C$:Ciphertext,所有可能密文组成的集合。

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

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

  • $E$:Encrypt algorithrm,加密算法。用于建立$\mathscr{M \times K \longrightarrow C}$(即明文 + 密钥 到 密文) 的对应关系。
  • $D$:Decrypt algorithrm,解密算法。用于建立$\mathscr{D \times K \longrightarrow M}$(即密文 + 密钥 到 明文) 的对应关系。

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

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

想不到吧

一致性原则

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

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

用符号来表示,就是:
$$
\forall\:m \in \mathscr M,\;k \in \mathscr K \
D(k,\: E(k,\: m))=m
$$
这就得到了密码学中非常重要的一致性方程(等式)

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

特性

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

  • 算法$E$通常是一个随机化算法:对于一个给定的输入,算法$E$通常会依据自行生成的随机数进行加密操作。
  • 算法$D$一定是一个确定化算法:对于一个给定的输入,算法$D$一定会给出相同的明文。

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

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

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

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

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

定义

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

  • $\mathscr K = {0, \: 1}^n$
  • $\mathscr M = {0, \: 1}^n$
  • $\mathscr C = {0, \: 1}^n = \mathscr M$

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

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

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

  • $E(k, \: m)=k\oplus m:=c$
  • $D(k, \: c)=k\oplus c$

为了使这个密♂码成为密♂码而不是“密码”,我们需要证明它满足一致性方程:
$$
\begin{align}
D(K, \: E(k, \: m))&=D(k, \: k \oplus m)\
&= k\oplus(k\oplus m) \
&= (k\oplus k)\oplus m \
&=0\oplus m \
&=m
\end{align}
$$
(上述表达式中的$\oplus$表示异或运算,关于异或运算的详细解释请见你好,密码学(3):离散概率(速成课)(续)

好处

  • 使用OTP密♂码,我们能极快极快地加密或解密,即使消息的长度非常长。因为做异或运算对于计算机来说是非常简单且快速的事情。
  • 我们能获得超乎想像的、完美的安全性。(关于 密码的安全性 的定义及 OTP密码安全性极高 的证明将在下文给出)

但是… …

OTP密♂码是不可能实现哒!

OTP密♂码是不可能实现哒!

OTP密♂码是不可能实现哒!

惊不惊喜意不意外

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

为什么呢?

因为

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

。。。。。。

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

这也就是OTP被窝称为很难实现的密♂码而不是不是密码的“密码”的原因了。

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

81311012714191810278

密码的安全性

定义和阐释

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

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

Claude Shannon,引自 zh.wikipedia.org/zh-hans/克劳德·香农

“1948年,香农发表了划时代的论文——通信的数学原理,奠定了现代信息论的基础。”(引自维基百科

在这篇论文中,香农讨论了密码的安全性并分析了OTP密码。

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

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

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

下面给出该定义的符号描述:
$$
\forall m_1 ,\: m_2 \in \mathscr M \;\; (\:len(m_1)=len(m_2)\:)\qquad \mathtt{and} \quad \forall c \in \mathscr K\\
Pr[\:E(k, \: m_1)=c\:]\;=\;Pr[\:E(k, \: m_2)=c\:]\\
(k \overset{R} \longleftarrow \mathscr K )
$$
(其中$k \overset{R} \longleftarrow \mathscr K$表示“$k$是在$\mathscr M$上的随机均匀变量”,详见你好,密码学(2):离散概率(速成课)

该描述表明:

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

即:
$$
\mathtt{given}\quad c \quad \mathtt{can\;\:not\:\;tell\;\:if\;\:message\;\:is}\quad m_1\:\:\mathtt{or}\:\:m_2\\
(\forall\:m_1,\;m_2)
$$
但是(没错又是但是),一个完美安全的密码并不是牢不可破的。因为完美安全的定义描述了一个完美安全的算法“免疫”任何针对密文的攻击。但攻击一个密码的方式不止针对密文攻击一种。(比如旁路攻击)

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

要证明一个密码具有完美安全性,只要证明它满足上面的等式就好了:
$$
\mathtt{for\;\:OTP: \qquad if\quad}E(k, \: m)=c\\
\begin{align}
k\oplus m &= c\
k&=m\oplus c
\end{align}
\#{k\in \mathscr K:\;\:E(k,\:m)=c}\;=\;1\qquad \forall m, \: c
$$
因此,这就证明了“OTP密码具有完美安全性”。

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

<完>

=。=
0%