数字签名

# 简介

带密钥的消息摘要算法。与手写签名类似，起到了抗否认的作用。手写签名针对纸质文件内容确认，数字签名对数据进行摘要处理。如果经过手写签名的文件被修改，该文件无效。同理，经过数字签名的数据，通过验证签名操作辨别该数据是否被修改。如Windows操作系统的产品密钥

数字签名算法包含了公钥和私钥，是非对称加密算法与消息摘要算法的结合体，近似看成是附加了公钥和私钥的消息摘要算法

发送方将发送的数据进行签名处理，发送携带签名的数据。接受方可以验证该签名与数据是否相符来确认数据完整性 用于签名的相关信息私有，用于验证签名的相关信息公有，且必须成对出现。遵循“私钥签名。公钥验证”的签名/验证方式

数字签名主要包括RSA、DSA和ECDSA算法。RSA源于质因数分解，DSA及ECDSA源于离散对数

# RSA

RSA算法不仅是非对称加密算法的经典，也是数字签名算法的经典。

• 分类：RSA签名长度与密钥长度相同

  • MD系列：密钥长度1024
    • MD2withRSA
    • MD5withRSA
  • SHA系列：SHA1密钥1024，其余2048
    • SHA1withRSA
    • SHA224withRSA
    • SHA256withRSA
    • SHA384withRSA
    • SHA512withRSA

• 代码

  • Java API

  // 签名
  public static byte[] sign(byte[] data, byte[] privateKey) throws Exception {
      // 将传入私钥转换成可用私钥
      PKCS8EncodedKeySpec pkcs8KeysSpec = new PKCS8EncodedKeySpce(privateKey);
      KeyFactory keyFactory = KeyFactory.getInstance("RSA");  // 密钥是RSA算法的密钥
      PrivateKey priKey = keyFactory.generatePrivate(pkcs8KeysSpec);
  
      // 签名
      Signature signature = Signature.getInstance("MD5withRSA");  // 指明签名算法
      signature.initSign(priKey);  // 初始化传入私钥
      signature.update(data);  // 传入待签名数据
      return signature.sign();  // 生成并返回签名
  }
  
  // 验签
  public static byte[] verify(byte[] data, byte[] publicKey byte[] sign) throws Exception {
      // 将传入公钥转换成可用公钥
      PKCS8EncodedKeySpec pkcs8KeysSpec = new PKCS8EncodedKeySpce(publicKey);
      KeyFactory keyFactory = KeyFactory.getInstance("RSA");  // 密钥是RSA算法的密钥
      PrivateKey pubKey = keyFactory.generatePrivate(pkcs8KeysSpec);
  
      // 验证签名
      Signature signature = Signature.getInstance("MD5withRSA");  // 指明签名算法
      signature.initSign(pubKey);  // 初始化传入公钥
      signature.update(data);  // 传入签名数据
      return signature.verify();  // 返回验证结果布尔值
  }
  

# DSA

DSA (Digital Signature Algorithm 数字签名算法) 仅可进行数字签名，使用DSA算法的数字证书无法进行加密通信，而RSA不仅可进行数字签名，还可进行加解密

DSA可认为是RSA的简化版，仅支持SHA系列算法。密钥长度默认1024，范围512 - 1024（64倍数）。签名长度与密钥长度无关

• SHA1withDSA
• SHA224withDSA
• SHA256withDSA
• SHA384withDSA
• SHA512withDSA

# 实现流程

流程参考wiki-数字签名算法open in new window。其中 为信息编码散列所用的函数，即SHA系列函数

• 参数选择

  • 选择长度为 N 比特的质数 q （N即为模数长度，q为小素数因子）
  • 选择长度为 L 比特的质数 p （L即为密钥长度），使得 ，其中 k 为常数。FIPS（联邦信息处理标准） 186-4 规定 (L,N) 必须为 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一种
  • 从 2 至 p-2 随机选择 h，一般可选 2，在下一步求原根 g 中进行模幂（先进行幂运算后在求模）运算时效率较高
  • 计算基数（该基数需要为p的原根） 。若 ，则取 h 为它值进行计算

• 用户密钥：每个用户独自计算密钥组合

  • 选择私钥： 从 1 至 q-2 随机选择私钥 x
  • 计算公钥： ，并发布

• 签名

  • 随机选取 ， 与 互质
  • 计算 ，若 ，则取 为它值进行计算
  • 计算 ，若 ，则取 为它值进行计算。其中 为模反元素， 是待签名内容的散列值
  • 签名为

• 验签

  • 验证 且
  • 计算
  • 计算
  • 计算
  • 计算
  • 时，签名有效

# 原理

• 数论基础：费马小定理 - 若 是一整数， 是一质数， 不是 的倍数，则
• 根据签名可知
• 式(1) 两边同乘
• 根据验签可知
• 将计算公钥的公式 代入 式(3) 得到
• 由于 作为 的指数，计算时使用 。因此可将 式(2) 代入 式(4) 对指数进行化简
• 根据验签 ，代入 式(5) 得
• 此时 式(6) 与签名时 的定义一致

# ECDSA

ECDSA (Elliptic Curve Digital Signature Algorithm 椭圆曲线数字签名算法) 是ECC与DSA的结合。速度快、强度高、签名短。用途有 以太坊数字加密货币，Windows操作系统的产品密钥等

常见ECDSA算法有：NONEwithECDSA、RIPEMD160withECDSA、SHA系列withECDSA

# 密钥长度

与一般的圆锥曲线算法一致，密钥长度大约为安全等级位数的2倍

# 涉及到的数学内容

• 加密中使用的椭圆曲线： 为非标准椭圆圆锥曲线，与椭圆函数 不同（只是与其相关才命名为椭圆曲线），不能互相转换

• 加法规则

  
  • 封闭性：如果 和 是曲线上的点，其加法定义为 和 所形成的直线，和曲线E交点 的相反点(关于x轴对称点) 即为它们的和，也是曲线上的点
    • 求坐标：计算直线斜率 ，而后将直线方程代入得到坐标公式
  • 存在无穷远点（point at infinity）：存在一个特殊的点 ，满足 。无穷远点：平行线相交与无穷远点
  • 存在逆元素（Inverse element）：对于任意曲线上的点 ，存在一个点 ，使得 。情况3中的 为 的逆元，即x轴对称点。几何理解：根据加分定义， 与 的连线与对称线平行（重合），交点即为

• 标量乘法：在椭圆曲线中，标量乘法 是指将点 与标量 相乘，表示 在曲线上的重复加法，根据封闭性， 结果依然在曲线上

  • 是通过将 与自己加 次得到的
    • 如果 ，那么 ，即 自身相加三次
    • 计算 时反复相加即可
  • 坐标计算： 时，即倍点。如 情况2 中的 ，切线交点为 ，结果为。使用求导计算切线斜率 后，将 代入坐标公式即可
  • 已知标量 和点 求出 较为简单。已知结果点 和基点 求标量 是难题，即 椭圆曲线离散对数问题。加密中 即为公钥，标量 为私钥

# 实现流程

• 公私钥产生

  • 是定义的椭圆曲线
  • 是椭圆曲线上的一个基点（生成元点）。此参数公开
  • 是生成元点 的阶。此参数公开
    • 阶： 的最小整数
    • 做标量乘法时不断得到新的点。直到标量为 时结果为无穷远点
    • 此时根据公式 ，得到 ，即得到了之前得到过的点，由此进入了循环
    • 因此， 可以确定 的重复加法生成的点集的大小
  • 私钥 是一个随机选择的数，且
  • 公钥 是通过 计算得到的（私钥 与生成元点 的乘积）

• 签名

  • 随机选取 生成点集中的一个点
    • 随机选择整数 。其中 是临时值，必须保密，且每次签名时都要重新生成，以保证签名的安全性
    • 计算点 ，得到坐标
  • 计算 。 如果 , 重新选点集中的点（重新选择 ）
  • 计算 . 如果 , 重新选点集中的点（重新选择 ）。此处计算消息 的摘要值，并加入私钥
    • 是 的模 的逆元，即满足
  • 签名为

• 验签

  • 判断 与 是否都在 内（由于 ）
  • 计算
  • 计算
  • 计算 。如果得到无穷远点，验证失败
  • 判断 是否成立。成立则验证成功，否则验证失败

# 原理

• 根据验签时计算出的点
• 根据公钥定义 代入 式(1)
• 将 代入 式(2)
• 将 的定义 代入 式(3)
• 由于 ，所以若验签成功时， 即为签名时的 ，即
• 根据 的定义 ，因此