基于椭圆曲线的ECC非对称密码系统

发表于 更新于 阅读次数： 本文字数： 2k 阅读时长 ≈ 7 分钟

一、概述

ECC（椭圆曲线密码学，Elliptic Curve Cryptography）是一种基于有限域上椭圆曲线的公开密钥加密算法。
与 RSA 加密算法相比，ECC的主要优势是使用较小的密钥长度并提供相当等级的安全性，另一个优势是可以定义群之间的双线性映射，基于 Weil 对或是 Tate 对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。

椭圆曲线在密码学中的使用是在1985年由 Neal Koblitz 和 Victor Miller 分别独立提出的。椭圆曲线密码学的算法是在2004年至2005年开始广泛应用。
目前主要有两种有限域在 ECC 中被广泛应用，分别基于素数域和伽罗瓦域。

二、基于素数域

方程式：$y^2=x^3+ax+b \mod p$
参数格式：$(p,a,b,G,n,h)$，其中$G$

  • 以素数为模的整数域: $\mathbb {F} _{p}$在通用处理器上计算很快
  • 以 2 的幂为模的整数域: $\mathbb {F} _{2^{m}}$当使用专用硬件时，计算速度很快

三、基于伽罗瓦域

  • 基于伽罗瓦域的形式：$y^2+xy=x^3+ax^2+1$
    曲线的参数格式：$(m,f(x),a,b,G,n,h)$，对应不同的$GF(2^m)$域

蒙哥马利曲线（Montgomery curve）是另一种形式的椭圆曲线，方程如下：
$by^2 = x^3 + ax^2 + x$

ECC

RFC 7748 收录了两种蒙哥马利曲线，分别是 Curve25519 和 Curve448。
Curve25519 是蒙哥马利曲线形式的一个实例， 声称是最快的 Diffie-Hellman 密钥交换函数，由 Daniel J. Bernstein 在2005年设计，提供128比特位安全性，并未被任何已知专利所涵盖。
Curve448 是 Mike Hamburg 在 2015 年设计的新曲线, 旨在提供 224 比特的安全性。
RFC 7748 同时给出了基于两条椭圆曲线的仅依赖 x 坐标的 ECDH 密钥交换协议 X25519 和 X448.

$(q,FR,a,b\{,SEED\},G,n,h)$，其中：

  • $q$：有限域的阶（元素的个数）。对于素数域，$q=p$；对于伽罗瓦域，$q=2^m$
  • $FR$：域表示。对于素数域，$FR$为空；对于伽罗瓦域，$q=2^m$
  • $a,b$：椭圆曲线方程的参数。
  • $SEED$：可选，用于生成和验证a、b以及可能的G(取决于生成方法)的规范过程。
  • $G$：生成点。是一个由 a 和 b 确定的点$(G_x,G_y)$。
  • $n$：生成点$G$的阶。
  • $h$：由$G$生成的循环子群的协因子。

其中，q为域的阶，FR为域表示，S为种子，a，b为椭圆曲线参数，P为基点，n为点P的阶，h为余因子；

自 。[17] 从 2014 年开始，OpenSSH[18] 默认为基于 Curve25519 的 ECDH，而 GnuPG 增加了对 Ed25519 密钥的支持，用于签名和加密。[19]2020年，曲线的使用最终在密钥交换和签名方面都实现了标准化。[20][21]

2017 年，NIST 宣布将 Curve25519 和 Curve448 添加到特别出版物 800-186 中，该出版物指定了供美国联邦政府使用的已批准的椭圆曲线。[22] 两者都在RFC 7748中进行了描述。[23] 2019 年“FIPS 186-5”草案指出，打算允许使用 Ed25519[24] 进行数字签名。2023 年特别出版物 800-186 的更新允许使用 Curve25519。[25]

  • 椭圆方程：$y^2 = x^3 + 486662x^2 + x$，即：a=486662，b=1
  • 有限域：$GF(2^{255}-19)$，也是名字中25519的由来
  • 基点 $x = 9$，阶数 $n = 2^{252} + 27742317777372353535851937790883648493$

Curve25519 的构造使其避免了许多潜在的实现缺陷。根据设计，它不受定时攻击的影响，并且它接受任何32字节的字符串作为有效的公钥，并且不需要验证。

本文重点关注 Curve25519 及相应的密钥交换协议 X25519. Curve25519 是定义在有限域
Fp, p = 2255 − 19 的蒙哥马利形式椭圆曲线 y
2 = x
3 + 486662x
2 + x, 其中曲线上点的个数
#E(Fp) = 8 · n1, 也即余因子为 8, 并且有
n1 = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed,

一次性迪菲-赫尔曼密钥交换协议

一次性迪菲-赫尔曼密钥交换协议（One-Pass Diffie-Hellman Key Agreement），定义在 NISP SP 800-56A 的 6.2.2.2 章节，名称为One-Pass Diffie-Hellman, C(1e,1s,ECC CDH) Scheme，含义是：

  • 密钥交换通过一次性的DH（Diffie-Hellman）协议，C 是指协因子（Cofactor）
  • 使用了1个临时密钥，1个静态密钥
  • 加密算法是椭圆曲线加密算法 ECC（Elliptic Curve Cryptography）

DH 协议最初采用 FFC 算法（Finite Field Cryptography，有限域加密），也称为幂等算法，安全强度较低
Curve 25519 使用蒙哥马利曲线：$y^2 = x^3 + 486662x^2 + x$
该曲线定义在由素数定义的素数场的二次扩展上，使用基点x = 9
这个基点的阶数是

蒙哥马利曲线（Montgomery curve）是另一种形式的椭圆曲线，方程如下：

onePassECCCDH

素数域$p = 2^{255}-19$，也是名字中25519的由来。

  • $p = 2^{255} − 19$
  • 域空间大小：q =
  • FR =
  • 参数：a = 486662
  • 参数：b = 1
  • 初始值（可选）：SEED = N/A
  • 生成元：G =
  • 辅因子：h = 8

对于Protected Unless Open的文件保护类型，分析其实现方案是：

1. 初始化存储介质的环节

  • 安全隔区随机生成一对非对称密钥（静态）
  • 静态私钥就是 Class B Key，包裹后的密文持久化存储在系统密钥包

2.（某个）文件创建的环节

  • 安全隔区随机生成一个文件独有密钥 per-file key
  • 安全隔区随机生成一对非对称密钥（临时），封装密钥 =（静态私钥，临时公钥），生成 per-file key！
  • 安全隔区将（临时公钥，per-file key！）发给操作系统
  • 操作系统创建 cnode 元数据，持久化存储 per-file key!，并增加了一个字段存储临时公钥
  • 安全隔区将 per-file key 发给 AES 引擎，实现文件内容的加密存储

临时私钥从为被使用？好像没有哪个文档提及其用途

3.（重新）打开文件的环节

  • 操作系统作从文件元数据中获得（临时公钥，per-file key！），并发送给安全隔区
  • 安全隔区以 Class B key 作为静态私钥，解封密钥 =（静态私钥，临时公钥），将 per-file key！解封为 per-file key
  • 安全隔区将 per-file key 发给 AES 引擎，实现文件内容的加密读写
  • 一旦该文件被关闭，安全隔区就在内存中丢弃 per-file key，该文件将无法读写

4. 用户重置passcode

理论上应有如下操作：

  1. 根据新的 passcode 重新执行 KDF 函数，生成新的 Class B key
  2. 找到所有数据保护类型为 Class B 的文件元数据，执行如下循环操作：
    • 解封密钥 =（旧的静态私钥，临时公钥），将 per-file key！恢复为 per-file key
    • 封装密钥 =（新的静态私钥，临时公钥），将 per-file key 封装为新的 per-file key！
    • 操作系统接受新的 per-file key！，并持久化存储在元数据 cnode 的 cprotect 字段
  3. 循环结束后，将新的 Class B key 持久化存储在系统钥匙包

静态私钥保存在 Class B key，但没有文档提及其用途和持久化存储位置，似乎被丢弃了
临时私钥的情况也是类似，而且似乎丢弃了也不影响算法的实现。。。

onePassECCCDH

参考文献

文档下载