前沿密码研讨
# 区块链与比特币
Blockchain
区块链(Blockchain)是一种去中心化的分布式账本技术,最初被用于比特币,现在被广泛应用于金融、供应链、身份认证、医疗等领域
- Block(区块):指的是交易数据被打包后形成的单元
- Chain(链):指的是这些区块按时间顺序通过加密链接在一起,形成一条链式结构
区块链本质上是一个由多个“区块”按时间顺序串联组成的数据结构,每个区块中记录了一组交易数据,并通过密码学方法保证不可篡改
- 就是一个链表,只不过节点数据很特别
每个区块中不仅包含交易数据,还包含前一个区块的哈希值(加密摘要),从而形成一个前后相连、不可逆的链式结构,一旦前面的区块内容被修改,其后的所有区块的哈希也会发生变化,因此可以有效防止数据篡改
它具有以下几个核心特性
| 特性 | 解释 |
|---|---|
| 分布式 | 数据不是集中在一个服务器上,而是存储在网络中所有节点中 |
| 去中心化 | 不依赖任何单一机构或第三方,节点间通过共识机制达成一致 |
| 不可篡改 | 一旦数据被记录到区块链上就无法更改 |
| 可追溯性 | 每笔交易都有完整的时间戳和历史记录 |
| 透明性和可验证性 | 所有节点都能验证交易的真实性和完整性 |
可以将区块链比作一本多人共享的“记账本”,每一页就是一个区块,每页内容写好后都盖章封存(哈希+共识机制),然后连接到前一页之后,所有人都能看到记账内容,但没人能偷偷改动过去的记录(这样将失去有效性)
# 哈希与共识机制
我们把每个区块看作一本“账簿页面”
- 上面写着本轮的交易记录
- 为了防止事后修改,系统要给它盖章封存
这个“封存”过程由两部分组成
| 组成 | 含义 | 作用 |
|---|---|---|
| 哈希(Hash) | 用加密算法把区块“压缩”为一个唯一摘要值 | 一旦数据改动,哈希值就会改变,能立刻察觉 |
| 共识机制(如 PoW) | 网络中大多数节点共同同意这个区块有效 | 防止恶意节点随意造假 |
哈希 = 在每页账簿上盖防伪印章
在区块链中
- 每个区块都记录前一个区块的哈希值
- 区块内容一改,哈希就变,链就断了
- 这使得任何人想修改历史记录都变得几乎不可能
哈希保证了“区块内部”和“区块之间”都不能被偷偷篡改,我们可以保证任意一个链的合法性,并且链上的区块可以通过摘要值保证其无法篡改
区块的合法性如何保证?用到共识机制
| 机制 | 说明 |
|---|---|
| 工作量证明(Proof of Work) | 比特币使用,必须算出一个符合条件的哈希(很难) |
| 权益证明(PoS) | 以太坊等使用,凭“持币量”投票决策 |
| 拜占庭容错、DPoS、PBFT 等 | 其他公链/联盟链使用 |
共识 = 众人见证并盖公章,谁造假就会被识破
在比特币中
- 谁想添加新区块,必须算出一个合格哈希(挖矿)
- 这非常耗费计算力,意味着这个“封章”具有“成本”
- 网络只接受最长合法链作为真正的“账本”
共识机制保证了大家都接受同一个历史,不会有“分叉账本”乱象
区块链的安全与可信,来源于哈希算法提供的防篡改能力和共识机制提供的集体认可,这套机制就是区块链最本质的盖章封存
# 最长合法链
什么叫“最长合法链”?在比特币系统中
- 每一个新区块都是接在上一个合法区块后面
- 这样连接形成了一个链条,称为“区块链”
- 不同的矿工可能同时挖出不同的新块,就可能出现分叉
- 比特币规定: “ 以工作量为准,链上块最多的那条链为主链”
所以,“最长合法链”意思是:目前全网算力共同认定的、累计工作量最大的那条区块链,即所有节点都认为是“正统”的链,即唯一的账本
为什么叫“最长”?这指的是什么长度?不是指字节数或块个数,而是指“累积的工作量(难度)
- 在比特币中,每个区块都必须经过挖矿计算(工作量证明,PoW)
- 你挖得越多、链越长,就代表你为这条链投入了更多计算资源
- 网络规定:谁的链累积的工作量最多,谁的链就被视为“主链”
- 这通常表现为块数最多的一条链,因为每个块的难度是固定的
举个例子,假设区块链已经走到第 100 个区块,某一时刻,两个矿工同时挖出了第 101 块,分别叫101A和101B,网络产生了“短暂分叉”
... → 100 → 101A
↘︎ 101B
2
此时,有的节点收到101A,有的收到101B,网络短暂不一致,假如接下来矿工 C 在101A的基础上成功挖出102A,链就变成
... → 100 → 101A → 102A
↘︎ 101B
2
这时,“A链”更长了,大多数节点就会选择它,那么最长合法链 = ... → 100 → 101A → 102A
而101B和其交易就会被丢弃,称为“孤块(orphan block)”
- 需要注意的是,
101B本身是一个合法的区块(他正确引用了上一个区块 100 的哈希并且工作量证明 PoW 达标),但是不是一个合法的比特币,因为这笔帐被主链抛弃了
最长合法链解决了什么问题?它是去中心化世界中解决冲突、达成共识的方式
- 没有中央服务器说了算
- 所有节点都用相同规则判断哪条链是主链
- 就算发生了分叉,大家也知道: “我们跟着最长合法链走”,这就避免了混乱
# 比特币概述
比特币(Bitcoin)是第一个真正实现的区块链应用,它是一种去中心化的数字加密货币,由中本聪(Satoshi Nakamoto)在 2008 年提出,2009 年正式发布。其工作流程如下
1️⃣ 交易打包成区块
- 用户发起交易(例如 A 给 B 转 1 个比特币)
- 网络节点广播这笔交易
- “矿工”收集一批交易并打包成一个区块(block)
2️⃣ 工作量证明(PoW)机制:挖矿
- 为了添加这个新区块,矿工必须完成一个复杂的数学难题(找一个满足条件的哈希值)
- 这个过程称为“挖矿”,谁先解出问题,谁就能把区块加到区块链上,并获得比特币奖励
3️⃣ 区块链接成链
- 每个新区块中记录上一个区块的哈希值
- 形成一个不可篡改的链式结构 —— 区块链
- 一旦区块被添加,其内部数据几乎无法更改,因为更改一个区块将破坏整个后续链条的哈希
4️⃣ 全网共识
- 所有节点都验证新区块是否合法(是否遵循规则、是否有双重支付等)
- 一致接受后,这个区块就被永久记录
所以比特币到底是什么,是一串哈希吗?实际上是一个私钥,具备“控制账本上某个地址”的能力 —— 拥有比特币
哈希算法在整个系统里大量使用
| 用途 | 内容 | 哈希算法 |
|---|---|---|
| 区块链结构 | 每个区块有一个哈希值,指向上一个区块 | SHA-256 |
| 挖矿过程 | 通过不断尝试不同 nonce,找出符合难度的哈希 | SHA-256 x2 |
| 地址生成 | 比特币地址是从公钥哈希计算出来的 | RIPEMD-160(SHA-256 pk) |
| 交易 ID | 每笔交易也有一个唯一的哈希值(txid) | SHA-256 x2 |
当拥有 1 个比特币,其实
- 你有一个私钥,对应一个地址
- 区块链账本里记录了一个或多个“未花费的输出”,指向这个地址,总金额为 1 BTC
- 当你转账时,系统检查这些 UTXO,再生成新的交易,把这些比特币“花掉”
# 双花问题
“双花”(Double Spending)是区块链和加密货币中最关键、也最需要防范的问题之一,它指的是:同一个 BTC 被恶意的花费两次,例如
- 把 1 BTC 支付给商家 A
- 同时将另一笔交易广播出去,把同样的 1 BTC 支付给你的另一个地址 B
- 如果你能让“支付给 B 的交易”被矿工先打包进区块链中,那么你就“收回”了那笔钱,A 就被骗了
比特币用以下机制来防御双花
| 防御机制 | 说明 |
|---|---|
| 区块链结构 | 所有交易都要被打包进单一主链(最长合法链)且不可更改 |
| 工作量证明(PoW) | 想“抢跑”插入伪造交易,需要极高算力才能制造“更长链” |
| 等待多个确认 | 商家会等6个区块确认才认为交易不可逆 |
| 去中心化 | 网络中成千上万节点共同验证、同步,攻击难度非常高 |
为什么双重支付难以实现?
- 要双花成功,你得控制超过全网一半的算力(所谓 51% 攻击)
- 即使你广播了两笔冲突交易,矿工只会打包其中一笔
- 其他那一笔会被网络判定为“双花交易”,直接丢弃
# 减半机制
比特币的“减半机制”是其最重要的货币发行机制之一,它是比特币通缩模型的核心
- 比特币减半机制是指:每当网络挖出 210000 个区块(大约每 4 年),挖矿所得的比特币奖励就会减少一半,直到总发行量接近 2100 万个比特币为止
为什么要减半?控制总量以模拟黄金的稀缺性
- 比特币的最大供应量为 2100万枚
- 如果不减半,发行会无限制增发
- 减半机制让发行量逐渐趋近于 2100 万
抑制通货膨胀
- 减少供应速度,保证稀缺
- 吸引长期投资者,形成稳定预期
减半的经济效应
| 影响因素 | 说明 |
|---|---|
| 矿工收入减少 | 如果币价不涨,矿工收益会缩水一半 |
| 币价有上涨预期 | 因为供应减少,而需求可能稳定甚至上升 |
| 市场投机波动 | 减半前后往往伴随价格剧烈波动 |
| 挖矿难度调整 | 有些矿工退出后,全网难度会自动调整以维持出块速度 |
这其实是一个经济学问题,而并非密码学范畴,减半事件是写死在比特币代码里的(Bitcoin Core),无法人为更改
比特币减半机制是比特币每 4 年减产一半的系统规则,用以模拟稀缺性、控制总量、增强长期价值,它是比特币“通缩”特性和“数字黄金”地位的根本来源(人为稀缺)
# 简单的矿工
本质上其实就是一个 SHA-256 哈希,目的是找到哈希值为 hash(input) 并满足特定要求的 nonce
public class SimpleMiner {
// 将任意字符串进行 SHA-256 哈希
public String sha256(String input) throws Exception {
MessageDigest digest = MessageDigest.getInstance("SHA-256");
byte[] hashBytes = digest.digest(input.getBytes(StandardCharsets.UTF_8));
// 将字节数组转换为十六进制字符串
StringBuilder hexString = new StringBuilder();
for (byte b : hashBytes) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1) hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
}
public Map<String, Object> mine(String blockData, int difficulty){
Map<String, Object> data = new HashMap<>();
int nonce = 0;
String hash;
long startTime = System.currentTimeMillis();
// 要求哈希值的前缀有 difficulty 个 0,才满足要求
String targetPrefix = "0".repeat(difficulty);
while (true) {
// blockData 是假设的区块内容
String input = blockData + nonce;
try {
hash = sha256(input);
} catch (Exception e) {
data.put("Error", e.toString());
return data;
}
if (hash.startsWith(targetPrefix)) {
System.out.println("找到符合条件的 nonce: " + nonce);
System.out.println("对应哈希值: " + hash);
data.put("nonce", nonce);
data.put("hash", hash);
break;
}
nonce++;
}
long endTime = System.currentTimeMillis();
System.out.println("耗时: " + (endTime - startTime) + " ms");
data.put("time_cost", endTime-startTime);
return data;
}
public static void main(String[] args) throws Exception {
SimpleMiner miner = new SimpleMiner();
Map<String, Object> data = miner.mine("Alice trade 10 btc to Bob", 5);
System.out.println(data);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
输入{"Alice trade 10 btc to Bob", 5},输出
找到符合条件的 nonce: 1155772
对应哈希值: 00000a65e3e876194ca42b6663680bdd12dd6c0046b528e0cd4f1f19cb32d5d0
耗时: 1468 ms
2
3
# 抗量子加密
# Shor 算法
Shor 算法(1994)是量子计算的一个突破性发现,它能在多项式时间内解决一些传统计算难以处理的数学问题,如 RSA 和 ECC
- 量子计算机的出现将使得 Shor 算法成为现实,并使得目前广泛使用的 RSA、ECC、DSA 等基于大数分解和离散对数的加密算法变得不再安全
量子计算的广泛应用可能尚需几十年,但为了避免未来量子计算突破传统加密算法后带来的安全危机,提前准备抗量子签名算法是非常必要的。通过标准化新型抗量子签名算法,能够在量子计算技术逐步成熟的过程中平滑过渡,避免数据泄露和信息丧失
另外,抗量子算法可能在计算复杂度和资源消耗方面存在折衷,即在设计抗量子签名算法时需要考虑算法的效率与安全性,确保其在实际应用中能够平衡计算和存储成本
| 场景 | 用途 |
|---|---|
| 网络通信 | 1. TLS/SSL 协议:用于服务器认证和客户端认证,Dilithium 作为后量子签名候选方案,替代传统的 RSA 或 ECC 签名,抵抗量子计算可能带来的攻击风险 2. VPN 和安全隧道:在构建加密隧道的身份验证阶段,Dilithium 提供快速、轻量化的签名验证 |
| 物联网设备 | 1. 资源受限设备:Dilithium 的签名生成和验证操作均适合嵌入式设备,尤其是在低功耗和有限存储场景下(如智能家居、工业传感器) 2. 边缘计算与5G场景:在设备边缘节点进行安全认证时,Dilithium 以其存储和计算效率成为抗量子密码的优选 |
| 区块链与电子货币 | 1. 交易认证:在区块链网络中,用于交易签名和节点认证,确保抗量子攻击的安全性 2. 数字资产保护:支持智能合约和数字资产的安全签名机制,提供持久的抗量子攻击保障 |
| 加密系统 | 1. 长期数据保护:政府机密和军事信息需长期安全存储,Dilithium 提供抗量子签名,保障数据完整性 2. 国防通信与安全协议:用于军事通信中的身份认证和加密密钥协商 |
# 后量子对称加密
参考对称轻量级密码算法,如 PRESENT、SPARX 等的设计思路,基于格上的 LPN 问题(LWE 问题的特殊情况)也常用于对称加密场景
# 后量子签名
后量子数字签名
格基算法:基于格的问题,如
- 学习错误问题 LWE(Dilithium)
- 短整数解问题 SIS(Falcon)
- 最短向量问题 SVP(NTRU)
被认为对量子计算机具有抗性,因此成为抗量子密码学的热门研究方向
Kyber
- Kyber 是一个广泛使用的基于 LWE 的加密方案,也提供了一种基于 LWE 的签名方案(通常与加密协议一同使用)
- Kyber 签名方案基于基于LWE问题的密钥交换和公钥加密系统
- 该签名方案适用于公钥加密系统中,并具有较好的效率和紧凑性
Falcon:一种基于 NTRU 格和 SIS 问题的高效抗量子签名方案,其核心思想是
- 使用格上的短向量作为签名,确保签名的长度较短
- 引入拒绝采样技术,保证签名的随机性和抗攻击性
- 基于 LWE 问题
- 是 NIST 抗量子密码学标准化项目中的候选算法(现已入选)
- 特点:签名大小较小,验证速度快,适合通用签名场景
- 参考场景:抗量子环境下的区块链和身份认证
BLISS(Bimodal Lattice Signature Scheme)
- 基于格上的离散高斯采样,采用 LWE 的设计思想
- 优点:签名小,计算速度快,密钥生成相对高效。
- 缺点:在侧信道攻击下可能存在风险
基于哈希的康量子算法:哈希函数的安全性已经过几十年的广泛研究,基于哈希的签名算法在理论上简单且抗量子攻击
SPHINCS+
- 是 NIST 抗量子密码学标准化项目中的另一候选算法
- 特点:无状态签名,完全基于哈希函数,无需额外的数学假设
- 缺点:签名长度较长,但安全性非常高
- 应用场景:适合需要强安全性保证的系统,如军事和政府通信
Merkle 签名方案
- 使用 Merkle 树作为核心数据结构,支持大批量签名
- 优点:简单、直接
- 缺点:签名效率不高,需要维护状态(改进版如 SPHINCS+ 解决了这一问题)
其他抗量子签名算法
| 算法 | 数学理论 | 特点 |
|---|---|---|
| Rainbow | 基于多变量多项式 | 使用多层多变量多项式系统设计;优点:签名小,验证速度快;缺点:密钥较大,在某些应用中存储成本高;应用:轻量级设备或需要快速签名的场景 |
| Wave | 基于纠错码 | 基于纠错码和稀疏多项式;优点:签名小,验证速度快;缺点:目前仍处于研究阶段,实际应用较少 |
| SeaSign | 基于等距映射 | 基于超奇异椭圆曲线的等距映射问题;特点:密钥和签名大小非常小,特别适合低带宽环境;缺点:签名生成速度较慢,仍在优化中 |
| Picnic | 基于组合理论 | 利用组合数学问题的难度构造,基于零知识证明和哈希函数;特点:无需复杂的数学假设,签名大小中等;缺点:验证速度可能较慢;应用:嵌入式设备或资源受限的环境 |
# Dilithium 算法
CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme (opens new window)
# LWE 和 SIS 问题
LWE(Learning With Errors)和 SIS(Short Integer Solution)问题是两种在基于格的密码学(lattice-based cryptography)中常见的困难问题,它们是许多现代抗量子密码学协议的安全基础
LWE 是基于格理论的一种问题,它描述了如何从某些错误的线性关系中学习信息。具体而言,LWE 问题要求从一组添加噪声的线性方程中恢复出未知的密钥或向量,其定义如下
加密方已知 n 长的密钥向量 s,通过 m 长的噪声向量 e 将一个 mxn 的矩阵 A 加密为 b
比如一个 3x2 的矩阵 A,和 2 长的向量 s,3 长的噪声 e
可加密为
攻击方要想破解该系统,需要从截取的密文 b 中恢复密钥 s,这个操作是极其困难的,其困难性来自于两方面
- 误差(Noise):误差向量 e 的引入使得问题变得不再是一个简单的线性方程组,因此从给定的 A 和 b 中恢复出 s 是困难的
- 高维空间:LWE 的实例通常涉及到大矩阵和向量(高维度),使得算法的时间复杂度和计算复杂度非常高
注意:在 RFID 认证中提到的 LPN(Learning Party with Noise)问题是 LWE 问题在模数 q 为 2 的域上的特例,其计算始终为模二加法(异或运算),故而更适合在轻量场景下使用,如身份认证、对称加密等领域
SIS 问题与 LWE 问题有密切的关系,可以看作是 LWE 问题的一种变种,其定义如下,给定一个 mxn 的矩阵 A 和一个 m 长目标向量 b,其目标是找到一个 n 长的向量 x 使得
并且 x 是“短”的,即 x 的元素值非常小,也就是说,SIS 问题要求我们找到一个小整数解,使得上述方程成立
SIS 问题的困难性在于
- 寻找短整数解:我们必须在可能的解空间中寻找一个具有小值的解,这使得问题非常难以解决。
- 矩阵的规模:类似于 LWE,SIS 问题通常涉及到高维度的矩阵,因此解决这个问题需要耗费大量计算资源
# LWE 问题的一般签名形式
An Improved Compression Technique for Signatures Based on Learning with Errors (opens new window)
公钥生成:得到私钥SK = S和公钥PK = (A, T)
其中 E 必须是一个足够“小”的噪声,满足短向量性质,否则将拒绝采样
签名
- 要加密的数据为随机生成的向量 y
- y 先通过公钥矩阵 A 内积为向量 v
- 而后和随机数 μ 一起经过哈希得到 c,再二次哈希得到 c(注意两个 c 通过加粗区分)
- 再计算密文 z = y + Sc
- 签名值为 (z, c)
需要注意的是,这里 c 和 z 必须满足 6~8 的条件,即满足短向量性质,否则将拒绝采样
验签:收到的签名值为 (z, c)
1️⃣ 先计算二重哈希 c = F(c)
2️⃣ 由于已知公钥 (A, T),于是根据 (z, c) 计算 w,该 w 实际上等于
3️⃣ 由于 w 的特性,式子中的 Ec 将被忽略,即有 w ≈ v
进而服务器计算 c' = H([w], μ),并与哈希值 c 进行比较,若一致且 z 为短向量,则验签通过
# Dilithium 加密
Dilithium 加密细节
# 密钥生成
随机数/向量生成
- 生成两个 256 位的随机数 ρ,K
- 从随机分布中抽取两个秘密密钥向量 s1 和 s2,这些向量的系数属于环 Rq 且大小不超过 η
矩阵扩展:将种子 ρ 扩展成一个大小为 k×ℓ 的矩阵 A,其中每个元素在多项式环Rq = Zq[X]/(Xn+1)上,其中q = 2^23−2^13+1, n=256。但为了更快的实现考虑,矩阵 A 实际上是以系数在Zq^(256)中的矩阵格式输出并存储的,计算
而后将 t 分解为 d 位高位 t1 和余下的低位 t0 两个部分
- 本方案中公钥的第二部分为 t1 而非 t,使得此时的公钥只需要
⌈logq⌉−d字节,而非⌈logq⌉字节
将 ρ 和 t1 打包(联结)并使用 SHAKE-256 哈希,得到 384 位的 tr,用于签名时的消息摘要
最终输出密钥对
# 签名
1️⃣ 初始化
- 由种子 ρ 生成矩阵 A
- 将 tr 和消息 M 打包并使用 SHAKE-256 哈希,得到 384 位的消息摘要 μ
- 初始化
κ = 0, (z, h) = ⊥,当(z, h) = ⊥时重复下述签名过程并累加计数器κ,直到生成有效签名
生成掩码向量 y:扩展K || μ || κ生成多项式向量 y,其中
注意:由于签名可能需要重复尝试多次,每次尝试时附加的计数器 κ 可以确保相同消息的多次签名尝试会输出不同的随机数
2️⃣ 计算w = Ay
计算 w1:将 w 的每个系数拆分为高位和低位部分,依照
提取其高位部分 w1,其中
生成挑战值 c:挑战值 c 由消息 M 和 w1 的哈希值生成,c 是环 Rq 中的多项式,具有 60 个 ±1 的系数,其他系数为 0
3️⃣ 计算初始签名值 z
分解w-cs2的高低位,以进一步检查签名的有效性
拒绝采样、高低位校验:
- 设置参数 β,其值为 cs1 的最大可能系数。由于 c 只有 60 个 ±1 的系数,且 s1 的最大系数为 η,因此有 β ≤ 60η
- 检查
Ay−cs2的低位部分 - 检查
Ay−cs2的高位部分
如果 z 的任何系数大于 γ1−β、Ay−cs2 低位部分的任何系数大于 γ2−β、Ay−cs2 高位部分不为 w1 中的任意一项成立,则拒绝此签名
生成附加提示 h 用于验证,确保验证者可以正确恢复出高位信息。由于公钥只包含高位部分 t1,验证时无法直接计算Az−ct的完整值,而是只能计算
为了弥补这一点,签名者需要发送提示 h,告知验证者 ct0 导致进位的位置,从而能够正确恢复Az−ct的高位部分。此时,如果 ct0 的任何系数大于 γ2,或是提示 h 中的 1 的数目超出限制 ω,则同样拒绝此签名
4️⃣ 输出签名
# 验签
已知公钥 pk,明文消息 M 和签名 σ
1️⃣ 初始化
- 由种子 ρ 生成矩阵 A
- 将 ρ 和 t1 打包并使用 SHAKE-256 哈希后,整体再和 M 哈希得到 384 位的消息摘要 μ
2️⃣ 计算 w1′
使用提示 h 恢复Az−ct1的高位部分 w1'。验证者计算
这只包含 Az 和 ct1 的高位部分,并使用 h 中包含的进位信息恢复 w1′
3️⃣ 验证判断
- z 的所有系数是否小于 γ1−β
- c 是否等于 H(M || w1′)
- 提示 h 中的 1 的数目是否超出限制 ω