SM9代理环签名方案

摘要

条件：SM9数字签名算法

代理环签名方案：

六步骤：系统初始化、密钥提取、代理委托、代理验证、签名和验证

SM9数字签名之前看的一篇有详细讲解签名流程做的笔记

密钥生成中心使用用户标识计算用户的密钥,原始签名者使用已知信息计算代理授权,然后将代理授权委托给代理签名者。代理签名者验证委托的真实性后,通过签名步骤产生代理环签名,产生的签名可以使用验证算法验证。

优势之处：实现了签名权力的委托，同时通过环签名的匿名性保护签名者的隐私，并且在随机预言模型证明其具有适应性选择消息攻击厦大不可伪造性。

引言部分

1、1996年，MAMBO[3]等人提出代理签名的概念，允许原始签名者将自己的签名权委托给代理签名者，由代理签名者代替原始签名者进行签名，得到的签名具有同样的效用，实现了签名权的委托与撤销。

2、基于身份的密码体制（Identity-Based Cryptography，IBC）

  • 核心理念：IBC 允许用户直接将**自己的唯一标识（Identifier, ID）**作为公钥使用。例如，用户的电子邮箱地址、IP地址或身份证号等都可以直接作为加密或验签所需的公钥。
  • 私钥生成机制：在这种体制下，用户的私钥并非由用户自己生成，而是由一个可信的第三方机构——**密钥生成中心（Key Generation Center, KGC）**负责计算生成，并以安全的方式发送给用户。

基础必备

困难问题假设

  1. 离散对数问题(Discrete logarithm Problem,DLP).给定椭圆曲线上任意两个点$P$、$Q$给定$aP=Q$,在多项式时间内$a$是不可解的
  2. $q-SDH$问题(q-Strong Diiffie-Hellman Problem).给定双线性映射 $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ 与 $q+2$ 个元素$ \bigl(P,\ Q,\ [s]Q,\ [s^2]Q,\ \dots,\ [s^q]Q\bigr) \in \mathbb{G}_1 \times \mathbb{G}_2^{,q+1} $其中 $s \in \mathbb{Z}_N^*$ 未知，找到一组数$ \Bigl(B,\ \frac{1}{B+s} \cdot P\Bigr) $是困难的。$B\in \mathbb{Z}_p^* $

环签名

给定一个环$L={L_1,L_2,…,L_n}$ ，环中用户i的公私钥对为 ($p{k_i},s{k_i}$),（$i\in{1,2,…,n}$） 。

假设$L_K(1<=k<=n)$是签名者。一个环签名体制包含环签名产生算法$Ring-Sign$和环签名验证算法$Ring-Verify$。

1）$Ring-Sign$签名算法 ：输入待签名的消息$m$、环中

所有用户的公钥 $L_K(1<=k<=n)$、签名者的私钥$sk_i$，该

算法的输出是签名者$L_k$对消息$m$的环签名$θ$。

功能：无法追踪到具体某一个公钥持有者的签名

2）$Ring-Verify$验证算法 ：输入是待验证的消息

签名对($m,θ$)、环中所有成员的公钥 ；当验证通过时，

输出为1 ；否则，输出为0。

SM9

签名流程

Setup（系统建立）

  • KGC 选择双线性群 ($BP = (G_1, G_2, G_T, e, N))$，生成元 $(P_1 \in G_1, P_2 \in G_2)$
  • 选主私钥 ($\alpha \in [1, N-1]$)，计算主公钥 ($P_{pub}$ =$ \alpha P_2 \in G_2$)
  • 计算 (g = e($P_1$, $P_{pub}$) $\in$ $G_T$)
  • 输出：主公钥 (mpk = ($BP, P_1, P_2, P_{pub}, g, H_1, H_2, hid$))，主私钥 (msk =$ \alpha$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
安全参数 λ
     │
     ▼
选择 BN 曲线 → BP = (G₁, G₂, G_T, e, N)
     │
     ▼
选生成元 P₂ ∈ G₂ ──ψ──▶ P₁ = ψ(P₂) ∈ G₁
     │
     ▼
随机选 α ∈ [1, N-1] ────▶ P_pub = α·P₂ ∈ G₂
     │                        │
     │              e(P₁, P_pub) = e(P₁, P₂)^α
     │                        │
     │                        ▼
     │                   g = e(P₁, P_pub) ∈ G_T
     │
     ▼
选定 H₁, H₂（基于 SM3）, hid（1 字节）
     │
     ▼
 mpk = (BP, P₁, P₂, P_pub, g, H₁, H₂, hid)  ← 公开
 msk = α                                    ← 绝密

KeyGen（用户私钥生成）

  • 给定用户标识 ($ID$)，KGC 计算：
    • ($t_1 = H_1(ID \parallel hid, N) + \alpha \pmod N$)
    • ($t_2 = \alpha \cdot t_1^{-1} \pmod N$)
    • ($sk_{ID}$ = $t_2 $$\cdot $$P_1$)（群 ($G_1$) 中的元素）
  • 关键设计：私钥 ($sk_{ID} = \frac{\alpha}{H_1(ID)+\alpha} \cdot P_1$)，把身份标识”嵌入”到了私钥中

Sign（签名）

  • 选随机数 (r)，计算 ($w = g^r$)（把 (g) 作为”一次性基底”）
  • 计算哈希 ($h = H_2(M \parallel w, N$))
  • 计算 ($\ell = r - h \pmod N$)，若 ($\ell = 0$) 则重新选 (r)
  • 签名 ($\sigma = (h, S = \ell \cdot sk_{ID}$))
  • 核心逻辑：($S = (r-h) \cdot \frac{\alpha}{H_1(ID)+\alpha} \cdot P_1$)，把随机数、消息哈希、身份私钥三者绑定

Verify（验证）

  • 计算 ($t = g^{h}$)，
  • 计算 ($h_1$ = $H_1(ID \parallel hid, N)$)，($P = h_1 P_2 + P_{pub} = (h_1 + \alpha)P_2$)
  • 计算 ($u = e(S, P)$)，($w’ = u \cdot t$)
  • 检查 ($H_2(M \parallel w’, N) = h$)

验证核心逻辑：

$
\begin{aligned}
u &= e(S, P) = e((r-h)sk_{ID}, (h_1+\alpha)P_2) \
&= e((r-h)\frac{\alpha}{h_1+\alpha}P_1, (h_1+\alpha)P_2) = e(P_1, P_2)^{(r-h)\alpha}
\end{aligned}
$

$
w’ = u \cdot g^h = e(P_1, P_2)^{(r-h)\alpha} \cdot e(P_1, \alpha P_2)^h = e(P_1, P_2)^{\alpha r} = g^r = w
$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
用户身份 ID（即公钥）
      ↓
KGC 生成私钥: sk_ID = α/(H1(ID)+α) · P₁
      ↓
┌── 签名场景 ──────────────────────────┐
│ 签名者用 sk_ID 对消息 M 签名          │
│ 验证者用 ID（公钥）+ 主公钥 验证      │
└──────────────────────────────────────┘
      ↓
┌── 加密场景 ──────────────────────────┐
│ 发送者用 ID 封装密钥 K                │
│ 接收者用 sk_ID 解封装得到 K           │
│ 用 K 对称加密实际消息                 │
└──────────────────────────────────────┘

基于SM9的代理环签名方案

$ID_i$表示用户$i$的身份标识

$ID$和$\widetilde{ID}$分别表示委托代理的身份集和其子集。

假设委托代理中代理签名者的身份数量为$n$($n$>=2)

$ID$的子集$\widetilde{ID}$大小为$z$(z>=2)环内成员可以通过预计算$g=e(P_1,P_{pub})$来提高整体方案效率

流程：

系统初始化

$KGC$输入安全参数$l$—>安全参数$para$和系统主密钥（$s,P_{pub}$）

  1. KGC产生随机数$s\in{1,…,N}$为主私钥
  2. 计算$G2$中的元素$P_{pub}=[s]\cdot P2$作为主公钥，主密钥对为$s,P_{pub}$
  3. 保存$s$,公开$P_{pub}$和系统参数$Para={e,G_1,G_2,P_1,P_2,P_{pub},H_1,H_2}$

即$Setup(l)->(para,(s,P_{pub}))$

密钥提取

KGC计算并生成用户密钥。

输入四个对应参数计算出用户$i$的密钥，并将用户私钥$d_i$用安全方式发送给身份为$ID_i$的用户

$Extract(Para,s,P_{pub},ID_i)->d_i$

  1. KGC选择一个字节表示的私钥生成函数标识符$hid$

  2. 在有限域$Z_N$上计算$B_i=H_1(ID_i||hid,N)$，$B_i$需要转化为整数

  3. 整数$t_1=B_i+s$,

    if $t_1=0$,重新计算主私钥s

    else $t_2=s\cdot t_1^{-1}$

  4. 用户私钥$d_i=[t_2]\cdot P_1->d_i=[s.(B_i+s)^{-1}\cdot P_1]$

  5. 标识$ID_i$用户公钥可由任意用户计算生成$Q_i=[B_i]\cdot P_1+P_{pub}$

代理委托

身份标识为$ID_A$的原始签名者决定将签名权委托给具有身份集合$ID$的委托代理

输入：$Para,P_{pub},ID_A,ID$(身份集合)、身份为$ID_A$的原始签名者的私钥$d_A$和期限的授权信息$R$

输出：一个授权$ε$

$ProxyDelegation(Para,P_{pub},ID_A,ID,d_A,R)->ε$

  1. 原始签名者A选择随机数$r\in Z_N^*$

  2. 计算群$G_T$中元素$ω_1 = g^r$(ω1转为比特串)

    ($g = e$($P_1$, $P_{pub}$) $\in$ $G_T$)

  3. 计算群$G1$中元素$\sigma=r\cdot d_A$，$U=\sum_{i\neq A}^nB_i\cdot d_A$(把所有代理签名者的 $B_i$ 值聚合到 $d_A$里)

  4. 计算整数$h_1=H_2(\omega_1||\sigma,R),l_1=(r-h_1)modN$.

    if $l=0$ 重新选择随机数$r$

    else 计算$S_1=l_1\cdot d_A$

  5. 公开$h_1,U,\omega_1$,将$\varepsilon=(\sigma,S_1)$作为签名委托授权用安全的方式发送给代理签名者

代理验证

输入：$Para,P_{pub}，ID_A,ID,R,\varepsilon$,如果$\varepsilon$是一个有效授权输出1否则0

$VerifyDelegation(Para,P_{pub},ID_A,ID,R,\varepsilon)->{0,1}$

利用双线性对验证

代理验证 = 把授权凭证 $ε = (σ, S₁)$ 当作 SM9 签名来验证

原始签名者 A 用自己私钥 $d_A $对$ (ω₁, σ, R)$ 签名 → 得到$ S₁$

代理签名者 $π $收到后：
用 A 的公钥对应$G_2 $形式$(B_A P₂ + P_{pub}) $+ 主公钥参数 $g$
→ 验证这个”授权签名”是否合法
→ 合法就接受授权，进入签名步骤

签名

$Sign(Para,L,\widetilde{ID},\varepsilon，ID_π ,D_π ,M)->θ$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
步骤(1): r₁,r₂,...,r_n ──▶ R₁,R₂,...,R_n  (R_A = S₁)
                               │
                               ▼
步骤(2): {r_i} + {B_i} $──▶ α (环匿名)
         σ + {B_i}     ──▶ β (授权绑定)
                               │
         r_π ──▶ ω₂ = g^{r_π}  │     ω₁ (来自A的委托)
                               │        │
                               ▼        ▼        
步骤(4):              ω₃ = α · β · ω₁ · ω₂
                               │
                               ▼
步骤(5):     h₂ = H₂(M ∥ ω₃)
             l₂ = r_π - h₂
             S = l₂ · d_π    (π用自己的SM9私钥)
             u = e(S·B_π, P₂+P_pub)
                               │
                               ▼
步骤(6):    θ = (h₂, R₁,...,R_n, u)

  1. $π $为环里每个成员（除了$ A$）生成一个随机点 $R_i$。但 $R_A $不随机——它直接复用代理委托中的 $S_1$。这实现了”绑定”：签名必须跟 A 的授权 S₁ 关联

  2. $\alpha = e\left(\sum_{i\neq A}^{n} r_i \cdot P_1,;; \sum_{i\neq A}^{n} B_i \cdot P_2 + P_{pub}\right)$

    $\beta = \sigma \cdot e\left(\sum_{i\neq A}^{n} B_i \cdot P_1,;; P_2\right)$

    量 含义
    α 把所有代理签名者的随机因子 $r_i$ 绑在一起，与代理签名者群体的”集体公钥”做双线性对。集体公钥 = ($\sum B_i P_2 + P_{pub}$)（把所有人的身份哈希 $B_i $聚合到一个 $G_2$ 公钥上）
    β 把授权 token σ 和所有代理签名者的身份哈希$ B_i $绑在一起。$σ$ 来自 A 的委托（$σ = r · d_A$），确保签名与 A 的授权不可分割

  3. $π $自己的随机承诺 ω₂

    $ω₂=g^{r_π }$

  4. $\boxed{\omega_3 = \alpha \cdot \beta \cdot \omega_1 \cdot \omega_2}$

    因子 来源 含义
    α 步骤 (2) 环的匿名性承诺
    β 步骤 (2) 代理授权的绑定
    ω₁ 代理委托（原始签名者 A 发出的） A 的原始承诺（g^r）
    ω₂ 步骤 (3) π 的个人承诺（g^{r_π}

  5. 签名核心

    $h_2=H_2(M||ω_3)$

    $l_2=r_π-h_2(mod N)$

    if $l_2=0$重选随机数

    $S=l_2\cdot d_π$

    $u=e(S\cdot B_π,P_2+P_{pub})$

  6. $\boxed{\theta = (h_2,; R_1, R_2, \ldots, R_n,; u)}$

1
2
3
4
5
6
7
8
  SM9 标准签名                代理环签名（本文）
┌──────────────┐      ┌──────────────────────────┐
│ w = g^r      │      │ ω₃ = α·β·ω₁·ω₂           │  ← 承诺更复杂
│ h = H₂(M∥w)  │      │ h₂ = H₂(M∥ω₃)            │  ← 哈希逻辑一致
│ l = r - h    │      │ l₂ = r_π - h₂             │  ← 用自己的 r_π
│ S = l·d      │      │ S = l₂·d_π               │  ← 用自己的私钥
│ 签名 = (h,S) │      │ θ = (h₂,R₁..R_n,u)       │  ← 多了环+授权
└──────────────┘      └──────────────────────────┘