今日币价

BTC：23000$

ETH：1600$

前言

随着web3的快速发展，区块链技术越来越成熟，作为程序员有必要了解区块链技术，区块链技术包含密码学，P2P网络，零知识证明等相关技术，从今天开始本人争取每周写一篇关于区块链相关的技术文章，目前主要集中在密码学相关的技术上，后续会陆续介绍其他模块。本文主要介绍在区块链中广泛应用的椭圆曲线加解密算法原理，由于本人水平有限，如有错误之处还请指正

数学基础

数学基础部分比较鼓噪无味，涉及到代数和群论相关的知识，如果对这部分不感兴趣可以直接跳过，只需要记住基本概念也可以理解椭圆曲线加解密的原理，不过还是建议读者看一下有利于理解椭圆曲线加解密的原理

• 模运算

定义：给定一个正整数p，任意一个整数n，一定存在等式 ：n = kp + r ；其中 k、r 是整数，且 0 r < p，则称 k 为 n 除以 p 的商，r 为 n 除以 p 的余数

同余式：正整数a，b对p取模，它们的余数相同，记做 a b (mod p)

逆元：ax 1 mod p, 则称a关于1模p的乘法逆元为x。也可表示为ax 1(mod p)

模运算加法，减法，乘法满足结合律，交换律，分配律，模除法比较特殊需要采用扩展欧几里德定理求解，有兴趣的读者可以自行搜索阅读

• 群

1、定义

如果一个非空集合上定义了一个二元运算 ，满足如下性质：

(1).封闭性：任意，则有

(2).结合性：任意,则有

(3).存在单位元：存在一个元素,使得任意,则有，单位元也叫幺元

(4).存在逆元：任意,存在,使得,e为单位元

则称集合以及二元运算构成一个群，记,也可以简化为通过上面群定义，我们可以很容易知道整数集合和加法构成群，但和乘法不构成群

半群：满足封闭性，结合性的群称为半群

幺半群：满足封闭性，结合性，存在幺元的群称为幺半群

阿贝尔群是一种特殊的群，除了满足普通群的四个公理，阿贝尔群还需要满足一个额外的公理：交换性即任意,则有，故阿尔贝群也叫交换群

2、阶

群中元素的个数称为群的阶，如元素个数无限，则称无限群，否则为有限群。群中的元素也定义了阶，对于任意,若有正整数，使得,其中是单位元，则称最小的m为的阶，若不存在，则的阶无限大

3、子群

给定集合,如果集合,且包含了单位元，同时中元素的逆元也在中，那么称为的子群

4、循环群

设为一个群，若存在一个内的元素,使得,则称为关于的循环群，叫做的生成元。

阶为质数的群都是循环群(拉格朗日定理)

• 环

环是一个具有两个二元运算（加法和乘法，这里加法和乘法并非初等代数的运算）的非空集合，也记为，其特性如下：

(1).是一个阿尔贝群

(2).是一个幺半群

(3).乘法对加法满足分配律：

交换环是在环的基础上也需要满足交换律

• 域

域在交换环的基础上对于非零元素都需要有乘法逆元，也就是需要是一个阿尔贝群

群，环，域关系图

椭圆曲线

• 定义

Wolfram MathWorld 给出了非常精准的定义：一条椭圆曲线就是一组被 定义的且满足 的集合。 这个限定条件是为了保证曲线不包含奇点(singularities). 这个方程称为椭圆曲线的维尔斯特拉斯标准形式（Weierstrass normal form）

是如何得出，这个涉及到导数相关的内容，不能有奇异点，则对x求导不能有重根

给出了椭圆曲线的定义之后，我们可以定义椭圆曲线上的阿贝尔群

(1).群中的元素就是椭圆曲线上的点

(2).单元元就是无穷远点，用表示

(3).逆元是关于x轴对称的点

(4).加法规则定义如下：取一条直线上的三点（这条直线和椭圆曲线相交的三点），（皆非零），他们的总和等于，

根据加法规则，P+Q+R=o，那么P+Q=-R，即P,Q两点相加交于第三点R，第三点R取x轴对称的点-R

P，Q相等，则点P的切线交于另外一点R再取x对称点-R

• 点乘

当P，Q两点相等时，点加则可以表示为P+Q=P+P=2P，当对点P重复点加n次，那么则可以表示为nP

• 离散对数

等式, 已知n,P计算G非常容易，已知G，P计算n非常困难（即离散对数难题）

读者有兴趣可以深入了解一下离散对数难题，本人还未深入了解，这里就不展开。椭圆曲线的加解密及签名功能主要是以离散对数难题和加法为基础

至此我们可以用如下表示椭圆曲线：

椭圆曲线密码学

• 有限域上椭圆曲线

实数域下的椭圆曲线并不适合加密，因为采用连续的数在加密过程中可能会出现计算偏差导致无法解密，而且CDH秘钥交换算法也需要循环群，所以椭圆曲线加密需要定义在有限域上，其定义如下：

公式太长编辑器无法处理，这里其实应该是

有限域上的椭圆曲线的点为离散的点

有限域上椭圆曲线的加法运算

在椭圆曲线加密算法中，我们一般是需要选择阶较大的曲线且需要找到一个循环子群适合加密，那么一条椭圆加密曲线可以表示为(p,a,b,G,n,h):

p: 模数，决定一个域

a,b:曲线参数

G:生成元

n:G的阶

h:辅因子，该参数表示曲线可以分割成多少个阶为n的循环子群，secp256k1为1，爱德华曲线为8

ECC加密属于非对称加密，也就是加密和解密用的是不同的秘钥，分别称为私钥和公钥，私钥是不能泄露的，公钥可以公开，基于上述椭圆曲线分析，我们在一个阶为n，G为生成元的循环子群里面随机选择一个数k作为私钥，kG作为公钥，根据离散对数难题，可以推出知道私钥很容易计算公钥，反之则非常困难

• ECDH秘钥交换

Alice与Bob想要进行通信，由于通信隧道并不安全需要双方协商秘钥进行信息加密

(1).Alice，Bob分别椭圆曲线（比如secp256k1）生成私钥和公钥，

(2).Alice将自己的公钥kG发送给Bob，Bob计算秘钥

(3).Bob将自己的公钥dG发送给Alice，Alice计算秘钥

(4).双方都采用作为会话秘钥

ECDH秘钥协商

ECDH秘钥交换并不能防中间人攻击，需要结合身份认证机制验证双方身份

• ECC加解密

加密的过程一般公钥加密私钥解密

私钥，公钥，消息m映射到椭圆曲线上的点

加密：随机生成,

解密：

• ECDSA签名

签名一般是采用私钥签名，公钥验证签名，为私钥，为公钥

签名：

(1).消息采用hash算法生成

(2).随机生成随机数()，计算

(3).计算mod 如果为0则跳回2

(4).计算mod，为私钥，如果为0则跳回2

(5).将作为签名发送给验证方

验证签名：

(1).验证，如果不是则签名无效

(2).消息采用hash算法生成

(3).计算mod ,mod

(4).计算,如果为无穷远点则签名无效

(5).如果mod 则签名有效，否则无效

算法推导正确性如下：,把带入方程则有

• 公钥恢复

对于给定的消息和签名是可以恢复出签名者的公钥的，步骤如下：

(1).验证，如果不是则签名无效

(2).针对每个等，根据椭圆曲线方程计算出

(3).消息采用hash算法生成

(4).计算mod ,mod

(5).计算

(6).用验证签名是否有效，如有效则为签名者的公钥

这里的（5）是否正确留给读者自行验证吧，跟验证签名其实是一样的过程

公钥恢复的过程需要针对（2）不断地尝试，需要取多少次取决于椭圆曲线的的值，同时对于每个取值计算的都有两个，这样也浪费计算资源，所以在比特币和以太坊的签名中都会多一个值,签名的形式一般是,这里的的取值范围是27-35表示x坐标是否大于以及y坐标的奇偶性

参考

• https://cryptobook.nakov.com/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc
• http://sparkandshine.net/algebraic-structure-primer-group-ring-field-vector-space/#31
• https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v
• https://www.fisco.com.cn/class_32/383.html
• https://blog.csdn.net/Professor_LT/article/details/101148114
• https://math.stackexchange.com/questions/1929289/why-4a327b20-iff-x3axb-0-has-exactly-three-solutions
• https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
• https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

声明

图片来源网络，侵删