【密码学】现代密码学

  1. 去年
    6月前Ray Eldath 重新编辑

    这是一个知乎上 发过的文章的优化显示版本。因为知乎的显示效果实在太差了...三级标题都没有...垃圾知乎死全家!

    在本系列中,我们将讨论:

    • 基础知识:离散概率速成
    • 密码系统,密码安全性的度量
    • OTP密码和攻击OTP密码
    • 伪随机数生成器
    • 流密码
    • 分组密码
    • 哈希和抗碰撞
    • 公钥密码学
    • ...

    所以,准备等吧让我们开始吧!

    最后:

    论坛终于原生支持Markdown了...
    以及超理的asnowwolf表情好棒啊啊啊啊啊 /asnowwolf-laugh

  2. 10月前Ray Eldath 重新编辑

    -image-

    什么是密码学

    导览

    课程地址请见Coursera

    密码学的核心

    -image-

    安全密钥的构造

    • 在协议结束时,两方均能获得一个只有通信双方知道的密钥$k$。
    • 通信双方均能确信自己是在和对方通信。(而不是和其它什么人通信)

    安全通信

    • 使用$k$密钥加密的信息是绝对安全且可信[/b]的。
    • 即 密钥安全 ≡ 信息安全 ,密钥可信完整 ≡ 信息可信完整

    关键:密码学应保证信息的安全性完整性

    以及:编辑器点击上方工具栏的按钮后会文本框会跳到最末,导致长文编辑的不方便。强烈建议修改。这就是这个回复为什么这么短的原因。
     /asnowwolf-upset

  3. 10月前Ray Eldath 重新编辑

    但是密码学还能做到更多

    -image-

    - 数字签名

    • 关键:基于内容的签署函数
    • 个人理解:即内容(文本)不同或密钥(特征)不同,得到的签名都不同。

    - 匿名通信

    • Mixnet:通过多重代理实现通信双方的 互相不可知单方可知
    • 即 发信人不知道收信人,收信人也不知道发信人,代理服务器不知道“发信人在和收信人通信”。
    • 或 发信人知道收信人,但 收信人不知道发信人,代理服务器不知道“发信人在和收信人通信”。

    - 匿名电子货币

    • 收款人不知道付款人(付款人匿名)
    • 阻止付款人将 一单位货币 非法拷贝多次以得到 $N$单位货币

        关键:当一单位电子货币被消费一次,则付款人匿名;
        但若一单位电子货币被消费多次(出现了非法拷贝),则付款人信息被公开。

    协议

    安全多方计算

    保证“外界只知道输出的结果,而不知道用户的输入(因为可能包含不应透露的信息)”?

    • 通常情况下,这是对$\alpha = f(x1, x2, x3, ... ,xn)$进行计算,公布$\alpha$的计算结果且保证$x1, x2, x3, ... ,xn$不被泄露。
    • “一种较呆板、不安全的方法”:找到一个“可信机构”,将输入交给可信机构,由可信机构计算并输出结果。但你需确保可信机构是可信。(因为可信机构能够掌握这些 “不应被泄露” 的输入)
    • 密码学中非常中心的理论:如果任何计算能通过将该计算交给“可信机构”计算来完成,那么该计算不依赖“可信机构”也一定能完成。
    • 可信机构一定不必须。

        关键:各个参与者之间互相建立通信,通过某种协议,使得在计算结束后,每个参与者只知道自己的信息和计算结果。

  4. 密码学的“魔法”

    私密外包计算

    搜索

    • 通信发起方将加密后的信息传送给接收方,接收方可以依据已经加密后的信息进行搜索运算并返回搜索结果,但接收方不知道信息的实际内容(只知道加密后的内容)
    • 接收方能对加密后的信息进行特定运算,但接收方不知道信息本身。

    零知识证明

    - 通信发起方能够向接收方证明“我拥有$A$”,并且接收方能够确信“发起方拥有$A$”,但是接收方不知道$A$是什么

    一门严谨的科学

    三个步骤

    1. 给出一个“威胁模型”

      - 攻击者会对数字签名的“可靠性(不可伪造)”发起攻击

    2. 证明“任何需要通过方案$A$去破解系统的攻击者都能解决难题$B$”

      - 任何攻击者要攻击数字签名的可靠性必须能够解决因子整数分解

    3. 证明难题$B$是“不可解决”的

      - 因子整数分解是普遍认为不可解的

    4. 最终证明:该威胁模型下没有一种方法能够攻破体系
      - 该体系在该威胁模型下是安全的


    本节完

  5. 10月前Ray Eldath 重新编辑

    -image-

    密码学I:离散概率(速成课)

    导览

    课程地址请见Coursera

    对于分布概率的更详细解释,请见:WikiBooks (English)

    基本定义

    $U$:一个总是有限集的全集。通常是n位二进制字符串的集合,记为$\{0,1\}^n$。

    $P$:全集上的$U$概率分布 ,为一个函数,即$P$。该函数为$U$上的元素分配一个值。

    例如:对于$\{0,1\}^n$,即U表示所有两位的二进制串集合。此时$U=\{00, 01, 10, 11\}$。而因为$U$是二进制字符串,因此$P$为$U$中的每一个元素分配一个$0$到$1$之间的数,称作该元素在全集$U$中概率(或权重)。

    我们要求:将$U$中所有元素的概率加起来,我们能得到1。即:
    $$
    \sum_{x\in U} P(x)=1
    $$

    即对于全集$U$中的每一个元素,$P$返回该元素的概率组成的集合。


    常用概率分布

    均匀分布

    先导定义:
    $|U|$:全集$U$的大小,即全集$U$中元素的个数。

    均匀分布:即为全集$U$中的每一个元素分配相同的权重。
    因为我们要求权重之和为1并且所有这些权重都相等,因此对全集中的每一个元素$X$,它的概率为$1\over |U|$。
    这意味着若从这个分布中随机抽样,将得到所有$n$位字符串上的均匀样本。即根据这个分布 所有字符串被抽中的可能性是相同的。

    在点$x_0$的点分布
    点分布:将所有权重放在单一的点$x_0$上,并对其他$U$中的元素的可能性赋$0$值。即:

    $$
    P(x_0)=1,\quad \forall x \neq x_0: \;P(x)=0
    $$

    因此,此时若从这个分布中多次抽样,将总是能够确保抽到$x_0$代表的数值而绝不会抽到任何其他的数值。

    本节最后
    由于全集$U$总是有限集,事实上我们可以把分布于$U$中每一个元素的权重写出来 从而将整个分布表示为一个向量。该向量的每个实数都在$0$到$1$之间。

  6. 事件

    基本定义
    事件:考虑全集$U$的一个子集$A$ ,因为全集$U$的所有元素概率之和为$1$,因此它的子集$A$的概率之和必然介于$0$和$1$之间。即:

    $$
    \mathbf {For\;\:a\;\:set\;}A\subseteq U:\quad Pr[A]=\sum x \in [0,1]
    $$

    此时,称全集$U$的子集$A$为一个事件,集合$A$的概率称为事件的概率

    联合界(union bound)
    联合界:假定有2个事件 $A_1$ 和 $A_2$ ,它们都是全集$U$的子集。因为$U$代表两个集合的并 ,所以 $A_1$ 或 $A_2$ 发生的概率小于这两个概率之和。即:

    $$
    Pr[A_1 \cup A_2] \; \le\; Pr[A_1]+Pr[A_2]
    $$

    原因在于,当我们计算这两个概率之和时,$A_1$ 和 $A_2$ 交集交集中元素的概率被计算了2次,所以这两个概率之和将大于或等于 $A_1$ 和 $A_2$ 并集的实际概率。
    特别地,若 $A_1 \cap A_2= \varnothing$ ,那么 $Pr[A_1 \cap A_2]$ 将等于 $Pr[A_1]+Pr[A_2]$ ,即:

    $$
    \mathbf {if} A_1 \cap A_2= \varnothing, \quad \mathbf{than} \;\;\; Pr[A_1 \cap A_2]=Pr[A_1]+Pr[A_2]
    $$

    随机变量

    随机变量:一个从全集映射到某个集合$v$的函数,记为$X$。此时我们说集合V是随机变量的值域。
    更一般地,如果有一个从某个集合$v$中取值的随机变量,那么它实际上生成了集合$v$上的一个概率分布,即:

    $$
    \mathbf { rand \;\; var.} \;\: x \;\; \mathbf { includes\;\;a\;\;distribution\;\;on} \;\;V \mathbf:\quad Pr[X=v]:=Pr[x^{-1}(v)]
    $$

    意思是说:随机变量输出$v$的概率等于我们从全集中随机抽取一个元素,对其施加函数$X$ ,然后输出$v$的可能性是多少。
    正式地,我们说$X$输出$v$的概率就等于我们从全集中随机抽取一个元素,正好落在 $v$在函数$X$之下的原像 中的概率。

    关键:随机变量在特定集合$v$中取值,就生成了$v$上的一个概率分布。

    均匀随机变量

    均匀随机变量:假定$U$是某个有限集合,对于全集$U$中的所有元素$a$,随机抽取一个元素$r$等于$a$的概率是 $1\over|U|$ ,即:

    $$
    r \overset{R} \longleftarrow \mathbf{\;\;means\;\;devote\;\;uniform\;random\;variable\;\;on}\;\;U\\
    \forall\;a\in U:\quad Pr[i=a]\;=\;\;\frac{1}{|U|}
    $$

    正式来讲,均匀随机变量是一个恒等函数 ,也就是说对全集中的所有$x$,$R(x)$等于$x$。

  7. 随机化算法

    确定性算法:给定输入数据,总是产生相同输出的算法。即一个输入数据$m$ ,总产生相同输出$A(m)$的函数:

    $$
    y \longleftarrow A(m)
    $$

    随机化算法:取输入数据$m$作为输入,但它每次执行算法时都重新取一个隐性参数$r$,因为我们每次执行算法所取的$r$都不同,因此即使输入的数据$m$一致,输出也不会相同:

    $$
    y \longleftarrow A(m\;;\;r)\quad \mathbf{where}\quad r \overset{R} \longleftarrow \{0,1\}^R\\\\
    \mathbf{output\;\;is\;\;a\;\;random\;\;variable}\\\\
    y \overset{R} \longleftarrow A(m)
    $$

    关键:即使随机化算法每次执行时的输入都一样,你还是会得到不同的输出。

    本节完

    注意:本节和下一节的知识相当基础和重要。在以后探讨OTP密码、密码的安全性和PRG时将会经常用到。

  8. 10月前Ray Eldath 重新编辑

    -image-

    密码学I:离散概率(速成课)(续)

    导览

    课程地址请见Coursera

    对于离散概率的更详细解释,请见:WikiBooks (English)


    欢迎访问作者博客

    若未阅读上篇文章密码学I:离散概率的,强烈建议前去阅读。

    独立性

    定义

    独立性:若存在两事件$A$、$B$,$A$事件的发生无法向你提供关于$B$事件的任何信息,则称$A$、$B$两事件是互相独立的。即:

    $$
    Pr[A\;\:\mathtt{and}\;\:B]=Pr[A]\cdot Pr[B ]
    $$

    通常来讲,独立性衡量的是两事件间互不相关的程度。

    随机变量中的独立性

    若有两个在集合$V$中取值的随机变量$X,Y$,那么如果这两个随机变量满足:
    $$
    \forall a,b\in V\\\\
    Pr[X=a\;\:\mathtt{and}\;\:X=b]\;\;=\;\;Pr[X]\cdot Pr[Y=b]
    $$

    这意味着即使你知道$X=a$你也不知道关于$y$的取值的任何信息。

  9. 10月前Ray Eldath 重新编辑

    异或运算(XOR)

    这是一种在密码学中相当重要的运算。

    关于其重要的原因我们将稍后讲到。

    定义

    一种对数值$A$和$B$进行的运算,记为:
    $$
    A\oplus B
    $$
    其运算基本规则为:两两数值相同时为假,而数值不同时为真。

    通常来讲,我们所写的形如$100101\oplus 110110$表示过对数值的每一位进行运算。即(一般我们用$1$表示“真”,用$0$表示“假”):$$100101\oplus 110110=010011$$

    请见:维基百科 - 逻辑异或(中文 - 大陆简体)

    异或运算(XOR)的重要性质

    阐述:若存在一个随机变量$y$,和一个独立均匀随机变量$x$,此时$x$和$y$的异或(无论$y$以什么方式分布)$z$总是一个均匀的随机变量

    换句话说如果我取一个随机的分布,然后用独立均匀随机变量和它进行异或运算,最终得到的一定是一个均匀随机变量,即:
    $$
    Y\mathtt{\quad is\;\:a\;\:\mathbf{rand.}\;\:var.\;\:over\quad}\{0,1\}^2,\\\\
    X\mathtt{\quad is\;\:an\;\:\mathbf{indep.\;\:uniform}\;\:var.\;\:on\quad}\{0,1\}^2\\\\
    \mathtt{Than\;\;}Z:Y\oplus X\mathtt{\quad is\;\:\mathbf{uniform}\;\:var.\;\:over\quad}\{0,1\}^2
    $$
     /<< 证明现不列出。可能会在作者博客上给出。

    生日悖论(The birthday paradox)

    定义
    定义:假设在全集$U$中选择几个独立、以相同方式分布的随机变量$n$ ,则如若选择$\sqrt{|U|}$次,则基本上有很大的几率(超过$\frac{1}{2}$)会有两个相同的元素。换句话说,若抽样$\sqrt{|U|}$次,那么很有可能(超过$\frac{1}{2}$)你的两个抽样会是 一样的,即:
    $$
    r_1,...,r_n\in U\mathtt{\quad are\;\:indep.\;\:and\;\:has\;\:same\;\:way\;\:of\;\:distribution}\\\\
    \mathtt{when}\quad n=1.2 \times \sqrt{|U|} \quad \mathtt{than}\quad Pr[\exists i\neq j: \;r_i=r_j ]\ge \frac{1}{2}\\\\
    \text(\exists \quad \text{means "exist")}
    $$

    该定理被叫做“悖论”是因为经常使用该定理来描述人们的生日。因为根据该定理,最少仅仅需要$1.2\times\sqrt{365}$个人聚集在一起就能够使得有两个人有同样的生日的概率大于$\frac{1}{2}$,即24个人。这就是为什么叫做悖论,因为24应该是一个比大多数人的预计都要小的数。

    应用
    -image-
    假设我们有一个100万样本的全集,那么当我们抽样大概1200次时, 我们抽样到相通数字元素的概率大约是$0.5$;但是你可以看到如果我们抽样2200次,有两个元素相同的概率就已经是$0.9$了;你也看到了抽样3000次时基本就是$1$了。所以只要取样个数超过全集大小的平方根,抽到相同元素的概率将会很快趋近于1

    以后我们会再返回并更具体地学习生日悖论,但目前就到此为止。

    结语

    本节和上一节主要介绍了概率分布基础、事件、随机变量基本知识以及一种在密码学中非常常用也非常重要的算法XOR(异或运算,$\oplus$)及其基本性质,最后简要介绍了密码学中一个非常中心的理论:生日悖论。
    本节和上一节的知识相当基础和重要。

    下一节/下一章我们会开始学习我们的加密系统的第一个例子。

    本节完

    本章完

  10. 你的博客背景吓我一跳,还以为蜘蛛爬我电脑上了…… /O!O

  11. @z6226618 你的博客背景吓我一跳,还以为蜘蛛爬我电脑上了…… /O!O

    2333( ・ิϖ・ิ)

  12.  /asnowwolf-smile

  13. 10月前
    10月前Ray Eldath 重新编辑

    -image-

    喵。

    密码系统

    密码系统的定义

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

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

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

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

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

    - $D$ :Decrypt algorithm,解密算法。用于建立 $D \times K \longrightarrow M$(即密文 + 密钥 到 明文) 的对应关系。

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

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

    -image-

    一致性原则

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

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

    用符号来表示,就是:

    $$
    \forall\:m \in M,\;k \in K \\ D(k,\: E(k,\: m))=m
    $$

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

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

    特性

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

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

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

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

  14. 7月前
    7月前Ray Eldath 重新编辑

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

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

    定义

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

    • $K = {0, \: 1}^n$
    • $M = {0, \: 1}^n$
    • $C = {0, \: 1}^n = 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密码是不可能实现哒!

    1498625083235424.png

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

    为什么呢?

    因为

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

    90.png

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

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

    81311012714191810278

    话说在markdown块里用不了[attachment]标签还是有点蛋疼啊... 对不起 是我傻逼了 打扰大家了
    而且我上边的公式为啥没法正常显示 我原本是一个多行对齐的啊 /asnowwolf-smile 问题解决。原来行尾的\\需要转义到\\\\... /--

  15. 7月前Ray Eldath 重新编辑

    密码的安全性

    定义和阐释

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

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

    Claude-Elwood-Shannon.jpg

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

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

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

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

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

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

    $$ \forall m_0 ,\: m_1 \in M \;\; (\:len(m_1)=len(m_2)\:)\qquad \text{and} \quad \forall c \in K\ Pr[\:E(k, \: m_0)=c\:]\;=\;Pr[\:E(k, \: m_1)=c\:]\ (k \overset{R} \longleftarrow K ) $$

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

    该描述表明:

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

    即:

    $$ \text{given}\quad c \quad \text{can not tell if message is}\quad m_1\:\:\text{or}\:\:m_2\ (\forall\:m_1,\;m_2) $$

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

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

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

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

    <完>

    完成于2017.7.27 最后修订于2018.1.25

  16. 难道不可以事先传输一个otp keypad(比如安全信使之类的,信使不能截获消息因为 他拿到的是乱码),然后传输
    另外量子通信不就是干这个的吗?(保密传输大量真随机数据,但是不能传输任意数据)

  17. @Alan-Liang 难道不可以事先传输一个otp keypad(比如安全信使之类的,信使不能截获消息因为 他拿到的是乱码),然后传输
    另外量子通信不就是干这个的吗?(保密传输大量真随机数据,但是不能传输任意数据)

    emm... 这里的意思是此处所指的OTP密码要求密钥和原文等长,如果你能事先传输一个和原文等长的密钥,那就没有必要使用加密手段了;因为你完全可以直接传输原文过去。
    我确信很早以前在环科上看过一个讲量子通信的论文... 但是找了半天也没有找到 所以它到底怎么工作我现在也不太清楚

    看来以后得记个索引...

  18. 6月前

    hello-cryptography-5.png

    啦啦啦~ /asnowwolf-laugh

    上节回顾

    在上一节中,我们讨论了第一个完整的密码OTP密码,并以通过香农提出的密码安全理论衡量了OTP的安全性是完美的。

    本节我们将对收尾上节,并讨论一些必要的知识PRG和针对OTP密码的攻击。

    “OTP密码是最优情况”

    引语

    上节提到,OTP密码由于密钥长度需等于明文长度,因此在实际中很难实现

    那么,有没有一种密码,既具有完美安全,密钥长度又没有那么长呢?

    为什么这么说?

    因为当然没有啊!(///ω///)

    8.png

    没想到吧

    没想到吧!

    怎么样!没想到吧!

    让我们再次请出克劳德·香农教授:

    Claude-Elwood-Shannon.jpg

    克劳德·香农 来源:a0.att.hudong.com

    怎么样!帅不帅!

    香农在论证完“OTP密码具有完美安全性”之后,又论证了一个非常重要的命题:

    若一个密码完美安全,则其全体密钥的数量的必须不少于全体明文的数量

    即:

    $$ |\mathscr K|\ge |\mathscr M| $$

    也就是说... ...

    $$ \mathtt{for \;\: perfect \;\: key,}\quad len(k)\ge len(m) $$

    因此,OTP密码的密钥长度等于明文长度,其实是完美密码中的最优情况

    因此,对于上篇文章中评论(指的是[url=https://zhuanlan.zhihu.com/talk-about-cryptography]知乎上[/url]的评论)提出的问题:~~对于“足够长的PSK”~~没有足够长的PSK,最“足够”长就是和明文一样长

    (注:香农完整论文请见(PDF) A Mathematical Theory of Communication by C.E. Shannon hosted by the Harvard Mathematics Department at Harvard University

    所以... ...

  19. 6月前Ray Eldath 重新编辑

    续上一回复=-=

    伪随机数生成器(PRG)

    在攻击OTP密码(嗯?)和讨论流密码(下篇讲)之前,我们需要了解一个相当重要的玩意:伪随机数生成器(Pseudo-random Generator, PRG)

    这有啥用?

    本篇不会涉及到流密码。但为了说明PRG的用途,在这里还是要提一下。

    流密码实现的基本思路,就是将随机的密钥换成伪随机的密钥;即对输入的密钥$k$应用一个伪随机数生成器$G$,将其扩充为一个长得多的伪随机密钥$G(k)$,随后使用这个$G(k)$完成加密过程。

    定义

    本质上讲,PRG就是一个高效的、确定的、不可预测的函数$G$,能将一个长度为$s$的二进制数字符串,扩充为一个长得多的、长度为$n$的二进制数字符串。即:

    $$
    \text{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 : \quad E(k,\:m)=c \;\}=1 \quad \forall m,\:c
    $$

    • 高效:可理解为在特定时间内完成,或在多项式时间内完成。本系列文章中的“高效”均采用这个定义。
    • 确定:可简单理解为只要输入不变,输出必然不变。严格定义请见你好,密码学(2):离散概率(速成课)【就在上边】)。

    不可预测性

    我们提到,PRG必须具有一个性质,叫做不可预测性。

    这是个啥玩意呢?

    简单来说,“不可预测”就是“不”“可预测”。

    所以,下面我们将讨论可预测性

    33.jpg

    想不到吧

    (其实这么安排是为了便于理解。真的,你们要相信我)

    如果一个“PRG”函数$G$是可预测的,那么说明存在一个高效的函数$A$,能过通过$G$的输出的前1位字符串,还原出余下的位。即:

    $$
    \exists \:i:\quad G(k)|_{1,...,i} \overset{A}\longrightarrow G(k)|_{i+1}
    $$

    如果一个“PRG”是可预测的,那么若一个攻击者截获了密文,并且事先知道明文的前缀;(例如必须以“Dear Ray Eldath: ”开头,哈哈)那么他可以将截获的密文与该前缀异或,得到的就是$G(k)$的前缀。由于该“PRG”是可预测的,因此该攻击者就能通过$G(k)$的前缀,还原出整个$k$。

    严格地讲(有兴趣的阅读,跳过此部分对后续内容理解没有影响),不可预测性阐述对于所有的$i$,没有有效的破解算法$A$,能以不可忽略的概率预测出第$i+1$位。

    • 不可忽略:可理解为函数值大于某个特定概率值$\varepsilon$(例如$\varepsilon\gt {1 \over 2^{30}}$);或对于函数$\varepsilon:Z^{\ge0}\rightarrow R^{\ge0}$,函数值大于$1$除以某个多项式的值的可能性无限大(即$\exists \:d:\varepsilon(\lambda) \ge {1 \over {\lambda^d}}\quad \mathtt{inf.\;\: often}\quad(\varepsilon > {1\over \mathtt{poly}},\; \mathtt{for \;\: many\;\:}\lambda)$)(别问窝后面的定义啥意思,自己想。窝也看不懂)。

    未完待续...

  20. 6月前Ray Eldath 重新编辑

    安全性

    本节内容增补于2018.1.24

    我们说一个PRG是安全的,就意味着我们认为这个PRG的输出是均匀的。也就是说,一个PRG$G$是安全的,当且仅当它的输出分布与均匀随机分布不可区分 。即:

    $$
    [\;k\overset{R} \longleftarrow \mathscr K \text{, output }G(k)\;] \quad \text{is `indistinguishable` from } \quad [\;r\overset{R} \longleftarrow {\{0,1\&} ^n\text{, output r}\;]
    $$

    这意味着由于种子空间太小而远远小于全体二进制字符串空间的PRG输出空间(见下图),要与全体二进制字符串空间不可区分

    Venn.png

    并不是一个显然的特性。从上图可以看出,要使远小于蓝色圆框(代表全体二进制字符串)与红色圆形(代表PRG输出)不可区分,是困难的。

    为了定义“不可区分”,下面将引入几个概念:

    1. 二进制串是否随机:统计测试

    统计测试是一个算法$A$,它以$n$位的二进制字符串作为输入,输出其是否随机

    $$
    \text{for } \;\: x={\{0, 1\}}^n \text{, }\quad A(x)=
    \begin{cases}
    0, & \text{if $\;x\;$ is not random} \\
    1, & \text{if $\;x\;$ is random}
    \end{cases}
    $$

    可能会采取以下策略来判断一个二进制字符串$x$是否是随机的:

    1. $A(x)=1$,当且仅当$x$中$0$出现的次数$1$出现的次数差距足够小

    $$ A(x)=1 \quad \iff \quad |\:\#0(x)-\#1(x)\:| \le 10 \sqrt n \quad \text{(for example)} $$

    1. $A(x)=1$,当且仅当$x$中连续出现$00$序列(即两个$0$挨着)的次数足够小

    $$ A(x)=1 \quad \iff \quad |\:\#00(x)-\frac n 4 \: | \le 10 \sqrt x \quad \text{(for exampl-e)} $$

    1. ...

    以上这些可能的策略仅为说明统计测试可能以怎样的模式进行。不具有实际实现意义。

    2. 统计测试的优劣:优势

    统计测试$A$相对于PRG$G$的优势,是$A$认为$G$输出的伪随机序列作为输入是随机的的概率,与$A$认为真随机序列$r$作是随机的的概率的差:

    Snipaste_2018-01-25_18-37-35.png

    妈呀这公式打得费劲死了ヾ|≧_≦|〃

    由于$\underset{PRG} {Adv}$是一个概率的差,因而它只能取$0$和$1$之间(包括$0$和$1$)的值,即$\underset{PRG}{Adv} \in [0,\:1]$。

    下面我们来看看这个值的意义:

    • 它越接近$1$,$A$就越认为一个真随机序列和一个$G$输出的伪随机序列的差别就越大,则这个统计测试就越能区分真随机序列和伪随机序列
    • 反之亦然。越接近$0$,就越不能区分。
  21. 更新的帖子 ›
 

后才能发言