【密码学】现代密码学

  1. ‹ 更旧的帖子
  2. 去年

    密码学的“魔法”

    私密外包计算

    搜索

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

    零知识证明

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

    一门严谨的科学

    三个步骤

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

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

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

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

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

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

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


    本节完

  3. 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$之间。

  4. 事件

    基本定义
    事件:考虑全集$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$。

  5. 随机化算法

    确定性算法:给定输入数据,总是产生相同输出的算法。即一个输入数据$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时将会经常用到。

  6. 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$的取值的任何信息。

  7. 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$)及其基本性质,最后简要介绍了密码学中一个非常中心的理论:生日悖论。
    本节和上一节的知识相当基础和重要。

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

    本节完

    本章完

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

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

    2333( ・ิϖ・ิ)

  10.  /asnowwolf-smile

  11. 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):离散概率(速成课)

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

  12. 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 问题解决。原来行尾的\\需要转义到\\\\... /--

  13. 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

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

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

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

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

  16. 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

    所以... ...

  17. 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)$)(别问窝后面的定义啥意思,自己想。窝也看不懂)。

    未完待续...

  18. 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$,就越不能区分。
  19. 3. 安全性

    我们已经定义了衡量字符串是否随机的统计测试,再定义了衡量统计测试优劣的优势,下面我们将定义PRG的安全性。

    为便于讲解,我们先讨论在一个单独的统计测试$A$的情况下$G$的安全性,再讨论$G$的全局安全性:

    如果对于统计测试$A$相对于PRG$G$的优势可忽略,那么我们认为$A$验证了$G$的输出分布与均匀随机分布不可区分 ,也即$G$在$A$下是安全的。

    我对这个定义做一点解释:

    • 首先,统计测试$A$的作用在于衡量$G$的输出是否随机,而优势的作用在于衡量$A$区分$G$的输出与真随机序列的能力;
    • 因而如果这个值比较高(不可忽略,见上文对它的定义),那么$A$就认为一个真随机序列与$G$的输出的差别就比较大,故根据先前的描述,这个PRG被$A$验证了它不安全。我们会说$G$被$A$以优势$\underset{PRG} {Adv}$攻破。

    下面给出$G$的全局安全定义:

    $G$是安全的,当且仅当不存在有效的统计测试可以攻破$G$。

    解释:

    • 如果不存在一个统计测试$A$,能以不可忽略的优势攻破$G$,那么所有的统计测试都不能有效区分PRG$G$的输出与真随机序列的区别,也就是说$G$的输出与真随机序列不可区分,故根据我们最开始的讨论,$G$就是安全的。

    这样,我们就定义了PRG的安全性。

    这是可实现的吗?

    还有最后一个问题,就像讨论OTP时一样,我们还想知道,这是可实现的吗?

    答案是:不知道!

    因为要求证是否有一个安全的PRG算法,等价于证明$P\ne NP$。

    90.png

    关于为何如此,我还没找到相关的论文。麻烦找到过相关资料的读者告知一下*<(´・ω・)っ

    延伸阅读

    此外,关于PRG的安全性,推荐以下几个页面作为延伸阅读:

    如何评价一个伪随机数生成算法的优劣? - sunoru的回答 - 知乎

    如何评价一个伪随机数生成算法的优劣? - 余天升的回答 - 知乎

    随机性#随机性测试方法 - 维基百科

    NIST Statistical Test Suite

    本节到此为止。下一节:典型的弱PRG实现 /xx

  20. 典型的弱PRG实现

    这是反例!!请勿在要求密码学强度的系统中使用这些实现!!

    这是反例!!请勿在要求密码学强度的系统中使用这些实现!!

    这是反例!!请勿在要求密码学强度的系统中使用这些实现!!

    • 线性同余方法:该方法被广泛应用于统计学强度的系统中。关于线性同余方法,维基百科的解释已经很清楚了,在此不过多解释:

      维基百科 - 线性同余方法#随机性 摘自zh.wikipedia.org

      此外,对线性同余方法的改进,请见清华大学学报(自然科学版)# 2009.02 - 改进线性同余法随机数发生器

    • GNU C Library中提供的random()实现:该生成器每轮输出几位相同数据;每轮应用相同的线性变换,因此非常容易预测。要构建密码学强度的系统,请使用C++标准库中头文件random提供的各种random_engine

    • 自Java 7起提供的Random类及使用该类的Math.random()方法:从该Random.nextDouble()的实现可以看出,尽管使用了各种运算,但该方法依然是可预测的。要构建密码学强度的系统,请使用SecureRandom类

    • ... ...

    一般来说,各大编程语言提供的伪随机数通用实现出于效率方面的考量,都达不到密码学强度的要求。请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现。请查看使用的编程语言是否有提供密码学强度的伪随机数生成器实现。没有就自己实现一个吧。

    咳咳。我再强调一下:

    请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现!!

    请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现!!

    请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现!!

    请查看使用的编程语言是否有提供密码学强度的伪随机数生成器实现。没有就自己实现一个。

    这点相当重要。类似Kerberos 4的系统就因为伪随机数生成器实现的问题而被攻破。(参见维基百科 - Kerberos#历史

    攻击OTP密码

    看到这个标题,我不确定会不会有人心生疑问:

    OTP密码不是完美安全的吗?又怎么能被攻破呢?

    是的!OTP密码确实完美安全,但“完美安全”指的是免疫任何唯密文攻击。而本节所述的攻击大多是针对密码实现的攻击。(也就是说这些实现或多或少的不严格符合OTP密码的定义)

    。。。。。。

    好啦!让我们开始吧!

    Attack 1:使用相同密码本加密多于一个的不同密文

    我们来通过一个例子看看,当使用同一密码本加密两条(此处以两条为例)的不同密文时会发生什么:

    由于上文已经介绍了PRG的相关知识,因此下文中将使用$PRG(k)$代替前文中的$k$,从而使论述更为可信。

    首先,我需要得到这两个消息的加密结果(密文):

    $$ c_1=m_1\oplus PRG(k)\\ c_2=m_2\oplus PRG(k) $$

    Q1:那么,当我计算$c_1\oplus c_2$时,会得到什么呢?

    先不要往下看,先自己想想!

    由于$PRG(k)\oplus PRG(k)=0$,因此$c_1\oplus c_2$的结果就为$m_1\oplus m_2$

    震惊!将使用相同密码本加密两条密文的结果异或,得到的竟然是... ...

    得到了$m_1\oplus m_2$,由于语言本身(如英语)或编码方式(如ASCII)本身就提供了额外的信息,我们很轻易的就能分开$m_1$和$m_2$,从而得到明文。

    这么明显的错误,难道不是很容易避免吗?

    当然不是!

    著名的WEP协议(已过时)就因为这个问题(和其他一些严重的安全问题)最终被取代。

    说句题外话:在无线局域网络环境的配置中请勿使用WEP协议!推荐使用安全得多的WPA2/PSK协议。

    在WEP协议中,用于加密(可简单理解为携带无线局域网数据的单位)的密钥为$PRG(\theta \;||\;k)$,(其中$||$表示“拼接”,$\theta$表示“帧计数器”,即初始时为$0$,每多发送一个帧的计数器时$+1$s的计数器)我们可以看到WEP协议为了使每个帧使用不同的密钥加密引入了$\theta$这个帧计数器。但是由于密码的长度是固定的,因此$\theta$并不能无限增大,必须在约$10^{24}$后重置到$0$。于是... ...

    问题就出现了。

    基于一些其它的WEP协议的重大安全缺陷,我们最少可以在监听$40000$个帧后得到用于加密的主密钥$k$。至此,WEP系统已经可被认为是“易被攻破的”了。

    那有没有更好的实现方案?

  21. Attack 1:更好的实现

    从本质上看,Attack 1的出现是由于“不同明文使用不同密钥加密”的实现不正确导致的。因此下面将给出此类问题的通用实现(可能不是最好的):

    在上文对PRG的讨论中,我们指出PRG函数输出的是一个比输入长得多的字符串,(请允许我去掉那一长串形容词)因此我们可以直接将该长输出分段,然后每段加密不同的明文:

    capture1

    从而为每个明文分配不同的伪随机密钥。

    Attack 2:不完整的密文

    上篇文章对OTP密码的讨论中可以看出,OTP密码并没有提供对密文的完整性保护;也就是说,攻击者可以不被发现地修改密文,从而对明文造成特定影响

    Q2:我们使用OTP加密明文$m$将得到$m\oplus k$,但若攻击者截获此密文,并对其施加$\oplus p$,再解密被施加了操作的密文,我会得到什么?

    通过OTP密码的定义和异或运算的定义,我们可以知道$D(k,\: (E(m,\:k)\oplus p)\:)=(\:(m\oplus k)\: \oplus p)\oplus k$将得到$m\oplus p$

    问题就出现了。

    在预知$m$中部分消息和消息位置(比如$m$中一定在位置$(i,\:i+10)$($i$已知)包含字符串Ray Eldath)的情况下,我可以通过计算 我想替换上去的消息 和 已知明文中消息 的异或得到$p$,再在对应位置替换,则可以完成对消息的“不被发现的”篡改。

    那有没有更好的实现方案?

    Attack 2:更好的实现

    答案是:没有!

    因为Attack 2完全是由于“OTP密码不提供完整性保护”导致的,因此只有为OTP密码增添完整性保护,才能解决这个问题。

    关于如何为密码增添完整性保护,请期待以后的文章。(意思就是先坑着)

    <完>

    本篇完。下一篇:流密码基础 - 定义及其应用

 

后才能发言