密码学基础

1 密码

  • 加密encrypt、解密decrypt、明文plaintext、密文ciphertext、密码破译cryptanalysis、密钥key
  • 对称密码symmetric cryptography
  • 公钥密码public-key cryptography
  • 混合密码系统hybrid cryptography

2 历史上的密码

  • 凯撒密码–平移密码
  • 简单替换密码–频率分析破译
  • Enigma

3 对称密码

  • 编码操作：转为二进制序列
  • 异或XOR：
    • 加密：明文A 异或 密钥B = 密文C
    • 解密：密文C 异或 密钥B = 明文A
  • 一次性密码本：绝对无法破译但效率低的密码，无法解决密钥配送问题
  • DES：Data Encryption Standard
    • 分组密码
    • Feistel网络，轮
    • 选择明文攻击CPA
      • 差分分析：改变一部分明文并分析密文如何随之改变
      • 线性分析：将明文和密文的一些对应比特位进行XOR并计算其结果为零的概率
    • 三重DES，包括DES-EDE2和DES-EDE3
  • AES密码：advanced encryption standard
    • Rijndael
    • 竞争实现标准化

4 分组密码模式

模式 名称 优点 缺点 备注
ECB 电子密码本模式 简单
快速
支持并行运算		 明文中的重复排列会反映在密文中
通过删除、替换密文分组可以对明文进行
对包含某些比特错误的密文进行解密时，对应的分组会出错
不能抵御重放攻击		 不应使用
CBC 密文分组链接模式 明文的重复排列不会反映在密文中
支持并行计算（仅解密）
能够解密任意密文分组		 对包含某些错误比特的密文进行解密时，第—个分组的全部比特以及后一个分组的相应比特会出错，
加密不支持并行计算		 CRYPTREC推荐
《实用密码学》推荐
CFB 密文反馈模式 不需要填充
支持并行运算（仅解密）
能够解密任意密文分组		 加密不支持并行计算
对包含某些错误比特的密文进行解密时，第一个分组的全部比特以及后一个分组的相应比特会出错
不能抵御重放攻击		 CRYPTREC推荐
OFB 输出反馈模式 不需要填充
可事先进行加密解密的准备
加密解密使用相同的结构
对包含某些错误比特的密文进行解密时，只有明文中相应的比特会出错		 不支持并行运算
主动攻击者反转密文分组中的某些比特时，明文分组中相应比特也会反转		 CRYPTREC推荐
CTR 计数器模式 不需要填充
可事先进行加密解密的准备
加密解密使用相同的结构
对包含某些错误比特的密文进行解密时，只有明文中相应的比特会出错
支持加解密并行运算		 主动攻击者反转密文分组中的某些比特时，明文分组中相应比特也会反转 CRYPTREC推荐
《实用密码学》推荐

5 公钥密码

  • 密钥配送问题解决方法：
    • 事先共享
    • 密钥分配中心KDC
    • 密钥交换
    • 公钥密码
  • 接收者将公钥发送给发送者，发送者使用公钥加密后将密文传递给接收者，接收者使用对应的私钥进行解密
  • 公钥密码存在的问题，公钥认证问题，中间人攻击：窃听者给发送者错误的公钥并获取明文，再将明文篡改后使用正确的公钥加密返回给接收者从而实现攻击
  • RSA算法
    $$
    密文=明文^E mod N,(E,N)是公钥\
    明文=密文^D mod N,(D,N)是私钥
    $$
    • 算法：生成密钥对，准备两个很大的质数p和q
      $$
      N=pq\
      L=lcm(p-1,q-1),lcm表示求最小公倍数\
      1<E<L,gcd(E,L) = 1,gcd表示求最大公约数（使用辗转相除法）\
      1<D<L,E      DmodL=1
      $$
  • RSA攻击方法：一旦发现了对大整数进行质因数分解的高效算法， RSA 就能够被破译
    • 中间人攻击
    • 选择密文攻击–RSA-OAEP
  • 其他公钥密码
    • EIGamal
    • Rabin
    • ECC，椭圆曲线加密

6 混合密码系统

  • 背景：
    • 公钥密码不足：计算效率低，但可以解决密钥配送问题
    • 对称密码不足：密钥配送麻烦，但是速度快
  • 混合密码系统
    • 概念：使用公钥密码保护对称密码密钥
    • 加密过程：明文使用对称密码密钥加密，对称密码密钥使用公钥加密，两者发送给接收者
    • 解密过程：对称密码密钥使用私钥解密，密文使用对称密码密钥解密

7 单向散列函数

  • 文件、密文是否被篡改：完整性、一致性，integrity
  • 单向散列函数有一个输入和输出，输入称为消息，输出称为散列值
    • 根据任意长度的消息计算出固定长度的散列值，无论消息的长度如何，散列值的大小应当不变
    • 能够快速计算出散列值
    • 消息不同散列值也不同，理论上消息变化一个比特，散列值应当有明显变化以确定消息是否被篡改
    • 两个不同的消息产生同一个散列值的情况称为碰撞(collision )，难以发现碰撞的性质称为抗碰撞性(collision resistance)
    • 单向散列函数必须确保要找到和该条消息具有相同散列值的另外一条消息是非常困难的。这一性质称为弱抗碰撞性。单向散列函数都必须具备弱抗碰撞性。
    • 强抗碰撞性。所谓强抗碰撞性，是指要找到散列值相同的两条不同的消息是非常困难的这一性质。在这里，散列值可以是任意值。
    • 单向散列函数必须具备单向性(one-way )。单向性指的是无法通过散列值反算出消息的性质。
  • 单向散列函数又称为哈希函数
  • 实际应用
    • 检测软件是否被篡改
    • 基于口令的加密
    • 消息认证码
    • 数字签名
    • 伪随机数生成器
    • 一次性口令
  • 常见的单向散列函数
    • MD4、MD5，强对抗性已被攻破
    • SHA-1，不安全
    • SHA-256、SHA-384、SHA-521（SHA-2）
    • RIPEMD-160
    • SHA-3：Keccak算法
  • 对单向散列函数的攻击
    • 暴力破解，针对弱抗碰撞性
    • 先准备两个散列值相同的不同消息，针对强抗碰撞性
  • 单向散列函数无法解决的问题
    • 无法验证伪装，只能识别是否篡改
    • 使用认证技术可以识破伪装，认证技术包括消息验证码和数字签名

8 消息认证码

  • 概述：可以判断消息是否被篡改，并且发送者是否被伪装
  • 消息认证码，Message Authentication Code，MAC，是一种确认完整性并进行认证的技术
    • 消息认证码的输入包括任意长度的消息和一个发送者与接收者之间共享的密钥，它可以输出固定长度的数据，这个数据称为MAC 值。
    • 要计算MAC 必须持有共享密钥，没有共享密钥的人就无法计算MAC 值，消息认证码正是利用这一性质来完成认证的。消息认证码是一种与密钥相关联的单向散列函数。
  • 使用过程：发送者将密钥和消息计算得到消息认证码MAC，将消息和认证码发送给接收者，接收者根据消息和密钥计算MAC并与发送者提供的MAC进行比对，如果不一致则认证失败
  • 消息认证码需要解决共享密钥的配送问题
  • 常用消息认证码技术
    • SWIFT
    • IPsec
    • SSL/TLS
  • 实现手段：
    • SHA-2、HMAC等单向散列函数
    • 分组密码AES
  • 认证加密AEAD，结合对称密码和消息认证码，同时满足CIA即，机密性、完整性和认证
  • Encrypt-then-MAC，先加密再计算密文的MAC，除此之外还有Encrypt-and-MAC (将明文用对称密码加密，并对明文计算MAC 值）和MAC-then-Encrypt (先计算明文的MAC 值，然后将明文和MAC 值同时用对称密码加密）。
  • HMAC，使用单向散列函数构造消息认证码的方法
  • 对消息认证码的攻击
    • 重放攻击：攻击者将窃取的MAC值和密文进行重新发送
      • 抵御方法：序号、时间戳、接收者提前发送nonce随机数并需要发送者将随机数包含在明文中
    • 密钥推测攻击
      • 根据单向散列值推测出对称密钥
  • 消息认证码无法解决的问题
    • 第三方证明，因为第三方不知道密钥所以无法验证，需要签名技术
    • 防止否认，发送者可以否认发送，接收者无法证明是否发送

9 数字签名

数字签名digital signature，是一种将相当于现实世界中的盖章、签字的功能在计算机世界中进行实现的技术。使用数字签名可以识别篡和伪装，还可以防止否认。

  • 主要行为：
    • 发送者Alice生成消息签名，根据消息内容计算数字签名的值
    • 接收者Bob或者第三方Victor验证消息签，检查该消息的签名是否真的属于A lice ,
  • Alice 使用“签名密钥”来生成消息的签名，而Bob 和Victor 则使用“验证密钥”来验证消息的签名。数字签名对签名密钥和验证密钥进行了区分，使用验证密钥是无法生成签名的。这一点非常重要。此外，签名密钥只能由签名的人持有，而验证密钥则是任何需要验证签名的人都可以持有。数字签名的实现原理与公钥密码原理相反。
私钥 公钥
公钥密码 接收者解密时使用 发送者加密使用
数字签名 签名者生成签名时使用（发送者） 验证者验证签名时使用（接收者）
谁持有 接收者/签名者个人持有 任何人持有
  • 用公钥加密所得到的密文，只能用与该公钥配对的私钥才能解密；同样地，用私钥加密所得到的密文，也只能用与该私钥配对的公钥才能解密。也就是说，如果用某个公钥成功解密了密文，那么就能够证明这段密文是用与该公钥配对的私钥进行加密所得到的。
  • Alice可以用私钥解密任何人用相对应的公钥加密的密文，相反，任何人都可以用公钥验证Alice用对应的私钥生成的签名。
  • 数字签名的方法：
    • 直接对消息签名
    • 对消息的单向散列值签名
      • Alice 用单向散列函数计算消息的散列值。
      • Alice 用自己的私钥对散列值进行加密。
      • Alice 将消息（未加密）和签名发送给Bob 。
      • Bob 用Alice 的公钥对收到的签名进行解密。
      • Bob 将签名解密后得到的散列值与Al ice 直接发送的消息的散列值进行对比。
  • 数字签名不是为了保证Alice消息的机密性，而是确保其他人能认证该消息来自于Alice。无论签名被复制多少份，都能确定消息的来源。如果有人篡改签名和消息，至少会造成签名验证失败。
  • 应用实例：
    • 安全信息公告
    • 软件下载
    • 对公钥进行签名，确认公钥的合法性
  • 数字签名实现：RSA算法，ECDSA算法基于椭圆曲线密码
  • 对数字签名的攻击
    • 中间人攻击，需要对公钥进行签名
    • 利用数字签名攻击公钥密码，将密文让私钥持有者签名从而获得明文
    • 潜在伪造
  • 数字签名无法解决的问题：公钥认证问题

10 证书

证书Public-Key Certificate, PKC，为公钥加上数字签名。认证机构就是能够认定“公钥确实属千此入”并能够生成数字签名的个人或者组织。认证机构中有国际性组织和政府所设立的组织，也有通过提供认证服务来盈利的一般企业，此外个人也可以成立认证机构。Bob在认证机构Trent注册自己的公钥，Alice使用经认证的公钥加密消息给Bob。对证书的攻击：

  • 在公钥注册前攻击

  • 注册相似人名

  • 窃取认证机构的私钥

  • 伪装成认证机构攻击

    11 密钥

  • 密钥长度决定密钥空间的大小

  • 密钥与明文是等价的

  • 密钥分为用于机密性的密钥和用于认证的密钥，会话密钥（一次性）和主密钥，加密内容的密钥和加密密钥的密钥

  • 密钥生成：

    • 用随机数生成密钥，密码学用途的伪随机数生成器必须是专门针对密码学用途而设计的，必须具备不可预测性
    • 用口令（password）生成密钥

  • 配送密钥：事先共享，密钥分配中心，公钥密码，Diffie-Hellman密钥交换

  • 更新密钥：（参考《信息安全工程》Anderson著）用当前密钥的散列值作为下一个密钥。

  • 密钥保存：将密钥加密后保存KEK

  • Diffie-Hellman 密钥交换：基于有限域的离散对数难以计算所实现

    • Alic给Bob一个大质数P和生成元G
    • Alice和Bob各在1~P-2的区间内生成一个随机数并保密
    • Alic发送$G^A mod P$给Bob
    • Bob发送$G^B mod P$给Alice
    • Alice计算$(G^B mod P)^A mod P$作为密钥
    • Bob计算$(G^A mod P)^B mod P$作为密钥，与Alice相同
    • 生成元的计算方法：
      • 设13为P，则任取G在0-P-1内，A在1~P-1的范围内，生成元$G^A mod P$应当与A一一对应的关系
      • 例如2的1次方到12次方取13的模与1-12一一对应因此2是13的生成元

  • 基于口令的密码Password Based Encryption

    • 生成KEK，用口令和伪随机生成的盐计算单向散列函数值生成KEK
    • 生成会话密钥并加密，用KEK加密，加密后保存盐和加密后的会话密钥，并丢弃KEK（可根据口令和盐重新生成）
    • 加密消息

  • 盐：盐是由伪随机数生成器生成的随机数，在生成密钥(KEK ) 时会和口令一起被输入单向散列函数。

    • 盐用来抵御字典攻击

  • 拉伸：使用多次单向散列函数计算KEK，增加攻击者的成本

12 随机数

  • 应用场景：
    • 生成密钥和密钥对
    • 在CBC、CFB、OFB中生成初始化向量
    • 生成nonce
    • 生成盐
  • 随机数的分类
    • 随机性–弱伪随机数
      • 不存在统计学偏差
    • 不可预测性–强伪随机数
      • 在攻击者知道之前数据的情况下依旧无法预测下一个随机数
      • 不可预测性是通过使用其他的密码技术来实现
    • 不可重现性–真随机数
      • 计算机所有能产生的随机数会存在周期，就可以重现
      • 不可重现的随机数需要从不可重现的物理现象中获取信息
  • 密码学中的随机数需要具备不可预测性，只具备随机性的随机数是不够的，”杂乱无章也可以被看穿“
  • 伪随机数生成器：从外部输入种子seed进入内部状态初始化
    • 线性同余法–不具备不可预测性
      • 将当前的伪随机数值乘以A 再加上C, 然后将除以M 得到的余数作为下一个伪随机数。
      • 可以根据内部状态推测下一个伪随机数，且具备周期性
      • C语言的rand函数也是基于线性同余法
    • 单向散列函数法
      • 用种子初始化内部状态计数器
      • 根据计数器值计算散列值作为随机数
      • 计数值++
      • 继续输出随机数
      • 由于攻击者无法根据散列值推算出计数器的状态，因此无法预测下一个随机数，单向散列函数的单向性是支撑伪随机数生成器不可预测性的基础。
    • 密码法
      • 将单向散列函数法中的函数计算过程改为密钥加密过程，密码的机密性是支撑伪随机数生成器不可预测性的基础。
    • ANSI X9.17：PGP密码软件的基础
  • 对伪随机数生成器的攻击：
    • 对种子进行攻击
    • 对随机数池进行攻击

PGP

Pretty Good Privacy密码软件

SSL/TLS

Secure Socket Layer和Transport Layer Security，用于安全通信的密码通信方法。