非常好的密码学系列视频导论 自行扶梯

目录

1.分组加密简介
2.非对称密码学的数学基础
3.RSA算法的原理
4.DH算法的原理
5.信息摘要和Hash算法

1.分组加密简介

其实 之前的一篇文章里面已经提及到了分組加密(Block cipher)密和流加密(Stream cipher)。知乎上许多人讨论 bitcoin 的区块加密原理,这里只简单概述 Block cipher ,下面引用 wiki 凑个字数。

在密码学中,流加密(英语:Stream cipher),又译为串流加密、资料流加密,是一种对称加密算法,加密和解密双方使用相同伪随机加密数据流(pseudo-random stream)作为密钥,明文数据每次与密钥数据流顺次对应加密,得到密文数据流。实践中数据通常是一个位(bit)并用异或(xor)操作加密。该算法解决了对称加密完善保密性(perfect secrecy)的实际操作困难。“完善保密性”由克劳德·香农于1949年提出。由于完善保密性要求密钥长度不短于明文长度,故而实际操作存在困难,改由较短数据流通过特定算法得到密钥流。

在密码学中,分组加密(英语:Block cipher),又称分块加密或块密码,是一种对称密钥算法。它将明文分成多个等长的模块(block),使用确定的算法和对称密钥对每组分别加密解密。分组加密是极其重要的加密协议组成,其中典型的如DES和AES作为美国政府核定的标准加密算法,应用领域从电子邮件加密到银行交易转帐,非常广泛。现代分组加密建立在迭代的思想上产生密文。其思想由克劳德·香农在他1949年的重要论文《保密系统的通信理论》(Communication Theory of Secrecy Systems)中提出,作为一种通过简单操作如替代和排列等以有效改善保密性的方法。[1] 迭代产生的密文在每一轮加密中使用不同的子密钥,而子密钥生成自原始密钥。

常用的分组密码工作模式有:

电子密码本(ECB)
密码块链接(CBC)

<—–此处只介绍上面两个模式—–>

填充密码块链接(PCBC)
密文反馈(CFB)
输出反馈(OFB)
计数器模式(CTR)

最简单的加密模式即为电子密码本(Electronic codebook,ECB)模式。需要加密的消息按照块密码的块大小被分为数个块,并对每个块进行独立加密。1976年,IBM发明了密码分组链接(CBC,Cipher-block chaining)模式。在CBC模式中,每个明文块先与前一个密文块进行异或后,再进行加密。在这种方法中,每个密文块都依赖于它前面的所有明文块。同时,为了保证每条消息的唯一性,在第一个块中需要使用初始化向量。


电子密码本(ECB)
可以说这种分组加密模式是最简单的,就是切割成等大的 Block 之后,用相同的 Key 进行加密和解密。看图片就一目了然:

用公式来表示,已知存在普通的加密方式:
c = Ek(m)
把 m 分成许多小块 m0,m1,m2,m3……mn
这时候,就存在:
c0 = Ek(m0 )
c1 = Ek(m1 )
c2 = Ek(m2 )
c3 = Ek(m3 )
……
mn = Ek(mn )

由于 EBC 采用了同一把 key ,所以在运算的时候,支持并发多进程同时计算,在性能上有绝对的优势。但是,当接受端收到的报文顺序是c0,c2,c3,c1,这样的错误顺序, ECB 就没办法解决了,这就存在密码学中的 剪下和贴上问题(Cut and Paste)。还有信息安全中的完整性(Integrity)和保密性的问题,由于采用了相同的 key ,所以明文 m 和密文 c 总是存在一一对应的关系,当攻击者有足够多的对应关系时,就有很大几率猜测到明文的内容。譬如 ip 包的数据格式有些是不变的,用 EBC 加密时,对应的密文总是不变的。

补充一点,ECB 是如何处理不足一个 Block 的数据的,密码学称为填充(Padding)。譬如采用的是 DES 加密,会把数据分成 64 bit 为一个 Block ,不足部分就填充数据,填充需要协商,可以是全零,或者全一,或者其他等等。


密码块链接(CBC)
刚刚上面说了 ECB 的优缺点,现在假设每一个 Block 采用不同的 Key 加密,能解决上面的问题吗?其实本系列的前几篇提到多的 OTP(one-time pad) 思路和这个假设是一样的,第一个 Block 用一把 key 加密,然后第二个 Block 用第二把 key 做加密,如此类推,这是最安全的,但是需要频繁交换 key ,而且管理上也很麻烦。

既然 OTP 不行,那么前几篇提到的 codebook 可以解决 ECB 的缺点吗?codebook 里面就有许多随机的 key

嗯,是可以的。也如前几篇提及的办法一样,除了 codebook 之外还需要 Additive book 的加入。首先介绍一个叫初始向量(initialization vector)的东西,它是一个随机乱数,简称IV。用公式来表示,已知存在普通的加密方式:
c = Ek(m)
把 m 分成许多小块 m0,m1,m2,m3……mn
这时候,就存在:
c0 = Ek(m0⊕IV )
c1 = Ek(m1⊕c0)
c2 = Ek(m2⊕c1 )
c3 = Ek(m3⊕c2 )
……
mn = Ek(mn⊕cn-1 )

这样的好处在于,加密依然采用同一把 Key,但是打破了 ECB 里面的独立性问题,相邻之间的密文会受到影响。


CBC 的优点使它也存在缺点,那就是当一个 Block 存在错误的时候,会导致后面的加密或者解密出现问题,譬如当c1加密出错,变成了g1,那么在解密的时候就会出现下面的错误:

虽然上面影响的明文只有m1和m2,但是依然是存在 Cut and Paste 问题


下面一张图,就很好的证明了 CBC 的加密保密性强于 ECB

计算器模式(CTR)
计算器模式不常见,在CTR模式中,有一个自增的算子,这个算子用密钥加密之后的输出和明文异或的结果得到密文,相当于一次一密。这种加密方式简单快速,安全可靠,而且可以并行加密,但是在计算器不能维持很长的情况下,密钥只能使用一次。CTR的示意图如下所示:

2.非对称密码学的数学基础

高中数学考过11分的我,无所畏惧。继续凑字数:

公开密钥加密(英语:public-key cryptography,又译为公开密钥加密),也称为非对称加密(asymmetric cryptography),一种密码学算法类型,在这种密码学方法中,需要一对密钥,一个是私人密钥,另一个则是公开密钥。这两个密钥是数学相关。用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。常见的公钥加密算法有:RSA、ElGamal、背包算法、Rabin(RSA的特例)、迪菲-赫尔曼密钥交换协议中的公钥加密算法、椭圆曲线加密算法(英语:Elliptic Curve Cryptography, ECC)。使用最广泛的是RSA算法(由发明者Rivest、Shmir和Adleman姓氏首字母缩写而来)是著名的公开秘钥加密算法,ElGamal是另一种常用的非对称加密算法。

与对称密钥加密相比,公钥加密使用两把不同的密钥,公钥可在互联网上公开,私钥必须保证仅自己所有。因为使用公钥进行加密的内容,只有私钥可以解开。但用私钥加密的内容,公钥可以解开。详细請参考阮一峰先生的 RSA算法原理一

3.RSA算法的原理

RSA算法原理二 写的无懈可击,小白不敢妄自概述,大家可以优先参考。

4.DH算法的原理

迪菲-赫尔曼密钥交换(英语:Diffie–Hellman key exchange,缩写为D-H) 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。公钥交换的概念最早由瑞夫·墨克(Ralph C. Merkle)提出,而这个密钥交换方法,由惠特菲尔德·迪菲(Bailey Whitfield Diffie)和马丁·赫尔曼(Martin Edward Hellman)在1976年首次发表。马丁·赫尔曼曾主张这个密钥交换方法,应被称为迪菲-赫尔曼-墨克密钥交换(英语:Diffie–Hellman–Merkle key exchange)。虽然迪菲-赫尔曼密钥交换本身是一个匿名(无认证)的密钥交换协议,它却是很多认证协议的基础,并且被用来提供传输层安全协议的短暂模式中的完备的前向安全性。
关于离散对数的概念和算法的原理,许多前辈写的很好,可以参考这一篇文章。

  • 1 给定 p 为质数,并且选定 g 为 generator ,其满足对于 x ∈ {1,2,3….,p-1}会有 n 使得 x = gn mod p
  • 2 Alice 选择自己的私有数值 a
  • 3 Bob 选择自己的私有数值 b
  • 4 Alice 将 ga mod p 发送给 Bob
  • 5 Bob 将 gb mod p 发送给 Alice
  • 6 Alice 和 Bob 可以利用自己的私有数值计算出一个共享的值:gab mod p,这个值可以当作是对称加密算法里面的 Key

我们可以发现,有下面的数学表达式
公开的内容有:g 和 p
私有的内容有: Alice 的 a 和 Bob 的 b
Alice 需要计算(gba = gab mod p
Bob 需要计算(gab = gab mod p
Alice 和 Bob 可以使用 KAB = gab mod p 作为对称加密算法的 Key
一个被动的攻击者只能窃听通讯,但是无法得到 gab ,因为求解离散对数问题是困难的,但是存在 MITM 攻击的可能性。比如存在攻击者 Charlie 的话,那么就会有下面:

  • 1 Alice 发送的 ga mod p 给 Bob,但是通讯的数据被中间人 Charlie 截获

  • 2 Charlie 伪装自己是 Alice ,继续与 Bob 通讯,所以会发送 gc mod p 给 Bob

  • 3 Bob 收到了 Charlie 的数据,此时会认为通讯者是 Alice ,于是会回应gb mod p 给 Charlie

  • 4 Charlie 收到 Bob 的回应,为了伪造 Alice 和 Bob 之间是正常通讯,Charlie 会发送 应gc mod p 给 Alice

  • 5 整个 MITM 攻击链完成,相当于在 Charlie 站在 Alice 和 Bob 两个人之间

    下面举一个例子,只需要知道基本的模运算和一点点英语水平,不能理解的话建议回到 文章RSA算法部分 阅览两篇参考文章

5.信息摘要和Hash算法

首先需要知道信息安全的 CIA 原则。对于消息,需要保证完整性、可行性和时效性。对消息加密不一定就能解决完整性的问题,譬如 ECB 分组加密,攻击者重新排列分组次序后可以破解。再者不是所以消息都需要加密传输,譬如广播包,认证数据等,只需要证明数据来源可靠真实即可。消息认证有三种方式:

  • 1 消息加密(Message encryption),整个消息的密文作为认证的标识
  • 2 消息认证码(公开函数+密钥),采用一个公开函数,加上一个密钥产生一个固定长度的值作为认证标识
  • 3 散列函数,一个公开的函数将任意长度的消息映射到一个固定长度的散列值作为认证标识

消息认证码(英语:Message authentication code,缩写为MAC),又译为消息鉴别码、文件消息认证码、讯息鉴别码、信息认证码,是经过特定算法后产生的一小段信息,检查某段消息的完整性,以及作身份验证。它可以用来检查在消息传递过程中,其内容是否被更改过,不管更改的原因是来自意外或是蓄意攻击。同时可以作为消息来源的身份验证,确认消息的来源。
消息认证码的算法中,通常会使用带密钥的散列函数(HMAC),或者块密码的带认证工作模式(如CBC-MAC)。
信息鉴别码不能提供对信息的保密,若要同时实现保密认证,同时需要对信息进行加密

MAC 使用一个双方共享的秘密密钥生产一个固定大小的小数据块,并加入到消息中。
Alice 和 Bob 共享密钥 K,对于消息 m,MAC = Ck(m)。这时候如果接受方和发送方的MAC一致,就可以得知:

  • 消息 m 未被修改
  • 消息来自所声明的发送者
  • 如果消息中含有序列号,则可以保证正确的消息顺序

MAC函数类似于加密函数,但是不需要可逆性,因此数学上比加密算法被攻击的弱点少一点。MAC 不等于数字签名,因为通讯双方使用的是相同的 Key 。MAC 具有固定的长度,它的结构是它安全保证的基础,密钥足够长+加密算法足够好≠安全

  • m = (X1,X2,X3….Xt
  • 对于 m 产生的 MAC 是 M = X1⊕X2⊕X3⊕….⊕Xt
  • MAC = Ek(M)
  • 攻击者选择 M1 = (Y1,Y2….Yt-1,Yt)使得 Yt 满足:Yt = Y1⊕Y2⊕….⊕Yt-1⊕M
  • 于是M = M1,得出 Ek(M) = Ek(M1),得到 Ck(M) = Ck(M1),几时攻击者不知道 K ,仍然可以伪造消息 M1

    MD5消息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hash value),用于确保信息传输完整一致。MD5由罗纳德·李维斯特设计,于1992年公开,用以取代MD4算法。这套算法的程序在 RFC 1321 中被加以规范。
    将数据(如一段文字)运算变为另一固定长度值,是散列算法的基础原理。
    1996年后被证实存在弱点,可以被加以破解,对于需要高度安全性的数据,专家一般建议改用其他算法,如SHA-1。2004年,证实MD5算法无法防止碰撞,因此无法适用于安全性认证,如SSL公开密钥认证或是数字签名等用途。

MD5 以512位的分组来处理输入的信息,每一组又划分为16个32位子分组,每一个分组又要进过四轮的循环处理,啪啪啪的运行之后得出128位的摘要值。一般128位的MD5散列被表示为32位十六进制数字。以下是一个43位长的仅ASCII字母列的MD5散列:

1
2
3
4
5
6
7
8
MD5("The quick brown fox jumps over the lazy dog")
= 9e107d9d372bb6826bd81d3542a419d6
即使在原文中作一个小变化(比如用c取代d)其散列也会发生巨大的变化:
MD5("The quick brown fox jumps over the lazy cog")
= 1055d3e698d289f2af8663725127bd4b
空文的散列为:
MD5("")
= d41d8cd98f00b204e9800998ecf8427e

2009年谢涛和冯登国仅用了220.96的碰撞算法复杂度,破解了MD5的碰撞抵抗,该攻击在普通计算机上运行只需要数秒钟。MD5 是一种不可逆的变换算法,典型应用是对一段信息(Message)产生信息摘要(Message Digest),以防止被篡改。下面介绍的 sha-1 算法就是由 MD4 的基础上开发的。

SHA-1(英语:Secure Hash Algorithm 1,中文名:安全散列算法1)是一种密码散列函数,美国国家安全局设计,并由美国国家标准技术研究所(NIST)发布为联邦数据处理标准(FIPS)。SHA-1可以生成一个被称为消息摘要的160位(20字节)散列值,散列值通常的呈现形式为40个十六进制数。
SHA-1已经不再视为可抵御有充足资金、充足计算资源的攻击者。2005年,密码分析人员发现了对SHA-1的有效攻击方法,这表明该算法可能不够安全,不能继续使用,自2010年以来,许多组织建议用SHA-2或SHA-3来替换SHA-1。Microsoft、Google以及Mozilla都宣布,它们旗下的浏览器将在2017年前停止接受使用SHA-1算法签名的SSL证书。
2017年2月23日,CWI Amsterdam与Google宣布了一个成功的SHA-1碰撞攻击,发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。

一个最简单的 Hash 函数是这样运作的:

  • 将输入的数据分成若干等长的分组
  • 对每一个分组按位进行异或运算
  • 结果为其消息摘要

Hash 函数的特点:

  1. 输入长度没有长度限制,能把任意长度的输入数据生成固定的输出
  2. 已知 m ,计算 hash(m)是容易的
  3. 已知 c = hash(m),求 m 是困难的
  4. 已知 hash(m1)= c1, 构造 m2,使得 hash(m2)= c1 是困难的
  5. 已知 c = hash(m),c 的每一个比特都与 m 的每一个比特有关,并且高度敏感。每改变一个 m 的 比特,都会有明显的影响。

有两种攻击手法适用于 Hash 函数,暴力破解和生日悖论,由生日悖论得知,当一个40比特的信息摘要是很不安全的,因为只需要用220(大概一百万)次的随机 Hash 就至少拥有 50% 概率得出正确明文。通常建议消息摘要的长度至少应该128比特,此时生日攻击需要约264次 Hash 运算。
MD5 标准的输出长度选为128比特
SHA-1 标准的输出长度选为160比特

IV = initial value 初始值
CV = chaining value 链接值
Yi = ith input block 第i个输入数据块
f = compression algorithm 压缩算法
n = length of hash code 散列码的长度
b = length of input block 输入块的长度
把原始消息 M 分成一些固定长度的块 Yi ,最后一块填充 padding 并使用包含消息 M 的长度。设置初始值CV0,压缩函数f,CVi = f(CVi-2,Yi-1) ,最后一个CVi为hash值
关于 sha1 攻击

结束语

之所以研究密码学,完全是因为考试需要…..重感冒配上小费马定律会更搭噢