# 加密算法

  • 加密(encryption):指将一段明文数据(plaintext)根据加密算法转换成密文(ciphertext),从而隐藏其原本内容。
  • 解密(decryption):加密的逆过程,将密文还原成明文。
  • 密钥(key):加密算法中的可变输入参数。
    • 古典的加密技术,比如密码本,是将明文中的每个字母替换成另一个字母,从而得到密文。一旦被攻击者得知了加密原理,就容易将密文破解成明文。
    • 现代的加密技术,通常使用一些公开发表的加密算法,所有人都可阅读其原理。其安全性取决于两个方面:
      • 使用同一个加密算法加密同一段明文数据时,只要输入不同的密钥,就会生成不同的密文。因此,加密算法、密文可以公开,但拥有密钥的人才能将密文解读成明文。
      • 加密算法基于数学难题等因素,实现了高度安全性。
    • 密钥的位数越长,一般越难破译,不过加密和解密需要的时间也就越长。
    • 加密算法不能实现绝对的保密,比如攻击者可以花几百年时间暴力破解密文。因此加密的原则是:使破译密钥的时间比密钥的有效期久,或者使破译密钥的代价大于所保护信息的价值。

# 对称加密

:Symmetric Cryptography ,一种加密方案,特点是加密、解密时使用同一个密钥。

  • 基本流程:
    1. 通信双方协商一个密钥。比如发送方随机生成一个密钥,发给接收方。
    2. 发送方用密钥将消息加密成密文,然后发给接收方。
    3. 接收方收到密文,用密钥解密成明文。
  • 安全性主要取决于密钥是否泄漏。
    • 传输密文时,不担心被第三方窃听,因为第三方没有密钥,不能解密。
    • 一旦密钥泄露,第三方就可以解读当前传输的密文、历史传输的密文。
    • 为了减少密钥泄露时的损失,对称加密方案仅适用于一对一的通信,不适用于多对多的通信。
      • 假设 n 个用户相互通信。每两个用户之间,应该生成一个不同的密钥,n 个用户之间应该生成 n*(n-1)/2 个密钥。
      • 如果 n 个用户采用同一个密钥,则任意用户泄露了密钥,就会导致所有用户的密文被破解。
  • 常见的几种算法:
    • RC2
      • 1987 年,由麻省理工学院的教授 Ron Rivest 发明。他还发明了 RC4、RC5、RC6 对称加密算法,发明了 RSA 非对称加密算法,发明了 MD2、MD4、MD5 哈希算法。
      • 数据块长度为 64 位,密钥长度为 1~128 字节。
    • DES(Data Encryption Standard,数据加密标准)
      • 1977 年由美国政府发布。
      • 数据块长度为 64 位,密钥长度只有 56 位,容易被暴力破解。
    • AES(Advanced Encryption Standard,高级加密标准)
      • 2001 年由美国政府发布,旨在取代 DES 。
      • 数据块长度为 128 位,密钥长度有三种选择:128、192、256 位。

# 非对称加密

:Asymmetric Cryptography ,一种加密方案,特点是加密、解密时使用的密钥不同。其中一个是公钥(可以公开给所有人),另一个是私钥(必须私密保存)。

  • 安全性高于对称加密方案,但是算法更复杂,加密、解密速度更慢。

    • 对称加密时,通信双方需要协商一个相同的密钥,在协商过程中密钥可能被第三方窃听。
    • 非对称加密时,私钥不需要分享给对方,因此避免了在通信过程中私钥被窃听的风险。
  • 适合加密一对一、多对多的通信。常见用途:

    • 加密、解密数据
      • 单向加密通信的示例:
        1. 用户 A 生成一对用于加密的公钥、用于解密的私钥,然后将公钥发给其他人,也可以公布给所有人。
        2. 任何人都可以用公钥加密一条任意内容的消息,然后发送给用户 A 。该消息只能被 A 解密。
      • 双向加密通信的示例:
        1. 用户 A 、用户 B 分别创建一对公钥、私钥。然后将自己的公钥告诉对方,该过程称为互换公钥。
        2. 每次用户 A、用户 B 发送消息给对方时,就用对方的公钥加密,从而保证该消息只能被对方解密,第三方窃听了消息也不能解密。相当于建立一条专用的加密信道。
    • 数字签名(digital signature)
      • 示例:
        1. 用户 A 生成一对用于加密的私钥、用于解密的公钥,然后将公钥发给其他人,也可以公布给所有人。
        2. 用户 A 发布一条任意内容的消息。同时计算该消息的哈希值,用私钥加密之后发布,这称为数字签名,用途类似于现实世界的手写签名。
        3. 任何人都可以用公钥解密数字签名,读取其中的哈希值,从而验证该消息的内容没有被篡改,并且签署者是用户 A 。
      • 哈希算法只能校验数据一致性,而数字签名既能校验数据一致性,还有不可否认性(Non-Repudiation):用户 A 发布一条消息及其数字签名之后,不能否认自己发布了该消息,因为只有他有私钥来生成有效的数字签名。
      • MAC 算法、对称加密都没有不可否认性,安全性低于非对称加密。因为通信双方需要协商一个相同的加密密钥,一旦密钥泄露,第三方就可以冒名发送数据包。
    • 数字证书(digital certificate)
      • 数字签名存在一个安全问题:其他人如何检验一个公钥真的是用户 A 创建的?第三方可能冒充用户 A 发布一个公钥,再冒充用户 A 发布一条消息及其数字签名。
      • 常见的解决方案是,创建数字证书。示例:
        1. 建立一个权威机构(例如 PKI 架构下的 CA 机构),创建一对私钥、公钥,用于生成数字签名。
        2. 所有人事先下载权威机构的公钥(例如安装操作系统时内置其公钥)。因此每当权威机构发布一条消息及其数字签名,会被所有人信任。
        3. 用户 A 将自己的公钥发送给权威机构,请求作证。
        4. 权威机构发布一条消息及其数字签名,大意为 "用户 A 的公钥值是 xx" 。这称为数字证书,用途类似于现实世界的纸质证书。
        5. 用户 A 每次与其他人通信时,先发送数字证书,让对方相信 "用户 A 的公钥值是 xx" 。然后就可以发送任意内容的消息,并用该公钥生成数字签名。
  • 常见的几种算法:

    • RSA
      • 1977 年,由麻省理工学院的 Ron Rivest、Adi Shamir、Leonard Adleman 三人发布,命名取自他们姓氏的首字母。
      • RSA 是世界上第一个非对称加密算法,成为了非对称加密的行业标准,流行至今。
      • 支持加密、解密数据。支持数字签名。
      • 它的安全性是基于一个数学难题:找出两个大素数并计算乘积很容易,但对乘积进行因式分解,反推出两个大素数非常难。
      • RSA 的密钥长度有 1024、2048、4096 等。密钥越长,越难被破解,但也增加了计算耗时。
    • DSA(Digital Signature Algorithm ,数字签名算法)
      • 1991 年由美国政府发布。
      • 不支持加密、解密数据。专用于数字签名。
      • GPG(GNU Privacy Guard ,GnuPG)是一个命令行工具,支持用 RSA、DSA 算法生成密钥。
    • ECDSA(Elliptic Curve Digital Signature Algorithm ,椭圆曲线数字签名算法)
      • 1999 年发布,是 DSA 算法的一种变体。
      • 不支持加密、解密。专用于数字签名。
      • 它的安全性是基于一个数学难题:椭圆曲线离散对数问题。
      • ECDSA 比 RSA 算法更安全。256 位长度的 ECDSA 密钥,安全性相当于 3072 位长度的 RSA 密钥。
      • 例:
        • 1990 年代,Netscape 公司发布了 SSL 协议之后,通常用 RSA 算法生成 SSL 公钥、私钥。
        • 目前,一些网站改用 ECDSA 算法生成 SSL 公钥、私钥,这样能缩短密钥长度,从而稍微减少网络传输耗时、CPU 开销。

# AE

  • 在计算机通信领域使用加密算法时,即使保密了通信内容,也可能被破坏通信过程。假设主机 A 将一段数据加密之后发送给主机 B ,第三方不能解密数据,但可以:

    • 随机修改数据中的部分字节,导致主机 B 收到错误的数据。对策:校验数据一致性。
    • 将主机 A 发出的多段数据,打乱顺序之后发送给主机 B 。对策:每发送一段数据,包含一个递增的序列号。
    • 将主机 A 发出的某段数据,重复发送多次给主机 B ,称为重放攻击(replay attack)。对策:接收方根据序列号,去除重复的数据。
  • 2000 年代,人们开始研究 AE(Authenticated Encryption,认证加密)方案:在加密数据的同时,还支持校验数据一致性。

    • AE 方案有多种算法实现,基本逻辑为:
      • 加密过程:
        • 输入一段明文、一个密钥
        • 输出一段密文、一个验证码
      • 解密过程:
        • 输入一段密文、一个密钥、一个验证码
        • 输出一段明文
    • 这里的验证码通常采用 Message Authentication Code ,用于校验主体数据的一致性。而且第三方没有密钥,不能伪造这个验证码。
      • MAC 算法只负责对一段数据生成验证码,不在乎这段数据是否被加密。因此 MAC 算法、AE 算法有各自的用途,不一定组合使用。

# AEAD

  • AEAD(Authenticated Encryption with Associated Data)是 AE 方案的一种变体。

    • 特点:在加密时,允许额外输入一些关联数据。这些关联数据以明文公开,但受验证码保护,避免被篡改。
    • 因此,AEAD 方案集成了 AE 算法、MAC 算法的功能:加密、校验数据一致性、防伪验证码、关联数据。因此是目前最常用的加密方案。
  • AEAD 的用途举例:

    • AEAD 可用于 IPsec 协议,加密传输 IP 数据包的 payload ,并保护 src_ip、dst_ip 等头部关联数据,从而允许第三方路由转发该数据包,但不能篡改 payload 或头部。
    • AEAD 可用于 SSH 协议:
      • 用 ssh-keygen 命令生成 SSH 公钥、私钥时,默认采用 RSA 算法。
      • SSH 登录过程中,client 与 server 默认会协商一个 AEAD 算法。当 SSH 登录成功之后,双方会以 AEAD 算法建立 SSH 信道,加密传输数据。可执行 ssh -Q cipher 查看本机支持的 AEAD 算法。
  • AEAD 方案有多种算法实现,举例:

    • AES-CBC :不安全,已被弃用。
    • AES-CTR :不支持校验数据一致性,因此不推荐使用。
    • AES-GCM
      • 组合使用 AES-CTR 加密算法与 Galois MAC 消息验证码。
      • 是目前最常用的一种 AEAD 算法。
    • AES-CCM
      • 比 AES-GCM 速度更慢,因此较少使用。
    • ChaCha20-Poly1305
      • 组合使用 ChaCha20 流密码与 Poly1305 MAC 消息验证码。
      • 与 AES-GCM 的安全性差不多,但速度更快。
      • AES 算法属于分组密码(block cipher):将数据以 block 为单位分组,每次加密一个 block ,每个 block 大小为几十字节。
      • ChaCha20 属于流密码(stream cipher):每次加密 1 bit 或 1 byte 。

# 量子加密

:Quantum Cryptography ,基于量子纠缠进行加密通信。

  • 量子具有不确定性、测量坍缩、不可克隆的特性,能保证通信过程不被窃听,实现绝对的加密通信。

# 后量子加密

:Post-Quantum Cryptography ,是指能避免被量子计算机暴力破解的加密算法。

  • 传统的加密算法主要基于一些非常难解决的数学难题,比如素数因式分解问题、离散对数问题、椭圆曲线离散对数问题。
    • 使用传统计算机几乎不可能暴力破解传统加密算法,因为穷举的计算量太大,耗时超过上千年。
    • 使用量子计算机,并针对一种数学难题设计合适的量子算法,可能容易暴力破解一些传统加密算法。
      • 例如:使用量子算法 Shor 可以在几天内破解 2048 位的 RSA 密钥。
  • 目前,大部分对称加密算法、哈希算法依然难以被量子计算机破解,只是破解速度稍快,增加密码长度便可有效防御,使得破解的服务器成本、时间成本远远高于保密价值。
  • 后量子加密算法应该具备以下特点:
    • 安全:能抵抗传统计算机、量子计算机的暴力破解。
    • 加密、解密的速度快
    • 通信开销低:密码长度不超过 10 KB 。
    • 与传统密码算法的使用流程相同,从而方便替换。