密码学常见算法

on technology
  • 流程
    • 加密：明文变为密文
    • 解密：密文变为明文
    • 发送者加密信息，发送给接受者；接受者解密信息，读取信息；窃听者无法获取信息
  • 类型
    • 对称(common-key cryptography, symmetric cryptography)：加密/解密使用同一个密钥
    • 非对称(public-key cryptography, asymmetric cryptography)：加密/解密使用不同密钥
    • 混合以上两种
    • 单向散列函数：根据同时发布的软件与散列值验证软件未被篡改
    • 消息认证码：验证消息是否来自所期望的通信对象
    • 数字签名：与现实生活中的盖章，签字类似。
  • 应用
    • 防窃听 -> 对称/非对称加密
    • 防篡改 -> 单向散列, 消息认证码, 数字签名
    • 防中间人 -> 消息认证码，数字签名
    • 防否认 -> 数字签名
  • cryptography && steganography
    • cryptography 隐藏的是内容
    • steganography 隐藏的是消息本身（例如数字水印）
  • security by obscurity 是一种通过保密密码算法本身来确保安全性的行为。stupid!
    • 密码算法就算是私密的，也不一定安全
    • 不存在永久私密的密码算法，早晚有一天会被扒皮
    • 开发高强度的密码算法很困难
    • 低强度的密码 = 完全没有加密
  • 一些简单的加密
    • Caesar cipher: 按照字母表平移。可以暴力破解。
    • Simple substitution cipher：建立字母表的另一种一一对应关系。可以通过频率分析来破译。
    • Enigma: 使用每日密码加密通信密码，用密钥加密密钥（Key Encrypting Key)加密信息。
      • 弱点1. 通信密码输入两次有特征
      • 弱点2. 通信密码不随机会有特征
      • 弱点3. 每日密码的私密性很难
    • 密钥与算法分开。算法可以公开，密钥不能公开。密文的私密性在于密钥的私密性。
  • XOR(exclusive or, 异或)特性：相同的数进行XOR运算结果为0。 跟加密解密类似：A XOR key = B, B XOR key = A。
  • Vernam cipher(one-time pad): 即使被破解了也不知道是否是正确的（密钥空间大的可以产生很多规则字符串），所以是无法被暴力破解的。
    • 特性: unconditionally secure, theoretically unbreakable
    • 不实用：
      • 没有安全的渠道可以发送密钥
      • 没有安全的方法保存密钥
      • 密钥完全不能重用，否则一旦丢失密钥，过去的消息也能被解密
      • 密钥需与消息等长，同步也是大问题
      • 计算机是只能产生伪随机数作为密钥
  • DES：将 64bit 的明文加密为 64bit 的密文
    • 密钥长度64， 其中8个用于纠错，有效载荷是56.
    • 明文被分组用于加密
    • 使用的基本结构叫 Feistel network.
      • 数据总共经过 16 round 循环
      • 在一轮中产生一个局部密钥：subkey；应用 round function: 数据分为左右两半，右侧数据与subkey 生成加密的比特序列，再与左侧进行 XOR。最后将输入的右测直接变为输出的右测。
      • 每两轮对调左右测。
      • 倒着应用 16 round 的subkey 可以解开密文。
      • 不管使用多复杂的轮函数，结果都能被解开。
  • Triple-DES: DES 应用三次
    • DES-EDE1: 三个密钥独立：有168个密钥长度，密钥空间是DES的3次方
    • DES-EDE2: k1=k3,k1!=k2: 有112个密钥重读
    • DES-EDE3: k1=k2=k3: 等价于des.

    • 密文 = EK3(DK2(EK1(平文)))

    • 平文 = DK1(EK2(DK3(密文)))

    • 加密时，第二步使用解密函数，是因为可以兼容 DES
    • Wikipedia 提到了中途相遇攻击？？？会削弱安全性（EDE1->112bit, EDE2->80bit)
  • AES: 应用了 Rijndael 对称加密算法，这个算法使用了 SPN Structure
    • 分组为 128bit(16byte), 每个 byte 进行 subbytes 处理
    • subtypes 是以每个字节的值为索引从一张有256个值的替换表(S-Box)中查找（其实就是 Simple substitution cypher 的 256 值版本）
    • 接下来进行一次 ShiftRows，（有规律的乱序位移）
    • 接下来进行一次 MixColumns: 对一组4字节的值进行比特运算，变为另一个4字节的值
    • 最后进行一次 AddRoundKey: 每个字节与 round key 进行 xor.
    • 总共进行 10 ~ 14 round
    • 解密使用反向反序运算: AddRoundKey, InvMixColumns，InvShiftRows， InvSubByptes (不像 DES 可以用同一种结构加密解密）
    • 理论上存在数学方法破译？？
  • 对称加密的结论：
    • 超过 512 bit 的密钥总长没有意义，因为空间已经足够大（2^512), 算法又会慢下来。
    • DES 已经很容易暴力破解
    • TDES 是兼容版本，今后会被 AES 取代
    • AES(Rijndael) 目前足够安全
    • 当年 AES 征集的最终候选算法也都足够安全，也许可以用来做候选算法
    • AES
    • AES
    • AES

  • 分组：因为 DES 和 AES 都只能加密定长明文，所以需要分组。分组模式必须足够好，否则会有特征泄漏。

  • 分组密码模式
    • stream cipher: 对数据流连续处理（比如one-time pad)

    • block cipher: 每次处理定长的一块数据的一类密码算法

    • ECB(electronic codebook mode): 明文分组逐个加密变为密文分组
      • 缺点：相同的明文分组会产生相同的密文分组，产生了特征
      • 攻击：攻击者可以对调顺序，操纵明文（比如对调转账人和到帐人的数据包，删除密文分组，复制密文分组），除非使用了消息验证码。
    • CBC(cipher block chaining mode)：前一个密文分组与当前明文分组内容 XOR 后再加密得到当前密文分组。事先需要准备一个随机的初始化向量IV。
      • IV 随机，意味着同一个密钥对同一个明文加密，也能得到不一样的密文
      • 一个分组数据出错，也只影响两个分组；但如果一个分组长度变化，会导致后续所有都会分组出错。
      • 无法做并行计算
      • 攻击：比特反转：解密时，如果能反转IV的bit，则明文对应的bit也会被反转，所以可以操纵解密出来的第一个明文分组。
      • 对密文直接操纵比较困难，因为后续的都会被影响
    • CFB(cipher feedback mode)：前一个密文分组送入密码算法计算，得到的内容与当前明文做XOR，得到当前密文分组。需要随机的IV。
      • 有点像弱化版的one-time pad, 因为在流程上明文与密文之间只有一次xor. 但加密的 key stream 是伪随机数。在实现上，CFB 可以做到逐比特加密。
      • 攻击：重放攻击：用以前截获的数据混入新截获的数据。解密的数据只有替换的第一个分组会出错（因为从替换的第二个分组开始，进行xor运算的密钥是替换的第一个分组，是正确的）。
    • OFB(output feedback mode): 密码算法的输出反馈到密码算法的输入。需要随机的IV
      • 有点像 CFB, 明文与密文之间也是隔着一次 XOR 运算。CFB 的 key 是通过密文分组计算得到的，OFB 是通过上一轮的加密IV计算得到的。
      • 由于 OFB XOR 需要的 key stream 可以实现计算，与明文分组无关。所以可以提前准备好 key stream. 运算速度可以很快。另外生成key stream 与 xor 也可以并行计算。
      • 看上去好像不会遭受重放攻击？？但是会遭受比特反转攻击。
      • 算法缺点：假设反馈前的密文和反馈后的密文刚好是一样的，那么之后的反馈就无效了：之后所有的密文就是单一的了。
    • CTR(counter mode)：对计数器加密生成 key stream, 与明文做 xor 运算
      • 计数器的初始值是由 nonce(8bit) + 分组序号(8bit) 组成，可保证每组使用的密钥流也是不一样的
      • OFB 是加密的输出反馈到输入，CTR 则是计数器的值用作输入
      • 支持并行
      • 错误比特的密文只会影响明文中相对应的比特，不会被放大（和OFB一样）
      • 能实现进行加密解密的准备
      • 加密解密的结构一样
      • OFB 的算法缺点不存在：因为 nonce+序列 可以保证不会有一样的密文用于 XOR 计算。
  • 分组算法的结论
    • 用 CBC 和 CTR
  • key distribution problem
    • 事先共享密钥：最大的问题在于人数多时会组合爆炸
    • 密钥分配中心：单点故障
    • Diffie-Hellman 密钥交换
      • A/B 双方任意一个生成两个质数 P, G
      • A 生成随机数 X
      • B 生成随机数 Y
      • A 将 G^X % P 发给 B
      • B 将 G^Y % P 发给 A
      • A 计算 (G^Y % P)^X % P = G^(X * Y) % P 为共享的私钥
      • B 计算 (G^X % P)^Y % P = G^(X * Y) % P 为共享的私钥
      • 以上的发送环节即使被窃听了也不会被人计算出来，原因是根据 G^X % P 计算 X 的算法叫 finite group 的离散对数问题，目前还未出现有效解法
    • 公钥密码！任何人都能通过公钥加密，而只有拥有私钥的人才能解密。通过公钥密码可以解决密码配送问题
      • 发送者只需要公钥；接受者只需要私钥；私钥不能被窃听者获取；公钥被获取也没关系
      • 公钥和私钥是一一对应的，同时生成的，统称为 key pair.
      • 要解决的问题：公钥认证与处理速度。
  • RSA
    • 加密：密文 = (明文 ^ E) % N
    • 公钥 = (E, N)
    • 解密：明文 = （密文 ^ D) % N
    • 私钥 = (D, N)
    • 生成密钥对：
      • N: 先准备两个很大的质数p, q. 太大了算不完，太小了不安全。512bit 很合适。N = p * q
      • L: 最小公倍数(least common multiple), L = lcm(p-1, q-1)
      • E: 需要通过伪随机生成器生成 E 的候选数，它必须满足条件 1 < E < L, gcd(E, L) = 1. 啊很多质数都能达到这个条件。
      • D: 1 < D < L, E * D % L = 1
    • 中间人攻击：拦截公钥，替换公钥，让加密方使用被替换后的假公钥加密数据。结论：仅有公钥密码本身是无法防御中间人攻击的。方案：证书。
  • ElGamal
    • 利用 mod N 下求离散对数的困难度设计公钥算法。
    • 缺点：密文长度是明文的两倍
  • Rabin
    • 利用 mod N 下求平方根的困难度设计公钥算法。
    • 与质因数分解困难度一样
  • ECC(Elliptic Curve Cryptosystems)
    • 椭圆曲线特定点进行特殊的乘法运算的逆运算很困难
    • 所需的密钥长度比 RSA 短
  • 一些点
    • 非对称加密与对称加密的机密性没有可比性。它是由密钥长度决定的
    • 相同长度的密钥长度，对称加密比非对称加密抵御暴力破解的能力更强
    • 由于效率，非对称不太可能取代对称
    • 加密解密生成keypair都不需要做质因数分解，只有密码破译者才需要做。
    • 对称加密通过转换明文为复杂性是来保证机密性，公钥加密则通过数学难题来保证。
  • 混合加密
    • 通过伪随机数生成器生成对称密码加密中使用的会话密钥
    • 基于对称加密算法，使用会话密钥加密消息
    • 基于非对称加密算法，使用公钥加密会话密钥
    • 组合加密消息与加密会话密钥为密文
    • 应用：PGP