Sherlock's blog

有容乃大，无欲则刚

0%

图解密码技术笔记

发表于 更新于 分类于
这篇文章是《图解密码技术》的读书笔记。希望没有密码技术背景的人或是没有读过这本 书的人通过这篇文章迅速建立起密码技术的基本概念。 各种密码技术就是用来保密，我们从具体的场景看起, 然后引出各种应对的手段。
  1. 监听
1
2
3
4
5
6
7
+-----+               +-----+
|  A  |------+------> |  B  |
+-----+      |        +-----+
             v
           +-----+
           |  C  |
           +-----+

比如A发送信息给B，可能有C在链路上监听。应对的方法就是对要发送的信息加密, 比如我
们可以把发送的信息码字都加上1，B减去1就得到A原来发送的信息。这里就引入了密码学
上的几个基本概念, 这里对发送的信息加密就是原来的信息和额外的信息做运算，我们把
额外的信息叫做秘钥，把所做的运算叫做加解密算法。秘钥一般是不公开的，对于加解密
算法，有公开的算法，也有商业公司自己保密的算法，不过公开的算法的安全性要大大高于
私有的算法，现在一般的做法也是密码相关的行业组织会公开征集特定用途的算法，大家
通过竞争选出最好的算法。

可以看到上面的例子中，A用来加密的秘钥和B用来解密的秘钥是一样的。这种加解密的
方法叫对称加解密。实际使用中，秘钥和加解密算法是很复杂的，C即使听到了加密信息，
没有秘钥也解不出A发出的信息。

但是这样的加解密方法有一个要解决的问题: 怎么把一样的秘钥分发给A和B(前面我们已经
提到算法是公开的)。A直接传给B显然是不靠谱的，因为C完全可以听到。引入第三方，也不
靠谱，只要传输，C就可以听到秘钥。

为了应对是上面的问题，人们发明了非对称加解密。也就是说A用来加密的秘钥和B用来解密
的秘钥不是同一个。非对称加解密使用的方法就是: 把加密秘钥发给对方，请对方用这个加密
秘钥加密信息, 解密秘钥自己留着，用来解密信息。下面的图是基本流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 +-----+                      +-----+
 |  A  |--------------------->|  B  |
 +-----+                      +-----+

           +-------+
           |pub key|  --> 
 +-----+   +-------+          +-----+
 |  A  |--------------------->|  B  |
 +-----+                      +-----+     +-------+   +---+
                                          |message| + |key| --+
             +--------------+             +-------+   +---+   |
          <--|crypto message| <-------------------------------+
 +-----+     +--------------+ +-----+
 |  A  |--------------------->|  B  |
 +-----+                      +-----+

 
+--------+   +--------------+
|priv key| + |crypto message|     
+--------+ | +--------------+
           v
+-----------------+
|message sent by B|
+-----------------+

可以看到C即使听到pub key也没有用，因为pub key是用来给发给A的信息加密的。上面又
有几个新的概念，公钥是可以公开的秘钥，私钥必须保密。

我们平时用的ssh用的就是非对称加密, 和上面的模型是可以对上的。非对称加密解决了
对称加密里对称秘钥分发的问题，我们可以使用非对称加解密代替对称加解密。当然，我们
也可以一开始采用非对称加解密解决对称加解密秘钥分发的问题，然后就可以使用对称
加解密了。

可以看到，非对称加解密的缺点是C可以拿到给A发信息用的加密秘钥。这样C可以把自己的
公钥发给B，诱导B用C的公钥加密信息，这样C监听B发给A的信息，就可以用C自己的私钥
解密信息。为了解决这个问题，就需要B可以确认他收到的是A的公钥。(to do: how to do)

非对称加解密还有一个缺点，就是秘钥生成和加解密都需要很大的算里。所以很适合做专门
的硬件加速器去offload cpu资源。

这里可以看下RSA算法步骤，RSA算法是经典的非对称加解密算法。我们这里只简单罗列RSA
算法的步骤，因为他表现的很简单有趣。这里E和N为加密秘钥，D和N为解密秘钥。加密和
解密做的运算就是:

1
2
                  E                            D
密文 = 明文  mod N           明文 = 密文  mod N

是不是很简单? 上面的密文和明文都是数字，加解密完全是一个求幂然后取模运算。但是
E, D是一个很大的数，大到用二进制表示，需要512bit，1024bit，2048bit，4096bit…
不同秘钥长度，当然密码的强度是不一样的。

E, D, N生成的算法是：

  1. 找两个很大的素数p, q

  2. N = p × q

  3. L = 最小公倍数(p - 1, q - 1)

  4. E为和L互质的数 —> (E, N)是加密秘钥，公钥

  5. (E × D) mod L = 1, 求出D —> (D, N)是解密秘钥，私钥

第2,5步的逆运算在数学上很困难，这个是RSA算法保密的根本。

  1. 篡改
1
2
3
4
5
6
7
+-----+                      +-----+
|  A  |------+  +----------->|  B  |
+-----+      |  |            +-----+
             v  |
           +----++
           |  C  |
           +-----+

相比较上面的被动攻击，C还可以篡改A发给B的数据，然后发给B(其实上面也提到了主动
攻击, 我们先从简单的说起)。为了应对这样的攻击，B需要有办法验证收到信息的完整性。
一般用单向散列得到A发出信息的hash码，然后A把这个hash码也发给B，B对收到的信息做
同样的单向散列，把得到的hash码和收到的hash作对比，从而验证信息的完整性。

这要的算法有SHA3, MD5等。其实，一般我们发送大文件的时候，用md5sum算文件hash码,
然后在对接收到的文件做校验，就是一样的道理。

单向散列算法需要保证的就是防止碰撞发生，简单说就是不同数据得到的hash码要不一样。

单向散列只是单纯的验证数据的完整性，并不能确认数据就是A发出的。C可以把A发给B的
数据和hash值都截获，修改数据，然后对修改后的数据做下单向散列，然后把修改的数据
和新生成的hash值发给B。

  1. 认证
1
2
3
4
5
6
7
+-----+                      +-----+
|  A  |--------------------> |  B  |
+-----+       +------------> +-----+
              |
           +--+--+
           |  C  |
           +-----+

如上，C也做下单向散列，然后把正确的hash码发送给B。B需要有办法确认他收到信息是A
发给他的，而不是别人伪造的。这里的问题和上面非对称加解密里C把自己的公钥发给B是
一样的问题。

当A，B有共享秘钥的时候，解决这个问题的方法是，信息和共享秘钥一起做单向散列。
但是非对称加密公钥配送的问题还是没有解决

对上面认证(也叫消息认证码)的攻击有: 重放攻击。有了消息认证码之后C无法篡改A发给B
的信息，但是C可以截获A发给B的信息，在A发给B信息后，再次发同样的信息给B。比如，A
给B的信息是请求B向A转一笔钱，那么B接收的C的信息后将会再次转钱给A。不过，应对这种
重放攻击，A只要在发送的信息加上编号或者是时间戳就好了。

消息认证码无法解决的问题: 对第三方证明，防止否认。对第三方证明比较好理解, 共享
秘钥存在于A和B，第三方的机构无法证明信息是A向B发的。防止否认的意思是, B也无法证
明A确实向B发了一条消息。其中的关键是消息认证码用的是共享秘钥, 比如A向B发了一个信
息说向B借了10万元钱(相当于A给B写了一个欠条)，这个信息用消息认证码加密, 当B拿着这
个消息向A去索要钱的时候，A完全可以否认自己发过这个消息，因为B也有A一样的秘钥，完
全是可以自己制造这个消息出来的。为了解决A否认消息是他发出的，就要引入数字签名，
就是给自己发出的信息签上自己的名字。

  1. 签名

如何给自己发出的消息上标记上自己无法否认的信息作为自己的签名？签名可以用非对称
加解密的相反运算实现: 用私钥加密信息给信息签名，用公钥解密加密的信息做验证。
因为私钥只有自己知道，而且用和私钥不对应的公钥算出来的数据不是被加密数据(算出
的数据接近随机值), 所以可以用这样的办法实现数字签名。

可以看出来，签名和签名验证的计算量是很大的，比如用RSA算法做签名，相当于对数据做
乘幂运算再做取模运算。当然，签名可以对数据的单向散列值做, 不过即使这样计算量也大。
可以看出签名和非对称加解密是可以用一个硬件加速器来做的。这里先做单向散列再做签名
是多个加解密算法级联使用的一个例子，在实际情况中这种情况很多，这对软件加解密框架
的设计提出了比较高的要求，关于这部分的设计实现可以参考Linux内核crypto子系统的
设计实现，同时该子系统也是c语言面向对象编程的一个很好的参考实例。

有很多针对签名的攻击, 其中利用签名解密信息的攻击很有意思。签名的本质是用私钥做
运算, 所做的运算如果数据是正好是加密数据，那么相当于做解密运算。攻击者如果手上
有一个别人发给签名者的加密信息(签名者对应的公钥加过密), 攻击者请求签名者给这段
信息签名, 如果签名，实际上签名者就被攻击者诱导做了解密运算。不过，一般情况下签名
者也不会对一段来历不明的信息做签名。

签名还有一个注意的地方是撤销签名，类比一下就是撕毁借条。但是数字签名无法撕毁，
办法就是再签一个说之前的签名无效了。

  1. 公钥证书

上面的各种办法其实还是没有办法解决非对称加解密里公钥配送的问题。

引入第三方机构办法公钥证书。

  1. 秘钥

上面各种加解密算法里多次提到秘钥。这里的秘钥其实就是一个巨大的数字。除了公钥
秘钥必须严格保密，因为加解密算法是公开的，秘钥的价值非常巨大，他的价值和明文是
相等的。

需要注意的是对称加解密里的秘钥配送还可以用秘钥配送去实现，比较经典的有DH算法。
直观的看，就是A和B预定几个数值(明文传送，C是可见的)，然后用公共的算法得到一个
相同的数值, C即使知道预定的值也无法计算出A和B的共享秘钥。

DH算法的一般步骤是:

秘钥管理里有秘钥作废比较有意思，秘钥作废之后要彻底销毁。这样做的原因是防止之前
的信息被解密，比如C长期截获并保存A和B之间的信息，如果C的到废弃的秘钥，他就可以
把之前的信息解密。

  1. 随机数

有些秘钥使用的是随机数，所以随机数是否是真随机这一点很关键。另外，并不是所有使用
随机数的地方都需要真随机数，但是加解密中使用的随机数一定要用真随机。单纯软件生
成的随机数一定是伪随机数。

和加解密类似，随机数的生成包括算法和种子，随机数生成算法类比加解密算法，是公开
的，种子类似秘钥，一定是私密的而且必须是真随机的。因为纯软件的种子一定不是随机
的，所以上面提到单纯软件生成的随机数一定是伪随机数。

Intel上硬件上已经提供了真随机数生成的指令。

  1. PGP
  1. SSL/TSL
  1. 区块链
  1. 硬件

SEC, HPRE, ZIP, RDE, TRNG, DMA