Ray Eldath

正式用户

最新动态 1天前

  1. 6月前
    2018-06-30 18:42:57
    Ray Eldath 修改了简介为: 渴望知识的高中生 / 知乎:Ray Eldath; GitHub: Ray-Eldath 知乎:Ray Eldath
  2. 2018-06-30 18:33:24
    Ray Eldath 更新于 【密码学】现代密码学

    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密码增添完整性保护,才能解决这个问题。

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

    <完>

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

  3. 2018-06-30 18:32:24
    Ray Eldath 更新于 【密码学】现代密码学

    典型的弱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系统已经可被认为是“易被攻破的”了。

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

  4. 2018-06-24 00:15:43
    Ray Eldath 更新于 【密码学】现代密码学

    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$。

    [attachment:5b2e71fb05d57]

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

    延伸阅读

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

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

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

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

    NIST Statistical Test Suite

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

  5. 2018-06-24 00:13:48
    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输出空间(见下图),要与全体二进制字符串空间不可区分

    [attachment:5b2e711d85d57]

    并不是一个显然的特性。从上图可以看出,要使远小于蓝色圆框(代表全体二进制字符串)与红色圆形(代表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$作是随机的的概率的差:

    [attachment:5b2e7135c2bd2]

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

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

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

    • 它越接近$1$,$A$就越认为一个真随机序列和一个$G$输出的伪随机序列的差别就越大,则这个统计测试就越能区分真随机序列和伪随机序列
    • 反之亦然。越接近$0$,就越不能区分。
  6. 2018-06-24 00:08:13
    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必须具有一个性质,叫做不可预测性。

    这是个啥玩意呢?

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

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

    [attachment:5b2e703d66339]

    想不到吧

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

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

    未完待续...

  7. 2018-06-24 00:03:20
    Ray Eldath 更新于 【密码学】现代密码学

    [attachment:5b2e6e6136de1]

    啦啦啦~ /asnowwolf-laugh

    上节回顾

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

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

    “OTP密码是最优情况”

    引语

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

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

    为什么这么说?

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

    [attachment:5b2e6ee7cd628]

    没想到吧

    没想到吧!

    怎么样!没想到吧!

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

    [attachment:5b2e6ebd949d2]

    克劳德·香农 来源: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

    所以... ...

  8. 7月前
    2018-06-10 10:11:00
    Ray Eldath 更新于 【密码学】现代密码学

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

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

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

  9. 2018-06-09 21:34:39
    Ray Eldath 更新于 【密码学】现代密码学

    密码的安全性

    定义和阐释

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

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

    [attachment:5b1bd7530c47b]

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

    “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

  10. 2018-06-09 20:57:28
    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密码是不可能实现哒!

    [attachment:5b1bcda602929]

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

    为什么呢?

    因为

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

    [attachment:5b1bcdcdc6f89]

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

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

    81311012714191810278

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

查看更多