Chapter 9-Public Key and RSA

主要介绍了公钥密码学和RSA算法。公钥密码学是一种非对称加密技术，其中加密和解密使用不同的密钥。RSA算法是公钥密码学中一种广泛应用的算法。

Chapter 9-Public Key and RSA

• Public-Key Cryptography
  • intro
    • 实现依赖于数论（大整数难分解）
    • 离散对数难解
    • 使用两个密钥
      • 公钥
        • 任何人都知道，用于加密和验证签名
      • 私钥
        • 只有消息接收者知道，用于解密和创建签名
      • 不能从公钥确定私钥
  • 解决两个问题
    • Key distribution
      • 如何在不需要信任一个密钥分配中心(Key Distribution Center,KDC)的情况下安全的进行通信
    • digital signatures
      • 如何验证一条消息来自于生成的发送者，并且内容完整无缺
  • example
    • RSA
      • 子主题
  • process
    • encryption with public key
    • encryption with private key
  • Application
    • en/de cryption
      • provide secrecy
    • digital signatures
      • provide authentication
    • key exchange
      • of session keys
  • Requirement
    • one-way function
      • 
    • trap-door one-way function
    • 这两个相关密钥任何一个都可以用于加密另一个用于解密
    • 这两个密钥数学上相关，但是从一个密钥推导另一个密钥是计算上不切实际的
  • security
    • exhaustive search theoretically possible
    • but keys used are genetic(通用的) and supper-polynomial can always choose a bigger instance, unlike block ciphers
    • 加解密很容易，破解很难
    • 难题足够难
    • 更慢
• RSA
  • En/De cryption
    • sender encrypt a message M
      • 
    • owner decrypt the ciphertext C
      • 
    • 注意： M进行加密钱必须小于模数n，如果消息大于模数n那么它需要备份快
  • Key Setup
    • 1.生成密钥对
      • 每个用户通过选择两个大素数p和q来生成一堆公钥/私钥
    • 2.计算模数n
      • n=p*q
    • 3.计算欧拉函数
      • φ(n) = (p-1)(q-1)
        • 简化剩余系得个数
    • 4.选择公钥指数e
      • 随机选择一个加密密钥e
        • 1 < e < φ(n)
        • e和φ(n)互质
    • 5.计算私钥指数d
      • 解决方程e * d ≡ 1 (mod φ(n))
      • i.e. d是e模φ(n)的乘法逆元
    • 6.发布公钥
      • PU = {e, n}
        • 任何人都可以用他加密信息
    • 7.发布私钥
      • PR = {d, n}
        • 仅用户自己知道用来解密信息
  • security
    • the cost of factoring large numbers 大整数难分解
  • 
  • 有效性
    • 基于欧拉定理
    • RSA中欧拉定理得应用
      • 
    • 为什么解密过程可以还原M
  • Exponentiation
    • Square and Multiply Algorithm(平方-乘算法)