本文大纲

简介
RSA
DSA
- 实现流程
- 原理
ECDSA

Leopold

文章

分类

标签

github.com/SayNop

gitee.com/WhenTimeGoesBy

fur999immer@gmail.com

数字签名

2024-05-18

CryptographyCryptographyRSADSAECDSA

简介

带密钥的消息摘要算法。与手写签名类似，起到了抗否认的作用。手写签名针对纸质文件内容确认，数字签名对数据进行摘要处理。如果经过手写签名的文件被修改，该文件无效。同理，经过数字签名的数据，通过验证签名操作辨别该数据是否被修改。如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。其中 $H$ 为信息编码散列所用的函数，即SHA系列函数

参数选择
- 选择长度为 N 比特的质数 q （N即为模数长度，q为小素数因子）
- 选择长度为 L 比特的质数 p （L即为密钥长度），使得 $p - 1 = k q$ ，其中 k 为常数。FIPS（联邦信息处理标准） 186-4 规定 (L,N) 必须为 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一种
- 从 2 至 p-2 随机选择 h，一般可选 2，在下一步求原根 g 中进行模幂（先进行幂运算后在求模）运算时效率较高
- 计算基数（该基数需要为p的原根） $g = h^{\frac{p - 1}{q}} m o d p$ 。若 $g = 1$ ，则取 h 为它值进行计算
用户密钥：每个用户独自计算密钥组合
- 选择私钥：从 1 至 q-2 随机选择私钥 x
- 计算公钥： $y = g^{x} \mod p$ ，并发布
签名
- 随机选取 $1 < k < q - 1$ ， $k$ 与 $p - 1$ 互质
- 计算 $r = (g^{k} mod p) mod q$ ，若 $r = 0$ ，则取 $k$ 为它值进行计算
- 计算 $s = (k^{- 1} (H (m) + x \cdot r)) mod q$ ，若 $s = 0$ ，则取 $k$ 为它值进行计算。其中 $k^{- 1}$ 为模反元素， $H (m)$ 是待签名内容的散列值
- 签名为 $(r, s)$
验签
- 验证 $0 < r < q$ 且 $0 < s < q$
- 计算 $w = s^{- 1} mod q$
- 计算 $u_{1} = H (m) \cdot w mod q$
- 计算 $u_{2} = r \cdot w mod q$
- 计算 $v = (g^{u_{1}} y^{u_{2}} mod p) mod q$
- $v = r$ 时，签名有效

原理

数论基础：费马小定理 - 若 $a$ 是一整数， $p$ 是一质数， $a$ 不是 $p$ 的倍数，则 $a^{p - 1} \equiv 1 (\mod p)$
根据签名可知 $\begin{matrix} (1) & s = (k^{- 1} (H (m) + x \cdot r)) mod q \end{matrix}$
式(1) 两边同乘 $k$ $\begin{matrix} (2) & k \cdot s = (H (m) + x \cdot r) mod q \end{matrix}$
根据验签可知 $\begin{matrix} (3) & v = (g^{H (m) \cdot w} y^{r \cdot w} mod p) mod q \end{matrix}$
将计算公钥的公式 $y = g^{x} \mod p$ 代入式(3) 得到 $\begin{aligned} v & = (g^{H (m) \cdot w m o d q} g^{x \cdot r \cdot w m o d q} mod p) mod q \\ (4) & = (g^{w (H (m) + x \cdot r) m o d q} mod p) mod q \end{aligned}$
由于 $u 1$ $u 2$ 作为 $g$ 的指数，计算时使用 $m o d q$ 。因此可将式(2) 代入式(4) 对指数进行化简 $\begin{matrix} (5) & v = (g^{w \cdot k \cdot s m o d q} mod p) mod q \end{matrix}$
根据验签 $w = s^{- 1} mod q$ ，代入式(5) 得 $\begin{matrix} (6) & v = (g^{k} mod p) mod q \end{matrix}$
此时式(6) 与签名时 $r$ 的定义一致

ECDSA

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

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

密钥长度

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

涉及到的数学内容

加密中使用的椭圆曲线： $y^{2} = x^{3} + a x + b$ 为非标准椭圆圆锥曲线，与椭圆函数 $\frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} = 1$ 不同（只是与其相关才命名为椭圆曲线），不能互相转换
加法规则
- 封闭性：如果 $P$ 和 $Q$ 是曲线上的点，其加法定义为 $P$ 和 $Q$ 所形成的直线，和曲线E交点 $R$ 的相反点(关于x轴对称点) $P + Q = - R$ 即为它们的和，也是曲线上的点 $\begin{matrix} P + Q = - R \\ (x_{p}, y_{p}) + (x_{q}, y_{q}) = (x_{r}, y_{r}) \end{matrix}$
  - 求坐标：计算直线斜率 $λ$ ，而后将直线方程代入得到坐标公式 $λ = \frac{y_{q} - y_{p}}{x_{q} - x_{p}}$ $\begin{array}{l} x_{r} = λ^{2} - x_{p} - x_{q} \\ y_{r} = λ (x_{p} - x_{r}) - y_{p} \end{array}$
- 存在无穷远点（point at infinity）：存在一个特殊的点 $O$ ，满足 $P + O = P$ 。无穷远点：平行线相交与无穷远点
- 存在逆元素（Inverse element）：对于任意曲线上的点 $P$ ，存在一个点 $- P$ ，使得 $P + (- P) = O$ 。情况3中的 $Q$ 为 $P$ 的逆元，即x轴对称点。几何理解：根据加分定义， $P$ 与 $Q$ 的连线与对称线平行（重合），交点即为 $O$
标量乘法：在椭圆曲线中，标量乘法 $k G$ 是指将点 $G$ 与标量 $k$ 相乘，表示 $G$ 在曲线上的重复加法，根据封闭性， $K = k G$ 结果依然在曲线上
- $k G$ 是通过将 $G$ 与自己加 $k - 1$ 次得到的
  - 如果 $k = 3$ ，那么 $k G = G + G + G$ ，即 $G$ 自身相加三次
  - 计算 $k > 2$ 时反复相加即可
- 坐标计算： $k = 2$ 时，即倍点。如情况2 中的 $Q$ ，切线交点为 $P$ ，结果为 $- P$ 。使用求导计算切线斜率 $λ$ 后，将 $λ$ 代入坐标公式即可 $λ = \frac{3 x_{p}^{2} + a}{2 y_{p}}$
- 已知标量 $k$ 和点 $G$ 求出 $k G$ 较为简单。已知结果点 $K$ 和基点 $G$ 求标量 $k$ 是难题，即椭圆曲线离散对数问题。加密中 $K$ 即为公钥，标量 $k$ 为私钥

实现流程

公私钥产生
- $E$ 是定义的椭圆曲线
- $G$ 是椭圆曲线上的一个基点（生成元点）。此参数公开
- $n$ 是生成元点 $G$ 的阶。此参数公开
  - 阶： $n G = O$ 的最小整数 $n$
  - $G$ 做标量乘法时不断得到新的点。直到标量为 $n$ 时结果为无穷远点 $O$
  - 此时根据公式 $P + O = P$ ，得到 $(n + 1) G = G$ ，即得到了之前得到过的点，由此进入了循环
  - 因此， $n$ 可以确定 $G$ 的重复加法生成的点集的大小
- 私钥 $d$ 是一个随机选择的数，且 $1 \leq d \leq n - 1$
- 公钥 $Q$ 是通过 $Q = d G$ 计算得到的（私钥 $d$ 与生成元点 $G$ 的乘积）
签名
- 随机选取 $G$ 生成点集中的一个点
  - 随机选择整数 $1 \leq k \leq n$ 。其中 $k$ 是临时值，必须保密，且每次签名时都要重新生成，以保证签名的安全性
  - 计算点 $K = k G$ ，得到坐标 $(x_{K}, y_{K})$
- 计算 $r = x_{K} mod n$ 。如果 $r = 0$ , 重新选点集中的点（重新选择 $k$ ）
- 计算 $s = k^{- 1} (H (m) + r \cdot d) mod n$ . 如果 $s = 0$ , 重新选点集中的点（重新选择 $k$ ）。此处计算消息 $m$ 的摘要值，并加入私钥
  - $k^{- 1}$ 是 $k$ 的模 $n$ 的逆元，即满足 $k^{- 1} \cdot k \equiv 1 m o d n$
- 签名为 $(r, s)$
验签
- 判断 $r$ 与 $s$ 是否都在 $[1, n - 1]$ 内（由于 $m o d n$ ）
- 计算 $u_{1} = H (m) \cdot s^{- 1} m o d n$
- 计算 $u_{2} = r \cdot s^{- 1} m o d n$
- 计算 $(x_{1}, y_{1}) = u_{1} \cdot G + u_{2} \cdot Q_{A}$ 。如果得到无穷远点，验证失败
- 判断 $r \equiv x_{1} (\mod n)$ 是否成立。成立则验证成功，否则验证失败

原理

根据验签时计算出的点 $C$ $\begin{matrix} (1) & C = u_{1} \cdot G + u_{2} \cdot Q_{A} \end{matrix}$
根据公钥定义 $Q = d G$ 代入式(1) $\begin{aligned} C & = u_{1} \cdot G + u_{2} d \cdot G \\ (2) & = (u_{1} + u_{2} d) \cdot G \end{aligned}$
将 $u 1$ $u 2$ 代入式(2) $\begin{aligned} C & = (H (m) s^{- 1} + r \cdot d s^{- 1}) \cdot G \\ (3) & = (H (m) + r \cdot d) s^{- 1} \cdot G \end{aligned}$
将 $s$ 的定义代入式(3) $\begin{aligned} C & = (H (m) + r \cdot d) (k^{- 1} (H (m) + r \cdot d))^{- 1} \cdot G \\ = (H (m) + r \cdot d) (H (m) + r \cdot d)^{- 1} (k^{- 1})^{- 1} \cdot G \\ (4) & = k G \end{aligned}$
由于 $K = k G$ ，所以若验签成功时， $C$ 即为签名时的 $K$ ，即 $x_{K} = x_{1}$
根据 $r$ 的定义 $r = x_{K} mod n$ ，因此 $r \equiv x_{1} (\mod n)$

数字签名

# 简介

# RSA

# DSA

# 实现流程

# 原理

# ECDSA

# 密钥长度

# 涉及到的数学内容

# 实现流程

# 原理

简介

RSA

DSA

实现流程

原理

ECDSA

密钥长度

涉及到的数学内容

实现流程

原理