写点什么

一场椭圆曲线的寻根问祖之旅

2020 年 2 月 26 日

一场椭圆曲线的寻根问祖之旅

本文介绍密码学中常见的椭圆曲线以及他们之间的关系,介绍不同标准体系的命名规则,尝试描述椭圆曲线之间的家族演义关系。文章试图讲清椭圆曲线相关概念和功能,不涉及复杂的数学证明和推理,欢迎感兴趣的同学阅读。


笔者主要参考 Wikipedia 和相关组织网站的信息进行整理,不排除出现纰漏的可能,欢迎专家批评指正。


一个可能你没关心过的问题

《一个数字引发的探索——ECDSA解析》中提到的椭圆曲线 secp256k1,它有一些特性,可以快速计算出 recoveryID。


这个 secp256k1 为什么如此命名?


不怕各位笑话,我在弄清楚它之前,经常拼写错,写成 sec256pk1,seck256p1 等。


咬文嚼字 secp256k1

搞清楚 secp256k1 的命名含义其实很简单,搜索引擎可以快速为你定位到答案,它出自一个密码协议标准,每一个字母和数字都代表着特定含义,我们来逐一解析。



1、密码协议标准

第一部分是「sec」,sec 是 Standards for Efficient Cryptography 的简称,是 SECG 发布的一种密码学协议标准。


SECG 发布的「SEC 1」和「SEC 2」两个关于椭圆曲线的协议标准,在「SEC 2」中有详细说明 secp256k1 以及其他曲线的参数定义。


除了「sec」,还有众多其他关于椭圆曲线的协议标准,从「SafeCurve」中可以看到有下列不同类型的标准。



「SafeCurve」此处较久没有更新,有些标准已经更新了多次,例如 NIST 关于数字签名的标准 FIPS 186 目前在用的是第四版,第五版也在起草中了,从「NIST」官网中可见。


NIST 是美国的国家标准技术研究所(National Institute of Standards and Technology),因此,NIST 的标准也是美国标准。



「NIST FIPS 186-4」标准中定义了若干椭圆曲线标准,例如 NIST P-256、NIST P-384 等,其中开头 NIST 也代表密码协议标准的名字。后续描述都是围绕这两个标准来解析。


2、有限域

第二部分是「p」,p 表示该椭圆曲线是基于素数有限域 Fp。有限域是离散数学中的概念,此处不做展开,简单来说,它是一个由有限数量元素组成的集合,元素之间可以进行加法和乘法计算,具备一些独特的属性。


密码学中使用椭圆曲线都是基于有限域的,除了素数有限域 Fp 之外,还有另一种特征为 2 的有限域 F2m(因格式问题,2m 应为 2 的 m 次方,下同) ,Fp 的大小(元素个数)为 p,F2m 的大小为 2m。


基于 Fp 的椭圆曲线为:



基于 F2m 的椭圆曲线为:



在「SEC 2」中还定义了 sect163k1、sect163r1 等曲线,其中,t 表示的是该曲线基于 F2m。在「NIST FIPS 186-4」中定了 P-256、B-163 等曲线,P-表示基于 Fp,B-表示基于 F2m。


3、有限域大小

每个椭圆曲线 E 都有若干关键参数,包括阶为 n 的基点 G 和系数 h 等,其中,n 为一个大素数,n*h 为椭圆曲线上点的数量。为了计算效率考虑,h 通常设置为 1、2 或 4。


通俗地讲,如果椭圆曲线上的点数量越多,那么这条椭圆曲线的安全度就越高,因此 n 的取值是影响曲线安全的关键。


椭圆曲线又都是基于有限域的,曲线上的点都是有限域中的元素,因此,有限域大小决定了曲线安全度。


第三部分「256」就是有限域大小的表现形式,还有更多其他如 192、224、384 等,在「NIST FIPS 186-4」中有个表格展现了 Fp 和 F2m 两个域的各种不同大小配置。



SEC 标准在这块的设置和 NIST 标准类似,我们会看到 p 系列的曲线有 p192、p224、p256(secp256k1 就是其中一种)、p384 和 p521,t/B 系列有 t163/B-163、t233/B-233 等。


4、Koblitz Curve

第四部分「k」表示该曲线是 Koblitz Curve,从「SEC 2」中可以看到还有此处标记为 r 的曲线(如 secp256r1),r 表示该曲线是伪随机曲线 Pesudo-Random Curve。


Koblitz Curve 命名源自数学家「Neal Koblitz」,它是一种特殊的曲线,它的一些参数是精心挑选设置的。Koblitz Curve 具有自同态的性质,可以通过优化大幅提升计算效率。


相比之下,Pesudo-Random Curve 的对应参数是通过随机种子计算出来的,有标准的检验算法可以检测所有参数是随机种子产生而来。


对应「2、有限域」中的两个椭圆曲线,Koblitz Curve 分别简化为:




例如,secp256k1 对应的曲线 b=7,即曲线表示为



在「NIST FIPS 186-4」中 Koblitz Curve 曲线以「K-」标记开头,分别有 K-163、K-233 等。


5、末位标记

到了第五部分「1」,这是代表在前 4 个条件下提供了多种推荐参数设置,在 SEC 标准中大部分该位都是 1,即只提供一种推荐参数,sect163r2 是一个例外。


下面把 SEC 和 NIST 两个标准推荐的曲线分别列一下,二者有较大部分是相同的参数设置。



上述表格中,同一行中 SEC 和 NIST 都出现的,两个曲线虽然名字不同,但参数完全相同,也就是说其实一样的。


橙色底纹的几个 SEC 曲线没有对应的 NIST 曲线,因此 SEC 标准包含的曲线比 NIST 多一些,本文开头提到的 secp256k1 就是 SEC 单独存在的。


说到这里,不得不提一个正经八卦。据说,NIST 推荐的 Pesudo-Random Curve,也就是 P 和 B 系列,并没有公布随机数挑选规则,外界存在一种疑虑,可能 NSA(美国国家安全局)掌握了后门,能够轻易破解这些密码协议。


有兴趣的同学可以搜索「Dual_EC_DRBG 后门」,更大的八卦是据说中本聪选择 secp256k1 作为比特币签名算法的曲线,而没有选择更常用的 secp256r1,也是因为这个潜藏的风险。


椭圆曲线族谱

调研发现,「STD」记录了比「SafeCurve」更为详细的标准和曲线,感觉这可以算是椭圆曲线族谱了。翻阅该网站记录的所有曲线,发现绝大部分还是基于「(2)有限域」中的曲线,推荐的参数不同而已。


但是,在「other」中存在几种例外,E-222 采用 Edward Curve,Curve25519 采用 Montgomery Curve,Ed448 采用 Twisted Edward Curve。


Edward Curve 是什么?Montgomery Curve 又是怎样的?Edward 与 Twisted Edward Curve 又有什么关系?


上述问题再一次触碰到我的知识盲区,所以接下来只好以截图为主,内容源自 Wikipedia,如果觉得看着有点晕,可直接跳过看结论。


「Edward Curve」定义如下:



「Montgomery Curve」定义如下:



「Twisted Edward Curve」定义如下:



「Curve25519」定义如下:



「Ed25519」的定义如下:



根据 Wikipedia,大概可以整理出这么几个信息:


  • Edward Curve 是 Twisted Edward Curve 中的一种;

  • Twisted Edward Curve 和 Montgomery Curve 可以互相转换;

  • Edward Curve 和 Montgomery Curve 这两种曲线都具有特殊属性,例如能够为计算加速;

  • Curve25519 是一种曲线,Ed25519 是一种签名算法;

  • Curve25519 又是精选的 Montgomery Curve,具有更高的计算效率;

  • Curve25519 和 Ed25519 采用的曲线是一致的,一个是 Montgomery 表现形式,一个是 Twisted Edward Curve 表现形式;

  • 25519 的取名来自于该曲线的有限域参数 p=2 的 225 次方-19;


在阅读 Wikipedia 的过程中发现一个名字「Weierstrass equation」,原来它才是这些曲线的鼻祖,在一个域 k 上的任何一个平面曲线,都可以表示成 Weierstrass equation。



不难发现,前面提到过的各个公式都是 Weierstrass equation 的一种演化版本(Twisted Edward Curve 看起来不是,但是它可以转换到 Montgomery Curve,本质上也一样)


到此,为椭圆曲线寻根问到祖,并且从「STD」也获知了椭圆曲线家族的族谱。


「STD」中罗列了多个其他标准,例如 Brainpool 曲线系列、BN 曲线系列、MNT 曲线系列等,这些系列的背后都代表了一种独特的曲线生成哲学,或是为了提供可验证的随机数,或是为了提供满足 Paring 的特性,或是为了提高抗攻击的能力等等,每一份精心选择的参数都是一群数学家们巧夺天工的设计。


后话

古有拆文解字,参透汉字玄机,道破人生天机;


而今咬文嚼字,摸清椭圆原理,揭开曲线家谱。


始于名字,解码 secp256k1,厘清标准;


终于名字,问祖 weierstrass,致敬大神。


通过了解椭圆曲线之间的内在关系,对其设计有了更多一点的理解。知道的更多了,不知道的也更多了,那些特殊曲线的数学原理是什么?为什么具有更高的计算效率?性能能提升多少?…


又是一个深夜,拥抱最新的收获,夹杂更多的困惑。电脑中正好在播放“把太细的神经割掉,会不会比较睡得着…”


作者简介

李辉忠,FISCO BCOS 高级架构师,微众银行区块链底层平台研发负责人。


参考资料

SEC1 :


https://www.secg.org/sec1-v2.pdf


SEC2:


https://www.secg.org/sec2-v2.pdf


NIST:


https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf


STD:


https://neuromancer.sk/std/


SafeCurves:


https://safecurves.cr.yp.to


Koblitz Curves:


https://link.springer.com/content/pdf/10.1007%2F3-540-46766-1_22.pdf


Weierstrass Equation:


https://www.lmfdb.org/knowledge/show/ec.weierstrass_coeffs


Montgomery Curve wiki:


https://en.wikipedia.org/wiki/Montgomery_curve


Twisted Edward Curve wiki:


https://en.wikipedia.org/wiki/Twisted_Edwards_curve


Edward Curve wiki:


https://en.wikipedia.org/wiki/Twisted_Edwards_curve


ECDSA wiki:


https://en.wikipedia.org/wiki/EdDSA#Ed25519


Curve25519 wiki:


https://en.wikipedia.org/wiki/Curve25519


Curve25519 paper:


http://cr.yp.to/ecdh/curve25519-20060209.pdf


Ed25519 paper:


http://ed25519.cr.yp.to/ed25519-20110926.pdf


2020 年 2 月 26 日 14:481585

评论 1 条评论

发布
用户头像
敬佩作者刨根问底的精神!
2020 年 06 月 03 日 09:55
回复
没有更多了
发现更多内容

前端面试vue部分(1)——谈谈你对MVVM的理解

dd多了个多

Vue 前端 Web 前端面试

应用开发基础知识-文件系统

superman

文件系统

百度安全研究院:区块链智能合约介绍

百度安全

比特币 区块链 智能合约 以太坊

消息队列面试热点一锅端

yes的练级攻略

kafka RocketMQ 面试题 消息队列

Kafka集群缩容实战

大数据学徒

大数据 kafka 运维 Big Data

微服务架构下的核心话题 (一):微服务架构下各类项目的顺势崛起

xcbeyond

架构 微服务

架构训练营第九周作业

张锐

第九周作业

andy

极客大学

秒杀系统的挑战和应对方案

2流程序员

LeetCode题解:189. 旋转数组,3次翻转,JavaScript,详细注释

Lee Chen

LeetCode 前端进阶训练营

架构师训练营第九章作业

叮叮董董

秒杀系统的架构设计

莫莫大人

总结

chenzt

JVM 垃圾回收原理

周冬辉

秒杀系统设计初稿

jason

《深度工作》学习笔记(4)

石云升

学习 读书笔记 习惯 专注 深度工作

前端面试 vue 部分 (2)——Vue是如何实现双向绑定的

dd多了个多

Vue Web 前端开发 前端面试

起伏激荡的以太网,抱上这条大腿才能乘风破浪

脑极体

关于微信电子发票生态,这三种服务商最有机会

诸葛小猿

电子发票 发票

1.8w字 | 初中级前端 JavaScript 自测清单 - 2

pingan8787

Java 前端 web前端

第九周总结

andy

当面试官问我ArrayList和LinkedList哪个更占空间时,我这么答让他眼前一亮

鄙人薛某

Java 面试 集合 面试题 java基础

Elasticsearch从入门到放弃:瞎说Mapping

Jackey

elasticsearch

大厂的人才衡量标准

池建强

人才标准

【第九周作业】

Aldaron

垃圾回收

Mr.Monkey

架构师训练营第9周

大丁💸💵💴💶🚀🐟

架构师训练营第九章总结

叮叮董董

架构师训练营 - 第九周 - 作业

韩挺

Atlassian 重磅推出12个新功能为您打造全新 DevOps 体验!

Atlassian

项目管理 DevOps Atlassian Jira

JVM学习总结

jason

2021年全国大学生计算机系统能力大赛操作系统设计赛 技术报告会

2021年全国大学生计算机系统能力大赛操作系统设计赛 技术报告会

一场椭圆曲线的寻根问祖之旅-InfoQ