Hyper の 个人博客

1 预备知识

1.1 困难问题

ECDL 问题
椭圆曲线上的循环加法群 $G$ 由无穷远点 $O$ 和曲线 $E$ 上的其他点组成，$P$、$q$ 为生成元和阶。给定群 $G$ 中已知两个点 $P$ 和 $Q$，且 $Q = xP$，其中 $x \in \mathbb{Z}_q^*$。敌手 $A$ 在 PPT 时间内计算 $x$ 是困难的，即解决 ECDL 问题的概率 $\epsilon$ 是可忽略的。
* 注：然而，本文方案实际并未使用到椭圆曲线，故基于的困难问题应为离散对数问题
RSA 问题
一个 PPT 敌手 $A$ 尝试计算一个整数 $u$，使得 $u^e \equiv c \pmod{n}$，其中 $(n,e,c)$ 是已知的，且 $n$ 是两个不同奇素数 $p$ 和 $q$ 的乘积，满足最大公约数 $\gcd(e, (p - 1)(q - 1)) = 1$。$A$ 解决 RSA 问题的概率 $\epsilon_{\text{RSA}}^A = \Pr[A(n, e, c) \to u]$ 是可忽略的。
变种 RSA 问题
一个 PPT 敌手 $A$ 尝试计算两个整数 $(w,u)$，使得 $u^e \equiv a w^z \pmod{n}$。其中 $(n, e, a, z)$ 是已知的，且 $n$ 是两个不同奇素数 $p$ 和 $q$ 的乘积，满足 $\gcd(e, (p - 1)(q - 1)) = 1$。$A$ 解决 VRSA 问题的概率 $\epsilon_{\text{VRSA}}^A = \Pr[A(n, e, a, z) \to (w, u)]$ 是可忽略的。

1.2 Shamir 秘密共享

Shamir 秘密共享方案通过将一个秘密值 $s$ 拆分为 $n$ 个片段 $s_1, ..., s_n$​，每位参与者 $P_1, ..., P_n$ 分别持有一个片段。核心原理是：当群体中至少有 $t$ 个成员时，能够恢复秘密值 $s$；否则无法恢复。

• 秘密分发

  • 随机选择 $s \in Z_q^*$ 作为共享的秘密值，随机选取一个满足 $f(0) = s$ 的 $t-1$ 次多项式 $f(x)= s + \sum_{j=1}^{t-1} a_jx^j \ mod \ q$
  • 随机选择 $\alpha_i \in Z_q^*$​，计算 $f(\alpha_i) = s_i$，其中 $i \in \{1, ..., n\}$
  • 将第 $i$ 个片段 $\{\alpha_i, f(\alpha_i) \}$ 分发给对应的参与者 $P_i$

• 秘密恢复：对包含至少 $t$ 个参与者的群体 $S$，这些参与者通过以下等式恢复秘密值 $s=f(\alpha_i)$，其中$\Delta_{\alpha_i,S}(x)$ 为拉格朗日基本多项式：

  $$f(x) = \sum_{P_i \in S} \Delta_{\alpha_i,S}(x) f(\alpha_i)$$

  $$\Delta_{\alpha_i,S}(x) = \prod_{P_k \in S, k \neq i} \frac{x - \alpha_k}{\alpha_i - \alpha_k} \mod q$$

1.3 汉明距离

汉明距离（Hamming Distance）最早用于数据传输纠错码，是两个字符串或向量中对应位置位不同的数目。给定两个等长的字符串或向量 $x = (x_1, x_2, \dots, x_n)$ 和 $y = (y_1, y_2, \dots, y_n)$，其汉明距离 $d_H(x, y)$ 定义为：

$$d_H (x, y) = \sum_{i=1}^{n} \delta (x_i, y_i), \ \text {其中} \ \delta (x_i, y_i) = \begin {cases} 1 & \text {当 } x_i \neq y_i \\ 0 & \text {当 } x_i = y_i \end {cases}$$

2 认证方案流程

• $Setup$：系统初始化，由 TA 执行，输入安全参数 $λ$，TA 与 KGC 共同输出系统主私钥 $s$，并发布系统参数 $Para$​

• $Registration \ and \ Pseudo$-$identity \ Generation$：注册与假名生成，每辆车辆 $V_j$ 向 TA 申请注册，TA 运行本算法输入车辆的生物特征 $bio_j$​，输出生物身份 $BID_j$。随后车辆为 $V_j$ 创建假名 $PID_j$​，并通过安全信道发送给车辆

• $Partial \ Private \ Key \ Extract$：部分密钥生成，由 KGC 执行，输入 $V_j$ 的假名 $PID_j$​、系统主密钥 $s$ 和系统参数 $Para$​，输出 $V_j$​ 的部分私钥 $PS_{PID}$

• $Set \ Secret \ Value$：设置秘密值，由 $V_j$ 执行，输入其假名 $PID_j$ 和系统参数 $Para$​，生成其秘密值 $x_{PID}$

• $Set \ Private \ Key$：设置私钥，由 $V_j$ 执行，输入假名 $PID_j$​、部分私钥 $PS_{PID}$、系统参数 $Para$​ 和秘密值 $x_{PID}$，生成其完整私钥 $SK_{PID}$

• $Set \ Public \ Key$：设置公钥，由 $V_j$ 执行，给定车辆 $V_j$​ 的秘密值 $x_{PID_j}$​，生成 $V_j$ 的公钥 $PK_{PID_j}$

• $Sign$：签名，由 $V_j$ 执行，输入 $V_j$ 的假名 $PID_j$、系统参数 $Para$、消息 $m$ 和完整私钥 $SK_{PID}$，输出与 $PID_j$ 和消息 $m$ 关联的签名 $\sigma$

• $Verify$：验证，给定车辆 $V_j$ 的假名 $PID_j$​、系统参数 $Para$、公钥 $PK_{PID_j}$​、消息 $m$ 和签名 $\sigma$，返回 $1$ 或 $0$

2.1 系统初始化

在此阶段，TA 生成系统主密钥并公布参数列表：

• 给定安全参数 $\lambda$，随机选取大素数 $p$ 和 $q$，计算 $ϕ(N)=(p−1)(q−1)$ 和 $N=pq$，并将 $p$、$q$ 和 $ϕ(N)$ 保密

• 另选一组大素数 $p'$ 和 $q'$，使得 $p' \neq p、q' \neq q$、且 $q' \mid (p'-1)$。同时，选取 $g \in \mathbb{Z}^*_{p'}$ 且 $g \neq 1$，满足 $g^{q'} \equiv 1 \pmod{p'}$

• TA 随机选取一个整数 $e$，满足 $1 < e < \phi(N)$ 且 $\text{gcd}(e, \phi(N)) = 1$。TA 根据方程 $e \cdot s \equiv 1 \pmod{\phi(N)}$ 计算出主私钥 $s$

• 定义一个安全的对称密钥加密方案 $\text{Enc}_\kappa(\cdot)/\text{Dec}_\kappa(\cdot)$，$\kappa$ 为对称密钥

• TA 与 KGC 选择三个密码学哈希函数：

  • $H_1:\{0, 1\}^* \to\mathbb{Z}^*_{N}$
  • $H_2 : \{0, 1\}^* \to \{0, 1\}^{|N|/4}$
  • $H_3 : \{0, 1\}^* \times \{0, 1\}^* \times \mathbb{Z}^*_{p'} \times \{0, 1\}^\pi \to \mathbb{Z}^*_{q'}$

• 公开参数列表 $Para=(p',q',N,e,g,H_1,H_2,H_3)$

2.2 注册和假名生成

车辆在进入车联网前需要向 TA 注册：

• $V_j$ 通过安全信道向 TA 提供其真实的生物特征 $bio$

• TA 生成生物特征标识 $BID_j = \text{IdGen}(bio)$，$\text{IdGen}(\cdot)$ 是一种身份提取函数

• TA 为 $V_j$ 创建假名 $PID_j = \text{Enc}_\kappa(BID_j \| n_{PID}) \| T_j$，其中 $n_{PID}$ 是请求的假名数量，$T_j$ 为假名有效期

• TA 通过安全信道向 $V_j$ 发送 $\{BID_j, PID_j\}$

这一步还考虑了恶意车辆冒充 RSU 的情况，作者声称的解决方案是：

• 定义另一个安全签名方案，由 TA 将方案交给 RSU

• RSU 定期广播自己的公钥、私钥签名后的真实身份、验签方法 $Ver_{pk}(.)$

• 车辆用 RSU 公钥验签；若验证失败，表明为假冒 RSU，向 TA 上报

• TA 追溯此假冒 RSU 的真实身份

但这样做实际上是把系统的安全性建立在这个签名方案的保密性上，这并不能解决实际问题；而如果方案公开，对于一个正确的签名方案，伪装成 RSU 的恶意车辆总能自行选取一个 $RID'$，对 $RID'$ 生成一个合法签名并通过其他车辆的验证。

2.3 完整密钥生成

KGC 获取车辆 $V_j$ 假名 $PID_j$，生物特征相关属性集 $\omega = (\omega_i)_{i=1}^n$，主私钥 $s$，为 $V_j$ 生成部分私钥：

• 随机选取阶数为 $d-1$ 的多项式 $p(x)$，满足 $p(0) = s$

• 计算 $V_j$​ 的部分私钥 $PS_{PID_j}=(PS_{i,j})_{i=1}^n$，其中$PS_{i,j} = H_1(PID_j)^{p(\omega_i)} \ mod \ N$

• 将部分私钥 $PS_{PID_j}$ 经安全信道交给 $V_j$
  车辆 $V_j$ 计算完整的公私钥对：

  • 随机选取 $x_{PID_j} \in \mathbb{Z}^*_{q'}$ 和阶数为 $d-1$ 的多项式 $f(x)$，满足 $f(0) = x_{PID_j}=\{x_{i, PID_j}\}_{i=1}^n$，其中 $x_{i, PID_j} = f(\omega_i)$
  • 私钥 $SK_{PID_j} = (PS_{PID_j}, x_{PID_j})$，公钥 $PK_{PID_j} = g^{x_{PID_j}} \ mod \ p'$

2.4 签名

车辆 $V_j$ 对消息 $m_j$ 签名：

• 随机选取 $l_j \in \mathbb{Z}^*_N$​ 和阶数为 $d−1$ 的多项式 $g(x)$，满足 $g(0) = l_j$。对于 $i \in \{1, \dots, n\}$，计算：

  • $y_{i,j} = l_{i,j}^e \ mod \ N$，其中 $l_{i,j} = g(\omega_i)$
  • $u_{i,j} = P\text{S}_{i,j} \cdot l_{j}^{H_2(m_j)} \ mod \ N$

• 随机选取 $k_j \in \mathbb{Z}^*_N$​ 和阶数为 $d−1$ 的多项式 $q(x)$，满足 $q(0) = k_j$。对于 $i \in \{1, \dots, n\}$，计算：

  • $r_j = g^{k_j} \ mod \ p'$
  • $v_{i,j} = k_{i,j} - x_{PID_j} \cdot h_j \ mod \ q'$，其中 $k_{i,j} = q(\omega_i)$，$h_j = H_3(m_j, PID_j, r_j, T_j)$，$T_j$ 为时间戳

• 得到签名 $\sigma_j = (u_j, v_j, y_j, r_j, h_j)$，其中 $y_j = (y_{i,j})_{i=1}^n$, $u_j = (u_{i,j})_{i=1}^n$, $v_j = (v_{i,j})_{i=1}^n$

2.5 验证

验证者接收消息 - 签名对 $(m_j, \sigma_j)$ 和车辆 $V_j$ 公钥 $PK_{PID_j}$，生物特征相关属性集 $\omega = (\omega_i)_{i=1}^n$，$\omega' = (\omega'_i)_{i=1}^n$，其满足 $|\omega \cap \omega'| \geq d$，验证签名：

• 从 $\omega \cap \omega'$ 中随机选取一个包含 $d$ 个元素的子集 $S$，验证等式

  $$\left( \prod_{\omega_i \in S} u_{i,j}^{\Delta_{\omega_i, S(0)}} \right)^e = H_1(PID_j) \cdot \left( \sum_{\omega_i \in S} y_{i,j}{\Delta_{\omega_i, S(0)}} ^{H_2(m_j)ed \Delta_{\omega_i, S(0)}} \right) \mod N$$

  其中 $\Delta_{\omega_i, S(0)}$ 为拉格朗日基本多项式。若上述等式成立，进入下一步验证

• 计算 $h_j' = H_3(m_j, PID_j, r_j', T_j)$，验证等式

$$r'_j=\left(\prod_{\omega_i \in S} g_j^{v'_{i,j}} \right) \cdot \left(PK_{PID_j} \right)^{h'_j d} \ mod \ p'$$

3 安全性分析

3.1 安全规约回顾

安全规约中涉及的三类实体：

• 敌手（Adversary）：意图攻破密码学方案的实体；

• 挑战者（Challenger）：当敌手与真实方案（Real Scheme）交互时，敌手实际上是在与挑战者交互，由挑战者生成真实方案并应答敌手的询问请求。挑战者仅出现在安全模型和安全描述中；

• 模拟器（Simulator）：当敌手与模拟方案（Simulated Scheme）进行交互时，敌手实际上是在与模拟器进行交互，由模拟器生成模拟方案并应答来自敌手的询问请求。模拟器仅出现在安全归约中，作为运行归约算法的一方。

3.2 无证书签名的安全模型

• I 型敌手：外部攻击者，可随意替换任意实体的公钥，但无法获知主密钥

• II 型敌手：恶意的 KGC，可获知系统主密钥，但无法替换用户公钥

3.3 本文模拟方案

底层困难问题

• DL 问题：已知 $\{x, y \ | \ y=g^x, \ x \in Z_q^∗ \}$，求解 $x$ 是困难的。

• VRSA 问题：已知 $\{n, e, a, z \ | \ \ n = pq, \ \gcd(e, (p-1)(q-1)) = 1, u^e \equiv a w^z \pmod{n}, \ u, w \in Z_q^∗ \}$，求解 $u$ 和 $w$ 是困难的。

3.4 求解困难问题

Type I 型敌手

I 型敌手伪造对于 $(\hat{PID} , \hat{m} )$ 的签名 $(\hat{u} ,\hat{v} ,\hat{y} ,\hat{r} ,\hat{h} )$，满足

得 $\left(\sum_{\omega_i \in S} \hat{y}_i{\Delta_{\omega_i, S(0)}}, \prod_{\omega_i \in S} \hat{u}_i^{\Delta_{\omega_i, S(0)}}\right)$ 为困难问题的解

然而，这与 VRSA 问题的难度相矛盾，故方案是安全的。

Type II 型敌手

在询问 $Public \ Key \ Query$ 时，若 $|PID \cap PID_{\pi}| \geq d$，则令 $P K_{PID} = \beta$
在求解推导中，通过控制 $H_3$ 的不同，得到对同一条消息的两条签名，满足
$\left( \prod_{\omega_i \in S} g^{\hat{v}} \right) PK_{P ID_\pi}^{\hat{h}d} = \hat{r} \ mod \ p'$ ①
$\left( \prod_{\omega_i \in S} g^{\hat{v'}} \right) PK_{P ID_\pi}^{\hat{h'}d} = \hat{r} \ mod \ p'$ ②
$①-②$得 $\log_g \beta = \frac{\hat{v} - \hat{v}'}{(\hat{h}' - \hat{h})d}$ 为困难问题的解

然而，这与 DL 问题的难度相矛盾，故方案是安全的。

3.5 非形式化安全性证明

• 消息认证：根据证明，本方案在 ECDLP 和变种 RSA 问题难以解决的假设下是抗自适应选择消息攻击的，所提方案可以保证消息的完整性、认证性和不可否认性。

• 条件隐私保护：车辆 $V_i$ 使用假名 $P ID_j$​ 保护其真实身份，假名基于安全对称加密方案 $\text{Enc}_\kappa(\cdot)/\text{Dec}_\kappa(\cdot)$ 生成，在不知道对称密钥 $\kappa$ 的情况下，任何实体都无法恢复 $V_i$ 的真实身份。仅 TA 拥有密钥，具备恢复 $V_i$ 的真实身份 $BID_j$ 的能力。

• 容错性：方案基于秘密共享将系统主私钥 $s$ 和车辆 $V_j$ 的秘密值 $x_{PID_j}$ 分别分成 $n$ 份，使得车辆 $V_j$ 的部分私钥、完整私钥及签名均可以被构造为 $n$ 份的形式。任何包含至少 $d$ 个属性的属性集均可验证 $V_j$ 的签名，因此方案具有容错性。

• 可追溯性：当恶意车辆发送错误信息时，TA 可通过下述公式提取车辆 $V_j$​ 的生物特征身份 $BID_j$​ 并追踪恶意车辆：

• 不可链接性：假名生成时用到的随机数 $l_j$​ 和 $k_j$​ 是不重复的，每个 $PID$ 是随机且唯一的。因此，攻击者无法关联由同一签名者生成的多个签名。

4 实验评估

4.1 计算开销

本文采用 MIRACL 密码学库计算了不同基本操作的执行时间。选取的参考方案 [19~25] 均为基于双线性配对的方案，因此与作者选取的这些方案相比，本文无配对的方案具有更低的计算开销。

• $T_{bp}$：执行双线性映射操作的时间

• $T_{bp.m}$：执行基于双线性映射的标量乘法操作的时间

• $T_{bp.sm}$：执行基于双线性映射的小指数测试的时间

• $T_{bp.a}$：执行基于双线性映射的点加操作的时间

• $T_{e.m}$：执行椭圆曲线上标量乘法操作的时间

• $T_{e.sm}$：执行椭圆曲线上小指数测试的时间

• $T_{e.a}$：执行椭圆曲线上点加操作的时间

• $T_{e.ex}$：执行模幂运算所需的时间

• $T_{mtp}$：执行映射到点的哈希时间

4.2 通信开销

对 I 型双线性配对，为达到 80bit 安全长度，需要 $|g_1 |≥ 1024(bits)$，故 $\mathbb{G}_1$ 的群元素大小为 $1024\div 8=128$ 字节。对比表明，本文方案在签名长度方面具有更低的通信开销。

• $l_{Z^*_{q}}$：20 字节，$Z^*_{q}$​ 中的元素长度

• $l_{G_1}$：128 字节， $\mathbb{G}_1$ 中的元素长度

• $l_{G}$：40 字节，$\mathbb{G}$ 中的元素长度

• 时间戳和哈希函数的输出分别设置为 4 字节和 20 字节

1 Class 类文件结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

ClassFile {
    u4 magic;
    u2 minor_version;
    u2 major_version;
    u2 constant_pool_count;
    cp_info constant_pool[constant_pool_count-1];
    u2 access_flags;
    u2 this_class;
    u2 super_class;
    u2 interfaces_count;
    u2 interfaces[interfaces_count];
    u2 fields_count;
    field_info fields[fields_count];
    u2 methods_count;
    method_info methods[methods_count];
    u2 attributes_count;
    attribute_info attributes[attributes_count];
}

def Class 文件是一组以 8 个字节为基础单位的二进制流，存储内容几乎全部是程序运行的必要数据，各数据项严格按照顺序紧凑排列，中间无任何分隔符。根据《Java 虚拟机规范》，Class 文件由一个 ClassFile 结构组成，采用的是一种类似于 C 语言结构体的伪结构来存储数据，仅包含下述两种数据类型：

• 无符号数：基本数据类型，用 u1、u2、u4、u8 表示 1~8 个字节的无符号数，可表示数字、索引引用、数量值或是以 UTF-8 格式编码的字符串

• 表：包含多个无符号数，用于描述有层次关系的复合结构的数据

  • 为便于区分，所有表命名均以 “_info” 结尾
  • 整个 Class 文件本质上也是一张表

1.1 全限定名、简单名称和描述符

在 Class 文件中，这三类特殊字符串的出现频率很高：

• 全限定名：类的全限定名是将类全名中的 “.” 用 “/” 替换，并在最后加入一个 “;” 标志结束的字符串

  e.g. Object 类的全限定名为 Ljava/lang/Object;

• 简单名称：没有类型和参数修饰的方法或字段名称

  e.g. 假设当前的 Class 文件中包含了一个 hello () 方法，则 hello () 方法的简单名称为 hello

• 方法和字段的描述符

  • 描述字段的数据类型：基本数据类型以及 void 类型均用一个大写字符表示，对象类型用字符 L 加对象的全限定名表示
  • 描述方法的参数列表（包括数量、类型以及顺序）及其返回值：按照先参数列表、后返回值的顺序描述，参数列表按照参数的严格顺序置于 “()” 内

  e.g. 方法 void hello () 的描述符为 “() V”

1.2 魔数和版本号

• 魔数（Magic Number）：为每个 Class 文件的头 4 个字节，唯一作用是确定文件是否为一个能被虚拟机接受的 Class 文件

• 次版本号（Minor Version）：第 5、第 6 个字节，JDK1.2 后置 0

• 主版本号（Major Version）：第 7、第 8 个字节

  e.g. 52（0x0034）代表 JDK8 版本下编译产生的字节码文件

1.3 常量池

def 常量池（constant pool）可理解为 Class 文件的资源仓库，入口处由常量池容量计数值（constant_pool_count）从 1 开始记录了常量池中的常量数目。主要存放下述两类常量：

• 字面量：文本字符串、被声明为 final 的常量值等

• 符号引用

  • 被模块导出或者开放的包
  • 类和接口的全限定名
  • 字段、方法的名称和描述符
  • 方法句柄和方法类型
  • 动态调用点和动态常量

以 JDK13 为例，常量表包含了 17 种不同类型的常量，彼此数据结构完全独立（建议在有需要时查表）

1.4 访问标志

def 访问标志（access_flags）是一个标志掩码，用于表示类或接口的访问权限和属性。一共有 16 个标志位可以使用，截止 JDK9 定义了 9 个。Class 文件中访问标志的 2 个字节紧跟在常量池之后，值按照按位取或的方式（压缩状态）计算

e.g. 假设当前有一个 Main 类，是一个访问权限为 public 的普通 Class，且未被声明为 final 或 abstract，则有 ACC_PUBLIC | ACC_SUPER = 0x0001 | 0x0020 = 0x0021

1.5 类索引、父类索引和接口索引集合

Class 文件中由这三项数据确定继承关系：

• 类索引（this_class）：2 个字节，用于确定类的全限定名，指向一个类型为 CONSTANT_Class_info 的类描述符常量，通过 CONSTANT_Class_info 类型的常量中的索引值可以找到定义在 CONSTANT_Utf8_info 类型的常量中的全限定名字符串

• 父类索引（super_class）：2 个字节，用于确定类的父类的全限定名

• 接口索引集合（interfaces []）：一组 u2 类型数据的集合，描述类实现的接口

  • 由接口计数器（interfaces_count）表示索引表的容量
  • 按照 implements/extends 关键字后的接口顺序排列

1.6 字段表集合

1
2
3
4
5
6
7

field_info {
    u2 access_flags;
    u2 name_index;
    u2 descriptor_index;
    u2 attributes_count;
    attribute_info attributes[attributes_count];
}

def 字段表（field_info）用于描述接口或者类中声明的变量

• 字段访问标志（access_flags）：类比类的访问标志

• 字段的简单名称对常量池项的引用（name_index）

• 字段的描述符对常量池项的引用（descriptor_index）

• 属性计数器（attributes_count）

• 属性表集合（attribute_info）：存储额外信息

  e.g. 对字段声明 final static int m=520; 存储的额外信息为常量 520

1.7 方法表集合

1
2
3
4
5
6
7

method_info {
    u2 access_flags;
    u2 name_index;
    u2 descriptor_index;
    u2 attributes_count;
    attribute_info attributes[attributes_count];
}

def 字段表（method_info）用于描述接口或者类中声明的方法

• 方法访问标志（access_flags）：类比类的访问标志

• 方法的简单名称对常量池项的引用（name_index）

• 方法的描述符对常量池项的引用（descriptor_index）

• 属性计数器（attributes_count）

• 属性表集合（attribute_info）

Javac 编译器会自动添加方法，最常见的是类构造器 <clinit>() 方法和实例构造器 <init>() 方法

1.8 属性表集合

def 属性表（attribute_info）用于描述信息，从 JVM 实现必须包含的属性到任何人实现的编译器写入的自定义属性均可，JVM 运行时将忽略未知属性

• 属性名称为从常量池中引用的 CONSTANT_Utf8_info 类型的常量

• 属性值的结构是完全自定义的，以 u4 长度的属性说明属性值所占用的位数

1.8.1 Code 属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Code_attribute {
    u2 attribute_name_index;
    u4 attribute_length;
    u2 max_stack;
    u2 max_locals;
    u4 code_length;
    u1 code[code_length];
    u2 exception_table_length;
    {	u2 start_pc;
    	u2 end_pc;
    	u2 handler_pc;
    	u2 catch_type;
    } exception_table[exception_table_length];
    u2 attributes_count;
    attribute_info attributes[attributes_count];
}

def Code 属性是 Class 文件中最重要的一个属性，Java 程序方法体中的代码在编译后以字节码指令的形式存储在 Code 属性内

• 抽象类或接口中的方法不存在 Code 属性

1
2
3
4
5
6
7
8
9
10
11
12
13

public Fundamentals.BinarySearch.Main();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial  #1  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 10: 0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       5     0  this   LFundamentals/BinarySearch/Main;

使用 Javap 反编译一个字节码文件，可知 Code 属性中包含以下主要信息：

• 最大操作数栈（stack，对应 max_stack）：JVM 运行时根据该值分配栈帧（Stack Frame）中的操作栈深度

• 局部变量表所需存储空间（locals，对应 max_locals）

  • 单位是变量槽（Slot），占用 4 个字节，是虚拟机为局部变量分配内存所使用的最小单位

• 方法的参数数目（args_size）

• 方法体内容（attribute_info）

  • 将第一个引用类型本地变量推送至栈顶
  • 执行该类型的实例方法，即常量池存放的第一个变量 java/lang/Object."<init>":()V
  • 执行返回语句

• 行号表（LineNumberTable）：描述源码行号与字节码行号（字节码偏移量）之间的对应关系

• 局部变量表（LocalVariableTable）：描述源码中定义的变量与栈帧中局部变量之间的关系

2 字节码指令

def 字节码指令是代表某种特定含义的操作码

• 指令长度只有一个字节

• JVM 面向操作数栈而非寄存器架构，大多数指令不带参数

• 操作码助记符：l 代表 long，s 代表 short，b 代表 byte，c 代表 char，f 代表 float，d 代表 double，a 代表 reference

大部分指令都不支持整数类型 byte、char 和 short，且没有任何指令支持 boolean 类型。实际上在大多数情况下，这四种类型均使用 int 作为运算类型。故以下主要以 int 类型列举部分常见指令：

• 加载和存储指令

  • 将一个局部变量加载到操作数栈：iload、iload_<n>
  • 将一个数值从操作数栈存储到局部变量表：istore、istore_<n>
  • 将一个常量加载到操作数栈：bipush、ldc、iconst_<i>

• 运算指令

  • 四则运算：iadd、isub、imul、idiv
  • 按位运算：iand、ior、ixor
  • 局部变量自增指令：iinc

• 对象创建与访问指令

  • 创建类实例：new
  • 创建数组：newarray
  • 访问实例字段和类字段：getfield、putfield、getstatic、putstatic
  • 把一个数组元素加载到操作数栈：iaload
  • 将一个操作数栈的值储存到数组元素中：iastore

• 操作数栈管理指令

  • 将操作数栈栈顶一个或两个元素出栈：pop、pop2
  • 复制栈顶数值并复制值入栈：dup、dup_x1
  • 将栈最顶端的两个数值互换：swap

• 控制转移指令

  • 条件分支：ifeq、ifnonnull
  • 复合条件分支：tableswitch、lookupswitch
  • 无条件分支：goto、jsr、ret

• 方法调用和返回指令

  • 调用对象的实例方法：invokevirtual
  • 调用接口方法：invokeinterface
  • 调用一些需要特殊处理（实例初始化、私有和父类方法）的实例方法：invokespecial
  • 调用类静态方法：invokestatic

3 JVM 类加载机制

3.1 类的生命周期

def 类加载过程包含加载、验证、准备、解析和初始化五个部分，是一个类型从被加载到虚拟机内存中到完成初始化的全过程

• 验证、准备、解析三个部分统称为连接

• 第 1~4 阶段的顺序是确定的：指按顺序开始，而不是按顺序依次执行

• 为支持运行时绑定特性，解析阶段可以在初始化阶段之后开始

3.1.1 加载

在加载阶段，JVM 完成以下步骤：

• 通过一个类的全限定名获取定义此类的二进制字节流

• 将该字节流代表的静态存储结构转化为方法区的运行时数据结构

• 在内存中生成一个代表类的 java.lang.Class 对象，作为方法区该类数据的访问入口

3.1.2 验证

验证阶段旨在确保 Class 文件的字节流中包含的信息符合约束：

• 文件格式验证：从魔数和版本号的格式开始检查直至属性表

• 元数据验证：对字节码描述的信息进行语义分析，保证元数据信息中的数据类型符合 Java 语言规范

• 字节码验证：验证中最复杂的步骤，对类的方法体（Code 属性）进行校验分析

• 符号引用验证：对常量池中的各种符号引用进行匹配性校验，确保能够正常解析

3.1.3 准备

在准备阶段，正式为静态变量分配内存并设置初始值

• 准备阶段分配内存的仅包括类变量，而不包括实例变量，实例变量会在对象实例化时随着对象一块分配在 Java 堆中

• 一般地，设置的初始值是数据类型默认的零值；但如果类字段的字段属性表中存在 ConstantValue 属性，则准备阶段变量值将初始化为 ConstantValue 属性指定的初始值

  e.g. 语句 public static int a = 520; 对应准备阶段 a 的初始值为 0

3.1.4 解析

解析阶段将常量池内的符号引用替换为直接引用，解析动作主要针对类或接口、字段、类方法、接口方法、方法类型、方法句柄和调用点限定符 7 类符号引用进行

• 符号引用（Symbolic References）：以一组符号来描述所引用的目标，可为任意形式的字面量，仅要求能无歧义地定位到目标

• 直接引用（Direct References）：直接指向目标的指针、相对偏移量或能间接定位到目标的句柄

3.1.5 初始化

初始化阶段执行类中编写的 Java 程序代码。《Java 虚拟机规范》严格规定有且只有六种情况必须立即对类进行初始化，类的初始化时机如下：

• 遇到 new、getstatic、putstatic 或 invokestatic 字节码指令时

• 使用 java.lang.reflect 包的方法对类型进行反射调用时

• 加载一个类的子类时

• 虚拟机启动时，需初始化包含 main () 方法的主类

• （JDK7+）一个 java.lang.invoke.MethodHandle 实例最后的解析结果为 REF_getStatic、REF_putStatic、REF_invokeStatic、REF_newInvokeSpecial 四种类型的方法句柄，且该方法句柄对应的类未初始化时

• （JDK8+）一个接口包含有 default 关键字修饰的方法，且该接口的实现类已初始化时

3.1.6 使用

类访问方法区内数据结构的接口， 对象是 Java 堆的数据

3.1.7 卸载

出现以下情况 JVM 将结束生命周期：

• 执行 System.exit () 方法

• 程序正常执行结束

• 程序异常终止

• 操作系统出错导致 JVM 进程终止

3.2 类加载器

def 类加载器用于实现类的加载动作

• 每个类加载器，都拥有一个独立的类名称空间

  e.g. 两个类来源于同一个 Class，被同一个 Java 虚拟机加载，如果用于加载的类加载器不同，则两个类必定不相等

3.2.1 双亲委派模型

从开发人员的角度，类加载器可划分为以下类型：

• 启动类加载器（Bootstrap Class Loader）：负责加载存放在 <JAVA_HOME>\lib 目录，或在 -Xbootclasspath 参数指定路径下的，并且能被虚拟机识别的类库（如 rt.jar、tools.jar，所有的 java.* 开头的类均被启动类加载器加载）

  • 启动类加载器无法被 Java 程序直接引用，如果需要向其委派加载请求，可直接使用 null 代替

• 扩展类加载器（Extension Class Loader）：负责加载 <JAVA_HOME>\lib\ext 目录中，或由 java.ext.dirs 系统变量指定路径下的所有类库（如 javax.* 开头的类）

  • 在 sun.misc.Launcher$ExtClassLoader 类实现
  • 由于扩展类加载器是由 Java 代码实现的，开发者可直接在程序中使用扩展类加载器加载类

• 应用程序类加载器（Application Class Loader）：负责加载用户类路径（ClassPath）下的所有类库

  • 在 sun.misc.Launcher$AppClassLoader 类实现
  • 一般情况下作为程序默认的类加载器，开发者可以直接使用

def 双亲委派模型体现为三层类加载器、双亲委派的类加载架构

• 要求除顶层的启动类加载器外，其余的类加载器都应有自己的父类加载器

• 父类加载器是采用组合而非继承关系实现

参考

[1] 深入理解 Java 虚拟机：JVM 高级特性与最佳实践（第 3 版）

[2] Java JVM 虚拟机 已完结（IDEA 2021 版本）4K 蓝光画质

[3] 柏码知识库 | JVM 笔记（三）类与类加载

[4] Java 全栈知识体系

[5] Java Virtual Machine Specification

1 方案介绍

1.1 无证书签名方案 CLSS

• $Setup(k)$：系统初始化

• $PPKE(UID_i, s)$：部分密钥生成

• $SPRK(UID_i, d_i)$：设置用户完整私钥

• $SPK(UID_i, sv_i)$：设置用户公钥

• $Sign(M_i, sk_i, UID_i, pk_i)$：签名

• $Verify(M_i, σ_i, UID_i, pk_i)$：单次验证

• $BatchVerify(\{M_i, σ_i, UID_i, pk_i\}^n_{i=1})$：批量验证

1.1.1 系统初始化

$Setup(k)$：由 $KGC$ 执行，根据安全参数生成主密钥和参数列表

• 给定安全参数 $k$，生成参数集合 $\langle G_1, G_2, \psi, G_T, e, q, P, P' \rangle$

• 随机选取 $s \in \mathbb{Z}_{q}^*$ 作为主私钥，计算主公钥 $P_0 = sP, P'_0 = sP'$

• 选择三个密码学哈希函数$H_0 : \{0, 1\}^* \rightarrow G_1^*$, $H_1 : \{0, 1\}^* \rightarrow \mathbb{Z}_{q}^*$, $H_2 : \{0, 1\}^* \rightarrow G_2^*$

• 公开参数列表 $\text{paramList} = \{G_1, G_2, \psi, G_T, e, q, P, P', P_0, P'_0, H_0, H_1, H_2\}$

1.1.2 部分密钥生成

$PPKE(UID_i, s)$：由 $KGC$ 执行，接受用户身份 $UID_i \in \{0, 1\}^*$ 和主私钥 $s$ 作为输入，生成用户部分私钥 $d_i$

• 计算 $d_i = sQ_i$，其中 $Q_i = H_0(U ID_i)$

1.1.3 设置完整私钥

$SPRK(UID_i, d_i)$：由具有 $UID_i$ 身份的用户执行，输入身份 $UID_i$ 和部分私钥 $d_i$，生成其完整私钥 $sk_{i}$

• 选择随机数 $sv_{i} \in \mathbb{Z}_{q}^*$​ 作为其秘密值

• 设置完整私钥 $sk_{i} = (sv_{i}, d_i)$

1.1.4 设置公钥

$SPK(UID_i, sv_i)$：由具有 $UID_i$ 身份的用户执行，输入用户身份 $UID_i$ 和秘密值 $sv_i$，生成用户公钥 $pk_i$

• 计算 $pk_i=sv_iP$

1.1.5 签名

$Sign(M_i, sk_i, UID_i, pk_i)$：由具有 $UID_i$ 身份、完整私钥 $sk_i$ 和公钥 $pk_i$ 的签名者执行，输入消息 $M_i$​、$sk_{i}$、$UID_i$​ 和 $pk_i$，生成对消息 $M_i$ 的签名 $σ_i$

• 随机选取 $r_i \in \mathbb{Z}_{q}^*$​，设置 $R_i = r_iP$

• 计算 $u_i = H_1(UID_i || M_i || pk_i || R_i || \Delta)$ 和 $W = H_2(\Delta)$，其中 $\Delta$ 是基于时间戳生成的一次性消息

• 计算 $V_i = u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)$

• 设置签名 $\sigma_i = (R_i, V_i)$

1.1.6 验证

$Verify(M_i, σ_i, UID_i, pk_i)$：输入消息 $M_i$、签名 $σ_i$、用户身份 $UID_i$ 和用户公钥 $pk_i$，验证者验证签名 $σ_i$ 的有效性

• 计算 $Q_i = H_0(U ID_i)$，$u_i = H_1(UID_i || M_i || pk_i || R_i || \Delta)$，$W = H_2(\Delta)$

• 如果 $e(V_i, P') = e(u_ipk_i + R_i, W)e(u_iQ_i + R_i, P'_0)$ 成立，则输出 $1$；否则输出 $0$

正确性证明：代入$V_i = u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)$，$d_i = sQ_i$​，$P_0 = sP$，$P'_0 = sP'$，$pk_i=sv_iP$，$R_i = r_iP$，有
$e(V_i, P') = e(u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0), P')$
$=e(u_isv_{i}\psi(W), P') \cdot e(u_id_i , P') \cdot e(r_i\psi(W),P') \cdot e(r_iP_0,P')$
$=e(u_isv_{i}P,W) \cdot e(u_isQ_i,P') \cdot e(r_iP,W)\cdot e(r_iP,P_0')$
$=e(u_ipk_i,W)\cdot e(u_iQ_i,sP')\cdot e(R_i,W)\cdot e(R_i,P_0')$
$=e(u_ipk_i + R_i, W)e(u_iQ_i + R_i, P'_0)$

1.1.7 批量验证

$BatchVerify(\{M_i, σ_i, UID_i, pk_i\}^n_{i=1})$：验证者批量验证消息 - 签名对 $(M_i, σ_i)$

• 随机选取 $\theta = (\theta_1, \theta_2, ..., \theta_n)$，其中 $\theta_i \in \{0, 1\}^l$，$l$ 为小整数

• 计算 $Q_i = H_0(U ID_i)$，$u_i = H_1(UID_i || M_i || pk_i || R_i || \Delta)$，$W = H_2(\Delta)$

• 如果 $e(\sum_{i=1}^{n} \theta_i V_i, P')$ = $e(\sum_{i=1}^{n} \theta_i(u_i pk_i + R_i), W)$$e(\sum_{i=1}^{n} \theta_i(u_i Q_i + R_i), P'_0)$ 成立，则输出 $1$；否则输出 $0$

正确性证明：代入$V_i = u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)$，$d_i = sQ_i$​，$P_0 = sP$，$P'_0 = sP'$，$pk_i=sv_iP$，$R_i = r_iP$，有
$e(\sum_{i=1}^{n} \theta_i V_i, P') =e(\sum_{i=1}^{n} \theta_i (u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)), P')$
$=e((\sum_{i=1}^{n} \theta_iu_isv_{i}) \cdot\psi(W), P') \cdot e(\sum_{i=1}^{n} \theta_iu_id_i , P')$ $\cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot \psi(W),P') \cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot P_0,P')$
$=e((\sum_{i=1}^{n} \theta_iu_isv_{i}) \cdot P,W) \cdot e(\sum_{i=1}^{n} \theta_iu_isQ_i,P')$$\cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot P,W)\cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot P,P_0')$
$=e(\sum_{i=1}^{n} \theta_iu_ipk_i,W)\cdot e((\sum_{i=1}^{n} \theta_iu_iQ_i,sP')$$\cdot e(\sum_{i=1}^{n} \theta_iR_i,W)\cdot e(\sum_{i=1}^{n} \theta_iR_i,P_0')$
$=e(\sum_{i=1}^{n} \theta_i(u_i pk_i + R_i), W)$$e(\sum_{i=1}^{n} \theta_i(u_i Q_i + R_i), P'_0)$

1.2 车对车通信方案 ES&PPS

1.2.1 系统初始化阶段

在此阶段，$KGC$ 生成系统主密钥并公布参数列表

• 给定安全参数 $k$，运行 $Setup(k)$ 算法，生成主密钥 $s$ 和参数列表 $\text{paramList} = \{G_1, G_2, \psi, G_T, e, q, P, P', P_0, P'_0, H_0, H_1, H_2\}$

• 选择一个安全的对称加密方案 $E_{\text{key}}(\cdot) / D_{\text{key}}(\cdot)$ 及其密钥 $\text{key}$

• 设置系统主密钥为 $(\text{key}, s)$

• 公开参数列表 $\text{paramList}' = \{\text{paramList}, E_{\text{key}}(\cdot) / D_{\text{key}}(\cdot)\}$