从零开始学习椭圆曲线密码学 - 初学者友好版
想象你想给朋友发送一条秘密信息，但中间有个坏人可能会偷看。密码学就是解决这个问题的三个魔法：
你用一把锁（加密密钥）把消息锁进一个盒子里。坏人看不懂盒子里的内容。
明文信息 + 密钥 → 密文（乱码）
"Hello" + 锁 → "xK#@9$2L"
只有拥有钥匙（解密密钥）的朋友才能打开盒子看到真实消息。
密文（乱码） + 钥匙 → 明文信息
"xK#@9$2L" + 钥匙 → "Hello"
你用你的私人印章给信息盖章，别人可以用你的公开印章验证器验证这个盖章确实来自你。
消息 + 私人印章 → 签名
"Hello" + 你的签名 → "Sign:abc123"
别人用你的验证器验证 → "确实来自你！"
直观理解：想象一个圆形的时钟。
12点
11点 | 1点
10点 | | 2点
-----+-----
9点 | | 3点
8点 | 4点
7点 5点
6点
在模12的世界里：
- 13 mod 12 = 1（13点 = 下午1点）
- 25 mod 12 = 1（25点 = 下午1点）
- 15 mod 12 = 3（15点 = 下午3点）
公式：a mod n = a 除以 n 的余数
例子：
17 mod 5 = 2 （17 = 3×5 + 2）
23 mod 7 = 2 （23 = 3×7 + 2）
100 mod 13 = 9 （100 = 7×13 + 9）
为什么重要？ 在密码学中，我们使用巨大的素数作为模（比如 2^256），这样计算就会循环，但很难反推。
素数：只能被 1 和自己整除的数
素数：2, 3, 5, 7, 11, 13, 17, 19, 23, ...
非素数：4, 6, 8, 9, 10, 12, ...
互质（互质数）：两个数的最大公约数是1
3 和 7 互质 （gcd(3,7) = 1）
6 和 9 不互质 （gcd(6,9) = 3）
问题：在模 n 的世界里，如何"除法"？
答案：找到一个数的乘法逆元
例子：在模11的世界里，3的逆元是4，因为：
3 × 4 ≡ 12 ≡ 1 (mod 11)
↑ 余数是1（模11）
为什么重要？
- 签名时需要计算
k^(-1)（k的逆元） - 没有逆元的计算就无法进行
密码学中的数字非常大：
256位数字的范围：
最小: 1
最大: 115792089237316195423570985008687907853269984665640564039457584007913129639935
这是一个78位的十进制数！
bECCsh 如何处理？
用纯 Bash 字符串进行逐位运算：
# 例子：计算 123 + 456（字符串方式）
# 从右到左逐位相加，处理进位
123
+ 456
-----
579数学定义（别被吓到）：
y² ≡ x³ + ax + b (mod p)
人类语言解释：
这是一条曲线，满足一个特定的数学方程。在实数平面上，它看起来像这样：
y
↑
/ | \
/ | \
/ | \
| | |
| | | ← 椭圆曲线的形状
| | |
| | |
\ | /
\ | /
\ | /
----+---- → x
关键特性：
- 关于x轴对称
- 很多现实密码学应用都用这条曲线
- 在模 p（一个大素数）下工作
在椭圆曲线上，点就是满足方程的 (x, y) 对。
例子：secp256r1 曲线的一个点
点 G（基点）的坐标：
x = 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
y = 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
（这些是十六进制的超大数字）
直观理解：
想象在曲线上，如果从某个点 P 向上画一条竖直线，会发现：
- 在某处与曲线相交一次（点 P 本身）
- 在另一处相交（点 -P）
- 还有一个"看不见"的交点：无穷远点 ∞
y
↑
| P
| /
|/
----+---- x
/|
/ |
-P |
| ∞(看不见的点，在无穷远处)
性质：
- ∞ 是"加法的身份元素"：P + ∞ = P
- 这就像普通数学中的 0：a + 0 = a
问题：如何在曲线上"加"两个点？
答案：用几何方法！
y
↑
| P •
| ╱
|╱___
•──────•─── x
R Q
步骤：
- 找出过 P 和 Q 的直线
- 这条直线会与曲线相交第三点 R'
- P + Q 的结果 = R' 的镜像点 R（关于x轴对称）
公式：
λ = (y₂ - y₁) / (x₂ - x₁) ← 直线的斜率
x₃ = λ² - x₁ - x₂ ← 第三个点的x坐标
y₃ = λ(x₁ - x₃) - y₁ ← 镜像后的y坐标
y
↑
| P •
| ╱ ← 在P处的切线
| ╱
|╱
----+---- x
|
R' |
| ← 镜像
R •
步骤：
- 在点 P 处画切线（而不是连接两点的直线）
- 切线与曲线交于 R'
- P + P 的结果 = R' 的镜像点 R
公式（求切线斜率）：
λ = (3x₁² + a) / (2y₁) ← 在P处的切线斜率（微积分）
x₃ = λ² - 2x₁ ← 结果的x坐标
y₃ = λ(x₁ - x₃) - y₁ ← 结果的y坐标
具体例子（使用小数字）：
曲线：y² = x³ - 3x + 7（在整数上）
点 P = (1, 2)，点 Q = (2, 3)
λ = (3 - 2) / (2 - 1) = 1/1 = 1
x₃ = 1² - 1 - 2 = -2
y₃ = 1(1 - (-2)) - 2 = 1 × 3 - 2 = 1
结果：P + Q = (-2, 1)
问题：如何计算 k×P（k是一个数字）？
简单（但慢）的方法：
5 × P = P + P + P + P + P
只需加5次！
聪明（快速）的方法：二进制展开法
想要计算 5 × P
首先，5 的二进制是：101₂
所以：5 × P = 1×2²×P + 0×2¹×P + 1×2⁰×P
= 4×P + 0 + P
= 4P + P
步骤：
result = ∞
遍历二进制位（从最高位到最低位）：
位5（从左）：二进制位=1
result = 2 × result + P = P
位4：二进制位=0
result = 2 × result = 2P
位3：二进制位=1
result = 2 × result + P = 5P ✓
为什么快？
- 直接方法需要 k 次加法
- 二进制方法只需要约 2log₂(k) 次操作（约2倍的位数）
对于256位数：
- 直接：2^256 次加法（不可能！）
- 二进制：约 512 次加法（可行！）
流程：
1️⃣ 生成随机数
Random number generator
↓
d（私钥）← 范围：1 到 n-1
2️⃣ 计算公钥
Q = d × G
（用 d 乘以基点 G）
↓
得到公钥：Q = (x, y)
私钥 vs 公钥：
| 特性 | 私钥 d | 公钥 Q |
|---|---|---|
| 长度 | 256位数字 | 坐标对(x, y) |
| 谁知道 | 只有你 | 全世界都知道 |
| 用途 | 签名、解密 | 验证签名、加密 |
| 安全性 | ⭐⭐⭐⭐⭐ 极度机密 | ⭐ 完全公开 |
| 泄露后果 | 灾难性 | 无关紧要 |
例子：
步骤1：生成私钥
d = 112233445566778899001122334455667788990011223344556677889900112233（256位）
步骤2：计算公钥（d × G）
Q = d × G
Q = (
48439561293906451759052585252797914202762949526041747995844080717082404635286,
36134250956749795798585127919587881956611106672985015071877198253596914405109
)
单向性问题：
从私钥 d 计算公钥 Q = d×G 很简单（几秒钟）
但反过来，从公钥 Q 计算私钥 d 非常困难（需要数千年）
这称为椭圆曲线离散对数问题：
正向：d → Q = d×G ✓ 简单、快速
逆向：Q → d = log_G(Q) ✗ 困难、缓慢
为什么这么困难？
对于256位椭圆曲线，可能的 d 值有 2^256 个（约 10^77）
要全部尝试需要：
- 按照美国能源部的计算，约需 1000 万年
- 用全球所有计算机一起计算，仍需 1000 年
日常类比：
想象你寄一份信，你在信上签名。接收者可以：
- ✓ 确认签名来自你（真实性）
- ✓ 确认信没被篡改（完整性）
- ✓ 你无法否认签过名（不可否认性）
数字签名也是这样，但用数学实现。
消息 "我转账100元给Bob"
↓
📝 步骤1：计算消息摘要
使用 SHA-256 哈希函数
h = SHA256("我转账100元给Bob")
h = "abc123def456..."（256位哈希值）
↓
🔑 步骤2：生成随机数 k
k = 随机选择（1到n-1之间）
k = "xyz789..."
↓
🎯 步骤3：计算签名的第一部分 r
计算点：(x₁, y₁) = k × G
r = x₁ mod n
r = "sig_part_1"
↓
🔐 步骤4：计算签名的第二部分 s
s = k⁻¹ × (h + d × r) mod n
其中：
- k⁻¹ = k 的模逆元
- d = 你的私钥
- h = 消息摘要
s = "sig_part_2"
↓
✍️ 签名完成！
签名 = (r, s)
任何人都可以验证（使用你的公钥）：
收到：消息 + 签名(r, s) + 你的公钥 Q
↓
📝 步骤1：计算消息摘要（同样的哈希）
h = SHA256("我转账100元给Bob")
↓
🔍 步骤2：计算验证值 w
w = s⁻¹ mod n
（s 的模逆元）
↓
✔️ 步骤3：计算两个中间点
u₁ = h × w mod n
u₂ = r × w mod n
↓
🎯 步骤4：计算验证点
(x₁, y₁) = u₁ × G + u₂ × Q
其中 + 是椭圆曲线点加法
↓
✅ 步骤5：验证
if (x₁ mod n == r) {
✓ 签名有效！（消息未被篡改，确实来自该私钥的所有者）
} else {
✗ 签名无效！（被篡改或者不是该私钥签的）
}
如果签名生成正确：
s = k⁻¹(h + dr) mod n
两边乘以 k：
ks = h + dr mod n
重新排列：
h = ks - dr mod n
验证时：
u₁G + u₂Q
= (hw)G + (rw)Q
= (hw)G + (rw)(dG) （Q = dG）
= (hw + rwd)G
= w(h + rd)G
= w(ks)G （h + rd = ks）
= kG （w = s⁻¹，所以ws = 1）
所以 x₁（kG的x坐标）确实等于 r！✓
Bitcoin 地址生成：
私钥 d ──→ 公钥 Q ──→ 哈希 ──→ 比特币地址
交易签名：
消息（转账） ──→ 签名(r,s) ──→ 网络广播
接收者验证：
签名(r,s) + 公钥 + 消息 ──→ 验证器 ──→ ✓/✗
你访问网站：
1. 网站发送公钥给你
2. 你用公钥加密密码
3. 网站用私钥解密
4. 建立安全连接
开发者发布软件：
1. 计算软件的哈希
2. 用私钥签名
3. 用户用公钥验证
4. 确保软件未被篡改
用途：NIST推荐，最常用，被美国政府采用
| 参数 | 值 |
|---|---|
| 素数 p | 2²²⁴(2³²-1)+2¹⁹²+2⁹⁶-1 |
| 曲线参数 a | -3 |
| 曲线参数 b | 41058363725... (很长) |
| 阶 n | 115792089210... (约115 × 10³⁶) |
| 安全级别 | 128位 |
适合场景：
- ✓ 政府应用
- ✓ TLS/SSL
- ✓ 需要审计的系统
用途：比特币和以太坊采用
| 参数 | 值 |
|---|---|
| 素数 p | 2²⁵⁶ - 2³² - 977 |
| 曲线参数 a | 0（简化） |
| 曲线参数 b | 7 |
| 阶 n | 115792089237... |
| 安全级别 | 128位 |
适合场景：
- ✓ 区块链应用
- ✓ 加密货币
- ✓ 去中心化系统
secp256r1 vs secp256k1：
相似点：都是256位，安全级别相同
区别：
- secp256r1 是官方标准（NIST）
- secp256k1 有特殊数学性质，适合比特币
- secp256k1 略快一点（参数简化）
用途：需要更高安全级别
| 参数 | 值 |
|---|---|
| 密钥长度 | 384位 |
| 安全级别 | 192位 |
| 计算速度 | 慢于256位 |
适合场景：
- ✓ 长期存储的关键数据
- ✓ 政府分类信息
- ✓ 需要持久安全性的系统
A: 模运算让密码学成为可能：
- 没有mod，数字会无限增长，计算时间无限长
- 用mod，数字被限制在 0 到 p-1，计算有限且可预测
A: 理论上：不可能（需要破解ECC离散对数问题） 实际上：不可能（即使所有计算机一起工作1000年）
A: 非常重要！ 这是一个致命的漏洞：
- 如果同一个k用于两个不同的消息签名
- 攻击者可以计算出你的私钥
- 这就是为什么 RFC 6979 使用"确定性k"（从消息推导k）
| 方法 | 密钥大小 | 签名大小 | 速度 | 安全性 |
|---|---|---|---|---|
| ECDSA | 256位 | 512位 | 快 | 128位 |
| RSA | 2048位 | 2048位 | 慢 | 112位 |
| EdDSA | 256位 | 512位 | 快 | 128位 |
结论：ECDSA 用更小的密钥实现相同的安全性。
A: 很慢（预期内）！
OpenSSL: 签名 0.01 秒
bECCsh: 签名 380 秒
倍数: 38000× 倍慢
为什么?
- Bash 不是为密码学优化
- 每个数学操作都用字符串完成
- 纯Bash没有硬件加速
但!
- 完全纯Bash实现
- 零外部依赖
- 100% 可读和审查
✓ 可以：
- 学习和教学
- 理解算法原理
- 小规模概念验证
- 资源受限的嵌入式系统
✗ 不可以：
- 生产加密应用
- 高频交易系统
- 实时金融交易
- 需要快速响应的系统
1. 椭圆曲线 = 特殊的数学曲线
2. 曲线上的点 = 密钥和签名的基础
3. 点加法 = 椭圆曲线"算术"的操作
4. 标量乘法 = 快速计算大数点乘
5. 离散对数困难 = 密钥安全的数学基础
6. ECDSA = 使用上述所有概念的签名算法
好的随机数 d
↓
私钥 d（秘密保管）
↓
计算公钥 Q = d×G
↓
使用 d 签名消息
↓
用 Q 验证签名
↓
完整的数字签名系统
RSA: 2048位密钥 = 112位安全性
ECC: 256位密钥 = 128位安全性
ECC 赢了！
- 密钥小 → 传输快
- 计算快 → 更节能
- 签名小 → 空间小
-
可视化工具
- 在线椭圆曲线可视化：https://www.desmos.com/
- 搜索 "elliptic curve" 看动画
-
官方标准
- SEC 2: Recommended Elliptic Curve Domain Parameters
- FIPS 186-4: Digital Signature Standard
-
精妙的解释
- "Andrea Corbellini" 的 ECC 教程（英文，非常清晰）
- YouTube 上搜索 "Elliptic Curve Cryptography"
-
数学深度
- Guide to Elliptic Curve Cryptography
- 作者：Hankerson, Menezes, Vanstone
| 术语 | 简单解释 |
|---|---|
| 模运算 | 取余数运算（a mod n） |
| 素数 | 只能被1和自己整除的数 |
| 逆元 | 在模运算中的"倒数" |
| 椭圆曲线 | 满足 y²=x³+ax+b 的曲线 |
| 基点 G | 曲线上的参考点 |
| 私钥 d | 你的秘密数字 |
| 公钥 Q | d×G，公开的点坐标 |
| 签名 | 两个数字(r, s)，证明你的身份 |
| 哈希 | 任意大小数据→固定大小摘要 |
| DLP | 离散对数问题（ECC的数学基础） |
本指南旨在让任何人都能理解椭圆曲线密码学的原理。即使你从未学过高等数学，也能通过这个指南了解 bECCsh 的原理。
🚀 现在你已准备好探索 bECCsh 的代码了！